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

Print this page

        

@@ -33,11 +33,10 @@
  * http://creativecommons.org/publicdomain/zero/1.0/
  */
 
 package java.util.concurrent;
 import java.util.*;
-import java.util.concurrent.atomic.*;
 
 /**
  * A scalable concurrent {@link ConcurrentNavigableMap} implementation.
  * The map is sorted according to the {@linkplain Comparable natural
  * ordering} of its keys, or by a {@link Comparator} provided at map

@@ -88,10 +87,11 @@
  * @author Doug Lea
  * @param <K> the type of keys maintained by this map
  * @param <V> the type of mapped values
  * @since 1.6
  */
+@SuppressWarnings("unchecked")
 public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
     implements ConcurrentNavigableMap<K,V>,
                Cloneable,
                java.io.Serializable {
     /*

@@ -350,15 +350,15 @@
      * doesn't matter too much if different threads don't see updates.
      */
     private transient int randomSeed;
 
     /** Lazily initialized key set */
-    private transient KeySet keySet;
+    private transient KeySet<K> keySet;
     /** Lazily initialized entry set */
-    private transient EntrySet entrySet;
+    private transient EntrySet<K,V> entrySet;
     /** Lazily initialized values collection */
-    private transient Values values;
+    private transient Values<V> values;
     /** Lazily initialized descending key set */
     private transient ConcurrentNavigableMap<K,V> descendingMap;
 
     /**
      * Initializes or resets state. Needed by constructors, clone,

@@ -515,11 +515,11 @@
         private static final long nextOffset;
 
         static {
             try {
                 UNSAFE = sun.misc.Unsafe.getUnsafe();
-                Class k = Node.class;
+                Class<?> k = Node.class;
                 valueOffset = UNSAFE.objectFieldOffset
                     (k.getDeclaredField("value"));
                 nextOffset = UNSAFE.objectFieldOffset
                     (k.getDeclaredField("next"));
             } catch (Exception e) {

@@ -595,11 +595,11 @@
         private static final sun.misc.Unsafe UNSAFE;
         private static final long rightOffset;
         static {
             try {
                 UNSAFE = sun.misc.Unsafe.getUnsafe();
-                Class k = Index.class;
+                Class<?> k = Index.class;
                 rightOffset = UNSAFE.objectFieldOffset
                     (k.getDeclaredField("right"));
             } catch (Exception e) {
                 throw new Error(e);
             }

@@ -931,11 +931,11 @@
              * keeping levels in an array to access them while
              * creating new head index nodes from the opposite
              * direction.
              */
             level = max + 1;
-            Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1];
+            Index<K,V>[] idxs = (Index<K,V>[])new Index<?,?>[level+1];
             Index<K,V> idx = null;
             for (int i = 1; i <= level; ++i)
                 idxs[i] = idx = new Index<K,V>(z, idx, null);
 
             HeadIndex<K,V> oldh;

@@ -1434,21 +1434,21 @@
      * instance. (The keys and values themselves are not cloned.)
      *
      * @return a shallow copy of this map
      */
     public ConcurrentSkipListMap<K,V> clone() {
-        ConcurrentSkipListMap<K,V> clone = null;
         try {
-            clone = (ConcurrentSkipListMap<K,V>) super.clone();
-        } catch (CloneNotSupportedException e) {
-            throw new InternalError();
-        }
-
+            @SuppressWarnings("unchecked")
+            ConcurrentSkipListMap<K,V> clone =
+                (ConcurrentSkipListMap<K,V>) super.clone();
         clone.initialize();
         clone.buildFromSorted(this);
         return clone;
+        } catch (CloneNotSupportedException e) {
+            throw new InternalError();
     }
