Return-Path: Delivered-To: apmail-harmony-commits-archive@www.apache.org Received: (qmail 54132 invoked from network); 28 Jul 2009 09:30:11 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.3) by minotaur.apache.org with SMTP; 28 Jul 2009 09:30:11 -0000 Received: (qmail 61576 invoked by uid 500); 28 Jul 2009 09:31:28 -0000 Delivered-To: apmail-harmony-commits-archive@harmony.apache.org Received: (qmail 61532 invoked by uid 500); 28 Jul 2009 09:31:28 -0000 Mailing-List: contact commits-help@harmony.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@harmony.apache.org Delivered-To: mailing list commits@harmony.apache.org Received: (qmail 61523 invoked by uid 99); 28 Jul 2009 09:31:28 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 28 Jul 2009 09:31:28 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=10.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 28 Jul 2009 09:31:20 +0000 Received: by eris.apache.org (Postfix, from userid 65534) id 566EB23889C1; Tue, 28 Jul 2009 09:30:59 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit 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 -0000 To: commits@harmony.apache.org From: hindessm@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20090728093059.566EB23889C1@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org 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 not throw - * {@link ConcurrentModificationException}. However, iterators are - * designed to be used by only one thread at a time. + * They do not throw {@link ConcurrentModificationException}. + * However, iterators are designed to be used by only one thread at a time. * *

The allowed concurrency among update operations is guided by * the optional concurrencyLevel constructor argument - * (default 16), which is used as a hint for internal sizing. The + * (default 16), 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. * - *

This class implements all of the optional methods - * of the {@link Map} and {@link Iterator} interfaces. + *

This class and its views and iterators implement all of the + * optional methods of the {@link Map} and {@link Iterator} + * interfaces. * - *

Like {@link java.util.Hashtable} but unlike {@link - * java.util.HashMap}, this class does NOT allow null to be - * used as a key or value. + *

Like {@link Hashtable} but unlike {@link HashMap}, this class + * does not allow null to be used as a key or value. * *

