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 }