You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by hi...@apache.org on 2009/07/28 11:30:48 UTC
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...
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 @@
}
}
}
-