diff -r 588d5bf7a560 -r aa70afac4eca rt/emul/compact/src/main/java/java/util/concurrent/ConcurrentHashMap.java
--- a/rt/emul/compact/src/main/java/java/util/concurrent/ConcurrentHashMap.java Thu Oct 03 15:40:35 2013 +0200
+++ b/rt/emul/compact/src/main/java/java/util/concurrent/ConcurrentHashMap.java Fri Oct 04 10:52:01 2013 +0200
@@ -32,9 +32,8 @@
* Expert Group and released to the public domain, as explained at
* http://creativecommons.org/publicdomain/zero/1.0/
*/
+package java.util.concurrent;
-package java.util.concurrent;
-import java.util.concurrent.locks.*;
import java.util.*;
import java.io.Serializable;
import java.io.IOException;
@@ -42,55 +41,57 @@
import java.io.ObjectOutputStream;
/**
- * A hash table supporting full concurrency of retrievals and
- * adjustable expected concurrency for updates. This class obeys the
- * same functional specification as {@link java.util.Hashtable}, and
- * includes versions of methods corresponding to each method of
- * Hashtable. However, even though all operations are
- * thread-safe, retrieval operations do not entail locking,
- * and there is not any support for locking the entire table
- * in a way that prevents all access. This class is fully
- * interoperable with Hashtable in programs that rely on its
- * thread safety but not on its synchronization details.
+ * A hash table supporting full concurrency of retrievals and adjustable
+ * expected concurrency for updates. This class obeys the same functional
+ * specification as {@link java.util.Hashtable}, and includes versions of
+ * methods corresponding to each method of
+ * Hashtable. However, even though all operations are thread-safe,
+ * retrieval operations do not entail locking, and there is
+ * not any support for locking the entire table in a way that prevents
+ * all access. This class is fully interoperable with Hashtable in
+ * programs that rely on its thread safety but not on its synchronization
+ * details.
*
- *
Retrieval operations (including get) generally do not
- * block, so may overlap with update operations (including
- * put and remove). Retrievals reflect the results
- * of the most recently completed update operations holding
- * upon their onset. For aggregate operations such as putAll
- * and clear, concurrent retrievals may reflect insertion or
- * 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.
+ *
+ * Retrieval operations (including get) generally do not block, so may
+ * overlap with update operations (including
+ * put and remove). Retrievals reflect the results of the most
+ * recently completed update operations holding upon their onset. For
+ * aggregate operations such as putAll
+ * and clear, concurrent retrievals may reflect insertion or 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.
*
- *
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
- * 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
- * vary. Ideally, you should choose a value to accommodate as many
- * threads as will ever concurrently modify the table. Using a
- * significantly higher value than you need can waste space and time,
- * 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. 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
+ *
+ * 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 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 vary. Ideally, you should choose a value to accommodate as
+ * many threads as will ever concurrently modify the table. Using a
+ * significantly higher value than you need can waste space and time, 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. 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 and its views and iterators implement 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 Hashtable} but unlike {@link 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
+ *
+ * This class is a member of the
*
* Java Collections Framework.
*
@@ -100,34 +101,9 @@
* @param the type of mapped values
*/
public class ConcurrentHashMap extends AbstractMap
- implements ConcurrentMap, Serializable {
+ implements ConcurrentMap, Serializable {
+
private static final long serialVersionUID = 7249069246763182397L;
-
- /*
- * The basic strategy is to subdivide the table among Segments,
- * each of which itself is a concurrently readable hash table. To
- * reduce footprint, all but one segments are constructed only
- * when first needed (see ensureSegment). To maintain visibility
- * in the presence of lazy construction, accesses to segments as
- * well as elements of segment's table must use volatile access,
- * which is done via Unsafe within methods segmentAt etc
- * below. These provide the functionality of AtomicReferenceArrays
- * but reduce the levels of indirection. Additionally,
- * volatile-writes of table elements and entry "next" fields
- * within locked operations use the cheaper "lazySet" forms of
- * writes (via putOrderedObject) because these writes are always
- * followed by lock releases that maintain sequential consistency
- * of table updates.
- *
- * Historical note: The previous version of this class relied
- * heavily on "final" fields, which avoided some volatile reads at
- * the expense of a large initial footprint. Some remnants of
- * that design (including forced construction of segment 0) exist
- * to ensure serialization compatibility.
- */
-
- /* ---------------- Constants -------------- */
-
/**
* The default initial capacity for this table,
* used when not otherwise specified in a constructor.
@@ -146,574 +122,8 @@
*/
static final int DEFAULT_CONCURRENCY_LEVEL = 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;
+ private final Map delegate;
- /**
- * The minimum capacity for per-segment tables. Must be a power
- * of two, at least two to avoid immediate resizing on next use
- * after lazy construction.
- */
- static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
-
- /**
- * The maximum number of segments to allow; used to bound
- * constructor arguments. Must be power of two less than 1 << 24.
- */
- 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;
-
- transient Set keySet;
- transient Set> entrySet;
- transient Collection values;
-
- /**
- * ConcurrentHashMap list entry. Note that this is never exported
- * out as a user-visible Map.Entry.
- */
- static final class HashEntry {
- final int hash;
- final K key;
- volatile V value;
- volatile HashEntry next;
-
- HashEntry(int hash, K key, V value, HashEntry next) {
- this.hash = hash;
- this.key = key;
- this.value = value;
- this.next = next;
- }
-
- /**
- * Sets next field with volatile write semantics. (See above
- * about use of putOrderedObject.)
- */
- final void setNext(HashEntry n) {
- UNSAFE.putOrderedObject(this, nextOffset, n);
- }
-
- // Unsafe mechanics
- static final sun.misc.Unsafe UNSAFE;
- static final long nextOffset;
- static {
- try {
- UNSAFE = sun.misc.Unsafe.getUnsafe();
- Class k = HashEntry.class;
- nextOffset = UNSAFE.objectFieldOffset
- (k.getDeclaredField("next"));
- } catch (Exception e) {
- throw new Error(e);
- }
- }
- }
-
- /**
- * Gets the ith element of given table (if nonnull) with volatile
- * read semantics. Note: This is manually integrated into a few
- * performance-sensitive methods to reduce call overhead.
- */
- @SuppressWarnings("unchecked")
- static final HashEntry entryAt(HashEntry[] tab, int i) {
- return (tab == null) ? null :
- (HashEntry) UNSAFE.getObjectVolatile
- (tab, ((long)i << TSHIFT) + TBASE);
- }
-
- /**
- * Sets the ith element of given table, with volatile write
- * semantics. (See above about use of putOrderedObject.)
- */
- static final void setEntryAt(HashEntry[] tab, int i,
- HashEntry e) {
- UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e);
- }
-
- /**
- * 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);
- }
-
- /**
- * 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
- * kept in a consistent state, so can be read (via volatile
- * reads of segments and tables) without locking. This
- * requires replicating nodes when necessary during table
- * resizing, so the old lists can be traversed by readers
- * still using old version of table.
- *
- * This class defines only mutative methods requiring locking.
- * Except as noted, the methods of this class perform the
- * per-segment versions of ConcurrentHashMap methods. (Other
- * methods are integrated directly into ConcurrentHashMap
- * methods.) These mutative methods use a form of controlled
- * spinning on contention via methods scanAndLock and
- * scanAndLockForPut. These intersperse tryLocks with
- * traversals to locate nodes. The main benefit is to absorb
- * cache misses (which are very common for hash tables) while
- * obtaining locks so that traversal is faster once
- * acquired. We do not actually use the found nodes since they
- * must be re-acquired under lock anyway to ensure sequential
- * consistency of updates (and in any case may be undetectably
- * stale), but they will normally be much faster to re-locate.
- * Also, scanAndLockForPut speculatively creates a fresh node
- * to use in put if no node is found.
- */
-
- private static final long serialVersionUID = 2249069246763182397L;
-
- /**
- * The maximum number of times to tryLock in a prescan before
- * possibly blocking on acquire in preparation for a locked
- * segment operation. On multiprocessors, using a bounded
- * number of retries maintains cache acquired while locating
- * nodes.
- */
- static final int MAX_SCAN_RETRIES =
- Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
-
- /**
- * The per-segment table. Elements are accessed via
- * entryAt/setEntryAt providing volatile semantics.
- */
- transient volatile HashEntry[] table;
-
- /**
- * The number of elements. Accessed only either within locks
- * or among other volatile reads that maintain visibility.
- */
- transient int count;
-
- /**
- * The total number of mutative operations in this segment.
- * Even though this may overflows 32 bits, it provides
- * sufficient accuracy for stability checks in CHM isEmpty()
- * and size() methods. Accessed only either within locks or
- * among other volatile reads that maintain visibility.
- */
- transient int modCount;
-
- /**
- * The table is rehashed when its size exceeds this threshold.
- * (The value of this field is always (int)(capacity *
- * loadFactor).)
- */
- transient int threshold;
-
- /**
- * The load factor for the hash table. Even though this value
- * is same for all segments, it is replicated to avoid needing
- * links to outer object.
- * @serial
- */
- final float loadFactor;
-
- Segment(float lf, int threshold, HashEntry[] tab) {
- this.loadFactor = lf;
- this.threshold = threshold;
- this.table = tab;
- }
-
- final V put(K key, int hash, V value, boolean onlyIfAbsent) {
- HashEntry node = tryLock() ? null :
- scanAndLockForPut(key, hash, value);
- V oldValue;
- try {
- HashEntry[] tab = table;
- int index = (tab.length - 1) & hash;
- HashEntry first = entryAt(tab, index);
- for (HashEntry e = first;;) {
- if (e != null) {
- K k;
- if ((k = e.key) == key ||
- (e.hash == hash && key.equals(k))) {
- oldValue = e.value;
- if (!onlyIfAbsent) {
- e.value = value;
- ++modCount;
- }
- break;
- }
- e = e.next;
- }
- else {
- if (node != null)
- node.setNext(first);
- else
- node = new HashEntry(hash, key, value, first);
- int c = count + 1;
- if (c > threshold && tab.length < MAXIMUM_CAPACITY)
- rehash(node);
- else
- setEntryAt(tab, index, node);
- ++modCount;
- count = c;
- oldValue = null;
- break;
- }
- }
- } finally {
- unlock();
- }
- return oldValue;
- }
-
- /**
- * Doubles size of table and repacks entries, also adding the
- * given node to new table
- */
- @SuppressWarnings("unchecked")
- private void rehash(HashEntry node) {
- /*
- * Reclassify nodes in each list to new table. Because we
- * are using power-of-two expansion, the elements from
- * each bin must either stay at same index, or move with a
- * power of two offset. We eliminate unnecessary node
- * creation by catching cases where old nodes can be
- * reused because their next fields won't change.
- * Statistically, at the default threshold, only about
- * one-sixth of them need cloning when a table
- * doubles. The nodes they replace will be garbage
- * collectable as soon as they are no longer referenced by
- * any reader thread that may be in the midst of
- * concurrently traversing table. Entry accesses use plain
- * array indexing because they are followed by volatile
- * table write.
- */
- HashEntry[] oldTable = table;
- int oldCapacity = oldTable.length;
- int newCapacity = oldCapacity << 1;
- threshold = (int)(newCapacity * loadFactor);
- HashEntry[] newTable =
- (HashEntry[]) new HashEntry[newCapacity];
- int sizeMask = newCapacity - 1;
- for (int i = 0; i < oldCapacity ; i++) {
- HashEntry e = oldTable[i];
- if (e != null) {
- HashEntry next = e.next;
- int idx = e.hash & sizeMask;
- if (next == null) // Single node on list
- newTable[idx] = e;
- else { // Reuse consecutive sequence at same slot
- HashEntry lastRun = e;
- int lastIdx = idx;
- for (HashEntry last = next;
- last != null;
- last = last.next) {
- int k = last.hash & sizeMask;
- if (k != lastIdx) {
- lastIdx = k;
- lastRun = last;
- }
- }
- newTable[lastIdx] = lastRun;
- // Clone remaining nodes
- for (HashEntry p = e; p != lastRun; p = p.next) {
- V v = p.value;
- int h = p.hash;
- int k = h & sizeMask;
- HashEntry n = newTable[k];
- newTable[k] = new HashEntry(h, p.key, v, n);
- }
- }
- }
- }
- int nodeIndex = node.hash & sizeMask; // add the new node
- node.setNext(newTable[nodeIndex]);
- newTable[nodeIndex] = node;
- table = newTable;
- }
-
- /**
- * Scans for a node containing given key while trying to
- * acquire lock, creating and returning one if not found. Upon
- * return, guarantees that lock is held. UNlike in most
- * methods, calls to method equals are not screened: Since
- * traversal speed doesn't matter, we might as well help warm
- * up the associated code and accesses as well.
- *
- * @return a new node if key not found, else null
- */
- private HashEntry scanAndLockForPut(K key, int hash, V value) {
- HashEntry first = entryForHash(this, hash);
- HashEntry e = first;
- HashEntry node = null;
- int retries = -1; // negative while locating node
- while (!tryLock()) {
- HashEntry f; // to recheck first below
- if (retries < 0) {
- if (e == null) {
- if (node == null) // speculatively create node
- node = new HashEntry(hash, key, value, null);
- retries = 0;
- }
- else if (key.equals(e.key))
- retries = 0;
- else
- e = e.next;
- }
- else if (++retries > MAX_SCAN_RETRIES) {
- lock();
- break;
- }
- else if ((retries & 1) == 0 &&
- (f = entryForHash(this, hash)) != first) {
- e = first = f; // re-traverse if entry changed
- retries = -1;
- }
- }
- return node;
- }
-
- /**
- * Scans for a node containing the given key while trying to
- * acquire lock for a remove or replace operation. Upon
- * return, guarantees that lock is held. Note that we must
- * lock even if the key is not found, to ensure sequential
- * consistency of updates.
- */
- private void scanAndLock(Object key, int hash) {
- // similar to but simpler than scanAndLockForPut
- HashEntry first = entryForHash(this, hash);
- HashEntry e = first;
- int retries = -1;
- while (!tryLock()) {
- HashEntry f;
- if (retries < 0) {
- if (e == null || key.equals(e.key))
- retries = 0;
- else
- e = e.next;
- }
- else if (++retries > MAX_SCAN_RETRIES) {
- lock();
- break;
- }
- else if ((retries & 1) == 0 &&
- (f = entryForHash(this, hash)) != first) {
- e = first = f;
- retries = -1;
- }
- }
- }
-
- /**
- * Remove; match on key only if value null, else match both.
- */
- final V remove(Object key, int hash, Object value) {
- if (!tryLock())
- scanAndLock(key, hash);
- V oldValue = null;
- try {
- HashEntry[] tab = table;
- int index = (tab.length - 1) & hash;
- HashEntry e = entryAt(tab, index);
- HashEntry pred = null;
- while (e != null) {
- K k;
- HashEntry next = e.next;
- if ((k = e.key) == key ||
- (e.hash == hash && key.equals(k))) {
- V v = e.value;
- if (value == null || value == v || value.equals(v)) {
- if (pred == null)
- setEntryAt(tab, index, next);
- else
- pred.setNext(next);
- ++modCount;
- --count;
- oldValue = v;
- }
- break;
- }
- pred = e;
- e = next;
- }
- } finally {
- unlock();
- }
- return oldValue;
- }
-
- final boolean replace(K key, int hash, V oldValue, V newValue) {
- if (!tryLock())
- scanAndLock(key, hash);
- boolean replaced = false;
- try {
- HashEntry e;
- for (e = entryForHash(this, hash); e != null; e = e.next) {
- K k;
- if ((k = e.key) == key ||
- (e.hash == hash && key.equals(k))) {
- if (oldValue.equals(e.value)) {
- e.value = newValue;
- ++modCount;
- replaced = true;
- }
- break;
- }
- }
- } finally {
- unlock();
- }
- return replaced;
- }
-
- final V replace(K key, int hash, V value) {
- if (!tryLock())
- scanAndLock(key, hash);
- V oldValue = null;
- try {
- HashEntry e;
- for (e = entryForHash(this, hash); e != null; e = e.next) {
- K k;
- if ((k = e.key) == key ||
- (e.hash == hash && key.equals(k))) {
- oldValue = e.value;
- e.value = value;
- ++modCount;
- break;
- }
- }
- } finally {
- unlock();
- }
- return oldValue;
- }
-
- final void clear() {
- lock();
- try {
- HashEntry[] tab = table;
- for (int i = 0; i < tab.length ; i++)
- setEntryAt(tab, i, null);
- ++modCount;
- count = 0;
- } finally {
- unlock();
- }
- }
- }
-
- // Accessing segments
-
- /**
- * Gets the jth element of given segment array (if nonnull) with
- * volatile element access semantics via Unsafe. (The null check
- * can trigger harmlessly only during deserialization.) Note:
- * because each element of segments array is set only once (using
- * fully ordered writes), some performance-sensitive methods rely
- * on this method only as a recheck upon null reads.
- */
- @SuppressWarnings("unchecked")
- static final Segment segmentAt(Segment[] ss, int j) {
- long u = (j << SSHIFT) + SBASE;
- return ss == null ? null :
- (Segment) UNSAFE.getObjectVolatile(ss, u);
- }
-
- /**
- * Returns the segment for the given index, creating it and
- * recording in segment table (via CAS) if not already present.
- *
- * @param k the index
- * @return the segment
- */
- @SuppressWarnings("unchecked")
- private Segment ensureSegment(int k) {
- final Segment[] ss = this.segments;
- long u = (k << SSHIFT) + SBASE; // raw offset
- Segment seg;
- if ((seg = (Segment)UNSAFE.getObjectVolatile(ss, u)) == null) {
- Segment proto = ss[0]; // use segment 0 as prototype
- int cap = proto.table.length;
- float lf = proto.loadFactor;
- int threshold = (int)(cap * lf);
- HashEntry[] tab = (HashEntry[])new HashEntry[cap];
- if ((seg = (Segment)UNSAFE.getObjectVolatile(ss, u))
- == null) { // recheck
- Segment s = new Segment(lf, threshold, tab);
- while ((seg = (Segment)UNSAFE.getObjectVolatile(ss, u))
- == null) {
- if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
- break;
- }
- }
- }
- return seg;
- }
-
- // Hash-based segment and entry accesses
-
- /**
- * Get the segment for the given hash
- */
- @SuppressWarnings("unchecked")
- private Segment segmentForHash(int h) {
- long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
- return (Segment) UNSAFE.getObjectVolatile(segments, u);
- }
-
- /**
- * Gets the table entry for the given segment and hash
- */
- @SuppressWarnings("unchecked")
- static final HashEntry entryForHash(Segment seg, int h) {
- HashEntry[] tab;
- return (seg == null || (tab = seg.table) == null) ? null :
- (HashEntry) UNSAFE.getObjectVolatile
- (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
- }
-
- /* ---------------- Public operations -------------- */
/**
* Creates a new, empty map with the specified initial
@@ -736,32 +146,7 @@
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
- if (concurrencyLevel > MAX_SEGMENTS)
- concurrencyLevel = MAX_SEGMENTS;
- // Find power-of-two sizes best matching arguments
- int sshift = 0;
- int ssize = 1;
- while (ssize < concurrencyLevel) {
- ++sshift;
- ssize <<= 1;
- }
- this.segmentShift = 32 - sshift;
- this.segmentMask = ssize - 1;
- if (initialCapacity > MAXIMUM_CAPACITY)
- initialCapacity = MAXIMUM_CAPACITY;
- int c = initialCapacity / ssize;
- if (c * ssize < initialCapacity)
- ++c;
- int cap = MIN_SEGMENT_TABLE_CAPACITY;
- while (cap < c)
- cap <<= 1;
- // create segments and segments[0]
- Segment s0 =
- new Segment(loadFactor, (int)(cap * loadFactor),
- (HashEntry[])new HashEntry[cap]);
- Segment[] ss = (Segment[])new Segment[ssize];
- UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
- this.segments = ss;
+ delegate = new HashMap<>(initialCapacity, loadFactor);
}
/**
@@ -817,706 +202,126 @@
DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
putAll(m);
}
+
- /**
- * Returns true if this map contains no key-value mappings.
- *
- * @return true if this map contains no key-value mappings
- */
- public boolean isEmpty() {
- /*
- * Sum per-segment modCounts to avoid mis-reporting when
- * elements are concurrently added and removed in one segment
- * while checking another, in which case the table was never
- * actually empty at any point. (The sum ensures accuracy up
- * through at least 1<<31 per-segment modifications before
- * recheck.) Methods size() and containsValue() use similar
- * constructions for stability checks.
- */
- long sum = 0L;
- final Segment[] segments = this.segments;
- for (int j = 0; j < segments.length; ++j) {
- Segment seg = segmentAt(segments, j);
- if (seg != null) {
- if (seg.count != 0)
- return false;
- sum += seg.modCount;
- }
- }
- if (sum != 0L) { // recheck unless no modifications
- for (int j = 0; j < segments.length; ++j) {
- Segment seg = segmentAt(segments, j);
- if (seg != null) {
- if (seg.count != 0)
- return false;
- sum -= seg.modCount;
- }
- }
- if (sum != 0L)
- return false;
- }
- return true;
+ @Override
+ public int size() {
+ return delegate.size();
}
- /**
- * 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() {
- // Try a few times to get accurate count. On failure due to
- // continuous async changes in table, resort to locking.
- final Segment[] segments = this.segments;
- int size;
- boolean overflow; // true if size overflows 32 bits
- long sum; // sum of modCounts
- long last = 0L; // previous sum
- int retries = -1; // first iteration isn't retry
- try {
- for (;;) {
- if (retries++ == RETRIES_BEFORE_LOCK) {
- for (int j = 0; j < segments.length; ++j)
- ensureSegment(j).lock(); // force creation
- }
- sum = 0L;
- size = 0;
- overflow = false;
- for (int j = 0; j < segments.length; ++j) {
- Segment seg = segmentAt(segments, j);
- if (seg != null) {
- sum += seg.modCount;
- int c = seg.count;
- if (c < 0 || (size += c) < 0)
- overflow = true;
- }
- }
- if (sum == last)
- break;
- last = sum;
- }
- } finally {
- if (retries > RETRIES_BEFORE_LOCK) {
- for (int j = 0; j < segments.length; ++j)
- segmentAt(segments, j).unlock();
- }
- }
- return overflow ? Integer.MAX_VALUE : size;
+ @Override
+ public boolean isEmpty() {
+ return delegate.isEmpty();
}
- /**
- * Returns the value to which the specified key is mapped,
- * or {@code null} if this map contains no mapping for the key.
- *
- * 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) {
- Segment s; // manually integrate access methods to reduce overhead
- HashEntry[] tab;
- int h = hash(key.hashCode());
- long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
- if ((s = (Segment)UNSAFE.getObjectVolatile(segments, u)) != null &&
- (tab = s.table) != null) {
- for (HashEntry e = (HashEntry) UNSAFE.getObjectVolatile
- (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
- e != null; e = e.next) {
- K k;
- if ((k = e.key) == key || (e.hash == h && key.equals(k)))
- return e.value;
- }
- }
- return null;
+ @Override
+ public boolean containsKey(Object key) {
+ return delegate.containsKey(key);
}
- /**
- * 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 specified key is null
- */
- @SuppressWarnings("unchecked")
- public boolean containsKey(Object key) {
- Segment s; // same as get() except no need for volatile value read
- HashEntry[] tab;
- int h = hash(key.hashCode());
- long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
- if ((s = (Segment)UNSAFE.getObjectVolatile(segments, u)) != null &&
- (tab = s.table) != null) {
- for (HashEntry e = (HashEntry) UNSAFE.getObjectVolatile
- (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
- e != null; e = e.next) {
- K k;
- if ((k = e.key) == key || (e.hash == h && key.equals(k)))
- return true;
- }
- }
- return false;
+ @Override
+ public boolean containsValue(Object value) {
+ return delegate.containsValue(value);
}
- /**
- * Returns true if this map maps one or more keys to the
- * specified value. Note: This method requires a full internal
- * 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
- * @return true if this map maps one or more keys to the
- * specified value
- * @throws NullPointerException if the specified value is null
- */
- public boolean containsValue(Object value) {
- // Same idea as size()
- if (value == null)
- throw new NullPointerException();
- final Segment[] segments = this.segments;
- boolean found = false;
- long last = 0;
- int retries = -1;
- try {
- outer: for (;;) {
- if (retries++ == RETRIES_BEFORE_LOCK) {
- for (int j = 0; j < segments.length; ++j)
- ensureSegment(j).lock(); // force creation
- }
- long hashSum = 0L;
- int sum = 0;
- for (int j = 0; j < segments.length; ++j) {
- HashEntry[] tab;
- Segment seg = segmentAt(segments, j);
- if (seg != null && (tab = seg.table) != null) {
- for (int i = 0 ; i < tab.length; i++) {
- HashEntry e;
- for (e = entryAt(tab, i); e != null; e = e.next) {
- V v = e.value;
- if (v != null && value.equals(v)) {
- found = true;
- break outer;
- }
- }
- }
- sum += seg.modCount;
- }
- }
- if (retries > 0 && sum == last)
- break;
- last = sum;
- }
- } finally {
- if (retries > RETRIES_BEFORE_LOCK) {
- for (int j = 0; j < segments.length; ++j)
- segmentAt(segments, j).unlock();
- }
- }
- return found;
+ @Override
+ public V get(Object key) {
+ return delegate.get(key);
}
- /**
- * 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
- * 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 specified value is null
- */
- public boolean contains(Object value) {
- return containsValue(value);
+ @Override
+ public V put(K key, V value) {
+ return delegate.put(key, value);
}
- /**
- * 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 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
- */
- @SuppressWarnings("unchecked")
- public V put(K key, V value) {
- Segment s;
- if (value == null)
- throw new NullPointerException();
- int hash = hash(key.hashCode());
- int j = (hash >>> segmentShift) & segmentMask;
- if ((s = (Segment)UNSAFE.getObject // nonvolatile; recheck
- (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
- s = ensureSegment(j);
- return s.put(key, hash, value, false);
+ @Override
+ public V remove(Object key) {
+ return delegate.remove(key);
}
- /**
- * {@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
- */
- @SuppressWarnings("unchecked")
- public V putIfAbsent(K key, V value) {
- Segment s;
- if (value == null)
- throw new NullPointerException();
- int hash = hash(key.hashCode());
- int j = (hash >>> segmentShift) & segmentMask;
- if ((s = (Segment)UNSAFE.getObject
- (segments, (j << SSHIFT) + SBASE)) == null)
- s = ensureSegment(j);
- return s.put(key, hash, value, true);
+ @Override
+ public void putAll(Map extends K, ? extends V> m) {
+ delegate.putAll(m);
}
- /**
- * 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.
- *
- * @param m mappings to be stored in this map
- */
- public void putAll(Map extends K, ? extends V> m) {
- for (Map.Entry extends K, ? extends V> e : m.entrySet())
- put(e.getKey(), e.getValue());
+ @Override
+ public void clear() {
+ delegate.clear();
}
- /**
- * 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 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.hashCode());
- Segment s = segmentForHash(hash);
- return s == null ? null : s.remove(key, hash, null);
+ @Override
+ public Set keySet() {
+ return delegate.keySet();
}
- /**
- * {@inheritDoc}
- *
- * @throws NullPointerException if the specified key is null
- */
- public boolean remove(Object key, Object value) {
- int hash = hash(key.hashCode());
- Segment s;
- return value != null && (s = segmentForHash(hash)) != null &&
- s.remove(key, hash, value) != null;
+ @Override
+ public Collection values() {
+ return delegate.values();
}
- /**
- * {@inheritDoc}
- *
- * @throws NullPointerException if any of the arguments are null
- */
- public boolean replace(K key, V oldValue, V newValue) {
- int hash = hash(key.hashCode());
- if (oldValue == null || newValue == null)
- throw new NullPointerException();
- Segment s = segmentForHash(hash);
- return s != null && s.replace(key, hash, oldValue, newValue);
+ @Override
+ public Set> entrySet() {
+ return delegate.entrySet();
}
- /**
- * {@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) {
- int hash = hash(key.hashCode());
- if (value == null)
- throw new NullPointerException();
- Segment s = segmentForHash(hash);
- return s == null ? null : s.replace(key, hash, value);
+ @Override
+ public boolean equals(Object o) {
+ return delegate.equals(o);
}
- /**
- * Removes all of the mappings from this map.
- */
- public void clear() {
- final Segment[] segments = this.segments;
- for (int j = 0; j < segments.length; ++j) {
- Segment s = segmentAt(segments, j);
- if (s != null)
- s.clear();
+ @Override
+ public int hashCode() {
+ return delegate.hashCode();
+ }
+
+ @Override
+ public String toString() {
+ return delegate.toString();
+ }
+
+ @Override
+ public V putIfAbsent(K key, V value) {
+ V old = delegate.get(key);
+ if (old == null) {
+ return delegate.put(key, value);
+ }
+ return old;
+ }
+
+ @Override
+ public boolean remove(Object key, Object value) {
+ if (equals(value, delegate.get(key))) {
+ delegate.remove(key);
+ return true;
+ } else {
+ return false;
}
}
- /**
- * 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 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.
- */
- public Set keySet() {
- Set ks = keySet;
- return (ks != null) ? ks : (keySet = new KeySet());
- }
-
- /**
- * 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 Iterator.remove,
- * Collection.remove, removeAll,
- * retainAll, and clear operations. It does not
- * support the add or addAll operations.
- *
- * 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.
- */
- public Collection values() {
- Collection vs = values;
- return (vs != null) ? vs : (values = new Values());
- }
-
- /**
- * 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 Iterator.remove, Set.remove,
- * removeAll, retainAll, and clear
- * operations. It does not support the add or
- * addAll operations.
- *
- * 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.
- */
- public Set> entrySet() {
- Set> es = 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()
- */
- public Enumeration keys() {
- return new KeyIterator();
- }
-
- /**
- * Returns an enumeration of the values in this table.
- *
- * @return an enumeration of the values in this table
- * @see #values()
- */
- public Enumeration elements() {
- return new ValueIterator();
- }
-
- /* ---------------- Iterator Support -------------- */
-
- abstract class HashIterator {
- int nextSegmentIndex;
- int nextTableIndex;
- HashEntry[] currentTable;
- HashEntry nextEntry;
- HashEntry lastReturned;
-
- HashIterator() {
- nextSegmentIndex = segments.length - 1;
- nextTableIndex = -1;
- advance();
- }
-
- /**
- * Set nextEntry to first node of next non-empty table
- * (in backwards order, to simplify checks).
- */
- final void advance() {
- for (;;) {
- if (nextTableIndex >= 0) {
- if ((nextEntry = entryAt(currentTable,
- nextTableIndex--)) != null)
- break;
- }
- else if (nextSegmentIndex >= 0) {
- Segment seg = segmentAt(segments, nextSegmentIndex--);
- if (seg != null && (currentTable = seg.table) != null)
- nextTableIndex = currentTable.length - 1;
- }
- else
- break;
- }
- }
-
- final HashEntry nextEntry() {
- HashEntry e = nextEntry;
- if (e == null)
- throw new NoSuchElementException();
- lastReturned = e; // cannot assign until after null check
- if ((nextEntry = e.next) == null)
- advance();
- return e;
- }
-
- public final boolean hasNext() { return nextEntry != null; }
- public final boolean hasMoreElements() { return nextEntry != null; }
-
- public final void remove() {
- if (lastReturned == null)
- throw new IllegalStateException();
- ConcurrentHashMap.this.remove(lastReturned.key);
- lastReturned = null;
+ @Override
+ public boolean replace(K key, V oldValue, V newValue) {
+ if (equals(oldValue, delegate.get(key))) {
+ delegate.put(key, newValue);
+ return true;
+ } else {
+ return false;
}
}
- final class KeyIterator
- extends HashIterator
- implements Iterator, Enumeration
- {
- public final K next() { return super.nextEntry().key; }
- public final K nextElement() { return super.nextEntry().key; }
- }
-
- final class ValueIterator
- extends HashIterator
- implements Iterator, Enumeration
- {
- public final V next() { return super.nextEntry().value; }
- public final V nextElement() { return super.nextEntry().value; }
- }
-
- /**
- * Custom Entry class used by EntryIterator.next(), that relays
- * setValue changes to the underlying map.
- */
- final class WriteThroughEntry
- extends AbstractMap.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 (value == null) throw new NullPointerException();
- V v = super.setValue(value);
- ConcurrentHashMap.this.put(getKey(), value);
- return v;
+ @Override
+ public V replace(K key, V value) {
+ if (delegate.containsKey(key)) {
+ return delegate.put(key, value);
+ } else {
+ return null;
}
}
-
- final class EntryIterator
- extends HashIterator
- implements Iterator>
- {
- public Map.Entry next() {
- HashEntry e = super.nextEntry();
- return new WriteThroughEntry(e.key, e.value);
+
+ private static boolean equals(Object a, Object b) {
+ if (a == null) {
+ return b == null;
+ } else {
+ return a.equals(b);
}
}
-
- final class KeySet extends AbstractSet {
- public Iterator iterator() {
- return new KeyIterator();
- }
- public int size() {
- return ConcurrentHashMap.this.size();
- }
- public boolean isEmpty() {
- return ConcurrentHashMap.this.isEmpty();
- }
- public boolean contains(Object o) {
- return ConcurrentHashMap.this.containsKey(o);
- }
- public boolean remove(Object o) {
- return ConcurrentHashMap.this.remove(o) != null;
- }
- public void clear() {
- ConcurrentHashMap.this.clear();
- }
- }
-
- final class Values extends AbstractCollection {
- public Iterator iterator() {
- return new ValueIterator();
- }
- public int size() {
- return ConcurrentHashMap.this.size();
- }
- public boolean isEmpty() {
- return ConcurrentHashMap.this.isEmpty();
- }
- public boolean contains(Object o) {
- return ConcurrentHashMap.this.containsValue(o);
- }
- public void clear() {
- ConcurrentHashMap.this.clear();
- }
- }
-
- final class EntrySet extends AbstractSet> {
- public Iterator> iterator() {
- return new EntryIterator();
- }
- public boolean contains(Object o) {
- if (!(o instanceof Map.Entry))
- return false;
- 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;
- 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();
- }
- }
-
- /* ---------------- Serialization Support -------------- */
-
- /**
- * 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)
- * for each key-value mapping, followed by a null pair.
- * The key-value mappings are emitted in no particular order.
- */
- private void writeObject(java.io.ObjectOutputStream s) throws IOException {
- // force all segments for serialization compatibility
- for (int k = 0; k < segments.length; ++k)
- ensureSegment(k);
- s.defaultWriteObject();
-
- final Segment[] segments = this.segments;
- for (int k = 0; k < segments.length; ++k) {
- Segment seg = segmentAt(segments, k);
- seg.lock();
- try {
- HashEntry[] tab = seg.table;
- for (int i = 0; i < tab.length; ++i) {
- HashEntry e;
- for (e = entryAt(tab, i); e != null; e = e.next) {
- s.writeObject(e.key);
- s.writeObject(e.value);
- }
- }
- } finally {
- seg.unlock();
- }
- }
- s.writeObject(null);
- s.writeObject(null);
- }
-
- /**
- * Reconstitute the ConcurrentHashMap instance from a
- * stream (i.e., deserialize it).
- * @param s the stream
- */
- @SuppressWarnings("unchecked")
- private void readObject(java.io.ObjectInputStream s)
- throws IOException, ClassNotFoundException {
- s.defaultReadObject();
-
- // Re-initialize segments to be minimally sized, and let grow.
- int cap = MIN_SEGMENT_TABLE_CAPACITY;
- final Segment[] segments = this.segments;
- for (int k = 0; k < segments.length; ++k) {
- Segment seg = segments[k];
- if (seg != null) {
- seg.threshold = (int)(cap * seg.loadFactor);
- seg.table = (HashEntry[]) new HashEntry[cap];
- }
- }
-
- // Read the keys and values, and put the mappings in the table
- for (;;) {
- K key = (K) s.readObject();
- V value = (V) s.readObject();
- if (key == null)
- break;
- put(key, value);
- }
- }
-
- // Unsafe mechanics
- private static final sun.misc.Unsafe UNSAFE;
- private static final long SBASE;
- private static final int SSHIFT;
- private static final long TBASE;
- private static final int TSHIFT;
-
- static {
- int ss, ts;
- try {
- UNSAFE = sun.misc.Unsafe.getUnsafe();
- Class tc = HashEntry[].class;
- Class sc = Segment[].class;
- TBASE = UNSAFE.arrayBaseOffset(tc);
- SBASE = UNSAFE.arrayBaseOffset(sc);
- ts = UNSAFE.arrayIndexScale(tc);
- ss = UNSAFE.arrayIndexScale(sc);
- } catch (Exception e) {
- throw new Error(e);
- }
- if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0)
- throw new Error("data type scale not a power of two");
- SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
- TSHIFT = 31 - Integer.numberOfLeadingZeros(ts);
- }
-
}