src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java

Print this page

        

@@ -372,21 +372,15 @@
         randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
         head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
                                   null, null, 1);
     }
 
-    /** Updater for casHead */
-    private static final
-        AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex>
-        headUpdater = AtomicReferenceFieldUpdater.newUpdater
-        (ConcurrentSkipListMap.class, HeadIndex.class, "head");
-
     /**
      * compareAndSet head node
      */
     private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {
-        return headUpdater.compareAndSet(this, cmp, val);
+        return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
     }
 
     /* ---------------- Nodes -------------- */
 
     /**

@@ -421,32 +415,22 @@
             this.key = null;
             this.value = this;
             this.next = next;
         }
 
-        /** Updater for casNext */
-        static final AtomicReferenceFieldUpdater<Node, Node>
-            nextUpdater = AtomicReferenceFieldUpdater.newUpdater
-            (Node.class, Node.class, "next");
-
-        /** Updater for casValue */
-        static final AtomicReferenceFieldUpdater<Node, Object>
-            valueUpdater = AtomicReferenceFieldUpdater.newUpdater
-            (Node.class, Object.class, "value");
-
         /**
          * compareAndSet value field
          */
         boolean casValue(Object cmp, Object val) {
-            return valueUpdater.compareAndSet(this, cmp, val);
+            return UNSAFE.compareAndSwapObject(this, valueOffset, cmp, val);
         }
 
         /**
          * compareAndSet next field
          */
         boolean casNext(Node<K,V> cmp, Node<K,V> val) {
-            return nextUpdater.compareAndSet(this, cmp, val);
+            return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
         }
 
         /**
          * Returns true if this node is a marker. This method isn't
          * actually called in any current code checking for markers

@@ -520,10 +504,18 @@
             V v = getValidValue();
             if (v == null)
                 return null;
             return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);
         }
+
+        // Unsafe mechanics
+        private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe();
+        private static final long valueOffset =
+            objectFieldOffset(UNSAFE, "value", Node.class);
+        private static final long nextOffset =
+            objectFieldOffset(UNSAFE, "next", Node.class);
+
     }
 
     /* ---------------- Indexing -------------- */
 
     /**

@@ -545,20 +537,15 @@
             this.node = node;
             this.down = down;
             this.right = right;
         }
 
-        /** Updater for casRight */
-        static final AtomicReferenceFieldUpdater<Index, Index>
-            rightUpdater = AtomicReferenceFieldUpdater.newUpdater
-            (Index.class, Index.class, "right");
-
         /**
          * compareAndSet right field
          */
         final boolean casRight(Index<K,V> cmp, Index<K,V> val) {
-            return rightUpdater.compareAndSet(this, cmp, val);
+            return UNSAFE.compareAndSwapObject(this, rightOffset, cmp, val);
         }
 
         /**
          * Returns true if the node this indexes has been deleted.
          * @return true if indexed node is known to be deleted

@@ -589,10 +576,16 @@
          * @return true if successful
          */
         final boolean unlink(Index<K,V> succ) {
             return !indexesDeletedNode() && casRight(succ, succ.right);
         }
+
+        // Unsafe mechanics
+        private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe();
+        private static final long rightOffset =
+            objectFieldOffset(UNSAFE, "right", Index.class);
+
     }
 
     /* ---------------- Head nodes -------------- */
 
     /**

@@ -638,11 +631,12 @@
     /**
      * If using comparator, return a ComparableUsingComparator, else
      * cast key as Comparable, which may cause ClassCastException,
      * which is propagated back to caller.
      */
-    private Comparable<? super K> comparable(Object key) throws ClassCastException {
+    private Comparable<? super K> comparable(Object key)
+            throws ClassCastException {
         if (key == null)
             throw new NullPointerException();
         if (comparator != null)
             return new ComparableUsingComparator<K>((K)key, comparator);
         else

@@ -826,11 +820,11 @@
                     q = r;
                     r = r.right;
                     continue;
                 } else if (c == 0) {
                     Object v = n.value;
-                    return (v != null)? (V)v : getUsingFindNode(key);
+                    return (v != null) ? (V)v : getUsingFindNode(key);
                 } else
                     bound = n;
             }
 
             // Traverse down

@@ -844,11 +838,11 @@
         // Traverse nexts
         for (n = q.node.next;  n != null; n = n.next) {
             if ((k = n.key) != null) {
                 if ((c = key.compareTo(k)) == 0) {
                     Object v = n.value;
-                    return (v != null)? (V)v : getUsingFindNode(key);
+                    return (v != null) ? (V)v : getUsingFindNode(key);
                 } else if (c < 0)
                     break;
             }
         }
         return null;

