harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hinde...@apache.org
Subject svn commit: r798469 [5/28] - in /harmony/enhanced/classlib/branches/java6: ./ depends/build/platform/ depends/files/ depends/jars/ depends/manifests/icu4j_4.0/ depends/manifests/icu4j_4.2.1/ depends/manifests/icu4j_4.2.1/META-INF/ make/ modules/accessi...
Date Tue, 28 Jul 2009 09:30:48 GMT
Modified: harmony/enhanced/classlib/branches/java6/modules/concurrent/src/main/java/java/util/concurrent/ConcurrentHashMap.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/branches/java6/modules/concurrent/src/main/java/java/util/concurrent/ConcurrentHashMap.java?rev=798469&r1=798468&r2=798469&view=diff
==============================================================================
--- harmony/enhanced/classlib/branches/java6/modules/concurrent/src/main/java/java/util/concurrent/ConcurrentHashMap.java (original)
+++ harmony/enhanced/classlib/branches/java6/modules/concurrent/src/main/java/java/util/concurrent/ConcurrentHashMap.java Tue Jul 28 09:30:33 2009
@@ -33,13 +33,12 @@
  * removal of only some entries.  Similarly, Iterators and
  * Enumerations return elements reflecting the state of the hash table
  * at some point at or since the creation of the iterator/enumeration.
- * They do <em>not</em> throw
- * {@link ConcurrentModificationException}.  However, iterators are
- * designed to be used by only one thread at a time.
+ * They do <em>not</em> throw {@link ConcurrentModificationException}.
+ * However, iterators are designed to be used by only one thread at a time.
  *
  * <p> The allowed concurrency among update operations is guided by
  * the optional <tt>concurrencyLevel</tt> constructor argument
- * (default 16), which is used as a hint for internal sizing.  The
+ * (default <tt>16</tt>), which is used as a hint for internal sizing.  The
  * table is internally partitioned to try to permit the indicated
  * number of concurrent updates without contention. Because placement
  * in hash tables is essentially random, the actual concurrency will
@@ -49,24 +48,27 @@
  * and a significantly lower value can lead to thread contention. But
  * overestimates and underestimates within an order of magnitude do
  * not usually have much noticeable impact. A value of one is
- * appropriate when it is known that only one thread will modify
- * and all others will only read.
+ * appropriate when it is known that only one thread will modify and
+ * all others will only read. Also, resizing this or any other kind of
+ * hash table is a relatively slow operation, so, when possible, it is
+ * a good idea to provide estimates of expected table sizes in
+ * constructors.
  *
- * <p>This class implements all of the <em>optional</em> methods
- * of the {@link Map} and {@link Iterator} interfaces.
+ * <p>This class and its views and iterators implement all of the
+ * <em>optional</em> methods of the {@link Map} and {@link Iterator}
+ * interfaces.
  *
- * <p> Like {@link java.util.Hashtable} but unlike {@link
- * java.util.HashMap}, this class does NOT allow <tt>null</tt> to be
- * used as a key or value.
+ * <p> Like {@link Hashtable} but unlike {@link HashMap}, this class
+ * does <em>not</em> allow <tt>null</tt> to be used as a key or value.
  *
  * <p>This class is a member of the
- * <a href="{@docRoot}/../guide/collections/index.html">
+ * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  * Java Collections Framework</a>.
  *
  * @since 1.5
  * @author Doug Lea
  * @param <K> the type of keys maintained by this map
