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