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