- * @param <V> the type of mapped values 
+ * @param <V> the type of mapped values
  */
 public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
         implements ConcurrentMap<K, V>, Serializable {
@@ -80,29 +82,30 @@
     /* ---------------- Constants -------------- */
 
     /**
-     * The default initial number of table slots for this table.
-     * Used when not otherwise specified in constructor.
+     * The default initial capacity for this table,
+     * used when not otherwise specified in a constructor.
      */
-    static int DEFAULT_INITIAL_CAPACITY = 16;
+    static final int DEFAULT_INITIAL_CAPACITY = 16;
 
     /**
-     * The maximum capacity, used if a higher value is implicitly
-     * specified by either of the constructors with arguments.  MUST
-     * be a power of two <= 1<<30 to ensure that entries are indexible
-     * using ints.
+     * The default load factor for this table, used when not
+     * otherwise specified in a constructor.
      */
-    static final int MAXIMUM_CAPACITY = 1 << 30; 
+    static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
     /**
-     * The default load factor for this table.  Used when not
-     * otherwise specified in constructor.
+     * The default concurrency level for this table, used when not
+     * otherwise specified in a constructor.
      */
-    static final float DEFAULT_LOAD_FACTOR = 0.75f;
+    static final int DEFAULT_CONCURRENCY_LEVEL = 16;
 
     /**
-     * The default number of concurrency control segments.
-     **/
-    static final int DEFAULT_SEGMENTS = 16;
+     * The maximum capacity, used if a higher value is implicitly
+     * specified by either of the constructors with arguments.  MUST
+     * be a power of two <= 1<<30 to ensure that entries are indexable
+     * using ints.
+     */
+    static final int MAXIMUM_CAPACITY = 1 << 30;
 
     /**
      * The maximum number of segments to allow; used to bound
@@ -110,23 +113,31 @@
      */
     static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
 
+    /**
+     * Number of unsynchronized retries in size and containsValue
+     * methods before resorting to locking. This is used to avoid
+     * unbounded retries if tables undergo continuous modification
+     * which would make it impossible to obtain an accurate result.
+     */
+    static final int RETRIES_BEFORE_LOCK = 2;
+
     /* ---------------- Fields -------------- */
 
     /**
      * Mask value for indexing into segments. The upper bits of a
      * key's hash code are used to choose the segment.
-     **/
+     */
     final int segmentMask;
 
     /**
      * Shift value for indexing within segments.
-     **/
+     */
     final int segmentShift;
 
     /**
      * The segments, each of which is a specialized hash table
      */
-    final Segment[] segments;
+    final Segment<K,V>[] segments;
 
     transient Set<K> keySet;
     transient Set<Map.Entry<K,V>> entrySet;
@@ -135,18 +146,21 @@
     /* ---------------- Small Utilities -------------- */
 
     /**
-     * Returns a hash code for non-null Object x.
-     * Uses the same hash code spreader as most other java.util hash tables.
-     * @param x the object serving as a key
-     * @return the hash code
-     */
-    static int hash(Object x) {
-        int h = x.hashCode();
-        h += ~(h << 9);
-        h ^=  (h >>> 14);
-        h +=  (h << 4);
-        h ^=  (h >>> 10);
-        return h;
+     * Applies a supplemental hash function to a given hashCode, which
+     * defends against poor quality hash functions.  This is critical
+     * because ConcurrentHashMap uses power-of-two length hash tables,
+     * that otherwise encounter collisions for hashCodes that do not
+     * differ in lower or upper bits.
+     */
+    private static int hash(int h) {
+        // Spread bits to regularize both segment and index locations,
+        // using variant of single-word Wang/Jenkins hash.
+        h += (h <<  15) ^ 0xffffcd7d;
+        h ^= (h >>> 10);
+        h += (h <<   3);
+        h ^= (h >>>  6);
+        h += (h <<   2) + (h << 14);
+        return h ^ (h >>> 16);
     }
 
     /**
@@ -155,16 +169,47 @@
      * @return the segment
      */
     final Segment<K,V> segmentFor(int hash) {
-        return (Segment<K,V>) segments[(hash >>> segmentShift) & segmentMask];
+        return segments[(hash >>> segmentShift) & segmentMask];
     }
 
     /* ---------------- Inner Classes -------------- */
 
     /**
+     * ConcurrentHashMap list entry. Note that this is never exported
+     * out as a user-visible Map.Entry.
+     *
+     * Because the value field is volatile, not final, it is legal wrt
+     * the Java Memory Model for an unsynchronized reader to see null
+     * instead of initial value when read via a data race.  Although a
+     * reordering leading to this is not likely to ever actually
+     * occur, the Segment.readValueUnderLock method is used as a
+     * backup in case a null (pre-initialized) value is ever seen in
+     * an unsynchronized access method.
+     */
+    static final class HashEntry<K,V> {
+        final K key;
+        final int hash;
+        volatile V value;
+        final HashEntry<K,V> next;
+
+        HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
+            this.key = key;
+            this.hash = hash;
+            this.next = next;
+            this.value = value;
+        }
+
+        @SuppressWarnings("unchecked")
+        static final <K,V> HashEntry<K,V>[] newArray(int i) {
+            return new HashEntry[i];
+        }
+    }
+
+    /**
      * Segments are specialized versions of hash tables.  This
      * subclasses from ReentrantLock opportunistically, just to
      * simplify some locking and avoid separate construction.
-     **/
+     */
     static final class Segment<K,V> extends ReentrantLock implements Serializable {
         /*
          * Segments maintain a table of entry lists that are ALWAYS
@@ -178,58 +223,59 @@
          * is less than two for the default load factor threshold.)
          *
          * Read operations can thus proceed without locking, but rely
-         * on a memory barrier to ensure that completed write
-         * operations performed by other threads are
-         * noticed. Conveniently, the "count" field, tracking the
-         * number of elements, can also serve as the volatile variable
-         * providing proper read/write barriers. This is convenient
-         * because this field needs to be read in many read operations
-         * anyway. 
-         *
-         * Implementors note. The basic rules for all this are:
+         * on selected uses of volatiles to ensure that completed
+         * write operations performed by other threads are
+         * noticed. For most purposes, the "count" field, tracking the
+         * number of elements, serves as that volatile variable
+         * ensuring visibility.  This is convenient because this field
+         * needs to be read in many read operations anyway:
          *
-         *   - All unsynchronized read operations must first read the
+         *   - All (unsynchronized) read operations must first read the
          *     "count" field, and should not look at table entries if
          *     it is 0.
          *
-         *   - All synchronized write operations should write to
-         *     the "count" field after updating. The operations must not
-         *     take any action that could even momentarily cause
-         *     a concurrent read operation to see inconsistent
-         *     data. This is made easier by the nature of the read
-         *     operations in Map. For example, no operation
+         *   - All (synchronized) write operations should write to
+         *     the "count" field after structurally changing any bin.
+         *     The operations must not take any action that could even
+         *     momentarily cause a concurrent read operation to see
+         *     inconsistent data. This is made easier by the nature of
+         *     the read operations in Map. For example, no operation
          *     can reveal that the table has grown but the threshold
          *     has not yet been updated, so there are no atomicity
          *     requirements for this with respect to reads.
          *
-         * As a guide, all critical volatile reads and writes are marked
-         * in code comments.
+         * As a guide, all critical volatile reads and writes to the
+         * count field are marked in code comments.
          */
 
         private static final long serialVersionUID = 2249069246763182397L;
 
         /**
          * The number of elements in this segment's region.
-         **/
+         */
         transient volatile int count;
 
         /**
-         * Number of updates; used for checking lack of modifications
-         * in bulk-read methods.
+         * Number of updates that alter the size of the table. This is
+         * used during bulk-read methods to make sure they see a
+         * consistent snapshot: If modCounts change during a traversal
+         * of segments computing size or checking containsValue, then
+         * we might have an inconsistent view of state so (usually)
+         * must retry.
          */
         transient int modCount;
 
         /**
          * The table is rehashed when its size exceeds this threshold.
-         * (The value of this field is always (int)(capacity *
-         * loadFactor).)
+         * (The value of this field is always <tt>(int)(capacity *
+         * loadFactor)</tt>.)
          */
         transient int threshold;
 
         /**
-         * The per-segment table
+         * The per-segment table.
          */
-        transient HashEntry[] table;
+        transient volatile HashEntry<K,V>[] table;
 
         /**
          * The load factor for the hash table.  Even though this value
@@ -241,29 +287,59 @@
 
         Segment(int initialCapacity, float lf) {
             loadFactor = lf;
-            setTable(new HashEntry[initialCapacity]);
+            setTable(HashEntry.<K,V>newArray(initialCapacity));
+        }
+
+        @SuppressWarnings("unchecked")
+        static final <K,V> Segment<K,V>[] newArray(int i) {
+            return new Segment[i];
         }
 
         /**
-         * Set table to new HashEntry array.
+         * Sets table to new HashEntry array.
          * Call only while holding lock or in constructor.
-         **/
-        void setTable(HashEntry[] newTable) {
-            table = newTable;
+         */
+        void setTable(HashEntry<K,V>[] newTable) {
             threshold = (int)(newTable.length * loadFactor);
-            count = count; // write-volatile
+            table = newTable;
+        }
+
+        /**
+         * Returns properly casted first entry of bin for given hash.
+         */
+        HashEntry<K,V> getFirst(int hash) {
+            HashEntry<K,V>[] tab = table;
+            return tab[hash & (tab.length - 1)];
+        }
+
+        /**
+         * Reads value field of an entry under lock. Called if value
+         * field ever appears to be null. This is possible only if a
+         * compiler happens to reorder a HashEntry initialization with
+         * its table assignment, which is legal under memory model
+         * but is not known to ever occur.
+         */
+        V readValueUnderLock(HashEntry<K,V> e) {
+            lock();
+            try {
+                return e.value;
+            } finally {
+                unlock();
+            }
         }
 
         /* Specialized implementations of map methods */
 
         V get(Object key, int hash) {
             if (count != 0) { // read-volatile
-                HashEntry[] tab = table;
-                int index = hash & (tab.length - 1);
-                HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
+                HashEntry<K,V> e = getFirst(hash);
                 while (e != null) {
-                    if (e.hash == hash && key.equals(e.key))
-                        return e.value;
+                    if (e.hash == hash && key.equals(e.key)) {
+                        V v = e.value;
+                        if (v != null)
+                            return v;
+                        return readValueUnderLock(e); // recheck
+                    }
                     e = e.next;
                 }
             }
@@ -272,9 +348,7 @@
 
         boolean containsKey(Object key, int hash) {
             if (count != 0) { // read-volatile
-                HashEntry[] tab = table;
-                int index = hash & (tab.length - 1);
-                HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
+                HashEntry<K,V> e = getFirst(hash);
                 while (e != null) {
                     if (e.hash == hash && key.equals(e.key))
                         return true;
@@ -286,12 +360,17 @@
 
         boolean containsValue(Object value) {
             if (count != 0) { // read-volatile
-                HashEntry[] tab = table;
+                HashEntry<K,V>[] tab = table;
                 int len = tab.length;
-                for (int i = 0 ; i < len; i++)
-                    for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i] ; e != null ; e = e.next)
-                        if (value.equals(e.value))
+                for (int i = 0 ; i < len; i++) {
+                    for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
+                        V v = e.value;
+                        if (v == null) // recheck
+                            v = readValueUnderLock(e);
+                        if (value.equals(v))
                             return true;
+                    }
+                }
             }
             return false;
         }
@@ -299,27 +378,16 @@
         boolean replace(K key, int hash, V oldValue, V newValue) {
             lock();
             try {
-                int c = count;
-                HashEntry[] tab = table;
-                int index = hash & (tab.length - 1);
-                HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
-                HashEntry<K,V> e = first;
-                for (;;) {
-                    if (e == null)
-                        return false;
-                    if (e.hash == hash && key.equals(e.key))
-                        break;
+                HashEntry<K,V> e = getFirst(hash);
+                while (e != null && (e.hash != hash || !key.equals(e.key)))
                     e = e.next;
-                }
 
-                V v = e.value;
-                if (v == null || !oldValue.equals(v))
-                    return false;
-
-                e.value = newValue;
-                count = c; // write-volatile
-                return true;
-                
+                boolean replaced = false;
+                if (e != null && oldValue.equals(e.value)) {
+                    replaced = true;
+                    e.value = newValue;
+                }
+                return replaced;
             } finally {
                 unlock();
             }
@@ -328,24 +396,16 @@
         V replace(K key, int hash, V newValue) {
             lock();
             try {
-                int c = count;
-                HashEntry[] tab = table;
-                int index = hash & (tab.length - 1);
-                HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
-                HashEntry<K,V> e = first;
-                for (;;) {
-                    if (e == null)
-                        return null;
-                    if (e.hash == hash && key.equals(e.key))
-                        break;
+                HashEntry<K,V> e = getFirst(hash);
+                while (e != null && (e.hash != hash || !key.equals(e.key)))
                     e = e.next;
-                }
 
-                V v = e.value;
-                e.value = newValue;
-                count = c; // write-volatile
-                return v;
-                
+                V oldValue = null;
+                if (e != null) {
+                    oldValue = e.value;
+                    e.value = newValue;
+                }
+                return oldValue;
             } finally {
                 unlock();
             }
@@ -356,37 +416,38 @@
             lock();
             try {
                 int c = count;
-                HashEntry[] tab = table;
+                if (c++ > threshold) // ensure capacity
+                    rehash();
+                HashEntry<K,V>[] tab = table;
                 int index = hash & (tab.length - 1);
-                HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
+                HashEntry<K,V> first = tab[index];
+                HashEntry<K,V> e = first;
+                while (e != null && (e.hash != hash || !key.equals(e.key)))
+                    e = e.next;
 
-                for (HashEntry<K,V> e = first; e != null; e = (HashEntry<K,V>) e.next) {
-                    if (e.hash == hash && key.equals(e.key)) {
-                        V oldValue = e.value;
-                        if (!onlyIfAbsent)
-                            e.value = value;
-                        ++modCount;
-                        count = c; // write-volatile
-                        return oldValue;
-                    }
+                V oldValue;
+                if (e != null) {
+                    oldValue = e.value;
+                    if (!onlyIfAbsent)
+                        e.value = value;
                 }
-
-                tab[index] = new HashEntry<K,V>(hash, key, value, first);
-                ++modCount;
-                ++c;
-                count = c; // write-volatile
-                if (c > threshold)
-                    setTable(rehash(tab));
-                return null;
+                else {
+                    oldValue = null;
+                    ++modCount;
+                    tab[index] = new HashEntry<K,V>(key, hash, first, value);
+                    count = c; // write-volatile
+                }
+                return oldValue;
             } finally {
                 unlock();
             }
         }
 
-        HashEntry[] rehash(HashEntry[] oldTable) {
+        void rehash() {
+            HashEntry<K,V>[] oldTable = table;
             int oldCapacity = oldTable.length;
             if (oldCapacity >= MAXIMUM_CAPACITY)
-                return oldTable;
+                return;
 
             /*
              * Reclassify nodes in each list to new Map.  Because we are
@@ -402,12 +463,13 @@
              * right now.
              */
 
-            HashEntry[] newTable = new HashEntry[oldCapacity << 1];
+            HashEntry<K,V>[] newTable = HashEntry.newArray(oldCapacity<<1);
+            threshold = (int)(newTable.length * loadFactor);
             int sizeMask = newTable.length - 1;
             for (int i = 0; i < oldCapacity ; i++) {
                 // We need to guarantee that any existing reads of old Map can
                 //  proceed. So we cannot yet null out each bin.
-                HashEntry<K,V> e = (HashEntry<K,V>)oldTable[i];
+                HashEntry<K,V> e = oldTable[i];
 
                 if (e != null) {
                     HashEntry<K,V> next = e.next;
@@ -435,15 +497,14 @@
                         // Clone all remaining nodes
                         for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
                             int k = p.hash & sizeMask;
-                            newTable[k] = new HashEntry<K,V>(p.hash,
-                                                             p.key,
-                                                             p.value,
-                                                             (HashEntry<K,V>) newTable[k]);
+                            HashEntry<K,V> n = newTable[k];
+                            newTable[k] = new HashEntry<K,V>(p.key, p.hash,
+                                                             n, p.value);
                         }
                     }
                 }
             }
-            return newTable;
+            table = newTable;
         }
 
         /**
@@ -452,33 +513,31 @@
         V remove(Object key, int hash, Object value) {
             lock();
             try {
-                int c = count;
-                HashEntry[] tab = table;
+                int c = count - 1;
+                HashEntry<K,V>[] tab = table;
                 int index = hash & (tab.length - 1);
-                HashEntry<K,V> first = (HashEntry<K,V>)tab[index];
-
+                HashEntry<K,V> first = tab[index];
                 HashEntry<K,V> e = first;
-                for (;;) {
-                    if (e == null)
-                        return null;
-                    if (e.hash == hash && key.equals(e.key))
-                        break;
+                while (e != null && (e.hash != hash || !key.equals(e.key)))
                     e = e.next;
-                }
 
-                V oldValue = e.value;
-                if (value != null && !value.equals(oldValue))
-                    return null;
-
-                // All entries following removed node can stay in list, but
-                // all preceding ones need to be cloned.
-                HashEntry<K,V> newFirst = e.next;
-                for (HashEntry<K,V> p = first; p != e; p = p.next)
-                    newFirst = new HashEntry<K,V>(p.hash, p.key,
-                                                  p.value, newFirst);
-                tab[index] = newFirst;
-                ++modCount;
-                count = c-1; // write-volatile
+                V oldValue = null;
+                if (e != null) {
+                    V v = e.value;
+                    if (value == null || value.equals(v)) {
+                        oldValue = v;
+                        // All entries following removed node can stay
+                        // in list, but all preceding ones need to be
+                        // cloned.
+                        ++modCount;
+                        HashEntry<K,V> newFirst = e.next;
+                        for (HashEntry<K,V> p = first; p != e; p = p.next)
+                            newFirst = new HashEntry<K,V>(p.key, p.hash,
+                                                          newFirst, p.value);
+                        tab[index] = newFirst;
+                        count = c; // write-volatile
+                    }
+                }
                 return oldValue;
             } finally {
                 unlock();
@@ -486,50 +545,37 @@
         }
 
         void clear() {
-            lock();
-            try {
-                HashEntry[] tab = table;
-                for (int i = 0; i < tab.length ; i++)
-                    tab[i] = null;
-                ++modCount;
-                count = 0; // write-volatile
-            } finally {
-                unlock();
+            if (count != 0) {
+                lock();
+                try {
+                    HashEntry<K,V>[] tab = table;
+                    for (int i = 0; i < tab.length ; i++)
+                        tab[i] = null;
+                    ++modCount;
+                    count = 0; // write-volatile
+                } finally {
+                    unlock();
+                }
             }
         }
     }
 
-    /**
-     * ConcurrentHashMap list entry. Note that this is never exported
-     * out as a user-visible Map.Entry
-     */
-    static final class HashEntry<K,V> {
-        final K key;
-        V value;
-        final int hash;
-        final HashEntry<K,V> next;
-
-        HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
-            this.value = value;
-            this.hash = hash;
-            this.key = key;
-            this.next = next;
-        }
-    }
 
 
     /* ---------------- Public operations -------------- */
 
     /**
      * Creates a new, empty map with the specified initial
-     * capacity and the specified load factor.
+     * capacity, load factor and concurrency level.
      *
      * @param initialCapacity the initial capacity. The implementation
      * performs internal sizing to accommodate this many elements.
      * @param loadFactor  the load factor threshold, used to control resizing.
+     * Resizing may be performed when the average number of elements per
+     * bin exceeds this threshold.
      * @param concurrencyLevel the estimated number of concurrently
      * updating threads. The implementation performs internal sizing
-     * to try to accommodate this many threads.  
+     * to try to accommodate this many threads.
      * @throws IllegalArgumentException if the initial capacity is
      * negative or the load factor or concurrencyLevel are
      * nonpositive.
@@ -551,7 +597,7 @@
         }
         segmentShift = 32 - sshift;
         segmentMask = ssize - 1;
-        this.segments = new Segment[ssize];
+        this.segments = Segment.newArray(ssize);
 
         if (initialCapacity > MAXIMUM_CAPACITY)
             initialCapacity = MAXIMUM_CAPACITY;
@@ -567,44 +613,50 @@
     }
 
     /**
-     * Creates a new, empty map with the specified initial
-     * capacity,  and with default load factor and concurrencyLevel.
+     * Creates a new, empty map with the specified initial capacity,
+     * and with default load factor (0.75) and concurrencyLevel (16).
      *
-     * @param initialCapacity The implementation performs internal
-     * sizing to accommodate this many elements.
+     * @param initialCapacity the initial capacity. The implementation
+     * performs internal sizing to accommodate this many elements.
      * @throws IllegalArgumentException if the initial capacity of
      * elements is negative.
      */
     public ConcurrentHashMap(int initialCapacity) {
-        this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
+        this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
     }
 
     /**
-     * Creates a new, empty map with a default initial capacity,
-     * load factor, and concurrencyLevel.
+     * Creates a new, empty map with a default initial capacity (16),
+     * load factor (0.75) and concurrencyLevel (16).
      */
     public ConcurrentHashMap() {
-        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
+        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
     }
 
     /**
-     * Creates a new map with the same mappings as the given map.  The
-     * map is created with a capacity of twice the number of mappings in
-     * the given map or 11 (whichever is greater), and a default load factor.
-     * @param t the map
+     * Creates a new map with the same mappings as the given map.
+     * The map is created with a capacity of 1.5 times the number
+     * of mappings in the given map or 16 (whichever is greater),
+     * and a default load factor (0.75) and concurrencyLevel (16).
+     *
+     * @param m the map
      */
-    public ConcurrentHashMap(Map<? extends K, ? extends V> t) {
-        this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
-                      11),
-             DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
-        putAll(t);
+    public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
+        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
+                      DEFAULT_INITIAL_CAPACITY),
+             DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
+        putAll(m);
     }
 
-    // inherit Map javadoc
+    /**
+     * Returns <tt>true</tt> if this map contains no key-value mappings.
+     *
+     * @return <tt>true</tt> if this map contains no key-value mappings
+     */
     public boolean isEmpty() {
-        final Segment[] segments = this.segments;
+        final Segment<K,V>[] segments = this.segments;
         /*
-         * We need to keep track of per-segment modCounts to avoid ABA
+         * We keep track of per-segment modCounts to avoid ABA
          * problems in which an element in one segment was added and
          * in another removed during traversal, in which case the
          * table was never actually empty at any point. Note the
@@ -617,7 +669,7 @@
         for (int i = 0; i < segments.length; ++i) {
             if (segments[i].count != 0)
                 return false;
-            else 
+            else
                 mcsum += mc[i] = segments[i].modCount;
         }
         // If mcsum happens to be zero, then we know we got a snapshot
@@ -626,25 +678,35 @@
         if (mcsum != 0) {
             for (int i = 0; i < segments.length; ++i) {
                 if (segments[i].count != 0 ||
-                    mc[i] != segments[i].modCount) 
+                    mc[i] != segments[i].modCount)
                     return false;
             }
         }
         return true;
     }
 
-    // inherit Map javadoc
+    /**
+     * Returns the number of key-value mappings in this map.  If the
+     * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
+     * <tt>Integer.MAX_VALUE</tt>.
+     *
+     * @return the number of key-value mappings in this map
+     */
     public int size() {
-        final Segment[] segments = this.segments;
+        final Segment<K,V>[] segments = this.segments;
+        long sum = 0;
+        long check = 0;
         int[] mc = new int[segments.length];
-        for (;;) {
-            long sum = 0;
+        // Try a few times to get accurate count. On failure due to
+        // continuous async changes in table, resort to locking.
+        for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
+            check = 0;
+            sum = 0;
             int mcsum = 0;
             for (int i = 0; i < segments.length; ++i) {
                 sum += segments[i].count;
                 mcsum += mc[i] = segments[i].modCount;
             }
-            int check = 0;
             if (mcsum != 0) {
                 for (int i = 0; i < segments.length; ++i) {
                     check += segments[i].count;
@@ -654,43 +716,51 @@
                     }
                 }
             }
-            if (check == sum) {
-                if (sum > Integer.MAX_VALUE)
-                    return Integer.MAX_VALUE;
-                else
-                    return (int)sum;
-            }
+            if (check == sum)
+                break;
         }
+        if (check != sum) { // Resort to locking all segments
+            sum = 0;
+            for (int i = 0; i < segments.length; ++i)
+                segments[i].lock();
+            for (int i = 0; i < segments.length; ++i)
+                sum += segments[i].count;
+            for (int i = 0; i < segments.length; ++i)
+                segments[i].unlock();
+        }
+        if (sum > Integer.MAX_VALUE)
+            return Integer.MAX_VALUE;
+        else
+            return (int)sum;
     }
 
-
     /**
-     * Returns the value to which the specified key is mapped in this table.
+     * Returns the value to which the specified key is mapped,
+     * or {@code null} if this map contains no mapping for the key.
      *
-     * @param   key   a key in the table.
-     * @return  the value to which the key is mapped in this table;
-     *          <tt>null</tt> if the key is not mapped to any value in
-     *          this table.
-     * @throws  NullPointerException  if the key is
-     *               <tt>null</tt>.
+     * <p>More formally, if this map contains a mapping from a key
+     * {@code k} to a value {@code v} such that {@code key.equals(k)},
+     * then this method returns {@code v}; otherwise it returns
+     * {@code null}.  (There can be at most one such mapping.)
+     *
+     * @throws NullPointerException if the specified key is null
      */
     public V get(Object key) {
-        int hash = hash(key); // throws NullPointerException if key null
+        int hash = hash(key.hashCode());
         return segmentFor(hash).get(key, hash);
     }
 
     /**
      * Tests if the specified object is a key in this table.
      *
-     * @param   key   possible key.
-     * @return  <tt>true</tt> if and only if the specified object
-     *          is a key in this table, as determined by the
-     *          <tt>equals</tt> method; <tt>false</tt> otherwise.
-     * @throws  NullPointerException  if the key is
-     *               <tt>null</tt>.
+     * @param  key   possible key
+     * @return <tt>true</tt> if and only if the specified object
+     *         is a key in this table, as determined by the
+     *         <tt>equals</tt> method; <tt>false</tt> otherwise.
+     * @throws NullPointerException if the specified key is null
      */
     public boolean containsKey(Object key) {
-        int hash = hash(key); // throws NullPointerException if key null
+        int hash = hash(key.hashCode());
         return segmentFor(hash).containsKey(key, hash);
     }
 
@@ -700,18 +770,22 @@
      * traversal of the hash table, and so is much slower than
      * method <tt>containsKey</tt>.
      *
-     * @param value value whose presence in this map is to be tested.
+     * @param value value whose presence in this map is to be tested
      * @return <tt>true</tt> if this map maps one or more keys to the
-     * specified value.
-     * @throws  NullPointerException  if the value is <tt>null</tt>.
+     *         specified value
+     * @throws NullPointerException if the specified value is null
      */
     public boolean containsValue(Object value) {
         if (value == null)
             throw new NullPointerException();
 
-        final Segment[] segments = this.segments;
+        // See explanation of modCount use above
+
+        final Segment<K,V>[] segments = this.segments;
         int[] mc = new int[segments.length];
-        for (;;) {
+
+        // Try a few times without locking
+        for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
             int sum = 0;
             int mcsum = 0;
             for (int i = 0; i < segments.length; ++i) {
@@ -733,265 +807,217 @@
             if (cleanSweep)
                 return false;
         }
+        // Resort to locking all segments
+        for (int i = 0; i < segments.length; ++i)
+            segments[i].lock();
+        boolean found = false;
+        try {
+            for (int i = 0; i < segments.length; ++i) {
+                if (segments[i].containsValue(value)) {
+                    found = true;
+                    break;
+                }
+            }
+        } finally {
+            for (int i = 0; i < segments.length; ++i)
+                segments[i].unlock();
+        }
+        return found;
     }
 
     /**
      * Legacy method testing if some key maps into the specified value
      * in this table.  This method is identical in functionality to
-     * {@link #containsValue}, and  exists solely to ensure
+     * {@link #containsValue}, and exists solely to ensure
      * full compatibility with class {@link java.util.Hashtable},
      * which supported this method prior to introduction of the
      * Java Collections framework.
 
-     * @param      value   a value to search for.
-     * @return     <tt>true</tt> if and only if some key maps to the
-     *             <tt>value</tt> argument in this table as
-     *             determined by the <tt>equals</tt> method;
-     *             <tt>false</tt> otherwise.
-     * @throws  NullPointerException  if the value is <tt>null</tt>.
+     * @param  value a value to search for
+     * @return <tt>true</tt> if and only if some key maps to the
+     *         <tt>value</tt> argument in this table as
+     *         determined by the <tt>equals</tt> method;
+     *         <tt>false</tt> otherwise
+     * @throws NullPointerException if the specified value is null
      */
     public boolean contains(Object value) {
         return containsValue(value);
     }
 
     /**
-     * Maps the specified <tt>key</tt> to the specified
-     * <tt>value</tt> in this table. Neither the key nor the
-     * value can be <tt>null</tt>. 
+     * Maps the specified key to the specified value in this table.
+     * Neither the key nor the value can be null.
      *
      * <p> The value can be retrieved by calling the <tt>get</tt> method
      * with a key that is equal to the original key.
      *
-     * @param      key     the table key.
-     * @param      value   the value.
-     * @return     the previous value of the specified key in this table,
-     *             or <tt>null</tt> if it did not have one.
-     * @throws  NullPointerException  if the key or value is
-     *               <tt>null</tt>.
+     * @param key key with which the specified value is to be associated
+     * @param value value to be associated with the specified key
+     * @return the previous value associated with <tt>key</tt>, or
+     *         <tt>null</tt> if there was no mapping for <tt>key</tt>
+     * @throws NullPointerException if the specified key or value is null
      */
     public V put(K key, V value) {
         if (value == null)
             throw new NullPointerException();
-        int hash = hash(key);
+        int hash = hash(key.hashCode());
         return segmentFor(hash).put(key, hash, value, false);
     }
 
     /**
-     * If the specified key is not already associated
-     * with a value, associate it with the given value.
-     * This is equivalent to
-     * <pre>
-     *   if (!map.containsKey(key)) 
-     *      return map.put(key, value);
-     *   else
-     *      return map.get(key);
-     * </pre>
-     * Except that the action is performed atomically.
-     * @param key key with which the specified value is to be associated.
-     * @param value value to be associated with the specified key.
-     * @return previous value associated with specified key, or <tt>null</tt>
-     *         if there was no mapping for key.  A <tt>null</tt> return can
-     *         also indicate that the map previously associated <tt>null</tt>
-     *         with the specified key, if the implementation supports
-     *         <tt>null</tt> values.
-     *
-     * @throws UnsupportedOperationException if the <tt>put</tt> operation is
-     *            not supported by this map.
-     * @throws ClassCastException if the class of the specified key or value
-     *            prevents it from being stored in this map.
-     * @throws NullPointerException if the specified key or value is
-     *            <tt>null</tt>.
+     * {@inheritDoc}
      *
-     **/
+     * @return the previous value associated with the specified key,
+     *         or <tt>null</tt> if there was no mapping for the key
+     * @throws NullPointerException if the specified key or value is null
+     */
     public V putIfAbsent(K key, V value) {
         if (value == null)
             throw new NullPointerException();
-        int hash = hash(key);
+        int hash = hash(key.hashCode());
         return segmentFor(hash).put(key, hash, value, true);
     }
 
-
     /**
      * Copies all of the mappings from the specified map to this one.
-     *
      * These mappings replace any mappings that this map had for any of the
-     * keys currently in the specified Map.
+     * keys currently in the specified map.
      *
-     * @param t Mappings to be stored in this map.
+     * @param m mappings to be stored in this map
      */
-    public void putAll(Map<? extends K, ? extends V> t) {
-        for (Iterator<? extends Map.Entry<? extends K, ? extends V>> it = (Iterator<? extends Map.Entry<? extends K, ? extends V>>) t.entrySet().iterator(); it.hasNext(); ) {
-            Entry<? extends K, ? extends V> e = it.next();
+    public void putAll(Map<? extends K, ? extends V> m) {
+        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
             put(e.getKey(), e.getValue());
-        }
     }
 
     /**
-     * Removes the key (and its corresponding value) from this
-     * table. This method does nothing if the key is not in the table.
+     * Removes the key (and its corresponding value) from this map.
+     * This method does nothing if the key is not in the map.
      *
-     * @param   key   the key that needs to be removed.
-     * @return  the value to which the key had been mapped in this table,
-     *          or <tt>null</tt> if the key did not have a mapping.
-     * @throws  NullPointerException  if the key is
-     *               <tt>null</tt>.
+     * @param  key the key that needs to be removed
+     * @return the previous value associated with <tt>key</tt>, or
+     *         <tt>null</tt> if there was no mapping for <tt>key</tt>
+     * @throws NullPointerException if the specified key is null
      */
     public V remove(Object key) {
-        int hash = hash(key);
+        int hash = hash(key.hashCode());
         return segmentFor(hash).remove(key, hash, null);
     }
 
     /**
-     * Remove entry for key only if currently mapped to given value.
-     * Acts as
-     * <pre> 
-     *  if (map.get(key).equals(value)) {
-     *     map.remove(key);
-     *     return true;
-     * } else return false;
-     * </pre>
-     * except that the action is performed atomically.
-     * @param key key with which the specified value is associated.
-     * @param value value associated with the specified key.
-     * @return true if the value was removed
-     * @throws NullPointerException if the specified key is
-     *            <tt>null</tt>.
+     * {@inheritDoc}
+     *
+     * @throws NullPointerException if the specified key is null
      */
     public boolean remove(Object key, Object value) {
-        int hash = hash(key);
+        int hash = hash(key.hashCode());
+        if (value == null)
+            return false;
         return segmentFor(hash).remove(key, hash, value) != null;
     }
 
-
     /**
-     * Replace entry for key only if currently mapped to given value.
-     * Acts as
-     * <pre> 
-     *  if (map.get(key).equals(oldValue)) {
-     *     map.put(key, newValue);
-     *     return true;
-     * } else return false;
-     * </pre>
-     * except that the action is performed atomically.
-     * @param key key with which the specified value is associated.
-     * @param oldValue value expected to be associated with the specified key.
-     * @param newValue value to be associated with the specified key.
-     * @return true if the value was replaced
-     * @throws NullPointerException if the specified key or values are
-     * <tt>null</tt>.
+     * {@inheritDoc}
+     *
+     * @throws NullPointerException if any of the arguments are null
      */
     public boolean replace(K key, V oldValue, V newValue) {
         if (oldValue == null || newValue == null)
             throw new NullPointerException();
-        int hash = hash(key);
+        int hash = hash(key.hashCode());
         return segmentFor(hash).replace(key, hash, oldValue, newValue);
     }
 
     /**
-     * Replace entry for key only if currently mapped to some value.
-     * Acts as
-     * <pre> 
-     *  if ((map.containsKey(key)) {
-     *     return map.put(key, value);
-     * } else return null;
-     * </pre>
-     * except that the action is performed atomically.
-     * @param key key with which the specified value is associated.
-     * @param value value to be associated with the specified key.
-     * @return previous value associated with specified key, or <tt>null</tt>
-     *         if there was no mapping for key.  
-     * @throws NullPointerException if the specified key or value is
-     *            <tt>null</tt>.
+     * {@inheritDoc}
+     *
+     * @return the previous value associated with the specified key,
+     *         or <tt>null</tt> if there was no mapping for the key
+     * @throws NullPointerException if the specified key or value is null
      */
     public V replace(K key, V value) {
         if (value == null)
             throw new NullPointerException();
-        int hash = hash(key);
+        int hash = hash(key.hashCode());
         return segmentFor(hash).replace(key, hash, value);
     }
 
-
     /**
-     * Removes all mappings from this map.
+     * Removes all of the mappings from this map.
      */
     public void clear() {
         for (int i = 0; i < segments.length; ++i)
             segments[i].clear();
     }
 
-
     /**
-     * Returns a set view of the keys contained in this map.  The set is
-     * backed by the map, so changes to the map are reflected in the set, and
-     * vice-versa.  The set supports element removal, which removes the
-     * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
-     * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
-     * <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
+     * Returns a {@link Set} view of the keys contained in this map.
+     * The set is backed by the map, so changes to the map are
+     * reflected in the set, and vice-versa.  The set supports element
+     * removal, which removes the corresponding mapping from this map,
+     * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
+     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
+     * operations.  It does not support the <tt>add</tt> or
      * <tt>addAll</tt> operations.
-     * The returned <tt>iterator</tt> is a "weakly consistent" iterator that
-     * will never throw {@link java.util.ConcurrentModificationException},
+     *
+     * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
+     * that will never throw {@link ConcurrentModificationException},
      * and guarantees to traverse elements as they existed upon
      * construction of the iterator, and may (but is not guaranteed to)
      * reflect any modifications subsequent to construction.
-     *
-     * @return a set view of the keys contained in this map.
      */
     public Set<K> keySet() {
         Set<K> ks = keySet;
         return (ks != null) ? ks : (keySet = new KeySet());
     }
 
-
     /**
-     * Returns a collection view of the values contained in this map.  The
-     * collection is backed by the map, so changes to the map are reflected in
-     * the collection, and vice-versa.  The collection supports element
-     * removal, which removes the corresponding mapping from this map, via the
-     * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
-     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
-     * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
-     * The returned <tt>iterator</tt> is a "weakly consistent" iterator that
-     * will never throw {@link java.util.ConcurrentModificationException},
+     * Returns a {@link Collection} view of the values contained in this map.
+     * The collection is backed by the map, so changes to the map are
+     * reflected in the collection, and vice-versa.  The collection
+     * supports element removal, which removes the corresponding
+     * mapping from this map, via the <tt>Iterator.remove</tt>,
+     * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
+     * <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not
+     * support the <tt>add</tt> or <tt>addAll</tt> operations.
+     *
+     * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
+     * that will never throw {@link ConcurrentModificationException},
      * and guarantees to traverse elements as they existed upon
      * construction of the iterator, and may (but is not guaranteed to)
      * reflect any modifications subsequent to construction.
-     *
-     * @return a collection view of the values contained in this map.
      */
     public Collection<V> values() {
         Collection<V> vs = values;
         return (vs != null) ? vs : (values = new Values());
     }
 
-
     /**
-     * Returns a collection view of the mappings contained in this map.  Each
-     * element in the returned collection is a <tt>Map.Entry</tt>.  The
-     * collection is backed by the map, so changes to the map are reflected in
-     * the collection, and vice-versa.  The collection supports element
-     * removal, which removes the corresponding mapping from the map, via the
-     * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
-     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
-     * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
-     * The returned <tt>iterator</tt> is a "weakly consistent" iterator that
-     * will never throw {@link java.util.ConcurrentModificationException},
+     * Returns a {@link Set} view of the mappings contained in this map.
+     * The set is backed by the map, so changes to the map are
+     * reflected in the set, and vice-versa.  The set supports element
+     * removal, which removes the corresponding mapping from the map,
+     * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
+     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
+     * operations.  It does not support the <tt>add</tt> or
+     * <tt>addAll</tt> operations.
+     *
+     * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
+     * that will never throw {@link ConcurrentModificationException},
      * and guarantees to traverse elements as they existed upon
      * construction of the iterator, and may (but is not guaranteed to)
      * reflect any modifications subsequent to construction.
-     *
-     * @return a collection view of the mappings contained in this map.
      */
     public Set<Map.Entry<K,V>> entrySet() {
         Set<Map.Entry<K,V>> es = entrySet;
-        return (es != null) ? es : (entrySet = (Set<Map.Entry<K,V>>) (Set) new EntrySet());
+        return (es != null) ? es : (entrySet = new EntrySet());
     }
 
-
     /**
      * Returns an enumeration of the keys in this table.
      *
-     * @return  an enumeration of the keys in this table.
-     * @see     #keySet
+     * @return an enumeration of the keys in this table
+     * @see #keySet()
      */
     public Enumeration<K> keys() {
         return new KeyIterator();
@@ -1000,8 +1026,8 @@
     /**
      * Returns an enumeration of the values in this table.
      *
-     * @return  an enumeration of the values in this table.
-     * @see     #values
+     * @return an enumeration of the values in this table
+     * @see #values()
      */
     public Enumeration<V> elements() {
         return new ValueIterator();
@@ -1012,7 +1038,7 @@
     abstract class HashIterator {
         int nextSegmentIndex;
         int nextTableIndex;
-        HashEntry[] currentTable;
+        HashEntry<K,V>[] currentTable;
         HashEntry<K, V> nextEntry;
         HashEntry<K, V> lastReturned;
 
@@ -1029,16 +1055,16 @@
                 return;
 
             while (nextTableIndex >= 0) {
-                if ( (nextEntry = (HashEntry<K,V>)currentTable[nextTableIndex--]) != null)
+                if ( (nextEntry = currentTable[nextTableIndex--]) != null)
                     return;
             }
 
             while (nextSegmentIndex >= 0) {
-                Segment<K,V> seg = (Segment<K,V>)segments[nextSegmentIndex--];
+                Segment<K,V> seg = segments[nextSegmentIndex--];
                 if (seg.count != 0) {
                     currentTable = seg.table;
                     for (int j = currentTable.length - 1; j >= 0; --j) {
-                        if ( (nextEntry = (HashEntry<K,V>)currentTable[j]) != null) {
+                        if ( (nextEntry = currentTable[j]) != null) {
                             nextTableIndex = j - 1;
                             return;
                         }
@@ -1065,81 +1091,58 @@
         }
     }
 
-    final class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
-        public K next() { return super.nextEntry().key; }
+    final class KeyIterator
+        extends HashIterator
+        implements Iterator<K>, Enumeration<K>
+    {
+        public K next()        { return super.nextEntry().key; }
         public K nextElement() { return super.nextEntry().key; }
     }
 
-    final class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
-        public V next() { return super.nextEntry().value; }
+    final class ValueIterator
+        extends HashIterator
+        implements Iterator<V>, Enumeration<V>
+    {
+        public V next()        { return super.nextEntry().value; }
         public V nextElement() { return super.nextEntry().value; }
     }
 
-    
-
     /**
-     * Entry iterator. Exported Entry objects must write-through
-     * changes in setValue, even if the nodes have been cloned. So we
-     * cannot return internal HashEntry objects. Instead, the iterator
-     * itself acts as a forwarding pseudo-entry.
+     * Custom Entry class used by EntryIterator.next(), that relays
+     * setValue changes to the underlying map.
      */
-    final class EntryIterator extends HashIterator implements Map.Entry<K,V>, Iterator<Entry<K,V>> {
-        public Map.Entry<K,V> next() {
-            nextEntry();
-            return this;
-        }
-
-        public K getKey() {
-            if (lastReturned == null)
-                throw new IllegalStateException("Entry was removed");
-            return lastReturned.key;
-        }
-
-        public V getValue() {
-            if (lastReturned == null)
-                throw new IllegalStateException("Entry was removed");
-            return ConcurrentHashMap.this.get(lastReturned.key);
+    final class WriteThroughEntry
+        extends SimpleEntry<K,V>
+    {
+        WriteThroughEntry(K k, V v) {
+            super(k,v);
         }
 
+        /**
+         * Set our entry's value and write through to the map. The
+         * value to return is somewhat arbitrary here. Since a
+         * WriteThroughEntry does not necessarily track asynchronous
+         * changes, the most recent "previous" value could be
+         * different from what we return (or could even have been
+         * removed in which case the put will re-establish). We do not
+         * and cannot guarantee more.
+         */
         public V setValue(V value) {
-            if (lastReturned == null)
-                throw new IllegalStateException("Entry was removed");
-            return ConcurrentHashMap.this.put(lastReturned.key, value);
-        }
-
-        public boolean equals(Object o) {
-            // If not acting as entry, just use default.
-            if (lastReturned == null)
-                return super.equals(o);
-            if (!(o instanceof Map.Entry))
-                return false;
-            Map.Entry e = (Map.Entry)o;
-            return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
-        }
-
-        public int hashCode() {
-            // If not acting as entry, just use default.
-            if (lastReturned == null)
-                return super.hashCode();
-
-            Object k = getKey();
-            Object v = getValue();
-            return ((k == null) ? 0 : k.hashCode()) ^
-                   ((v == null) ? 0 : v.hashCode());
-        }
-
-        public String toString() {
-            // If not acting as entry, just use default.
-            if (lastReturned == null)
-                return super.toString();
-            else
-                return getKey() + "=" + getValue();
+            if (value == null) throw new NullPointerException();
+            V v = super.setValue(value);
+            ConcurrentHashMap.this.put(getKey(), value);
+            return v;
         }
+    }
 
-        boolean eq(Object o1, Object o2) {
-            return (o1 == null ? o2 == null : o1.equals(o2));
+    final class EntryIterator
+        extends HashIterator
+        implements Iterator<Entry<K,V>>
+    {
+        public Map.Entry<K,V> next() {
+            HashEntry<K,V> e = super.nextEntry();
+            return new WriteThroughEntry(e.key, e.value);
         }
-
     }
 
     final class KeySet extends AbstractSet<K> {
@@ -1149,6 +1152,9 @@
         public int size() {
             return ConcurrentHashMap.this.size();
         }
+        public boolean isEmpty() {
+            return ConcurrentHashMap.this.isEmpty();
+        }
         public boolean contains(Object o) {
             return ConcurrentHashMap.this.containsKey(o);
         }
@@ -1167,6 +1173,9 @@
         public int size() {
             return ConcurrentHashMap.this.size();
         }
+        public boolean isEmpty() {
+            return ConcurrentHashMap.this.isEmpty();
+        }
         public boolean contains(Object o) {
             return ConcurrentHashMap.this.containsValue(o);
         }
@@ -1182,44 +1191,32 @@
         public boolean contains(Object o) {
             if (!(o instanceof Map.Entry))
                 return false;
-            Map.Entry<K,V> e = (Map.Entry<K,V>)o;
+            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
             V v = ConcurrentHashMap.this.get(e.getKey());
             return v != null && v.equals(e.getValue());
         }
         public boolean remove(Object o) {
             if (!(o instanceof Map.Entry))
                 return false;
-            Map.Entry<K,V> e = (Map.Entry<K,V>)o;
+            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
             return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
         }
         public int size() {
             return ConcurrentHashMap.this.size();
         }
+        public boolean isEmpty() {
+            return ConcurrentHashMap.this.isEmpty();
+        }
         public void clear() {
             ConcurrentHashMap.this.clear();
         }
-        public Object[] toArray() {
-            // Since we don't ordinarily have distinct Entry objects, we
-            // must pack elements using exportable SimpleEntry
-            Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
-            for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
-                c.add(new SimpleEntry<K,V>(i.next()));
-            return c.toArray();
-        }
-        public <T> T[] toArray(T[] a) {
-            Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
-            for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
-                c.add(new SimpleEntry<K,V>(i.next()));
-            return c.toArray(a);
-        }
-
     }
 
     /**
      * This duplicates java.util.AbstractMap.SimpleEntry until this class
      * is made accessible.
      */
-    static final class SimpleEntry<K,V> implements Entry<K,V> {
+    static class SimpleEntry<K,V> implements Entry<K,V> {
         K key;
         V value;
 
@@ -1256,7 +1253,7 @@
 
         public int hashCode() {
             return ((key   == null)   ? 0 :   key.hashCode()) ^
-                   ((value == null)   ? 0 : value.hashCode());
+                    ((value == null)   ? 0 : value.hashCode());
         }
 
         public String toString() {
@@ -1268,12 +1265,11 @@
         }
     }
 
-    /* ---------------- Serialization Support -------------- */
+   /* ---------------- Serialization Support -------------- */
 
     /**
-     * Save the state of the <tt>ConcurrentHashMap</tt>
-     * instance to a stream (i.e.,
-     * serialize it).
+     * Save the state of the <tt>ConcurrentHashMap</tt> instance to a
+     * stream (i.e., serialize it).
      * @param s the stream
      * @serialData
      * the key (Object) and value (Object)
@@ -1284,12 +1280,12 @@
         s.defaultWriteObject();
 
         for (int k = 0; k < segments.length; ++k) {
-            Segment<K,V> seg = (Segment<K,V>)segments[k];
+            Segment<K,V> seg = segments[k];
             seg.lock();
             try {
-                HashEntry[] tab = seg.table;
+                HashEntry<K,V>[] tab = seg.table;
                 for (int i = 0; i < tab.length; ++i) {
-                    for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i]; e != null; e = e.next) {
+                    for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
                         s.writeObject(e.key);
                         s.writeObject(e.value);
                     }
@@ -1303,9 +1299,8 @@
     }
 
     /**
-     * Reconstitute the <tt>ConcurrentHashMap</tt>
-     * instance from a stream (i.e.,
-     * deserialize it).
+     * Reconstitute the <tt>ConcurrentHashMap</tt> instance from a
+     * stream (i.e., deserialize it).
      * @param s the stream
      */
     private void readObject(java.io.ObjectInputStream s)
@@ -1327,4 +1322,3 @@
         }
     }
 }
-



Mime
View raw message