0
|
1 /*
|
|
2 * Copyright 2002 Sun Microsystems, Inc. All Rights Reserved.
|
|
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
|
|
4 *
|
|
5 * This code is free software; you can redistribute it and/or modify it
|
|
6 * under the terms of the GNU General Public License version 2 only, as
|
|
7 * published by the Free Software Foundation.
|
|
8 *
|
|
9 * This code is distributed in the hope that it will be useful, but WITHOUT
|
|
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
12 * version 2 for more details (a copy is included in the LICENSE file that
|
|
13 * accompanied this code).
|
|
14 *
|
|
15 * You should have received a copy of the GNU General Public License version
|
|
16 * 2 along with this work; if not, write to the Free Software Foundation,
|
|
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
|
|
18 *
|
|
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
|
|
20 * CA 95054 USA or visit www.sun.com if you need additional information or
|
|
21 * have any questions.
|
|
22 *
|
|
23 */
|
|
24
|
|
25 package sun.jvm.hotspot.debugger;
|
|
26
|
|
27 import java.util.*;
|
|
28
|
|
29 /**
|
|
30 * This is a copy of java.util.HashMap which uses longs as keys
|
|
31 * instead of Objects. It turns out that using this in the PageCache
|
|
32 * implementation speeds up heap traversals by a factor of three.
|
|
33 *
|
|
34 * @author Josh Bloch
|
|
35 * @author Arthur van Hoff
|
|
36 */
|
|
37
|
|
38 public class LongHashMap
|
|
39 {
|
|
40 static class Entry {
|
|
41 private int hash;
|
|
42 private long key;
|
|
43 private Object value;
|
|
44 private Entry next;
|
|
45
|
|
46 Entry(int hash, long key, Object value, Entry next) {
|
|
47 this.hash = hash;
|
|
48 this.key = key;
|
|
49 this.value = value;
|
|
50 this.next = next;
|
|
51 }
|
|
52
|
|
53 /**
|
|
54 * Returns the key corresponding to this entry.
|
|
55 *
|
|
56 * @return the key corresponding to this entry.
|
|
57 */
|
|
58 long getKey() { return key; }
|
|
59
|
|
60 /**
|
|
61 * Returns the value corresponding to this entry. If the mapping
|
|
62 * has been removed from the backing map (by the iterator's
|
|
63 * <tt>remove</tt> operation), the results of this call are undefined.
|
|
64 *
|
|
65 * @return the value corresponding to this entry.
|
|
66 */
|
|
67 Object getValue() { return value; }
|
|
68
|
|
69 /**
|
|
70 * Replaces the value corresponding to this entry with the specified
|
|
71 * value (optional operation). (Writes through to the map.) The
|
|
72 * behavior of this call is undefined if the mapping has already been
|
|
73 * removed from the map (by the iterator's <tt>remove</tt> operation).
|
|
74 *
|
|
75 * @param value new value to be stored in this entry.
|
|
76 * @return old value corresponding to the entry.
|
|
77 *
|
|
78 * @throws UnsupportedOperationException if the <tt>put</tt> operation
|
|
79 * is not supported by the backing map.
|
|
80 * @throws ClassCastException if the class of the specified value
|
|
81 * prevents it from being stored in the backing map.
|
|
82 * @throws IllegalArgumentException if some aspect of this value
|
|
83 * prevents it from being stored in the backing map.
|
|
84 * @throws NullPointerException the backing map does not permit
|
|
85 * <tt>null</tt> values, and the specified value is
|
|
86 * <tt>null</tt>.
|
|
87 */
|
|
88 Object setValue(Object value) {
|
|
89 Object oldValue = this.value;
|
|
90 this.value = value;
|
|
91 return oldValue;
|
|
92 }
|
|
93
|
|
94 /**
|
|
95 * Compares the specified object with this entry for equality.
|
|
96 * Returns <tt>true</tt> if the given object is also a map entry and
|
|
97 * the two entries represent the same mapping. More formally, two
|
|
98 * entries <tt>e1</tt> and <tt>e2</tt> represent the same mapping
|
|
99 * if<pre>
|
|
100 * (e1.getKey()==null ?
|
|
101 * e2.getKey()==null : e1.getKey().equals(e2.getKey())) &&
|
|
102 * (e1.getValue()==null ?
|
|
103 * e2.getValue()==null : e1.getValue().equals(e2.getValue()))
|
|
104 * </pre>
|
|
105 * This ensures that the <tt>equals</tt> method works properly across
|
|
106 * different implementations of the <tt>Map.Entry</tt> interface.
|
|
107 *
|
|
108 * @param o object to be compared for equality with this map entry.
|
|
109 * @return <tt>true</tt> if the specified object is equal to this map
|
|
110 * entry.
|
|
111 */
|
|
112 public boolean equals(Object o) {
|
|
113 if (!(o instanceof Entry))
|
|
114 return false;
|
|
115 Entry e = (Entry)o;
|
|
116 return (key == e.getKey()) && eq(value, e.getValue());
|
|
117 }
|
|
118
|
|
119 /**
|
|
120 * Returns the hash code value for this map entry. The hash code
|
|
121 * of a map entry <tt>e</tt> is defined to be: <pre>
|
|
122 * (e.getKey()==null ? 0 : e.getKey().hashCode()) ^
|
|
123 * (e.getValue()==null ? 0 : e.getValue().hashCode())
|
|
124 * </pre>
|
|
125 * This ensures that <tt>e1.equals(e2)</tt> implies that
|
|
126 * <tt>e1.hashCode()==e2.hashCode()</tt> for any two Entries
|
|
127 * <tt>e1</tt> and <tt>e2</tt>, as required by the general
|
|
128 * contract of <tt>Object.hashCode</tt>.
|
|
129 *
|
|
130 * @return the hash code value for this map entry.
|
|
131 * @see Object#hashCode()
|
|
132 * @see Object#equals(Object)
|
|
133 * @see #equals(Object)
|
|
134 */
|
|
135 public int hashCode() {
|
|
136 return hash ^ (value==null ? 0 : value.hashCode());
|
|
137 }
|
|
138 }
|
|
139
|
|
140 /**
|
|
141 * The hash table data.
|
|
142 */
|
|
143 transient Entry table[];
|
|
144
|
|
145 /**
|
|
146 * The total number of mappings in the hash table.
|
|
147 */
|
|
148 transient int size;
|
|
149
|
|
150 /**
|
|
151 * The table is rehashed when its size exceeds this threshold. (The
|
|
152 * value of this field is (int)(capacity * loadFactor).)
|
|
153 *
|
|
154 * @serial
|
|
155 */
|
|
156 int threshold;
|
|
157
|
|
158 /**
|
|
159 * The load factor for the hash table.
|
|
160 *
|
|
161 * @serial
|
|
162 */
|
|
163 final float loadFactor;
|
|
164
|
|
165 /**
|
|
166 * The number of times this HashMap has been structurally modified
|
|
167 * Structural modifications are those that change the number of mappings in
|
|
168 * the HashMap or otherwise modify its internal structure (e.g.,
|
|
169 * rehash). This field is used to make iterators on Collection-views of
|
|
170 * the HashMap fail-fast. (See ConcurrentModificationException).
|
|
171 */
|
|
172 transient int modCount = 0;
|
|
173
|
|
174 /**
|
|
175 * Constructs a new, empty map with the specified initial
|
|
176 * capacity and the specified load factor.
|
|
177 *
|
|
178 * @param initialCapacity the initial capacity of the HashMap.
|
|
179 * @param loadFactor the load factor of the HashMap
|
|
180 * @throws IllegalArgumentException if the initial capacity is less
|
|
181 * than zero, or if the load factor is nonpositive.
|
|
182 */
|
|
183 public LongHashMap(int initialCapacity, float loadFactor) {
|
|
184 if (initialCapacity < 0)
|
|
185 throw new IllegalArgumentException("Illegal Initial Capacity: "+
|
|
186 initialCapacity);
|
|
187 if (loadFactor <= 0 || Float.isNaN(loadFactor))
|
|
188 throw new IllegalArgumentException("Illegal Load factor: "+
|
|
189 loadFactor);
|
|
190 if (initialCapacity==0)
|
|
191 initialCapacity = 1;
|
|
192 this.loadFactor = loadFactor;
|
|
193 table = new Entry[initialCapacity];
|
|
194 threshold = (int)(initialCapacity * loadFactor);
|
|
195 }
|
|
196
|
|
197 /**
|
|
198 * Constructs a new, empty map with the specified initial capacity
|
|
199 * and default load factor, which is <tt>0.75</tt>.
|
|
200 *
|
|
201 * @param initialCapacity the initial capacity of the HashMap.
|
|
202 * @throws IllegalArgumentException if the initial capacity is less
|
|
203 * than zero.
|
|
204 */
|
|
205 public LongHashMap(int initialCapacity) {
|
|
206 this(initialCapacity, 0.75f);
|
|
207 }
|
|
208
|
|
209 /**
|
|
210 * Constructs a new, empty map with a default capacity and load
|
|
211 * factor, which is <tt>0.75</tt>.
|
|
212 */
|
|
213 public LongHashMap() {
|
|
214 this(11, 0.75f);
|
|
215 }
|
|
216
|
|
217 /**
|
|
218 * Returns the number of key-value mappings in this map.
|
|
219 *
|
|
220 * @return the number of key-value mappings in this map.
|
|
221 */
|
|
222 public int size() {
|
|
223 return size;
|
|
224 }
|
|
225
|
|
226 /**
|
|
227 * Returns <tt>true</tt> if this map contains no key-value mappings.
|
|
228 *
|
|
229 * @return <tt>true</tt> if this map contains no key-value mappings.
|
|
230 */
|
|
231 public boolean isEmpty() {
|
|
232 return size == 0;
|
|
233 }
|
|
234
|
|
235 /**
|
|
236 * Returns the value to which this map maps the specified key. Returns
|
|
237 * <tt>null</tt> if the map contains no mapping for this key. A return
|
|
238 * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
|
|
239 * map contains no mapping for the key; it's also possible that the map
|
|
240 * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
|
|
241 * operation may be used to distinguish these two cases.
|
|
242 *
|
|
243 * @return the value to which this map maps the specified key.
|
|
244 * @param key key whose associated value is to be returned.
|
|
245 */
|
|
246 public Object get(long key) {
|
|
247 Entry e = getEntry(key);
|
|
248 return (e == null ? null : e.value);
|
|
249 }
|
|
250
|
|
251 /**
|
|
252 * Returns <tt>true</tt> if this map contains a mapping for the specified
|
|
253 * key.
|
|
254 *
|
|
255 * @return <tt>true</tt> if this map contains a mapping for the specified
|
|
256 * key.
|
|
257 * @param key key whose presence in this Map is to be tested.
|
|
258 */
|
|
259 public boolean containsKey(long key) {
|
|
260 return getEntry(key) != null;
|
|
261 }
|
|
262
|
|
263 /**
|
|
264 * Returns the entry associated with the specified key in the
|
|
265 * HashMap. Returns null if the HashMap contains no mapping
|
|
266 * for this key.
|
|
267 */
|
|
268 Entry getEntry(long key) {
|
|
269 Entry tab[] = table;
|
|
270 int hash = (int) key;
|
|
271 int index = (hash & 0x7FFFFFFF) % tab.length;
|
|
272
|
|
273 for (Entry e = tab[index]; e != null; e = e.next)
|
|
274 if (e.hash == hash && e.key ==key)
|
|
275 return e;
|
|
276
|
|
277 return null;
|
|
278 }
|
|
279
|
|
280 /**
|
|
281 * Returns <tt>true</tt> if this map maps one or more keys to the
|
|
282 * specified value.
|
|
283 *
|
|
284 * @param value value whose presence in this map is to be tested.
|
|
285 * @return <tt>true</tt> if this map maps one or more keys to the
|
|
286 * specified value.
|
|
287 */
|
|
288 public boolean containsValue(Object value) {
|
|
289 Entry tab[] = table;
|
|
290
|
|
291 if (value==null) {
|
|
292 for (int i = tab.length ; i-- > 0 ;)
|
|
293 for (Entry e = tab[i] ; e != null ; e = e.next)
|
|
294 if (e.value==null)
|
|
295 return true;
|
|
296 } else {
|
|
297 for (int i = tab.length ; i-- > 0 ;)
|
|
298 for (Entry e = tab[i] ; e != null ; e = e.next)
|
|
299 if (value.equals(e.value))
|
|
300 return true;
|
|
301 }
|
|
302
|
|
303 return false;
|
|
304 }
|
|
305
|
|
306 /**
|
|
307 * Associates the specified value with the specified key in this map.
|
|
308 * If the map previously contained a mapping for this key, the old
|
|
309 * value is replaced.
|
|
310 *
|
|
311 * @param key key with which the specified value is to be associated.
|
|
312 * @param value value to be associated with the specified key.
|
|
313 * @return previous value associated with specified key, or <tt>null</tt>
|
|
314 * if there was no mapping for key. A <tt>null</tt> return can
|
|
315 * also indicate that the HashMap previously associated
|
|
316 * <tt>null</tt> with the specified key.
|
|
317 */
|
|
318 public Object put(long key, Object value) {
|
|
319 Entry tab[] = table;
|
|
320 int hash = (int) key;
|
|
321 int index = (hash & 0x7FFFFFFF) % tab.length;
|
|
322
|
|
323 // Look for entry in hash table
|
|
324 for (Entry e = tab[index] ; e != null ; e = e.next) {
|
|
325 if (e.hash == hash && e.key == key) {
|
|
326 Object oldValue = e.value;
|
|
327 e.value = value;
|
|
328 return oldValue;
|
|
329 }
|
|
330 }
|
|
331
|
|
332 // It's not there; grow the hash table if necessary...
|
|
333 modCount++;
|
|
334 if (size >= threshold) {
|
|
335 rehash();
|
|
336 tab = table;
|
|
337 index = (hash & 0x7FFFFFFF) % tab.length;
|
|
338 }
|
|
339
|
|
340 // ...and add the entry
|
|
341 size++;
|
|
342 tab[index] = newEntry(hash, key, value, tab[index]);
|
|
343 return null;
|
|
344 }
|
|
345
|
|
346 /**
|
|
347 * Removes the mapping for this key from this map if present.
|
|
348 *
|
|
349 * @param key key whose mapping is to be removed from the map.
|
|
350 * @return previous value associated with specified key, or <tt>null</tt>
|
|
351 * if there was no mapping for key. A <tt>null</tt> return can
|
|
352 * also indicate that the map previously associated <tt>null</tt>
|
|
353 * with the specified key.
|
|
354 */
|
|
355 public Object remove(long key) {
|
|
356 Entry e = removeEntryForKey(key);
|
|
357 return (e == null ? null : e.value);
|
|
358 }
|
|
359
|
|
360 /**
|
|
361 * Removes and returns the entry associated with the specified key
|
|
362 * in the HashMap. Returns null if the HashMap contains no mapping
|
|
363 * for this key.
|
|
364 */
|
|
365 Entry removeEntryForKey(long key) {
|
|
366 Entry tab[] = table;
|
|
367 int hash = (int) key;
|
|
368 int index = (hash & 0x7FFFFFFF) % tab.length;
|
|
369
|
|
370 for (Entry e = tab[index], prev = null; e != null;
|
|
371 prev = e, e = e.next) {
|
|
372 if (e.hash == hash && e.key == key) {
|
|
373 modCount++;
|
|
374 if (prev != null)
|
|
375 prev.next = e.next;
|
|
376 else
|
|
377 tab[index] = e.next;
|
|
378
|
|
379 size--;
|
|
380 return e;
|
|
381 }
|
|
382 }
|
|
383
|
|
384 return null;
|
|
385 }
|
|
386
|
|
387 /**
|
|
388 * Removes the specified entry from this HashMap (and increments modCount).
|
|
389 *
|
|
390 * @throws ConcurrentModificationException if the entry is not in the Map
|
|
391 */
|
|
392 void removeEntry(Entry doomed) {
|
|
393 Entry[] tab = table;
|
|
394 int index = (doomed.hash & 0x7FFFFFFF) % tab.length;
|
|
395
|
|
396 for (Entry e = tab[index], prev = null; e != null;
|
|
397 prev = e, e = e.next) {
|
|
398 if (e == doomed) {
|
|
399 modCount++;
|
|
400 if (prev == null)
|
|
401 tab[index] = e.next;
|
|
402 else
|
|
403 prev.next = e.next;
|
|
404 size--;
|
|
405 return;
|
|
406 }
|
|
407 }
|
|
408 throw new ConcurrentModificationException();
|
|
409 }
|
|
410
|
|
411 /**
|
|
412 * Removes all mappings from this map.
|
|
413 */
|
|
414 public void clear() {
|
|
415 Entry tab[] = table;
|
|
416 modCount++;
|
|
417 for (int index = tab.length; --index >= 0; )
|
|
418 tab[index] = null;
|
|
419 size = 0;
|
|
420 }
|
|
421
|
|
422 /**
|
|
423 * Rehashes the contents of this map into a new <tt>HashMap</tt> instance
|
|
424 * with a larger capacity. This method is called automatically when the
|
|
425 * number of keys in this map exceeds its capacity and load factor.
|
|
426 */
|
|
427 void rehash() {
|
|
428 Entry oldTable[] = table;
|
|
429 int oldCapacity = oldTable.length;
|
|
430 int newCapacity = oldCapacity * 2 + 1;
|
|
431 Entry newTable[] = new Entry[newCapacity];
|
|
432
|
|
433 modCount++;
|
|
434 threshold = (int)(newCapacity * loadFactor);
|
|
435 table = newTable;
|
|
436
|
|
437 for (int i = oldCapacity ; i-- > 0 ;) {
|
|
438 for (Entry old = oldTable[i] ; old != null ; ) {
|
|
439 Entry e = old;
|
|
440 old = old.next;
|
|
441
|
|
442 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
|
|
443 e.next = newTable[index];
|
|
444 newTable[index] = e;
|
|
445 }
|
|
446 }
|
|
447 }
|
|
448
|
|
449 static boolean eq(Object o1, Object o2) {
|
|
450 return (o1==null ? o2==null : o1.equals(o2));
|
|
451 }
|
|
452
|
|
453 Entry newEntry(int hash, long key, Object value, Entry next) {
|
|
454 return new Entry(hash, key, value, next);
|
|
455 }
|
|
456
|
|
457 int capacity() {
|
|
458 return table.length;
|
|
459 }
|
|
460
|
|
461 float loadFactor() {
|
|
462 return loadFactor;
|
|
463 }
|
|
464 }
|