src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java
Print this page
*** 372,392 ****
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);
}
/* ---------------- Nodes -------------- */
/**
--- 372,386 ----
randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
null, null, 1);
}
/**
* compareAndSet head node
*/
private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {
! return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
}
/* ---------------- Nodes -------------- */
/**
*** 421,452 ****
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);
}
/**
* compareAndSet next field
*/
boolean casNext(Node<K,V> cmp, Node<K,V> val) {
! return nextUpdater.compareAndSet(this, cmp, val);
}
/**
* Returns true if this node is a marker. This method isn't
* actually called in any current code checking for markers
--- 415,436 ----
this.key = null;
this.value = this;
this.next = next;
}
/**
* compareAndSet value field
*/
boolean casValue(Object cmp, Object val) {
! return UNSAFE.compareAndSwapObject(this, valueOffset, cmp, val);
}
/**
* compareAndSet next field
*/
boolean casNext(Node<K,V> cmp, Node<K,V> 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,529 ****
--- 504,521 ----
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,564 ****
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);
}
/**
* Returns true if the node this indexes has been deleted.
* @return true if indexed node is known to be deleted
--- 537,551 ----
this.node = node;
this.down = down;
this.right = right;
}
/**
* compareAndSet right field
*/
final boolean casRight(Index<K,V> cmp, Index<K,V> 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,598 ****
--- 576,591 ----
* @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,648 ****
/**
* 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 {
if (key == null)
throw new NullPointerException();
if (comparator != null)
return new ComparableUsingComparator<K>((K)key, comparator);
else
--- 631,642 ----
/**
* 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 {
if (key == null)
throw new NullPointerException();
if (comparator != null)
return new ComparableUsingComparator<K>((K)key, comparator);
else
*** 826,836 ****
q = r;
r = r.right;
continue;
} else if (c == 0) {
Object v = n.value;
! return (v != null)? (V)v : getUsingFindNode(key);
} else
bound = n;
}
// Traverse down
--- 820,830 ----
q = r;
r = r.right;
continue;
} else if (c == 0) {
Object v = n.value;
! return (v != null) ? (V)v : getUsingFindNode(key);
} else
bound = n;
}
// Traverse down
*** 844,854 ****
// 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);
} else if (c < 0)
break;
}
}
return null;
--- 838,848 ----
// 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);
} else if (c < 0)
break;
}
}
return null;
*** 941,951 ****
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
return 0;
int level = 1;
while (((x >>>= 1) & 1) != 0) ++level;
return level;
}
--- 935,945 ----
private int randomLevel() {
int x = randomSeed;
x ^= x << 13;
x ^= x >>> 17;
randomSeed = x ^= x << 5;
! if ((x & 0x80000001) != 0) // test highest and lowest bits
return 0;
int level = 1;
while (((x >>>= 1) & 1) != 0) ++level;
return level;
}
*** 1254,1264 ****
} else {
Node<K,V> b = q.node;
Node<K,V> n = b.next;
for (;;) {
if (n == null)
! 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
--- 1248,1258 ----
} else {
Node<K,V> b = q.node;
Node<K,V> n = b.next;
for (;;) {
if (n == null)
! 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,1382 ****
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;
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read
break;
Object v = n.value;
if (v == null) { // n is deleted
--- 1366,1376 ----
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;
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read
break;
Object v = n.value;
if (v == null) { // n is deleted
*** 1388,1398 ****
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;
b = n;
n = f;
}
}
}
--- 1382,1392 ----
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;
b = n;
n = f;
}
}
}
*** 1742,1752 ****
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;
}
/**
* Returns <tt>true</tt> if this map contains no key-value mappings.
* @return <tt>true</tt> if this map contains no key-value mappings
--- 1736,1746 ----
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;
}
/**
* 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,2107 ****
* @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;
}
/**
* Returns a key-value mapping associated with the greatest key
* less than or equal to the given key, or <tt>null</tt> if there
--- 2091,2101 ----
* @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;
}
/**
* 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,2131 ****
* @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;
}
/**
* Returns a key-value mapping associated with the least key
* greater than or equal to the given key, or <tt>null</tt> if
--- 2115,2125 ----
* @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;
}
/**
* Returns a key-value mapping associated with the least key
* greater than or equal to the given key, or <tt>null</tt> if
*** 2143,2153 ****
* @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;
}
/**
* Returns a key-value mapping associated with the least key
* strictly greater than the given key, or <tt>null</tt> if there
--- 2137,2147 ----
* @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;
}
/**
* Returns a key-value mapping associated with the least key
* strictly greater than the given key, or <tt>null</tt> if there
*** 2167,2177 ****
* @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;
}
/**
* Returns a key-value mapping associated with the least
* key in this map, or <tt>null</tt> if the map is empty.
--- 2161,2171 ----
* @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;
}
/**
* Returns a key-value mapping associated with the least
* key in this map, or <tt>null</tt> if the map is empty.
*** 2340,2350 ****
for (E e : c)
list.add(e);
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; }
public int size() { return m.size(); }
public boolean isEmpty() { return m.isEmpty(); }
public boolean contains(Object o) { return m.containsKey(o); }
--- 2334,2345 ----
for (E e : c)
list.add(e);
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; }
public int size() { return m.size(); }
public boolean isEmpty() { return m.isEmpty(); }
public boolean contains(Object o) { return m.containsKey(o); }
*** 2357,2371 ****
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();
}
public E pollLast() {
Map.Entry<E,Object> e = m.pollLastEntry();
! return e == null? null : e.getKey();
}
public Iterator<E> iterator() {
if (m instanceof ConcurrentSkipListMap)
return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();
else
--- 2352,2366 ----
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();
}
public E pollLast() {
Map.Entry<E,Object> e = m.pollLastEntry();
! return (e == null) ? null : e.getKey();
}
public Iterator<E> iterator() {
if (m instanceof ConcurrentSkipListMap)
return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();
else
*** 2708,2720 ****
rel |= m.LT;
else
rel &= ~m.LT;
}
if (tooLow(key))
! return ((rel & m.LT) != 0)? null : lowestEntry();
if (tooHigh(key))
! 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;
--- 2703,2715 ----
rel |= m.LT;
else
rel &= ~m.LT;
}
if (tooLow(key))
! return ((rel & m.LT) != 0) ? null : lowestEntry();
if (tooHigh(key))
! 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,2791 ****
return m.put(key, value);
}
public V remove(Object key) {
K k = (K)key;
! return (!inBounds(k))? null : m.remove(k);
}
public int size() {
long count = 0;
for (ConcurrentSkipListMap.Node<K,V> n = loNode();
--- 2776,2786 ----
return m.put(key, value);
}
public V remove(Object key) {
K k = (K)key;
! return (!inBounds(k)) ? null : m.remove(k);
}
public int size() {
long count = 0;
for (ConcurrentSkipListMap.Node<K,V> n = loNode();
*** 2792,2802 ****
isBeforeEnd(n);
n = n.next) {
if (n.getValidValue() != null)
++count;
}
! return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count;
}
public boolean isEmpty() {
return !isBeforeEnd(loNode());
}
--- 2787,2797 ----
isBeforeEnd(n);
n = n.next) {
if (n.getValidValue() != null)
++count;
}
! return count >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)count;
}
public boolean isEmpty() {
return !isBeforeEnd(loNode());
}
*** 2970,3000 ****
public K higherKey(K key) {
return getNearKey(key, (m.GT));
}
public K firstKey() {
! return isDescending? highestKey() : lowestKey();
}
public K lastKey() {
! return isDescending? lowestKey() : highestKey();
}
public Map.Entry<K,V> firstEntry() {
! return isDescending? highestEntry() : lowestEntry();
}
public Map.Entry<K,V> lastEntry() {
! return isDescending? lowestEntry() : highestEntry();
}
public Map.Entry<K,V> pollFirstEntry() {
! return isDescending? removeHighest() : removeLowest();
}
public Map.Entry<K,V> pollLastEntry() {
! return isDescending? removeLowest() : removeHighest();
}
/* ---------------- Submap Views -------------- */
public NavigableSet<K> keySet() {
--- 2965,2995 ----
public K higherKey(K key) {
return getNearKey(key, (m.GT));
}
public K firstKey() {
! return isDescending ? highestKey() : lowestKey();
}
public K lastKey() {
! return isDescending ? lowestKey() : highestKey();
}
public Map.Entry<K,V> firstEntry() {
! return isDescending ? highestEntry() : lowestEntry();
}
public Map.Entry<K,V> lastEntry() {
! return isDescending ? lowestEntry() : highestEntry();
}
public Map.Entry<K,V> pollFirstEntry() {
! return isDescending ? removeHighest() : removeLowest();
}
public Map.Entry<K,V> pollLastEntry() {
! return isDescending ? removeLowest() : removeHighest();
}
/* ---------------- Submap Views -------------- */
public NavigableSet<K> keySet() {
*** 3139,3144 ****
--- 3134,3157 ----
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;
+ }
+ }
+
}