--- jsr166/src/extra166y/CustomConcurrentHashMap.java	2009/07/22 17:50:01	1.3
+++ jsr166/src/extra166y/CustomConcurrentHashMap.java	2011/08/03 14:44:33	1.18
@@ -1,7 +1,7 @@
 /*
  * Written by Doug Lea with assistance from members of JCP JSR-166
  * Expert Group and released to the public domain, as explained at
- * http://creativecommons.org/licenses/publicdomain
+ * http://creativecommons.org/publicdomain/zero/1.0/
  */
 
 package extra166y;
@@ -53,10 +53,10 @@ import sun.misc.Unsafe;
  *     (STRONG,
  *      new Equivalence<Person>() {
  *          public boolean equal(Person k, Object x) {
- *            return x instanceOf Person && k.name.equals(((Person)x).name);
+ *            return x instanceof Person && k.name.equals(((Person)x).name);
  *          }
  *          public int hash(Object x) {
- *             return (x instanceOf Person)? ((Person)x).name.hashCode() : 0;
+ *             return (x instanceof Person) ? ((Person)x).name.hashCode() : 0;
  *          }
  *        },
  *      STRONG, EQUALS, 0);
@@ -81,7 +81,7 @@ import sun.misc.Unsafe;
  * via a background thread common across all maps. Because of the
  * potential for asynchronous clearing of References, methods such as
  * <code>containsValue</code> have weaker guarantees than you might
- * expect even in the absence of other explicity concurrent
+ * expect even in the absence of other explicitly concurrent
  * operations. For example <code>containsValue(value)</code> may
  * return true even if <code>value</code> is no longer available upon
  * return from the method.
@@ -236,7 +236,7 @@ public class CustomConcurrentHashMap<K,
          * simple. The most common usage is to construct a new object
          * serving as an initial mapped value.
          *
-         * @param key the (nonnull) key
+         * @param key the (non-null) key
          * @return a value, or null if none
          */
         V map(K key);
