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