+    }
 
     /**
      * Streamlined bulk insertion to initialize from elements of
      * given sorted map.  Call only from constructor or clone
      * method.

@@ -1505,11 +1505,11 @@
     }
 
     /* ---------------- Serialization -------------- */
 
     /**
-     * Save the state of this map to a stream.
+     * Saves the state of this map to a stream (that is, serializes it).
      *
      * @serialData The key (Object) and value (Object) for each
      * key-value mapping represented by the map, followed by
      * <tt>null</tt>. The key-value mappings are emitted in key-order
      * (as determined by the Comparator, or by the keys' natural

@@ -1530,11 +1530,13 @@
         }
         s.writeObject(null);
     }
 
     /**
-     * Reconstitute the map from a stream.
+     * Reconstitutes the map from a stream (that is, deserializes it).
+     *
+     * @param s the stream
      */
     private void readObject(final java.io.ObjectInputStream s)
         throws java.io.IOException, ClassNotFoundException {
         // Read in the Comparator and any hidden stuff
         s.defaultReadObject();

@@ -1753,17 +1755,17 @@
      * <p>This method is equivalent to method {@code navigableKeySet}.
      *
      * @return a navigable set view of the keys in this map
      */
     public NavigableSet<K> keySet() {
-        KeySet ks = keySet;
-        return (ks != null) ? ks : (keySet = new KeySet(this));
+        KeySet<K> ks = keySet;
+        return (ks != null) ? ks : (keySet = new KeySet<K>(this));
     }
 
     public NavigableSet<K> navigableKeySet() {
-        KeySet ks = keySet;
-        return (ks != null) ? ks : (keySet = new KeySet(this));
+        KeySet<K> ks = keySet;
+        return (ks != null) ? ks : (keySet = new KeySet<K>(this));
     }
 
     /**
      * Returns a {@link Collection} view of the values contained in this map.
      * The collection's iterator returns the values in ascending order

@@ -1781,12 +1783,12 @@
      * and guarantees to traverse elements as they existed upon
      * construction of the iterator, and may (but is not guaranteed to)
      * reflect any modifications subsequent to construction.
      */
     public Collection<V> values() {
-        Values vs = values;
-        return (vs != null) ? vs : (values = new Values(this));
+        Values<V> vs = values;
+        return (vs != null) ? vs : (values = new Values<V>(this));
     }
 
     /**
      * Returns a {@link Set} view of the mappings contained in this map.
      * The set's iterator returns the entries in ascending key order.

@@ -1810,12 +1812,12 @@
      *
      * @return a set view of the mappings contained in this map,
      *         sorted in ascending key order
      */
     public Set<Map.Entry<K,V>> entrySet() {
-        EntrySet es = entrySet;
-        return (es != null) ? es : (entrySet = new EntrySet(this));
+        EntrySet<K,V> es = entrySet;
+        return (es != null) ? es : (entrySet = new EntrySet<K,V>(this));
     }
 
     public ConcurrentNavigableMap<K,V> descendingMap() {
         ConcurrentNavigableMap<K,V> dm = descendingMap;
         return (dm != null) ? dm : (descendingMap = new SubMap<K,V>

@@ -2302,12 +2304,12 @@
         return list;
     }
 
     static final class KeySet<E>
             extends AbstractSet<E> implements NavigableSet<E> {
-        private final ConcurrentNavigableMap<E,Object> m;
-        KeySet(ConcurrentNavigableMap<E,Object> map) { m = map; }
+        private final ConcurrentNavigableMap<E,?> m;
+        KeySet(ConcurrentNavigableMap<E,?> map) { m = map; }
         public int size() { return m.size(); }
         public boolean isEmpty() { return m.isEmpty(); }
         public boolean contains(Object o) { return m.containsKey(o); }
         public boolean remove(Object o) { return m.remove(o) != null; }
         public void clear() { m.clear(); }

@@ -2317,15 +2319,15 @@
         public E higher(E e) { return m.higherKey(e); }
         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();
+            Map.Entry<E,?> e = m.pollFirstEntry();
             return (e == null) ? null : e.getKey();
         }
         public E pollLast() {
-            Map.Entry<E,Object> e = m.pollLastEntry();
+            Map.Entry<E,?> e = m.pollLastEntry();
             return (e == null) ? null : e.getKey();
         }
         public Iterator<E> iterator() {
             if (m instanceof ConcurrentSkipListMap)
                 return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();

@@ -2372,24 +2374,24 @@
         }
         public NavigableSet<E> tailSet(E fromElement) {
             return tailSet(fromElement, true);
         }
         public NavigableSet<E> descendingSet() {
-            return new KeySet(m.descendingMap());
+            return new KeySet<E>(m.descendingMap());
         }
     }
 
     static final class Values<E> extends AbstractCollection<E> {
-        private final ConcurrentNavigableMap<Object, E> m;
-        Values(ConcurrentNavigableMap<Object, E> map) {
+        private final ConcurrentNavigableMap<?, E> m;
+        Values(ConcurrentNavigableMap<?, E> map) {
             m = map;
         }
         public Iterator<E> iterator() {
             if (m instanceof ConcurrentSkipListMap)
-                return ((ConcurrentSkipListMap<Object,E>)m).valueIterator();
+                return ((ConcurrentSkipListMap<?,E>)m).valueIterator();
             else
-                return ((SubMap<Object,E>)m).valueIterator();
+                return ((SubMap<?,E>)m).valueIterator();
         }
         public boolean isEmpty() {
             return m.isEmpty();
         }
         public int size() {

@@ -2419,18 +2421,18 @@
         }
 
         public boolean contains(Object o) {
             if (!(o instanceof Map.Entry))
                 return false;
-            Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o;
+            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
             V1 v = m.get(e.getKey());
             return v != null && v.equals(e.getValue());
         }
         public boolean remove(Object o) {
             if (!(o instanceof Map.Entry))
                 return false;
-            Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o;
+            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
             return m.remove(e.getKey(),
                             e.getValue());
         }
         public boolean isEmpty() {
             return m.isEmpty();

@@ -2566,13 +2568,13 @@
          */
         private ConcurrentSkipListMap.Node<K,V> loNode() {
             if (lo == null)
                 return m.findFirst();
             else if (loInclusive)
-                return m.findNear(lo, m.GT|m.EQ);
+                return m.findNear(lo, GT|EQ);
             else
-                return m.findNear(lo, m.GT);
+                return m.findNear(lo, GT);
         }
 
         /**
          * Returns highest node. This node might not be in range, so
          * most usages need to check bounds

@@ -2579,13 +2581,13 @@
          */
         private ConcurrentSkipListMap.Node<K,V> hiNode() {
             if (hi == null)
                 return m.findLast();
             else if (hiInclusive)
-                return m.findNear(hi, m.LT|m.EQ);
+                return m.findNear(hi, LT|EQ);
             else
-                return m.findNear(hi, m.LT);
+                return m.findNear(hi, LT);
         }
 
         /**
          * Returns lowest absolute key (ignoring directonality)
          */

@@ -2663,19 +2665,19 @@
         /**
          * Submap version of ConcurrentSkipListMap.getNearEntry
          */
         private Map.Entry<K,V> getNearEntry(K key, int rel) {
             if (isDescending) { // adjust relation for direction
-                if ((rel & m.LT) == 0)
-                    rel |= m.LT;
+                if ((rel & LT) == 0)
+                    rel |= LT;
                 else
-                    rel &= ~m.LT;
+                    rel &= ~LT;
             }
             if (tooLow(key))
-                return ((rel & m.LT) != 0) ? null : lowestEntry();
+                return ((rel & LT) != 0) ? null : lowestEntry();
             if (tooHigh(key))
-                return ((rel & m.LT) != 0) ? highestEntry() : null;
+                return ((rel & 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;

@@ -2686,25 +2688,25 @@
         }
 
         // Almost the same as getNearEntry, except for keys
         private K getNearKey(K key, int rel) {
             if (isDescending) { // adjust relation for direction
-                if ((rel & m.LT) == 0)
-                    rel |= m.LT;
+                if ((rel & LT) == 0)
+                    rel |= LT;
                 else
-                    rel &= ~m.LT;
+                    rel &= ~LT;
             }
             if (tooLow(key)) {
-                if ((rel & m.LT) == 0) {
+                if ((rel & LT) == 0) {
                     ConcurrentSkipListMap.Node<K,V> n = loNode();
                     if (isBeforeEnd(n))
                         return n.key;
                 }
                 return null;
             }
             if (tooHigh(key)) {
-                if ((rel & m.LT) != 0) {
+                if ((rel & LT) != 0) {
                     ConcurrentSkipListMap.Node<K,V> n = hiNode();
                     if (n != null) {
                         K last = n.key;
                         if (inBounds(last))
                             return last;

@@ -2732,11 +2734,11 @@
         }
 
         public V get(Object key) {
             if (key == null) throw new NullPointerException();
             K k = (K)key;
-            return ((!inBounds(k)) ? null : m.get(k));
+            return (!inBounds(k)) ? null : m.get(k);
         }
 
         public V put(K key, V value) {
             checkKeyBounds(key);
             return m.put(key, value);

@@ -2899,39 +2901,39 @@
         }
 
         /* ----------------  Relational methods -------------- */
 
         public Map.Entry<K,V> ceilingEntry(K key) {
-            return getNearEntry(key, (m.GT|m.EQ));
+            return getNearEntry(key, GT|EQ);
         }
 
         public K ceilingKey(K key) {
-            return getNearKey(key, (m.GT|m.EQ));
+            return getNearKey(key, GT|EQ);
         }
 
         public Map.Entry<K,V> lowerEntry(K key) {
-            return getNearEntry(key, (m.LT));
+            return getNearEntry(key, LT);
         }
 
         public K lowerKey(K key) {
-            return getNearKey(key, (m.LT));
+            return getNearKey(key, LT);
         }
 
         public Map.Entry<K,V> floorEntry(K key) {
-            return getNearEntry(key, (m.LT|m.EQ));
+            return getNearEntry(key, LT|EQ);
         }
 
         public K floorKey(K key) {
-            return getNearKey(key, (m.LT|m.EQ));
+            return getNearKey(key, LT|EQ);
         }
 
         public Map.Entry<K,V> higherEntry(K key) {
-            return getNearEntry(key, (m.GT));
+            return getNearEntry(key, GT);
         }
 
         public K higherKey(K key) {
-            return getNearKey(key, (m.GT));
+            return getNearKey(key, GT);
         }
 
         public K firstKey() {
             return isDescending ? highestKey() : lowestKey();
         }

@@ -2958,26 +2960,26 @@
 
         /* ---------------- Submap Views -------------- */
 
         public NavigableSet<K> keySet() {
             KeySet<K> ks = keySetView;
-            return (ks != null) ? ks : (keySetView = new KeySet(this));
+            return (ks != null) ? ks : (keySetView = new KeySet<K>(this));
         }
 
         public NavigableSet<K> navigableKeySet() {
             KeySet<K> ks = keySetView;
-            return (ks != null) ? ks : (keySetView = new KeySet(this));
+            return (ks != null) ? ks : (keySetView = new KeySet<K>(this));
         }
 
         public Collection<V> values() {
             Collection<V> vs = valuesView;
-            return (vs != null) ? vs : (valuesView = new Values(this));
+            return (vs != null) ? vs : (valuesView = new Values<V>(this));
         }
 
         public Set<Map.Entry<K,V>> entrySet() {
             Set<Map.Entry<K,V>> es = entrySetView;
-            return (es != null) ? es : (entrySetView = new EntrySet(this));
+            return (es != null) ? es : (entrySetView = new EntrySet<K,V>(this));
         }
 
         public NavigableSet<K> descendingKeySet() {
             return descendingMap().navigableKeySet();
         }

@@ -3107,11 +3109,11 @@
     private static final sun.misc.Unsafe UNSAFE;
     private static final long headOffset;
     static {
         try {
             UNSAFE = sun.misc.Unsafe.getUnsafe();
-            Class k = ConcurrentSkipListMap.class;
+            Class<?> k = ConcurrentSkipListMap.class;
             headOffset = UNSAFE.objectFieldOffset
                 (k.getDeclaredField("head"));
         } catch (Exception e) {
             throw new Error(e);
         }