This class is a member of the - * + * * Java Collections Framework. * * @since 1.5 * @author Doug Lea * @param the type of keys maintained by this map - * @param the type of mapped values + * @param the type of mapped values */ public class ConcurrentHashMap extends AbstractMap implements ConcurrentMap, 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[] segments; transient Set keySet; transient Set> 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 segmentFor(int hash) { - return (Segment) 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 { + final K key; + final int hash; + volatile V value; + final HashEntry next; + + HashEntry(K key, int hash, HashEntry next, V value) { + this.key = key; + this.hash = hash; + this.next = next; + this.value = value; + } + + @SuppressWarnings("unchecked") + static final HashEntry[] 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 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 (int)(capacity * + * loadFactor).) */ transient int threshold; /** - * The per-segment table + * The per-segment table. */ - transient HashEntry[] table; + transient volatile HashEntry[] 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.newArray(initialCapacity)); + } + + @SuppressWarnings("unchecked") + static final Segment[] 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[] newTable) { threshold = (int)(newTable.length * loadFactor); - count = count; // write-volatile + table = newTable; + } + + /** + * Returns properly casted first entry of bin for given hash. + */ + HashEntry getFirst(int hash) { + HashEntry[] 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 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 e = (HashEntry) tab[index]; + HashEntry 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 e = (HashEntry) tab[index]; + HashEntry 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[] tab = table; int len = tab.length; - for (int i = 0 ; i < len; i++) - for (HashEntry e = (HashEntry)tab[i] ; e != null ; e = e.next) - if (value.equals(e.value)) + for (int i = 0 ; i < len; i++) { + for (HashEntry 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 first = (HashEntry) tab[index]; - HashEntry e = first; - for (;;) { - if (e == null) - return false; - if (e.hash == hash && key.equals(e.key)) - break; + HashEntry 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 first = (HashEntry) tab[index]; - HashEntry e = first; - for (;;) { - if (e == null) - return null; - if (e.hash == hash && key.equals(e.key)) - break; + HashEntry 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[] tab = table; int index = hash & (tab.length - 1); - HashEntry first = (HashEntry) tab[index]; + HashEntry first = tab[index]; + HashEntry e = first; + while (e != null && (e.hash != hash || !key.equals(e.key))) + e = e.next; - for (HashEntry e = first; e != null; e = (HashEntry) 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(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(key, hash, first, value); + count = c; // write-volatile + } + return oldValue; } finally { unlock(); } } - HashEntry[] rehash(HashEntry[] oldTable) { + void rehash() { + HashEntry[] 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[] 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 e = (HashEntry)oldTable[i]; + HashEntry e = oldTable[i]; if (e != null) { HashEntry next = e.next; @@ -435,15 +497,14 @@ // Clone all remaining nodes for (HashEntry p = e; p != lastRun; p = p.next) { int k = p.hash & sizeMask; - newTable[k] = new HashEntry(p.hash, - p.key, - p.value, - (HashEntry) newTable[k]); + HashEntry n = newTable[k]; + newTable[k] = new HashEntry(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[] tab = table; int index = hash & (tab.length - 1); - HashEntry first = (HashEntry)tab[index]; - + HashEntry first = tab[index]; HashEntry 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 newFirst = e.next; - for (HashEntry p = first; p != e; p = p.next) - newFirst = new HashEntry(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 newFirst = e.next; + for (HashEntry p = first; p != e; p = p.next) + newFirst = new HashEntry(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[] 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 { - final K key; - V value; - final int hash; - final HashEntry next; - - HashEntry(int hash, K key, V value, HashEntry 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 t) { - this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, - 11), - DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS); - putAll(t); + public ConcurrentHashMap(Map 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 true if this map contains no key-value mappings. + * + * @return true if this map contains no key-value mappings + */ public boolean isEmpty() { - final Segment[] segments = this.segments; + final Segment[] 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 Integer.MAX_VALUE elements, returns + * Integer.MAX_VALUE. + * + * @return the number of key-value mappings in this map + */ public int size() { - final Segment[] segments = this.segments; + final Segment[] 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; - * null if the key is not mapped to any value in - * this table. - * @throws NullPointerException if the key is - * null. + *

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 true if and only if the specified object - * is a key in this table, as determined by the - * equals method; false otherwise. - * @throws NullPointerException if the key is - * null. + * @param key possible key + * @return true if and only if the specified object + * is a key in this table, as determined by the + * equals method; false 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 containsKey. * - * @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 true if this map maps one or more keys to the - * specified value. - * @throws NullPointerException if the value is null. + * 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[] 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 true if and only if some key maps to the - * value argument in this table as - * determined by the equals method; - * false otherwise. - * @throws NullPointerException if the value is null. + * @param value a value to search for + * @return true if and only if some key maps to the + * value argument in this table as + * determined by the equals method; + * false otherwise + * @throws NullPointerException if the specified value is null */ public boolean contains(Object value) { return containsValue(value); } /** - * Maps the specified key to the specified - * value in this table. Neither the key nor the - * value can be null. + * Maps the specified key to the specified value in this table. + * Neither the key nor the value can be null. * *

The value can be retrieved by calling the get 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 null if it did not have one. - * @throws NullPointerException if the key or value is - * null. + * @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 key, or + * null if there was no mapping for key + * @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 - *

-     *   if (!map.containsKey(key)) 
-     *      return map.put(key, value);
-     *   else
-     *      return map.get(key);
-     *

- * 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 null - * if there was no mapping for key. A null return can - * also indicate that the map previously associated null - * with the specified key, if the implementation supports - * null values. - * - * @throws UnsupportedOperationException if the put 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 - * null. + * {@inheritDoc} * - **/ + * @return the previous value associated with the specified key, + * or null 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 t) { - for (Iterator> it = (Iterator>) t.entrySet().iterator(); it.hasNext(); ) { - Entry e = it.next(); + public void putAll(Map m) { + for (Map.Entry 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 null if the key did not have a mapping. - * @throws NullPointerException if the key is - * null. + * @param key the key that needs to be removed + * @return the previous value associated with key, or + * null if there was no mapping for key + * @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 - *

 
-     *  if (map.get(key).equals(value)) {
-     *     map.remove(key);
-     *     return true;
-     * } else return false;
-     *

- * 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 - * null. + * {@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 - *

 
-     *  if (map.get(key).equals(oldValue)) {
-     *     map.put(key, newValue);
-     *     return true;
-     * } else return false;
-     *

- * 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 - * null. + * {@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 - *

 
-     *  if ((map.containsKey(key)) {
-     *     return map.put(key, value);
-     * } else return null;
-     *

- * 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 null - * if there was no mapping for key. - * @throws NullPointerException if the specified key or value is - * null. + * {@inheritDoc} + * + * @return the previous value associated with the specified key, + * or null 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 Iterator.remove, - * Set.remove, removeAll, retainAll, and - * clear operations. It does not support the add 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 Iterator.remove, Set.remove, + * removeAll, retainAll, and clear + * operations. It does not support the add or * addAll operations. - * The returned iterator is a "weakly consistent" iterator that - * will never throw {@link java.util.ConcurrentModificationException}, + * + *

The view's iterator 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> entrySet() { Set> es = entrySet; - return (es != null) ? es : (entrySet = (Set>) (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 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 elements() { return new ValueIterator(); @@ -1012,7 +1038,7 @@ abstract class HashIterator { int nextSegmentIndex; int nextTableIndex; - HashEntry[] currentTable; + HashEntry[] currentTable; HashEntry nextEntry; HashEntry lastReturned; @@ -1029,16 +1055,16 @@ return; while (nextTableIndex >= 0) { - if ( (nextEntry = (HashEntry)currentTable[nextTableIndex--]) != null) + if ( (nextEntry = currentTable[nextTableIndex--]) != null) return; } while (nextSegmentIndex >= 0) { - Segment seg = (Segment)segments[nextSegmentIndex--]; + Segment seg = segments[nextSegmentIndex--]; if (seg.count != 0) { currentTable = seg.table; for (int j = currentTable.length - 1; j >= 0; --j) { - if ( (nextEntry = (HashEntry)currentTable[j]) != null) { + if ( (nextEntry = currentTable[j]) != null) { nextTableIndex = j - 1; return; } @@ -1065,81 +1091,58 @@ } } - final class KeyIterator extends HashIterator implements Iterator, Enumeration { - public K next() { return super.nextEntry().key; } + final class KeyIterator + extends HashIterator + implements Iterator, Enumeration + { + public K next() { return super.nextEntry().key; } public K nextElement() { return super.nextEntry().key; } } - final class ValueIterator extends HashIterator implements Iterator, Enumeration { - public V next() { return super.nextEntry().value; } + final class ValueIterator + extends HashIterator + implements Iterator, Enumeration + { + 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, Iterator> { - public Map.Entry 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 + { + 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> + { + public Map.Entry next() { + HashEntry e = super.nextEntry(); + return new WriteThroughEntry(e.key, e.value); } - } final class KeySet extends AbstractSet { @@ -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 e = (Map.Entry)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 e = (Map.Entry)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> c = new ArrayList>(size()); - for (Iterator> i = iterator(); i.hasNext(); ) - c.add(new SimpleEntry(i.next())); - return c.toArray(); - } - public T[] toArray(T[] a) { - Collection> c = new ArrayList>(size()); - for (Iterator> i = iterator(); i.hasNext(); ) - c.add(new SimpleEntry(i.next())); - return c.toArray(a); - } - } /** * This duplicates java.util.AbstractMap.SimpleEntry until this class * is made accessible. */ - static final class SimpleEntry implements Entry { + static class SimpleEntry implements Entry { 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 ConcurrentHashMap - * instance to a stream (i.e., - * serialize it). + * Save the state of the ConcurrentHashMap 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 seg = (Segment)segments[k]; + Segment seg = segments[k]; seg.lock(); try { - HashEntry[] tab = seg.table; + HashEntry[] tab = seg.table; for (int i = 0; i < tab.length; ++i) { - for (HashEntry e = (HashEntry)tab[i]; e != null; e = e.next) { + for (HashEntry e = tab[i]; e != null; e = e.next) { s.writeObject(e.key); s.writeObject(e.value); } @@ -1303,9 +1299,8 @@ } /** - * Reconstitute the ConcurrentHashMap - * instance from a stream (i.e., - * deserialize it). + * Reconstitute the ConcurrentHashMap instance from a + * stream (i.e., deserialize it). * @param s the stream */ private void readObject(java.io.ObjectInputStream s) @@ -1327,4 +1322,3 @@ } } } -