Mercurial > hg > truffle
annotate agent/src/share/classes/sun/jvm/hotspot/debugger/LongHashMap.java @ 2245:638119ce7cfd
7009309: JSR 292: compiler/6991596/Test6991596.java crashes on fastdebug JDK7/b122
Reviewed-by: kvn, never
author | twisti |
---|---|
date | Tue, 01 Feb 2011 03:38:44 -0800 |
parents | c18cbe5936b8 |
children |
rev | line source |
---|---|
0 | 1 /* |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
2 * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved. |
0 | 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 * | |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
21 * questions. |
0 | 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 } |