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