1.1 --- a/rt/emul/compact/src/main/java/java/util/concurrent/ConcurrentHashMap.java Thu Oct 03 15:40:35 2013 +0200
1.2 +++ b/rt/emul/compact/src/main/java/java/util/concurrent/ConcurrentHashMap.java Fri Oct 04 10:52:01 2013 +0200
1.3 @@ -32,9 +32,8 @@
1.4 * Expert Group and released to the public domain, as explained at
1.5 * http://creativecommons.org/publicdomain/zero/1.0/
1.6 */
1.7 +package java.util.concurrent;
1.8
1.9 -package java.util.concurrent;
1.10 -import java.util.concurrent.locks.*;
1.11 import java.util.*;
1.12 import java.io.Serializable;
1.13 import java.io.IOException;
1.14 @@ -42,55 +41,57 @@
1.15 import java.io.ObjectOutputStream;
1.16
1.17 /**
1.18 - * A hash table supporting full concurrency of retrievals and
1.19 - * adjustable expected concurrency for updates. This class obeys the
1.20 - * same functional specification as {@link java.util.Hashtable}, and
1.21 - * includes versions of methods corresponding to each method of
1.22 - * <tt>Hashtable</tt>. However, even though all operations are
1.23 - * thread-safe, retrieval operations do <em>not</em> entail locking,
1.24 - * and there is <em>not</em> any support for locking the entire table
1.25 - * in a way that prevents all access. This class is fully
1.26 - * interoperable with <tt>Hashtable</tt> in programs that rely on its
1.27 - * thread safety but not on its synchronization details.
1.28 + * A hash table supporting full concurrency of retrievals and adjustable
1.29 + * expected concurrency for updates. This class obeys the same functional
1.30 + * specification as {@link java.util.Hashtable}, and includes versions of
1.31 + * methods corresponding to each method of
1.32 + * <tt>Hashtable</tt>. However, even though all operations are thread-safe,
1.33 + * retrieval operations do <em>not</em> entail locking, and there is
1.34 + * <em>not</em> any support for locking the entire table in a way that prevents
1.35 + * all access. This class is fully interoperable with <tt>Hashtable</tt> in
1.36 + * programs that rely on its thread safety but not on its synchronization
1.37 + * details.
1.38 *
1.39 - * <p> Retrieval operations (including <tt>get</tt>) generally do not
1.40 - * block, so may overlap with update operations (including
1.41 - * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results
1.42 - * of the most recently <em>completed</em> update operations holding
1.43 - * upon their onset. For aggregate operations such as <tt>putAll</tt>
1.44 - * and <tt>clear</tt>, concurrent retrievals may reflect insertion or
1.45 - * removal of only some entries. Similarly, Iterators and
1.46 - * Enumerations return elements reflecting the state of the hash table
1.47 - * at some point at or since the creation of the iterator/enumeration.
1.48 - * They do <em>not</em> throw {@link ConcurrentModificationException}.
1.49 - * However, iterators are designed to be used by only one thread at a time.
1.50 + * <p>
1.51 + * Retrieval operations (including <tt>get</tt>) generally do not block, so may
1.52 + * overlap with update operations (including
1.53 + * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results of the most
1.54 + * recently <em>completed</em> update operations holding upon their onset. For
1.55 + * aggregate operations such as <tt>putAll</tt>
1.56 + * and <tt>clear</tt>, concurrent retrievals may reflect insertion or removal of
1.57 + * only some entries. Similarly, Iterators and Enumerations return elements
1.58 + * reflecting the state of the hash table at some point at or since the creation
1.59 + * of the iterator/enumeration. They do <em>not</em> throw
1.60 + * {@link ConcurrentModificationException}. However, iterators are designed to
1.61 + * be used by only one thread at a time.
1.62 *
1.63 - * <p> The allowed concurrency among update operations is guided by
1.64 - * the optional <tt>concurrencyLevel</tt> constructor argument
1.65 - * (default <tt>16</tt>), which is used as a hint for internal sizing. The
1.66 - * table is internally partitioned to try to permit the indicated
1.67 - * number of concurrent updates without contention. Because placement
1.68 - * in hash tables is essentially random, the actual concurrency will
1.69 - * vary. Ideally, you should choose a value to accommodate as many
1.70 - * threads as will ever concurrently modify the table. Using a
1.71 - * significantly higher value than you need can waste space and time,
1.72 - * and a significantly lower value can lead to thread contention. But
1.73 - * overestimates and underestimates within an order of magnitude do
1.74 - * not usually have much noticeable impact. A value of one is
1.75 - * appropriate when it is known that only one thread will modify and
1.76 - * all others will only read. Also, resizing this or any other kind of
1.77 - * hash table is a relatively slow operation, so, when possible, it is
1.78 - * a good idea to provide estimates of expected table sizes in
1.79 + * <p>
1.80 + * The allowed concurrency among update operations is guided by the optional
1.81 + * <tt>concurrencyLevel</tt> constructor argument (default <tt>16</tt>), which
1.82 + * is used as a hint for internal sizing. The table is internally partitioned to
1.83 + * try to permit the indicated number of concurrent updates without contention.
1.84 + * Because placement in hash tables is essentially random, the actual
1.85 + * concurrency will vary. Ideally, you should choose a value to accommodate as
1.86 + * many threads as will ever concurrently modify the table. Using a
1.87 + * significantly higher value than you need can waste space and time, and a
1.88 + * significantly lower value can lead to thread contention. But overestimates
1.89 + * and underestimates within an order of magnitude do not usually have much
1.90 + * noticeable impact. A value of one is appropriate when it is known that only
1.91 + * one thread will modify and all others will only read. Also, resizing this or
1.92 + * any other kind of hash table is a relatively slow operation, so, when
1.93 + * possible, it is a good idea to provide estimates of expected table sizes in
1.94 * constructors.
1.95 *
1.96 - * <p>This class and its views and iterators implement all of the
1.97 - * <em>optional</em> methods of the {@link Map} and {@link Iterator}
1.98 - * interfaces.
1.99 + * <p>
1.100 + * This class and its views and iterators implement all of the
1.101 + * <em>optional</em> methods of the {@link Map} and {@link Iterator} interfaces.
1.102 *
1.103 - * <p> Like {@link Hashtable} but unlike {@link HashMap}, this class
1.104 - * does <em>not</em> allow <tt>null</tt> to be used as a key or value.
1.105 + * <p>
1.106 + * Like {@link Hashtable} but unlike {@link HashMap}, this class does
1.107 + * <em>not</em> allow <tt>null</tt> to be used as a key or value.
1.108 *
1.109 - * <p>This class is a member of the
1.110 + * <p>
1.111 + * This class is a member of the
1.112 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.113 * Java Collections Framework</a>.
1.114 *
1.115 @@ -100,34 +101,9 @@
1.116 * @param <V> the type of mapped values
1.117 */
1.118 public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
1.119 - implements ConcurrentMap<K, V>, Serializable {
1.120 + implements ConcurrentMap<K, V>, Serializable {
1.121 +
1.122 private static final long serialVersionUID = 7249069246763182397L;
1.123 -
1.124 - /*
1.125 - * The basic strategy is to subdivide the table among Segments,
1.126 - * each of which itself is a concurrently readable hash table. To
1.127 - * reduce footprint, all but one segments are constructed only
1.128 - * when first needed (see ensureSegment). To maintain visibility
1.129 - * in the presence of lazy construction, accesses to segments as
1.130 - * well as elements of segment's table must use volatile access,
1.131 - * which is done via Unsafe within methods segmentAt etc
1.132 - * below. These provide the functionality of AtomicReferenceArrays
1.133 - * but reduce the levels of indirection. Additionally,
1.134 - * volatile-writes of table elements and entry "next" fields
1.135 - * within locked operations use the cheaper "lazySet" forms of
1.136 - * writes (via putOrderedObject) because these writes are always
1.137 - * followed by lock releases that maintain sequential consistency
1.138 - * of table updates.
1.139 - *
1.140 - * Historical note: The previous version of this class relied
1.141 - * heavily on "final" fields, which avoided some volatile reads at
1.142 - * the expense of a large initial footprint. Some remnants of
1.143 - * that design (including forced construction of segment 0) exist
1.144 - * to ensure serialization compatibility.
1.145 - */
1.146 -
1.147 - /* ---------------- Constants -------------- */
1.148 -
1.149 /**
1.150 * The default initial capacity for this table,
1.151 * used when not otherwise specified in a constructor.
1.152 @@ -146,574 +122,8 @@
1.153 */
1.154 static final int DEFAULT_CONCURRENCY_LEVEL = 16;
1.155
1.156 - /**
1.157 - * The maximum capacity, used if a higher value is implicitly
1.158 - * specified by either of the constructors with arguments. MUST
1.159 - * be a power of two <= 1<<30 to ensure that entries are indexable
1.160 - * using ints.
1.161 - */
1.162 - static final int MAXIMUM_CAPACITY = 1 << 30;
1.163 + private final Map<K, V> delegate;
1.164
1.165 - /**
1.166 - * The minimum capacity for per-segment tables. Must be a power
1.167 - * of two, at least two to avoid immediate resizing on next use
1.168 - * after lazy construction.
1.169 - */
1.170 - static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
1.171 -
1.172 - /**
1.173 - * The maximum number of segments to allow; used to bound
1.174 - * constructor arguments. Must be power of two less than 1 << 24.
1.175 - */
1.176 - static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
1.177 -
1.178 - /**
1.179 - * Number of unsynchronized retries in size and containsValue
1.180 - * methods before resorting to locking. This is used to avoid
1.181 - * unbounded retries if tables undergo continuous modification
1.182 - * which would make it impossible to obtain an accurate result.
1.183 - */
1.184 - static final int RETRIES_BEFORE_LOCK = 2;
1.185 -
1.186 - /* ---------------- Fields -------------- */
1.187 -
1.188 - /**
1.189 - * Mask value for indexing into segments. The upper bits of a
1.190 - * key's hash code are used to choose the segment.
1.191 - */
1.192 - final int segmentMask;
1.193 -
1.194 - /**
1.195 - * Shift value for indexing within segments.
1.196 - */
1.197 - final int segmentShift;
1.198 -
1.199 - /**
1.200 - * The segments, each of which is a specialized hash table.
1.201 - */
1.202 - final Segment<K,V>[] segments;
1.203 -
1.204 - transient Set<K> keySet;
1.205 - transient Set<Map.Entry<K,V>> entrySet;
1.206 - transient Collection<V> values;
1.207 -
1.208 - /**
1.209 - * ConcurrentHashMap list entry. Note that this is never exported
1.210 - * out as a user-visible Map.Entry.
1.211 - */
1.212 - static final class HashEntry<K,V> {
1.213 - final int hash;
1.214 - final K key;
1.215 - volatile V value;
1.216 - volatile HashEntry<K,V> next;
1.217 -
1.218 - HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
1.219 - this.hash = hash;
1.220 - this.key = key;
1.221 - this.value = value;
1.222 - this.next = next;
1.223 - }
1.224 -
1.225 - /**
1.226 - * Sets next field with volatile write semantics. (See above
1.227 - * about use of putOrderedObject.)
1.228 - */
1.229 - final void setNext(HashEntry<K,V> n) {
1.230 - UNSAFE.putOrderedObject(this, nextOffset, n);
1.231 - }
1.232 -
1.233 - // Unsafe mechanics
1.234 - static final sun.misc.Unsafe UNSAFE;
1.235 - static final long nextOffset;
1.236 - static {
1.237 - try {
1.238 - UNSAFE = sun.misc.Unsafe.getUnsafe();
1.239 - Class k = HashEntry.class;
1.240 - nextOffset = UNSAFE.objectFieldOffset
1.241 - (k.getDeclaredField("next"));
1.242 - } catch (Exception e) {
1.243 - throw new Error(e);
1.244 - }
1.245 - }
1.246 - }
1.247 -
1.248 - /**
1.249 - * Gets the ith element of given table (if nonnull) with volatile
1.250 - * read semantics. Note: This is manually integrated into a few
1.251 - * performance-sensitive methods to reduce call overhead.
1.252 - */
1.253 - @SuppressWarnings("unchecked")
1.254 - static final <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {
1.255 - return (tab == null) ? null :
1.256 - (HashEntry<K,V>) UNSAFE.getObjectVolatile
1.257 - (tab, ((long)i << TSHIFT) + TBASE);
1.258 - }
1.259 -
1.260 - /**
1.261 - * Sets the ith element of given table, with volatile write
1.262 - * semantics. (See above about use of putOrderedObject.)
1.263 - */
1.264 - static final <K,V> void setEntryAt(HashEntry<K,V>[] tab, int i,
1.265 - HashEntry<K,V> e) {
1.266 - UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e);
1.267 - }
1.268 -
1.269 - /**
1.270 - * Applies a supplemental hash function to a given hashCode, which
1.271 - * defends against poor quality hash functions. This is critical
1.272 - * because ConcurrentHashMap uses power-of-two length hash tables,
1.273 - * that otherwise encounter collisions for hashCodes that do not
1.274 - * differ in lower or upper bits.
1.275 - */
1.276 - private static int hash(int h) {
1.277 - // Spread bits to regularize both segment and index locations,
1.278 - // using variant of single-word Wang/Jenkins hash.
1.279 - h += (h << 15) ^ 0xffffcd7d;
1.280 - h ^= (h >>> 10);
1.281 - h += (h << 3);
1.282 - h ^= (h >>> 6);
1.283 - h += (h << 2) + (h << 14);
1.284 - return h ^ (h >>> 16);
1.285 - }
1.286 -
1.287 - /**
1.288 - * Segments are specialized versions of hash tables. This
1.289 - * subclasses from ReentrantLock opportunistically, just to
1.290 - * simplify some locking and avoid separate construction.
1.291 - */
1.292 - static final class Segment<K,V> extends ReentrantLock implements Serializable {
1.293 - /*
1.294 - * Segments maintain a table of entry lists that are always
1.295 - * kept in a consistent state, so can be read (via volatile
1.296 - * reads of segments and tables) without locking. This
1.297 - * requires replicating nodes when necessary during table
1.298 - * resizing, so the old lists can be traversed by readers
1.299 - * still using old version of table.
1.300 - *
1.301 - * This class defines only mutative methods requiring locking.
1.302 - * Except as noted, the methods of this class perform the
1.303 - * per-segment versions of ConcurrentHashMap methods. (Other
1.304 - * methods are integrated directly into ConcurrentHashMap
1.305 - * methods.) These mutative methods use a form of controlled
1.306 - * spinning on contention via methods scanAndLock and
1.307 - * scanAndLockForPut. These intersperse tryLocks with
1.308 - * traversals to locate nodes. The main benefit is to absorb
1.309 - * cache misses (which are very common for hash tables) while
1.310 - * obtaining locks so that traversal is faster once
1.311 - * acquired. We do not actually use the found nodes since they
1.312 - * must be re-acquired under lock anyway to ensure sequential
1.313 - * consistency of updates (and in any case may be undetectably
1.314 - * stale), but they will normally be much faster to re-locate.
1.315 - * Also, scanAndLockForPut speculatively creates a fresh node
1.316 - * to use in put if no node is found.
1.317 - */
1.318 -
1.319 - private static final long serialVersionUID = 2249069246763182397L;
1.320 -
1.321 - /**
1.322 - * The maximum number of times to tryLock in a prescan before
1.323 - * possibly blocking on acquire in preparation for a locked
1.324 - * segment operation. On multiprocessors, using a bounded
1.325 - * number of retries maintains cache acquired while locating
1.326 - * nodes.
1.327 - */
1.328 - static final int MAX_SCAN_RETRIES =
1.329 - Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
1.330 -
1.331 - /**
1.332 - * The per-segment table. Elements are accessed via
1.333 - * entryAt/setEntryAt providing volatile semantics.
1.334 - */
1.335 - transient volatile HashEntry<K,V>[] table;
1.336 -
1.337 - /**
1.338 - * The number of elements. Accessed only either within locks
1.339 - * or among other volatile reads that maintain visibility.
1.340 - */
1.341 - transient int count;
1.342 -
1.343 - /**
1.344 - * The total number of mutative operations in this segment.
1.345 - * Even though this may overflows 32 bits, it provides
1.346 - * sufficient accuracy for stability checks in CHM isEmpty()
1.347 - * and size() methods. Accessed only either within locks or
1.348 - * among other volatile reads that maintain visibility.
1.349 - */
1.350 - transient int modCount;
1.351 -
1.352 - /**
1.353 - * The table is rehashed when its size exceeds this threshold.
1.354 - * (The value of this field is always <tt>(int)(capacity *
1.355 - * loadFactor)</tt>.)
1.356 - */
1.357 - transient int threshold;
1.358 -
1.359 - /**
1.360 - * The load factor for the hash table. Even though this value
1.361 - * is same for all segments, it is replicated to avoid needing
1.362 - * links to outer object.
1.363 - * @serial
1.364 - */
1.365 - final float loadFactor;
1.366 -
1.367 - Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
1.368 - this.loadFactor = lf;
1.369 - this.threshold = threshold;
1.370 - this.table = tab;
1.371 - }
1.372 -
1.373 - final V put(K key, int hash, V value, boolean onlyIfAbsent) {
1.374 - HashEntry<K,V> node = tryLock() ? null :
1.375 - scanAndLockForPut(key, hash, value);
1.376 - V oldValue;
1.377 - try {
1.378 - HashEntry<K,V>[] tab = table;
1.379 - int index = (tab.length - 1) & hash;
1.380 - HashEntry<K,V> first = entryAt(tab, index);
1.381 - for (HashEntry<K,V> e = first;;) {
1.382 - if (e != null) {
1.383 - K k;
1.384 - if ((k = e.key) == key ||
1.385 - (e.hash == hash && key.equals(k))) {
1.386 - oldValue = e.value;
1.387 - if (!onlyIfAbsent) {
1.388 - e.value = value;
1.389 - ++modCount;
1.390 - }
1.391 - break;
1.392 - }
1.393 - e = e.next;
1.394 - }
1.395 - else {
1.396 - if (node != null)
1.397 - node.setNext(first);
1.398 - else
1.399 - node = new HashEntry<K,V>(hash, key, value, first);
1.400 - int c = count + 1;
1.401 - if (c > threshold && tab.length < MAXIMUM_CAPACITY)
1.402 - rehash(node);
1.403 - else
1.404 - setEntryAt(tab, index, node);
1.405 - ++modCount;
1.406 - count = c;
1.407 - oldValue = null;
1.408 - break;
1.409 - }
1.410 - }
1.411 - } finally {
1.412 - unlock();
1.413 - }
1.414 - return oldValue;
1.415 - }
1.416 -
1.417 - /**
1.418 - * Doubles size of table and repacks entries, also adding the
1.419 - * given node to new table
1.420 - */
1.421 - @SuppressWarnings("unchecked")
1.422 - private void rehash(HashEntry<K,V> node) {
1.423 - /*
1.424 - * Reclassify nodes in each list to new table. Because we
1.425 - * are using power-of-two expansion, the elements from
1.426 - * each bin must either stay at same index, or move with a
1.427 - * power of two offset. We eliminate unnecessary node
1.428 - * creation by catching cases where old nodes can be
1.429 - * reused because their next fields won't change.
1.430 - * Statistically, at the default threshold, only about
1.431 - * one-sixth of them need cloning when a table
1.432 - * doubles. The nodes they replace will be garbage
1.433 - * collectable as soon as they are no longer referenced by
1.434 - * any reader thread that may be in the midst of
1.435 - * concurrently traversing table. Entry accesses use plain
1.436 - * array indexing because they are followed by volatile
1.437 - * table write.
1.438 - */
1.439 - HashEntry<K,V>[] oldTable = table;
1.440 - int oldCapacity = oldTable.length;
1.441 - int newCapacity = oldCapacity << 1;
1.442 - threshold = (int)(newCapacity * loadFactor);
1.443 - HashEntry<K,V>[] newTable =
1.444 - (HashEntry<K,V>[]) new HashEntry[newCapacity];
1.445 - int sizeMask = newCapacity - 1;
1.446 - for (int i = 0; i < oldCapacity ; i++) {
1.447 - HashEntry<K,V> e = oldTable[i];
1.448 - if (e != null) {
1.449 - HashEntry<K,V> next = e.next;
1.450 - int idx = e.hash & sizeMask;
1.451 - if (next == null) // Single node on list
1.452 - newTable[idx] = e;
1.453 - else { // Reuse consecutive sequence at same slot
1.454 - HashEntry<K,V> lastRun = e;
1.455 - int lastIdx = idx;
1.456 - for (HashEntry<K,V> last = next;
1.457 - last != null;
1.458 - last = last.next) {
1.459 - int k = last.hash & sizeMask;
1.460 - if (k != lastIdx) {
1.461 - lastIdx = k;
1.462 - lastRun = last;
1.463 - }
1.464 - }
1.465 - newTable[lastIdx] = lastRun;
1.466 - // Clone remaining nodes
1.467 - for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
1.468 - V v = p.value;
1.469 - int h = p.hash;
1.470 - int k = h & sizeMask;
1.471 - HashEntry<K,V> n = newTable[k];
1.472 - newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
1.473 - }
1.474 - }
1.475 - }
1.476 - }
1.477 - int nodeIndex = node.hash & sizeMask; // add the new node
1.478 - node.setNext(newTable[nodeIndex]);
1.479 - newTable[nodeIndex] = node;
1.480 - table = newTable;
1.481 - }
1.482 -
1.483 - /**
1.484 - * Scans for a node containing given key while trying to
1.485 - * acquire lock, creating and returning one if not found. Upon
1.486 - * return, guarantees that lock is held. UNlike in most
1.487 - * methods, calls to method equals are not screened: Since
1.488 - * traversal speed doesn't matter, we might as well help warm
1.489 - * up the associated code and accesses as well.
1.490 - *
1.491 - * @return a new node if key not found, else null
1.492 - */
1.493 - private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
1.494 - HashEntry<K,V> first = entryForHash(this, hash);
1.495 - HashEntry<K,V> e = first;
1.496 - HashEntry<K,V> node = null;
1.497 - int retries = -1; // negative while locating node
1.498 - while (!tryLock()) {
1.499 - HashEntry<K,V> f; // to recheck first below
1.500 - if (retries < 0) {
1.501 - if (e == null) {
1.502 - if (node == null) // speculatively create node
1.503 - node = new HashEntry<K,V>(hash, key, value, null);
1.504 - retries = 0;
1.505 - }
1.506 - else if (key.equals(e.key))
1.507 - retries = 0;
1.508 - else
1.509 - e = e.next;
1.510 - }
1.511 - else if (++retries > MAX_SCAN_RETRIES) {
1.512 - lock();
1.513 - break;
1.514 - }
1.515 - else if ((retries & 1) == 0 &&
1.516 - (f = entryForHash(this, hash)) != first) {
1.517 - e = first = f; // re-traverse if entry changed
1.518 - retries = -1;
1.519 - }
1.520 - }
1.521 - return node;
1.522 - }
1.523 -
1.524 - /**
1.525 - * Scans for a node containing the given key while trying to
1.526 - * acquire lock for a remove or replace operation. Upon
1.527 - * return, guarantees that lock is held. Note that we must
1.528 - * lock even if the key is not found, to ensure sequential
1.529 - * consistency of updates.
1.530 - */
1.531 - private void scanAndLock(Object key, int hash) {
1.532 - // similar to but simpler than scanAndLockForPut
1.533 - HashEntry<K,V> first = entryForHash(this, hash);
1.534 - HashEntry<K,V> e = first;
1.535 - int retries = -1;
1.536 - while (!tryLock()) {
1.537 - HashEntry<K,V> f;
1.538 - if (retries < 0) {
1.539 - if (e == null || key.equals(e.key))
1.540 - retries = 0;
1.541 - else
1.542 - e = e.next;
1.543 - }
1.544 - else if (++retries > MAX_SCAN_RETRIES) {
1.545 - lock();
1.546 - break;
1.547 - }
1.548 - else if ((retries & 1) == 0 &&
1.549 - (f = entryForHash(this, hash)) != first) {
1.550 - e = first = f;
1.551 - retries = -1;
1.552 - }
1.553 - }
1.554 - }
1.555 -
1.556 - /**
1.557 - * Remove; match on key only if value null, else match both.
1.558 - */
1.559 - final V remove(Object key, int hash, Object value) {
1.560 - if (!tryLock())
1.561 - scanAndLock(key, hash);
1.562 - V oldValue = null;
1.563 - try {
1.564 - HashEntry<K,V>[] tab = table;
1.565 - int index = (tab.length - 1) & hash;
1.566 - HashEntry<K,V> e = entryAt(tab, index);
1.567 - HashEntry<K,V> pred = null;
1.568 - while (e != null) {
1.569 - K k;
1.570 - HashEntry<K,V> next = e.next;
1.571 - if ((k = e.key) == key ||
1.572 - (e.hash == hash && key.equals(k))) {
1.573 - V v = e.value;
1.574 - if (value == null || value == v || value.equals(v)) {
1.575 - if (pred == null)
1.576 - setEntryAt(tab, index, next);
1.577 - else
1.578 - pred.setNext(next);
1.579 - ++modCount;
1.580 - --count;
1.581 - oldValue = v;
1.582 - }
1.583 - break;
1.584 - }
1.585 - pred = e;
1.586 - e = next;
1.587 - }
1.588 - } finally {
1.589 - unlock();
1.590 - }
1.591 - return oldValue;
1.592 - }
1.593 -
1.594 - final boolean replace(K key, int hash, V oldValue, V newValue) {
1.595 - if (!tryLock())
1.596 - scanAndLock(key, hash);
1.597 - boolean replaced = false;
1.598 - try {
1.599 - HashEntry<K,V> e;
1.600 - for (e = entryForHash(this, hash); e != null; e = e.next) {
1.601 - K k;
1.602 - if ((k = e.key) == key ||
1.603 - (e.hash == hash && key.equals(k))) {
1.604 - if (oldValue.equals(e.value)) {
1.605 - e.value = newValue;
1.606 - ++modCount;
1.607 - replaced = true;
1.608 - }
1.609 - break;
1.610 - }
1.611 - }
1.612 - } finally {
1.613 - unlock();
1.614 - }
1.615 - return replaced;
1.616 - }
1.617 -
1.618 - final V replace(K key, int hash, V value) {
1.619 - if (!tryLock())
1.620 - scanAndLock(key, hash);
1.621 - V oldValue = null;
1.622 - try {
1.623 - HashEntry<K,V> e;
1.624 - for (e = entryForHash(this, hash); e != null; e = e.next) {
1.625 - K k;
1.626 - if ((k = e.key) == key ||
1.627 - (e.hash == hash && key.equals(k))) {
1.628 - oldValue = e.value;
1.629 - e.value = value;
1.630 - ++modCount;
1.631 - break;
1.632 - }
1.633 - }
1.634 - } finally {
1.635 - unlock();
1.636 - }
1.637 - return oldValue;
1.638 - }
1.639 -
1.640 - final void clear() {
1.641 - lock();
1.642 - try {
1.643 - HashEntry<K,V>[] tab = table;
1.644 - for (int i = 0; i < tab.length ; i++)
1.645 - setEntryAt(tab, i, null);
1.646 - ++modCount;
1.647 - count = 0;
1.648 - } finally {
1.649 - unlock();
1.650 - }
1.651 - }
1.652 - }
1.653 -
1.654 - // Accessing segments
1.655 -
1.656 - /**
1.657 - * Gets the jth element of given segment array (if nonnull) with
1.658 - * volatile element access semantics via Unsafe. (The null check
1.659 - * can trigger harmlessly only during deserialization.) Note:
1.660 - * because each element of segments array is set only once (using
1.661 - * fully ordered writes), some performance-sensitive methods rely
1.662 - * on this method only as a recheck upon null reads.
1.663 - */
1.664 - @SuppressWarnings("unchecked")
1.665 - static final <K,V> Segment<K,V> segmentAt(Segment<K,V>[] ss, int j) {
1.666 - long u = (j << SSHIFT) + SBASE;
1.667 - return ss == null ? null :
1.668 - (Segment<K,V>) UNSAFE.getObjectVolatile(ss, u);
1.669 - }
1.670 -
1.671 - /**
1.672 - * Returns the segment for the given index, creating it and
1.673 - * recording in segment table (via CAS) if not already present.
1.674 - *
1.675 - * @param k the index
1.676 - * @return the segment
1.677 - */
1.678 - @SuppressWarnings("unchecked")
1.679 - private Segment<K,V> ensureSegment(int k) {
1.680 - final Segment<K,V>[] ss = this.segments;
1.681 - long u = (k << SSHIFT) + SBASE; // raw offset
1.682 - Segment<K,V> seg;
1.683 - if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
1.684 - Segment<K,V> proto = ss[0]; // use segment 0 as prototype
1.685 - int cap = proto.table.length;
1.686 - float lf = proto.loadFactor;
1.687 - int threshold = (int)(cap * lf);
1.688 - HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
1.689 - if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
1.690 - == null) { // recheck
1.691 - Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
1.692 - while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
1.693 - == null) {
1.694 - if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
1.695 - break;
1.696 - }
1.697 - }
1.698 - }
1.699 - return seg;
1.700 - }
1.701 -
1.702 - // Hash-based segment and entry accesses
1.703 -
1.704 - /**
1.705 - * Get the segment for the given hash
1.706 - */
1.707 - @SuppressWarnings("unchecked")
1.708 - private Segment<K,V> segmentForHash(int h) {
1.709 - long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
1.710 - return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);
1.711 - }
1.712 -
1.713 - /**
1.714 - * Gets the table entry for the given segment and hash
1.715 - */
1.716 - @SuppressWarnings("unchecked")
1.717 - static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) {
1.718 - HashEntry<K,V>[] tab;
1.719 - return (seg == null || (tab = seg.table) == null) ? null :
1.720 - (HashEntry<K,V>) UNSAFE.getObjectVolatile
1.721 - (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
1.722 - }
1.723 -
1.724 - /* ---------------- Public operations -------------- */
1.725
1.726 /**
1.727 * Creates a new, empty map with the specified initial
1.728 @@ -736,32 +146,7 @@
1.729 float loadFactor, int concurrencyLevel) {
1.730 if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
1.731 throw new IllegalArgumentException();
1.732 - if (concurrencyLevel > MAX_SEGMENTS)
1.733 - concurrencyLevel = MAX_SEGMENTS;
1.734 - // Find power-of-two sizes best matching arguments
1.735 - int sshift = 0;
1.736 - int ssize = 1;
1.737 - while (ssize < concurrencyLevel) {
1.738 - ++sshift;
1.739 - ssize <<= 1;
1.740 - }
1.741 - this.segmentShift = 32 - sshift;
1.742 - this.segmentMask = ssize - 1;
1.743 - if (initialCapacity > MAXIMUM_CAPACITY)
1.744 - initialCapacity = MAXIMUM_CAPACITY;
1.745 - int c = initialCapacity / ssize;
1.746 - if (c * ssize < initialCapacity)
1.747 - ++c;
1.748 - int cap = MIN_SEGMENT_TABLE_CAPACITY;
1.749 - while (cap < c)
1.750 - cap <<= 1;
1.751 - // create segments and segments[0]
1.752 - Segment<K,V> s0 =
1.753 - new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
1.754 - (HashEntry<K,V>[])new HashEntry[cap]);
1.755 - Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
1.756 - UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
1.757 - this.segments = ss;
1.758 + delegate = new HashMap<>(initialCapacity, loadFactor);
1.759 }
1.760
1.761 /**
1.762 @@ -817,706 +202,126 @@
1.763 DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
1.764 putAll(m);
1.765 }
1.766 +
1.767
1.768 - /**
1.769 - * Returns <tt>true</tt> if this map contains no key-value mappings.
1.770 - *
1.771 - * @return <tt>true</tt> if this map contains no key-value mappings
1.772 - */
1.773 - public boolean isEmpty() {
1.774 - /*
1.775 - * Sum per-segment modCounts to avoid mis-reporting when
1.776 - * elements are concurrently added and removed in one segment
1.777 - * while checking another, in which case the table was never
1.778 - * actually empty at any point. (The sum ensures accuracy up
1.779 - * through at least 1<<31 per-segment modifications before
1.780 - * recheck.) Methods size() and containsValue() use similar
1.781 - * constructions for stability checks.
1.782 - */
1.783 - long sum = 0L;
1.784 - final Segment<K,V>[] segments = this.segments;
1.785 - for (int j = 0; j < segments.length; ++j) {
1.786 - Segment<K,V> seg = segmentAt(segments, j);
1.787 - if (seg != null) {
1.788 - if (seg.count != 0)
1.789 - return false;
1.790 - sum += seg.modCount;
1.791 - }
1.792 - }
1.793 - if (sum != 0L) { // recheck unless no modifications
1.794 - for (int j = 0; j < segments.length; ++j) {
1.795 - Segment<K,V> seg = segmentAt(segments, j);
1.796 - if (seg != null) {
1.797 - if (seg.count != 0)
1.798 - return false;
1.799 - sum -= seg.modCount;
1.800 - }
1.801 - }
1.802 - if (sum != 0L)
1.803 - return false;
1.804 - }
1.805 - return true;
1.806 + @Override
1.807 + public int size() {
1.808 + return delegate.size();
1.809 }
1.810
1.811 - /**
1.812 - * Returns the number of key-value mappings in this map. If the
1.813 - * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
1.814 - * <tt>Integer.MAX_VALUE</tt>.
1.815 - *
1.816 - * @return the number of key-value mappings in this map
1.817 - */
1.818 - public int size() {
1.819 - // Try a few times to get accurate count. On failure due to
1.820 - // continuous async changes in table, resort to locking.
1.821 - final Segment<K,V>[] segments = this.segments;
1.822 - int size;
1.823 - boolean overflow; // true if size overflows 32 bits
1.824 - long sum; // sum of modCounts
1.825 - long last = 0L; // previous sum
1.826 - int retries = -1; // first iteration isn't retry
1.827 - try {
1.828 - for (;;) {
1.829 - if (retries++ == RETRIES_BEFORE_LOCK) {
1.830 - for (int j = 0; j < segments.length; ++j)
1.831 - ensureSegment(j).lock(); // force creation
1.832 - }
1.833 - sum = 0L;
1.834 - size = 0;
1.835 - overflow = false;
1.836 - for (int j = 0; j < segments.length; ++j) {
1.837 - Segment<K,V> seg = segmentAt(segments, j);
1.838 - if (seg != null) {
1.839 - sum += seg.modCount;
1.840 - int c = seg.count;
1.841 - if (c < 0 || (size += c) < 0)
1.842 - overflow = true;
1.843 - }
1.844 - }
1.845 - if (sum == last)
1.846 - break;
1.847 - last = sum;
1.848 - }
1.849 - } finally {
1.850 - if (retries > RETRIES_BEFORE_LOCK) {
1.851 - for (int j = 0; j < segments.length; ++j)
1.852 - segmentAt(segments, j).unlock();
1.853 - }
1.854 - }
1.855 - return overflow ? Integer.MAX_VALUE : size;
1.856 + @Override
1.857 + public boolean isEmpty() {
1.858 + return delegate.isEmpty();
1.859 }
1.860
1.861 - /**
1.862 - * Returns the value to which the specified key is mapped,
1.863 - * or {@code null} if this map contains no mapping for the key.
1.864 - *
1.865 - * <p>More formally, if this map contains a mapping from a key
1.866 - * {@code k} to a value {@code v} such that {@code key.equals(k)},
1.867 - * then this method returns {@code v}; otherwise it returns
1.868 - * {@code null}. (There can be at most one such mapping.)
1.869 - *
1.870 - * @throws NullPointerException if the specified key is null
1.871 - */
1.872 - public V get(Object key) {
1.873 - Segment<K,V> s; // manually integrate access methods to reduce overhead
1.874 - HashEntry<K,V>[] tab;
1.875 - int h = hash(key.hashCode());
1.876 - long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
1.877 - if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
1.878 - (tab = s.table) != null) {
1.879 - for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
1.880 - (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
1.881 - e != null; e = e.next) {
1.882 - K k;
1.883 - if ((k = e.key) == key || (e.hash == h && key.equals(k)))
1.884 - return e.value;
1.885 - }
1.886 - }
1.887 - return null;
1.888 + @Override
1.889 + public boolean containsKey(Object key) {
1.890 + return delegate.containsKey(key);
1.891 }
1.892
1.893 - /**
1.894 - * Tests if the specified object is a key in this table.
1.895 - *
1.896 - * @param key possible key
1.897 - * @return <tt>true</tt> if and only if the specified object
1.898 - * is a key in this table, as determined by the
1.899 - * <tt>equals</tt> method; <tt>false</tt> otherwise.
1.900 - * @throws NullPointerException if the specified key is null
1.901 - */
1.902 - @SuppressWarnings("unchecked")
1.903 - public boolean containsKey(Object key) {
1.904 - Segment<K,V> s; // same as get() except no need for volatile value read
1.905 - HashEntry<K,V>[] tab;
1.906 - int h = hash(key.hashCode());
1.907 - long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
1.908 - if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
1.909 - (tab = s.table) != null) {
1.910 - for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
1.911 - (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
1.912 - e != null; e = e.next) {
1.913 - K k;
1.914 - if ((k = e.key) == key || (e.hash == h && key.equals(k)))
1.915 - return true;
1.916 - }
1.917 - }
1.918 - return false;
1.919 + @Override
1.920 + public boolean containsValue(Object value) {
1.921 + return delegate.containsValue(value);
1.922 }
1.923
1.924 - /**
1.925 - * Returns <tt>true</tt> if this map maps one or more keys to the
1.926 - * specified value. Note: This method requires a full internal
1.927 - * traversal of the hash table, and so is much slower than
1.928 - * method <tt>containsKey</tt>.
1.929 - *
1.930 - * @param value value whose presence in this map is to be tested
1.931 - * @return <tt>true</tt> if this map maps one or more keys to the
1.932 - * specified value
1.933 - * @throws NullPointerException if the specified value is null
1.934 - */
1.935 - public boolean containsValue(Object value) {
1.936 - // Same idea as size()
1.937 - if (value == null)
1.938 - throw new NullPointerException();
1.939 - final Segment<K,V>[] segments = this.segments;
1.940 - boolean found = false;
1.941 - long last = 0;
1.942 - int retries = -1;
1.943 - try {
1.944 - outer: for (;;) {
1.945 - if (retries++ == RETRIES_BEFORE_LOCK) {
1.946 - for (int j = 0; j < segments.length; ++j)
1.947 - ensureSegment(j).lock(); // force creation
1.948 - }
1.949 - long hashSum = 0L;
1.950 - int sum = 0;
1.951 - for (int j = 0; j < segments.length; ++j) {
1.952 - HashEntry<K,V>[] tab;
1.953 - Segment<K,V> seg = segmentAt(segments, j);
1.954 - if (seg != null && (tab = seg.table) != null) {
1.955 - for (int i = 0 ; i < tab.length; i++) {
1.956 - HashEntry<K,V> e;
1.957 - for (e = entryAt(tab, i); e != null; e = e.next) {
1.958 - V v = e.value;
1.959 - if (v != null && value.equals(v)) {
1.960 - found = true;
1.961 - break outer;
1.962 - }
1.963 - }
1.964 - }
1.965 - sum += seg.modCount;
1.966 - }
1.967 - }
1.968 - if (retries > 0 && sum == last)
1.969 - break;
1.970 - last = sum;
1.971 - }
1.972 - } finally {
1.973 - if (retries > RETRIES_BEFORE_LOCK) {
1.974 - for (int j = 0; j < segments.length; ++j)
1.975 - segmentAt(segments, j).unlock();
1.976 - }
1.977 - }
1.978 - return found;
1.979 + @Override
1.980 + public V get(Object key) {
1.981 + return delegate.get(key);
1.982 }
1.983
1.984 - /**
1.985 - * Legacy method testing if some key maps into the specified value
1.986 - * in this table. This method is identical in functionality to
1.987 - * {@link #containsValue}, and exists solely to ensure
1.988 - * full compatibility with class {@link java.util.Hashtable},
1.989 - * which supported this method prior to introduction of the
1.990 - * Java Collections framework.
1.991 -
1.992 - * @param value a value to search for
1.993 - * @return <tt>true</tt> if and only if some key maps to the
1.994 - * <tt>value</tt> argument in this table as
1.995 - * determined by the <tt>equals</tt> method;
1.996 - * <tt>false</tt> otherwise
1.997 - * @throws NullPointerException if the specified value is null
1.998 - */
1.999 - public boolean contains(Object value) {
1.1000 - return containsValue(value);
1.1001 + @Override
1.1002 + public V put(K key, V value) {
1.1003 + return delegate.put(key, value);
1.1004 }
1.1005
1.1006 - /**
1.1007 - * Maps the specified key to the specified value in this table.
1.1008 - * Neither the key nor the value can be null.
1.1009 - *
1.1010 - * <p> The value can be retrieved by calling the <tt>get</tt> method
1.1011 - * with a key that is equal to the original key.
1.1012 - *
1.1013 - * @param key key with which the specified value is to be associated
1.1014 - * @param value value to be associated with the specified key
1.1015 - * @return the previous value associated with <tt>key</tt>, or
1.1016 - * <tt>null</tt> if there was no mapping for <tt>key</tt>
1.1017 - * @throws NullPointerException if the specified key or value is null
1.1018 - */
1.1019 - @SuppressWarnings("unchecked")
1.1020 - public V put(K key, V value) {
1.1021 - Segment<K,V> s;
1.1022 - if (value == null)
1.1023 - throw new NullPointerException();
1.1024 - int hash = hash(key.hashCode());
1.1025 - int j = (hash >>> segmentShift) & segmentMask;
1.1026 - if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
1.1027 - (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
1.1028 - s = ensureSegment(j);
1.1029 - return s.put(key, hash, value, false);
1.1030 + @Override
1.1031 + public V remove(Object key) {
1.1032 + return delegate.remove(key);
1.1033 }
1.1034
1.1035 - /**
1.1036 - * {@inheritDoc}
1.1037 - *
1.1038 - * @return the previous value associated with the specified key,
1.1039 - * or <tt>null</tt> if there was no mapping for the key
1.1040 - * @throws NullPointerException if the specified key or value is null
1.1041 - */
1.1042 - @SuppressWarnings("unchecked")
1.1043 - public V putIfAbsent(K key, V value) {
1.1044 - Segment<K,V> s;
1.1045 - if (value == null)
1.1046 - throw new NullPointerException();
1.1047 - int hash = hash(key.hashCode());
1.1048 - int j = (hash >>> segmentShift) & segmentMask;
1.1049 - if ((s = (Segment<K,V>)UNSAFE.getObject
1.1050 - (segments, (j << SSHIFT) + SBASE)) == null)
1.1051 - s = ensureSegment(j);
1.1052 - return s.put(key, hash, value, true);
1.1053 + @Override
1.1054 + public void putAll(Map<? extends K, ? extends V> m) {
1.1055 + delegate.putAll(m);
1.1056 }
1.1057
1.1058 - /**
1.1059 - * Copies all of the mappings from the specified map to this one.
1.1060 - * These mappings replace any mappings that this map had for any of the
1.1061 - * keys currently in the specified map.
1.1062 - *
1.1063 - * @param m mappings to be stored in this map
1.1064 - */
1.1065 - public void putAll(Map<? extends K, ? extends V> m) {
1.1066 - for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1.1067 - put(e.getKey(), e.getValue());
1.1068 + @Override
1.1069 + public void clear() {
1.1070 + delegate.clear();
1.1071 }
1.1072
1.1073 - /**
1.1074 - * Removes the key (and its corresponding value) from this map.
1.1075 - * This method does nothing if the key is not in the map.
1.1076 - *
1.1077 - * @param key the key that needs to be removed
1.1078 - * @return the previous value associated with <tt>key</tt>, or
1.1079 - * <tt>null</tt> if there was no mapping for <tt>key</tt>
1.1080 - * @throws NullPointerException if the specified key is null
1.1081 - */
1.1082 - public V remove(Object key) {
1.1083 - int hash = hash(key.hashCode());
1.1084 - Segment<K,V> s = segmentForHash(hash);
1.1085 - return s == null ? null : s.remove(key, hash, null);
1.1086 + @Override
1.1087 + public Set<K> keySet() {
1.1088 + return delegate.keySet();
1.1089 }
1.1090
1.1091 - /**
1.1092 - * {@inheritDoc}
1.1093 - *
1.1094 - * @throws NullPointerException if the specified key is null
1.1095 - */
1.1096 - public boolean remove(Object key, Object value) {
1.1097 - int hash = hash(key.hashCode());
1.1098 - Segment<K,V> s;
1.1099 - return value != null && (s = segmentForHash(hash)) != null &&
1.1100 - s.remove(key, hash, value) != null;
1.1101 + @Override
1.1102 + public Collection<V> values() {
1.1103 + return delegate.values();
1.1104 }
1.1105
1.1106 - /**
1.1107 - * {@inheritDoc}
1.1108 - *
1.1109 - * @throws NullPointerException if any of the arguments are null
1.1110 - */
1.1111 - public boolean replace(K key, V oldValue, V newValue) {
1.1112 - int hash = hash(key.hashCode());
1.1113 - if (oldValue == null || newValue == null)
1.1114 - throw new NullPointerException();
1.1115 - Segment<K,V> s = segmentForHash(hash);
1.1116 - return s != null && s.replace(key, hash, oldValue, newValue);
1.1117 + @Override
1.1118 + public Set<Entry<K, V>> entrySet() {
1.1119 + return delegate.entrySet();
1.1120 }
1.1121
1.1122 - /**
1.1123 - * {@inheritDoc}
1.1124 - *
1.1125 - * @return the previous value associated with the specified key,
1.1126 - * or <tt>null</tt> if there was no mapping for the key
1.1127 - * @throws NullPointerException if the specified key or value is null
1.1128 - */
1.1129 - public V replace(K key, V value) {
1.1130 - int hash = hash(key.hashCode());
1.1131 - if (value == null)
1.1132 - throw new NullPointerException();
1.1133 - Segment<K,V> s = segmentForHash(hash);
1.1134 - return s == null ? null : s.replace(key, hash, value);
1.1135 + @Override
1.1136 + public boolean equals(Object o) {
1.1137 + return delegate.equals(o);
1.1138 }
1.1139
1.1140 - /**
1.1141 - * Removes all of the mappings from this map.
1.1142 - */
1.1143 - public void clear() {
1.1144 - final Segment<K,V>[] segments = this.segments;
1.1145 - for (int j = 0; j < segments.length; ++j) {
1.1146 - Segment<K,V> s = segmentAt(segments, j);
1.1147 - if (s != null)
1.1148 - s.clear();
1.1149 + @Override
1.1150 + public int hashCode() {
1.1151 + return delegate.hashCode();
1.1152 + }
1.1153 +
1.1154 + @Override
1.1155 + public String toString() {
1.1156 + return delegate.toString();
1.1157 + }
1.1158 +
1.1159 + @Override
1.1160 + public V putIfAbsent(K key, V value) {
1.1161 + V old = delegate.get(key);
1.1162 + if (old == null) {
1.1163 + return delegate.put(key, value);
1.1164 + }
1.1165 + return old;
1.1166 + }
1.1167 +
1.1168 + @Override
1.1169 + public boolean remove(Object key, Object value) {
1.1170 + if (equals(value, delegate.get(key))) {
1.1171 + delegate.remove(key);
1.1172 + return true;
1.1173 + } else {
1.1174 + return false;
1.1175 }
1.1176 }
1.1177
1.1178 - /**
1.1179 - * Returns a {@link Set} view of the keys contained in this map.
1.1180 - * The set is backed by the map, so changes to the map are
1.1181 - * reflected in the set, and vice-versa. The set supports element
1.1182 - * removal, which removes the corresponding mapping from this map,
1.1183 - * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1.1184 - * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1.1185 - * operations. It does not support the <tt>add</tt> or
1.1186 - * <tt>addAll</tt> operations.
1.1187 - *
1.1188 - * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1.1189 - * that will never throw {@link ConcurrentModificationException},
1.1190 - * and guarantees to traverse elements as they existed upon
1.1191 - * construction of the iterator, and may (but is not guaranteed to)
1.1192 - * reflect any modifications subsequent to construction.
1.1193 - */
1.1194 - public Set<K> keySet() {
1.1195 - Set<K> ks = keySet;
1.1196 - return (ks != null) ? ks : (keySet = new KeySet());
1.1197 - }
1.1198 -
1.1199 - /**
1.1200 - * Returns a {@link Collection} view of the values contained in this map.
1.1201 - * The collection is backed by the map, so changes to the map are
1.1202 - * reflected in the collection, and vice-versa. The collection
1.1203 - * supports element removal, which removes the corresponding
1.1204 - * mapping from this map, via the <tt>Iterator.remove</tt>,
1.1205 - * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1.1206 - * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not
1.1207 - * support the <tt>add</tt> or <tt>addAll</tt> operations.
1.1208 - *
1.1209 - * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1.1210 - * that will never throw {@link ConcurrentModificationException},
1.1211 - * and guarantees to traverse elements as they existed upon
1.1212 - * construction of the iterator, and may (but is not guaranteed to)
1.1213 - * reflect any modifications subsequent to construction.
1.1214 - */
1.1215 - public Collection<V> values() {
1.1216 - Collection<V> vs = values;
1.1217 - return (vs != null) ? vs : (values = new Values());
1.1218 - }
1.1219 -
1.1220 - /**
1.1221 - * Returns a {@link Set} view of the mappings contained in this map.
1.1222 - * The set is backed by the map, so changes to the map are
1.1223 - * reflected in the set, and vice-versa. The set supports element
1.1224 - * removal, which removes the corresponding mapping from the map,
1.1225 - * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1.1226 - * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1.1227 - * operations. It does not support the <tt>add</tt> or
1.1228 - * <tt>addAll</tt> operations.
1.1229 - *
1.1230 - * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1.1231 - * that will never throw {@link ConcurrentModificationException},
1.1232 - * and guarantees to traverse elements as they existed upon
1.1233 - * construction of the iterator, and may (but is not guaranteed to)
1.1234 - * reflect any modifications subsequent to construction.
1.1235 - */
1.1236 - public Set<Map.Entry<K,V>> entrySet() {
1.1237 - Set<Map.Entry<K,V>> es = entrySet;
1.1238 - return (es != null) ? es : (entrySet = new EntrySet());
1.1239 - }
1.1240 -
1.1241 - /**
1.1242 - * Returns an enumeration of the keys in this table.
1.1243 - *
1.1244 - * @return an enumeration of the keys in this table
1.1245 - * @see #keySet()
1.1246 - */
1.1247 - public Enumeration<K> keys() {
1.1248 - return new KeyIterator();
1.1249 - }
1.1250 -
1.1251 - /**
1.1252 - * Returns an enumeration of the values in this table.
1.1253 - *
1.1254 - * @return an enumeration of the values in this table
1.1255 - * @see #values()
1.1256 - */
1.1257 - public Enumeration<V> elements() {
1.1258 - return new ValueIterator();
1.1259 - }
1.1260 -
1.1261 - /* ---------------- Iterator Support -------------- */
1.1262 -
1.1263 - abstract class HashIterator {
1.1264 - int nextSegmentIndex;
1.1265 - int nextTableIndex;
1.1266 - HashEntry<K,V>[] currentTable;
1.1267 - HashEntry<K, V> nextEntry;
1.1268 - HashEntry<K, V> lastReturned;
1.1269 -
1.1270 - HashIterator() {
1.1271 - nextSegmentIndex = segments.length - 1;
1.1272 - nextTableIndex = -1;
1.1273 - advance();
1.1274 - }
1.1275 -
1.1276 - /**
1.1277 - * Set nextEntry to first node of next non-empty table
1.1278 - * (in backwards order, to simplify checks).
1.1279 - */
1.1280 - final void advance() {
1.1281 - for (;;) {
1.1282 - if (nextTableIndex >= 0) {
1.1283 - if ((nextEntry = entryAt(currentTable,
1.1284 - nextTableIndex--)) != null)
1.1285 - break;
1.1286 - }
1.1287 - else if (nextSegmentIndex >= 0) {
1.1288 - Segment<K,V> seg = segmentAt(segments, nextSegmentIndex--);
1.1289 - if (seg != null && (currentTable = seg.table) != null)
1.1290 - nextTableIndex = currentTable.length - 1;
1.1291 - }
1.1292 - else
1.1293 - break;
1.1294 - }
1.1295 - }
1.1296 -
1.1297 - final HashEntry<K,V> nextEntry() {
1.1298 - HashEntry<K,V> e = nextEntry;
1.1299 - if (e == null)
1.1300 - throw new NoSuchElementException();
1.1301 - lastReturned = e; // cannot assign until after null check
1.1302 - if ((nextEntry = e.next) == null)
1.1303 - advance();
1.1304 - return e;
1.1305 - }
1.1306 -
1.1307 - public final boolean hasNext() { return nextEntry != null; }
1.1308 - public final boolean hasMoreElements() { return nextEntry != null; }
1.1309 -
1.1310 - public final void remove() {
1.1311 - if (lastReturned == null)
1.1312 - throw new IllegalStateException();
1.1313 - ConcurrentHashMap.this.remove(lastReturned.key);
1.1314 - lastReturned = null;
1.1315 + @Override
1.1316 + public boolean replace(K key, V oldValue, V newValue) {
1.1317 + if (equals(oldValue, delegate.get(key))) {
1.1318 + delegate.put(key, newValue);
1.1319 + return true;
1.1320 + } else {
1.1321 + return false;
1.1322 }
1.1323 }
1.1324
1.1325 - final class KeyIterator
1.1326 - extends HashIterator
1.1327 - implements Iterator<K>, Enumeration<K>
1.1328 - {
1.1329 - public final K next() { return super.nextEntry().key; }
1.1330 - public final K nextElement() { return super.nextEntry().key; }
1.1331 - }
1.1332 -
1.1333 - final class ValueIterator
1.1334 - extends HashIterator
1.1335 - implements Iterator<V>, Enumeration<V>
1.1336 - {
1.1337 - public final V next() { return super.nextEntry().value; }
1.1338 - public final V nextElement() { return super.nextEntry().value; }
1.1339 - }
1.1340 -
1.1341 - /**
1.1342 - * Custom Entry class used by EntryIterator.next(), that relays
1.1343 - * setValue changes to the underlying map.
1.1344 - */
1.1345 - final class WriteThroughEntry
1.1346 - extends AbstractMap.SimpleEntry<K,V>
1.1347 - {
1.1348 - WriteThroughEntry(K k, V v) {
1.1349 - super(k,v);
1.1350 - }
1.1351 -
1.1352 - /**
1.1353 - * Set our entry's value and write through to the map. The
1.1354 - * value to return is somewhat arbitrary here. Since a
1.1355 - * WriteThroughEntry does not necessarily track asynchronous
1.1356 - * changes, the most recent "previous" value could be
1.1357 - * different from what we return (or could even have been
1.1358 - * removed in which case the put will re-establish). We do not
1.1359 - * and cannot guarantee more.
1.1360 - */
1.1361 - public V setValue(V value) {
1.1362 - if (value == null) throw new NullPointerException();
1.1363 - V v = super.setValue(value);
1.1364 - ConcurrentHashMap.this.put(getKey(), value);
1.1365 - return v;
1.1366 + @Override
1.1367 + public V replace(K key, V value) {
1.1368 + if (delegate.containsKey(key)) {
1.1369 + return delegate.put(key, value);
1.1370 + } else {
1.1371 + return null;
1.1372 }
1.1373 }
1.1374 -
1.1375 - final class EntryIterator
1.1376 - extends HashIterator
1.1377 - implements Iterator<Entry<K,V>>
1.1378 - {
1.1379 - public Map.Entry<K,V> next() {
1.1380 - HashEntry<K,V> e = super.nextEntry();
1.1381 - return new WriteThroughEntry(e.key, e.value);
1.1382 +
1.1383 + private static boolean equals(Object a, Object b) {
1.1384 + if (a == null) {
1.1385 + return b == null;
1.1386 + } else {
1.1387 + return a.equals(b);
1.1388 }
1.1389 }
1.1390 -
1.1391 - final class KeySet extends AbstractSet<K> {
1.1392 - public Iterator<K> iterator() {
1.1393 - return new KeyIterator();
1.1394 - }
1.1395 - public int size() {
1.1396 - return ConcurrentHashMap.this.size();
1.1397 - }
1.1398 - public boolean isEmpty() {
1.1399 - return ConcurrentHashMap.this.isEmpty();
1.1400 - }
1.1401 - public boolean contains(Object o) {
1.1402 - return ConcurrentHashMap.this.containsKey(o);
1.1403 - }
1.1404 - public boolean remove(Object o) {
1.1405 - return ConcurrentHashMap.this.remove(o) != null;
1.1406 - }
1.1407 - public void clear() {
1.1408 - ConcurrentHashMap.this.clear();
1.1409 - }
1.1410 - }
1.1411 -
1.1412 - final class Values extends AbstractCollection<V> {
1.1413 - public Iterator<V> iterator() {
1.1414 - return new ValueIterator();
1.1415 - }
1.1416 - public int size() {
1.1417 - return ConcurrentHashMap.this.size();
1.1418 - }
1.1419 - public boolean isEmpty() {
1.1420 - return ConcurrentHashMap.this.isEmpty();
1.1421 - }
1.1422 - public boolean contains(Object o) {
1.1423 - return ConcurrentHashMap.this.containsValue(o);
1.1424 - }
1.1425 - public void clear() {
1.1426 - ConcurrentHashMap.this.clear();
1.1427 - }
1.1428 - }
1.1429 -
1.1430 - final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1.1431 - public Iterator<Map.Entry<K,V>> iterator() {
1.1432 - return new EntryIterator();
1.1433 - }
1.1434 - public boolean contains(Object o) {
1.1435 - if (!(o instanceof Map.Entry))
1.1436 - return false;
1.1437 - Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1.1438 - V v = ConcurrentHashMap.this.get(e.getKey());
1.1439 - return v != null && v.equals(e.getValue());
1.1440 - }
1.1441 - public boolean remove(Object o) {
1.1442 - if (!(o instanceof Map.Entry))
1.1443 - return false;
1.1444 - Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1.1445 - return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1.1446 - }
1.1447 - public int size() {
1.1448 - return ConcurrentHashMap.this.size();
1.1449 - }
1.1450 - public boolean isEmpty() {
1.1451 - return ConcurrentHashMap.this.isEmpty();
1.1452 - }
1.1453 - public void clear() {
1.1454 - ConcurrentHashMap.this.clear();
1.1455 - }
1.1456 - }
1.1457 -
1.1458 - /* ---------------- Serialization Support -------------- */
1.1459 -
1.1460 - /**
1.1461 - * Save the state of the <tt>ConcurrentHashMap</tt> instance to a
1.1462 - * stream (i.e., serialize it).
1.1463 - * @param s the stream
1.1464 - * @serialData
1.1465 - * the key (Object) and value (Object)
1.1466 - * for each key-value mapping, followed by a null pair.
1.1467 - * The key-value mappings are emitted in no particular order.
1.1468 - */
1.1469 - private void writeObject(java.io.ObjectOutputStream s) throws IOException {
1.1470 - // force all segments for serialization compatibility
1.1471 - for (int k = 0; k < segments.length; ++k)
1.1472 - ensureSegment(k);
1.1473 - s.defaultWriteObject();
1.1474 -
1.1475 - final Segment<K,V>[] segments = this.segments;
1.1476 - for (int k = 0; k < segments.length; ++k) {
1.1477 - Segment<K,V> seg = segmentAt(segments, k);
1.1478 - seg.lock();
1.1479 - try {
1.1480 - HashEntry<K,V>[] tab = seg.table;
1.1481 - for (int i = 0; i < tab.length; ++i) {
1.1482 - HashEntry<K,V> e;
1.1483 - for (e = entryAt(tab, i); e != null; e = e.next) {
1.1484 - s.writeObject(e.key);
1.1485 - s.writeObject(e.value);
1.1486 - }
1.1487 - }
1.1488 - } finally {
1.1489 - seg.unlock();
1.1490 - }
1.1491 - }
1.1492 - s.writeObject(null);
1.1493 - s.writeObject(null);
1.1494 - }
1.1495 -
1.1496 - /**
1.1497 - * Reconstitute the <tt>ConcurrentHashMap</tt> instance from a
1.1498 - * stream (i.e., deserialize it).
1.1499 - * @param s the stream
1.1500 - */
1.1501 - @SuppressWarnings("unchecked")
1.1502 - private void readObject(java.io.ObjectInputStream s)
1.1503 - throws IOException, ClassNotFoundException {
1.1504 - s.defaultReadObject();
1.1505 -
1.1506 - // Re-initialize segments to be minimally sized, and let grow.
1.1507 - int cap = MIN_SEGMENT_TABLE_CAPACITY;
1.1508 - final Segment<K,V>[] segments = this.segments;
1.1509 - for (int k = 0; k < segments.length; ++k) {
1.1510 - Segment<K,V> seg = segments[k];
1.1511 - if (seg != null) {
1.1512 - seg.threshold = (int)(cap * seg.loadFactor);
1.1513 - seg.table = (HashEntry<K,V>[]) new HashEntry[cap];
1.1514 - }
1.1515 - }
1.1516 -
1.1517 - // Read the keys and values, and put the mappings in the table
1.1518 - for (;;) {
1.1519 - K key = (K) s.readObject();
1.1520 - V value = (V) s.readObject();
1.1521 - if (key == null)
1.1522 - break;
1.1523 - put(key, value);
1.1524 - }
1.1525 - }
1.1526 -
1.1527 - // Unsafe mechanics
1.1528 - private static final sun.misc.Unsafe UNSAFE;
1.1529 - private static final long SBASE;
1.1530 - private static final int SSHIFT;
1.1531 - private static final long TBASE;
1.1532 - private static final int TSHIFT;
1.1533 -
1.1534 - static {
1.1535 - int ss, ts;
1.1536 - try {
1.1537 - UNSAFE = sun.misc.Unsafe.getUnsafe();
1.1538 - Class tc = HashEntry[].class;
1.1539 - Class sc = Segment[].class;
1.1540 - TBASE = UNSAFE.arrayBaseOffset(tc);
1.1541 - SBASE = UNSAFE.arrayBaseOffset(sc);
1.1542 - ts = UNSAFE.arrayIndexScale(tc);
1.1543 - ss = UNSAFE.arrayIndexScale(sc);
1.1544 - } catch (Exception e) {
1.1545 - throw new Error(e);
1.1546 - }
1.1547 - if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0)
1.1548 - throw new Error("data type scale not a power of two");
1.1549 - SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
1.1550 - TSHIFT = 31 - Integer.numberOfLeadingZeros(ts);
1.1551 - }
1.1552 -
1.1553 }