--- jsr166/src/jsr166e/ConcurrentHashMapV8.java 2011/08/30 07:18:46 1.3 +++ jsr166/src/jsr166e/ConcurrentHashMapV8.java 2011/08/30 11:35:39 1.5 @@ -146,11 +146,15 @@ public class ConcurrentHashMapV8 * there is no existing node during a put operation, then one can * be CAS'ed in (without need for lock except in computeIfAbsent); * the CAS serves as validation. This is on average the most - * common case for put operations. The expected number of locks - * covering different elements (i.e., bins with 2 or more nodes) - * is approximately 10% at steady state under default settings. - * Lock contention probability for two threads accessing arbitrary - * distinct elements is thus less than 1% even for small tables. + * common case for put operations -- under random hash codes, the + * distribution of nodes in bins follows a Poisson distribution + * (see http://en.wikipedia.org/wiki/Poisson_distribution) with a + * parameter of 0.5 on average under the default loadFactor of + * 0.75. The expected number of locks covering different elements + * (i.e., bins with 2 or more nodes) is approximately 10% at + * steady state under default settings. Lock contention + * probability for two threads accessing arbitrary distinct + * elements is, roughly, 1 / (8 * #elements). * * The table is resized when occupancy exceeds a threshold. Only * a single thread performs the resize (using field "resizing", to @@ -339,7 +343,7 @@ public class ConcurrentHashMapV8 /* ---------------- Access and update operations -------------- */ /** Implementation for get and containsKey **/ - private final Object internalGet(Object k) { + private final Object internalGet(Object k) { int h = spread(k.hashCode()); Node[] tab = table; retry: while (tab != null) { @@ -380,7 +384,7 @@ public class ConcurrentHashMapV8 else { boolean validated = false; boolean checkSize = false; - synchronized(e) { + synchronized (e) { Node first = e; for (;;) { Object ek, ev; @@ -438,7 +442,7 @@ public class ConcurrentHashMapV8 else { boolean validated = false; boolean deleted = false; - synchronized(e) { + synchronized (e) { Node pred = null; Node first = e; for (;;) { @@ -497,7 +501,7 @@ public class ConcurrentHashMapV8 tab = grow(0); else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) { Node node = new Node(h, k, null, null); - synchronized(node) { + synchronized (node) { if (casTabAt(tab, i, null, node)) { validated = true; try { @@ -515,9 +519,11 @@ public class ConcurrentHashMapV8 } else if (e.hash < 0) tab = (Node[])e.key; + else if (Thread.holdsLock(e)) + throw new IllegalStateException("Recursive map computation"); else { boolean checkSize = false; - synchronized(e) { + synchronized (e) { Node first = e; for (;;) { Object ek, ev; @@ -586,7 +592,7 @@ public class ConcurrentHashMapV8 } else { boolean validated = false; - synchronized(e) { + synchronized (e) { int idx = e.hash & mask; Node lastRun = e; for (Node p = e.next; p != null; p = p.next) { @@ -677,7 +683,7 @@ public class ConcurrentHashMapV8 */ private final void internalPutAll(Map m) { int s = m.size(); - grow((s >= (MAXIMUM_CAPACITY >>> 1))? s : s + (s >>> 1)); + grow((s >= (MAXIMUM_CAPACITY >>> 1)) ? s : s + (s >>> 1)); for (Map.Entry e : m.entrySet()) { Object k = e.getKey(); Object v = e.getValue(); @@ -702,7 +708,7 @@ public class ConcurrentHashMapV8 tab = (Node[])e.key; else { boolean validated = false; - synchronized(e) { + synchronized (e) { if (tabAt(tab, i) == e) { validated = true; do { @@ -983,7 +989,9 @@ public class ConcurrentHashMapV8 */ public int size() { long n = counter.sum(); - return n <= 0L? 0 : n >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)n; + return (n <= 0L) ? 0 : + (n >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : + (int)n; } /** @@ -1117,11 +1125,16 @@ public class ConcurrentHashMapV8 * * * except that the action is performed atomically. Some attempted - * operations on this map by other threads may be blocked while - * computation is in progress, so the computation should be short - * and simple, and must not attempt to update any other mappings - * of this Map. The most common usage is to construct a new object - * serving as an initial mapped value, or memoized result. + * update operations on this map by other threads may be blocked + * while computation is in progress, so the computation should be + * short and simple, and must not attempt to update any other + * mappings of this Map. The most appropriate usage is to + * construct a new object serving as an initial mapped value, or + * memoized result, as in: + * 
{@code
+     * map.computeIfAbsent(key, new MappingFunction() {
+     *   public V map(K k) { return new Value(f(k)); }};
+     * }
* * @param key key with which the specified value is to be associated * @param mappingFunction the function to compute a value @@ -1130,6 +1143,9 @@ public class ConcurrentHashMapV8 * returned {@code null}. * @throws NullPointerException if the specified key or mappingFunction * is null, + * @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, * in which case the mapping is left unestablished. */ @@ -1140,7 +1156,7 @@ public class ConcurrentHashMapV8 } /** - * Computes the value associated with he given key using the given + * Computes the value associated with the given key using the given * mappingFunction, and if non-null, enters it into the map. This * is equivalent to * @@ -1149,14 +1165,15 @@ public class ConcurrentHashMapV8 * if (value != null) * map.put(key, value); * else - * return map.get(key); + * value = map.get(key); + * return value; * * * except that the action is performed atomically. Some attempted - * operations on this map by other threads may be blocked while - * computation is in progress, so the computation should be short - * and simple, and must not attempt to update any other mappings - * of this Map. + * update operations on this map by other threads may be blocked + * while computation is in progress, so the computation should be + * short and simple, and must not attempt to update any other + * mappings of this Map. * * @param key key with which the specified value is to be associated * @param mappingFunction the function to compute a value @@ -1165,6 +1182,9 @@ public class ConcurrentHashMapV8 * returned {@code null} and the value was not otherwise present. * @throws NullPointerException if the specified key or mappingFunction * is null, + * @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, * in which case the mapping is unchanged. */