--- jsr166/src/jsr166e/ConcurrentHashMapV8.java 2011/10/02 22:01:06 1.27 +++ jsr166/src/jsr166e/ConcurrentHashMapV8.java 2012/03/04 20:34:27 1.37 @@ -20,6 +20,7 @@ import java.util.Enumeration; import java.util.ConcurrentModificationException; import java.util.NoSuchElementException; import java.util.concurrent.ConcurrentMap; +import java.util.concurrent.ThreadLocalRandom; import java.util.concurrent.locks.LockSupport; import java.io.Serializable; @@ -71,7 +72,7 @@ import java.io.Serializable; * versions of this class, constructors may optionally specify an * expected {@code concurrencyLevel} as an additional hint for * internal sizing. Note that using many keys with exactly the same - * {@code hashCode{}} is a sure way to slow down performance of any + * {@code hashCode()} is a sure way to slow down performance of any * hash table. * *

This class and its views and iterators implement all of the @@ -351,7 +352,7 @@ public class ConcurrentHashMapV8 * Encodings for special uses of Node hash fields. See above for * explanation. */ - static final int MOVED = 0x80000000; // hash field for fowarding nodes + static final int MOVED = 0x80000000; // hash field for forwarding nodes static final int LOCKED = 0x40000000; // set/tested only as a bit static final int WAITING = 0xc0000000; // both bits set/tested together static final int HASH_BITS = 0x3fffffff; // usable bits of normal node hash @@ -391,7 +392,7 @@ public class ConcurrentHashMapV8 /** * Key-value entry. Note that this is never exported out as a * user-visible Map.Entry (see WriteThroughEntry and SnapshotEntry - * below). Nodes with a negative hash field are special, and do + * below). Nodes with a hash field of MOVED are special, and do * not contain user keys or values. Otherwise, keys are never * null, and null val fields indicate that a node is in the * process of being deleted or created. For purposes of read-only @@ -435,11 +436,13 @@ public class ConcurrentHashMapV8 */ final void tryAwaitLock(Node[] tab, int i) { if (tab != null && i >= 0 && i < tab.length) { // bounds check + int r = ThreadLocalRandom.current().nextInt(); // randomize spins int spins = MAX_SPINS, h; while (tabAt(tab, i) == this && ((h = hash) & LOCKED) != 0) { if (spins >= 0) { - if (--spins == MAX_SPINS >>> 1) - Thread.yield(); // heuristically yield mid-way + r ^= r << 1; r ^= r >>> 3; r ^= r << 10; // xorshift + if (r >= 0 && --spins == 0) + Thread.yield(); // yield before block } else if (casHash(h, h | WAITING)) { synchronized (this) { @@ -595,7 +598,7 @@ public class ConcurrentHashMapV8 } finally { if (!f.casHash(fh | LOCKED, fh)) { f.hash = fh; - synchronized(f) { f.notifyAll(); }; + synchronized (f) { f.notifyAll(); }; } } if (validated) { @@ -752,7 +755,7 @@ public class ConcurrentHashMapV8 } finally { if (!f.casHash(fh | LOCKED, fh)) { f.hash = fh; - synchronized(f) { f.notifyAll(); }; + synchronized (f) { f.notifyAll(); }; } } if (validated) { @@ -789,7 +792,7 @@ public class ConcurrentHashMapV8 setTabAt(tab, i, null); if (!node.casHash(fh, h)) { node.hash = h; - synchronized(node) { node.notifyAll(); }; + synchronized (node) { node.notifyAll(); }; } } } @@ -843,7 +846,7 @@ public class ConcurrentHashMapV8 } finally { if (!f.casHash(fh | LOCKED, fh)) { f.hash = fh; - synchronized(f) { f.notifyAll(); }; + synchronized (f) { f.notifyAll(); }; } } if (validated) @@ -934,13 +937,13 @@ public class ConcurrentHashMapV8 break; } } + if (val == null) + throw new NullPointerException(); if (added) { counter.add(1L); if (checkSize) checkForResize(); } - else if (val == null) - throw new NullPointerException(); return val; } @@ -1002,7 +1005,7 @@ public class ConcurrentHashMapV8 } finally { if (!f.casHash(fh | LOCKED, fh)) { f.hash = fh; - synchronized(f) { f.notifyAll(); }; + synchronized (f) { f.notifyAll(); }; } } if (validated) { @@ -1099,7 +1102,7 @@ public class ConcurrentHashMapV8 while ((sc = sizeCtl) >= 0) { Node[] tab = table; int n; if (tab == null || (n = tab.length) == 0) { - n = (sc > c)? sc : c; + n = (sc > c) ? sc : c; if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) { try { if (table == tab) { @@ -1150,7 +1153,7 @@ public class ConcurrentHashMapV8 continue; } else { // transiently use a locked forwarding node - Node g = new Node(MOVED|LOCKED, nextTab, null, null); + Node g = new Node(MOVED|LOCKED, nextTab, null, null); if (!casTabAt(tab, i, f, g)) continue; setTabAt(nextTab, i, null); @@ -1271,7 +1274,7 @@ public class ConcurrentHashMapV8 } finally { if (!f.casHash(fh | LOCKED, fh)) { f.hash = fh; - synchronized(f) { f.notifyAll(); }; + synchronized (f) { f.notifyAll(); }; } } if (validated) @@ -1291,7 +1294,7 @@ public class ConcurrentHashMapV8 * * At each step, the iterator snapshots the key ("nextKey") and * value ("nextVal") of a valid node (i.e., one that, at point of - * snapshot, has a nonnull user value). Because val fields can + * snapshot, has a non-null user value). Because val fields can * change (including to null, indicating deletion), field nextVal * might not be accurate at point of use, but still maintains the * weak consistency property of holding a value that was once @@ -1460,8 +1463,8 @@ public class ConcurrentHashMapV8 if (initialCapacity < concurrencyLevel) // Use at least as many bins initialCapacity = concurrencyLevel; // as estimated threads long size = (long)(1.0 + (long)initialCapacity / loadFactor); - int cap = ((size >= (long)MAXIMUM_CAPACITY) ? - MAXIMUM_CAPACITY: tableSizeFor((int)size)); + int cap = ((size >= (long)MAXIMUM_CAPACITY) ? + MAXIMUM_CAPACITY: tableSizeFor((int)size)); this.counter = new LongAdder(); this.sizeCtl = cap; } @@ -1678,7 +1681,7 @@ public class ConcurrentHashMapV8 * final String msg = ...; * map.compute(key, new RemappingFunction() { * public String remap(Key k, String v) { - * return (v == null) ? msg : v + msg;});} + * return (v == null) ? msg : v + msg;});}} * * @param key key with which the specified value is to be associated * @param remappingFunction the function to compute a value @@ -1689,7 +1692,7 @@ public class ConcurrentHashMapV8 * @throws IllegalStateException if the computation detectably * attempts a recursive update to this map that would * otherwise never complete - * @throws RuntimeException or Error if the mappingFunction does so, + * @throws RuntimeException or Error if the remappingFunction does so, * in which case the mapping is unchanged */ @SuppressWarnings("unchecked") @@ -2187,7 +2190,7 @@ public class ConcurrentHashMapV8 return true; } - public final boolean removeAll(Collection c) { + public final boolean removeAll(Collection c) { boolean modified = false; for (Iterator it = iter(); it.hasNext();) { if (c.contains(it.next())) { @@ -2237,7 +2240,7 @@ public class ConcurrentHashMapV8 } static final class Values extends MapView - implements Collection { + implements Collection { Values(ConcurrentHashMapV8 map) { super(map); } public final boolean contains(Object o) { return map.containsValue(o); } @@ -2267,7 +2270,7 @@ public class ConcurrentHashMapV8 } } - static final class EntrySet extends MapView + static final class EntrySet extends MapView implements Set> { EntrySet(ConcurrentHashMapV8 map) { super(map); } @@ -2401,7 +2404,7 @@ public class ConcurrentHashMapV8 } table = tab; counter.add(size); - sc = n - (n >>> 2) - 1; + sc = n - (n >>> 2); } } finally { sizeCtl = sc;