You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by ag...@apache.org on 2018/09/07 13:49:30 UTC
[27/50] [abbrv] ignite git commit: IGNITE-9360 Remove SnapTreeMap and
tests on it. - Fixes #4608.
http://git-wip-us.apache.org/repos/asf/ignite/blob/35706b94/modules/core/src/main/java/org/apache/ignite/internal/util/snaptree/SnapTreeMap.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/util/snaptree/SnapTreeMap.java b/modules/core/src/main/java/org/apache/ignite/internal/util/snaptree/SnapTreeMap.java
deleted file mode 100644
index dce2fb8..0000000
--- a/modules/core/src/main/java/org/apache/ignite/internal/util/snaptree/SnapTreeMap.java
+++ /dev/null
@@ -1,2917 +0,0 @@
-/*
- * Copyright (c) 2009 Stanford University, unless otherwise specified.
- * All rights reserved.
- *
- * This software was developed by the Pervasive Parallelism Laboratory of
- * Stanford University, California, USA.
- *
- * Permission to use, copy, modify, and distribute this software in source
- * or binary form for any purpose with or without fee is hereby granted,
- * provided that the following conditions are met:
- *
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- *
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * 3. Neither the name of Stanford University nor the names of its
- * contributors may be used to endorse or promote products derived
- * from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
- * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
- * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-package org.apache.ignite.internal.util.snaptree;
-
-import org.apache.ignite.*;
-import org.apache.ignite.internal.util.*;
-import org.apache.ignite.internal.util.lang.*;
-
-import java.io.IOException;
-import java.io.ObjectInputStream;
-import java.io.ObjectOutputStream;
-import java.io.Serializable;
-import java.util.AbstractMap;
-import java.util.AbstractSet;
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.Iterator;
-import java.util.Map;
-import java.util.NavigableSet;
-import java.util.NoSuchElementException;
-import java.util.Set;
-import java.util.SortedMap;
-import java.util.SortedSet;
-import java.util.concurrent.ConcurrentNavigableMap;
-
-// TODO: optimized buildFromSorted
-// TODO: submap.clone()
-
-/** A concurrent AVL tree with fast cloning, based on the algorithm of Bronson,
- * Casper, Chafi, and Olukotun, "A Practical Concurrent Binary Search Tree"
- * published in PPoPP'10. To simplify the locking protocols rebalancing work
- * is performed in pieces, and some removed keys are be retained as routing
- * nodes in the tree.
- *
- * <p>This data structure honors all of the contracts of {@link
- * java.util.concurrent.ConcurrentSkipListMap}, with the additional contract
- * that clone, size, toArray, and iteration are linearizable (atomic).
- *
- * <p>The tree uses optimistic concurrency control. No locks are usually
- * required for get, containsKey, firstKey, firstEntry, lastKey, or lastEntry.
- * Reads are not lock free (or even obstruction free), but obstructing threads
- * perform no memory allocation, system calls, or loops, which seems to work
- * okay in practice. All of the updates to the tree are performed in fixed-
- * size blocks, so restoration of the AVL balance criteria may occur after a
- * change to the tree has linearized (but before the mutating operation has
- * returned). The tree is always properly balanced when quiescent.
- *
- * <p>To clone the tree (or produce a snapshot for consistent iteration) the
- * root node is marked as shared, which must be (*) done while there are no
- * pending mutations. New mutating operations are blocked if a mark is
- * pending, and when existing mutating operations are completed the mark is
- * made.
- * <em>* - It would be less disruptive if we immediately marked the root as
- * shared, and then waited for pending operations that might not have seen the
- * mark without blocking new mutations. This could result in imbalance being
- * frozen into the shared portion of the tree, though. To minimize the
- * problem we perform the mark and reenable mutation on whichever thread
- * notices that the entry count has become zero, to reduce context switches on
- * the critical path.</em>
- *
- * <p>The same multi-cache line data structure required for efficiently
- * tracking the entry and exit for mutating operations is used to maintain the
- * current size of the tree. This means that the size can be computed by
- * quiescing as for a clone, but without doing any marking.
- *
- * <p>Range queries such as higherKey are not amenable to the optimistic
- * hand-over-hand locking scheme used for exact searches, so they are
- * implemented with pessimistic concurrency control. Mutation can be
- * considered to acquire a lock on the map in Intention-eXclusive mode, range
- * queries, size(), and root marking acquire the lock in Shared mode.
- *
- * @author Nathan Bronson
- */
-@SuppressWarnings("ALL")
-public class SnapTreeMap<K, V> extends AbstractMap<K, V> implements ConcurrentNavigableMap<K, V>, Cloneable,
- Serializable {
-
- /** */
- private static final long serialVersionUID = 0L;
-
- /** If false, null values will trigger a NullPointerException. When false,
- * this map acts exactly like a ConcurrentSkipListMap, except for the
- * running time of the methods. The ability to get a snapshot reduces the
- * potential ambiguity between null values and absent entries, so I'm not
- * sure what the default should be.
- */
- static final boolean AllowNullValues = false;
-
- /** This is a special value that indicates the presence of a null value,
- * to differentiate from the absence of a value. Only used when
- * {@link #AllowNullValues} is true.
- */
- static final Object SpecialNull = new Object();
-
- /** This is a special value that indicates that an optimistic read
- * failed.
- */
- static final Object SpecialRetry = new Object();
-
-
- /** The number of spins before yielding. */
- static final int SpinCount = Integer.parseInt(System.getProperty("snaptree.spin", "100"));
-
- /** The number of yields before blocking. */
- static final int YieldCount = Integer.parseInt(System.getProperty("snaptree.yield", "0"));
-
-
- // we encode directions as characters
- static final char Left = 'L';
- static final char Right = 'R';
-
-
- /** An <tt>OVL</tt> is a version number and lock used for optimistic
- * concurrent control of some program invariant. If {@link #isShrinking}
- * then the protected invariant is changing. If two reads of an OVL are
- * performed that both see the same non-changing value, the reader may
- * conclude that no changes to the protected invariant occurred between
- * the two reads. The special value UnlinkedOVL is not changing, and is
- * guaranteed to not result from a normal sequence of beginChange and
- * endChange operations.
- * <p>
- * For convenience <tt>endChange(ovl) == endChange(beginChange(ovl))</tt>.
- */
- static long beginChange(long ovl) { return ovl | 1; }
- static long endChange(long ovl) { return (ovl | 3) + 1; }
- static final long UnlinkedOVL = 2;
-
- static boolean isShrinking(long ovl) { return (ovl & 1) != 0; }
- static boolean isUnlinked(long ovl) { return (ovl & 2) != 0; }
- static boolean isShrinkingOrUnlinked(long ovl) { return (ovl & 3) != 0L; }
-
-
- protected static class Node<K,V> implements Map.Entry<K,V> {
- public K key;
- volatile int height;
-
- /** null means this node is conceptually not present in the map.
- * SpecialNull means the value is null.
- */
- volatile Object vOpt;
- volatile Node<K,V> parent;
- volatile long shrinkOVL;
- volatile Node<K,V> left;
- volatile Node<K,V> right;
-
- Node(final K key,
- final int height,
- final Object vOpt,
- final Node<K,V> parent,
- final long shrinkOVL,
- final Node<K,V> left,
- final Node<K,V> right)
- {
- this.key = key;
- this.height = height;
- this.vOpt = vOpt;
- this.parent = parent;
- this.shrinkOVL = shrinkOVL;
- this.left = left;
- this.right = right;
- }
-
- @Override
- public K getKey() { return key; }
-
- @Override
- @SuppressWarnings("unchecked")
- public V getValue() {
- final Object tmp = vOpt;
- if (AllowNullValues) {
- return tmp == SpecialNull ? null : (V)tmp;
- } else {
- return (V)tmp;
- }
- }
-
- @Override
- public V setValue(final V v) {
- throw new UnsupportedOperationException();
- }
-
- Node<K,V> child(char dir) { return dir == Left ? left : right; }
-
- void setChild(char dir, Node<K,V> node) {
- if (dir == Left) {
- left = node;
- } else {
- right = node;
- }
- }
-
- //////// copy-on-write stuff
-
- private static <K,V> boolean isShared(final Node<K,V> node) {
- return node != null && node.parent == null;
- }
-
- static <K,V> Node<K,V> markShared(final Node<K,V> node) {
- if (node != null) {
- node.parent = null;
- }
- return node;
- }
-
- private Node<K,V> lazyCopy(Node<K,V> newParent) {
- assert (isShared(this));
- assert (!isShrinkingOrUnlinked(shrinkOVL));
-
- return new Node<K,V>(key, height, vOpt, newParent, 0L, markShared(left), markShared(right));
- }
-
- Node<K,V> unsharedLeft() {
- final Node<K,V> cl = left;
- if (!isShared(cl)) {
- return cl;
- } else {
- lazyCopyChildren();
- return left;
- }
- }
-
- Node<K,V> unsharedRight() {
- final Node<K,V> cr = right;
- if (!isShared(cr)) {
- return cr;
- } else {
- lazyCopyChildren();
- return right;
- }
- }
-
- Node<K,V> unsharedChild(final char dir) {
- return dir == Left ? unsharedLeft() : unsharedRight();
- }
-
- private synchronized void lazyCopyChildren() {
- final Node<K,V> cl = left;
- if (isShared(cl)) {
- left = cl.lazyCopy(this);
- }
- final Node<K,V> cr = right;
- if (isShared(cr)) {
- right = cr.lazyCopy(this);
- }
- }
-
- //////// per-node blocking
-
- private void waitUntilShrinkCompleted(final long ovl) {
- if (!isShrinking(ovl)) {
- return;
- }
-
- for (int tries = 0; tries < SpinCount; ++tries) {
- if (shrinkOVL != ovl) {
- return;
- }
- }
-
- for (int tries = 0; tries < YieldCount; ++tries) {
- Thread.yield();
- if (shrinkOVL != ovl) {
- return;
- }
- }
-
- // spin and yield failed, use the nuclear option
- synchronized (this) {
- // we can't have gotten the lock unless the shrink was over
- }
- assert(shrinkOVL != ovl);
- }
-
- int validatedHeight() {
- final int hL = left == null ? 0 : left.validatedHeight();
- final int hR = right == null ? 0 : right.validatedHeight();
- assert(Math.abs(hL - hR) <= 1);
- final int h = 1 + Math.max(hL, hR);
- assert(h == height);
- return height;
- }
-
- //////// SubMap.size() helper
-
- static <K,V> int computeFrozenSize(Node<K,V> root,
- Comparable<? super K> fromCmp,
- boolean fromIncl,
- final Comparable<? super K> toCmp,
- final boolean toIncl) {
- int result = 0;
- while (true) {
- if (root == null) {
- return result;
- }
- if (fromCmp != null) {
- final int c = fromCmp.compareTo(root.key);
- if (c > 0 || (c == 0 && !fromIncl)) {
- // all matching nodes are on the right side
- root = root.right;
- continue;
- }
- }
- if (toCmp != null) {
- final int c = toCmp.compareTo(root.key);
- if (c < 0 || (c == 0 && !toIncl)) {
- // all matching nodes are on the left side
- root = root.left;
- continue;
- }
- }
-
- // Current node matches. Nodes on left no longer need toCmp, nodes
- // on right no longer need fromCmp.
- if (root.vOpt != null) {
- ++result;
- }
- result += computeFrozenSize(root.left, fromCmp, fromIncl, null, false);
- fromCmp = null;
- root = root.right;
- }
- }
-
- //////// Map.Entry stuff
-
- @Override
- public boolean equals(final Object o) {
- if (!(o instanceof Map.Entry)) {
- return false;
- }
- final Map.Entry rhs = (Map.Entry)o;
- return eq(key, rhs.getKey()) && eq(getValue(), rhs.getValue());
- }
-
- private static boolean eq(final Object o1, final Object o2) {
- return o1 == null ? o2 == null : o1.equals(o2);
- }
-
- @Override
- public int hashCode() {
- return (key == null ? 0 : key.hashCode()) ^
- (getValue() == null ? 0 : getValue().hashCode());
- }
-
- @Override
- public String toString() {
- return key + "=" + getValue();
- }
- }
-
- private static class RootHolder<K,V> extends Node<K,V> {
- RootHolder() {
- super(null, 1, null, null, 0L, null, null);
- }
-
- RootHolder(final RootHolder<K,V> snapshot) {
- super(null, 1 + snapshot.height, null, null, 0L, null, snapshot.right);
- }
- }
-
- private static class COWMgr<K,V> extends CopyOnWriteManager<RootHolder<K,V>> {
- COWMgr() {
- super(new RootHolder<K,V>(), 0);
- }
-
- COWMgr(final RootHolder<K,V> initialValue, final int initialSize) {
- super(initialValue, initialSize);
- }
-
- protected RootHolder<K,V> freezeAndClone(final RootHolder<K,V> value) {
- Node.markShared(value.right);
- return new RootHolder<K,V>(value);
- }
-
- protected RootHolder<K,V> cloneFrozen(final RootHolder<K,V> frozenValue) {
- return new RootHolder<K,V>(frozenValue);
- }
- }
-
- //////// node access functions
-
- private static int height(final Node<?,?> node) {
- return node == null ? 0 : node.height;
- }
-
- @SuppressWarnings("unchecked")
- private V decodeNull(final Object vOpt) {
- assert (vOpt != SpecialRetry);
- if (AllowNullValues) {
- return vOpt == SpecialNull ? null : (V)vOpt;
- } else {
- return (V)vOpt;
- }
- }
-
- private static Object encodeNull(final Object v) {
- if (AllowNullValues) {
- return v == null ? SpecialNull : v;
- } else {
- if (v == null) {
- throw new NullPointerException();
- }
- return v;
- }
- }
-
- //////////////// state
-
- private final Comparator<? super K> comparator;
- private transient volatile COWMgr<K,V> holderRef;
-
- //////////////// public interface
-
- public SnapTreeMap() {
- this.comparator = null;
- this.holderRef = new COWMgr<K,V>();
- }
-
- public SnapTreeMap(final Comparator<? super K> comparator) {
- this.comparator = comparator;
- this.holderRef = new COWMgr<K,V>();
- }
-
- public SnapTreeMap(final Map<? extends K, ? extends V> source) {
- this.comparator = null;
- this.holderRef = new COWMgr<K,V>();
- putAll(source);
- }
-
- public SnapTreeMap(final SortedMap<K,? extends V> source) {
- this.comparator = source.comparator();
- if (source instanceof SnapTreeMap) {
- final SnapTreeMap<K,V> s = (SnapTreeMap<K,V>) source;
- this.holderRef = (COWMgr<K,V>) s.holderRef.clone();
- }
- else {
- // TODO: take advantage of the sort order
- // for now we optimize only by bypassing the COWMgr
- int size = 0;
- final RootHolder<K,V> holder = new RootHolder<K,V>();
- for (Map.Entry<K,? extends V> e : source.entrySet()) {
- final K k = e.getKey();
- final V v = e.getValue();
- if (k == null) {
- throw new NullPointerException("source map contained a null key");
- }
- if (!AllowNullValues && v == null) {
- throw new NullPointerException("source map contained a null value");
- }
- updateUnderRoot(k, comparable(k), UpdateAlways, null, encodeNull(v), holder);
- ++size;
- }
-
- this.holderRef = new COWMgr<K,V>(holder, size);
- }
- }
-
- @SuppressWarnings("unchecked")
- @Override
- public SnapTreeMap<K,V> clone() {
- final SnapTreeMap<K,V> copy;
- try {
- copy = (SnapTreeMap<K,V>) super.clone();
- } catch (final CloneNotSupportedException xx) {
- throw new InternalError();
- }
- assert(copy.comparator == comparator);
- copy.holderRef = (COWMgr<K,V>) holderRef.clone();
- return copy;
- }
-
- @Override
- public int size() {
- return holderRef.size();
- }
-
- @Override
- public boolean isEmpty() {
- // removed-but-not-unlinked nodes cannot be leaves, so if the tree is
- // truly empty then the root holder has no right child
- return holderRef.read().right == null;
- }
-
- @Override
- public void clear() {
- holderRef = new COWMgr<K,V>();
- }
-
- @Override
- public Comparator<? super K> comparator() {
- return comparator;
- }
-
- @Override
- public boolean containsValue(final Object value) {
- // apply the same null policy as the rest of the code, but fall
- // back to the default implementation
- encodeNull(value);
- return super.containsValue(value);
- }
-
- //////// concurrent search
-
- @Override
- public boolean containsKey(final Object key) {
- return getImpl(key) != null;
- }
-
- @Override
- public V get(final Object key) {
- return decodeNull(getImpl(key));
- }
-
- @SuppressWarnings("unchecked")
- protected Comparable<? super K> comparable(final Object key) {
- if (key == null) {
- throw new NullPointerException();
- }
- if (comparator == null) {
- return (Comparable<? super K>)key;
- }
- return new Comparable<K>() {
- final Comparator<? super K> _cmp = comparator;
-
- @SuppressWarnings("unchecked")
- public int compareTo(final K rhs) { return _cmp.compare((K)key, rhs); }
- };
- }
-
- /** Returns either a value or SpecialNull, if present, or null, if absent. */
- private Object getImpl(final Object key) {
- final Comparable<? super K> k = comparable(key);
-
- while (true) {
- final Node<K,V> right = holderRef.read().right;
- if (right == null) {
- return null;
- } else {
- final int rightCmp = k.compareTo(right.key);
- if (rightCmp == 0) {
- // who cares how we got here
- return right.vOpt;
- }
-
- final long ovl = right.shrinkOVL;
- if (isShrinkingOrUnlinked(ovl)) {
- right.waitUntilShrinkCompleted(ovl);
- // RETRY
- } else if (right == holderRef.read().right) {
- // the reread of .right is the one protected by our read of ovl
- final Object vo = attemptGet(k, right, (rightCmp < 0 ? Left : Right), ovl);
- if (vo != SpecialRetry) {
- return vo;
- }
- // else RETRY
- }
- }
- }
- }
-
- private Object attemptGet(final Comparable<? super K> k,
- final Node<K,V> node,
- final char dirToC,
- final long nodeOVL) {
- while (true) {
- final Node<K,V> child = node.child(dirToC);
-
- if (child == null) {
- if (node.shrinkOVL != nodeOVL) {
- return SpecialRetry;
- }
-
- // Note is not present. Read of node.child occurred while
- // parent.child was valid, so we were not affected by any
- // shrinks.
- return null;
- } else {
- final int childCmp = k.compareTo(child.key);
- if (childCmp == 0) {
- // how we got here is irrelevant
- return child.vOpt;
- }
-
- // child is non-null
- final long childOVL = child.shrinkOVL;
- if (isShrinkingOrUnlinked(childOVL)) {
- child.waitUntilShrinkCompleted(childOVL);
-
- if (node.shrinkOVL != nodeOVL) {
- return SpecialRetry;
- }
- // else RETRY
- } else if (child != node.child(dirToC)) {
- // this .child is the one that is protected by childOVL
- if (node.shrinkOVL != nodeOVL) {
- return SpecialRetry;
- }
- // else RETRY
- } else {
- if (node.shrinkOVL != nodeOVL) {
- return SpecialRetry;
- }
-
- // At this point we know that the traversal our parent took
- // to get to node is still valid. The recursive
- // implementation will validate the traversal from node to
- // child, so just prior to the nodeOVL validation both
- // traversals were definitely okay. This means that we are
- // no longer vulnerable to node shrinks, and we don't need
- // to validate nodeOVL any more.
- final Object vo = attemptGet(k, child, (childCmp < 0 ? Left : Right), childOVL);
- if (vo != SpecialRetry) {
- return vo;
- }
- // else RETRY
- }
- }
- }
- }
-
- @Override
- public K firstKey() {
- return extremeKeyOrThrow(Left);
- }
-
- @Override
- @SuppressWarnings("unchecked")
- public Map.Entry<K,V> firstEntry() {
- return (SimpleImmutableEntry<K,V>) extreme(false, Left);
- }
-
- @Override
- public K lastKey() {
- return extremeKeyOrThrow(Right);
- }
-
- @SuppressWarnings("unchecked")
- public Map.Entry<K,V> lastEntry() {
- return (SimpleImmutableEntry<K,V>) extreme(false, Right);
- }
-
- private K extremeKeyOrThrow(final char dir) {
- final K k = (K) extreme(true, dir);
- if (k == null) {
- throw new NoSuchElementException();
- }
- return k;
- }
-
- /** Returns a key if returnKey is true, a SimpleImmutableEntry otherwise.
- * Returns null if none exists.
- */
- private Object extreme(final boolean returnKey, final char dir) {
- while (true) {
- final Node<K,V> right = holderRef.read().right;
- if (right == null) {
- return null;
- } else {
- final long ovl = right.shrinkOVL;
- if (isShrinkingOrUnlinked(ovl)) {
- right.waitUntilShrinkCompleted(ovl);
- // RETRY
- } else if (right == holderRef.read().right) {
- // the reread of .right is the one protected by our read of ovl
- final Object vo = attemptExtreme(returnKey, dir, right, ovl);
- if (vo != SpecialRetry) {
- return vo;
- }
- // else RETRY
- }
- }
- }
- }
-
- private Object attemptExtreme(final boolean returnKey,
- final char dir,
- final Node<K,V> node,
- final long nodeOVL) {
- while (true) {
- final Node<K,V> child = node.child(dir);
-
- if (child == null) {
- // read of the value must be protected by the OVL, because we
- // must linearize against another thread that inserts a new min
- // key and then changes this key's value
- final Object vo = node.vOpt;
-
- if (node.shrinkOVL != nodeOVL) {
- return SpecialRetry;
- }
-
- assert(vo != null);
-
- return returnKey ? node.key : new SimpleImmutableEntry<K,V>(node.key, decodeNull(vo));
- } else {
- // child is non-null
- final long childOVL = child.shrinkOVL;
- if (isShrinkingOrUnlinked(childOVL)) {
- child.waitUntilShrinkCompleted(childOVL);
-
- if (node.shrinkOVL != nodeOVL) {
- return SpecialRetry;
- }
- // else RETRY
- } else if (child != node.child(dir)) {
- // this .child is the one that is protected by childOVL
- if (node.shrinkOVL != nodeOVL) {
- return SpecialRetry;
- }
- // else RETRY
- } else {
- if (node.shrinkOVL != nodeOVL) {
- return SpecialRetry;
- }
-
- final Object vo = attemptExtreme(returnKey, dir, child, childOVL);
- if (vo != SpecialRetry) {
- return vo;
- }
- // else RETRY
- }
- }
- }
- }
-
- //////////////// quiesced search
-
- @Override
- @SuppressWarnings("unchecked")
- public K lowerKey(final K key) {
- return (K) boundedExtreme(null, false, comparable(key), false, true, Right);
- }
-
- @Override
- @SuppressWarnings("unchecked")
- public K floorKey(final K key) {
- return (K) boundedExtreme(null, false, comparable(key), true, true, Right);
- }
-
- @Override
- @SuppressWarnings("unchecked")
- public K ceilingKey(final K key) {
- return (K) boundedExtreme(comparable(key), true, null, false, true, Left);
- }
-
- @Override
- @SuppressWarnings("unchecked")
- public K higherKey(final K key) {
- return (K) boundedExtreme(comparable(key), false, null, false, true, Left);
- }
-
-
- @Override
- @SuppressWarnings("unchecked")
- public Entry<K,V> lowerEntry(final K key) {
- return (Entry<K,V>) boundedExtreme(null, false, comparable(key), false, false, Right);
- }
-
- @Override
- @SuppressWarnings("unchecked")
- public Entry<K,V> floorEntry(final K key) {
- return (Entry<K,V>) boundedExtreme(null, false, comparable(key), true, false, Right);
- }
-
- @Override
- @SuppressWarnings("unchecked")
- public Entry<K,V> ceilingEntry(final K key) {
- return (Entry<K,V>) boundedExtreme(comparable(key), true, null, false, false, Left);
- }
-
- @Override
- @SuppressWarnings("unchecked")
- public Entry<K,V> higherEntry(final K key) {
- return (Entry<K,V>) boundedExtreme(comparable(key), false, null, false, false, Left);
- }
-
- /** Returns null if none exists. */
- @SuppressWarnings("unchecked")
- private K boundedExtremeKeyOrThrow(final Comparable<? super K> minCmp,
- final boolean minIncl,
- final Comparable<? super K> maxCmp,
- final boolean maxIncl,
- final char dir) {
- final K k = (K) boundedExtreme(minCmp, minIncl, maxCmp, maxIncl, true, dir);
- if (k == null) {
- throw new NoSuchElementException();
- }
- return k;
- }
-
- /** Returns null if none exists. */
- @SuppressWarnings("unchecked")
- private Object boundedExtreme(final Comparable<? super K> minCmp,
- final boolean minIncl,
- final Comparable<? super K> maxCmp,
- final boolean maxIncl,
- final boolean returnKey,
- final char dir) {
- K resultKey;
- Object result;
-
- if ((dir == Left && minCmp == null) || (dir == Right && maxCmp == null)) {
- // no bound in the extreme direction, so use the concurrent search
- result = extreme(returnKey, dir);
- if (result == null) {
- return null;
- }
- resultKey = returnKey ? (K) result : ((SimpleImmutableEntry<K,V>) result).getKey();
- }
- else {
- RootHolder holder = holderRef.availableFrozen();
- final Epoch.Ticket ticket;
- if (holder == null) {
- ticket = holderRef.beginQuiescent();
- holder = holderRef.read();
- }
- else {
- ticket = null;
- }
- try {
- final Node<K,V> node = (dir == Left)
- ? boundedMin(holder.right, minCmp, minIncl)
- : boundedMax(holder.right, maxCmp, maxIncl);
- if (node == null) {
- return null;
- }
- resultKey = node.key;
- if (returnKey) {
- result = node.key;
- }
- else if (ticket == null) {
- // node of a frozen tree is okay, copy otherwise
- result = node;
- }
- else {
- // we must copy the node
- result = new SimpleImmutableEntry<K,V>(node.key, node.getValue());
- }
- }
- finally {
- if (ticket != null) {
- ticket.leave(0);
- }
- }
- }
-
- if (dir == Left && maxCmp != null) {
- final int c = maxCmp.compareTo(resultKey);
- if (c < 0 || (c == 0 && !maxIncl)) {
- return null;
- }
- }
- if (dir == Right && minCmp != null) {
- final int c = minCmp.compareTo(resultKey);
- if (c > 0 || (c == 0 && !minIncl)) {
- return null;
- }
- }
-
- return result;
- }
-
- private Node<K,V> boundedMin(Node<K,V> node,
- final Comparable<? super K> minCmp,
- final boolean minIncl) {
- while (node != null) {
- final int c = minCmp.compareTo(node.key);
- if (c < 0) {
- // there may be a matching node on the left branch
- final Node<K,V> z = boundedMin(node.left, minCmp, minIncl);
- if (z != null) {
- return z;
- }
- }
-
- if (c < 0 || (c == 0 && minIncl)) {
- // this node is a candidate, is it actually present?
- if (node.vOpt != null) {
- return node;
- }
- }
-
- // the matching node is on the right branch if it is present
- node = node.right;
- }
- return null;
- }
-
- private Node<K,V> boundedMax(Node<K,V> node,
- final Comparable<? super K> maxCmp,
- final boolean maxIncl) {
- while (node != null) {
- final int c = maxCmp.compareTo(node.key);
- if (c > 0) {
- // there may be a matching node on the right branch
- final Node<K,V> z = boundedMax(node.right, maxCmp, maxIncl);
- if (z != null) {
- return z;
- }
- }
-
- if (c > 0 || (c == 0 && maxIncl)) {
- // this node is a candidate, is it actually present?
- if (node.vOpt != null) {
- return node;
- }
- }
-
- // the matching node is on the left branch if it is present
- node = node.left;
- }
- return null;
- }
-
- //////////////// update
-
- private static final int UpdateAlways = 0;
- private static final int UpdateIfAbsent = 1;
- private static final int UpdateIfPresent = 2;
- private static final int UpdateIfEq = 3;
-
- private static boolean shouldUpdate(final int func, final Object prev, final Object expected) {
- switch (func) {
- case UpdateAlways: return true;
- case UpdateIfAbsent: return prev == null;
- case UpdateIfPresent: return prev != null;
- default: { // UpdateIfEq
- assert(expected != null);
- if (prev == null) {
- return false;
- }
- if (AllowNullValues && (prev == SpecialNull || expected == SpecialNull)) {
- return prev == SpecialNull && expected == SpecialNull;
- }
- return prev.equals(expected);
- }
- }
- }
-
- private static Object noUpdateResult(final int func, final Object prev) {
- return func == UpdateIfEq ? Boolean.FALSE : prev;
- }
-
- private static Object updateResult(final int func, final Object prev) {
- return func == UpdateIfEq ? Boolean.TRUE : prev;
- }
-
- private static int sizeDelta(final int func, final Object result, final Object newValue) {
- switch (func) {
- case UpdateAlways: {
- return (result != null ? -1 : 0) + (newValue != null ? 1 : 0);
- }
- case UpdateIfAbsent: {
- assert(newValue != null);
- return result != null ? 0 : 1;
- }
- case UpdateIfPresent: {
- return result == null ? 0 : (newValue != null ? 0 : -1);
- }
- default: { // UpdateIfEq
- return !((Boolean) result) ? 0 : (newValue != null ? 0 : -1);
- }
- }
- }
-
- @Override
- public V put(final K key, final V value) {
- return decodeNull(update(key, UpdateAlways, null, encodeNull(value)));
- }
-
- @Override
- public V putIfAbsent(final K key, final V value) {
- return decodeNull(update(key, UpdateIfAbsent, null, encodeNull(value)));
- }
-
- @Override
- public V replace(final K key, final V value) {
- return decodeNull(update(key, UpdateIfPresent, null, encodeNull(value)));
- }
-
- @Override
- public boolean replace(final K key, final V oldValue, final V newValue) {
- return (Boolean) update(key, UpdateIfEq, encodeNull(oldValue), encodeNull(newValue));
- }
-
- @Override
- public V remove(final Object key) {
- return decodeNull(update(key, UpdateAlways, null, null));
- }
-
- @Override
- public boolean remove(final Object key, final Object value) {
- if (key == null) {
- throw new NullPointerException();
- }
- if (!AllowNullValues && value == null) {
- return false;
- }
- return (Boolean) update(key, UpdateIfEq, encodeNull(value), null);
- }
-
- // manages the epoch
- private Object update(final Object key,
- final int func,
- final Object expected,
- final Object newValue) {
- final Comparable<? super K> k = comparable(key);
- int sd = 0;
- final Epoch.Ticket ticket = holderRef.beginMutation();
- try {
- final Object result = updateUnderRoot(key, k, func, expected, newValue, holderRef.mutable());
- sd = sizeDelta(func, result, newValue);
- return result;
- } finally {
- ticket.leave(sd);
- }
- }
-
- // manages updates to the root holder
- @SuppressWarnings("unchecked")
- private Object updateUnderRoot(final Object key,
- final Comparable<? super K> k,
- final int func,
- final Object expected,
- final Object newValue,
- final RootHolder<K,V> holder) {
-
- while (true) {
- final Node<K,V> right = holder.unsharedRight();
- if (right == null) {
- // key is not present
- if (!shouldUpdate(func, null, expected)) {
- return noUpdateResult(func, null);
- }
- if (newValue == null || attemptInsertIntoEmpty((K)key, newValue, holder)) {
- // nothing needs to be done, or we were successful, prev value is Absent
- return updateResult(func, null);
- }
- // else RETRY
- } else {
- final long ovl = right.shrinkOVL;
- if (isShrinkingOrUnlinked(ovl)) {
- right.waitUntilShrinkCompleted(ovl);
- // RETRY
- } else if (right == holder.right) {
- // this is the protected .right
- final Object vo = attemptUpdate(key, k, func, expected, newValue, holder, right, ovl);
- if (vo != SpecialRetry) {
- return vo;
- }
- // else RETRY
- }
- }
- }
- }
-
- private boolean attemptInsertIntoEmpty(final K key,
- final Object vOpt,
- final RootHolder<K,V> holder) {
- synchronized (holder) {
- if (holder.right == null) {
- holder.right = new Node<K,V>(key, 1, vOpt, holder, 0L, null, null);
- holder.height = 2;
- return true;
- } else {
- return false;
- }
- }
- }
-
- /** If successful returns the non-null previous value, SpecialNull for a
- * null previous value, or null if not previously in the map.
- * The caller should retry if this method returns SpecialRetry.
- */
- @SuppressWarnings("unchecked")
- private Object attemptUpdate(final Object key,
- final Comparable<? super K> k,
- final int func,
- final Object expected,
- final Object newValue,
- final Node<K,V> parent,
- final Node<K,V> node,
- final long nodeOVL) {
- // As the search progresses there is an implicit min and max assumed for the
- // branch of the tree rooted at node. A left rotation of a node x results in
- // the range of keys in the right branch of x being reduced, so if we are at a
- // node and we wish to traverse to one of the branches we must make sure that
- // the node has not undergone a rotation since arriving from the parent.
- //
- // A rotation of node can't screw us up once we have traversed to node's
- // child, so we don't need to build a huge transaction, just a chain of
- // smaller read-only transactions.
-
- assert (nodeOVL != UnlinkedOVL);
-
- final int cmp = k.compareTo(node.key);
- if (cmp == 0) {
- return attemptNodeUpdate(func, expected, newValue, parent, node);
- }
-
- final char dirToC = cmp < 0 ? Left : Right;
-
- while (true) {
- final Node<K,V> child = node.unsharedChild(dirToC);
-
- if (node.shrinkOVL != nodeOVL) {
- return SpecialRetry;
- }
-
- if (child == null) {
- // key is not present
- if (newValue == null) {
- // Removal is requested. Read of node.child occurred
- // while parent.child was valid, so we were not affected
- // by any shrinks.
- return noUpdateResult(func, null);
- } else {
- // Update will be an insert.
- final boolean success;
- final Node<K,V> damaged;
- synchronized (node) {
- // Validate that we haven't been affected by past
- // rotations. We've got the lock on node, so no future
- // rotations can mess with us.
- if (node.shrinkOVL != nodeOVL) {
- return SpecialRetry;
- }
-
- if (node.child(dirToC) != null) {
- // Lost a race with a concurrent insert. No need
- // to back up to the parent, but we must RETRY in
- // the outer loop of this method.
- success = false;
- damaged = null;
- } else {
- // We're valid. Does the user still want to
- // perform the operation?
- if (!shouldUpdate(func, null, expected)) {
- return noUpdateResult(func, null);
- }
-
- // Create a new leaf
- node.setChild(dirToC, new Node<K,V>((K)key, 1, newValue, node, 0L, null, null));
- success = true;
-
- // attempt to fix node.height while we've still got
- // the lock
- damaged = fixHeight_nl(node);
- }
- }
- if (success) {
- fixHeightAndRebalance(damaged);
- return updateResult(func, null);
- }
- // else RETRY
- }
- } else {
- // non-null child
- final long childOVL = child.shrinkOVL;
- if (isShrinkingOrUnlinked(childOVL)) {
- child.waitUntilShrinkCompleted(childOVL);
- // RETRY
- } else if (child != node.child(dirToC)) {
- // this second read is important, because it is protected
- // by childOVL
- // RETRY
- } else {
- // validate the read that our caller took to get to node
- if (node.shrinkOVL != nodeOVL) {
- return SpecialRetry;
- }
-
- // At this point we know that the traversal our parent took
- // to get to node is still valid. The recursive
- // implementation will validate the traversal from node to
- // child, so just prior to the nodeOVL validation both
- // traversals were definitely okay. This means that we are
- // no longer vulnerable to node shrinks, and we don't need
- // to validate nodeOVL any more.
- final Object vo = attemptUpdate(key, k, func, expected, newValue, node, child, childOVL);
- if (vo != SpecialRetry) {
- return vo;
- }
- // else RETRY
- }
- }
- }
- }
-
- /** parent will only be used for unlink, update can proceed even if parent
- * is stale.
- */
- private Object attemptNodeUpdate(final int func,
- final Object expected,
- final Object newValue,
- final Node<K,V> parent,
- final Node<K,V> node) {
- if (newValue == null) {
- // removal
- if (node.vOpt == null) {
- // This node is already removed, nothing to do.
- return noUpdateResult(func, null);
- }
- }
-
- if (newValue == null && (node.left == null || node.right == null)) {
- // potential unlink, get ready by locking the parent
- final Object prev;
- final Node<K,V> damaged;
- synchronized (parent) {
- if (isUnlinked(parent.shrinkOVL) || node.parent != parent) {
- return SpecialRetry;
- }
-
- synchronized (node) {
- prev = node.vOpt;
- if (!shouldUpdate(func, prev, expected)) {
- return noUpdateResult(func, prev);
- }
- if (prev == null) {
- return updateResult(func, prev);
- }
- if (!attemptUnlink_nl(parent, node)) {
- return SpecialRetry;
- }
- }
- // try to fix the parent while we've still got the lock
- damaged = fixHeight_nl(parent);
- }
- fixHeightAndRebalance(damaged);
- return updateResult(func, prev);
- } else {
- // potential update (including remove-without-unlink)
- synchronized (node) {
- // regular version changes don't bother us
- if (isUnlinked(node.shrinkOVL)) {
- return SpecialRetry;
- }
-
- final Object prev = node.vOpt;
- if (!shouldUpdate(func, prev, expected)) {
- return noUpdateResult(func, prev);
- }
-
- // retry if we now detect that unlink is possible
- if (newValue == null && (node.left == null || node.right == null)) {
- return SpecialRetry;
- }
-
- // update in-place
- node.vOpt = newValue;
-
- afterNodeUpdate_nl(node, newValue);
-
- return updateResult(func, prev);
- }
- }
- }
-
- protected void afterNodeUpdate_nl(Node<K,V> node, Object val) {
- }
-
- /** Does not adjust the size or any heights. */
- private boolean attemptUnlink_nl(final Node<K,V> parent, final Node<K,V> node) {
- // assert (Thread.holdsLock(parent));
- // assert (Thread.holdsLock(node));
- assert (!isUnlinked(parent.shrinkOVL));
-
- final Node<K,V> parentL = parent.left;
- final Node<K,V> parentR = parent.right;
- if (parentL != node && parentR != node) {
- // node is no longer a child of parent
- return false;
- }
-
- assert (!isUnlinked(node.shrinkOVL));
- assert (parent == node.parent);
-
- final Node<K,V> left = node.unsharedLeft();
- final Node<K,V> right = node.unsharedRight();
- if (left != null && right != null) {
- // splicing is no longer possible
- return false;
- }
- final Node<K,V> splice = left != null ? left : right;
-
- if (parentL == node) {
- parent.left = splice;
- } else {
- parent.right = splice;
- }
- if (splice != null) {
- splice.parent = parent;
- }
-
- node.shrinkOVL = UnlinkedOVL;
- node.vOpt = null;
-
- return true;
- }
-
- //////////////// NavigableMap stuff
-
- @Override
- public Map.Entry<K,V> pollFirstEntry() {
- return pollExtremeEntry(Left);
- }
-
- @Override
- public Map.Entry<K,V> pollLastEntry() {
- return pollExtremeEntry(Right);
- }
-
- private Map.Entry<K,V> pollExtremeEntry(final char dir) {
- final Epoch.Ticket ticket = holderRef.beginMutation();
- int sizeDelta = 0;
- try {
- final Map.Entry<K,V> prev = pollExtremeEntryUnderRoot(dir, holderRef.mutable());
- if (prev != null) {
- sizeDelta = -1;
- }
- return prev;
- } finally {
- ticket.leave(sizeDelta);
- }
- }
-
- private Map.Entry<K,V> pollExtremeEntryUnderRoot(final char dir, final RootHolder<K,V> holder) {
- while (true) {
- final Node<K,V> right = holder.unsharedRight();
- if (right == null) {
- // tree is empty, nothing to remove
- return null;
- } else {
- final long ovl = right.shrinkOVL;
- if (isShrinkingOrUnlinked(ovl)) {
- right.waitUntilShrinkCompleted(ovl);
- // RETRY
- } else if (right == holder.right) {
- // this is the protected .right
- final Map.Entry<K,V> result = attemptRemoveExtreme(dir, holder, right, ovl);
- if (result != SpecialRetry) {
- return result;
- }
- // else RETRY
- }
- }
- }
- }
-
- private Map.Entry<K,V> attemptRemoveExtreme(final char dir,
- final Node<K,V> parent,
- final Node<K,V> node,
- final long nodeOVL) {
- assert (nodeOVL != UnlinkedOVL);
-
- while (true) {
- final Node<K,V> child = node.unsharedChild(dir);
-
- if (nodeOVL != node.shrinkOVL) {
- return null;
- }
-
- if (child == null) {
- // potential unlink, get ready by locking the parent
- final Object vo;
- final Node<K,V> damaged;
- synchronized (parent) {
- if (isUnlinked(parent.shrinkOVL) || node.parent != parent) {
- return null;
- }
-
- synchronized (node) {
- vo = node.vOpt;
- if (node.child(dir) != null || !attemptUnlink_nl(parent, node)) {
- return null;
- }
- // success!
- }
- // try to fix parent.height while we've still got the lock
- damaged = fixHeight_nl(parent);
- }
- fixHeightAndRebalance(damaged);
- return new SimpleImmutableEntry<K,V>(node.key, decodeNull(vo));
- } else {
- // keep going down
- final long childOVL = child.shrinkOVL;
- if (isShrinkingOrUnlinked(childOVL)) {
- child.waitUntilShrinkCompleted(childOVL);
- // RETRY
- } else if (child != node.child(dir)) {
- // this second read is important, because it is protected
- // by childOVL
- // RETRY
- } else {
- // validate the read that our caller took to get to node
- if (node.shrinkOVL != nodeOVL) {
- return null;
- }
-
- final Map.Entry<K,V> result = attemptRemoveExtreme(dir, node, child, childOVL);
- if (result != null) {
- return result;
- }
- // else RETRY
- }
- }
- }
- }
-
-
-
- //////////////// tree balance and height info repair
-
- private static final int UnlinkRequired = -1;
- private static final int RebalanceRequired = -2;
- private static final int NothingRequired = -3;
-
- private int nodeCondition(final Node<K,V> node) {
- // Begin atomic.
-
- final Node<K,V> nL = node.left;
- final Node<K,V> nR = node.right;
-
- if ((nL == null || nR == null) && node.vOpt == null) {
- return UnlinkRequired;
- }
-
- final int hN = node.height;
- final int hL0 = height(nL);
- final int hR0 = height(nR);
-
- // End atomic. Since any thread that changes a node promises to fix
- // it, either our read was consistent (and a NothingRequired conclusion
- // is correct) or someone else has taken responsibility for either node
- // or one of its children.
-
- final int hNRepl = 1 + Math.max(hL0, hR0);
- final int bal = hL0 - hR0;
-
- if (bal < -1 || bal > 1) {
- return RebalanceRequired;
- }
-
- return hN != hNRepl ? hNRepl : NothingRequired;
- }
-
- private void fixHeightAndRebalance(Node<K,V> node) {
- while (node != null && node.parent != null) {
- final int condition = nodeCondition(node);
- if (condition == NothingRequired || isUnlinked(node.shrinkOVL)) {
- // nothing to do, or no point in fixing this node
- return;
- }
-
- if (condition != UnlinkRequired && condition != RebalanceRequired) {
- synchronized (node) {
- node = fixHeight_nl(node);
- }
- } else {
- final Node<K,V> nParent = node.parent;
- synchronized (nParent) {
- if (!isUnlinked(nParent.shrinkOVL) && node.parent == nParent) {
- synchronized (node) {
- node = rebalance_nl(nParent, node);
- }
- }
- // else RETRY
- }
- }
- }
- }
-
- /** Attempts to fix the height of a (locked) damaged node, returning the
- * lowest damaged node for which this thread is responsible. Returns null
- * if no more repairs are needed.
- */
- private Node<K,V> fixHeight_nl(final Node<K,V> node) {
- final int c = nodeCondition(node);
- switch (c) {
- case RebalanceRequired:
- case UnlinkRequired:
- // can't repair
- return node;
- case NothingRequired:
- // Any future damage to this node is not our responsibility.
- return null;
- default:
- node.height = c;
- // we've damaged our parent, but we can't fix it now
- return node.parent;
- }
- }
-
- /** nParent and n must be locked on entry. Returns a damaged node, or null
- * if no more rebalancing is necessary.
- */
- private Node<K,V> rebalance_nl(final Node<K,V> nParent, final Node<K,V> n) {
-
- final Node<K,V> nL = n.unsharedLeft();
- final Node<K,V> nR = n.unsharedRight();
-
- if ((nL == null || nR == null) && n.vOpt == null) {
- if (attemptUnlink_nl(nParent, n)) {
- // attempt to fix nParent.height while we've still got the lock
- return fixHeight_nl(nParent);
- } else {
- // retry needed for n
- return n;
- }
- }
-
- final int hN = n.height;
- final int hL0 = height(nL);
- final int hR0 = height(nR);
- final int hNRepl = 1 + Math.max(hL0, hR0);
- final int bal = hL0 - hR0;
-
- if (bal > 1) {
- return rebalanceToRight_nl(nParent, n, nL, hR0);
- } else if (bal < -1) {
- return rebalanceToLeft_nl(nParent, n, nR, hL0);
- } else if (hNRepl != hN) {
- // we've got more than enough locks to do a height change, no need to
- // trigger a retry
- n.height = hNRepl;
-
- // nParent is already locked, let's try to fix it too
- return fixHeight_nl(nParent);
- } else {
- // nothing to do
- return null;
- }
- }
-
- private Node<K,V> rebalanceToRight_nl(final Node<K,V> nParent,
- final Node<K,V> n,
- final Node<K,V> nL,
- final int hR0) {
- // L is too large, we will rotate-right. If L.R is taller
- // than L.L, then we will first rotate-left L.
- synchronized (nL) {
- final int hL = nL.height;
- if (hL - hR0 <= 1) {
- return n; // retry
- } else {
- final Node<K,V> nLR = nL.unsharedRight();
- final int hLL0 = height(nL.left);
- final int hLR0 = height(nLR);
- if (hLL0 >= hLR0) {
- // rotate right based on our snapshot of hLR
- return rotateRight_nl(nParent, n, nL, hR0, hLL0, nLR, hLR0);
- } else {
- synchronized (nLR) {
- // If our hLR snapshot is incorrect then we might
- // actually need to do a single rotate-right on n.
- final int hLR = nLR.height;
- if (hLL0 >= hLR) {
- return rotateRight_nl(nParent, n, nL, hR0, hLL0, nLR, hLR);
- } else {
- // If the underlying left balance would not be
- // sufficient to actually fix n.left, then instead
- // of rolling it into a double rotation we do it on
- // it's own. This may let us avoid rotating n at
- // all, but more importantly it avoids the creation
- // of damaged nodes that don't have a direct
- // ancestry relationship. The recursive call to
- // rebalanceToRight_nl in this case occurs after we
- // release the lock on nLR.
- //
- // We also need to avoid damaging n.left if post-
- // rotation it would be an unnecessary routing node.
- // Note that although our height snapshots might be
- // stale, their zero/non-zero state can't be.
- final int hLRL = height(nLR.left);
- final int b = hLL0 - hLRL;
- if (b >= -1 && b <= 1 && !((hLL0 == 0 || hLRL == 0) && nL.vOpt == null)) {
- // nParent.child.left won't be damaged after a double rotation
- return rotateRightOverLeft_nl(nParent, n, nL, hR0, hLL0, nLR, hLRL);
- }
- }
- }
- // focus on nL, if necessary n will be balanced later
- return rebalanceToLeft_nl(n, nL, nLR, hLL0);
- }
- }
- }
- }
-
- private Node<K,V> rebalanceToLeft_nl(final Node<K,V> nParent,
- final Node<K,V> n,
- final Node<K,V> nR,
- final int hL0) {
- synchronized (nR) {
- final int hR = nR.height;
- if (hL0 - hR >= -1) {
- return n; // retry
- } else {
- final Node<K,V> nRL = nR.unsharedLeft();
- final int hRL0 = height(nRL);
- final int hRR0 = height(nR.right);
- if (hRR0 >= hRL0) {
- return rotateLeft_nl(nParent, n, hL0, nR, nRL, hRL0, hRR0);
- } else {
- synchronized (nRL) {
- final int hRL = nRL.height;
- if (hRR0 >= hRL) {
- return rotateLeft_nl(nParent, n, hL0, nR, nRL, hRL, hRR0);
- } else {
- final int hRLR = height(nRL.right);
- final int b = hRR0 - hRLR;
- if (b >= -1 && b <= 1 && !((hRR0 == 0 || hRLR == 0) && nR.vOpt == null)) {
- return rotateLeftOverRight_nl(nParent, n, hL0, nR, nRL, hRR0, hRLR);
- }
- }
- }
- return rebalanceToRight_nl(n, nR, nRL, hRR0);
- }
- }
- }
- }
-
- private Node<K,V> rotateRight_nl(final Node<K,V> nParent,
- final Node<K,V> n,
- final Node<K,V> nL,
- final int hR,
- final int hLL,
- final Node<K,V> nLR,
- final int hLR) {
- final long nodeOVL = n.shrinkOVL;
-
- final Node<K,V> nPL = nParent.left;
-
- n.shrinkOVL = beginChange(nodeOVL);
-
- n.left = nLR;
- if (nLR != null) {
- nLR.parent = n;
- }
-
- nL.right = n;
- n.parent = nL;
-
- if (nPL == n) {
- nParent.left = nL;
- } else {
- nParent.right = nL;
- }
- nL.parent = nParent;
-
- // fix up heights links
- final int hNRepl = 1 + Math.max(hLR, hR);
- n.height = hNRepl;
- nL.height = 1 + Math.max(hLL, hNRepl);
-
- n.shrinkOVL = endChange(nodeOVL);
-
- // We have damaged nParent, n (now parent.child.right), and nL (now
- // parent.child). n is the deepest. Perform as many fixes as we can
- // with the locks we've got.
-
- // We've already fixed the height for n, but it might still be outside
- // our allowable balance range. In that case a simple fixHeight_nl
- // won't help.
- final int balN = hLR - hR;
- if (balN < -1 || balN > 1) {
- // we need another rotation at n
- return n;
- }
-
- // we've fixed balance and height damage for n, now handle
- // extra-routing node damage
- if ((nLR == null || hR == 0) && n.vOpt == null) {
- // we need to remove n and then repair
- return n;
- }
-
- // we've already fixed the height at nL, do we need a rotation here?
- final int balL = hLL - hNRepl;
- if (balL < -1 || balL > 1) {
- return nL;
- }
-
- // nL might also have routing node damage (if nL.left was null)
- if (hLL == 0 && nL.vOpt == null) {
- return nL;
- }
-
- // try to fix the parent height while we've still got the lock
- return fixHeight_nl(nParent);
- }
-
- private Node<K,V> rotateLeft_nl(final Node<K,V> nParent,
- final Node<K,V> n,
- final int hL,
- final Node<K,V> nR,
- final Node<K,V> nRL,
- final int hRL,
- final int hRR) {
- final long nodeOVL = n.shrinkOVL;
-
- final Node<K,V> nPL = nParent.left;
-
- n.shrinkOVL = beginChange(nodeOVL);
-
- // fix up n links, careful to be compatible with concurrent traversal for all but n
- n.right = nRL;
- if (nRL != null) {
- nRL.parent = n;
- }
-
- nR.left = n;
- n.parent = nR;
-
- if (nPL == n) {
- nParent.left = nR;
- } else {
- nParent.right = nR;
- }
- nR.parent = nParent;
-
- // fix up heights
- final int hNRepl = 1 + Math.max(hL, hRL);
- n.height = hNRepl;
- nR.height = 1 + Math.max(hNRepl, hRR);
-
- n.shrinkOVL = endChange(nodeOVL);
-
- final int balN = hRL - hL;
- if (balN < -1 || balN > 1) {
- return n;
- }
-
- if ((nRL == null || hL == 0) && n.vOpt == null) {
- return n;
- }
-
- final int balR = hRR - hNRepl;
- if (balR < -1 || balR > 1) {
- return nR;
- }
-
- if (hRR == 0 && nR.vOpt == null) {
- return nR;
- }
-
- return fixHeight_nl(nParent);
- }
-
- private Node<K,V> rotateRightOverLeft_nl(final Node<K,V> nParent,
- final Node<K,V> n,
- final Node<K,V> nL,
- final int hR,
- final int hLL,
- final Node<K,V> nLR,
- final int hLRL) {
- final long nodeOVL = n.shrinkOVL;
- final long leftOVL = nL.shrinkOVL;
-
- final Node<K,V> nPL = nParent.left;
- final Node<K,V> nLRL = nLR.unsharedLeft();
- final Node<K,V> nLRR = nLR.unsharedRight();
- final int hLRR = height(nLRR);
-
- n.shrinkOVL = beginChange(nodeOVL);
- nL.shrinkOVL = beginChange(leftOVL);
-
- // fix up n links, careful about the order!
- n.left = nLRR;
- if (nLRR != null) {
- nLRR.parent = n;
- }
-
- nL.right = nLRL;
- if (nLRL != null) {
- nLRL.parent = nL;
- }
-
- nLR.left = nL;
- nL.parent = nLR;
- nLR.right = n;
- n.parent = nLR;
-
- if (nPL == n) {
- nParent.left = nLR;
- } else {
- nParent.right = nLR;
- }
- nLR.parent = nParent;
-
- // fix up heights
- final int hNRepl = 1 + Math.max(hLRR, hR);
- n.height = hNRepl;
- final int hLRepl = 1 + Math.max(hLL, hLRL);
- nL.height = hLRepl;
- nLR.height = 1 + Math.max(hLRepl, hNRepl);
-
- n.shrinkOVL = endChange(nodeOVL);
- nL.shrinkOVL = endChange(leftOVL);
-
- // caller should have performed only a single rotation if nL was going
- // to end up damaged
- assert(Math.abs(hLL - hLRL) <= 1);
- assert(!((hLL == 0 || nLRL == null) && nL.vOpt == null));
-
- // We have damaged nParent, nLR (now parent.child), and n (now
- // parent.child.right). n is the deepest. Perform as many fixes as we
- // can with the locks we've got.
-
- // We've already fixed the height for n, but it might still be outside
- // our allowable balance range. In that case a simple fixHeight_nl
- // won't help.
- final int balN = hLRR - hR;
- if (balN < -1 || balN > 1) {
- // we need another rotation at n
- return n;
- }
-
- // n might also be damaged by being an unnecessary routing node
- if ((nLRR == null || hR == 0) && n.vOpt == null) {
- // repair involves splicing out n and maybe more rotations
- return n;
- }
-
- // we've already fixed the height at nLR, do we need a rotation here?
- final int balLR = hLRepl - hNRepl;
- if (balLR < -1 || balLR > 1) {
- return nLR;
- }
-
- // try to fix the parent height while we've still got the lock
- return fixHeight_nl(nParent);
- }
-
- private Node<K,V> rotateLeftOverRight_nl(final Node<K,V> nParent,
- final Node<K,V> n,
- final int hL,
- final Node<K,V> nR,
- final Node<K,V> nRL,
- final int hRR,
- final int hRLR) {
- final long nodeOVL = n.shrinkOVL;
- final long rightOVL = nR.shrinkOVL;
-
- final Node<K,V> nPL = nParent.left;
- final Node<K,V> nRLL = nRL.unsharedLeft();
- final Node<K,V> nRLR = nRL.unsharedRight();
- final int hRLL = height(nRLL);
-
- n.shrinkOVL = beginChange(nodeOVL);
- nR.shrinkOVL = beginChange(rightOVL);
-
- // fix up n links, careful about the order!
- n.right = nRLL;
- if (nRLL != null) {
- nRLL.parent = n;
- }
-
- nR.left = nRLR;
- if (nRLR != null) {
- nRLR.parent = nR;
- }
-
- nRL.right = nR;
- nR.parent = nRL;
- nRL.left = n;
- n.parent = nRL;
-
- if (nPL == n) {
- nParent.left = nRL;
- } else {
- nParent.right = nRL;
- }
- nRL.parent = nParent;
-
- // fix up heights
- final int hNRepl = 1 + Math.max(hL, hRLL);
- n.height = hNRepl;
- final int hRRepl = 1 + Math.max(hRLR, hRR);
- nR.height = hRRepl;
- nRL.height = 1 + Math.max(hNRepl, hRRepl);
-
- n.shrinkOVL = endChange(nodeOVL);
- nR.shrinkOVL = endChange(rightOVL);
-
- assert(Math.abs(hRR - hRLR) <= 1);
-
- final int balN = hRLL - hL;
- if (balN < -1 || balN > 1) {
- return n;
- }
- if ((nRLL == null || hL == 0) && n.vOpt == null) {
- return n;
- }
- final int balRL = hRRepl - hNRepl;
- if (balRL < -1 || balRL > 1) {
- return nRL;
- }
- return fixHeight_nl(nParent);
- }
-
- //////////////// Map views
-
- @Override
- public NavigableSet<K> keySet() {
- return navigableKeySet();
- }
-
- @Override
- public Set<Map.Entry<K,V>> entrySet() {
- return new EntrySet();
- }
-
- private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
-
- @Override
- public int size() {
- return SnapTreeMap.this.size();
- }
-
- @Override
- public boolean isEmpty() {
- return SnapTreeMap.this.isEmpty();
- }
-
- @Override
- public void clear() {
- SnapTreeMap.this.clear();
- }
-
- @Override
- public boolean contains(final Object o) {
- if (!(o instanceof Map.Entry<?,?>)) {
- return false;
- }
- final Object k = ((Map.Entry<?,?>)o).getKey();
- final Object v = ((Map.Entry<?,?>)o).getValue();
- final Object actualVo = SnapTreeMap.this.getImpl(k);
- if (actualVo == null) {
- // no associated value
- return false;
- }
- final V actual = decodeNull(actualVo);
- return v == null ? actual == null : v.equals(actual);
- }
-
- @Override
- public boolean add(final Entry<K,V> e) {
- final Object v = encodeNull(e.getValue());
- return update(e.getKey(), UpdateAlways, null, v) != v;
- }
-
- @Override
- public boolean remove(final Object o) {
- if (!(o instanceof Map.Entry<?,?>)) {
- return false;
- }
- final Object k = ((Map.Entry<?,?>)o).getKey();
- final Object v = ((Map.Entry<?,?>)o).getValue();
- return SnapTreeMap.this.remove(k, v);
- }
-
- @Override
- public Iterator<Entry<K,V>> iterator() {
- return new EntryIter<K,V>(SnapTreeMap.this);
- }
- }
-
- private static class EntryIter<K,V> extends AbstractIter<K,V> implements Iterator<Map.Entry<K,V>> {
- private EntryIter(final SnapTreeMap<K,V> m) {
- super(m);
- }
-
- private EntryIter(final SnapTreeMap<K,V> m,
- final Comparable<? super K> minCmp,
- final boolean minIncl,
- final Comparable<? super K> maxCmp,
- final boolean maxIncl,
- final boolean descending) {
- super(m, minCmp, minIncl, maxCmp, maxIncl, descending);
- }
-
- @Override
- public Entry<K,V> next() {
- return nextNode();
- }
- }
-
- private static class KeyIter<K,V> extends AbstractIter<K,V> implements Iterator<K> {
- private KeyIter(final SnapTreeMap<K,V> m) {
- super(m);
- }
-
- private KeyIter(final SnapTreeMap<K,V> m,
- final Comparable<? super K> minCmp,
- final boolean minIncl,
- final Comparable<? super K> maxCmp,
- final boolean maxIncl,
- final boolean descending) {
- super(m, minCmp, minIncl, maxCmp, maxIncl, descending);
- }
-
- @Override
- public K next() {
- return nextNode().key;
- }
- }
-
- private static class AbstractIter<K,V> {
- private final SnapTreeMap<K,V> m;
- private final boolean descending;
- private final char forward;
- private final char reverse;
- private Node<K,V>[] path;
- private int depth = 0;
- private Node<K,V> mostRecentNode;
- private final K endKey;
-
- @SuppressWarnings("unchecked")
- AbstractIter(final SnapTreeMap<K,V> m) {
- this.m = m;
- this.descending = false;
- this.forward = Right;
- this.reverse = Left;
- final Node<K,V> root = m.holderRef.frozen().right;
- this.path = (Node<K,V>[]) new Node[1 + height(root)];
- this.endKey = null;
- pushFirst(root);
- }
-
- @SuppressWarnings("unchecked")
- AbstractIter(final SnapTreeMap<K,V> m,
- final Comparable<? super K> minCmp,
- final boolean minIncl,
- final Comparable<? super K> maxCmp,
- final boolean maxIncl,
- final boolean descending) {
- this.m = m;
- this.descending = descending;
- this.forward = !descending ? Right : Left;
- this.reverse = !descending ? Left : Right;
- final Comparable<? super K> fromCmp;
- final boolean fromIncl = !descending ? minIncl : maxIncl;
- final Comparable<? super K> toCmp;
- final boolean toIncl = !descending ? maxIncl : minIncl;
- if (!descending) {
- fromCmp = minCmp;
- toCmp = maxCmp;
- } else {
- fromCmp = maxCmp;
- toCmp = minCmp;
- }
-
- final Node<K,V> root = m.holderRef.frozen().right;
-
- if (toCmp != null) {
- this.endKey = (K) m.boundedExtreme(minCmp, minIncl, maxCmp, maxIncl, true, forward);
- if (this.endKey == null) {
- // no node satisfies the bound, nothing to iterate
- // ---------> EARLY EXIT
- return;
- }
- } else {
- this.endKey = null;
- }
-
- this.path = (Node<K,V>[]) new Node[1 + height(root)];
-
- if (fromCmp == null) {
- pushFirst(root);
- }
- else {
- pushFirst(root, fromCmp, fromIncl);
- if (depth > 0 && top().vOpt == null) {
- advance();
- }
- }
- }
-
- private int cmp(final Comparable<? super K> comparable, final K key) {
- final int c = comparable.compareTo(key);
- if (!descending) {
- return c;
- } else {
- return c == Integer.MIN_VALUE ? 1 : -c;
- }
- }
-
- private void pushFirst(Node<K,V> node) {
- while (node != null) {
- path(node);
- node = node.child(reverse);
- }
- }
-
- private void path(Node<K,V> node) {
- if (depth == path.length)
- path = Arrays.copyOf(path, depth + 2);
-
- path[depth++] = node;
- }
-
- private void pushFirst(Node<K,V> node, final Comparable<? super K> fromCmp, final boolean fromIncl) {
- while (node != null) {
- final int c = cmp(fromCmp, node.key);
- if (c > 0 || (c == 0 && !fromIncl)) {
- // everything we're interested in is on the right
- node = node.child(forward);
- }
- else {
- path(node);
- if (c == 0) {
- // start the iteration here
- return;
- }
- else {
- node = node.child(reverse);
- }
- }
- }
- }
-
- private Node<K,V> top() {
- return path[depth - 1];
- }
-
- private void advance() {
- do {
- final Node<K,V> t = top();
- if (endKey != null && endKey == t.key) {
- depth = 0;
- path = null;
- return;
- }
-
- final Node<K,V> fwd = t.child(forward);
- if (fwd != null) {
- pushFirst(fwd);
- } else {
- // keep going up until we pop a node that is a left child
- Node<K,V> popped;
- do {
- popped = path[--depth];
- } while (depth > 0 && popped == top().child(forward));
- }
-
- if (depth == 0) {
- // clear out the path so we don't pin too much stuff
- path = null;
- return;
- }
-
- // skip removed-but-not-unlinked entries
- } while (top().vOpt == null);
- }
-
- public boolean hasNext() {
- return depth > 0;
- }
-
- Node<K,V> nextNode() {
- if (depth == 0) {
- throw new NoSuchElementException();
- }
- mostRecentNode = top();
- advance();
- return mostRecentNode;
- }
-
- public void remove() {
- if (mostRecentNode == null) {
- throw new IllegalStateException();
- }
- m.remove(mostRecentNode.key);
- mostRecentNode = null;
- }
- }
-
- //////////////// navigable keySet
-
- @Override
- public NavigableSet<K> navigableKeySet() {
- return new KeySet<K>(this) {
- public Iterator<K> iterator() {
- return new KeyIter<K,V>(SnapTreeMap.this);
- }
- };
- }
-
- @Override
- public NavigableSet<K> descendingKeySet() {
- return descendingMap().navigableKeySet();
- }
-
- private abstract static class KeySet<K> extends AbstractSet<K> implements NavigableSet<K> {
-
- private final ConcurrentNavigableMap<K,?> map;
-
- protected KeySet(final ConcurrentNavigableMap<K,?> map) {
- this.map = map;
- }
-
- //////// basic Set stuff
-
- @Override
- abstract public Iterator<K> iterator();
-
- @Override
- public boolean contains(final Object o) { return map.containsKey(o); }
- @Override
- public boolean isEmpty() { return map.isEmpty(); }
- @Override
- public int size() { return map.size(); }
- @Override
- public boolean remove(final Object o) { return map.remove(o) != null; }
-
- //////// SortedSet stuff
-
- @Override
- public Comparator<? super K> comparator() { return map.comparator(); }
- @Override
- public K first() { return map.firstKey(); }
- @Override
- public K last() { return map.lastKey(); }
-
- //////// NavigableSet stuff
-
- @Override
- public K lower(final K k) { return map.lowerKey(k); }
- @Override
- public K floor(final K k) { return map.floorKey(k); }
- @Override
- public K ceiling(final K k) { return map.ceilingKey(k); }
- @Override
- public K higher(final K k) { return map.higherKey(k); }
-
- @Override
- public K pollFirst() { return map.pollFirstEntry().getKey(); }
- @Override
- public K pollLast() { return map.pollLastEntry().getKey(); }
-
- @Override
- public NavigableSet<K> descendingSet() { return map.descendingKeySet(); }
- @Override
- public Iterator<K> descendingIterator() { return map.descendingKeySet().iterator(); }
-
- @Override
- public NavigableSet<K> subSet(final K fromElement, final boolean minInclusive, final K toElement, final boolean maxInclusive) {
- return map.subMap(fromElement, minInclusive, toElement, maxInclusive).keySet();
- }
- @Override
- public NavigableSet<K> headSet(final K toElement, final boolean inclusive) {
- return map.headMap(toElement, inclusive).keySet();
- }
- @Override
- public NavigableSet<K> tailSet(final K fromElement, final boolean inclusive) {
- return map.tailMap(fromElement, inclusive).keySet();
- }
- @Override
- public SortedSet<K> subSet(final K fromElement, final K toElement) {
- return map.subMap(fromElement, toElement).keySet();
- }
- @Override
- public SortedSet<K> headSet(final K toElement) {
- return map.headMap(toElement).keySet();
- }
- @Override
- public SortedSet<K> tailSet(final K fromElement) {
- return map.tailMap(fromElement).keySet();
- }
- }
-
- //////////////// NavigableMap views
-
- @Override
- public ConcurrentNavigableMap<K,V> subMap(final K fromKey,
- final boolean fromInclusive,
- final K toKey,
- final boolean toInclusive) {
- final Comparable<? super K> fromCmp = comparable(fromKey);
- if (fromCmp.compareTo(toKey) > 0) {
- throw new IllegalArgumentException();
- }
- return new SubMap<K,V>(this, fromKey, fromCmp, fromInclusive, toKey, comparable(toKey), toInclusive, false);
- }
-
- @Override
- public ConcurrentNavigableMap<K,V> headMap(final K toKey, final boolean inclusive) {
- return new SubMap<K,V>(this, null, null, false, toKey, comparable(toKey), inclusive, false);
- }
-
- @Override
- public ConcurrentNavigableMap<K,V> tailMap(final K fromKey, final boolean inclusive) {
- return new SubMap<K,V>(this, fromKey, comparable(fromKey), inclusive, null, null, false, false);
- }
-
- @Override
- public ConcurrentNavigableMap<K,V> subMap(final K fromKey, final K toKey) {
- return subMap(fromKey, true, toKey, false);
- }
-
- @Override
- public ConcurrentNavigableMap<K,V> headMap(final K toKey) {
- return headMap(toKey, false);
- }
-
- @Override
- public ConcurrentNavigableMap<K,V> tailMap(final K fromKey) {
- return tailMap(fromKey, true);
- }
-
- @Override
- public ConcurrentNavigableMap<K,V> descendingMap() {
- return new SubMap(this, null, null, false, null, null, false, true);
- }
-
- private static class SubMap<K, V> extends AbstractMap<K, V> implements ConcurrentNavigableMap<K, V>, Serializable {
- /** */
- private static final long serialVersionUID = 0L;
-
- private final SnapTreeMap<K,V> m;
- private final K minKey;
- private transient Comparable<? super K> minCmp;
- private final boolean minIncl;
- private final K maxKey;
- private transient Comparable<? super K> maxCmp;
- private final boolean maxIncl;
- private final boolean descending;
-
- private SubMap(final SnapTreeMap<K,V> m,
- final K minKey,
- final Comparable<? super K> minCmp,
- final boolean minIncl,
- final K maxKey,
- final Comparable<? super K> maxCmp,
- final boolean maxIncl,
- final boolean descending) {
- this.m = m;
- this.minKey = minKey;
- this.minCmp = minCmp;
- this.minIncl = minIncl;
- this.maxKey = maxKey;
- this.maxCmp = maxCmp;
- this.maxIncl = maxIncl;
- this.descending = descending;
- }
-
- // TODO: clone
-
- private boolean tooLow(final K key) {
- if (minCmp == null) {
- return false;
- } else {
- final int c = minCmp.compareTo(key);
- return c > 0 || (c == 0 && !minIncl);
- }
- }
-
- private boolean tooHigh(final K key) {
- if (maxCmp == null) {
- return false;
- } else {
- final int c = maxCmp.compareTo(key);
- return c < 0 || (c == 0 && !maxIncl);
- }
- }
-
- private boolean inRange(final K key) {
- return !tooLow(key) && !tooHigh(key);
- }
-
- private void requireInRange(final K key) {
- if (key == null) {
- throw new NullPointerException();
- }
- if (!inRange(key)) {
- throw new IllegalArgumentException();
- }
- }
-
- private char minDir() {
- return descending ? Right : Left;
- }
-
- private char maxDir() {
- return descending ? Left : Right;
- }
-
- //////// AbstractMap
-
- @Override
- public boolean isEmpty() {
- return m.boundedExtreme(minCmp, minIncl, maxCmp, maxIncl, true, Left) == null;
- }
-
- @Override
- public int size() {
- final Node<K,V> root = m.holderRef.frozen().right;
- return Node.computeFrozenSize(root, minCmp, minIncl, maxCmp, maxIncl);
- }
-
- @Override
- @SuppressWarnings("unchecked")
- public boolean containsKey(final Object key) {
- if (key == null) {
- throw new NullPointerException();
- }
- final K k = (K) key;
- return inRange(k) && m.containsKey(k);
- }
-
- @Override
- public boolean containsValue(final Object value) {
- /
<TRUNCATED>