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);
}