Mercurial > hg > blitz_condensed
comparison src/com/go/trove/util/IdentityMap.java @ 0:3dc0c5604566
Initial checkin of blitz 2.0 fcs - no installer yet.
author | Dan Creswell <dan.creswell@gmail.com> |
---|---|
date | Sat, 21 Mar 2009 11:00:06 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:3dc0c5604566 |
---|---|
1 /* ==================================================================== | |
2 * Trove - Copyright (c) 1997-2000 Walt Disney Internet Group | |
3 * ==================================================================== | |
4 * The Tea Software License, Version 1.1 | |
5 * | |
6 * Copyright (c) 2000 Walt Disney Internet Group. All rights reserved. | |
7 * | |
8 * Redistribution and use in source and binary forms, with or without | |
9 * modification, are permitted provided that the following conditions | |
10 * are met: | |
11 * | |
12 * 1. Redistributions of source code must retain the above copyright | |
13 * notice, this list of conditions and the following disclaimer. | |
14 * | |
15 * 2. Redistributions in binary form must reproduce the above copyright | |
16 * notice, this list of conditions and the following disclaimer in | |
17 * the documentation and/or other materials provided with the | |
18 * distribution. | |
19 * | |
20 * 3. The end-user documentation included with the redistribution, | |
21 * if any, must include the following acknowledgment: | |
22 * "This product includes software developed by the | |
23 * Walt Disney Internet Group (http://opensource.go.com/)." | |
24 * Alternately, this acknowledgment may appear in the software itself, | |
25 * if and wherever such third-party acknowledgments normally appear. | |
26 * | |
27 * 4. The names "Tea", "TeaServlet", "Kettle", "Trove" and "BeanDoc" must | |
28 * not be used to endorse or promote products derived from this | |
29 * software without prior written permission. For written | |
30 * permission, please contact opensource@dig.com. | |
31 * | |
32 * 5. Products derived from this software may not be called "Tea", | |
33 * "TeaServlet", "Kettle" or "Trove", nor may "Tea", "TeaServlet", | |
34 * "Kettle", "Trove" or "BeanDoc" appear in their name, without prior | |
35 * written permission of the Walt Disney Internet Group. | |
36 * | |
37 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED | |
38 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES | |
39 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE | |
40 * DISCLAIMED. IN NO EVENT SHALL THE WALT DISNEY INTERNET GROUP OR ITS | |
41 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | |
42 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, | |
43 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR | |
44 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY | |
45 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
46 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
47 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
48 * ==================================================================== | |
49 * | |
50 * For more information about Tea, please see http://opensource.go.com/. | |
51 */ | |
52 | |
53 package com.go.trove.util; | |
54 | |
55 import java.lang.ref.*; | |
56 import java.util.*; | |
57 | |
58 /****************************************************************************** | |
59 * An IdentityMap is like WeakHashMap, except it uses a key's identity | |
60 * hashcode and equals methods. IdentityMap is not thread-safe and must be | |
61 * wrapped with Collections.synchronizedMap to be made thread-safe. Most of the | |
62 * implementation for this class is ripped off from java.util.HashMap, but not | |
63 * java.util.WeakHashMap, in order to acheive greater efficiency. | |
64 * <p> | |
65 * The documentation for WeakHashMap states that it is intended primarily | |
66 * for use with key objects whose equals methods test for object identity | |
67 * using the == operator. Because WeakHashMap uses a key's own equals and | |
68 * hashcode methods, it is better suited for implementing methods that behave | |
69 * like {@link String#intern}. However, because WeakHashMap stongly references | |
70 * values, {@link Utils#intern Utils.intern} provides a safer intern mechanism. | |
71 * <p> | |
72 * In this implementation, all key objects are tested for equality using the | |
73 * == operator, and null keys are not permitted. IdentityMap is therefore | |
74 * better suited for "canonicalized" mappings. | |
75 * <p> | |
76 * Note: Weakly referenced entries may be automatically removed during | |
77 * either accessor or mutator operations, possibly causing a concurrent | |
78 * modification to be detected. Therefore, even if multiple threads are only | |
79 * accessing this map, be sure to synchronize this map first. Also, do not | |
80 * rely on the value returned by size() when using an iterator from this map. | |
81 * The iterators may return less entries than the amount reported by size(). | |
82 * | |
83 * @author Brian S O'Neill | |
84 * @version | |
85 * <!--$$Revision: 1.1 $-->, <!--$$JustDate:--> 00/12/18 <!-- $--> | |
86 * @see java.util.WeakHashMap | |
87 * @see java.util.HashMap | |
88 */ | |
89 public class IdentityMap extends AbstractMap implements Map, Cloneable { | |
90 // Types of Iterators | |
91 static final int KEYS = 0; | |
92 static final int VALUES = 1; | |
93 static final int ENTRIES = 2; | |
94 | |
95 static final Iterator cEmptyHashIterator = new Iterator() { | |
96 public boolean hasNext() { | |
97 return false; | |
98 } | |
99 | |
100 public Object next() { | |
101 throw new NoSuchElementException(); | |
102 } | |
103 | |
104 public void remove() { | |
105 throw new IllegalStateException(); | |
106 } | |
107 }; | |
108 | |
109 /** | |
110 * Test program. | |
111 */ | |
112 /* | |
113 public static void main(String[] args) throws Exception { | |
114 Map map = new IdentityMap(); | |
115 map.put("Hello", "There"); | |
116 for (int i=0; i<1000000; i++) { | |
117 if (i % 5 == 0) { | |
118 map.put(new String("Hello"), "Dude"); | |
119 } | |
120 map.get("Hello"); | |
121 map.get("Stuff"); | |
122 } | |
123 | |
124 System.out.println(map.containsValue("Dude")); | |
125 System.out.println(map.get("Hello")); | |
126 | |
127 System.gc(); | |
128 | |
129 System.out.println(map); | |
130 System.out.println(map.size()); | |
131 | |
132 System.out.println(map.containsValue("Dude")); | |
133 System.out.println(map.get("Hello")); | |
134 | |
135 map.remove("Hello"); | |
136 | |
137 System.out.println(map); | |
138 System.out.println(map.size()); | |
139 | |
140 System.out.println(map.containsValue("Dude")); | |
141 System.out.println(map.get("Hello")); | |
142 } | |
143 */ | |
144 | |
145 /** | |
146 * Converts a string to a collection without calling size(). Iterators from | |
147 * this map may return less entries than the amount reported by size(). | |
148 */ | |
149 static String toString(Collection c) { | |
150 StringBuffer buf = new StringBuffer(); | |
151 Iterator it = c.iterator(); | |
152 buf.append("["); | |
153 for (int i = 0; it.hasNext(); i++) { | |
154 if (i > 0) { | |
155 buf.append(", "); | |
156 } | |
157 buf.append(String.valueOf(it.next())); | |
158 } | |
159 buf.append("]"); | |
160 return buf.toString(); | |
161 } | |
162 | |
163 /** | |
164 * The hash table data. | |
165 */ | |
166 private transient Entry mTable[]; | |
167 | |
168 /** | |
169 * The total number of mappings in the hash table. | |
170 */ | |
171 private transient int mCount; | |
172 | |
173 /** | |
174 * The table is rehashed when its size exceeds this threshold. (The | |
175 * value of this field is (int)(capacity * loadFactor).) | |
176 * | |
177 * @serial | |
178 */ | |
179 private int mThreshold; | |
180 | |
181 /** | |
182 * The load factor for the hashtable. | |
183 * | |
184 * @serial | |
185 */ | |
186 private float mLoadFactor; | |
187 | |
188 /** | |
189 * The number of times this HashMap has been structurally modified | |
190 * Structural modifications are those that change the number of mappings in | |
191 * the HashMap or otherwise modify its internal structure (e.g., | |
192 * rehash). This field is used to make iterators on Collection-views of | |
193 * the HashMap fail-fast. (See ConcurrentModificationException). | |
194 */ | |
195 private transient int mModCount = 0; | |
196 | |
197 // Views | |
198 | |
199 private transient Set mKeySet = null; | |
200 private transient Set mEntrySet = null; | |
201 private transient Collection mValues = null; | |
202 | |
203 /** | |
204 * Constructs a new, empty map with the specified initial | |
205 * capacity and the specified load factor. | |
206 * | |
207 * @param initialCapacity the initial capacity of the HashMap. | |
208 * @param loadFactor the load factor of the HashMap | |
209 * @throws IllegalArgumentException if the initial capacity is less | |
210 * than zero, or if the load factor is nonpositive. | |
211 */ | |
212 public IdentityMap(int initialCapacity, float loadFactor) { | |
213 if (initialCapacity < 0) { | |
214 throw new IllegalArgumentException("Illegal Initial Capacity: "+ | |
215 initialCapacity); | |
216 } | |
217 | |
218 if (loadFactor <= 0 || Float.isNaN(loadFactor)) { | |
219 throw new IllegalArgumentException("Illegal Load factor: "+ | |
220 loadFactor); | |
221 } | |
222 | |
223 if (initialCapacity == 0) { | |
224 initialCapacity = 1; | |
225 } | |
226 | |
227 mLoadFactor = loadFactor; | |
228 mTable = new Entry[initialCapacity]; | |
229 mThreshold = (int)(initialCapacity * loadFactor); | |
230 } | |
231 | |
232 /** | |
233 * Constructs a new, empty map with the specified initial capacity | |
234 * and default load factor, which is <tt>0.75</tt>. | |
235 * | |
236 * @param initialCapacity the initial capacity of the HashMap. | |
237 * @throws IllegalArgumentException if the initial capacity is less | |
238 * than zero. | |
239 */ | |
240 public IdentityMap(int initialCapacity) { | |
241 this(initialCapacity, 0.75f); | |
242 } | |
243 | |
244 /** | |
245 * Constructs a new, empty map with a default capacity and load | |
246 * factor, which is <tt>0.75</tt>. | |
247 */ | |
248 public IdentityMap() { | |
249 this(11, 0.75f); | |
250 } | |
251 | |
252 /** | |
253 * Constructs a new map with the same mappings as the given map. The | |
254 * map is created with a capacity of twice the number of mappings in | |
255 * the given map or 11 (whichever is greater), and a default load factor, | |
256 * which is <tt>0.75</tt>. | |
257 */ | |
258 public IdentityMap(Map t) { | |
259 this(Math.max(2 * t.size(), 11), 0.75f); | |
260 putAll(t); | |
261 } | |
262 | |
263 /** | |
264 * Returns the number of key-value mappings in this map, but this value | |
265 * may be larger than actual amount of entries produced by an iterator. | |
266 * | |
267 * @return the number of key-value mappings in this map. | |
268 */ | |
269 public int size() { | |
270 return mCount; | |
271 } | |
272 | |
273 /** | |
274 * Returns <tt>true</tt> if this map contains no key-value mappings. | |
275 * | |
276 * @return <tt>true</tt> if this map contains no key-value mappings. | |
277 */ | |
278 public boolean isEmpty() { | |
279 return mCount == 0; | |
280 } | |
281 | |
282 /** | |
283 * Returns <tt>true</tt> if this map maps one or more keys to the | |
284 * specified value. | |
285 * | |
286 * @param value value whose presence in this map is to be tested. | |
287 * @return <tt>true</tt> if this map maps one or more keys to the | |
288 * specified value. | |
289 */ | |
290 public boolean containsValue(Object value) { | |
291 Entry tab[] = mTable; | |
292 | |
293 if (value == null) { | |
294 for (int i = tab.length ; i-- > 0 ;) { | |
295 for (Entry e = tab[i], prev = null; e != null; e = e.mNext) { | |
296 if (e.getKey() == null) { | |
297 // Clean up after a cleared Reference. | |
298 mModCount++; | |
299 if (prev != null) { | |
300 prev.mNext = e.mNext; | |
301 } | |
302 else { | |
303 tab[i] = e.mNext; | |
304 } | |
305 mCount--; | |
306 } | |
307 else if (e.mValue == null) { | |
308 return true; | |
309 } | |
310 else { | |
311 prev = e; | |
312 } | |
313 } | |
314 } | |
315 } | |
316 else { | |
317 for (int i = tab.length ; i-- > 0 ;) { | |
318 for (Entry e = tab[i], prev = null; e != null; e = e.mNext) { | |
319 if (e.getKey() == null) { | |
320 // Clean up after a cleared Reference. | |
321 mModCount++; | |
322 if (prev != null) { | |
323 prev.mNext = e.mNext; | |
324 } | |
325 else { | |
326 tab[i] = e.mNext; | |
327 } | |
328 mCount--; | |
329 } | |
330 else if (value.equals(e.mValue)) { | |
331 return true; | |
332 } | |
333 else { | |
334 prev = e; | |
335 } | |
336 } | |
337 } | |
338 } | |
339 | |
340 return false; | |
341 } | |
342 | |
343 /** | |
344 * Returns <tt>true</tt> if this map contains a mapping for the specified | |
345 * key. | |
346 * | |
347 * @return <tt>true</tt> if this map contains a mapping for the specified | |
348 * key. | |
349 * @param key key whose presence in this Map is to be tested. | |
350 */ | |
351 public boolean containsKey(Object key) { | |
352 if (key == null) { | |
353 return false; | |
354 } | |
355 | |
356 Entry tab[] = mTable; | |
357 int hash = System.identityHashCode(key); | |
358 int index = (hash & 0x7FFFFFFF) % tab.length; | |
359 | |
360 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { | |
361 Object entryKey = e.getKey(); | |
362 | |
363 if (entryKey == null) { | |
364 // Clean up after a cleared Reference. | |
365 mModCount++; | |
366 if (prev != null) { | |
367 prev.mNext = e.mNext; | |
368 } | |
369 else { | |
370 tab[index] = e.mNext; | |
371 } | |
372 mCount--; | |
373 } | |
374 else if (e.mHash == hash && key == entryKey) { | |
375 return true; | |
376 } | |
377 else { | |
378 prev = e; | |
379 } | |
380 } | |
381 | |
382 return false; | |
383 } | |
384 | |
385 /** | |
386 * Returns the value to which this map maps the specified key. Returns | |
387 * <tt>null</tt> if the map contains no mapping for this key. A return | |
388 * value of <tt>null</tt> does not <i>necessarily</i> indicate that the | |
389 * map contains no mapping for the key; it's also possible that the map | |
390 * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt> | |
391 * operation may be used to distinguish these two cases. | |
392 * | |
393 * @return the value to which this map maps the specified key. | |
394 * @param key key whose associated value is to be returned. | |
395 */ | |
396 public Object get(Object key) { | |
397 if (key == null) { | |
398 return null; | |
399 } | |
400 | |
401 Entry tab[] = mTable; | |
402 int hash = System.identityHashCode(key); | |
403 int index = (hash & 0x7FFFFFFF) % tab.length; | |
404 | |
405 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { | |
406 Object entryKey = e.getKey(); | |
407 | |
408 if (entryKey == null) { | |
409 // Clean up after a cleared Reference. | |
410 mModCount++; | |
411 if (prev != null) { | |
412 prev.mNext = e.mNext; | |
413 } | |
414 else { | |
415 tab[index] = e.mNext; | |
416 } | |
417 mCount--; | |
418 } | |
419 else if (e.mHash == hash && key == entryKey) { | |
420 return e.mValue; | |
421 } | |
422 else { | |
423 prev = e; | |
424 } | |
425 } | |
426 | |
427 return null; | |
428 } | |
429 | |
430 /** | |
431 * Scans the contents of this map, removing all entries that have a | |
432 * cleared weak key. | |
433 */ | |
434 private void cleanup() { | |
435 Entry tab[] = mTable; | |
436 | |
437 for (int i = tab.length ; i-- > 0 ;) { | |
438 for (Entry e = tab[i], prev = null; e != null; e = e.mNext) { | |
439 if (e.getKey() == null) { | |
440 // Clean up after a cleared Reference. | |
441 mModCount++; | |
442 if (prev != null) { | |
443 prev.mNext = e.mNext; | |
444 } | |
445 else { | |
446 tab[i] = e.mNext; | |
447 } | |
448 mCount--; | |
449 } | |
450 else { | |
451 prev = e; | |
452 } | |
453 } | |
454 } | |
455 } | |
456 | |
457 /** | |
458 * Rehashes the contents of this map into a new <tt>HashMap</tt> instance | |
459 * with a larger capacity. This method is called automatically when the | |
460 * number of keys in this map exceeds its capacity and load factor. | |
461 */ | |
462 private void rehash() { | |
463 int oldCapacity = mTable.length; | |
464 Entry oldMap[] = mTable; | |
465 | |
466 int newCapacity = oldCapacity * 2 + 1; | |
467 Entry newMap[] = new Entry[newCapacity]; | |
468 | |
469 mModCount++; | |
470 mThreshold = (int)(newCapacity * mLoadFactor); | |
471 mTable = newMap; | |
472 | |
473 for (int i = oldCapacity ; i-- > 0 ;) { | |
474 for (Entry old = oldMap[i] ; old != null ; ) { | |
475 Entry e = old; | |
476 old = old.mNext; | |
477 | |
478 // Only copy entry if its key hasn't been cleared. | |
479 if (e.getKey() == null) { | |
480 mCount--; | |
481 } | |
482 else { | |
483 int index = (e.mHash & 0x7FFFFFFF) % newCapacity; | |
484 e.mNext = newMap[index]; | |
485 newMap[index] = e; | |
486 } | |
487 } | |
488 } | |
489 } | |
490 | |
491 /** | |
492 * Associates the specified value with the specified key in this map. | |
493 * If the map previously contained a mapping for this key, the old | |
494 * value is replaced. | |
495 * | |
496 * @param key key with which the specified value is to be associated. | |
497 * @param value value to be associated with the specified key. | |
498 * @return previous value associated with specified key, or <tt>null</tt> | |
499 * if there was no mapping for key. A <tt>null</tt> return can | |
500 * also indicate that the HashMap previously associated | |
501 * <tt>null</tt> with the specified key. | |
502 */ | |
503 public Object put(Object key, Object value) { | |
504 if (key == null) { | |
505 throw new NullPointerException("Null key is not permitted"); | |
506 } | |
507 | |
508 // Makes sure the key is not already in the HashMap. | |
509 Entry tab[] = mTable; | |
510 int hash = System.identityHashCode(key); | |
511 int index = (hash & 0x7FFFFFFF) % tab.length; | |
512 | |
513 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { | |
514 Object entryKey = e.getKey(); | |
515 | |
516 if (entryKey == null) { | |
517 // Clean up after a cleared Reference. | |
518 mModCount++; | |
519 if (prev != null) { | |
520 prev.mNext = e.mNext; | |
521 } | |
522 else { | |
523 tab[index] = e.mNext; | |
524 } | |
525 mCount--; | |
526 } | |
527 else if (e.mHash == hash && key == entryKey) { | |
528 Object old = e.mValue; | |
529 e.mValue = value; | |
530 return old; | |
531 } | |
532 else { | |
533 prev = e; | |
534 } | |
535 } | |
536 | |
537 mModCount++; | |
538 | |
539 if (mCount >= mThreshold) { | |
540 // Cleanup the table if the threshold is exceeded. | |
541 cleanup(); | |
542 } | |
543 | |
544 if (mCount >= mThreshold) { | |
545 // Rehash the table if the threshold is still exceeded. | |
546 rehash(); | |
547 tab = mTable; | |
548 index = (hash & 0x7FFFFFFF) % tab.length; | |
549 } | |
550 | |
551 // Creates the new entry. | |
552 Entry e = new Entry(hash, key, value, tab[index]); | |
553 tab[index] = e; | |
554 mCount++; | |
555 return null; | |
556 } | |
557 | |
558 /** | |
559 * Removes the mapping for this key from this map if present. | |
560 * | |
561 * @param key key whose mapping is to be removed from the map. | |
562 * @return previous value associated with specified key, or <tt>null</tt> | |
563 * if there was no mapping for key. A <tt>null</tt> return can | |
564 * also indicate that the map previously associated <tt>null</tt> | |
565 * with the specified key. | |
566 */ | |
567 public Object remove(Object key) { | |
568 Entry tab[] = mTable; | |
569 int hash = System.identityHashCode(key); | |
570 int index = (hash & 0x7FFFFFFF) % tab.length; | |
571 | |
572 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { | |
573 Object entryKey = e.getKey(); | |
574 | |
575 if (entryKey == null) { | |
576 // Clean up after a cleared Reference. | |
577 mModCount++; | |
578 if (prev != null) { | |
579 prev.mNext = e.mNext; | |
580 } | |
581 else { | |
582 tab[index] = e.mNext; | |
583 } | |
584 mCount--; | |
585 } | |
586 else if (e.mHash == hash && key == entryKey) { | |
587 mModCount++; | |
588 if (prev != null) { | |
589 prev.mNext = e.mNext; | |
590 } | |
591 else { | |
592 tab[index] = e.mNext; | |
593 } | |
594 mCount--; | |
595 | |
596 Object oldValue = e.mValue; | |
597 e.mValue = null; | |
598 return oldValue; | |
599 } | |
600 else { | |
601 prev = e; | |
602 } | |
603 } | |
604 | |
605 return null; | |
606 } | |
607 | |
608 /** | |
609 * Copies all of the mappings from the specified map to this one. | |
610 * | |
611 * These mappings replace any mappings that this map had for any of the | |
612 * keys currently in the specified Map. | |
613 * | |
614 * @param t Mappings to be stored in this map. | |
615 */ | |
616 public void putAll(Map t) { | |
617 Iterator i = t.entrySet().iterator(); | |
618 while (i.hasNext()) { | |
619 Map.Entry e = (Map.Entry) i.next(); | |
620 put(e.getKey(), e.getValue()); | |
621 } | |
622 } | |
623 | |
624 /** | |
625 * Removes all mappings from this map. | |
626 */ | |
627 public void clear() { | |
628 Entry tab[] = mTable; | |
629 mModCount++; | |
630 for (int index = tab.length; --index >= 0; ) { | |
631 tab[index] = null; | |
632 } | |
633 mCount = 0; | |
634 } | |
635 | |
636 /** | |
637 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and | |
638 * values themselves are not cloned. | |
639 * | |
640 * @return a shallow copy of this map. | |
641 */ | |
642 public Object clone() { | |
643 try { | |
644 IdentityMap t = (IdentityMap)super.clone(); | |
645 t.mTable = new Entry[mTable.length]; | |
646 for (int i = mTable.length ; i-- > 0 ; ) { | |
647 t.mTable[i] = (mTable[i] != null) | |
648 ? (Entry)mTable[i].clone() : null; | |
649 } | |
650 t.mKeySet = null; | |
651 t.mEntrySet = null; | |
652 t.mValues = null; | |
653 t.mModCount = 0; | |
654 return t; | |
655 } | |
656 catch (CloneNotSupportedException e) { | |
657 // this shouldn't happen, since we are Cloneable | |
658 throw new InternalError(); | |
659 } | |
660 } | |
661 | |
662 /** | |
663 * Returns a set view of the keys contained in this map. The set is | |
664 * backed by the map, so changes to the map are reflected in the set, and | |
665 * vice-versa. The set supports element removal, which removes the | |
666 * corresponding mapping from this map, via the <tt>Iterator.remove</tt>, | |
667 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and | |
668 * <tt>clear</tt> operations. It does not support the <tt>add</tt> or | |
669 * <tt>addAll</tt> operations. | |
670 * | |
671 * @return a set view of the keys contained in this map. | |
672 */ | |
673 public Set keySet() { | |
674 if (mKeySet == null) { | |
675 mKeySet = new AbstractSet() { | |
676 public Iterator iterator() { | |
677 return getHashIterator(KEYS); | |
678 } | |
679 public int size() { | |
680 return mCount; | |
681 } | |
682 public boolean contains(Object o) { | |
683 return containsKey(o); | |
684 } | |
685 public boolean remove(Object o) { | |
686 return o == null ? false : IdentityMap.this.remove(o) == o; | |
687 } | |
688 public void clear() { | |
689 IdentityMap.this.clear(); | |
690 } | |
691 public String toString() { | |
692 return IdentityMap.this.toString(this); | |
693 } | |
694 }; | |
695 } | |
696 return mKeySet; | |
697 } | |
698 | |
699 /** | |
700 * Returns a collection view of the values contained in this map. The | |
701 * collection is backed by the map, so changes to the map are reflected in | |
702 * the collection, and vice-versa. The collection supports element | |
703 * removal, which removes the corresponding mapping from this map, via the | |
704 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, | |
705 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. | |
706 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. | |
707 * | |
708 * @return a collection view of the values contained in this map. | |
709 */ | |
710 public Collection values() { | |
711 if (mValues==null) { | |
712 mValues = new AbstractCollection() { | |
713 public Iterator iterator() { | |
714 return getHashIterator(VALUES); | |
715 } | |
716 public int size() { | |
717 return mCount; | |
718 } | |
719 public boolean contains(Object o) { | |
720 return containsValue(o); | |
721 } | |
722 public void clear() { | |
723 IdentityMap.this.clear(); | |
724 } | |
725 public String toString() { | |
726 return IdentityMap.this.toString(this); | |
727 } | |
728 }; | |
729 } | |
730 return mValues; | |
731 } | |
732 | |
733 /** | |
734 * Returns a collection view of the mappings contained in this map. Each | |
735 * element in the returned collection is a <tt>Map.Entry</tt>. The | |
736 * collection is backed by the map, so changes to the map are reflected in | |
737 * the collection, and vice-versa. The collection supports element | |
738 * removal, which removes the corresponding mapping from the map, via the | |
739 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, | |
740 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. | |
741 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. | |
742 * | |
743 * @return a collection view of the mappings contained in this map. | |
744 * @see Map.Entry | |
745 */ | |
746 public Set entrySet() { | |
747 if (mEntrySet==null) { | |
748 mEntrySet = new AbstractSet() { | |
749 public Iterator iterator() { | |
750 return getHashIterator(ENTRIES); | |
751 } | |
752 | |
753 public boolean contains(Object o) { | |
754 if (!(o instanceof Map.Entry)) { | |
755 return false; | |
756 } | |
757 Map.Entry entry = (Map.Entry)o; | |
758 Object key = entry.getKey(); | |
759 | |
760 Entry tab[] = mTable; | |
761 int hash = System.identityHashCode(key); | |
762 int index = (hash & 0x7FFFFFFF) % tab.length; | |
763 | |
764 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { | |
765 Object entryKey = e.getKey(); | |
766 | |
767 if (entryKey == null) { | |
768 // Clean up after a cleared Reference. | |
769 mModCount++; | |
770 if (prev != null) { | |
771 prev.mNext = e.mNext; | |
772 } | |
773 else { | |
774 tab[index] = e.mNext; | |
775 } | |
776 mCount--; | |
777 } | |
778 else if (e.mHash == hash && e.identityEquals(entry)) { | |
779 return true; | |
780 } | |
781 else { | |
782 prev = e; | |
783 } | |
784 } | |
785 | |
786 return false; | |
787 } | |
788 | |
789 public boolean remove(Object o) { | |
790 if (!(o instanceof Map.Entry)) { | |
791 return false; | |
792 } | |
793 Map.Entry entry = (Map.Entry)o; | |
794 Object key = entry.getKey(); | |
795 Entry tab[] = mTable; | |
796 int hash = System.identityHashCode(key); | |
797 int index = (hash & 0x7FFFFFFF) % tab.length; | |
798 | |
799 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { | |
800 Object entryKey = e.getKey(); | |
801 | |
802 if (entryKey == null) { | |
803 // Clean up after a cleared Reference. | |
804 mModCount++; | |
805 if (prev != null) { | |
806 prev.mNext = e.mNext; | |
807 } | |
808 else { | |
809 tab[index] = e.mNext; | |
810 } | |
811 mCount--; | |
812 } | |
813 else if (e.mHash == hash && e.identityEquals(entry)) { | |
814 mModCount++; | |
815 if (prev != null) { | |
816 prev.mNext = e.mNext; | |
817 } | |
818 else { | |
819 tab[index] = e.mNext; | |
820 } | |
821 mCount--; | |
822 | |
823 e.mValue = null; | |
824 return true; | |
825 } | |
826 else { | |
827 prev = e; | |
828 } | |
829 } | |
830 return false; | |
831 } | |
832 | |
833 public int size() { | |
834 return mCount; | |
835 } | |
836 | |
837 public void clear() { | |
838 IdentityMap.this.clear(); | |
839 } | |
840 | |
841 public String toString() { | |
842 return IdentityMap.this.toString(this); | |
843 } | |
844 }; | |
845 } | |
846 | |
847 return mEntrySet; | |
848 } | |
849 | |
850 public String toString() { | |
851 StringBuffer buf = new StringBuffer(); | |
852 Iterator it = entrySet().iterator(); | |
853 | |
854 buf.append("{"); | |
855 for (int i = 0; it.hasNext(); i++) { | |
856 if (i > 0) { | |
857 buf.append(", "); | |
858 } | |
859 Map.Entry e = (Map.Entry)it.next(); | |
860 buf.append(e.getKey() + "=" + e.getValue()); | |
861 } | |
862 buf.append("}"); | |
863 return buf.toString(); | |
864 } | |
865 | |
866 private Iterator getHashIterator(int type) { | |
867 if (mCount == 0) { | |
868 return cEmptyHashIterator; | |
869 } | |
870 else { | |
871 return new HashIterator(type); | |
872 } | |
873 } | |
874 | |
875 /** | |
876 * HashMap collision list entry. | |
877 */ | |
878 private static class Entry extends WeakReference implements Map.Entry { | |
879 int mHash; | |
880 Object mValue; | |
881 Entry mNext; | |
882 | |
883 Entry(int hash, Object key, Object value, Entry next) { | |
884 super(key); | |
885 mHash = hash; | |
886 mValue = value; | |
887 mNext = next; | |
888 } | |
889 | |
890 protected Object clone() { | |
891 return new Entry(mHash, getKey(), mValue, | |
892 (mNext == null ? null : (Entry)mNext.clone())); | |
893 } | |
894 | |
895 // Map.Entry Ops | |
896 | |
897 public Object getKey() { | |
898 return Entry.this.get(); | |
899 } | |
900 | |
901 public Object getValue() { | |
902 return mValue; | |
903 } | |
904 | |
905 public Object setValue(Object value) { | |
906 Object oldValue = mValue; | |
907 mValue = value; | |
908 return oldValue; | |
909 } | |
910 | |
911 public boolean equals(Object o) { | |
912 if (!(o instanceof Map.Entry)) { | |
913 return false; | |
914 } | |
915 Map.Entry e = (Map.Entry)o; | |
916 | |
917 Object key = getKey(); | |
918 | |
919 return (key==null ? e.getKey()==null : key.equals(e.getKey())) && | |
920 (mValue==null ? e.getValue()==null : mValue.equals(e.getValue())); | |
921 } | |
922 | |
923 public boolean identityEquals(Map.Entry e) { | |
924 return (getKey() == e.getKey()) && | |
925 (mValue==null ? e.getValue()==null : mValue.equals(e.getValue())); | |
926 } | |
927 | |
928 public int hashCode() { | |
929 return mHash ^ (mValue==null ? 0 : mValue.hashCode()); | |
930 } | |
931 | |
932 public String toString() { | |
933 return getKey() + "=" + mValue; | |
934 } | |
935 } | |
936 | |
937 private class HashIterator implements Iterator { | |
938 private Entry[] mTable = IdentityMap.this.mTable; | |
939 private int mIndex = mTable.length; | |
940 private Entry mEntry; | |
941 // To ensure that the iterator doesn't return cleared entries, keep a | |
942 // hard reference to the key. Its existence will prevent the weak | |
943 // key from being cleared. | |
944 private Object mEntryKey; | |
945 private Entry mLastReturned; | |
946 private int mType; | |
947 | |
948 /** | |
949 * The modCount value that the iterator believes that the backing | |
950 * List should have. If this expectation is violated, the iterator | |
951 * has detected concurrent modification. | |
952 */ | |
953 private int expectedModCount = mModCount; | |
954 | |
955 HashIterator(int type) { | |
956 mType = type; | |
957 } | |
958 | |
959 public boolean hasNext() { | |
960 while (mEntry == null || | |
961 (mEntryKey = mEntry.getKey()) == null) { | |
962 if (mEntry != null) { | |
963 // Clean up after a cleared Reference. | |
964 remove(mEntry); | |
965 mEntry = mEntry.mNext; | |
966 } | |
967 else { | |
968 if (mIndex <= 0) { | |
969 return false; | |
970 } | |
971 else { | |
972 mEntry = mTable[--mIndex]; | |
973 } | |
974 } | |
975 } | |
976 | |
977 return true; | |
978 } | |
979 | |
980 public Object next() { | |
981 if (mModCount != expectedModCount) { | |
982 throw new ConcurrentModificationException(); | |
983 } | |
984 | |
985 if (!hasNext()) { | |
986 throw new NoSuchElementException(); | |
987 } | |
988 | |
989 mLastReturned = mEntry; | |
990 mEntry = mEntry.mNext; | |
991 | |
992 return mType == KEYS ? mLastReturned.getKey() : | |
993 (mType == VALUES ? mLastReturned.getValue() : mLastReturned); | |
994 } | |
995 | |
996 public void remove() { | |
997 if (mLastReturned == null) { | |
998 throw new IllegalStateException(); | |
999 } | |
1000 if (mModCount != expectedModCount) { | |
1001 throw new ConcurrentModificationException(); | |
1002 } | |
1003 remove(mLastReturned); | |
1004 mLastReturned = null; | |
1005 } | |
1006 | |
1007 private void remove(Entry toRemove) { | |
1008 Entry[] tab = mTable; | |
1009 int index = (toRemove.mHash & 0x7FFFFFFF) % tab.length; | |
1010 | |
1011 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { | |
1012 if (e == toRemove) { | |
1013 mModCount++; | |
1014 expectedModCount++; | |
1015 if (prev == null) { | |
1016 tab[index] = e.mNext; | |
1017 } | |
1018 else { | |
1019 prev.mNext = e.mNext; | |
1020 } | |
1021 mCount--; | |
1022 return; | |
1023 } | |
1024 else { | |
1025 prev = e; | |
1026 } | |
1027 } | |
1028 throw new ConcurrentModificationException(); | |
1029 } | |
1030 } | |
1031 } |