224 |
|
* <p>All arguments to all task methods must be non-null. |
225 |
|
* |
226 |
|
* <p>This class is a member of the |
227 |
< |
* <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework"> |
227 |
> |
* <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework"> |
228 |
|
* Java Collections Framework</a>. |
229 |
|
* |
230 |
|
* @since 1.5 |
356 |
|
* cases where old nodes can be reused because their next fields |
357 |
|
* won't change. On average, only about one-sixth of them need |
358 |
|
* cloning when a table doubles. The nodes they replace will be |
359 |
< |
* garbage collectable as soon as they are no longer referenced by |
359 |
> |
* garbage collectible as soon as they are no longer referenced by |
360 |
|
* any reader thread that may be in the midst of concurrently |
361 |
|
* traversing table. Upon transfer, the old table bin contains |
362 |
|
* only a special forwarding node (with hash field "MOVED") that |
673 |
|
* See Hackers Delight, sec 3.2 |
674 |
|
*/ |
675 |
|
private static final int tableSizeFor(int c) { |
676 |
< |
int n = c - 1; |
677 |
< |
n |= n >>> 1; |
678 |
< |
n |= n >>> 2; |
679 |
< |
n |= n >>> 4; |
680 |
< |
n |= n >>> 8; |
681 |
< |
n |= n >>> 16; |
676 |
> |
int n = -1 >>> Integer.numberOfLeadingZeros(c - 1); |
677 |
|
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; |
678 |
|
} |
679 |
|
|
728 |
|
|
729 |
|
@SuppressWarnings("unchecked") |
730 |
|
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) { |
731 |
< |
return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE); |
731 |
> |
return (Node<K,V>)U.getReferenceAcquire(tab, ((long)i << ASHIFT) + ABASE); |
732 |
|
} |
733 |
|
|
734 |
|
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, |
735 |
|
Node<K,V> c, Node<K,V> v) { |
736 |
< |
return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v); |
736 |
> |
return U.compareAndSetReference(tab, ((long)i << ASHIFT) + ABASE, c, v); |
737 |
|
} |
738 |
|
|
739 |
|
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) { |
740 |
< |
U.putObjectRelease(tab, ((long)i << ASHIFT) + ABASE, v); |
740 |
> |
U.putReferenceRelease(tab, ((long)i << ASHIFT) + ABASE, v); |
741 |
|
} |
742 |
|
|
743 |
|
/* ---------------- Fields -------------- */ |
810 |
|
* elements is negative |
811 |
|
*/ |
812 |
|
public ConcurrentHashMap(int initialCapacity) { |
813 |
< |
if (initialCapacity < 0) |
819 |
< |
throw new IllegalArgumentException(); |
820 |
< |
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? |
821 |
< |
MAXIMUM_CAPACITY : |
822 |
< |
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)); |
823 |
< |
this.sizeCtl = cap; |
813 |
> |
this(initialCapacity, LOAD_FACTOR, 1); |
814 |
|
} |
815 |
|
|
816 |
|
/** |
844 |
|
|
845 |
|
/** |
846 |
|
* Creates a new, empty map with an initial table size based on |
847 |
< |
* the given number of elements ({@code initialCapacity}), table |
848 |
< |
* density ({@code loadFactor}), and number of concurrently |
847 |
> |
* the given number of elements ({@code initialCapacity}), initial |
848 |
> |
* table density ({@code loadFactor}), and number of concurrently |
849 |
|
* updating threads ({@code concurrencyLevel}). |
850 |
|
* |
851 |
|
* @param initialCapacity the initial capacity. The implementation |
1434 |
|
if (size == 0L) |
1435 |
|
sizeCtl = 0; |
1436 |
|
else { |
1437 |
< |
int n; |
1438 |
< |
if (size >= (long)(MAXIMUM_CAPACITY >>> 1)) |
1439 |
< |
n = MAXIMUM_CAPACITY; |
1450 |
< |
else { |
1451 |
< |
int sz = (int)size; |
1452 |
< |
n = tableSizeFor(sz + (sz >>> 1) + 1); |
1453 |
< |
} |
1437 |
> |
long ts = (long)(1.0 + size / LOAD_FACTOR); |
1438 |
> |
int n = (ts >= (long)MAXIMUM_CAPACITY) ? |
1439 |
> |
MAXIMUM_CAPACITY : tableSizeFor((int)ts); |
1440 |
|
@SuppressWarnings("unchecked") |
1441 |
|
Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n]; |
1442 |
|
int mask = n - 1; |
1638 |
|
* If the specified key is not already associated with a value, |
1639 |
|
* attempts to compute its value using the given mapping function |
1640 |
|
* and enters it into this map unless {@code null}. The entire |
1641 |
< |
* method invocation is performed atomically, so the function is |
1642 |
< |
* applied at most once per key. Some attempted update operations |
1643 |
< |
* on this map by other threads may be blocked while computation |
1644 |
< |
* is in progress, so the computation should be short and simple, |
1645 |
< |
* and must not attempt to update any other mappings of this map. |
1641 |
> |
* method invocation is performed atomically. The supplied |
1642 |
> |
* function is invoked exactly once per invocation of this method |
1643 |
> |
* if the key is absent, else not at all. Some attempted update |
1644 |
> |
* operations on this map by other threads may be blocked while |
1645 |
> |
* computation is in progress, so the computation should be short |
1646 |
> |
* and simple. |
1647 |
> |
* |
1648 |
> |
* <p>The mapping function must not modify this map during computation. |
1649 |
|
* |
1650 |
|
* @param key key with which the specified value is to be associated |
1651 |
|
* @param mappingFunction the function to compute a value |
1752 |
|
* If the value for the specified key is present, attempts to |
1753 |
|
* compute a new mapping given the key and its current mapped |
1754 |
|
* value. The entire method invocation is performed atomically. |
1755 |
< |
* Some attempted update operations on this map by other threads |
1756 |
< |
* may be blocked while computation is in progress, so the |
1757 |
< |
* computation should be short and simple, and must not attempt to |
1758 |
< |
* update any other mappings of this map. |
1755 |
> |
* The supplied function is invoked exactly once per invocation of |
1756 |
> |
* this method if the key is present, else not at all. Some |
1757 |
> |
* attempted update operations on this map by other threads may be |
1758 |
> |
* blocked while computation is in progress, so the computation |
1759 |
> |
* should be short and simple. |
1760 |
> |
* |
1761 |
> |
* <p>The remapping function must not modify this map during computation. |
1762 |
|
* |
1763 |
|
* @param key key with which a value may be associated |
1764 |
|
* @param remappingFunction the function to compute a value |
1847 |
|
* Attempts to compute a mapping for the specified key and its |
1848 |
|
* current mapped value (or {@code null} if there is no current |
1849 |
|
* mapping). The entire method invocation is performed atomically. |
1850 |
< |
* Some attempted update operations on this map by other threads |
1851 |
< |
* may be blocked while computation is in progress, so the |
1852 |
< |
* computation should be short and simple, and must not attempt to |
1853 |
< |
* update any other mappings of this Map. |
1850 |
> |
* The supplied function is invoked exactly once per invocation of |
1851 |
> |
* this method. Some attempted update operations on this map by |
1852 |
> |
* other threads may be blocked while computation is in progress, |
1853 |
> |
* so the computation should be short and simple. |
1854 |
> |
* |
1855 |
> |
* <p>The remapping function must not modify this map during computation. |
1856 |
|
* |
1857 |
|
* @param key key with which the specified value is to be associated |
1858 |
|
* @param remappingFunction the function to compute a value |
2313 |
|
Node<K,V>[] tab, nt; int n, sc; |
2314 |
|
while (s >= (long)(sc = sizeCtl) && (tab = table) != null && |
2315 |
|
(n = tab.length) < MAXIMUM_CAPACITY) { |
2316 |
< |
int rs = resizeStamp(n); |
2316 |
> |
int rs = resizeStamp(n) << RESIZE_STAMP_SHIFT; |
2317 |
|
if (sc < 0) { |
2318 |
< |
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || |
2319 |
< |
sc == rs + MAX_RESIZERS || (nt = nextTable) == null || |
2326 |
< |
transferIndex <= 0) |
2318 |
> |
if (sc == rs + MAX_RESIZERS || sc == rs + 1 || |
2319 |
> |
(nt = nextTable) == null || transferIndex <= 0) |
2320 |
|
break; |
2321 |
|
if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) |
2322 |
|
transfer(tab, nt); |
2323 |
|
} |
2324 |
< |
else if (U.compareAndSetInt(this, SIZECTL, sc, |
2332 |
< |
(rs << RESIZE_STAMP_SHIFT) + 2)) |
2324 |
> |
else if (U.compareAndSetInt(this, SIZECTL, sc, rs + 2)) |
2325 |
|
transfer(tab, null); |
2326 |
|
s = sumCount(); |
2327 |
|
} |
2335 |
|
Node<K,V>[] nextTab; int sc; |
2336 |
|
if (tab != null && (f instanceof ForwardingNode) && |
2337 |
|
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) { |
2338 |
< |
int rs = resizeStamp(tab.length); |
2338 |
> |
int rs = resizeStamp(tab.length) << RESIZE_STAMP_SHIFT; |
2339 |
|
while (nextTab == nextTable && table == tab && |
2340 |
|
(sc = sizeCtl) < 0) { |
2341 |
< |
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || |
2342 |
< |
sc == rs + MAX_RESIZERS || transferIndex <= 0) |
2341 |
> |
if (sc == rs + MAX_RESIZERS || sc == rs + 1 || |
2342 |
> |
transferIndex <= 0) |
2343 |
|
break; |
2344 |
|
if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) { |
2345 |
|
transfer(tab, nextTab); |
2519 |
|
setTabAt(tab, i, fwd); |
2520 |
|
advance = true; |
2521 |
|
} |
2522 |
+ |
else if (f instanceof ReservationNode) |
2523 |
+ |
throw new IllegalStateException("Recursive update"); |
2524 |
|
} |
2525 |
|
} |
2526 |
|
} |
3265 |
|
return true; |
3266 |
|
} |
3267 |
|
|
3268 |
< |
private static final Unsafe U = Unsafe.getUnsafe(); |
3269 |
< |
private static final long LOCKSTATE; |
3276 |
< |
static { |
3277 |
< |
try { |
3278 |
< |
LOCKSTATE = U.objectFieldOffset |
3279 |
< |
(TreeBin.class.getDeclaredField("lockState")); |
3280 |
< |
} catch (ReflectiveOperationException e) { |
3281 |
< |
throw new ExceptionInInitializerError(e); |
3282 |
< |
} |
3283 |
< |
} |
3268 |
> |
private static final long LOCKSTATE |
3269 |
> |
= U.objectFieldOffset(TreeBin.class, "lockState"); |
3270 |
|
} |
3271 |
|
|
3272 |
|
/* ----------------Table Traversal -------------- */ |
4563 |
|
public static class KeySetView<K,V> extends CollectionView<K,V,K> |
4564 |
|
implements Set<K>, java.io.Serializable { |
4565 |
|
private static final long serialVersionUID = 7249069246763182397L; |
4566 |
+ |
@SuppressWarnings("serial") // Conditionally serializable |
4567 |
|
private final V value; |
4568 |
|
KeySetView(ConcurrentHashMap<K,V> map, V value) { // non-public |
4569 |
|
super(map); |
6324 |
|
|
6325 |
|
// Unsafe mechanics |
6326 |
|
private static final Unsafe U = Unsafe.getUnsafe(); |
6327 |
< |
private static final long SIZECTL; |
6328 |
< |
private static final long TRANSFERINDEX; |
6329 |
< |
private static final long BASECOUNT; |
6330 |
< |
private static final long CELLSBUSY; |
6331 |
< |
private static final long CELLVALUE; |
6332 |
< |
private static final int ABASE; |
6327 |
> |
private static final long SIZECTL |
6328 |
> |
= U.objectFieldOffset(ConcurrentHashMap.class, "sizeCtl"); |
6329 |
> |
private static final long TRANSFERINDEX |
6330 |
> |
= U.objectFieldOffset(ConcurrentHashMap.class, "transferIndex"); |
6331 |
> |
private static final long BASECOUNT |
6332 |
> |
= U.objectFieldOffset(ConcurrentHashMap.class, "baseCount"); |
6333 |
> |
private static final long CELLSBUSY |
6334 |
> |
= U.objectFieldOffset(ConcurrentHashMap.class, "cellsBusy"); |
6335 |
> |
private static final long CELLVALUE |
6336 |
> |
= U.objectFieldOffset(CounterCell.class, "value"); |
6337 |
> |
private static final int ABASE = U.arrayBaseOffset(Node[].class); |
6338 |
|
private static final int ASHIFT; |
6339 |
|
|
6340 |
|
static { |
6341 |
< |
try { |
6342 |
< |
SIZECTL = U.objectFieldOffset |
6343 |
< |
(ConcurrentHashMap.class.getDeclaredField("sizeCtl")); |
6344 |
< |
TRANSFERINDEX = U.objectFieldOffset |
6353 |
< |
(ConcurrentHashMap.class.getDeclaredField("transferIndex")); |
6354 |
< |
BASECOUNT = U.objectFieldOffset |
6355 |
< |
(ConcurrentHashMap.class.getDeclaredField("baseCount")); |
6356 |
< |
CELLSBUSY = U.objectFieldOffset |
6357 |
< |
(ConcurrentHashMap.class.getDeclaredField("cellsBusy")); |
6358 |
< |
|
6359 |
< |
CELLVALUE = U.objectFieldOffset |
6360 |
< |
(CounterCell.class.getDeclaredField("value")); |
6361 |
< |
|
6362 |
< |
ABASE = U.arrayBaseOffset(Node[].class); |
6363 |
< |
int scale = U.arrayIndexScale(Node[].class); |
6364 |
< |
if ((scale & (scale - 1)) != 0) |
6365 |
< |
throw new Error("array index scale not a power of two"); |
6366 |
< |
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale); |
6367 |
< |
} catch (ReflectiveOperationException e) { |
6368 |
< |
throw new ExceptionInInitializerError(e); |
6369 |
< |
} |
6341 |
> |
int scale = U.arrayIndexScale(Node[].class); |
6342 |
> |
if ((scale & (scale - 1)) != 0) |
6343 |
> |
throw new ExceptionInInitializerError("array index scale not a power of two"); |
6344 |
> |
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale); |
6345 |
|
|
6346 |
|
// Reduce the risk of rare disastrous classloading in first call to |
6347 |
|
// LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773 |
6348 |
|
Class<?> ensureLoaded = LockSupport.class; |
6349 |
+ |
|
6350 |
+ |
// Eager class load observed to help JIT during startup |
6351 |
+ |
ensureLoaded = ReservationNode.class; |
6352 |
|
} |
6353 |
|
} |