20 |
|
import java.util.ConcurrentModificationException; |
21 |
|
import java.util.NoSuchElementException; |
22 |
|
import java.util.concurrent.ConcurrentMap; |
23 |
+ |
import java.util.concurrent.ThreadLocalRandom; |
24 |
|
import java.util.concurrent.locks.LockSupport; |
25 |
|
import java.io.Serializable; |
26 |
|
|
72 |
|
* versions of this class, constructors may optionally specify an |
73 |
|
* expected {@code concurrencyLevel} as an additional hint for |
74 |
|
* internal sizing. Note that using many keys with exactly the same |
75 |
< |
* {@code hashCode{}} is a sure way to slow down performance of any |
75 |
> |
* {@code hashCode()} is a sure way to slow down performance of any |
76 |
|
* hash table. |
77 |
|
* |
78 |
|
* <p>This class and its views and iterators implement all of the |
352 |
|
* Encodings for special uses of Node hash fields. See above for |
353 |
|
* explanation. |
354 |
|
*/ |
355 |
< |
static final int MOVED = 0x80000000; // hash field for fowarding nodes |
355 |
> |
static final int MOVED = 0x80000000; // hash field for forwarding nodes |
356 |
|
static final int LOCKED = 0x40000000; // set/tested only as a bit |
357 |
|
static final int WAITING = 0xc0000000; // both bits set/tested together |
358 |
|
static final int HASH_BITS = 0x3fffffff; // usable bits of normal node hash |
392 |
|
/** |
393 |
|
* Key-value entry. Note that this is never exported out as a |
394 |
|
* user-visible Map.Entry (see WriteThroughEntry and SnapshotEntry |
395 |
< |
* below). Nodes with a negative hash field are special, and do |
395 |
> |
* below). Nodes with a hash field of MOVED are special, and do |
396 |
|
* not contain user keys or values. Otherwise, keys are never |
397 |
|
* null, and null val fields indicate that a node is in the |
398 |
|
* process of being deleted or created. For purposes of read-only |
436 |
|
*/ |
437 |
|
final void tryAwaitLock(Node[] tab, int i) { |
438 |
|
if (tab != null && i >= 0 && i < tab.length) { // bounds check |
439 |
+ |
int r = ThreadLocalRandom.current().nextInt(); // randomize spins |
440 |
|
int spins = MAX_SPINS, h; |
441 |
|
while (tabAt(tab, i) == this && ((h = hash) & LOCKED) != 0) { |
442 |
|
if (spins >= 0) { |
443 |
< |
if (--spins == MAX_SPINS >>> 1) |
444 |
< |
Thread.yield(); // heuristically yield mid-way |
443 |
> |
r ^= r << 1; r ^= r >>> 3; r ^= r << 10; // xorshift |
444 |
> |
if (r >= 0 && --spins == 0) |
445 |
> |
Thread.yield(); // yield before block |
446 |
|
} |
447 |
|
else if (casHash(h, h | WAITING)) { |
448 |
|
synchronized (this) { |
598 |
|
} finally { |
599 |
|
if (!f.casHash(fh | LOCKED, fh)) { |
600 |
|
f.hash = fh; |
601 |
< |
synchronized(f) { f.notifyAll(); }; |
601 |
> |
synchronized (f) { f.notifyAll(); }; |
602 |
|
} |
603 |
|
} |
604 |
|
if (validated) { |
755 |
|
} finally { |
756 |
|
if (!f.casHash(fh | LOCKED, fh)) { |
757 |
|
f.hash = fh; |
758 |
< |
synchronized(f) { f.notifyAll(); }; |
758 |
> |
synchronized (f) { f.notifyAll(); }; |
759 |
|
} |
760 |
|
} |
761 |
|
if (validated) { |
792 |
|
setTabAt(tab, i, null); |
793 |
|
if (!node.casHash(fh, h)) { |
794 |
|
node.hash = h; |
795 |
< |
synchronized(node) { node.notifyAll(); }; |
795 |
> |
synchronized (node) { node.notifyAll(); }; |
796 |
|
} |
797 |
|
} |
798 |
|
} |
846 |
|
} finally { |
847 |
|
if (!f.casHash(fh | LOCKED, fh)) { |
848 |
|
f.hash = fh; |
849 |
< |
synchronized(f) { f.notifyAll(); }; |
849 |
> |
synchronized (f) { f.notifyAll(); }; |
850 |
|
} |
851 |
|
} |
852 |
|
if (validated) |
937 |
|
break; |
938 |
|
} |
939 |
|
} |
940 |
+ |
if (val == null) |
941 |
+ |
throw new NullPointerException(); |
942 |
|
if (added) { |
943 |
|
counter.add(1L); |
944 |
|
if (checkSize) |
945 |
|
checkForResize(); |
946 |
|
} |
942 |
– |
else if (val == null) |
943 |
– |
throw new NullPointerException(); |
947 |
|
return val; |
948 |
|
} |
949 |
|
|
1005 |
|
} finally { |
1006 |
|
if (!f.casHash(fh | LOCKED, fh)) { |
1007 |
|
f.hash = fh; |
1008 |
< |
synchronized(f) { f.notifyAll(); }; |
1008 |
> |
synchronized (f) { f.notifyAll(); }; |
1009 |
|
} |
1010 |
|
} |
1011 |
|
if (validated) { |
1102 |
|
while ((sc = sizeCtl) >= 0) { |
1103 |
|
Node[] tab = table; int n; |
1104 |
|
if (tab == null || (n = tab.length) == 0) { |
1105 |
< |
n = (sc > c)? sc : c; |
1105 |
> |
n = (sc > c) ? sc : c; |
1106 |
|
if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) { |
1107 |
|
try { |
1108 |
|
if (table == tab) { |
1153 |
|
continue; |
1154 |
|
} |
1155 |
|
else { // transiently use a locked forwarding node |
1156 |
< |
Node g = new Node(MOVED|LOCKED, nextTab, null, null); |
1156 |
> |
Node g = new Node(MOVED|LOCKED, nextTab, null, null); |
1157 |
|
if (!casTabAt(tab, i, f, g)) |
1158 |
|
continue; |
1159 |
|
setTabAt(nextTab, i, null); |
1274 |
|
} finally { |
1275 |
|
if (!f.casHash(fh | LOCKED, fh)) { |
1276 |
|
f.hash = fh; |
1277 |
< |
synchronized(f) { f.notifyAll(); }; |
1277 |
> |
synchronized (f) { f.notifyAll(); }; |
1278 |
|
} |
1279 |
|
} |
1280 |
|
if (validated) |
1294 |
|
* |
1295 |
|
* At each step, the iterator snapshots the key ("nextKey") and |
1296 |
|
* value ("nextVal") of a valid node (i.e., one that, at point of |
1297 |
< |
* snapshot, has a nonnull user value). Because val fields can |
1297 |
> |
* snapshot, has a non-null user value). Because val fields can |
1298 |
|
* change (including to null, indicating deletion), field nextVal |
1299 |
|
* might not be accurate at point of use, but still maintains the |
1300 |
|
* weak consistency property of holding a value that was once |
1463 |
|
if (initialCapacity < concurrencyLevel) // Use at least as many bins |
1464 |
|
initialCapacity = concurrencyLevel; // as estimated threads |
1465 |
|
long size = (long)(1.0 + (long)initialCapacity / loadFactor); |
1466 |
< |
int cap = ((size >= (long)MAXIMUM_CAPACITY) ? |
1467 |
< |
MAXIMUM_CAPACITY: tableSizeFor((int)size)); |
1466 |
> |
int cap = ((size >= (long)MAXIMUM_CAPACITY) ? |
1467 |
> |
MAXIMUM_CAPACITY: tableSizeFor((int)size)); |
1468 |
|
this.counter = new LongAdder(); |
1469 |
|
this.sizeCtl = cap; |
1470 |
|
} |
1692 |
|
* @throws IllegalStateException if the computation detectably |
1693 |
|
* attempts a recursive update to this map that would |
1694 |
|
* otherwise never complete |
1695 |
< |
* @throws RuntimeException or Error if the mappingFunction does so, |
1695 |
> |
* @throws RuntimeException or Error if the remappingFunction does so, |
1696 |
|
* in which case the mapping is unchanged |
1697 |
|
*/ |
1698 |
|
@SuppressWarnings("unchecked") |
2190 |
|
return true; |
2191 |
|
} |
2192 |
|
|
2193 |
< |
public final boolean removeAll(Collection c) { |
2193 |
> |
public final boolean removeAll(Collection<?> c) { |
2194 |
|
boolean modified = false; |
2195 |
|
for (Iterator<?> it = iter(); it.hasNext();) { |
2196 |
|
if (c.contains(it.next())) { |
2240 |
|
} |
2241 |
|
|
2242 |
|
static final class Values<K,V> extends MapView<K,V> |
2243 |
< |
implements Collection<V> { |
2243 |
> |
implements Collection<V> { |
2244 |
|
Values(ConcurrentHashMapV8<K, V> map) { super(map); } |
2245 |
|
public final boolean contains(Object o) { return map.containsValue(o); } |
2246 |
|
|
2270 |
|
} |
2271 |
|
} |
2272 |
|
|
2273 |
< |
static final class EntrySet<K,V> extends MapView<K,V> |
2273 |
> |
static final class EntrySet<K,V> extends MapView<K,V> |
2274 |
|
implements Set<Map.Entry<K,V>> { |
2275 |
|
EntrySet(ConcurrentHashMapV8<K, V> map) { super(map); } |
2276 |
|
|
2404 |
|
} |
2405 |
|
table = tab; |
2406 |
|
counter.add(size); |
2407 |
< |
sc = n - (n >>> 2) - 1; |
2407 |
> |
sc = n - (n >>> 2); |
2408 |
|
} |
2409 |
|
} finally { |
2410 |
|
sizeCtl = sc; |