View Javadoc

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  /***
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     The basic strategy is an optimistic-style scheme based on
156     the guarantee that the hash table and its lists are always
157     kept in a consistent enough state to be read without locking:
158 
159     * Read operations first proceed without locking, by traversing the
160        apparently correct list of the apparently correct bin. If an
161        entry is found, but not invalidated (value field null), it is
162        returned. If not found, operations must recheck (after a memory
163        barrier) to make sure they are using both the right list and
164        the right table (which can change under resizes). If
165        invalidated, reads must acquire main update lock to wait out
166        the update, and then re-traverse.
167 
168     * All list additions are at the front of each bin, making it easy
169        to check changes, and also fast to traverse.  Entry next
170        pointers are never assigned. Remove() builds new nodes when
171        necessary to preserve this.
172 
173     * Remove() (also clear()) invalidates removed nodes to alert read
174        operations that they must wait out the full modifications.
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     // Compute the appropriate capacity
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     // Multiply by 127 (quickly, via shifts), and mix in some high
296     // bits to help guard against bunching of codes that are
297     // consecutive or equally spaced.
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     // throw null pointer exception if key null
406     int hash = hash(key);
407 
408     /* 
409        Start off at the apparently correct bin.  If entry is found, we
410        need to check after a barrier anyway.  If not found, we need a
411        barrier to check if we are actually in right bin. So either
412        way, we encounter only one barrier unless we need to retry.
413        And we only need to fully synchronize if there have been
414        concurrent modifications.
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         // If key apparently not there, check to
426         // make sure this was a valid read
427 
428         Entry[] reread = getTableForReading();
429         if (tab == reread && first == tab[index])
430           return null;
431         else {
432           // Wrong list -- must restart traversal at new first
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         // Entry was invalidated during deletion. But it could
445         // have been re-inserted, so we must retraverse.
446         // To avoid useless contention, get lock to wait out modifications
447         // before retraversing.
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           //  make sure we are adding to correct list
514           if (first == tab[index]) {
515             //  Add to front of list
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       // retry if wrong list or lost race against concurrent remove
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; // avoid retriggering
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      * Reclassify nodes in each list to new Map.  Because we are
588      * using power-of-two expansion, the elements from each bin
589      * must either stay at same index, or move to
590      * oldCapacity+index. We also eliminate unnecessary node
591      * creation by catching cases where old nodes can be reused
592      * because their next fields won't change. Statistically, at
593      * the default threshhold, only about one-sixth of them need
594      * cloning. (The nodes they replace will be garbage
595      * collectable as soon as they are no longer referenced by any
596      * reader thread that may be in the midst of traversing table
597      * right now.)
598      */
599     
600     for (int i = 0; i < oldCapacity ; i++) {
601       // We need to guarantee that any existing reads of old Map can
602       //  proceed. So we cannot yet null out each bin.  
603       Entry e = oldTable[i];
604       
605       if (e != null) {
606         int idx = e.hash & mask;
607         Entry next = e.next;
608         
609         //  Single node on list
610         if (next == null) 
611           newTable[idx] = e;
612         
613         else {    
614           // Reuse trailing consecutive sequence of all same bit
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           // Clone all remaining nodes
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       Find the entry, then 
654         1. Set value field to null, to force get() to retry
655         2. Rebuild the list without this entry.
656            All entries following removed node can stay in list, but
657            all preceeding ones need to be cloned.  Traversals rely
658            on this strategy to ensure that elements will not be
659           repeated during iteration.
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       // Wrong list or interference
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     // Expand enough to hold at least n elements without resizing.
795     // We can only resize table by factor of two at a time.
796     // It is faster to rehash with fewer elements, so do it now.
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       // must invalidate all to force concurrent get's to wait and then retry
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       // this shouldn't happen, since we are Cloneable
857       throw new InternalError();
858     }
859   }
860 
861   // Views
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        The use of volatile for value field ensures that
1028        we can detect status changes without synchronization.
1029        The other fields are never changed, and are
1030        marked as final. 
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     // Map.Entry Ops 
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;           // snapshot of table
1115     protected int index;                   // current slot 
1116     protected Entry entry = null;          // current node of slot
1117     protected Object currentKey;           // key for current node
1118     protected Object currentValue;         // value for current node
1119     protected Entry lastReturned = null;   // last node returned by next
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         currentkey and currentValue are set here to ensure that next()
1134         returns normally if hasNext() returns true. This avoids
1135         surprises especially when final element is removed during
1136         traversal -- instead, we just ignore the removal during
1137         current traversal.  
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     // Write out the threshold, loadfactor, and any hidden stuff
1212     s.defaultWriteObject();
1213     
1214     // Write out number of buckets
1215     s.writeInt(table.length);
1216     
1217     // Write out size (number of Mappings)
1218     s.writeInt(count);
1219     
1220     // Write out keys and values (alternating)
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     // Read in the threshold, loadfactor, and any hidden stuff
1240     s.defaultReadObject();
1241 
1242     // Read in number of buckets and allocate the bucket array;
1243     int numBuckets = s.readInt();
1244     table = new Entry[numBuckets];
1245     
1246     // Read in size (number of Mappings)
1247     int size = s.readInt();
1248     
1249     // Read the keys and values, and put the mappings in the table
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 }