@@ -941,11 +935,11 @@
     private int randomLevel() {
         int x = randomSeed;
         x ^= x << 13;
         x ^= x >>> 17;
         randomSeed = x ^= x << 5;
-        if ((x & 0x8001) != 0) // test highest and lowest bits
+        if ((x & 0x80000001) != 0) // test highest and lowest bits
             return 0;
         int level = 1;
         while (((x >>>= 1) & 1) != 0) ++level;
         return level;
     }

@@ -1254,11 +1248,11 @@
             } else {
                 Node<K,V> b = q.node;
                 Node<K,V> n = b.next;
                 for (;;) {
                     if (n == null)
-                        return (b.isBaseHeader())? null : b;
+                        return b.isBaseHeader() ? null : b;
                     Node<K,V> f = n.next;            // inconsistent read
                     if (n != b.next)
                         break;
                     Object v = n.value;
                     if (v == null) {                 // n is deleted

@@ -1372,11 +1366,11 @@
         for (;;) {
             Node<K,V> b = findPredecessor(key);
             Node<K,V> n = b.next;
             for (;;) {
                 if (n == null)
-                    return ((rel & LT) == 0 || b.isBaseHeader())? null : b;
+                    return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
                 Node<K,V> f = n.next;
                 if (n != b.next)                  // inconsistent read
                     break;
                 Object v = n.value;
                 if (v == null) {                  // n is deleted

@@ -1388,11 +1382,11 @@
                 int c = key.compareTo(n.key);
                 if ((c == 0 && (rel & EQ) != 0) ||
                     (c <  0 && (rel & LT) == 0))
                     return n;
                 if ( c <= 0 && (rel & LT) != 0)
-                    return (b.isBaseHeader())? null : b;
+                    return b.isBaseHeader() ? null : b;
                 b = n;
                 n = f;
             }
         }
     }

@@ -1742,11 +1736,11 @@
         long count = 0;
         for (Node<K,V> n = findFirst(); n != null; n = n.next) {
             if (n.getValidValue() != null)
                 ++count;
         }
-        return (count >= Integer.MAX_VALUE)? Integer.MAX_VALUE : (int)count;
+        return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) count;
     }
 
     /**
      * Returns <tt>true</tt> if this map contains no key-value mappings.
      * @return <tt>true</tt> if this map contains no key-value mappings

@@ -2097,11 +2091,11 @@
      * @throws ClassCastException {@inheritDoc}
      * @throws NullPointerException if the specified key is null
      */
     public K lowerKey(K key) {
         Node<K,V> n = findNear(key, LT);
-        return (n == null)? null : n.key;
+        return (n == null) ? null : n.key;
     }
 
     /**
      * Returns a key-value mapping associated with the greatest key
      * less than or equal to the given key, or <tt>null</tt> if there

@@ -2121,11 +2115,11 @@
      * @throws ClassCastException {@inheritDoc}
      * @throws NullPointerException if the specified key is null
      */
     public K floorKey(K key) {
         Node<K,V> n = findNear(key, LT|EQ);
-        return (n == null)? null : n.key;
+        return (n == null) ? null : n.key;
     }
 
     /**
      * Returns a key-value mapping associated with the least key
      * greater than or equal to the given key, or <tt>null</tt> if

@@ -2143,11 +2137,11 @@
      * @throws ClassCastException {@inheritDoc}
      * @throws NullPointerException if the specified key is null
      */
     public K ceilingKey(K key) {
         Node<K,V> n = findNear(key, GT|EQ);
-        return (n == null)? null : n.key;
+        return (n == null) ? null : n.key;
     }
 
     /**
      * Returns a key-value mapping associated with the least key
      * strictly greater than the given key, or <tt>null</tt> if there

@@ -2167,11 +2161,11 @@
      * @throws ClassCastException {@inheritDoc}
      * @throws NullPointerException if the specified key is null
      */
     public K higherKey(K key) {
         Node<K,V> n = findNear(key, GT);
-        return (n == null)? null : n.key;
+        return (n == null) ? null : n.key;
     }
 
     /**
      * Returns a key-value mapping associated with the least
      * key in this map, or <tt>null</tt> if the map is empty.

@@ -2340,11 +2334,12 @@
         for (E e : c)
             list.add(e);
         return list;
     }
 
-    static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
+    static final class KeySet<E>
+            extends AbstractSet<E> implements NavigableSet<E> {
         private final ConcurrentNavigableMap<E,Object> m;
         KeySet(ConcurrentNavigableMap<E,Object> map) { m = map; }
         public int size() { return m.size(); }
         public boolean isEmpty() { return m.isEmpty(); }
         public boolean contains(Object o) { return m.containsKey(o); }

@@ -2357,15 +2352,15 @@
         public Comparator<? super E> comparator() { return m.comparator(); }
         public E first() { return m.firstKey(); }
         public E last() { return m.lastKey(); }
         public E pollFirst() {
             Map.Entry<E,Object> e = m.pollFirstEntry();
-            return e == null? null : e.getKey();
+            return (e == null) ? null : e.getKey();
         }
         public E pollLast() {
             Map.Entry<E,Object> e = m.pollLastEntry();
-            return e == null? null : e.getKey();
+            return (e == null) ? null : e.getKey();
         }
         public Iterator<E> iterator() {
             if (m instanceof ConcurrentSkipListMap)
                 return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();
             else

@@ -2708,13 +2703,13 @@
                     rel |= m.LT;
                 else
                     rel &= ~m.LT;
             }
             if (tooLow(key))
-                return ((rel & m.LT) != 0)? null : lowestEntry();
+                return ((rel & m.LT) != 0) ? null : lowestEntry();
             if (tooHigh(key))
-                return ((rel & m.LT) != 0)? highestEntry() : null;
+                return ((rel & m.LT) != 0) ? highestEntry() : null;
             for (;;) {
                 Node<K,V> n = m.findNear(key, rel);
                 if (n == null || !inBounds(n.key))
                     return null;
                 K k = n.key;

@@ -2781,11 +2776,11 @@
             return m.put(key, value);
         }
 
         public V remove(Object key) {
             K k = (K)key;
-            return (!inBounds(k))? null : m.remove(k);
+            return (!inBounds(k)) ? null : m.remove(k);
         }
 
         public int size() {
             long count = 0;
             for (ConcurrentSkipListMap.Node<K,V> n = loNode();

@@ -2792,11 +2787,11 @@
                  isBeforeEnd(n);
                  n = n.next) {
                 if (n.getValidValue() != null)
                     ++count;
             }
-            return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count;
+            return count >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)count;
         }
 
         public boolean isEmpty() {
             return !isBeforeEnd(loNode());
         }

@@ -2970,31 +2965,31 @@
         public K higherKey(K key) {
             return getNearKey(key, (m.GT));
         }
 
         public K firstKey() {
-            return isDescending? highestKey() : lowestKey();
+            return isDescending ? highestKey() : lowestKey();
         }
 
         public K lastKey() {
-            return isDescending? lowestKey() : highestKey();
+            return isDescending ? lowestKey() : highestKey();
         }
 
         public Map.Entry<K,V> firstEntry() {
-            return isDescending? highestEntry() : lowestEntry();
+            return isDescending ? highestEntry() : lowestEntry();
         }
 
         public Map.Entry<K,V> lastEntry() {
-            return isDescending? lowestEntry() : highestEntry();
+            return isDescending ? lowestEntry() : highestEntry();
         }
 
         public Map.Entry<K,V> pollFirstEntry() {
-            return isDescending? removeHighest() : removeLowest();
+            return isDescending ? removeHighest() : removeLowest();
         }
 
         public Map.Entry<K,V> pollLastEntry() {
-            return isDescending? removeLowest() : removeHighest();
+            return isDescending ? removeLowest() : removeHighest();
         }
 
         /* ---------------- Submap Views -------------- */
 
         public NavigableSet<K> keySet() {

@@ -3139,6 +3134,24 @@
                 advance();
                 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
             }
         }
     }
+
+    // Unsafe mechanics
+    private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe();
+    private static final long headOffset =
+        objectFieldOffset(UNSAFE, "head", ConcurrentSkipListMap.class);
+
+    static long objectFieldOffset(sun.misc.Unsafe UNSAFE,
+                                  String field, Class<?> klazz) {
+        try {
+            return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field));
+        } catch (NoSuchFieldException e) {
+            // Convert Exception to corresponding Error
+            NoSuchFieldError error = new NoSuchFieldError(field);
+            error.initCause(e);
+            throw error;
+        }
+    }
+
 }