Source code: edu/emory/mathcs/util/VolatileHashMap.java
1 /* ***** BEGIN LICENSE BLOCK *****
2 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
3 *
4 * The contents of this file are subject to the Mozilla Public License Version
5 * 1.1 (the "License"); you may not use this file except in compliance with
6 * the License. You may obtain a copy of the License at
7 * http://www.mozilla.org/MPL/
8 *
9 * Software distributed under the License is distributed on an "AS IS" basis,
10 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
11 * for the specific language governing rights and limitations under the
12 * License.
13 *
14 * The Original Code is the Emory Utilities.
15 *
16 * The Initial Developer of the Original Code is
17 * The Distributed Computing Laboratory, Emory University.
18 * Portions created by the Initial Developer are Copyright (C) 2002
19 * the Initial Developer. All Rights Reserved.
20 *
21 * Alternatively, the contents of this file may be used under the terms of
22 * either the GNU General Public License Version 2 or later (the "GPL"), or
23 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
24 * in which case the provisions of the GPL or the LGPL are applicable instead
25 * of those above. If you wish to allow use of your version of this file only
26 * under the terms of either the GPL or the LGPL, and not to allow others to
27 * use your version of this file under the terms of the MPL, indicate your
28 * decision by deleting the provisions above and replace them with the notice
29 * and other provisions required by the GPL or the LGPL. If you do not delete
30 * the provisions above, a recipient may use your version of this file under
31 * the terms of any one of the MPL, the GPL or the LGPL.
32 *
33 * ***** END LICENSE BLOCK ***** */
34
35 package edu.emory.mathcs.util;
36
37 import java.util.*;
38 import java.lang.ref.WeakReference;
39 import java.lang.ref.ReferenceQueue;
40
41
42 /**
43 * A hashtable-based <tt>Map</tt> implementation with <em>weak values</em>.
44 * An entry in a <tt>VolatileHashMap</tt> will automatically be removed when
45 * its <i>value</i> is no longer in ordinary use. More precisely, the presence
46 * of a mapping to a given value will not prevent the value from being discarded
47 * by the garbage collector, that is, made finalizable, finalized, and then
48 * reclaimed. When a value has been discarded, all entries referring to it are
49 * effectively removed from the map. This class is a companion to
50 * {@link java.util.WeakHashMap}.
51 *
52 * <p> Null values and the null key are supported. This class has
53 * performance characteristics similar to those of the <tt>HashMap</tt>
54 * class, and has the same efficiency parameters of <em>initial capacity</em>
55 * and <em>load factor</em>.
56 *
57 * <p> Like most collection classes, this class is not synchronized. A
58 * synchronized <tt>VolatileHashMap</tt> may be constructed using the
59 * <tt>Collections.synchronizedMap</tt> method.
60 *
61 * <p> The behavior of the <tt>VolatileHashMap</tt> class depends in part upon
62 * the actions of the garbage collector, so several familiar (though not
63 * required) <tt>Map</tt> invariants do not hold for this class. Because
64 * the garbage collector may discard entries at any time, a
65 * <tt>VolatileHashMap</tt> may behave as though an unknown thread is silently
66 * removing entries. In particular, even if you synchronize on a
67 * <tt>VolatileHashMap</tt> instance and invoke none of its mutator methods, it
68 * is possible for the <tt>size</tt> method to return smaller values over
69 * time, for the <tt>isEmpty</tt> method to return <tt>false</tt> and
70 * then <tt>true</tt>, for the <tt>containsKey</tt> method to return
71 * <tt>true</tt> and later <tt>false</tt> for a given key, for the
72 * <tt>get</tt> method to return a value for a given key but later return
73 * <tt>null</tt>, for the <tt>put</tt> method to return
74 * <tt>null</tt> and the <tt>remove</tt> method to return
75 * <tt>false</tt> for a key that previously appeared to be in the map, and
76 * for successive examinations of the key set, the value set, and the entry set
77 * to yield successively smaller numbers of elements.
78 *
79 * <p>The iterators returned by all of this class's "collection view methods"
80 * are <i>fail-fast</i>: if the map is structurally modified at any time after
81 * the iterator is created, in any way except through the iterator's own
82 * <tt>remove</tt> or <tt>add</tt> methods, the iterator will throw a
83 * <tt>ConcurrentModificationException</tt>. Thus, in the face of concurrent
84 * modification, the iterator fails quickly and cleanly, rather than risking
85 * arbitrary, non-determixnistic behavior at an undetermined time in the
86 * future.
87 *
88 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
89 * as it is, generally speaking, impossible to make any hard guarantees in the
90 * presence of unsynchronized concurrent modification. Fail-fast iterators
91 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
92 * Therefore, it would be wrong to write a program that depended on this
93 * exception for its correctness: <i>the fail-fast behavior of iterators
94 * should be used only to detect bugs.</i>
95 *
96 * @see java.util.WeakHashMap
97 */
98 public class VolatileHashMap /*extends AbstractMap*/ implements Map {
99
100 /**
101 * The default initial capacity -- MUST be a power of two.
102 */
103 private static final int DEFAULT_INITIAL_CAPACITY = 16;
104
105 /**
106 * The maximum capacity, used if a higher value is implicitly specified
107 * by either of the constructors with arguments.
108 * MUST be a power of two <= 1<<30.
109 */
110 private static final int MAXIMUM_CAPACITY = 1 << 30;
111
112 /**
113 * The load fast used when none specified in constructor.
114 */
115 private static final float DEFAULT_LOAD_FACTOR = 0.75f;
116
117 /**
118 * The table, resized as necessary. Length MUST Always be a power of two.
119 */
120 private Entry[] table;
121
122 /**
123 * The number of key-value mappings contained in this weak hash map.
124 */
125 private int size;
126
127 /**
128 * The next size value at which to resize (capacity * load factor).
129 */
130 private int threshold;
131
132 /**
133 * The load factor for the hash table.
134 */
135 private final float loadFactor;
136
137 /**
138 * Reference queue for cleared WeakEntries
139 */
140 private final ReferenceQueue queue = new ReferenceQueue();
141
142 /**
143 * The number of times this HashMap has been structurally modified
144 * Structural modifications are those that change the number of mappings in
145 * the HashMap or otherwise modify its internal structure (e.g.,
146 * rehash). This field is used to make iterators on Collection-views of
147 * the HashMap fail-fast. (See ConcurrentModificationException).
148 */
149 private volatile int modCount;
150
151 /**
152 * Each of these fields are initialized to contain an instance of the
153 * appropriate view the first time this view is requested. The views are
154 * stateless, so there's no reason to create more than one of each.
155 */
156 transient volatile Set keySet = null;
157 transient volatile Collection values = null;
158
159 /**
160 * Constructs a new, empty <tt>VolatileHashMap</tt> with the given initial
161 * capacity and the given load factor.
162 *
163 * @param initialCapacity The initial capacity of the <tt>VolatileHashMap</tt>
164 * @param loadFactor The load factor of the <tt>VolatileHashMap</tt>
165 * @throws IllegalArgumentException If the initial capacity is negative,
166 * or if the load factor is nonpositive.
167 */
168 public VolatileHashMap(int initialCapacity, float loadFactor) {
169 if (initialCapacity < 0)
170 throw new IllegalArgumentException("Illegal Initial Capacity: "+
171 initialCapacity);
172 if (initialCapacity > MAXIMUM_CAPACITY)
173 initialCapacity = MAXIMUM_CAPACITY;
174
175 if (loadFactor <= 0 || Float.isNaN(loadFactor))
176 throw new IllegalArgumentException("Illegal Load factor: "+
177 loadFactor);
178 int capacity = 1;
179 while (capacity < initialCapacity)
180 capacity <<= 1;
181 table = new Entry[capacity];
182 this.loadFactor = loadFactor;
183 threshold = (int)(capacity * loadFactor);
184 }
185
186 /**
187 * Constructs a new, empty <tt>VolatileHashMap</tt> with the given initial
188 * capacity and the default load factor, which is <tt>0.75</tt>.
189 *
190 * @param initialCapacity The initial capacity of the <tt>VolatileHashMap</tt>
191 * @throws IllegalArgumentException If the initial capacity is negative.
192 */
193 public VolatileHashMap(int initialCapacity) {
194 this(initialCapacity, DEFAULT_LOAD_FACTOR);
195 }
196
197 /**
198 * Constructs a new, empty <tt>VolatileHashMap</tt> with the default initial
199 * capacity (16) and the default load factor (0.75).
200 */
201 public VolatileHashMap() {
202 this.loadFactor = DEFAULT_LOAD_FACTOR;
203 threshold = (int)(DEFAULT_INITIAL_CAPACITY);
204 table = new Entry[DEFAULT_INITIAL_CAPACITY];
205 }
206
207 /**
208 * Constructs a new <tt>VolatileHashMap</tt> with the same mappings as the
209 * specified <tt>Map</tt>. The <tt>VolatileHashMap</tt> is created with
210 * default load factor, which is <tt>0.75</tt> and an initial capacity
211 * sufficient to hold the mappings in the specified <tt>Map</tt>.
212 *
213 * @param t the map whose mappings are to be placed in this map.
214 * @throws NullPointerException if the specified map is null.
215 * @since 1.3
216 */
217 public VolatileHashMap(Map t) {
218 this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, 16),
219 DEFAULT_LOAD_FACTOR);
220 putAll(t);
221 }
222
223 // internal utilities
224
225 /**
226 * Value representing null keys inside tables.
227 */
228 private static final Object NULL_KEY = new Object();
229
230 /**
231 * Use NULL_KEY for key if it is null.
232 */
233 private static Object maskNull(Object key) {
234 return (key == null ? NULL_KEY : key);
235 }
236
237 /**
238 * Return internal representation of null key back to caller as null
239 */
240 private static Object unmaskNull(Object key) {
241 return (key == NULL_KEY ? null : key);
242 }
243
244 /**
245 * Return a hash code for non-null Object x.
246 */
247 int hash(Object x) {
248 int h = x.hashCode();
249 return h - (h << 7); // i.e., -127 * h
250 }
251
252 /**
253 * Check for equality of non-null reference x and possibly-null y. By
254 * default uses Object.equals.
255 */
256 boolean eq(Object x, Object y) {
257 return x == y || x.equals(y);
258 }
259
260 /**
261 * Return index for hash code h.
262 */
263 static int indexFor(int h, int length) {
264 return h & (length-1);
265 }
266
267 /**
268 * Expunge stale entries from the table.
269 */
270 private void expungeStaleEntries() {
271 Object r;
272 while ( (r = queue.poll()) != null) {
273 Entry e = ((Entry.ValueRef)r).base;
274 if (e == null) continue;
275 int h = e.hash;
276 int i = indexFor(h, table.length);
277
278 Entry prev = table[i];
279 Entry p = prev;
280 while (p != null) {
281 Entry next = p.next;
282 if (p == e) {
283 if (prev == e)
284 table[i] = next;
285 else
286 prev.next = next;
287 e.next = null; // Help GC
288 e.key = null; // " "
289 e.setValue(null); // " "
290 size--;
291 break;
292 }
293 prev = p;
294 p = next;
295 }
296 }
297 }
298
299 /**
300 * Return the table after first expunging stale entries
301 */
302 private Entry[] getTable() {
303 expungeStaleEntries();
304 return table;
305 }
306
307 /**
308 * Returns the number of key-value mappings in this map.
309 * This result is a snapshot, and may not reflect unprocessed
310 * entries that will be removed before next attempted access
311 * because they are no longer referenced.
312 */
313 public int size() {
314 if (size == 0)
315 return 0;
316 expungeStaleEntries();
317 return size;
318 }
319
320 /**
321 * Returns <tt>true</tt> if this map contains no key-value mappings.
322 * This result is a snapshot, and may not reflect unprocessed
323 * entries that will be removed before next attempted access
324 * because they are no longer referenced.
325 */
326 public boolean isEmpty() {
327 return size() == 0;
328 }
329
330 /**
331 * Returns the value to which the specified key is mapped in this volatile
332 * hash map, or <tt>null</tt> if the map contains no mapping for
333 * this key. A return value of <tt>null</tt> does not <i>necessarily</i>
334 * indicate that the map contains no mapping for the key; it is also
335 * possible that the map explicitly maps the key to <tt>null</tt>. The
336 * <tt>containsKey</tt> method may be used to distinguish these two
337 * cases.
338 *
339 * @param key the key whose associated value is to be returned.
340 * @return the value to which this map maps the specified key, or
341 * <tt>null</tt> if the map contains no mapping for this key.
342 * @see #put(Object, Object)
343 */
344 public Object get(Object key) {
345 Object k = maskNull(key);
346 int h = hash(k);
347 Entry[] tab = getTable();
348 int index = indexFor(h, tab.length);
349 Entry e = tab[index];
350 while (e != null) {
351 if (e.hash == h && eq(k, e.getKey()))
352 return e.getValue();
353 e = e.next;
354 }
355 return null;
356 }
357
358 /**
359 * Returns <tt>true</tt> if this map contains a mapping for the
360 * specified key.
361 *
362 * @param key The key whose presence in this map is to be tested
363 * @return <tt>true</tt> if there is a mapping for <tt>key</tt>;
364 * <tt>false</tt> otherwise
365 */
366 public boolean containsKey(Object key) {
367 return getEntry(key) != null;
368 }
369
370 /**
371 * Returns the entry associated with the specified key in the HashMap.
372 * Returns null if the HashMap contains no mapping for this key.
373 */
374 Entry getEntry(Object key) {
375 Object k = maskNull(key);
376 int h = hash(k);
377 Entry[] tab = getTable();
378 int index = indexFor(h, tab.length);
379 Entry e = tab[index];
380 while (e != null && !(e.hash == h && eq(k, e.getKey())))
381 e = e.next;
382 return e;
383 }
384
385 /**
386 * Associates the specified value with the specified key in this map.
387 * If the map previously contained a mapping for this key, the old
388 * value is replaced.
389 *
390 * @param key key with which the specified value is to be associated.
391 * @param value value to be associated with the specified key.
392 * @return previous value associated with specified key, or <tt>null</tt>
393 * if there was no mapping for key. A <tt>null</tt> return can
394 * also indicate that the HashMap previously associated
395 * <tt>null</tt> with the specified key.
396 */
397 public Object put(Object key, Object value) {
398 Object k = maskNull(key);
399 int h = hash(k);
400 Entry[] tab = getTable();
401 int i = indexFor(h, tab.length);
402
403 for (Entry e = tab[i]; e != null; e = e.next) {
404 if (h == e.hash && eq(k, e.getKey())) {
405 Object oldValue = e.getValue();
406 if (value != oldValue)
407 e.setValue(value);
408 return oldValue;
409 }
410 }
411
412 modCount++;
413 tab[i] = new Entry(k, value, queue, h, tab[i]);
414 if (++size >= threshold)
415 resize(tab.length * 2);
416 return null;
417 }
418
419 /**
420 * Rehashes the contents of this map into a new <tt>HashMap</tt> instance
421 * with a larger capacity. This method is called automatically when the
422 * number of keys in this map exceeds its capacity and load factor.
423 *
424 * Note that this method is a no-op if it's called with newCapacity ==
425 * 2*MAXIMUM_CAPACITY (which is Integer.MIN_VALUE).
426 *
427 * @param newCapacity the new capacity, MUST be a power of two.
428 */
429 void resize(int newCapacity) {
430 // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
431
432 Entry[] oldTable = getTable();
433 int oldCapacity = oldTable.length;
434
435 // check if needed
436 if (size < threshold || oldCapacity > newCapacity)
437 return;
438
439 Entry[] newTable = new Entry[newCapacity];
440
441 transfer(oldTable, newTable);
442 table = newTable;
443
444 /*
445 * If ignoring null elements and processing ref queue caused massive
446 * shrinkage, then restore old table. This should be rare, but avoids
447 * unbounded expansion of garbage-filled tables.
448 */
449 if (size >= threshold / 2) {
450 threshold = (int)(newCapacity * loadFactor);
451 } else {
452 expungeStaleEntries();
453 transfer(newTable, oldTable);
454 table = oldTable;
455 }
456 }
457
458 /** Transfer all entries from src to dest tables */
459 private void transfer(Entry[] src, Entry[] dest) {
460 for (int j = 0; j < src.length; ++j) {
461 Entry e = src[j];
462 src[j] = null;
463 while (e != null) {
464 Entry next = e.next;
465 Object val = e.getValue();
466 if (val == null) {
467 e.next = null; // Help GC
468 e.setValue(null); // " "
469 size--;
470 } else {
471 int i = indexFor(e.hash, dest.length);
472 e.next = dest[i];
473 dest[i] = e;
474 }
475 e = next;
476 }
477 }
478 }
479
480 /**
481 * Copies all of the mappings from the specified map to this map These
482 * mappings will replace any mappings that this map had for any of the
483 * keys currently in the specified map.<p>
484 *
485 * @param t mappings to be stored in this map.
486 * @throws NullPointerException if the specified map is null.
487 */
488 public void putAll(Map t) {
489 // Expand enough to hold t's elements without resizing.
490 int n = t.size();
491 if (n == 0)
492 return;
493 if (n >= threshold) {
494 n = (int)(n / loadFactor + 1);
495 if (n > MAXIMUM_CAPACITY)
496 n = MAXIMUM_CAPACITY;
497 int capacity = table.length;
498 while (capacity < n)
499 capacity <<= 1;
500 resize(capacity);
501 }
502
503 for (Iterator i = t.entrySet().iterator(); i.hasNext(); ) {
504 Map.Entry e = (Map.Entry) i.next();
505 put(e.getKey(), e.getValue());
506 }
507 }
508
509 /**
510 * Removes the mapping for this key from this map if present.
511 *
512 * @param key key whose mapping is to be removed from the map.
513 * @return previous value associated with specified key, or <tt>null</tt>
514 * if there was no mapping for key. A <tt>null</tt> return can
515 * also indicate that the map previously associated <tt>null</tt>
516 * with the specified key.
517 */
518 public Object remove(Object key) {
519 Object k = maskNull(key);
520 int h = hash(k);
521 Entry[] tab = getTable();
522 int i = indexFor(h, tab.length);
523 Entry prev = tab[i];
524 Entry e = prev;
525
526 while (e != null) {
527 Entry next = e.next;
528 if (h == e.hash && eq(k, e.getKey())) {
529 modCount++;
530 size--;
531 if (prev == e)
532 tab[i] = next;
533 else
534 prev.next = next;
535 return e.getValue();
536 }
537 prev = e;
538 e = next;
539 }
540
541 return null;
542 }
543
544
545
546 /** Special version of remove needed by Entry set */
547 Entry removeMapping(Object o) {
548 if (!(o instanceof Map.Entry))
549 return null;
550 Entry[] tab = getTable();
551 Map.Entry entry = (Map.Entry)o;
552 Object k = maskNull(entry.getKey());
553 int h = hash(k);
554 int i = indexFor(h, tab.length);
555 Entry prev = tab[i];
556 Entry e = prev;
557
558 while (e != null) {
559 Entry next = e.next;
560 if (h == e.hash && e.equals(entry)) {
561 modCount++;
562 size--;
563 if (prev == e)
564 tab[i] = next;
565 else
566 prev.next = next;
567 return e;
568 }
569 prev = e;
570 e = next;
571 }
572
573 return null;
574 }
575
576 /**
577 * Removes all mappings from this map.
578 */
579 public void clear() {
580 // clear out ref queue. We don't need to expunge entries
581 // since table is getting cleared.
582 while (queue.poll() != null)
583 ;
584
585 modCount++;
586 Entry tab[] = table;
587 for (int i = 0; i < tab.length; ++i)
588 tab[i] = null;
589 size = 0;
590
591 // Allocation of array may have caused GC, which may have caused
592 // additional entries to go stale. Removing these entries from the
593 // reference queue will make them eligible for reclamation.
594 while (queue.poll() != null)
595 ;
596 }
597
598 /**
599 * Returns <tt>true</tt> if this map maps one or more keys to the
600 * specified value.
601 *
602 * @param value value whose presence in this map is to be tested.
603 * @return <tt>true</tt> if this map maps one or more keys to the
604 * specified value.
605 */
606 public boolean containsValue(Object value) {
607 if (value==null)
608 return containsNullValue();
609
610 Entry tab[] = getTable();
611 for (int i = tab.length ; i-- > 0 ;)
612 for (Entry e = tab[i] ; e != null ; e = e.next)
613 if (value.equals(e.getValue()))
614 return true;
615 return false;
616 }
617
618 /**
619 * Special-case code for containsValue with null argument
620 */
621 private boolean containsNullValue() {
622 Entry tab[] = getTable();
623 for (int i = tab.length ; i-- > 0 ;)
624 for (Entry e = tab[i] ; e != null ; e = e.next)
625 if (e.getValue()==null)
626 return true;
627 return false;
628 }
629
630 /**
631 * The entries in this hash table
632 */
633 private static class Entry implements Map.Entry {
634
635 private static class ValueRef extends WeakReference {
636 volatile Entry base;
637 ReferenceQueue q;
638 ValueRef(Entry base, Object value, ReferenceQueue q) {
639 super(value, q);
640 this.base = base;
641 }
642 }
643
644 private Object key;
645 private ReferenceQueue refqueue;
646 private ValueRef value;
647 private final int hash;
648 private Entry next;
649
650 /**
651 * Create new entry.
652 */
653 Entry(Object key, Object value, ReferenceQueue queue,
654 int hash, Entry next) {
655 this.key = key;
656 this.hash = hash;
657 this.next = next;
658 this.refqueue = queue;
659 this.value = new ValueRef(this, value, queue);
660 }
661
662 public Object getKey() {
663 return key;
664 // return unmaskNull(key);
665 }
666
667 public Object getValue() {
668 return value == null ? null : value.get();
669 }
670
671 public Object setValue(Object newValue) {
672 Object oldValue;
673 if (value != null) {
674 oldValue = value.get();
675 value.base = null;
676 value.clear();
677 } else {
678 oldValue = null;
679 }
680 value = newValue != null ? new ValueRef(this, newValue, refqueue) : null;
681 return oldValue;
682
683 }
684
685 public boolean equals(Object o) {
686 if (!(o instanceof Map.Entry))
687 return false;
688 Map.Entry e = (Map.Entry)o;
689 Object k1 = getKey();
690 Object k2 = e.getKey();
691 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
692 Object v1 = getValue();
693 Object v2 = e.getValue();
694 if (v1 == v2 || (v1 != null && v1.equals(v2)))
695 return true;
696 }
697 return false;
698 }
699
700 public int hashCode() {
701 Object k = getKey();
702 Object v = getValue();
703 return ((k==null ? 0 : k.hashCode()) ^
704 (v==null ? 0 : v.hashCode()));
705 }
706
707 public String toString() {
708 return getKey() + "=" + getValue();
709 }
710 }
711
712 private abstract class HashIterator implements Iterator {
713 int index;
714 Entry entry = null;
715 Entry lastReturned = null;
716 int expectedModCount = modCount;
717
718 /**
719 * Strong reference needed to avoid disappearance of entry
720 * between hasNext and next
721 */
722 Object nextVal = null;
723
724 /**
725 * Strong reference needed to avoid disappearance of entry
726 * between nextEntry() and any use of the entry
727 */
728 Object currentVal = null;
729
730 HashIterator() {
731 index = (size() != 0 ? table.length : 0);
732 }
733
734 public boolean hasNext() {
735 Entry[] t = table;
736
737 while (nextVal == null) {
738 Entry e = entry;
739 int i = index;
740 while (e == null && i > 0)
741 e = t[--i];
742 entry = e;
743 index = i;
744 if (e == null) {
745 currentVal = null;
746 return false;
747 }
748 nextVal = e.getValue(); // hold on to val in strong ref
749 if (nextVal == null)
750 entry = entry.next;
751 }
752 return true;
753 }
754
755 /** The common parts of next() across different types of iterators */
756 protected Entry nextEntry() {
757 if (modCount != expectedModCount)
758 throw new ConcurrentModificationException();
759 if (nextVal == null && !hasNext())
760 throw new NoSuchElementException();
761
762 lastReturned = entry;
763 entry = entry.next;
764 currentVal = nextVal;
765 nextVal = null;
766 return lastReturned;
767 }
768
769 public void remove() {
770 if (lastReturned == null)
771 throw new IllegalStateException();
772 if (modCount != expectedModCount)
773 throw new ConcurrentModificationException();
774
775 VolatileHashMap.this.remove(entry.getKey());
776 expectedModCount = modCount;
777 lastReturned = null;
778 currentVal = null;
779 }
780
781 }
782
783 private class ValueIterator extends HashIterator {
784 public Object next() {
785 return nextEntry().getValue();
786 }
787 }
788
789 private class KeyIterator extends HashIterator {
790 public Object next() {
791 return nextEntry().getKey();
792 }
793 }
794
795 private class EntryIterator extends HashIterator {
796 public Object next() {
797 return nextEntry();
798 }
799 }
800
801 // Views
802
803 private transient Set entrySet = null;
804
805 /**
806 * Returns a set view of the keys contained in this map. The set is
807 * backed by the map, so changes to the map are reflected in the set, and
808 * vice-versa. The set supports element removal, which removes the
809 * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
810 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
811 * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
812 * <tt>addAll</tt> operations.
813 *
814 * @return a set view of the keys contained in this map.
815 */
816 public Set keySet() {
817 Set ks = keySet;
818 return (ks != null ? ks : (keySet = new KeySet()));
819 }
820
821 private class KeySet extends AbstractSet {
822 public Iterator iterator() {
823 return new KeyIterator();
824 }
825
826 public int size() {
827 return VolatileHashMap.this.size();
828 }
829
830 public boolean contains(Object o) {
831 return containsKey(o);
832 }
833
834 public boolean remove(Object o) {
835 if (containsKey(o)) {
836 VolatileHashMap.this.remove(o);
837 return true;
838 }
839 else
840 return false;
841 }
842
843 public void clear() {
844 VolatileHashMap.this.clear();
845 }
846
847 public Object[] toArray() {
848 Collection c = new ArrayList(size());
849 for (Iterator i = iterator(); i.hasNext(); )
850 c.add(i.next());
851 return c.toArray();
852 }
853
854 public Object[] toArray(Object a[]) {
855 Collection c = new ArrayList(size());
856 for (Iterator i = iterator(); i.hasNext(); )
857 c.add(i.next());
858 return c.toArray(a);
859 }
860 }
861
862 /**
863 * Returns a collection view of the values contained in this map. The
864 * collection is backed by the map, so changes to the map are reflected in
865 * the collection, and vice-versa. The collection supports element
866 * removal, which removes the corresponding mapping from this map, via the
867 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
868 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
869 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
870 *
871 * @return a collection view of the values contained in this map.
872 */
873 public Collection values() {
874 Collection vs = values;
875 return (vs != null ? vs : (values = new Values()));
876 }
877
878 private class Values extends AbstractCollection {
879 public Iterator iterator() {
880 return new ValueIterator();
881 }
882
883 public int size() {
884 return VolatileHashMap.this.size();
885 }
886
887 public boolean contains(Object o) {
888 return containsValue(o);
889 }
890
891 public void clear() {
892 VolatileHashMap.this.clear();
893 }
894
895 public Object[] toArray() {
896 Collection c = new ArrayList(size());
897 for (Iterator i = iterator(); i.hasNext(); )
898 c.add(i.next());
899 return c.toArray();
900 }
901
902 public Object[] toArray(Object a[]) {
903 Collection c = new ArrayList(size());
904 for (Iterator i = iterator(); i.hasNext(); )
905 c.add(i.next());
906 return c.toArray(a);
907 }
908 }
909
910 /**
911 * Returns a collection view of the mappings contained in this map. Each
912 * element in the returned collection is a <tt>Map.Entry</tt>. The
913 * collection is backed by the map, so changes to the map are reflected in
914 * the collection, and vice-versa. The collection supports element
915 * removal, which removes the corresponding mapping from the map, via the
916 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
917 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
918 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
919 *
920 * @return a collection view of the mappings contained in this map.
921 * @see Map.Entry
922 */
923 public Set entrySet() {
924 Set es = entrySet;
925 return (es != null ? es : (entrySet = new EntrySet()));
926 }
927
928 private class EntrySet extends AbstractSet {
929 public Iterator iterator() {
930 return new EntryIterator();
931 }
932
933 public boolean contains(Object o) {
934 if (!(o instanceof Map.Entry))
935 return false;
936 Map.Entry e = (Map.Entry)o;
937 Object k = e.getKey();
938 Entry candidate = getEntry(e.getKey());
939 return candidate != null && candidate.equals(e);
940 }
941
942 public boolean remove(Object o) {
943 return removeMapping(o) != null;
944 }
945
946 public int size() {
947 return VolatileHashMap.this.size();
948 }
949
950 public void clear() {
951 VolatileHashMap.this.clear();
952 }
953
954 public Object[] toArray() {
955 Collection c = new ArrayList(size());
956 for (Iterator i = iterator(); i.hasNext(); )
957 c.add(new SimpleEntry((Map.Entry) i.next()));
958 return c.toArray();
959 }
960
961 public Object[] toArray(Object a[]) {
962 Collection c = new ArrayList(size());
963 for (Iterator i = iterator(); i.hasNext(); )
964 c.add(new SimpleEntry((Map.Entry) i.next()));
965 return c.toArray(a);
966 }
967 }
968
969 static class SimpleEntry implements Map.Entry {
970 Object key;
971 Object value;
972
973 public SimpleEntry(Object key, Object value) {
974 this.key = key;
975 this.value = value;
976 }
977
978 public SimpleEntry(Map.Entry e) {
979 this.key = e.getKey();
980 this.value = e.getValue();
981 }
982
983 public Object getKey() {
984 return key;
985 }
986
987 public Object getValue() {
988 return value;
989 }
990
991 public Object setValue(Object value) {
992 Object oldValue = this.value;
993 this.value = value;
994 return oldValue;
995 }
996
997 public boolean equals(Object o) {
998 if (!(o instanceof Map.Entry))
999 return false;
1000 Map.Entry e = (Map.Entry)o;
1001 return eq(key, e.getKey()) && eq(value, e.getValue());
1002 }
1003
1004 public int hashCode() {
1005 Object v;
1006 return ((key == null) ? 0 : key.hashCode()) ^
1007 ((value == null) ? 0 : value.hashCode());
1008 }
1009
1010 public String toString() {
1011 return key + "=" + value;
1012 }
1013
1014 private static boolean eq(Object o1, Object o2) {
1015 return (o1 == null ? o2 == null : o1.equals(o2));
1016 }
1017 }
1018}