Mercurial > hg > blitz_stable

comparison src/EDU/oswego/cs/dl/util/concurrent/ConcurrentReaderHashMap.java @ 0:3dc0c5604566

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 File: ConcurrentReaderHashMap
3
4 Written by Doug Lea. Adapted from JDK1.2 HashMap.java and Hashtable.java
5 which carries the following copyright:
6
7 * Copyright 1997 by Sun Microsystems, Inc.,
8 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
9 * All rights reserved.
10 *
11 * This software is the confidential and proprietary information
12 * of Sun Microsystems, Inc. ("Confidential Information"). You
13 * shall not disclose such Confidential Information and shall use
14 * it only in accordance with the terms of the license agreement
15 * you entered into with Sun.
16
17 History:
18 Date Who What
19 28oct1999 dl Created
20 14dec1999 dl jmm snapshot
21 19apr2000 dl use barrierLock
22 12jan2001 dl public release
23 17nov2001 dl Minor tunings
24 20may2002 dl BarrierLock can now be serialized.
25 09dec2002 dl Fix interference checks.
26 */
27
28 package EDU.oswego.cs.dl.util.concurrent;
29
30 import java.util.Map;
31 import java.util.AbstractMap;
32 import java.util.AbstractSet;
33 import java.util.AbstractCollection;
34 import java.util.Collection;
35 import java.util.Set;
36 import java.util.Iterator;
37 import java.util.Enumeration;
38 import java.util.ConcurrentModificationException;
39 import java.util.NoSuchElementException;
40
41 import java.io.Serializable;
42 import java.io.IOException;
43 import java.io.ObjectInputStream;
44 import java.io.ObjectOutputStream;
45
46
47 /**
48 * A version of Hashtable that supports mostly-concurrent reading, but
49 * exclusive writing. Because reads are not limited to periods
50 * without writes, a concurrent reader policy is weaker than a classic
51 * reader/writer policy, but is generally faster and allows more
52 * concurrency. This class is a good choice especially for tables that
53 * are mainly created by one thread during the start-up phase of a
54 * program, and from then on, are mainly read (with perhaps occasional
55 * additions or removals) in many threads. If you also need concurrency
56 * among writes, consider instead using ConcurrentHashMap.
57 * <p>
58 *
59 * Successful retrievals using get(key) and containsKey(key) usually
60 * run without locking. Unsuccessful ones (i.e., when the key is not
61 * present) do involve brief synchronization (locking). Also, the
62 * size and isEmpty methods are always synchronized.
63 *
64 * <p> Because retrieval operations can ordinarily overlap with
65 * writing operations (i.e., put, remove, and their derivatives),
66 * retrievals can only be guaranteed to return the results of the most
67 * recently <em>completed</em> operations holding upon their
68 * onset. Retrieval operations may or may not return results
69 * reflecting in-progress writing operations. However, the retrieval
70 * operations do always return consistent results -- either those
71 * holding before any single modification or after it, but never a
72 * nonsense result. For aggregate operations such as putAll and
73 * clear, concurrent reads may reflect insertion or removal of only
74 * some entries. In those rare contexts in which you use a hash table
75 * to synchronize operations across threads (for example, to prevent
76 * reads until after clears), you should either encase operations
77 * in synchronized blocks, or instead use java.util.Hashtable.
78 *
79 * <p>
80 *
81 * This class also supports optional guaranteed
82 * exclusive reads, simply by surrounding a call within a synchronized
83 * block, as in <br>
84 * <code>ConcurrentReaderHashMap t; ... Object v; <br>
85 * synchronized(t) { v = t.get(k); } </code> <br>
86 *
87 * But this is not usually necessary in practice. For
88 * example, it is generally inefficient to write:
89 *
90 * <pre>
91 * ConcurrentReaderHashMap t; ... // Inefficient version
92 * Object key; ...
93 * Object value; ...
94 * synchronized(t) {
95 * if (!t.containsKey(key))
96 * t.put(key, value);
97 * // other code if not previously present
98 * }
99 * else {
100 * // other code if it was previously present
101 * }
102 * }
103 *</pre>
104 * Instead, if the values are intended to be the same in each case, just take advantage of the fact that put returns
105 * null if the key was not previously present:
106 * <pre>
107 * ConcurrentReaderHashMap t; ... // Use this instead
108 * Object key; ...
109 * Object value; ...
110 * Object oldValue = t.put(key, value);
111 * if (oldValue == null) {
112 * // other code if not previously present
113 * }
114 * else {
115 * // other code if it was previously present
116 * }
117 *</pre>
118 * <p>
119 *
120 * Iterators and Enumerations (i.e., those returned by
121 * keySet().iterator(), entrySet().iterator(), values().iterator(),
122 * keys(), and elements()) return elements reflecting the state of the
123 * hash table at some point at or since the creation of the
124 * iterator/enumeration. They will return at most one instance of
125 * each element (via next()/nextElement()), but might or might not
126 * reflect puts and removes that have been processed since they were
127 * created. They do <em>not</em> throw ConcurrentModificationException.
128 * However, these iterators are designed to be used by only one
129 * thread at a time. Sharing an iterator across multiple threads may
130 * lead to unpredictable results if the table is being concurrently
131 * modified. Again, you can ensure interference-free iteration by
132 * enclosing the iteration in a synchronized block. <p>
133 *
134 * This class may be used as a direct replacement for any use of
135 * java.util.Hashtable that does not depend on readers being blocked
136 * during updates. Like Hashtable but unlike java.util.HashMap,
137 * this class does NOT allow <tt>null</tt> to be used as a key or
138 * value. This class is also typically faster than ConcurrentHashMap
139 * when there is usually only one thread updating the table, but
140 * possibly many retrieving values from it.
141 * <p>
142 *
143 * Implementation note: A slightly faster implementation of
144 * this class will be possible once planned Java Memory Model
145 * revisions are in place.
146 *
147 * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
148
149 **/
150
151
152 public class ConcurrentReaderHashMap
153 extends AbstractMap
154 implements Map, Cloneable, Serializable {
155
156
157 /*
158 The basic strategy is an optimistic-style scheme based on
159 the guarantee that the hash table and its lists are always
160 kept in a consistent enough state to be read without locking:
161
162 * Read operations first proceed without locking, by traversing the
163 apparently correct list of the apparently correct bin. If an
164 entry is found, but not invalidated (value field null), it is
165 returned. If not found, operations must recheck (after a memory
166 barrier) to make sure they are using both the right list and
167 the right table (which can change under resizes). If
168 invalidated, reads must acquire main update lock to wait out
169 the update, and then re-traverse.
170
171 * All list additions are at the front of each bin, making it easy
172 to check changes, and also fast to traverse. Entry next
173 pointers are never assigned. Remove() builds new nodes when
174 necessary to preserve this.
175
176 * Remove() (also clear()) invalidates removed nodes to alert read
177 operations that they must wait out the full modifications.
178
179 */
180
181 /** A Serializable class for barrier lock **/
182 protected static class BarrierLock implements java.io.Serializable { }
183
184 /**
185 * Lock used only for its memory effects.
186 **/
187 protected final BarrierLock barrierLock = new BarrierLock();
188
189 /**
190 * field written to only to guarantee lock ordering.
191 **/
192
193 protected transient Object lastWrite;
194
195 /**
196 * Force a memory synchronization that will cause
197 * all readers to see table. Call only when already
198 * holding main synch lock.
199 **/
200 protected final void recordModification(Object x) {
201 synchronized(barrierLock) {
202 lastWrite = x;
203 }
204 }
205
206 /**
207 * Get ref to table; the reference and the cells it
208 * accesses will be at least as fresh as from last
209 * use of barrierLock
210 **/
211 protected final Entry[] getTableForReading() {
212 synchronized(barrierLock) {
213 return table;
214 }
215 }
216
217
218 /**
219 * The default initial number of table slots for this table (32).
220 * Used when not otherwise specified in constructor.
221 **/
222 public static int DEFAULT_INITIAL_CAPACITY = 32;
223
224
225 /**
226 * The minimum capacity, used if a lower value is implicitly specified
227 * by either of the constructors with arguments.
228 * MUST be a power of two.
229 */
230 private static final int MINIMUM_CAPACITY = 4;
231
232 /**
233 * The maximum capacity, used if a higher value is implicitly specified
234 * by either of the constructors with arguments.
235 * MUST be a power of two <= 1<<30.
236 */
237 private static final int MAXIMUM_CAPACITY = 1 << 30;
238
239 /**
240 * The default load factor for this table (1.0).
241 * Used when not otherwise specified in constructor.
242 **/
243
244 public static final float DEFAULT_LOAD_FACTOR = 0.75f;
245
246
247 /**
248 * The hash table data.
249 */
250 protected transient Entry[] table;
251
252 /**
253 * The total number of mappings in the hash table.
254 */
255 protected transient int count;
256
257 /**
258 * The table is rehashed when its size exceeds this threshold. (The
259 * value of this field is always (int)(capacity * loadFactor).)
260 *
261 * @serial
262 */
263 protected int threshold;
264
265 /**
266 * The load factor for the hash table.
267 *
268 * @serial
269 */
270 protected float loadFactor;
271
272 /**
273 * Returns the appropriate capacity (power of two) for the specified
274 * initial capacity argument.
275 */
276 private int p2capacity(int initialCapacity) {
277 int cap = initialCapacity;
278
279 // Compute the appropriate capacity
280 int result;
281 if (cap > MAXIMUM_CAPACITY || cap < 0) {
282 result = MAXIMUM_CAPACITY;
283 } else {
284 result = MINIMUM_CAPACITY;
285 while (result < cap)
286 result <<= 1;
287 }
288 return result;
289 }
290
291 /**
292 * Return hash code for Object x. Since we are using power-of-two
293 * tables, it is worth the effort to improve hashcode via
294 * the same multiplicative scheme as used in IdentityHashMap.
295 */
296 private static int hash(Object x) {
297 int h = x.hashCode();
298 // Multiply by 127 (quickly, via shifts), and mix in some high
299 // bits to help guard against bunching of codes that are
300 // consecutive or equally spaced.
301 return ((h << 7) - h + (h >>> 9) + (h >>> 17));
302 }
303
304 /**
305 * Check for equality of non-null references x and y.
306 **/
307 protected boolean eq(Object x, Object y) {
308 return x == y || x.equals(y);
309 }
310
311 /**
312 * Constructs a new, empty map with the specified initial
313 * capacity and the specified load factor.
314 *
315 * @param initialCapacity the initial capacity
316 * The actual initial capacity is rounded to the nearest power of two.
317 * @param loadFactor the load factor of the ConcurrentReaderHashMap
318 * @throws IllegalArgumentException if the initial maximum number
319 * of elements is less
320 * than zero, or if the load factor is nonpositive.
321 */
322
323 public ConcurrentReaderHashMap(int initialCapacity, float loadFactor) {
324 if (loadFactor <= 0)
325 throw new IllegalArgumentException("Illegal Load factor: "+
326 loadFactor);
327 this.loadFactor = loadFactor;
328
329 int cap = p2capacity(initialCapacity);
330
331 table = new Entry[cap];
332 threshold = (int)(cap * loadFactor);
333 }
334
335 /**
336 * Constructs a new, empty map with the specified initial
337 * capacity and default load factor.
338 *
339 * @param initialCapacity the initial capacity of the
340 * ConcurrentReaderHashMap.
341 * @throws IllegalArgumentException if the initial maximum number
342 * of elements is less
343 * than zero.
344 */
345
346 public ConcurrentReaderHashMap(int initialCapacity) {
347 this(initialCapacity, DEFAULT_LOAD_FACTOR);
348 }
349
350 /**
351 * Constructs a new, empty map with a default initial capacity
352 * and load factor.
353 */
354
355 public ConcurrentReaderHashMap() {
356 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
357 }
358
359 /**
360 * Constructs a new map with the same mappings as the given map. The
361 * map is created with a capacity of twice the number of mappings in
362 * the given map or 16 (whichever is greater), and a default load factor.
363 */
364
365 public ConcurrentReaderHashMap(Map t) {
366 this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, 16),
367 DEFAULT_LOAD_FACTOR);
368 putAll(t);
369 }
370
371 /**
372 * Returns the number of key-value mappings in this map.
373 *
374 * @return the number of key-value mappings in this map.
375 */
376
377 public synchronized int size() {
378 return count;
379 }
380
381 /**
382 * Returns <tt>true</tt> if this map contains no key-value mappings.
383 *
384 * @return <tt>true</tt> if this map contains no key-value mappings.
385 */
386
387 public synchronized boolean isEmpty() {
388 return count == 0;
389 }
390
391
392
393 /**
394 * Returns the value to which the specified key is mapped in this table.
395 *
396 * @param key a key in the table.
397 * @return the value to which the key is mapped in this table;
398 * <code>null</code> if the key is not mapped to any value in
399 * this table.
400 * @exception NullPointerException if the key is
401 * <code>null</code>.
402 * @see #put(Object, Object)
403 */
404
405
406 public Object get(Object key) {
407
408 // throw null pointer exception if key null
409 int hash = hash(key);
410
411 /*
412 Start off at the apparently correct bin. If entry is found, we
413 need to check after a barrier anyway. If not found, we need a
414 barrier to check if we are actually in right bin. So either
415 way, we encounter only one barrier unless we need to retry.
416 And we only need to fully synchronize if there have been
417 concurrent modifications.
418 */
419
420 Entry[] tab = table;
421 int index = hash & (tab.length - 1);
422 Entry first = tab[index];
423 Entry e = first;
424
425 for (;;) {
426 if (e == null) {
427
428 // If key apparently not there, check to
429 // make sure this was a valid read
430
431 Entry[] reread = getTableForReading();
432 if (tab == reread && first == tab[index])
433 return null;
434 else {
435 // Wrong list -- must restart traversal at new first
436 tab = reread;
437 e = first = tab[index = hash & (tab.length-1)];
438 }
439
440 }
441
442 else if (e.hash == hash && eq(key, e.key)) {
443 Object value = e.value;
444 if (value != null)
445 return value;
446
447 // Entry was invalidated during deletion. But it could
448 // have been re-inserted, so we must retraverse.
449 // To avoid useless contention, get lock to wait out modifications
450 // before retraversing.
451
452 synchronized(this) {
453 tab = table;
454 }
455 e = first = tab[index = hash & (tab.length-1)];
456
457 }
458 else
459 e = e.next;
460 }
461 }
462
463
464 /**
465 * Tests if the specified object is a key in this table.
466 *
467 * @param key possible key.
468 * @return <code>true</code> if and only if the specified object
469 * is a key in this table, as determined by the
470 * <tt>equals</tt> method; <code>false</code> otherwise.
471 * @exception NullPointerException if the key is
472 * <code>null</code>.
473 * @see #contains(Object)
474 */
475
476
477 public boolean containsKey(Object key) {
478 return get(key) != null;
479 }
480
481 /**
482 * Maps the specified <code>key</code> to the specified
483 * <code>value</code> in this table. Neither the key nor the
484 * value can be <code>null</code>. <p>
485 *
486 * The value can be retrieved by calling the <code>get</code> method
487 * with a key that is equal to the original key.
488 *
489 * @param key the table key.
490 * @param value the value.
491 * @return the previous value of the specified key in this table,
492 * or <code>null</code> if it did not have one.
493 * @exception NullPointerException if the key or value is
494 * <code>null</code>.
495 * @see Object#equals(Object)
496 * @see #get(Object)
497 */
498
499 public Object put(Object key, Object value) {
500 if (value == null)
501 throw new NullPointerException();
502
503 int hash = hash(key);
504 Entry[] tab = table;
505 int index = hash & (tab.length-1);
506 Entry first = tab[index];
507 Entry e;
508
509 for (e = first; e != null; e = e.next)
510 if (e.hash == hash && eq(key, e.key))
511 break;
512
513 synchronized(this) {
514 if (tab == table) {
515 if (e == null) {
516 // make sure we are adding to correct list
517 if (first == tab[index]) {
518 // Add to front of list
519 Entry newEntry = new Entry(hash, key, value, first);
520 tab[index] = newEntry;
521 if (++count >= threshold) rehash();
522 else recordModification(newEntry);
523 return null;
524 }
525 }
526 else {
527 Object oldValue = e.value;
528 if (first == tab[index] && oldValue != null) {
529 e.value = value;
530 return oldValue;
531 }
532 }
533 }
534
535 // retry if wrong list or lost race against concurrent remove
536 return sput(key, value, hash);
537 }
538 }
539
540
541 /**
542 * Continuation of put(), called only when synch lock is
543 * held and interference has been detected.
544 **/
545 protected Object sput(Object key, Object value, int hash) {
546
547 Entry[] tab = table;
548 int index = hash & (tab.length-1);
549 Entry first = tab[index];
550 Entry e = first;
551
552 for (;;) {
553 if (e == null) {
554 Entry newEntry = new Entry(hash, key, value, first);
555 tab[index] = newEntry;
556 if (++count >= threshold) rehash();
557 else recordModification(newEntry);
558 return null;
559 }
560 else if (e.hash == hash && eq(key, e.key)) {
561 Object oldValue = e.value;
562 e.value = value;
563 return oldValue;
564 }
565 else
566 e = e.next;
567 }
568 }
569
570
571 /**
572 * Rehashes the contents of this map into a new table
573 * with a larger capacity. This method is called automatically when the
574 * number of keys in this map exceeds its capacity and load factor.
575 */
576 protected void rehash() {
577 Entry[] oldTable = table;
578 int oldCapacity = oldTable.length;
579 if (oldCapacity >= MAXIMUM_CAPACITY) {
580 threshold = Integer.MAX_VALUE; // avoid retriggering
581 return;
582 }
583
584 int newCapacity = oldCapacity << 1;
585 int mask = newCapacity - 1;
586 threshold = (int)(newCapacity * loadFactor);
587
588 Entry[] newTable = new Entry[newCapacity];
589 /*
590 * Reclassify nodes in each list to new Map. Because we are
591 * using power-of-two expansion, the elements from each bin
592 * must either stay at same index, or move to
593 * oldCapacity+index. We also eliminate unnecessary node
594 * creation by catching cases where old nodes can be reused
595 * because their next fields won't change. Statistically, at
596 * the default threshhold, only about one-sixth of them need
597 * cloning. (The nodes they replace will be garbage
598 * collectable as soon as they are no longer referenced by any
599 * reader thread that may be in the midst of traversing table
600 * right now.)
601 */
602
603 for (int i = 0; i < oldCapacity ; i++) {
604 // We need to guarantee that any existing reads of old Map can
605 // proceed. So we cannot yet null out each bin.
606 Entry e = oldTable[i];
607
608 if (e != null) {
609 int idx = e.hash & mask;
610 Entry next = e.next;
611
612 // Single node on list
613 if (next == null)
614 newTable[idx] = e;
615
616 else {
617 // Reuse trailing consecutive sequence of all same bit
618 Entry lastRun = e;
619 int lastIdx = idx;
620 for (Entry last = next; last != null; last = last.next) {
621 int k = last.hash & mask;
622 if (k != lastIdx) {
623 lastIdx = k;
624 lastRun = last;
625 }
626 }
627 newTable[lastIdx] = lastRun;
628
629 // Clone all remaining nodes
630 for (Entry p = e; p != lastRun; p = p.next) {
631 int k = p.hash & mask;
632 newTable[k] = new Entry(p.hash, p.key,
633 p.value, newTable[k]);
634 }
635 }
636 }
637 }
638
639 table = newTable;
640 recordModification(newTable);
641 }
642
643 /**
644 * Removes the key (and its corresponding value) from this
645 * table. This method does nothing if the key is not in the table.
646 *
647 * @param key the key that needs to be removed.
648 * @return the value to which the key had been mapped in this table,
649 * or <code>null</code> if the key did not have a mapping.
650 * @exception NullPointerException if the key is
651 * <code>null</code>.
652 */
653
654 public Object remove(Object key) {
655 /*
656 Find the entry, then
657 1. Set value field to null, to force get() to retry
658 2. Rebuild the list without this entry.
659 All entries following removed node can stay in list, but
660 all preceeding ones need to be cloned. Traversals rely
661 on this strategy to ensure that elements will not be
662 repeated during iteration.
663 */
664
665
666 int hash = hash(key);
667 Entry[] tab = table;
668 int index = hash & (tab.length-1);
669 Entry first = tab[index];
670 Entry e = first;
671
672 for (e = first; e != null; e = e.next)
673 if (e.hash == hash && eq(key, e.key))
674 break;
675
676
677 synchronized(this) {
678 if (tab == table) {
679 if (e == null) {
680 if (first == tab[index])
681 return null;
682 }
683 else {
684 Object oldValue = e.value;
685 if (first == tab[index] && oldValue != null) {
686 e.value = null;
687 count--;
688
689 Entry head = e.next;
690 for (Entry p = first; p != e; p = p.next)
691 head = new Entry(p.hash, p.key, p.value, head);
692
693 tab[index] = head;
694 recordModification(head);
695 return oldValue;
696 }
697 }
698 }
699
700 // Wrong list or interference
701 return sremove(key, hash);
702 }
703 }
704
705 /**
706 * Continuation of remove(), called only when synch lock is
707 * held and interference has been detected.
708 **/
709
710 protected Object sremove(Object key, int hash) {
711 Entry[] tab = table;
712 int index = hash & (tab.length-1);
713 Entry first = tab[index];
714
715 for (Entry e = first; e != null; e = e.next) {
716 if (e.hash == hash && eq(key, e.key)) {
717 Object oldValue = e.value;
718 e.value = null;
719 count--;
720 Entry head = e.next;
721 for (Entry p = first; p != e; p = p.next)
722 head = new Entry(p.hash, p.key, p.value, head);
723
724 tab[index] = head;
725 recordModification(head);
726 return oldValue;
727 }
728 }
729 return null;
730 }
731
732
733 /**
734 * Returns <tt>true</tt> if this map maps one or more keys to the
735 * specified value. Note: This method requires a full internal
736 * traversal of the hash table, and so is much slower than
737 * method <tt>containsKey</tt>.
738 *
739 * @param value value whose presence in this map is to be tested.
740 * @return <tt>true</tt> if this map maps one or more keys to the
741 * specified value.
742 * @exception NullPointerException if the value is <code>null</code>.
743 */
744
745 public boolean containsValue(Object value) {
746 if (value == null) throw new NullPointerException();
747
748 Entry tab[] = getTableForReading();
749
750 for (int i = 0 ; i < tab.length; ++i) {
751 for (Entry e = tab[i] ; e != null ; e = e.next)
752 if (value.equals(e.value))
753 return true;
754 }
755
756 return false;
757 }
758
759 /**
760 * Tests if some key maps into the specified value in this table.
761 * This operation is more expensive than the <code>containsKey</code>
762 * method.<p>
763 *
764 * Note that this method is identical in functionality to containsValue,
765 * (which is part of the Map interface in the collections framework).
766 *
767 * @param value a value to search for.
768 * @return <code>true</code> if and only if some key maps to the
769 * <code>value</code> argument in this table as
770 * determined by the <tt>equals</tt> method;
771 * <code>false</code> otherwise.
772 * @exception NullPointerException if the value is <code>null</code>.
773 * @see #containsKey(Object)
774 * @see #containsValue(Object)
775 * @see Map
776 */
777
778 public boolean contains(Object value) {
779 return containsValue(value);
780 }
781
782
783 /**
784 * Copies all of the mappings from the specified map to this one.
785 *
786 * These mappings replace any mappings that this map had for any of the
787 * keys currently in the specified Map.
788 *
789 * @param t Mappings to be stored in this map.
790 */
791
792 public synchronized void putAll(Map t) {
793 int n = t.size();
794 if (n == 0)
795 return;
796
797 // Expand enough to hold at least n elements without resizing.
798 // We can only resize table by factor of two at a time.
799 // It is faster to rehash with fewer elements, so do it now.
800 while (n >= threshold)
801 rehash();
802
803 for (Iterator it = t.entrySet().iterator(); it.hasNext();) {
804 Map.Entry entry = (Map.Entry) it.next();
805 Object key = entry.getKey();
806 Object value = entry.getValue();
807 put(key, value);
808 }
809 }
810
811
812 /**
813 * Removes all mappings from this map.
814 */
815 public synchronized void clear() {
816 Entry tab[] = table;
817 for (int i = 0; i < tab.length ; ++i) {
818
819 // must invalidate all to force concurrent get's to wait and then retry
820 for (Entry e = tab[i]; e != null; e = e.next)
821 e.value = null;
822
823 tab[i] = null;
824 }
825 count = 0;
826 recordModification(tab);
827 }
828
829 /**
830 * Returns a shallow copy of this
831 * <tt>ConcurrentReaderHashMap</tt> instance: the keys and
832 * values themselves are not cloned.
833 *
834 * @return a shallow copy of this map.
835 */
836
837 public synchronized Object clone() {
838 try {
839 ConcurrentReaderHashMap t = (ConcurrentReaderHashMap)super.clone();
840
841 t.keySet = null;
842 t.entrySet = null;
843 t.values = null;
844
845 Entry[] tab = table;
846 t.table = new Entry[tab.length];
847 Entry[] ttab = t.table;
848
849 for (int i = 0; i < tab.length; ++i) {
850 Entry first = null;
851 for (Entry e = tab[i]; e != null; e = e.next)
852 first = new Entry(e.hash, e.key, e.value, first);
853 ttab[i] = first;
854 }
855
856 return t;
857 }
858 catch (CloneNotSupportedException e) {
859 // this shouldn't happen, since we are Cloneable
860 throw new InternalError();
861 }
862 }
863
864 // Views
865
866 protected transient Set keySet = null;
867 protected transient Set entrySet = null;
868 protected transient Collection values = null;
869
870 /**
871 * Returns a set view of the keys contained in this map. The set is
872 * backed by the map, so changes to the map are reflected in the set, and
873 * vice-versa. The set supports element removal, which removes the
874 * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
875 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
876 * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
877 * <tt>addAll</tt> operations.
878 *
879 * @return a set view of the keys contained in this map.
880 */
881
882 public Set keySet() {
883 Set ks = keySet;
884 return (ks != null)? ks : (keySet = new KeySet());
885 }
886
887 private class KeySet extends AbstractSet {
888 public Iterator iterator() {
889 return new KeyIterator();
890 }
891 public int size() {
892 return ConcurrentReaderHashMap.this.size();
893 }
894 public boolean contains(Object o) {
895 return ConcurrentReaderHashMap.this.containsKey(o);
896 }
897 public boolean remove(Object o) {
898 return ConcurrentReaderHashMap.this.remove(o) != null;
899 }
900 public void clear() {
901 ConcurrentReaderHashMap.this.clear();
902 }
903 }
904
905 /**
906 * Returns a collection view of the values contained in this map. The
907 * collection is backed by the map, so changes to the map are reflected in
908 * the collection, and vice-versa. The collection supports element
909 * removal, which removes the corresponding mapping from this map, via the
910 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
911 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
912 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
913 *
914 * @return a collection view of the values contained in this map.
915 */
916
917 public Collection values() {
918 Collection vs = values;
919 return (vs != null)? vs : (values = new Values());
920 }
921
922 private class Values extends AbstractCollection {
923 public Iterator iterator() {
924 return new ValueIterator();
925 }
926 public int size() {
927 return ConcurrentReaderHashMap.this.size();
928 }
929 public boolean contains(Object o) {
930 return ConcurrentReaderHashMap.this.containsValue(o);
931 }
932 public void clear() {
933 ConcurrentReaderHashMap.this.clear();
934 }
935 }
936
937 /**
938 * Returns a collection view of the mappings contained in this map. Each
939 * element in the returned collection is a <tt>Map.Entry</tt>. The
940 * collection is backed by the map, so changes to the map are reflected in
941 * the collection, and vice-versa. The collection supports element
942 * removal, which removes the corresponding mapping from the map, via the
943 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
944 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
945 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
946 *
947 * @return a collection view of the mappings contained in this map.
948 */
949
950 public Set entrySet() {
951 Set es = entrySet;
952 return (es != null) ? es : (entrySet = new EntrySet());
953 }
954
955 private class EntrySet extends AbstractSet {
956 public Iterator iterator() {
957 return new HashIterator();
958 }
959 public boolean contains(Object o) {
960 if (!(o instanceof Map.Entry))
961 return false;
962 Map.Entry entry = (Map.Entry)o;
963 Object v = ConcurrentReaderHashMap.this.get(entry.getKey());
964 return v != null && v.equals(entry.getValue());
965 }
966 public boolean remove(Object o) {
967 if (!(o instanceof Map.Entry))
968 return false;
969 return ConcurrentReaderHashMap.this.findAndRemoveEntry((Map.Entry)o);
970 }
971 public int size() {
972 return ConcurrentReaderHashMap.this.size();
973 }
974 public void clear() {
975 ConcurrentReaderHashMap.this.clear();
976 }
977 }
978
979 /**
980 * Helper method for entrySet.remove
981 **/
982 protected synchronized boolean findAndRemoveEntry(Map.Entry entry) {
983 Object key = entry.getKey();
984 Object v = get(key);
985 if (v != null && v.equals(entry.getValue())) {
986 remove(key);
987 return true;
988 }
989 else
990 return false;
991 }
992
993 /**
994 * Returns an enumeration of the keys in this table.
995 *
996 * @return an enumeration of the keys in this table.
997 * @see Enumeration
998 * @see #elements()
999 * @see #keySet()
1000 * @see Map
1001 */
1002 public Enumeration keys() {
1003 return new KeyIterator();
1004 }
1005
1006 /**
1007 * Returns an enumeration of the values in this table.
1008 * Use the Enumeration methods on the returned object to fetch the elements
1009 * sequentially.
1010 *
1011 * @return an enumeration of the values in this table.
1012 * @see java.util.Enumeration
1013 * @see #keys()
1014 * @see #values()
1015 * @see Map
1016 */
1017
1018 public Enumeration elements() {
1019 return new ValueIterator();
1020 }
1021
1022
1023 /**
1024 * ConcurrentReaderHashMap collision list entry.
1025 */
1026
1027 protected static class Entry implements Map.Entry {
1028
1029 /*
1030 The use of volatile for value field ensures that
1031 we can detect status changes without synchronization.
1032 The other fields are never changed, and are
1033 marked as final.
1034 */
1035
1036 protected final int hash;
1037 protected final Object key;
1038 protected final Entry next;
1039 protected volatile Object value;
1040
1041 Entry(int hash, Object key, Object value, Entry next) {
1042 this.hash = hash;
1043 this.key = key;
1044 this.next = next;
1045 this.value = value;
1046 }
1047
1048 // Map.Entry Ops
1049
1050 public Object getKey() {
1051 return key;
1052 }
1053
1054 /**
1055 * Get the value. Note: In an entrySet or entrySet.iterator,
1056 * unless the set or iterator is used under synchronization of the
1057 * table as a whole (or you can otherwise guarantee lack of
1058 * concurrent modification), <tt>getValue</tt> <em>might</em>
1059 * return null, reflecting the fact that the entry has been
1060 * concurrently removed. However, there are no assurances that
1061 * concurrent removals will be reflected using this method.
1062 *
1063 * @return the current value, or null if the entry has been
1064 * detectably removed.
1065 **/
1066 public Object getValue() {
1067 return value;
1068 }
1069
1070 /**
1071 * Set the value of this entry. Note: In an entrySet or
1072 * entrySet.iterator), unless the set or iterator is used under
1073 * synchronization of the table as a whole (or you can otherwise
1074 * guarantee lack of concurrent modification), <tt>setValue</tt>
1075 * is not strictly guaranteed to actually replace the value field
1076 * obtained via the <tt>get</tt> operation of the underlying hash
1077 * table in multithreaded applications. If iterator-wide
1078 * synchronization is not used, and any other concurrent
1079 * <tt>put</tt> or <tt>remove</tt> operations occur, sometimes
1080 * even to <em>other</em> entries, then this change is not
1081 * guaranteed to be reflected in the hash table. (It might, or it
1082 * might not. There are no assurances either way.)
1083 *
1084 * @param value the new value.
1085 * @return the previous value, or null if entry has been detectably
1086 * removed.
1087 * @exception NullPointerException if the value is <code>null</code>.
1088 *
1089 **/
1090
1091 public Object setValue(Object value) {
1092 if (value == null)
1093 throw new NullPointerException();
1094 Object oldValue = this.value;
1095 this.value = value;
1096 return oldValue;
1097 }
1098
1099 public boolean equals(Object o) {
1100 if (!(o instanceof Map.Entry))
1101 return false;
1102 Map.Entry e = (Map.Entry)o;
1103 return (key.equals(e.getKey()) && value.equals(e.getValue()));
1104 }
1105
1106 public int hashCode() {
1107 return key.hashCode() ^ value.hashCode();
1108 }
1109
1110 public String toString() {
1111 return key + "=" + value;
1112 }
1113
1114 }
1115
1116 protected class HashIterator implements Iterator, Enumeration {
1117 protected final Entry[] tab; // snapshot of table
1118 protected int index; // current slot
1119 protected Entry entry = null; // current node of slot
1120 protected Object currentKey; // key for current node
1121 protected Object currentValue; // value for current node
1122 protected Entry lastReturned = null; // last node returned by next
1123
1124 protected HashIterator() {
1125 tab = ConcurrentReaderHashMap.this.getTableForReading();
1126 index = tab.length - 1;
1127 }
1128
1129 public boolean hasMoreElements() { return hasNext(); }
1130 public Object nextElement() { return next(); }
1131
1132
1133 public boolean hasNext() {
1134
1135 /*
1136 currentkey and currentValue are set here to ensure that next()
1137 returns normally if hasNext() returns true. This avoids
1138 surprises especially when final element is removed during
1139 traversal -- instead, we just ignore the removal during
1140 current traversal.
1141 */
1142
1143 for (;;) {
1144 if (entry != null) {
1145 Object v = entry.value;
1146 if (v != null) {
1147 currentKey = entry.key;
1148 currentValue = v;
1149 return true;
1150 }
1151 else
1152 entry = entry.next;
1153 }
1154
1155 while (entry == null && index >= 0)
1156 entry = tab[index--];
1157
1158 if (entry == null) {
1159 currentKey = currentValue = null;
1160 return false;
1161 }
1162 }
1163 }
1164
1165 protected Object returnValueOfNext() { return entry; }
1166
1167 public Object next() {
1168 if (currentKey == null && !hasNext())
1169 throw new NoSuchElementException();
1170
1171 Object result = returnValueOfNext();
1172 lastReturned = entry;
1173 currentKey = currentValue = null;
1174 entry = entry.next;
1175 return result;
1176 }
1177
1178 public void remove() {
1179 if (lastReturned == null)
1180 throw new IllegalStateException();
1181 ConcurrentReaderHashMap.this.remove(lastReturned.key);
1182 lastReturned = null;
1183 }
1184
1185 }
1186
1187
1188 protected class KeyIterator extends HashIterator {
1189 protected Object returnValueOfNext() { return currentKey; }
1190 }
1191
1192 protected class ValueIterator extends HashIterator {
1193 protected Object returnValueOfNext() { return currentValue; }
1194 }
1195
1196
1197
1198 /**
1199 * Save the state of the <tt>ConcurrentReaderHashMap</tt>
1200 * instance to a stream (i.e.,
1201 * serialize it).
1202 *
1203 * @serialData The <i>capacity</i> of the
1204 * ConcurrentReaderHashMap (the length of the
1205 * bucket array) is emitted (int), followed by the
1206 * <i>size</i> of the ConcurrentReaderHashMap (the number of key-value
1207 * mappings), followed by the key (Object) and value (Object)
1208 * for each key-value mapping represented by the ConcurrentReaderHashMap
1209 * The key-value mappings are emitted in no particular order.
1210 */
1211
1212 private synchronized void writeObject(java.io.ObjectOutputStream s)
1213 throws IOException {
1214 // Write out the threshold, loadfactor, and any hidden stuff
1215 s.defaultWriteObject();
1216
1217 // Write out number of buckets
1218 s.writeInt(table.length);
1219
1220 // Write out size (number of Mappings)
1221 s.writeInt(count);
1222
1223 // Write out keys and values (alternating)
1224 for (int index = table.length-1; index >= 0; index--) {
1225 Entry entry = table[index];
1226
1227 while (entry != null) {
1228 s.writeObject(entry.key);
1229 s.writeObject(entry.value);
1230 entry = entry.next;
1231 }
1232 }
1233 }
1234
1235 /**
1236 * Reconstitute the <tt>ConcurrentReaderHashMap</tt>
1237 * instance from a stream (i.e.,
1238 * deserialize it).
1239 */
1240 private synchronized void readObject(java.io.ObjectInputStream s)
1241 throws IOException, ClassNotFoundException {
1242 // Read in the threshold, loadfactor, and any hidden stuff
1243 s.defaultReadObject();
1244
1245 // Read in number of buckets and allocate the bucket array;
1246 int numBuckets = s.readInt();
1247 table = new Entry[numBuckets];
1248
1249 // Read in size (number of Mappings)
1250 int size = s.readInt();
1251
1252 // Read the keys and values, and put the mappings in the table
1253 for (int i=0; i<size; i++) {
1254 Object key = s.readObject();
1255 Object value = s.readObject();
1256 put(key, value);
1257 }
1258 }
1259
1260 /**
1261 * Return the number of slots in this table
1262 **/
1263
1264 public synchronized int capacity() {
1265 return table.length;
1266 }
1267
1268 /**
1269 * Return the load factor
1270 **/
1271 public float loadFactor() {
1272 return loadFactor;
1273 }
1274 }