@@ -275,11 +275,12 @@ public class CustomConcurrentHashMap<K,
      */
     static interface NodeFactory extends Serializable {
         /**
-         * Creates and returns a Node using the given parameters
+         * Creates and returns a Node using the given parameters.
+         *
          * @param locator an opaque immutable locator for this node
-         * @parem key the (nonnull) immutable key
-         * @parem value the (nonnull) volatile value;
-         * @param cchm the table creating this node.
+         * @param key the (non-null) immutable key
+         * @param value the (non-null) volatile value
+         * @param cchm the table creating this node
          * @param linkage an opaque volatile linkage for maintaining this node
          */
         Node newNode(int locator, Object key, Object value,
@@ -303,7 +304,7 @@ public class CustomConcurrentHashMap<K,
     static interface Node extends Reclaimable {
         /**
          * Returns the key established during the creation of this node.
-         * Note: This method is named "get" rether than "getKey"
+         * Note: This method is named "get" rather than "getKey"
          * to simplify usage of Reference keys.
          * @return the key
          */
@@ -332,7 +333,7 @@ public class CustomConcurrentHashMap<K,
         void setValue(Object value);
 
         /**
-         * Returns the lonkage established during the creation of this
+         * Returns the linkage established during the creation of this
          * node or, if since updated, the linkage set by the most
          * recent call to setLinkage.
          * @return the linkage
@@ -532,9 +533,12 @@ public class CustomConcurrentHashMap<K,
             int sc = (int)((1L + (4L * es) / 3) >>> SEGMENT_BITS);
             if (sc < MIN_SEGMENT_CAPACITY)
                 sc = MIN_SEGMENT_CAPACITY;
-            else if (sc > MAX_SEGMENT_CAPACITY)
-                sc = MAX_SEGMENT_CAPACITY;
-            this.initialSegmentCapacity = sc;
+            int capacity = MIN_SEGMENT_CAPACITY; // ensure power of two
+            while (capacity < sc)
+                capacity <<= 1;
+            if (capacity > MAX_SEGMENT_CAPACITY)
+                capacity = MAX_SEGMENT_CAPACITY;
+            this.initialSegmentCapacity = capacity;
         }
         this.segments = (Segment[])new Segment[NSEGMENTS];
     }
@@ -629,7 +633,7 @@ public class CustomConcurrentHashMap<K,
 
     /**
      * Returns the segment for possibly inserting into the table
-     * associated with given hash, constructing it if necesary.
+     * associated with given hash, constructing it if necessary.
      * @param hash the hash code for the key
      * @return the segment
      */
@@ -638,7 +642,7 @@ public class CustomConcurrentHashMap<K,
         int index = (hash >>> SEGMENT_SHIFT) & SEGMENT_MASK;
         Segment seg = segs[index];
         if (seg == null) {
-            synchronized(segs) {
+            synchronized (segs) {
                 seg = segs[index];
                 if (seg == null) {
                     seg = new Segment();
@@ -696,7 +700,7 @@ public class CustomConcurrentHashMap<K,
      * if no such mapping exists
      *
      * @param  key   possible key
-     * @return the value associated with the kew or <tt>null</tt> if
+     * @return the value associated with the key or <tt>null</tt> if
      * there is no mapping.
      * @throws NullPointerException if the specified key is null
      */
@@ -712,7 +716,7 @@ public class CustomConcurrentHashMap<K,
     }
 
     /**
-     * Share dimplementation for put, putIfAbsent
+     * Shared implementation for put, putIfAbsent
      */
     final V doPut(K key, V value, boolean onlyIfNull) {
         if (key == null || value == null)
@@ -955,6 +959,10 @@ public class CustomConcurrentHashMap<K,
                     while (p != null) {
                         Node n = p.getLinkage();
                         if (p.get() != null && p.getValue() != null) {
+                            pred = p;
+                            p = n;
+                        }
+                        else {
                             if (pred == null)
                                 tab[i] = n;
                             else
@@ -962,10 +970,6 @@ public class CustomConcurrentHashMap<K,
                             seg.decrementCount();
                             p = n;
                         }
-                        else {
-                            pred = p;
-                            p = n;
-                        }
                     }
                 }
             } finally {
@@ -1006,7 +1010,7 @@ public class CustomConcurrentHashMap<K,
             if (seg != null && seg.getTableForTraversal() != null)
                 sum += seg.count;
         }
-        return sum >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)sum;
+        return (sum >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) sum;
     }
 
     /**
@@ -1065,7 +1069,7 @@ public class CustomConcurrentHashMap<K,
     /**
      * If the specified key is not already associated with a value,
      * computes its value using the given mappingFunction, and if
-     * nonnull, enters it into the map.  This is equivalent to
+     * non-null, enters it into the map.  This is equivalent to
      *
      * <pre>
      *   if (map.containsKey(key))
@@ -1078,7 +1082,7 @@ public class CustomConcurrentHashMap<K,
      * </pre>
      *
      * except that the action is performed atomically.  Some
-     * attemmpted operations on this map by other threads may be
+     * attempted operations on this map by other threads may be
      * blocked while computation is in progress. Because this function
      * is invoked within atomicity control, the computation should be
      * short and simple. The most common usage is to construct a new
@@ -1145,7 +1149,7 @@ public class CustomConcurrentHashMap<K,
      *     return remove(key);
      * </pre>
      *
-     * except that the action is performed atomically. Some attemmpted
+     * except that the action is performed atomically. Some attempted
      * operations on this map by other threads may be blocked while
      * computation is in progress.
      *
@@ -1154,7 +1158,7 @@ public class CustomConcurrentHashMap<K,
      * <pre>
      * map.compute(word, new RemappingFunction&lt;String,Integer&gt;() {
      *   public Integer remap(String k, Integer v) {
-     *     return v == null? 1 : v + 1;
+     *     return (v == null) ? 1 : v + 1;
      *   }});
      * </pre>
      *
@@ -1410,7 +1414,8 @@ public class CustomConcurrentHashMap<K,
             if (!(o instanceof Map.Entry))
                 return false;
             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
-            return CustomConcurrentHashMap.this.remove(e.getKey(), e.getValue());
+            return CustomConcurrentHashMap.this.remove(e.getKey(),
+                                                       e.getValue());
         }
         public int size() {
             return CustomConcurrentHashMap.this.size();
@@ -1554,7 +1559,7 @@ public class CustomConcurrentHashMap<K,
      * for each key-value mapping, followed by a null pair.
      * The key-value mappings are emitted in no particular order.
      */
-    private void writeObject(java.io.ObjectOutputStream s) throws IOException  {
+    private void writeObject(java.io.ObjectOutputStream s) throws IOException {
         s.defaultWriteObject();
         for (Map.Entry<K,V> e : entrySet()) {
             s.writeObject(e.getKey());
@@ -1565,11 +1570,11 @@ public class CustomConcurrentHashMap<K,
     }
 
     /**
-     * Reconstitute the instance from a stream (i.e., deserialize it).
+     * Reconstitutes the instance from a stream (that is, deserializes it).
      * @param s the stream
      */
     private void readObject(java.io.ObjectInputStream s)
-        throws IOException, ClassNotFoundException  {
+        throws IOException, ClassNotFoundException {
         s.defaultReadObject();
         this.segments = (Segment[])(new Segment[NSEGMENTS]);
         for (;;) {
@@ -1971,7 +1976,7 @@ public class CustomConcurrentHashMap<K,
         }
         public final Object getValue() {
             EmbeddedWeakReference vr = valueRef;
-            return vr == null? null : vr.get();
+            return (vr == null) ? null : vr.get();
         }
         public final void setValue(Object value) {
             if (value == null)
@@ -2039,7 +2044,7 @@ public class CustomConcurrentHashMap<K,
         }
         public final Object getValue() {
             EmbeddedSoftReference vr = valueRef;
-            return vr == null? null : vr.get();
+            return (vr == null) ? null : vr.get();
         }
         public final void setValue(Object value) {
             if (value == null)
@@ -2097,7 +2102,7 @@ public class CustomConcurrentHashMap<K,
         final int locator;
         final CustomConcurrentHashMap cchm;
         WeakKeyNode(int locator, Object key, CustomConcurrentHashMap cchm) {
-            super(key);
+            super(key, getReclamationQueue());
             this.locator = locator;
             this.cchm = cchm;
         }
@@ -2110,7 +2115,8 @@ public class CustomConcurrentHashMap<K,
 
     static abstract class WeakKeySelfValueNode
         extends WeakKeyNode {
-        WeakKeySelfValueNode(int locator, Object key, CustomConcurrentHashMap cchm) {
+        WeakKeySelfValueNode(int locator, Object key,
+                             CustomConcurrentHashMap cchm) {
             super(locator, key, cchm);
         }
         public final Object getValue() { return get(); }
@@ -2119,7 +2125,8 @@ public class CustomConcurrentHashMap<K,
 
     static final class TerminalWeakKeySelfValueNode
         extends WeakKeySelfValueNode {
-        TerminalWeakKeySelfValueNode(int locator, Object key, CustomConcurrentHashMap cchm) {
+        TerminalWeakKeySelfValueNode(int locator, Object key,
+                                     CustomConcurrentHashMap cchm) {
             super(locator, key, cchm);
         }
         public final Node getLinkage() { return null; }
@@ -2129,7 +2136,8 @@ public class CustomConcurrentHashMap<K,
     static final class LinkedWeakKeySelfValueNode
         extends WeakKeySelfValueNode {
         volatile Node linkage;
-        LinkedWeakKeySelfValueNode(int locator, Object key, CustomConcurrentHashMap cchm,
+        LinkedWeakKeySelfValueNode(int locator, Object key,
+                                   CustomConcurrentHashMap cchm,
                                    Node linkage) {
             super(locator, key, cchm);
             this.linkage = linkage;
@@ -2158,7 +2166,8 @@ public class CustomConcurrentHashMap<K,
     static abstract class WeakKeyStrongValueNode
         extends WeakKeyNode {
         volatile Object value;
-        WeakKeyStrongValueNode(int locator, Object key, Object value, CustomConcurrentHashMap cchm) {
+        WeakKeyStrongValueNode(int locator, Object key, Object value,
+                               CustomConcurrentHashMap cchm) {
             super(locator, key, cchm);
             this.value = value;
         }
@@ -2169,7 +2178,8 @@ public class CustomConcurrentHashMap<K,
     static final class TerminalWeakKeyStrongValueNode
         extends WeakKeyStrongValueNode {
         TerminalWeakKeyStrongValueNode(int locator,
-                                       Object key, Object value, CustomConcurrentHashMap cchm) {
+                                       Object key, Object value,
+                                       CustomConcurrentHashMap cchm) {
             super(locator, key, value, cchm);
         }
         public final Node getLinkage() { return null; }
@@ -2180,7 +2190,8 @@ public class CustomConcurrentHashMap<K,
         extends WeakKeyStrongValueNode {
         volatile Node linkage;
         LinkedWeakKeyStrongValueNode(int locator,
-                                     Object key, Object value, CustomConcurrentHashMap cchm,
+                                     Object key, Object value,
+                                     CustomConcurrentHashMap cchm,
                                      Node linkage) {
             super(locator, key, value, cchm);
             this.linkage = linkage;
@@ -2271,7 +2282,7 @@ public class CustomConcurrentHashMap<K,
         }
         public final Object getValue() {
             EmbeddedWeakReference vr = valueRef;
-            return vr == null? null : vr.get();
+            return (vr == null) ? null : vr.get();
         }
         public final void setValue(Object value) {
             if (value == null)
@@ -2334,7 +2345,7 @@ public class CustomConcurrentHashMap<K,
         }
         public final Object getValue() {
             EmbeddedSoftReference vr = valueRef;
-            return vr == null? null : vr.get();
+            return (vr == null) ? null : vr.get();
         }
         public final void setValue(Object value) {
             if (value == null)
@@ -2392,7 +2403,7 @@ public class CustomConcurrentHashMap<K,
         final int locator;
         final CustomConcurrentHashMap cchm;
         SoftKeyNode(int locator, Object key, CustomConcurrentHashMap cchm) {
-            super(key);
+            super(key, getReclamationQueue());
             this.locator = locator;
             this.cchm = cchm;
         }
@@ -2405,7 +2416,8 @@ public class CustomConcurrentHashMap<K,
 
     static abstract class SoftKeySelfValueNode
         extends SoftKeyNode {
-        SoftKeySelfValueNode(int locator, Object key, CustomConcurrentHashMap cchm) {
+        SoftKeySelfValueNode(int locator, Object key,
+                             CustomConcurrentHashMap cchm) {
             super(locator, key, cchm);
         }
         public final Object getValue() { return get(); }
@@ -2414,7 +2426,8 @@ public class CustomConcurrentHashMap<K,
 
     static final class TerminalSoftKeySelfValueNode
         extends SoftKeySelfValueNode {
-        TerminalSoftKeySelfValueNode(int locator, Object key, CustomConcurrentHashMap cchm) {
+        TerminalSoftKeySelfValueNode(int locator, Object key,
+                                     CustomConcurrentHashMap cchm) {
             super(locator, key, cchm);
         }
         public final Node getLinkage() { return null; }
@@ -2424,7 +2437,8 @@ public class CustomConcurrentHashMap<K,
     static final class LinkedSoftKeySelfValueNode
         extends SoftKeySelfValueNode {
         volatile Node linkage;
-        LinkedSoftKeySelfValueNode(int locator, Object key, CustomConcurrentHashMap cchm,
+        LinkedSoftKeySelfValueNode(int locator, Object key,
+                                   CustomConcurrentHashMap cchm,
                                    Node linkage) {
             super(locator, key, cchm);
             this.linkage = linkage;
@@ -2453,7 +2467,8 @@ public class CustomConcurrentHashMap<K,
     static abstract class SoftKeyStrongValueNode
         extends SoftKeyNode {
         volatile Object value;
-        SoftKeyStrongValueNode(int locator, Object key, Object value, CustomConcurrentHashMap cchm) {
+        SoftKeyStrongValueNode(int locator, Object key, Object value,
+                               CustomConcurrentHashMap cchm) {
             super(locator, key, cchm);
             this.value = value;
         }
@@ -2464,7 +2479,8 @@ public class CustomConcurrentHashMap<K,
     static final class TerminalSoftKeyStrongValueNode
         extends SoftKeyStrongValueNode {
         TerminalSoftKeyStrongValueNode(int locator,
-                                       Object key, Object value, CustomConcurrentHashMap cchm) {
+                                       Object key, Object value,
+                                       CustomConcurrentHashMap cchm) {
             super(locator, key, value, cchm);
         }
         public final Node getLinkage() { return null; }
@@ -2475,7 +2491,8 @@ public class CustomConcurrentHashMap<K,
         extends SoftKeyStrongValueNode {
         volatile Node linkage;
         LinkedSoftKeyStrongValueNode(int locator,
-                                     Object key, Object value, CustomConcurrentHashMap cchm,
+                                     Object key, Object value,
+                                     CustomConcurrentHashMap cchm,
                                      Node linkage) {
             super(locator, key, value, cchm);
             this.linkage = linkage;
@@ -2566,7 +2583,7 @@ public class CustomConcurrentHashMap<K,
         }
         public final Object getValue() {
             EmbeddedWeakReference vr = valueRef;
-            return vr == null? null : vr.get();
+            return (vr == null) ? null : vr.get();
         }
         public final void setValue(Object value) {
             if (value == null)
@@ -2629,7 +2646,7 @@ public class CustomConcurrentHashMap<K,
         }
         public final Object getValue() {
             EmbeddedSoftReference vr = valueRef;
-            return vr == null? null : vr.get();
+            return (vr == null) ? null : vr.get();
         }
         public final void setValue(Object value) {
             if (value == null)
@@ -2857,7 +2874,7 @@ public class CustomConcurrentHashMap<K,
         }
         public final Object getValue() {
             EmbeddedWeakReference vr = valueRef;
-            return vr == null? null : vr.get();
+            return (vr == null) ? null : vr.get();
         }
         public final void setValue(Object value) {
             if (value == null)
@@ -2914,7 +2931,7 @@ public class CustomConcurrentHashMap<K,
         volatile EmbeddedSoftReference valueRef;
         final CustomConcurrentHashMap cchm;
         IntKeySoftValueNode(int locator, Object key, Object value,
-                               CustomConcurrentHashMap cchm) {
+                            CustomConcurrentHashMap cchm) {
             super(locator, key);
             this.cchm = cchm;
             if (value != null)
@@ -2925,7 +2942,7 @@ public class CustomConcurrentHashMap<K,
         }
         public final Object getValue() {
             EmbeddedSoftReference vr = valueRef;
-            return vr == null? null : vr.get();
+            return (vr == null) ? null : vr.get();
         }
         public final void setValue(Object value) {
             if (value == null)
@@ -2980,7 +2997,7 @@ public class CustomConcurrentHashMap<K,
 
     // Temporary Unsafe mechanics for preliminary release
 
-    static final Unsafe _unsafe;
+    static final Unsafe UNSAFE;
     static final long tableBase;
     static final int tableShift;
     static final long segmentsBase;
@@ -3011,14 +3028,14 @@ public class CustomConcurrentHashMap<K,
 
     static {
         try {
-            _unsafe = getUnsafe();
-            tableBase = _unsafe.arrayBaseOffset(Node[].class);
-            int s = _unsafe.arrayIndexScale(Node[].class);
+            UNSAFE = getUnsafe();
+            tableBase = UNSAFE.arrayBaseOffset(Node[].class);
+            int s = UNSAFE.arrayIndexScale(Node[].class);
             if ((s & (s-1)) != 0)
                 throw new Error("data type scale not a power of two");
             tableShift = 31 - Integer.numberOfLeadingZeros(s);
-            segmentsBase = _unsafe.arrayBaseOffset(Segment[].class);
-            s = _unsafe.arrayIndexScale(Segment[].class);
+            segmentsBase = UNSAFE.arrayBaseOffset(Segment[].class);
+            s = UNSAFE.arrayIndexScale(Segment[].class);
             if ((s & (s-1)) != 0)
                 throw new Error("data type scale not a power of two");
             segmentsShift = 31 - Integer.numberOfLeadingZeros(s);
@@ -3030,12 +3047,14 @@ public class CustomConcurrentHashMap<K,
     // Fenced store into segment table array. Unneeded when we have Fences
     static final  void storeNode(Node[] table,
                                  int i, Node r) {
-        _unsafe.putOrderedObject(table, (i << tableShift) + tableBase, r);
+        long nodeOffset = ((long) i << tableShift) + tableBase;
+        UNSAFE.putOrderedObject(table, nodeOffset, r);
     }
 
     static final  void storeSegment(Segment[] segs,
                                     int i, Segment s) {
-        _unsafe.putOrderedObject(segs, (i << segmentsShift) + segmentsBase, s);
+        long segmentOffset = ((long) i << segmentsShift) + segmentsBase;
+        UNSAFE.putOrderedObject(segs, segmentOffset, s);
     }