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