ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java
(Generate patch)

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.13 by dl, Fri Aug 1 22:48:54 2003 UTC vs.
Revision 1.52 by dl, Mon Jul 12 11:01:14 2004 UTC

# Line 1 | Line 1
1   /*
2   * Written by Doug Lea with assistance from members of JCP JSR-166
3 < * Expert Group and released to the public domain. Use, modify, and
4 < * redistribute this code in any way without acknowledgement.
3 > * Expert Group and released to the public domain, as explained at
4 > * http://creativecommons.org/licenses/publicdomain
5   */
6  
7   package java.util.concurrent;
# Line 15 | Line 15 | import java.io.ObjectOutputStream;
15   /**
16   * A hash table supporting full concurrency of retrievals and
17   * adjustable expected concurrency for updates. This class obeys the
18 < * same functional specification as
19 < * <tt>java.util.Hashtable</tt>. However, even though all operations
20 < * are thread-safe, retrieval operations do <em>not</em> entail
21 < * locking, and there is <em>not</em> any support for locking the
22 < * entire table in a way that prevents all access.  This class is
23 < * fully interoperable with Hashtable in programs that rely on its
18 > * same functional specification as {@link java.util.Hashtable}, and
19 > * includes versions of methods corresponding to each method of
20 > * <tt>Hashtable</tt>. However, even though all operations are
21 > * thread-safe, retrieval operations do <em>not</em> entail locking,
22 > * and there is <em>not</em> any support for locking the entire table
23 > * in a way that prevents all access.  This class is fully
24 > * interoperable with <tt>Hashtable</tt> in programs that rely on its
25   * thread safety but not on its synchronization details.
26   *
27 < * <p> Retrieval operations (including <tt>get</tt>) ordinarily
28 < * overlap with update operations (including <tt>put</tt> and
29 < * <tt>remove</tt>). Retrievals reflect the results of the most
30 < * recently <em>completed</em> update operations holding upon their
31 < * onset.  For aggregate operations such as <tt>putAll</tt> and
32 < * <tt>clear</tt>, concurrent retrievals may reflect insertion or
27 > * <p> Retrieval operations (including <tt>get</tt>) generally do not
28 > * block, so may overlap with update operations (including
29 > * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results
30 > * of the most recently <em>completed</em> update operations holding
31 > * upon their onset.  For aggregate operations such as <tt>putAll</tt>
32 > * and <tt>clear</tt>, concurrent retrievals may reflect insertion or
33   * removal of only some entries.  Similarly, Iterators and
34   * Enumerations return elements reflecting the state of the hash table
35   * at some point at or since the creation of the iterator/enumeration.
36 < * They do <em>not</em> throw ConcurrentModificationException.
37 < * However, Iterators are designed to be used by only one thread at a
38 < * time.
36 > * They do <em>not</em> throw
37 > * {@link ConcurrentModificationException}.  However, iterators are
38 > * designed to be used by only one thread at a time.
39   *
40 < * <p> The allowed concurrency among update operations is controlled
41 < * by the optional <tt>segments</tt> constructor argument (default
42 < * 16). The table is divided into this many independent parts, each of
43 < * which can be updated concurrently. Because placement in hash tables
44 < * is essentially random, the actual concurrency will vary. As a rough
45 < * rule of thumb, you should choose at least as many segments as you
46 < * expect concurrent threads. However, using more segments than you
47 < * need can waste space and time. Using a value of 1 for
48 < * <tt>segments</tt> results in a table that is concurrently readable
49 < * but can only be updated by one thread at a time.
40 > * <p> The allowed concurrency among update operations is guided by
41 > * the optional <tt>concurrencyLevel</tt> constructor argument
42 > * (default 16), which is used as a hint for internal sizing.  The
43 > * table is internally partitioned to try to permit the indicated
44 > * number of concurrent updates without contention. Because placement
45 > * in hash tables is essentially random, the actual concurrency will
46 > * vary.  Ideally, you should choose a value to accommodate as many
47 > * threads as will ever concurrently modify the table. Using a
48 > * significantly higher value than you need can waste space and time,
49 > * and a significantly lower value can lead to thread contention. But
50 > * overestimates and underestimates within an order of magnitude do
51 > * not usually have much noticeable impact. A value of one is
52 > * appropriate when it is known that only one thread will modify and
53 > * all others will only read. Also, resizing this or any other kind of
54 > * hash table is a relatively slow operation, so, when possible, it is
55 > * a good idea to provide estimates of expected table sizes in
56 > * constructors.
57   *
58 < * <p> Like Hashtable but unlike java.util.HashMap, this class does
59 < * NOT allow <tt>null</tt> to be used as a key or value.
58 > * <p>This class and its views and iterators implement all of the
59 > * <em>optional</em> methods of the {@link Map} and {@link Iterator}
60 > * interfaces.
61 > *
62 > * <p> Like {@link java.util.Hashtable} but unlike {@link
63 > * java.util.HashMap}, this class does NOT allow <tt>null</tt> to be
64 > * used as a key or value.
65 > *
66 > * <p>This class is a member of the
67 > * <a href="{@docRoot}/../guide/collections/index.html">
68 > * Java Collections Framework</a>.
69   *
70   * @since 1.5
71   * @author Doug Lea
72 + * @param <K> the type of keys maintained by this map
73 + * @param <V> the type of mapped values
74   */
75   public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
76 <        implements ConcurrentMap<K, V>, Cloneable, Serializable {
76 >        implements ConcurrentMap<K, V>, Serializable {
77 >    private static final long serialVersionUID = 7249069246763182397L;
78  
79      /*
80       * The basic strategy is to subdivide the table among Segments,
# Line 64 | Line 84 | public class ConcurrentHashMap<K, V> ext
84      /* ---------------- Constants -------------- */
85  
86      /**
87 <     * The default initial number of table slots for this table (32).
87 >     * The default initial number of table slots for this table.
88       * Used when not otherwise specified in constructor.
89       */
90 <    private static int DEFAULT_INITIAL_CAPACITY = 16;
90 >    static int DEFAULT_INITIAL_CAPACITY = 16;
91  
92      /**
93       * The maximum capacity, used if a higher value is implicitly
94       * specified by either of the constructors with arguments.  MUST
95 <     * be a power of two <= 1<<30.
95 >     * be a power of two <= 1<<30 to ensure that entries are indexible
96 >     * using ints.
97       */
98 <    static final int MAXIMUM_CAPACITY = 1 << 30;
98 >    static final int MAXIMUM_CAPACITY = 1 << 30;
99  
100      /**
101       * The default load factor for this table.  Used when not
# Line 85 | Line 106 | public class ConcurrentHashMap<K, V> ext
106      /**
107       * The default number of concurrency control segments.
108       **/
109 <    private static final int DEFAULT_SEGMENTS = 16;
109 >    static final int DEFAULT_SEGMENTS = 16;
110 >
111 >    /**
112 >     * The maximum number of segments to allow; used to bound
113 >     * constructor arguments.
114 >     */
115 >    static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
116 >
117 >    /**
118 >     * Number of unsynchronized retries in size and containsValue
119 >     * methods before resorting to locking. This is used to avoid
120 >     * unbounded retries if tables undergo continuous modification
121 >     * which would make it impossible to obtain an accurate result.
122 >     */
123 >    static final int RETRIES_BEFORE_LOCK = 2;
124  
125      /* ---------------- Fields -------------- */
126  
# Line 93 | Line 128 | public class ConcurrentHashMap<K, V> ext
128       * Mask value for indexing into segments. The upper bits of a
129       * key's hash code are used to choose the segment.
130       **/
131 <    private final int segmentMask;
131 >    final int segmentMask;
132  
133      /**
134       * Shift value for indexing within segments.
135       **/
136 <    private final int segmentShift;
136 >    final int segmentShift;
137  
138      /**
139       * The segments, each of which is a specialized hash table
140       */
141 <    private final Segment[] segments;
141 >    final Segment[] segments;
142  
143 <    private transient Set<K> keySet;
144 <    private transient Set<Map.Entry<K,V>> entrySet;
145 <    private transient Collection<V> values;
143 >    transient Set<K> keySet;
144 >    transient Set<Map.Entry<K,V>> entrySet;
145 >    transient Collection<V> values;
146  
147      /* ---------------- Small Utilities -------------- */
148  
149      /**
150 <     * Return a hash code for non-null Object x.
151 <     * Uses the same hash code spreader as most other j.u hash tables.
150 >     * Returns a hash code for non-null Object x.
151 >     * Uses the same hash code spreader as most other java.util hash tables.
152       * @param x the object serving as a key
153       * @return the hash code
154       */
155 <    private static int hash(Object x) {
155 >    static int hash(Object x) {
156          int h = x.hashCode();
157          h += ~(h << 9);
158          h ^=  (h >>> 14);
# Line 127 | Line 162 | public class ConcurrentHashMap<K, V> ext
162      }
163  
164      /**
165 <     * Return the segment that should be used for key with given hash
165 >     * Returns the segment that should be used for key with given hash
166 >     * @param hash the hash code for the key
167 >     * @return the segment
168       */
169 <    private Segment<K,V> segmentFor(int hash) {
169 >    final Segment<K,V> segmentFor(int hash) {
170          return (Segment<K,V>) segments[(hash >>> segmentShift) & segmentMask];
171      }
172  
173      /* ---------------- Inner Classes -------------- */
174  
175      /**
176 +     * ConcurrentHashMap list entry. Note that this is never exported
177 +     * out as a user-visible Map.Entry.
178 +     *
179 +     * Because the value field is volatile, not final, it is legal wrt
180 +     * the Java Memory Model for an unsynchronized reader to see null
181 +     * instead of initial value when read via a data race.  Although a
182 +     * reordering leading to this is not likely to ever actually
183 +     * occur, the Segment.readValueUnderLock method is used as a
184 +     * backup in case a null (pre-initialized) value is ever seen in
185 +     * an unsynchronized access method.
186 +     */
187 +    static final class HashEntry<K,V> {
188 +        final K key;
189 +        final int hash;
190 +        volatile V value;
191 +        final HashEntry<K,V> next;
192 +
193 +        HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
194 +            this.key = key;
195 +            this.hash = hash;
196 +            this.next = next;
197 +            this.value = value;
198 +        }
199 +    }
200 +
201 +    /**
202       * Segments are specialized versions of hash tables.  This
203       * subclasses from ReentrantLock opportunistically, just to
204       * simplify some locking and avoid separate construction.
205       **/
206 <    private static final class Segment<K,V> extends ReentrantLock implements Serializable {
206 >    static final class Segment<K,V> extends ReentrantLock implements Serializable {
207          /*
208           * Segments maintain a table of entry lists that are ALWAYS
209           * kept in a consistent state, so can be read without locking.
# Line 153 | Line 216 | public class ConcurrentHashMap<K, V> ext
216           * is less than two for the default load factor threshold.)
217           *
218           * Read operations can thus proceed without locking, but rely
219 <         * on a memory barrier to ensure that completed write
220 <         * operations performed by other threads are
221 <         * noticed. Conveniently, the "count" field, tracking the
222 <         * number of elements, can also serve as the volatile variable
223 <         * providing proper read/write barriers. This is convenient
224 <         * because this field needs to be read in many read operations
162 <         * anyway. The use of volatiles for this purpose is only
163 <         * guaranteed to work in accord with reuirements in
164 <         * multithreaded environments when run on JVMs conforming to
165 <         * the clarified JSR133 memory model specification.  This true
166 <         * for hotspot as of release 1.4.
167 <         *
168 <         * Implementors note. The basic rules for all this are:
219 >         * on selected uses of volatiles to ensure that completed
220 >         * write operations performed by other threads are
221 >         * noticed. For most purposes, the "count" field, tracking the
222 >         * number of elements, serves as that volatile variable
223 >         * ensuring visibility.  This is convenient because this field
224 >         * needs to be read in many read operations anyway:
225           *
226 <         *   - All unsynchronized read operations must first read the
226 >         *   - All (unsynchronized) read operations must first read the
227           *     "count" field, and should not look at table entries if
228           *     it is 0.
229           *
230 <         *   - All synchronized write operations should write to
231 <         *     the "count" field after updating. The operations must not
232 <         *     take any action that could even momentarily cause
233 <         *     a concurrent read operation to see inconsistent
234 <         *     data. This is made easier by the nature of the read
235 <         *     operations in Map. For example, no operation
230 >         *   - All (synchronized) write operations should write to
231 >         *     the "count" field after structurally changing any bin.
232 >         *     The operations must not take any action that could even
233 >         *     momentarily cause a concurrent read operation to see
234 >         *     inconsistent data. This is made easier by the nature of
235 >         *     the read operations in Map. For example, no operation
236           *     can reveal that the table has grown but the threshold
237           *     has not yet been updated, so there are no atomicity
238           *     requirements for this with respect to reads.
239           *
240 <         * As a guide, all critical volatile reads and writes are marked
241 <         * in code comments.
240 >         * As a guide, all critical volatile reads and writes to the
241 >         * count field are marked in code comments.
242           */
243  
244 +        private static final long serialVersionUID = 2249069246763182397L;
245 +
246          /**
247           * The number of elements in this segment's region.
248           **/
249          transient volatile int count;
250  
251          /**
252 +         * Number of updates that alter the size of the table. This is
253 +         * used during bulk-read methods to make sure they see a
254 +         * consistent snapshot: If modCounts change during a traversal
255 +         * of segments computing size or checking containsValue, then
256 +         * we might have an inconsistent view of state so (usually)
257 +         * must retry.
258 +         */
259 +        transient int modCount;
260 +
261 +        /**
262           * The table is rehashed when its size exceeds this threshold.
263           * (The value of this field is always (int)(capacity *
264           * loadFactor).)
265           */
266 <        private transient int threshold;
266 >        transient int threshold;
267  
268          /**
269 <         * The per-segment table
269 >         * The per-segment table. Declared as a raw type, casted
270 >         * to HashEntry<K,V> on each use.
271           */
272 <        transient HashEntry[] table;
272 >        transient volatile HashEntry[] table;
273  
274          /**
275           * The load factor for the hash table.  Even though this value
# Line 208 | Line 277 | public class ConcurrentHashMap<K, V> ext
277           * links to outer object.
278           * @serial
279           */
280 <        private final float loadFactor;
280 >        final float loadFactor;
281  
282          Segment(int initialCapacity, float lf) {
283              loadFactor = lf;
# Line 219 | Line 288 | public class ConcurrentHashMap<K, V> ext
288           * Set table to new HashEntry array.
289           * Call only while holding lock or in constructor.
290           **/
291 <        private void setTable(HashEntry[] newTable) {
223 <            table = newTable;
291 >        void setTable(HashEntry[] newTable) {
292              threshold = (int)(newTable.length * loadFactor);
293 <            count = count; // write-volatile
293 >            table = newTable;
294 >        }
295 >
296 >        /**
297 >         * Return properly casted first entry of bin for given hash
298 >         */
299 >        HashEntry<K,V> getFirst(int hash) {
300 >            HashEntry[] tab = table;
301 >            return (HashEntry<K,V>) tab[hash & (tab.length - 1)];
302 >        }
303 >
304 >        /**
305 >         * Read value field of an entry under lock. Called if value
306 >         * field ever appears to be null. This is possible only if a
307 >         * compiler happens to reorder a HashEntry initialization with
308 >         * its table assignment, which is legal under memory model
309 >         * but is not known to ever occur.
310 >         */
311 >        V readValueUnderLock(HashEntry<K,V> e) {
312 >            lock();
313 >            try {
314 >                return e.value;
315 >            } finally {
316 >                unlock();
317 >            }
318          }
319  
320          /* Specialized implementations of map methods */
321  
322 <        V get(K key, int hash) {
322 >        V get(Object key, int hash) {
323              if (count != 0) { // read-volatile
324 <                HashEntry[] tab = table;
233 <                int index = hash & (tab.length - 1);
234 <                HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
324 >                HashEntry<K,V> e = getFirst(hash);
325                  while (e != null) {
326 <                    if (e.hash == hash && key.equals(e.key))
327 <                        return e.value;
326 >                    if (e.hash == hash && key.equals(e.key)) {
327 >                        V v = e.value;
328 >                        if (v != null)
329 >                            return v;
330 >                        return readValueUnderLock(e); // recheck
331 >                    }
332                      e = e.next;
333                  }
334              }
# Line 243 | Line 337 | public class ConcurrentHashMap<K, V> ext
337  
338          boolean containsKey(Object key, int hash) {
339              if (count != 0) { // read-volatile
340 <                HashEntry[] tab = table;
247 <                int index = hash & (tab.length - 1);
248 <                HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
340 >                HashEntry<K,V> e = getFirst(hash);
341                  while (e != null) {
342                      if (e.hash == hash && key.equals(e.key))
343                          return true;
# Line 259 | Line 351 | public class ConcurrentHashMap<K, V> ext
351              if (count != 0) { // read-volatile
352                  HashEntry[] tab = table;
353                  int len = tab.length;
354 <                for (int i = 0 ; i < len; i++)
355 <                    for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i] ; e != null ; e = e.next)
356 <                        if (value.equals(e.value))
354 >                for (int i = 0 ; i < len; i++) {
355 >                    for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i];
356 >                         e != null ;
357 >                         e = e.next) {
358 >                        V v = e.value;
359 >                        if (v == null) // recheck
360 >                            v = readValueUnderLock(e);
361 >                        if (value.equals(v))
362                              return true;
363 +                    }
364 +                }
365              }
366              return false;
367          }
368  
369 +        boolean replace(K key, int hash, V oldValue, V newValue) {
370 +            lock();
371 +            try {
372 +                HashEntry<K,V> e = getFirst(hash);
373 +                while (e != null && (e.hash != hash || !key.equals(e.key)))
374 +                    e = e.next;
375 +
376 +                boolean replaced = false;
377 +                if (e != null && oldValue.equals(e.value)) {
378 +                    replaced = true;
379 +                    e.value = newValue;
380 +                }
381 +                return replaced;
382 +            } finally {
383 +                unlock();
384 +            }
385 +        }
386 +
387 +        V replace(K key, int hash, V newValue) {
388 +            lock();
389 +            try {
390 +                HashEntry<K,V> e = getFirst(hash);
391 +                while (e != null && (e.hash != hash || !key.equals(e.key)))
392 +                    e = e.next;
393 +
394 +                V oldValue = null;
395 +                if (e != null) {
396 +                    oldValue = e.value;
397 +                    e.value = newValue;
398 +                }
399 +                return oldValue;
400 +            } finally {
401 +                unlock();
402 +            }
403 +        }
404 +
405 +
406          V put(K key, int hash, V value, boolean onlyIfAbsent) {
407              lock();
408              try {
409                  int c = count;
410 +                if (c++ > threshold) // ensure capacity
411 +                    rehash();
412                  HashEntry[] tab = table;
413                  int index = hash & (tab.length - 1);
414                  HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
415 +                HashEntry<K,V> e = first;
416 +                while (e != null && (e.hash != hash || !key.equals(e.key)))
417 +                    e = e.next;
418  
419 <                for (HashEntry<K,V> e = first; e != null; e = (HashEntry<K,V>) e.next) {
420 <                    if (e.hash == hash && key.equals(e.key)) {
421 <                        V oldValue = e.value;
422 <                        if (!onlyIfAbsent)
423 <                            e.value = value;
283 <                        count = c; // write-volatile
284 <                        return oldValue;
285 <                    }
419 >                V oldValue;
420 >                if (e != null) {
421 >                    oldValue = e.value;
422 >                    if (!onlyIfAbsent)
423 >                        e.value = value;
424                  }
425 <
426 <                tab[index] = new HashEntry<K,V>(hash, key, value, first);
427 <                ++c;
428 <                count = c; // write-volatile
429 <                if (c > threshold)
430 <                    setTable(rehash(tab));
431 <                return null;
432 <            }
295 <            finally {
425 >                else {
426 >                    oldValue = null;
427 >                    ++modCount;
428 >                    tab[index] = new HashEntry<K,V>(key, hash, first, value);
429 >                    count = c; // write-volatile
430 >                }
431 >                return oldValue;
432 >            } finally {
433                  unlock();
434              }
435          }
436  
437 <        private HashEntry[] rehash(HashEntry[] oldTable) {
437 >        void rehash() {
438 >            HashEntry[] oldTable = table;            
439              int oldCapacity = oldTable.length;
440              if (oldCapacity >= MAXIMUM_CAPACITY)
441 <                return oldTable;
441 >                return;
442  
443              /*
444               * Reclassify nodes in each list to new Map.  Because we are
# Line 309 | Line 447 | public class ConcurrentHashMap<K, V> ext
447               * offset. We eliminate unnecessary node creation by catching
448               * cases where old nodes can be reused because their next
449               * fields won't change. Statistically, at the default
450 <             * threshhold, only about one-sixth of them need cloning when
450 >             * threshold, only about one-sixth of them need cloning when
451               * a table doubles. The nodes they replace will be garbage
452               * collectable as soon as they are no longer referenced by any
453               * reader thread that may be in the midst of traversing table
# Line 317 | Line 455 | public class ConcurrentHashMap<K, V> ext
455               */
456  
457              HashEntry[] newTable = new HashEntry[oldCapacity << 1];
458 +            threshold = (int)(newTable.length * loadFactor);
459              int sizeMask = newTable.length - 1;
460              for (int i = 0; i < oldCapacity ; i++) {
461                  // We need to guarantee that any existing reads of old Map can
# Line 349 | Line 488 | public class ConcurrentHashMap<K, V> ext
488                          // Clone all remaining nodes
489                          for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
490                              int k = p.hash & sizeMask;
491 <                            newTable[k] = new HashEntry<K,V>(p.hash,
492 <                                                             p.key,
493 <                                                             p.value,
355 <                                                             (HashEntry<K,V>) newTable[k]);
491 >                            HashEntry<K,V> n = (HashEntry<K,V>)newTable[k];
492 >                            newTable[k] = new HashEntry<K,V>(p.key, p.hash,
493 >                                                             n, p.value);
494                          }
495                      }
496                  }
497              }
498 <            return newTable;
498 >            table = newTable;
499          }
500  
501          /**
# Line 366 | Line 504 | public class ConcurrentHashMap<K, V> ext
504          V remove(Object key, int hash, Object value) {
505              lock();
506              try {
507 <                int c = count;
507 >                int c = count - 1;
508                  HashEntry[] tab = table;
509                  int index = hash & (tab.length - 1);
510                  HashEntry<K,V> first = (HashEntry<K,V>)tab[index];
373
511                  HashEntry<K,V> e = first;
512 <                for (;;) {
376 <                    if (e == null)
377 <                        return null;
378 <                    if (e.hash == hash && key.equals(e.key))
379 <                        break;
512 >                while (e != null && (e.hash != hash || !key.equals(e.key)))
513                      e = e.next;
381                }
514  
515 <                V oldValue = e.value;
516 <                if (value != null && !value.equals(oldValue))
517 <                    return null;
518 <
519 <                // All entries following removed node can stay in list, but
520 <                // all preceeding ones need to be cloned.
521 <                HashEntry<K,V> newFirst = e.next;
522 <                for (HashEntry<K,V> p = first; p != e; p = p.next)
523 <                    newFirst = new HashEntry<K,V>(p.hash, p.key,
524 <                                                  p.value, newFirst);
525 <                tab[index] = newFirst;
526 <                count = c-1; // write-volatile
515 >                V oldValue = null;
516 >                if (e != null) {
517 >                    V v = e.value;
518 >                    if (value == null || value.equals(v)) {
519 >                        oldValue = v;
520 >                        // All entries following removed node can stay
521 >                        // in list, but all preceding ones need to be
522 >                        // cloned.
523 >                        ++modCount;
524 >                        HashEntry<K,V> newFirst = e.next;
525 >                        for (HashEntry<K,V> p = first; p != e; p = p.next)
526 >                            newFirst = new HashEntry<K,V>(p.key, p.hash,  
527 >                                                          newFirst, p.value);
528 >                        tab[index] = newFirst;
529 >                        count = c; // write-volatile
530 >                    }
531 >                }
532                  return oldValue;
533 <            }
397 <            finally {
533 >            } finally {
534                  unlock();
535              }
536          }
537  
538          void clear() {
539 <            lock();
540 <            try {
541 <                HashEntry[] tab = table;
542 <                for (int i = 0; i < tab.length ; i++)
543 <                    tab[i] = null;
544 <                count = 0; // write-volatile
545 <            }
546 <            finally {
547 <                unlock();
539 >            if (count != 0) {
540 >                lock();
541 >                try {
542 >                    HashEntry[] tab = table;
543 >                    for (int i = 0; i < tab.length ; i++)
544 >                        tab[i] = null;
545 >                    ++modCount;
546 >                    count = 0; // write-volatile
547 >                } finally {
548 >                    unlock();
549 >                }
550              }
551          }
552      }
553  
416    /**
417     * ConcurrentReaderHashMap list entry.
418     */
419    private static class HashEntry<K,V> implements Entry<K,V> {
420        private final K key;
421        private V value;
422        private final int hash;
423        private final HashEntry<K,V> next;
424
425        HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
426            this.value = value;
427            this.hash = hash;
428            this.key = key;
429            this.next = next;
430        }
431
432        public K getKey() {
433            return key;
434        }
435
436        public V getValue() {
437            return value;
438        }
439
440        public V setValue(V newValue) {
441            // We aren't required to, and don't provide any
442            // visibility barriers for setting value.
443            if (newValue == null)
444                throw new NullPointerException();
445            V oldValue = this.value;
446            this.value = newValue;
447            return oldValue;
448        }
449
450        public boolean equals(Object o) {
451            if (!(o instanceof Entry))
452                return false;
453            Entry<K,V> e = (Entry<K,V>)o;
454            return (key.equals(e.getKey()) && value.equals(e.getValue()));
455        }
456
457        public int hashCode() {
458            return  key.hashCode() ^ value.hashCode();
459        }
460
461        public String toString() {
462            return key + "=" + value;
463        }
464    }
554  
555  
556      /* ---------------- Public operations -------------- */
557  
558      /**
559 <     * Constructs a new, empty map with the specified initial
560 <     * capacity and the specified load factor.
559 >     * Creates a new, empty map with the specified initial
560 >     * capacity, load factor, and concurrency level.
561       *
562 <     * @param initialCapacity the initial capacity.  The actual
563 <     * initial capacity is rounded up to the nearest power of two.
562 >     * @param initialCapacity the initial capacity. The implementation
563 >     * performs internal sizing to accommodate this many elements.
564       * @param loadFactor  the load factor threshold, used to control resizing.
565 <     * @param segments the number of concurrently accessible segments. the
566 <     * actual number of segments is rounded to the next power of two.
565 >     * Resizing may be performed when the average number of elements per
566 >     * bin exceeds this threshold.
567 >     * @param concurrencyLevel the estimated number of concurrently
568 >     * updating threads. The implementation performs internal sizing
569 >     * to try to accommodate this many threads.  
570       * @throws IllegalArgumentException if the initial capacity is
571 <     * negative or the load factor or number of segments are
571 >     * negative or the load factor or concurrencyLevel are
572       * nonpositive.
573       */
574      public ConcurrentHashMap(int initialCapacity,
575 <                             float loadFactor, int segments) {
576 <        if (!(loadFactor > 0) || initialCapacity < 0 || segments <= 0)
575 >                             float loadFactor, int concurrencyLevel) {
576 >        if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
577              throw new IllegalArgumentException();
578  
579 +        if (concurrencyLevel > MAX_SEGMENTS)
580 +            concurrencyLevel = MAX_SEGMENTS;
581 +
582          // Find power-of-two sizes best matching arguments
583          int sshift = 0;
584          int ssize = 1;
585 <        while (ssize < segments) {
585 >        while (ssize < concurrencyLevel) {
586              ++sshift;
587              ssize <<= 1;
588          }
# Line 509 | Line 604 | public class ConcurrentHashMap<K, V> ext
604      }
605  
606      /**
607 <     * Constructs a new, empty map with the specified initial
608 <     * capacity,  and with default load factor and segments.
607 >     * Creates a new, empty map with the specified initial
608 >     * capacity,  and with default load factor (<tt>0.75f</tt>)
609 >     * and concurrencyLevel (<tt>16</tt>).
610       *
611 <     * @param initialCapacity the initial capacity of the
612 <     * ConcurrentHashMap.
611 >     * @param initialCapacity the initial capacity. The implementation
612 >     * performs internal sizing to accommodate this many elements.
613       * @throws IllegalArgumentException if the initial capacity of
614       * elements is negative.
615       */
# Line 522 | Line 618 | public class ConcurrentHashMap<K, V> ext
618      }
619  
620      /**
621 <     * Constructs a new, empty map with a default initial capacity,
622 <     * load factor, and number of segments
621 >     * Creates a new, empty map with a default initial capacity
622 >     * (<tt>16</tt>), load factor (<tt>0.75f</tt>) and
623 >     * concurrencyLevel (<tt>16</tt>).
624       */
625      public ConcurrentHashMap() {
626          this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
627      }
628  
629      /**
630 <     * Constructs a new map with the same mappings as the given map.  The
631 <     * map is created with a capacity of twice the number of mappings in
632 <     * the given map or 11 (whichever is greater), and a default load factor.
630 >     * Creates a new map with the same mappings as the given map.  The
631 >     * map is created with a capacity consistent with the default load
632 >     * factor (<tt>0.75f</tt>) and uses the default concurrencyLevel
633 >     * (<tt>16</tt>).
634 >     * @param t the map
635       */
636 <    public <A extends K, B extends V> ConcurrentHashMap(Map<A,B> t) {
636 >    public ConcurrentHashMap(Map<? extends K, ? extends V> t) {
637          this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
638 <                      11),
638 >                      DEFAULT_INITIAL_CAPACITY),
639               DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
640          putAll(t);
641      }
642  
643      // inherit Map javadoc
545    public int size() {
546        int c = 0;
547        for (int i = 0; i < segments.length; ++i)
548            c += segments[i].count;
549        return c;
550    }
551
552    // inherit Map javadoc
644      public boolean isEmpty() {
645 <        for (int i = 0; i < segments.length; ++i)
645 >        final Segment[] segments = this.segments;
646 >        /*
647 >         * We keep track of per-segment modCounts to avoid ABA
648 >         * problems in which an element in one segment was added and
649 >         * in another removed during traversal, in which case the
650 >         * table was never actually empty at any point. Note the
651 >         * similar use of modCounts in the size() and containsValue()
652 >         * methods, which are the only other methods also susceptible
653 >         * to ABA problems.
654 >         */
655 >        int[] mc = new int[segments.length];
656 >        int mcsum = 0;
657 >        for (int i = 0; i < segments.length; ++i) {
658              if (segments[i].count != 0)
659                  return false;
660 +            else
661 +                mcsum += mc[i] = segments[i].modCount;
662 +        }
663 +        // If mcsum happens to be zero, then we know we got a snapshot
664 +        // before any modifications at all were made.  This is
665 +        // probably common enough to bother tracking.
666 +        if (mcsum != 0) {
667 +            for (int i = 0; i < segments.length; ++i) {
668 +                if (segments[i].count != 0 ||
669 +                    mc[i] != segments[i].modCount)
670 +                    return false;
671 +            }
672 +        }
673          return true;
674      }
675  
676 +    // inherit Map javadoc
677 +    public int size() {
678 +        final Segment[] segments = this.segments;
679 +        long sum = 0;
680 +        long check = 0;
681 +        int[] mc = new int[segments.length];
682 +        // Try a few times to get accurate count. On failure due to
683 +        // continuous async changes in table, resort to locking.
684 +        for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
685 +            check = 0;
686 +            sum = 0;
687 +            int mcsum = 0;
688 +            for (int i = 0; i < segments.length; ++i) {
689 +                sum += segments[i].count;
690 +                mcsum += mc[i] = segments[i].modCount;
691 +            }
692 +            if (mcsum != 0) {
693 +                for (int i = 0; i < segments.length; ++i) {
694 +                    check += segments[i].count;
695 +                    if (mc[i] != segments[i].modCount) {
696 +                        check = -1; // force retry
697 +                        break;
698 +                    }
699 +                }
700 +            }
701 +            if (check == sum)
702 +                break;
703 +        }
704 +        if (check != sum) { // Resort to locking all segments
705 +            sum = 0;
706 +            for (int i = 0; i < segments.length; ++i)
707 +                segments[i].lock();
708 +            for (int i = 0; i < segments.length; ++i)
709 +                sum += segments[i].count;
710 +            for (int i = 0; i < segments.length; ++i)
711 +                segments[i].unlock();
712 +        }
713 +        if (sum > Integer.MAX_VALUE)
714 +            return Integer.MAX_VALUE;
715 +        else
716 +            return (int)sum;
717 +    }
718 +
719 +
720      /**
721       * Returns the value to which the specified key is mapped in this table.
722       *
723       * @param   key   a key in the table.
724       * @return  the value to which the key is mapped in this table;
725 <     *          <code>null</code> if the key is not mapped to any value in
725 >     *          <tt>null</tt> if the key is not mapped to any value in
726       *          this table.
727       * @throws  NullPointerException  if the key is
728 <     *               <code>null</code>.
569 <     * @see     #put(Object, Object)
728 >     *               <tt>null</tt>.
729       */
730      public V get(Object key) {
731          int hash = hash(key); // throws NullPointerException if key null
732 <        return segmentFor(hash).get((K) key, hash);
732 >        return segmentFor(hash).get(key, hash);
733      }
734  
735      /**
736       * Tests if the specified object is a key in this table.
737       *
738       * @param   key   possible key.
739 <     * @return  <code>true</code> if and only if the specified object
739 >     * @return  <tt>true</tt> if and only if the specified object
740       *          is a key in this table, as determined by the
741 <     *          <tt>equals</tt> method; <code>false</code> otherwise.
741 >     *          <tt>equals</tt> method; <tt>false</tt> otherwise.
742       * @throws  NullPointerException  if the key is
743 <     *               <code>null</code>.
585 <     * @see     #contains(Object)
743 >     *               <tt>null</tt>.
744       */
745      public boolean containsKey(Object key) {
746          int hash = hash(key); // throws NullPointerException if key null
# Line 598 | Line 756 | public class ConcurrentHashMap<K, V> ext
756       * @param value value whose presence in this map is to be tested.
757       * @return <tt>true</tt> if this map maps one or more keys to the
758       * specified value.
759 <     * @throws  NullPointerException  if the value is <code>null</code>.
759 >     * @throws  NullPointerException  if the value is <tt>null</tt>.
760       */
761      public boolean containsValue(Object value) {
762          if (value == null)
763              throw new NullPointerException();
764 +        
765 +        // See explanation of modCount use above
766  
767 <        for (int i = 0; i < segments.length; ++i) {
768 <            if (segments[i].containsValue(value))
769 <                return true;
767 >        final Segment[] segments = this.segments;
768 >        int[] mc = new int[segments.length];
769 >
770 >        // Try a few times without locking
771 >        for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
772 >            int sum = 0;
773 >            int mcsum = 0;
774 >            for (int i = 0; i < segments.length; ++i) {
775 >                int c = segments[i].count;
776 >                mcsum += mc[i] = segments[i].modCount;
777 >                if (segments[i].containsValue(value))
778 >                    return true;
779 >            }
780 >            boolean cleanSweep = true;
781 >            if (mcsum != 0) {
782 >                for (int i = 0; i < segments.length; ++i) {
783 >                    int c = segments[i].count;
784 >                    if (mc[i] != segments[i].modCount) {
785 >                        cleanSweep = false;
786 >                        break;
787 >                    }
788 >                }
789 >            }
790 >            if (cleanSweep)
791 >                return false;
792          }
793 <        return false;
793 >        // Resort to locking all segments
794 >        for (int i = 0; i < segments.length; ++i)
795 >            segments[i].lock();
796 >        boolean found = false;
797 >        try {
798 >            for (int i = 0; i < segments.length; ++i) {
799 >                if (segments[i].containsValue(value)) {
800 >                    found = true;
801 >                    break;
802 >                }
803 >            }
804 >        } finally {
805 >            for (int i = 0; i < segments.length; ++i)
806 >                segments[i].unlock();
807 >        }
808 >        return found;
809      }
810 +
811      /**
812 <     * Tests if some key maps into the specified value in this table.
813 <     * This operation is more expensive than the <code>containsKey</code>
814 <     * method.<p>
815 <     *
816 <     * Note that this method is identical in functionality to containsValue,
817 <     * (which is part of the Map interface in the collections framework).
818 <     *
812 >     * Legacy method testing if some key maps into the specified value
813 >     * in this table.  This method is identical in functionality to
814 >     * {@link #containsValue}, and  exists solely to ensure
815 >     * full compatibility with class {@link java.util.Hashtable},
816 >     * which supported this method prior to introduction of the
817 >     * Java Collections framework.
818 >
819       * @param      value   a value to search for.
820 <     * @return     <code>true</code> if and only if some key maps to the
821 <     *             <code>value</code> argument in this table as
820 >     * @return     <tt>true</tt> if and only if some key maps to the
821 >     *             <tt>value</tt> argument in this table as
822       *             determined by the <tt>equals</tt> method;
823 <     *             <code>false</code> otherwise.
824 <     * @throws  NullPointerException  if the value is <code>null</code>.
627 <     * @see        #containsKey(Object)
628 <     * @see        #containsValue(Object)
629 <     * @see   Map
823 >     *             <tt>false</tt> otherwise.
824 >     * @throws  NullPointerException  if the value is <tt>null</tt>.
825       */
826      public boolean contains(Object value) {
827          return containsValue(value);
828      }
829  
830      /**
831 <     * Maps the specified <code>key</code> to the specified
832 <     * <code>value</code> in this table. Neither the key nor the
833 <     * value can be <code>null</code>. <p>
831 >     * Maps the specified <tt>key</tt> to the specified
832 >     * <tt>value</tt> in this table. Neither the key nor the
833 >     * value can be <tt>null</tt>.
834       *
835 <     * The value can be retrieved by calling the <code>get</code> method
835 >     * <p> The value can be retrieved by calling the <tt>get</tt> method
836       * with a key that is equal to the original key.
837       *
838       * @param      key     the table key.
839       * @param      value   the value.
840       * @return     the previous value of the specified key in this table,
841 <     *             or <code>null</code> if it did not have one.
841 >     *             or <tt>null</tt> if it did not have one.
842       * @throws  NullPointerException  if the key or value is
843 <     *               <code>null</code>.
649 <     * @see     Object#equals(Object)
650 <     * @see     #get(Object)
843 >     *               <tt>null</tt>.
844       */
845      public V put(K key, V value) {
846          if (value == null)
# Line 661 | Line 854 | public class ConcurrentHashMap<K, V> ext
854       * with a value, associate it with the given value.
855       * This is equivalent to
856       * <pre>
857 <     *   if (!map.containsKey(key)) map.put(key, value);
858 <     *   return get(key);
857 >     *   if (!map.containsKey(key))
858 >     *      return map.put(key, value);
859 >     *   else
860 >     *      return map.get(key);
861       * </pre>
862       * Except that the action is performed atomically.
863       * @param key key with which the specified value is to be associated.
864       * @param value value to be associated with the specified key.
865       * @return previous value associated with specified key, or <tt>null</tt>
866 <     *         if there was no mapping for key.  A <tt>null</tt> return can
867 <     *         also indicate that the map previously associated <tt>null</tt>
673 <     *         with the specified key, if the implementation supports
674 <     *         <tt>null</tt> values.
675 <     *
676 <     * @throws NullPointerException this map does not permit <tt>null</tt>
677 <     *            keys or values, and the specified key or value is
866 >     *         if there was no mapping for key.
867 >     * @throws NullPointerException if the specified key or value is
868       *            <tt>null</tt>.
869 <     *
680 <     **/
869 >     */
870      public V putIfAbsent(K key, V value) {
871          if (value == null)
872              throw new NullPointerException();
# Line 695 | Line 884 | public class ConcurrentHashMap<K, V> ext
884       * @param t Mappings to be stored in this map.
885       */
886      public void putAll(Map<? extends K, ? extends V> t) {
887 <        Iterator<Map.Entry<? extends K, ? extends V>> it = t.entrySet().iterator();
699 <        while (it.hasNext()) {
887 >        for (Iterator<? extends Map.Entry<? extends K, ? extends V>> it = (Iterator<? extends Map.Entry<? extends K, ? extends V>>) t.entrySet().iterator(); it.hasNext(); ) {
888              Entry<? extends K, ? extends V> e = it.next();
889              put(e.getKey(), e.getValue());
890          }
# Line 708 | Line 896 | public class ConcurrentHashMap<K, V> ext
896       *
897       * @param   key   the key that needs to be removed.
898       * @return  the value to which the key had been mapped in this table,
899 <     *          or <code>null</code> if the key did not have a mapping.
899 >     *          or <tt>null</tt> if the key did not have a mapping.
900       * @throws  NullPointerException  if the key is
901 <     *               <code>null</code>.
901 >     *               <tt>null</tt>.
902       */
903      public V remove(Object key) {
904          int hash = hash(key);
# Line 718 | Line 906 | public class ConcurrentHashMap<K, V> ext
906      }
907  
908      /**
909 <     * Removes the (key, value) pair from this
910 <     * table. This method does nothing if the key is not in the table,
911 <     * or if the key is associated with a different value.
912 <     *
913 <     * @param   key   the key that needs to be removed.
914 <     * @param   value   the associated value. If the value is null,
915 <     *                   it means "any value".
916 <     * @return  the value to which the key had been mapped in this table,
917 <     *          or <code>null</code> if the key did not have a mapping.
918 <     * @throws  NullPointerException  if the key is
919 <     *               <code>null</code>.
909 >     * Remove entry for key only if currently mapped to given value.
910 >     * Acts as
911 >     * <pre>
912 >     *  if (map.get(key).equals(value)) {
913 >     *     map.remove(key);
914 >     *     return true;
915 >     * } else return false;
916 >     * </pre>
917 >     * except that the action is performed atomically.
918 >     * @param key key with which the specified value is associated.
919 >     * @param value value associated with the specified key.
920 >     * @return true if the value was removed
921 >     * @throws NullPointerException if the specified key is
922 >     *            <tt>null</tt>.
923       */
924      public boolean remove(Object key, Object value) {
925          int hash = hash(key);
926          return segmentFor(hash).remove(key, hash, value) != null;
927      }
928  
929 +
930      /**
931 <     * Removes all mappings from this map.
931 >     * Replace entry for key only if currently mapped to given value.
932 >     * Acts as
933 >     * <pre>
934 >     *  if (map.get(key).equals(oldValue)) {
935 >     *     map.put(key, newValue);
936 >     *     return true;
937 >     * } else return false;
938 >     * </pre>
939 >     * except that the action is performed atomically.
940 >     * @param key key with which the specified value is associated.
941 >     * @param oldValue value expected to be associated with the specified key.
942 >     * @param newValue value to be associated with the specified key.
943 >     * @return true if the value was replaced
944 >     * @throws NullPointerException if the specified key or values are
945 >     * <tt>null</tt>.
946       */
947 <    public void clear() {
948 <        for (int i = 0; i < segments.length; ++i)
949 <            segments[i].clear();
947 >    public boolean replace(K key, V oldValue, V newValue) {
948 >        if (oldValue == null || newValue == null)
949 >            throw new NullPointerException();
950 >        int hash = hash(key);
951 >        return segmentFor(hash).replace(key, hash, oldValue, newValue);
952 >    }
953 >
954 >    /**
955 >     * Replace entry for key only if currently mapped to some value.
956 >     * Acts as
957 >     * <pre>
958 >     *  if ((map.containsKey(key)) {
959 >     *     return map.put(key, value);
960 >     * } else return null;
961 >     * </pre>
962 >     * except that the action is performed atomically.
963 >     * @param key key with which the specified value is associated.
964 >     * @param value value to be associated with the specified key.
965 >     * @return previous value associated with specified key, or <tt>null</tt>
966 >     *         if there was no mapping for key.  
967 >     * @throws NullPointerException if the specified key or value is
968 >     *            <tt>null</tt>.
969 >     */
970 >    public V replace(K key, V value) {
971 >        if (value == null)
972 >            throw new NullPointerException();
973 >        int hash = hash(key);
974 >        return segmentFor(hash).replace(key, hash, value);
975      }
976  
977  
978      /**
979 <     * Returns a shallow copy of this
980 <     * <tt>ConcurrentHashMap</tt> instance: the keys and
981 <     * values themselves are not cloned.
982 <     *
983 <     * @return a shallow copy of this map.
753 <     */
754 <    public Object clone() {
755 <        // We cannot call super.clone, since it would share final
756 <        // segments array, and there's no way to reassign finals.
757 <
758 <        float lf = segments[0].loadFactor;
759 <        int segs = segments.length;
760 <        int cap = (int)(size() / lf);
761 <        if (cap < segs) cap = segs;
762 <        ConcurrentHashMap<K,V> t = new ConcurrentHashMap<K,V>(cap, lf, segs);
763 <        t.putAll(this);
764 <        return t;
979 >     * Removes all mappings from this map.
980 >     */
981 >    public void clear() {
982 >        for (int i = 0; i < segments.length; ++i)
983 >            segments[i].clear();
984      }
985  
986      /**
# Line 772 | Line 991 | public class ConcurrentHashMap<K, V> ext
991       * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
992       * <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
993       * <tt>addAll</tt> operations.
994 +     * The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
995 +     * will never throw {@link java.util.ConcurrentModificationException},
996 +     * and guarantees to traverse elements as they existed upon
997 +     * construction of the iterator, and may (but is not guaranteed to)
998 +     * reflect any modifications subsequent to construction.
999       *
1000       * @return a set view of the keys contained in this map.
1001       */
# Line 789 | Line 1013 | public class ConcurrentHashMap<K, V> ext
1013       * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1014       * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1015       * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1016 +     * The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
1017 +     * will never throw {@link java.util.ConcurrentModificationException},
1018 +     * and guarantees to traverse elements as they existed upon
1019 +     * construction of the iterator, and may (but is not guaranteed to)
1020 +     * reflect any modifications subsequent to construction.
1021       *
1022       * @return a collection view of the values contained in this map.
1023       */
# Line 807 | Line 1036 | public class ConcurrentHashMap<K, V> ext
1036       * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1037       * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1038       * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1039 +     * The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
1040 +     * will never throw {@link java.util.ConcurrentModificationException},
1041 +     * and guarantees to traverse elements as they existed upon
1042 +     * construction of the iterator, and may (but is not guaranteed to)
1043 +     * reflect any modifications subsequent to construction.
1044       *
1045       * @return a collection view of the mappings contained in this map.
1046       */
1047      public Set<Map.Entry<K,V>> entrySet() {
1048          Set<Map.Entry<K,V>> es = entrySet;
1049 <        return (es != null) ? es : (entrySet = new EntrySet());
1049 >        return (es != null) ? es : (entrySet = (Set<Map.Entry<K,V>>) (Set) new EntrySet());
1050      }
1051  
1052  
# Line 820 | Line 1054 | public class ConcurrentHashMap<K, V> ext
1054       * Returns an enumeration of the keys in this table.
1055       *
1056       * @return  an enumeration of the keys in this table.
1057 <     * @see     Enumeration
824 <     * @see     #elements()
825 <     * @see     #keySet()
826 <     * @see     Map
1057 >     * @see     #keySet
1058       */
1059      public Enumeration<K> keys() {
1060          return new KeyIterator();
# Line 831 | Line 1062 | public class ConcurrentHashMap<K, V> ext
1062  
1063      /**
1064       * Returns an enumeration of the values in this table.
834     * Use the Enumeration methods on the returned object to fetch the elements
835     * sequentially.
1065       *
1066       * @return  an enumeration of the values in this table.
1067 <     * @see     java.util.Enumeration
839 <     * @see     #keys()
840 <     * @see     #values()
841 <     * @see     Map
1067 >     * @see     #values
1068       */
1069      public Enumeration<V> elements() {
1070          return new ValueIterator();
# Line 846 | Line 1072 | public class ConcurrentHashMap<K, V> ext
1072  
1073      /* ---------------- Iterator Support -------------- */
1074  
1075 <    private abstract class HashIterator {
1076 <        private int nextSegmentIndex;
1077 <        private int nextTableIndex;
1078 <        private HashEntry[] currentTable;
1079 <        private HashEntry<K, V> nextEntry;
1080 <        private HashEntry<K, V> lastReturned;
1075 >    abstract class HashIterator {
1076 >        int nextSegmentIndex;
1077 >        int nextTableIndex;
1078 >        HashEntry[] currentTable;
1079 >        HashEntry<K, V> nextEntry;
1080 >        HashEntry<K, V> lastReturned;
1081  
1082 <        private HashIterator() {
1082 >        HashIterator() {
1083              nextSegmentIndex = segments.length - 1;
1084              nextTableIndex = -1;
1085              advance();
# Line 861 | Line 1087 | public class ConcurrentHashMap<K, V> ext
1087  
1088          public boolean hasMoreElements() { return hasNext(); }
1089  
1090 <        private void advance() {
1090 >        final void advance() {
1091              if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1092                  return;
1093  
# Line 902 | Line 1128 | public class ConcurrentHashMap<K, V> ext
1128          }
1129      }
1130  
1131 <    private class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1131 >    final class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1132          public K next() { return super.nextEntry().key; }
1133          public K nextElement() { return super.nextEntry().key; }
1134      }
1135  
1136 <    private class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1136 >    final class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1137          public V next() { return super.nextEntry().value; }
1138          public V nextElement() { return super.nextEntry().value; }
1139      }
1140  
1141 <    private class EntryIterator extends HashIterator implements Iterator<Entry<K,V>> {
1142 <        public Map.Entry<K,V> next() { return super.nextEntry(); }
1141 >    
1142 >
1143 >    /**
1144 >     * Entry iterator. Exported Entry objects must write-through
1145 >     * changes in setValue, even if the nodes have been cloned. So we
1146 >     * cannot return internal HashEntry objects. Instead, the iterator
1147 >     * itself acts as a forwarding pseudo-entry.
1148 >     */
1149 >    final class EntryIterator extends HashIterator implements Map.Entry<K,V>, Iterator<Entry<K,V>> {
1150 >        public Map.Entry<K,V> next() {
1151 >            nextEntry();
1152 >            return this;
1153 >        }
1154 >
1155 >        public K getKey() {
1156 >            if (lastReturned == null)
1157 >                throw new IllegalStateException("Entry was removed");
1158 >            return lastReturned.key;
1159 >        }
1160 >
1161 >        public V getValue() {
1162 >            if (lastReturned == null)
1163 >                throw new IllegalStateException("Entry was removed");
1164 >            return ConcurrentHashMap.this.get(lastReturned.key);
1165 >        }
1166 >
1167 >        public V setValue(V value) {
1168 >            if (lastReturned == null)
1169 >                throw new IllegalStateException("Entry was removed");
1170 >            return ConcurrentHashMap.this.put(lastReturned.key, value);
1171 >        }
1172 >
1173 >        public boolean equals(Object o) {
1174 >            // If not acting as entry, just use default.
1175 >            if (lastReturned == null)
1176 >                return super.equals(o);
1177 >            if (!(o instanceof Map.Entry))
1178 >                return false;
1179 >            Map.Entry e = (Map.Entry)o;
1180 >            return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1181 >        }
1182 >
1183 >        public int hashCode() {
1184 >            // If not acting as entry, just use default.
1185 >            if (lastReturned == null)
1186 >                return super.hashCode();
1187 >
1188 >            Object k = getKey();
1189 >            Object v = getValue();
1190 >            return ((k == null) ? 0 : k.hashCode()) ^
1191 >                   ((v == null) ? 0 : v.hashCode());
1192 >        }
1193 >
1194 >        public String toString() {
1195 >            // If not acting as entry, just use default.
1196 >            if (lastReturned == null)
1197 >                return super.toString();
1198 >            else
1199 >                return getKey() + "=" + getValue();
1200 >        }
1201 >
1202 >        boolean eq(Object o1, Object o2) {
1203 >            return (o1 == null ? o2 == null : o1.equals(o2));
1204 >        }
1205 >
1206      }
1207  
1208 <    private class KeySet extends AbstractSet<K> {
1208 >    final class KeySet extends AbstractSet<K> {
1209          public Iterator<K> iterator() {
1210              return new KeyIterator();
1211          }
# Line 932 | Line 1221 | public class ConcurrentHashMap<K, V> ext
1221          public void clear() {
1222              ConcurrentHashMap.this.clear();
1223          }
1224 +        public Object[] toArray() {
1225 +            Collection<K> c = new ArrayList<K>();
1226 +            for (Iterator<K> i = iterator(); i.hasNext(); )
1227 +                c.add(i.next());
1228 +            return c.toArray();
1229 +        }
1230 +        public <T> T[] toArray(T[] a) {
1231 +            Collection<K> c = new ArrayList<K>();
1232 +            for (Iterator<K> i = iterator(); i.hasNext(); )
1233 +                c.add(i.next());
1234 +            return c.toArray(a);
1235 +        }
1236      }
1237  
1238 <    private class Values extends AbstractCollection<V> {
1238 >    final class Values extends AbstractCollection<V> {
1239          public Iterator<V> iterator() {
1240              return new ValueIterator();
1241          }
# Line 947 | Line 1248 | public class ConcurrentHashMap<K, V> ext
1248          public void clear() {
1249              ConcurrentHashMap.this.clear();
1250          }
1251 +        public Object[] toArray() {
1252 +            Collection<V> c = new ArrayList<V>();
1253 +            for (Iterator<V> i = iterator(); i.hasNext(); )
1254 +                c.add(i.next());
1255 +            return c.toArray();
1256 +        }
1257 +        public <T> T[] toArray(T[] a) {
1258 +            Collection<V> c = new ArrayList<V>();
1259 +            for (Iterator<V> i = iterator(); i.hasNext(); )
1260 +                c.add(i.next());
1261 +            return c.toArray(a);
1262 +        }
1263      }
1264  
1265 <    private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1265 >    final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1266          public Iterator<Map.Entry<K,V>> iterator() {
1267              return new EntryIterator();
1268          }
# Line 972 | Line 1285 | public class ConcurrentHashMap<K, V> ext
1285          public void clear() {
1286              ConcurrentHashMap.this.clear();
1287          }
1288 +        public Object[] toArray() {
1289 +            // Since we don't ordinarily have distinct Entry objects, we
1290 +            // must pack elements using exportable SimpleEntry
1291 +            Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1292 +            for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1293 +                c.add(new SimpleEntry<K,V>(i.next()));
1294 +            return c.toArray();
1295 +        }
1296 +        public <T> T[] toArray(T[] a) {
1297 +            Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1298 +            for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1299 +                c.add(new SimpleEntry<K,V>(i.next()));
1300 +            return c.toArray(a);
1301 +        }
1302 +
1303 +    }
1304 +
1305 +    /**
1306 +     * This duplicates java.util.AbstractMap.SimpleEntry until this class
1307 +     * is made accessible.
1308 +     */
1309 +    static final class SimpleEntry<K,V> implements Entry<K,V> {
1310 +        K key;
1311 +        V value;
1312 +
1313 +        public SimpleEntry(K key, V value) {
1314 +            this.key   = key;
1315 +            this.value = value;
1316 +        }
1317 +
1318 +        public SimpleEntry(Entry<K,V> e) {
1319 +            this.key   = e.getKey();
1320 +            this.value = e.getValue();
1321 +        }
1322 +
1323 +        public K getKey() {
1324 +            return key;
1325 +        }
1326 +
1327 +        public V getValue() {
1328 +            return value;
1329 +        }
1330 +
1331 +        public V setValue(V value) {
1332 +            V oldValue = this.value;
1333 +            this.value = value;
1334 +            return oldValue;
1335 +        }
1336 +
1337 +        public boolean equals(Object o) {
1338 +            if (!(o instanceof Map.Entry))
1339 +                return false;
1340 +            Map.Entry e = (Map.Entry)o;
1341 +            return eq(key, e.getKey()) && eq(value, e.getValue());
1342 +        }
1343 +
1344 +        public int hashCode() {
1345 +            return ((key   == null)   ? 0 :   key.hashCode()) ^
1346 +                   ((value == null)   ? 0 : value.hashCode());
1347 +        }
1348 +
1349 +        public String toString() {
1350 +            return key + "=" + value;
1351 +        }
1352 +
1353 +        static boolean eq(Object o1, Object o2) {
1354 +            return (o1 == null ? o2 == null : o1.equals(o2));
1355 +        }
1356      }
1357  
1358      /* ---------------- Serialization Support -------------- */
# Line 1000 | Line 1381 | public class ConcurrentHashMap<K, V> ext
1381                          s.writeObject(e.value);
1382                      }
1383                  }
1384 <            }
1004 <            finally {
1384 >            } finally {
1385                  seg.unlock();
1386              }
1387          }

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines