Java > Open Source Codes > EDU > oswego > cs > dl > util > concurrent > ConcurrentReaderHashMap


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags