Mercurial > hg > blitz_condensed
comparison src/com/go/trove/util/SoftHashMap.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 * A Map that softly references its values and can be used as a simple cache. | |
60 * SoftHashMap is not thread-safe and must be wrapped with | |
61 * Collections.synchronizedMap to be made thread-safe. Most of the | |
62 * implementation for this class is ripped off from java.util.HashMap | |
63 * <p> | |
64 * Note: Softly referenced entries may be automatically removed during | |
65 * either accessor or mutator operations, possibly causing a concurrent | |
66 * modification to be detected. Therefore, even if multiple threads are only | |
67 * accessing this map, be sure to synchronize this map first. Also, do not | |
68 * rely on the value returned by size() when using an iterator from this map. | |
69 * The iterators may return less entries than the amount reported by size(). | |
70 * | |
71 * @author Brian S O'Neill | |
72 * @version | |
73 * <!--$$Revision: 1.1 $-->, <!--$$JustDate:--> 9/07/00 <!-- $--> | |
74 * @see Cache | |
75 */ | |
76 public class SoftHashMap extends AbstractMap implements Map, Cloneable { | |
77 /** | |
78 * Test program. | |
79 */ | |
80 /* | |
81 public static void main(String[] arg) throws Exception { | |
82 Map cache = new SoftHashMap(); | |
83 | |
84 for (int i = 0, j = 0; i < 100000; i++, j += 15) { | |
85 if (i % 100 == 0) { | |
86 System.out.println("Size = " + cache.size()); | |
87 } | |
88 | |
89 //Thread.sleep(1); | |
90 | |
91 Integer key = new Integer(i); | |
92 Integer value = new Integer(j); | |
93 | |
94 cache.put(key, value); | |
95 } | |
96 | |
97 Map.Entry entry = (Map.Entry)cache.entrySet().iterator().next(); | |
98 System.out.println(entry); | |
99 //entry = null; | |
100 | |
101 System.out.println(cache); | |
102 | |
103 int originalSize = cache.size(); | |
104 | |
105 //cache = null; | |
106 | |
107 for (int i=0; i<100; i++) { | |
108 System.gc(); | |
109 } | |
110 | |
111 System.out.println(cache); | |
112 | |
113 System.out.println(originalSize); | |
114 System.out.println(cache.size()); | |
115 System.out.println(entry); | |
116 | |
117 Thread.sleep(1000000); | |
118 } | |
119 */ | |
120 | |
121 /** | |
122 * The hash table data. | |
123 */ | |
124 private transient Entry mTable[]; | |
125 | |
126 /** | |
127 * The total number of mappings in the hash table. | |
128 */ | |
129 private transient int mCount; | |
130 | |
131 /** | |
132 * The table is rehashed when its size exceeds this threshold. (The | |
133 * value of this field is (int)(capacity * loadFactor).) | |
134 * | |
135 * @serial | |
136 */ | |
137 private int mThreshold; | |
138 | |
139 /** | |
140 * The load factor for the hashtable. | |
141 * | |
142 * @serial | |
143 */ | |
144 private float mLoadFactor; | |
145 | |
146 /** | |
147 * The number of times this HashMap has been structurally modified | |
148 * Structural modifications are those that change the number of mappings in | |
149 * the HashMap or otherwise modify its internal structure (e.g., | |
150 * rehash). This field is used to make iterators on Collection-views of | |
151 * the HashMap fail-fast. (See ConcurrentModificationException). | |
152 */ | |
153 private transient int mModCount = 0; | |
154 | |
155 // Views | |
156 | |
157 private transient Set mKeySet = null; | |
158 private transient Set mEntrySet = null; | |
159 private transient Collection mValues = null; | |
160 | |
161 /** | |
162 * Constructs a new, empty map with the specified initial | |
163 * capacity and the specified load factor. | |
164 * | |
165 * @param initialCapacity the initial capacity of the HashMap. | |
166 * @param loadFactor the load factor of the HashMap | |
167 * @throws IllegalArgumentException if the initial capacity is less | |
168 * than zero, or if the load factor is nonpositive. | |
169 */ | |
170 public SoftHashMap(int initialCapacity, float loadFactor) { | |
171 if (initialCapacity < 0) { | |
172 throw new IllegalArgumentException("Illegal Initial Capacity: "+ | |
173 initialCapacity); | |
174 } | |
175 | |
176 if (loadFactor <= 0 || Float.isNaN(loadFactor)) { | |
177 throw new IllegalArgumentException("Illegal Load factor: "+ | |
178 loadFactor); | |
179 } | |
180 | |
181 if (initialCapacity == 0) { | |
182 initialCapacity = 1; | |
183 } | |
184 | |
185 mLoadFactor = loadFactor; | |
186 mTable = new Entry[initialCapacity]; | |
187 mThreshold = (int)(initialCapacity * loadFactor); | |
188 } | |
189 | |
190 /** | |
191 * Constructs a new, empty map with the specified initial capacity | |
192 * and default load factor, which is <tt>0.75</tt>. | |
193 * | |
194 * @param initialCapacity the initial capacity of the HashMap. | |
195 * @throws IllegalArgumentException if the initial capacity is less | |
196 * than zero. | |
197 */ | |
198 public SoftHashMap(int initialCapacity) { | |
199 this(initialCapacity, 0.75f); | |
200 } | |
201 | |
202 /** | |
203 * Constructs a new, empty map with a default capacity and load | |
204 * factor, which is <tt>0.75</tt>. | |
205 */ | |
206 public SoftHashMap() { | |
207 this(11, 0.75f); | |
208 } | |
209 | |
210 /** | |
211 * Constructs a new map with the same mappings as the given map. The | |
212 * map is created with a capacity of twice the number of mappings in | |
213 * the given map or 11 (whichever is greater), and a default load factor, | |
214 * which is <tt>0.75</tt>. | |
215 */ | |
216 public SoftHashMap(Map t) { | |
217 this(Math.max(2 * t.size(), 11), 0.75f); | |
218 putAll(t); | |
219 } | |
220 | |
221 /** | |
222 * Returns the number of key-value mappings in this map, but this value | |
223 * may be larger than actual amount of entries produced by an iterator. | |
224 * | |
225 * @return the number of key-value mappings in this map. | |
226 */ | |
227 public int size() { | |
228 return mCount; | |
229 } | |
230 | |
231 /** | |
232 * Returns <tt>true</tt> if this map contains no key-value mappings. | |
233 * | |
234 * @return <tt>true</tt> if this map contains no key-value mappings. | |
235 */ | |
236 public boolean isEmpty() { | |
237 return mCount == 0; | |
238 } | |
239 | |
240 /** | |
241 * Returns <tt>true</tt> if this map maps one or more keys to the | |
242 * specified value. | |
243 * | |
244 * @param value value whose presence in this map is to be tested. | |
245 * @return <tt>true</tt> if this map maps one or more keys to the | |
246 * specified value. | |
247 */ | |
248 public boolean containsValue(Object value) { | |
249 if (value == null) { | |
250 value = new Null(); | |
251 } | |
252 | |
253 Entry tab[] = mTable; | |
254 | |
255 for (int i = tab.length ; i-- > 0 ;) { | |
256 for (Entry e = tab[i], prev = null; e != null; e = e.mNext) { | |
257 Object entryValue = e.getValue(); | |
258 | |
259 if (entryValue == null) { | |
260 // Clean up after a cleared Reference. | |
261 mModCount++; | |
262 if (prev != null) { | |
263 prev.mNext = e.mNext; | |
264 } | |
265 else { | |
266 tab[i] = e.mNext; | |
267 } | |
268 mCount--; | |
269 } | |
270 else if (value.equals(entryValue)) { | |
271 return true; | |
272 } | |
273 else { | |
274 prev = e; | |
275 } | |
276 } | |
277 } | |
278 | |
279 return false; | |
280 } | |
281 | |
282 /** | |
283 * Returns <tt>true</tt> if this map contains a mapping for the specified | |
284 * key. | |
285 * | |
286 * @return <tt>true</tt> if this map contains a mapping for the specified | |
287 * key. | |
288 * @param key key whose presence in this Map is to be tested. | |
289 */ | |
290 public boolean containsKey(Object key) { | |
291 Entry tab[] = mTable; | |
292 | |
293 if (key != null) { | |
294 int hash = key.hashCode(); | |
295 int index = (hash & 0x7FFFFFFF) % tab.length; | |
296 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { | |
297 if (e.getValue() == null) { | |
298 // Clean up after a cleared Reference. | |
299 mModCount++; | |
300 if (prev != null) { | |
301 prev.mNext = e.mNext; | |
302 } | |
303 else { | |
304 tab[index] = e.mNext; | |
305 } | |
306 mCount--; | |
307 } | |
308 else if (e.mHash == hash && key.equals(e.mKey)) { | |
309 return true; | |
310 } | |
311 else { | |
312 prev = e; | |
313 } | |
314 } | |
315 } | |
316 else { | |
317 for (Entry e = tab[0], prev = null; e != null; e = e.mNext) { | |
318 if (e.getValue() == null) { | |
319 // Clean up after a cleared Reference. | |
320 mModCount++; | |
321 if (prev != null) { | |
322 prev.mNext = e.mNext; | |
323 } | |
324 else { | |
325 tab[0] = e.mNext; | |
326 } | |
327 mCount--; | |
328 } | |
329 else if (e.mKey == null) { | |
330 return true; | |
331 } | |
332 else { | |
333 prev = e; | |
334 } | |
335 } | |
336 } | |
337 | |
338 return false; | |
339 } | |
340 | |
341 /** | |
342 * Returns the value to which this map maps the specified key. Returns | |
343 * <tt>null</tt> if the map contains no mapping for this key. A return | |
344 * value of <tt>null</tt> does not <i>necessarily</i> indicate that the | |
345 * map contains no mapping for the key; it's also possible that the map | |
346 * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt> | |
347 * operation may be used to distinguish these two cases. | |
348 * | |
349 * @return the value to which this map maps the specified key. | |
350 * @param key key whose associated value is to be returned. | |
351 */ | |
352 public Object get(Object key) { | |
353 Entry tab[] = mTable; | |
354 | |
355 if (key != null) { | |
356 int hash = key.hashCode(); | |
357 int index = (hash & 0x7FFFFFFF) % tab.length; | |
358 | |
359 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { | |
360 Object entryValue = e.getValue(); | |
361 | |
362 if (entryValue == null) { | |
363 // Clean up after a cleared Reference. | |
364 mModCount++; | |
365 if (prev != null) { | |
366 prev.mNext = e.mNext; | |
367 } | |
368 else { | |
369 tab[index] = e.mNext; | |
370 } | |
371 mCount--; | |
372 } | |
373 else if (e.mHash == hash && key.equals(e.mKey)) { | |
374 return (entryValue instanceof Null) ? null : entryValue; | |
375 } | |
376 else { | |
377 prev = e; | |
378 } | |
379 } | |
380 } | |
381 else { | |
382 for (Entry e = tab[0], prev = null; e != null; e = e.mNext) { | |
383 Object entryValue = e.getValue(); | |
384 | |
385 if (entryValue == null) { | |
386 // Clean up after a cleared Reference. | |
387 mModCount++; | |
388 if (prev != null) { | |
389 prev.mNext = e.mNext; | |
390 } | |
391 else { | |
392 tab[0] = e.mNext; | |
393 } | |
394 mCount--; | |
395 } | |
396 else if (e.mKey == null) { | |
397 return (entryValue instanceof Null) ? null : entryValue; | |
398 } | |
399 else { | |
400 prev = e; | |
401 } | |
402 } | |
403 } | |
404 | |
405 return null; | |
406 } | |
407 | |
408 /** | |
409 * Scans the contents of this map, removing all entries that have a | |
410 * cleared soft value. | |
411 */ | |
412 private void cleanup() { | |
413 Entry tab[] = mTable; | |
414 | |
415 for (int i = tab.length ; i-- > 0 ;) { | |
416 for (Entry e = tab[i], prev = null; e != null; e = e.mNext) { | |
417 if (e.getValue() == null) { | |
418 // Clean up after a cleared Reference. | |
419 mModCount++; | |
420 if (prev != null) { | |
421 prev.mNext = e.mNext; | |
422 } | |
423 else { | |
424 tab[i] = e.mNext; | |
425 } | |
426 mCount--; | |
427 } | |
428 else { | |
429 prev = e; | |
430 } | |
431 } | |
432 } | |
433 } | |
434 | |
435 /** | |
436 * Rehashes the contents of this map into a new <tt>HashMap</tt> instance | |
437 * with a larger capacity. This method is called automatically when the | |
438 * number of keys in this map exceeds its capacity and load factor. | |
439 */ | |
440 private void rehash() { | |
441 int oldCapacity = mTable.length; | |
442 Entry oldMap[] = mTable; | |
443 | |
444 int newCapacity = oldCapacity * 2 + 1; | |
445 Entry newMap[] = new Entry[newCapacity]; | |
446 | |
447 mModCount++; | |
448 mThreshold = (int)(newCapacity * mLoadFactor); | |
449 mTable = newMap; | |
450 | |
451 for (int i = oldCapacity ; i-- > 0 ;) { | |
452 for (Entry old = oldMap[i] ; old != null ; ) { | |
453 Entry e = old; | |
454 old = old.mNext; | |
455 | |
456 // Only copy entry if its value hasn't been cleared. | |
457 if (e.getValue() == null) { | |
458 mCount--; | |
459 } | |
460 else { | |
461 int index = (e.mHash & 0x7FFFFFFF) % newCapacity; | |
462 e.mNext = newMap[index]; | |
463 newMap[index] = e; | |
464 } | |
465 } | |
466 } | |
467 } | |
468 | |
469 /** | |
470 * Associates the specified value with the specified key in this map. | |
471 * If the map previously contained a mapping for this key, the old | |
472 * value is replaced. | |
473 * | |
474 * @param key key with which the specified value is to be associated. | |
475 * @param value value to be associated with the specified key. | |
476 * @return previous value associated with specified key, or <tt>null</tt> | |
477 * if there was no mapping for key. A <tt>null</tt> return can | |
478 * also indicate that the HashMap previously associated | |
479 * <tt>null</tt> with the specified key. | |
480 */ | |
481 public Object put(Object key, Object value) { | |
482 if (value == null) { | |
483 value = new Null(); | |
484 } | |
485 | |
486 // Makes sure the key is not already in the HashMap. | |
487 Entry tab[] = mTable; | |
488 int hash; | |
489 int index; | |
490 | |
491 if (key != null) { | |
492 hash = key.hashCode(); | |
493 index = (hash & 0x7FFFFFFF) % tab.length; | |
494 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { | |
495 Object entryValue = e.getValue(); | |
496 | |
497 if (e.getValue() == null) { | |
498 // Clean up after a cleared Reference. | |
499 mModCount++; | |
500 if (prev != null) { | |
501 prev.mNext = e.mNext; | |
502 } | |
503 else { | |
504 tab[index] = e.mNext; | |
505 } | |
506 mCount--; | |
507 } | |
508 else if (e.mHash == hash && key.equals(e.mKey)) { | |
509 e.setValue(value); | |
510 return (entryValue instanceof Null) ? null : entryValue; | |
511 } | |
512 else { | |
513 prev = e; | |
514 } | |
515 } | |
516 } | |
517 else { | |
518 hash = 0; | |
519 index = 0; | |
520 for (Entry e = tab[0], prev = null; e != null; e = e.mNext) { | |
521 Object entryValue = e.getValue(); | |
522 | |
523 if (entryValue == null) { | |
524 // Clean up after a cleared Reference. | |
525 mModCount++; | |
526 if (prev != null) { | |
527 prev.mNext = e.mNext; | |
528 } | |
529 else { | |
530 tab[0] = e.mNext; | |
531 } | |
532 mCount--; | |
533 } | |
534 else if (e.mKey == null) { | |
535 e.setValue(value); | |
536 return (entryValue instanceof Null) ? null : entryValue; | |
537 } | |
538 else { | |
539 prev = e; | |
540 } | |
541 } | |
542 } | |
543 | |
544 mModCount++; | |
545 | |
546 if (mCount >= mThreshold) { | |
547 // Cleanup the table if the threshold is exceeded. | |
548 cleanup(); | |
549 } | |
550 | |
551 if (mCount >= mThreshold) { | |
552 // Rehash the table if the threshold is still exceeded. | |
553 rehash(); | |
554 tab = mTable; | |
555 index = (hash & 0x7FFFFFFF) % tab.length; | |
556 } | |
557 | |
558 // Creates the new entry. | |
559 Entry e = new Entry(hash, key, (Object)value, tab[index]); | |
560 tab[index] = e; | |
561 mCount++; | |
562 return null; | |
563 } | |
564 | |
565 /** | |
566 * Removes the mapping for this key from this map if present. | |
567 * | |
568 * @param key key whose mapping is to be removed from the map. | |
569 * @return previous value associated with specified key, or <tt>null</tt> | |
570 * if there was no mapping for key. A <tt>null</tt> return can | |
571 * also indicate that the map previously associated <tt>null</tt> | |
572 * with the specified key. | |
573 */ | |
574 public Object remove(Object key) { | |
575 Entry tab[] = mTable; | |
576 | |
577 if (key != null) { | |
578 int hash = key.hashCode(); | |
579 int index = (hash & 0x7FFFFFFF) % tab.length; | |
580 | |
581 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { | |
582 Object entryValue = e.getValue(); | |
583 | |
584 if (entryValue == null) { | |
585 // Clean up after a cleared Reference. | |
586 mModCount++; | |
587 if (prev != null) { | |
588 prev.mNext = e.mNext; | |
589 } | |
590 else { | |
591 tab[index] = e.mNext; | |
592 } | |
593 mCount--; | |
594 } | |
595 else if (e.mHash == hash && key.equals(e.mKey)) { | |
596 mModCount++; | |
597 if (prev != null) { | |
598 prev.mNext = e.mNext; | |
599 } | |
600 else { | |
601 tab[index] = e.mNext; | |
602 } | |
603 mCount--; | |
604 | |
605 e.setValue(null); | |
606 return (entryValue instanceof Null) ? null : entryValue; | |
607 } | |
608 else { | |
609 prev = e; | |
610 } | |
611 } | |
612 } | |
613 else { | |
614 for (Entry e = tab[0], prev = null; e != null; e = e.mNext) { | |
615 Object entryValue = e.getValue(); | |
616 | |
617 if (entryValue == null) { | |
618 // Clean up after a cleared Reference. | |
619 mModCount++; | |
620 if (prev != null) { | |
621 prev.mNext = e.mNext; | |
622 } | |
623 else { | |
624 tab[0] = e.mNext; | |
625 } | |
626 mCount--; | |
627 } | |
628 else if (e.mKey == null) { | |
629 mModCount++; | |
630 if (prev != null) { | |
631 prev.mNext = e.mNext; | |
632 } | |
633 else { | |
634 tab[0] = e.mNext; | |
635 } | |
636 mCount--; | |
637 | |
638 e.setValue(null); | |
639 return (entryValue instanceof Null) ? null : entryValue; | |
640 } | |
641 else { | |
642 prev = e; | |
643 } | |
644 } | |
645 } | |
646 | |
647 return null; | |
648 } | |
649 | |
650 /** | |
651 * Copies all of the mappings from the specified map to this one. | |
652 * | |
653 * These mappings replace any mappings that this map had for any of the | |
654 * keys currently in the specified Map. | |
655 * | |
656 * @param t Mappings to be stored in this map. | |
657 */ | |
658 public void putAll(Map t) { | |
659 Iterator i = t.entrySet().iterator(); | |
660 while (i.hasNext()) { | |
661 Map.Entry e = (Map.Entry) i.next(); | |
662 put(e.getKey(), e.getValue()); | |
663 } | |
664 } | |
665 | |
666 /** | |
667 * Removes all mappings from this map. | |
668 */ | |
669 public void clear() { | |
670 Entry tab[] = mTable; | |
671 mModCount++; | |
672 for (int index = tab.length; --index >= 0; ) { | |
673 tab[index] = null; | |
674 } | |
675 mCount = 0; | |
676 } | |
677 | |
678 /** | |
679 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and | |
680 * values themselves are not cloned. | |
681 * | |
682 * @return a shallow copy of this map. | |
683 */ | |
684 public Object clone() { | |
685 try { | |
686 SoftHashMap t = (SoftHashMap)super.clone(); | |
687 t.mTable = new Entry[mTable.length]; | |
688 for (int i = mTable.length ; i-- > 0 ; ) { | |
689 t.mTable[i] = (mTable[i] != null) | |
690 ? (Entry)mTable[i].clone() : null; | |
691 } | |
692 t.mKeySet = null; | |
693 t.mEntrySet = null; | |
694 t.mValues = null; | |
695 t.mModCount = 0; | |
696 return t; | |
697 } | |
698 catch (CloneNotSupportedException e) { | |
699 // this shouldn't happen, since we are Cloneable | |
700 throw new InternalError(); | |
701 } | |
702 } | |
703 | |
704 /** | |
705 * Returns a set view of the keys contained in this map. The set is | |
706 * backed by the map, so changes to the map are reflected in the set, and | |
707 * vice-versa. The set supports element removal, which removes the | |
708 * corresponding mapping from this map, via the <tt>Iterator.remove</tt>, | |
709 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and | |
710 * <tt>clear</tt> operations. It does not support the <tt>add</tt> or | |
711 * <tt>addAll</tt> operations. | |
712 * | |
713 * @return a set view of the keys contained in this map. | |
714 */ | |
715 public Set keySet() { | |
716 if (mKeySet == null) { | |
717 mKeySet = new AbstractSet() { | |
718 public Iterator iterator() { | |
719 return getHashIterator(IdentityMap.KEYS); | |
720 } | |
721 public int size() { | |
722 return mCount; | |
723 } | |
724 public boolean contains(Object o) { | |
725 return containsKey(o); | |
726 } | |
727 public boolean remove(Object o) { | |
728 if (o == null) { | |
729 if (SoftHashMap.this.containsKey(null)) { | |
730 SoftHashMap.this.remove(null); | |
731 return true; | |
732 } | |
733 else { | |
734 return false; | |
735 } | |
736 } | |
737 else { | |
738 return SoftHashMap.this.remove(o) != null; | |
739 } | |
740 } | |
741 public void clear() { | |
742 SoftHashMap.this.clear(); | |
743 } | |
744 public String toString() { | |
745 return IdentityMap.toString(this); | |
746 } | |
747 }; | |
748 } | |
749 return mKeySet; | |
750 } | |
751 | |
752 /** | |
753 * Returns a collection view of the values contained in this map. The | |
754 * collection is backed by the map, so changes to the map are reflected in | |
755 * the collection, and vice-versa. The collection supports element | |
756 * removal, which removes the corresponding mapping from this map, via the | |
757 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, | |
758 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. | |
759 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. | |
760 * | |
761 * @return a collection view of the values contained in this map. | |
762 */ | |
763 public Collection values() { | |
764 if (mValues==null) { | |
765 mValues = new AbstractCollection() { | |
766 public Iterator iterator() { | |
767 return getHashIterator(IdentityMap.VALUES); | |
768 } | |
769 public int size() { | |
770 return mCount; | |
771 } | |
772 public boolean contains(Object o) { | |
773 return containsValue(o); | |
774 } | |
775 public void clear() { | |
776 SoftHashMap.this.clear(); | |
777 } | |
778 public String toString() { | |
779 return IdentityMap.toString(this); | |
780 } | |
781 }; | |
782 } | |
783 return mValues; | |
784 } | |
785 | |
786 /** | |
787 * Returns a collection view of the mappings contained in this map. Each | |
788 * element in the returned collection is a <tt>Map.Entry</tt>. The | |
789 * collection is backed by the map, so changes to the map are reflected in | |
790 * the collection, and vice-versa. The collection supports element | |
791 * removal, which removes the corresponding mapping from the map, via the | |
792 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, | |
793 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. | |
794 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. | |
795 * | |
796 * @return a collection view of the mappings contained in this map. | |
797 * @see Map.Entry | |
798 */ | |
799 public Set entrySet() { | |
800 if (mEntrySet==null) { | |
801 mEntrySet = new AbstractSet() { | |
802 public Iterator iterator() { | |
803 return getHashIterator(IdentityMap.ENTRIES); | |
804 } | |
805 | |
806 public boolean contains(Object o) { | |
807 if (!(o instanceof Map.Entry)) { | |
808 return false; | |
809 } | |
810 Map.Entry entry = (Map.Entry)o; | |
811 Object key = entry.getKey(); | |
812 | |
813 Entry tab[] = mTable; | |
814 int hash = key == null ? 0 : key.hashCode(); | |
815 int index = (hash & 0x7FFFFFFF) % tab.length; | |
816 | |
817 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { | |
818 Object entryValue = e.getValue(); | |
819 | |
820 if (entryValue == null) { | |
821 // Clean up after a cleared Reference. | |
822 mModCount++; | |
823 if (prev != null) { | |
824 prev.mNext = e.mNext; | |
825 } | |
826 else { | |
827 tab[index] = e.mNext; | |
828 } | |
829 mCount--; | |
830 } | |
831 else if (e.mHash == hash && e.equals(entry)) { | |
832 return true; | |
833 } | |
834 else { | |
835 prev = e; | |
836 } | |
837 } | |
838 | |
839 return false; | |
840 } | |
841 | |
842 public boolean remove(Object o) { | |
843 if (!(o instanceof Map.Entry)) { | |
844 return false; | |
845 } | |
846 Map.Entry entry = (Map.Entry)o; | |
847 Object key = entry.getKey(); | |
848 Entry tab[] = mTable; | |
849 int hash = key == null ? 0 : key.hashCode(); | |
850 int index = (hash & 0x7FFFFFFF) % tab.length; | |
851 | |
852 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { | |
853 Object entryValue = e.getValue(); | |
854 | |
855 if (entryValue == null) { | |
856 // Clean up after a cleared Reference. | |
857 mModCount++; | |
858 if (prev != null) { | |
859 prev.mNext = e.mNext; | |
860 } | |
861 else { | |
862 tab[index] = e.mNext; | |
863 } | |
864 mCount--; | |
865 } | |
866 else if (e.mHash == hash && e.equals(entry)) { | |
867 mModCount++; | |
868 if (prev != null) { | |
869 prev.mNext = e.mNext; | |
870 } | |
871 else { | |
872 tab[index] = e.mNext; | |
873 } | |
874 mCount--; | |
875 | |
876 e.setValue(null); | |
877 return true; | |
878 } | |
879 else { | |
880 prev = e; | |
881 } | |
882 } | |
883 return false; | |
884 } | |
885 | |
886 public int size() { | |
887 return mCount; | |
888 } | |
889 | |
890 public void clear() { | |
891 SoftHashMap.this.clear(); | |
892 } | |
893 | |
894 public String toString() { | |
895 return IdentityMap.toString(this); | |
896 } | |
897 }; | |
898 } | |
899 | |
900 return mEntrySet; | |
901 } | |
902 | |
903 public String toString() { | |
904 StringBuffer buf = new StringBuffer(); | |
905 Iterator it = entrySet().iterator(); | |
906 | |
907 buf.append("{"); | |
908 for (int i = 0; it.hasNext(); i++) { | |
909 if (i > 0) { | |
910 buf.append(", "); | |
911 } | |
912 Map.Entry e = (Map.Entry)it.next(); | |
913 buf.append(e.getKey() + "=" + e.getValue()); | |
914 } | |
915 buf.append("}"); | |
916 return buf.toString(); | |
917 } | |
918 | |
919 private Iterator getHashIterator(int type) { | |
920 if (mCount == 0) { | |
921 return IdentityMap.cEmptyHashIterator; | |
922 } | |
923 else { | |
924 return new HashIterator(type); | |
925 } | |
926 } | |
927 | |
928 /** | |
929 * HashMap collision list entry. | |
930 */ | |
931 private static class Entry implements Map.Entry { | |
932 int mHash; | |
933 Object mKey; | |
934 Entry mNext; | |
935 | |
936 private Reference mValue; | |
937 | |
938 Entry(int hash, Object key, Object value, Entry next) { | |
939 mHash = hash; | |
940 mKey = key; | |
941 mValue = new SoftReference(value); | |
942 mNext = next; | |
943 } | |
944 | |
945 private Entry(int hash, Object key, Reference value, Entry next) { | |
946 mHash = hash; | |
947 mKey = key; | |
948 mValue = value; | |
949 mNext = next; | |
950 } | |
951 | |
952 protected Object clone() { | |
953 return new Entry(mHash, mKey, (Reference)mValue, | |
954 (mNext==null ? null : (Entry)mNext.clone())); | |
955 } | |
956 | |
957 // Map.Entry Ops | |
958 | |
959 public Object getKey() { | |
960 return mKey; | |
961 } | |
962 | |
963 public Object getValue() { | |
964 return mValue.get(); | |
965 } | |
966 | |
967 public Object setValue(Object value) { | |
968 Object oldValue = getValue(); | |
969 if (value == null) { | |
970 mValue.clear(); | |
971 } | |
972 else { | |
973 mValue = new SoftReference(value); | |
974 } | |
975 return oldValue; | |
976 } | |
977 | |
978 public boolean equals(Object o) { | |
979 if (!(o instanceof Map.Entry)) { | |
980 return false; | |
981 } | |
982 Map.Entry e = (Map.Entry)o; | |
983 | |
984 Object value = getValue(); | |
985 | |
986 return (mKey==null ? e.getKey()==null : mKey.equals(e.getKey())) && | |
987 (value==null ? e.getValue()==null : value.equals(e.getValue())); | |
988 } | |
989 | |
990 public int hashCode() { | |
991 Object value = getValue(); | |
992 return mHash ^ (value==null ? 0 : value.hashCode()); | |
993 } | |
994 | |
995 public String toString() { | |
996 return mKey + "=" + getValue(); | |
997 } | |
998 } | |
999 | |
1000 private class HashIterator implements Iterator { | |
1001 private Entry[] mTable = SoftHashMap.this.mTable; | |
1002 private int mIndex = mTable.length; | |
1003 private Entry mEntry; | |
1004 // To ensure that the iterator doesn't return cleared entries, keep a | |
1005 // hard reference to the value. Its existence will prevent the soft | |
1006 // value from being cleared. | |
1007 private Object mEntryValue; | |
1008 private Entry mLastReturned; | |
1009 private int mType; | |
1010 | |
1011 /** | |
1012 * The modCount value that the iterator believes that the backing | |
1013 * List should have. If this expectation is violated, the iterator | |
1014 * has detected concurrent modification. | |
1015 */ | |
1016 private int expectedModCount = mModCount; | |
1017 | |
1018 HashIterator(int type) { | |
1019 mType = type; | |
1020 } | |
1021 | |
1022 public boolean hasNext() { | |
1023 while (mEntry == null || | |
1024 (mEntryValue = mEntry.getValue()) == null) { | |
1025 if (mEntry != null) { | |
1026 // Clean up after a cleared Reference. | |
1027 remove(mEntry); | |
1028 mEntry = mEntry.mNext; | |
1029 } | |
1030 | |
1031 if (mEntry == null) { | |
1032 if (mIndex <= 0) { | |
1033 return false; | |
1034 } | |
1035 else { | |
1036 mEntry = mTable[--mIndex]; | |
1037 } | |
1038 } | |
1039 } | |
1040 | |
1041 return true; | |
1042 } | |
1043 | |
1044 public Object next() { | |
1045 if (mModCount != expectedModCount) { | |
1046 throw new ConcurrentModificationException(); | |
1047 } | |
1048 | |
1049 if (!hasNext()) { | |
1050 throw new NoSuchElementException(); | |
1051 } | |
1052 | |
1053 mLastReturned = mEntry; | |
1054 mEntry = mEntry.mNext; | |
1055 | |
1056 if (mType == IdentityMap.KEYS) { | |
1057 return mLastReturned.getKey(); | |
1058 } | |
1059 else if (mType == IdentityMap.VALUES) { | |
1060 Object value = mLastReturned.getValue(); | |
1061 return (value instanceof Null) ? null : value; | |
1062 } | |
1063 else { | |
1064 return mLastReturned; | |
1065 } | |
1066 } | |
1067 | |
1068 public void remove() { | |
1069 if (mLastReturned == null) { | |
1070 throw new IllegalStateException(); | |
1071 } | |
1072 if (mModCount != expectedModCount) { | |
1073 throw new ConcurrentModificationException(); | |
1074 } | |
1075 remove(mLastReturned); | |
1076 mLastReturned = null; | |
1077 } | |
1078 | |
1079 private void remove(Entry toRemove) { | |
1080 Entry[] tab = mTable; | |
1081 int index = (toRemove.mHash & 0x7FFFFFFF) % tab.length; | |
1082 | |
1083 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { | |
1084 if (e == toRemove) { | |
1085 mModCount++; | |
1086 expectedModCount++; | |
1087 if (prev == null) { | |
1088 tab[index] = e.mNext; | |
1089 } | |
1090 else { | |
1091 prev.mNext = e.mNext; | |
1092 } | |
1093 mCount--; | |
1094 return; | |
1095 } | |
1096 else { | |
1097 prev = e; | |
1098 } | |
1099 } | |
1100 throw new ConcurrentModificationException(); | |
1101 } | |
1102 } | |
1103 | |
1104 /** | |
1105 * This allows null references to be saved into SoftHashMap and allow | |
1106 * entries to still be garbage collected. | |
1107 */ | |
1108 static class Null { | |
1109 public boolean equals(Object other) { | |
1110 return other == null || other instanceof Null; | |
1111 } | |
1112 | |
1113 public String toString() { | |
1114 return "null"; | |
1115 } | |
1116 } | |
1117 } |