http://git-wip-us.apache.org/repos/asf/ignite/blob/4a095674/modules/core/src/main/java/org/apache/ignite/internal/util/offheap/unsafe/GridOffHeapSnapTreeMap.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/util/offheap/unsafe/GridOffHeapSnapTreeMap.java b/modules/core/src/main/java/org/apache/ignite/internal/util/offheap/unsafe/GridOffHeapSnapTreeMap.java deleted file mode 100644 index 518e303..0000000 --- a/modules/core/src/main/java/org/apache/ignite/internal/util/offheap/unsafe/GridOffHeapSnapTreeMap.java +++ /dev/null @@ -1,4525 +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.offheap.unsafe; - -import java.util.AbstractMap; -import java.util.AbstractSet; -import java.util.ArrayList; -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.SortedSet; -import java.util.concurrent.ConcurrentNavigableMap; -import java.util.concurrent.ConcurrentSkipListMap; -import java.util.concurrent.CountDownLatch; -import java.util.concurrent.atomic.AtomicInteger; -import java.util.concurrent.atomic.AtomicLong; -import java.util.concurrent.locks.Lock; -import java.util.concurrent.locks.ReentrantReadWriteLock; - -import org.apache.ignite.*; -import org.apache.ignite.internal.processors.cache.distributed.dht.GridReservable; -import org.apache.ignite.internal.util.*; -import org.apache.ignite.internal.util.lang.*; -import org.apache.ignite.internal.util.typedef.internal.SB; -import org.jetbrains.annotations.Nullable; -import org.jsr166.ConcurrentHashMap8; - -/** - * 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 GridOffHeapSnapTreeMap<K extends GridOffHeapSmartPointer, V extends GridOffHeapSmartPointer> - extends AbstractMap<K, V> - implements ConcurrentNavigableMap<K, V>, Cloneable, AutoCloseable, GridReservable { - /** This is a special value that indicates that an optimistic read failed. */ - private static final GridOffHeapSmartPointer SpecialRetry = new GridOffHeapSmartPointer() { - @Override public long pointer() { - throw new IllegalStateException(); - } - - @Override public void incrementRefCount() { - throw new IllegalStateException(); - } - - @Override public void decrementRefCount() { - throw new IllegalStateException(); - } - }; - - /** The number of spins before yielding. */ - private static final int SpinCount = Integer.parseInt(System.getProperty("snaptree.spin", "100")); - - /** The number of yields before blocking. */ - private static final int YieldCount = Integer.parseInt(System.getProperty("snaptree.yield", "0")); - - /** We encode directions as characters. */ - private static final char Left = 'L'; - - /** We encode directions as characters. */ - private 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>. - */ - private static long beginChange(long ovl) { - return ovl | 1; - } - - /** - * @param ovl OVL. - * @return OVL. - */ - private static long endChange(long ovl) { - return (ovl | 3) + 1; - } - - /** */ - private static final long UnlinkedOVL = 2; - - /** - * @param ovl OVL. - * @return OVL. - */ - private static boolean isShrinking(long ovl) { - return (ovl & 1) != 0; - } - - /** - * @param ovl OVL. - * @return OVL. - */ - private static boolean isUnlinked(long ovl) { - return (ovl & 2) != 0; - } - - /** - * @param ovl OVL. - * @return OVL. - */ - private static boolean isShrinkingOrUnlinked(long ovl) { - return (ovl & 3) != 0L; - } - - /** Scale of long. */ - static final int scale = 8; - - /** */ - static final int KEY = 0 * scale; - - /** */ - static final int V_OPT = 1 * scale; - - /** */ - static final int LEFT = 2 * scale; - - /** */ - static final int RIGHT = 3 * scale; - - /** */ - static final int SHRINK_OVL = 4 * scale; - - /** */ - static final int PARENT = 5 * scale; - - /** */ - static final int HEIGHT = 6 * scale; - - /** */ - static final int LONGS_IN_NODE = 7; - - /** */ - static final int NODE_SIZE = LONGS_IN_NODE * scale; - - /** - * Resizable array of long values. - */ - private static class LongArray { - /** */ - private long[] arr; - - /** */ - private int idx = 0; - - /** - * Add element to this array. - * @param x Value. - */ - public void add(long x) { - if (arr == null) - arr = new long[4]; - else if (arr.length == idx) - arr = Arrays.copyOf(arr, arr.length * 2); - - arr[idx++] = x; - } - } - - /** - * @param key Key. - * @param height Height. - * @param vOpt Value. - * @param parent Parent. - * @param left Left. - * @param right Right. - * @return New node. - */ - private long newNode(final K key, final int height, final V vOpt, final long parent, long left, long right) { - long ptr = mem.allocate(NODE_SIZE); - - vOpt0(ptr); - - assert (vOpt != null && key != null) || (key == vOpt); - - key(ptr, key); - height(ptr, height); - vOpt(ptr, vOpt); - parent(ptr, parent); - shrinkOVL(ptr, 0); - left(ptr, left); - right(ptr, right); - - return ptr; - } - - /** - * @param node Node. - * @return Key pointer. - */ - protected long keyPtr(long node) { - return mem.readLongVolatile(node + KEY); - } - - /** - * @param ptr Node pointer. - * @return Key. - */ - private K key(long ptr) { - long resPtr = mem.readLongVolatile(ptr + KEY); - - if (resPtr == 0) { - return null; - } - - return keyFactory.createPointer(resPtr); - } - - /** - * @param ptr Node pointer. - * @return Value. - */ - private V vOpt(long ptr) { - long resPtr = mem.readLongVolatile(ptr + V_OPT); - - if (resPtr == 0) - return null; - - return valFactory.createPointer(resPtr); - } - - /** - * @param ptr Node pointer. - * @return {@code true} If value is null; - */ - private boolean vOptIsNull(long ptr) { - return mem.readLongVolatile(ptr + V_OPT) == 0; - } - - /** - * @param ptr Node pointer. - * @return Right child. - */ - long right(long ptr) { - return mem.readLongVolatile(ptr + RIGHT); - } - - /** - * @param ptr Node pointer. - * @return Left child. - */ - long left(long ptr) { - return mem.readLongVolatile(ptr + LEFT); - } - - /** - * @param ptr Node pointer. - * @param nodePtr Right child's pointer. - */ - protected void right(long ptr, long nodePtr) { - assert nodePtr >= 0; - - mem.writeLongVolatile(ptr + RIGHT, nodePtr); - } - - /** - * @param ptr Node pointer. - * @param nodePtr Left child's pointer. - */ - private void left(long ptr, long nodePtr) { - assert nodePtr >= 0; - - mem.writeLongVolatile(ptr + LEFT, nodePtr); - } - - /** - * @param ptr Node pointer. - * @return Parents pointer. - */ - private long parent(long ptr) { - return mem.readLongVolatile(ptr + PARENT); - } - - /** - * @param ptr Node pointer. - * @param nodePtr Parents pointer. - */ - private void parent(long ptr, long nodePtr) { - assert nodePtr >= 0; - - mem.writeLongVolatile(ptr + PARENT, nodePtr); - } - - /** - * Reads link from given node pointer to next when they are getting dealloctated. - * - * @param addr Node pointer. - * @return Next node pointer. - */ - private long readLink(long addr) { - long ptr = -mem.readLongVolatile(addr + PARENT); - - assert ptr >= 0; - - return ptr; - } - - /** - * Writes link to given pointer to this pointer. - * - * @param addr Node pointer. - * @param val Next node pointer. - */ - private void writeLink(long addr, long val) { - assert val > 0; - - mem.writeLongVolatile(addr + PARENT, -val); - -//// !!! The same code but with assertions. Don't remove!!! -// -// val = -val; -// addr += PARENT; -// -// long old; -// -// do { -// old = mem.readLongVolatile(addr); -// -// D.hangIfStopped(); -// -// if (old == val) { -// assert old == -Long.MAX_VALUE : old; -// -// return; -// } -// -// if (prev == 0) { -// assert old >= 0 || // First time added. -// old == -Long.MAX_VALUE : // Added as tail to another queue. -// (addr - PARENT) + " " + old + D.dumpWithStop(); -// } -// else -// assert -prev == old : old + " " + prev + D.dumpWithStop(); -// } -// while (!mem.casLong(addr, old, val)); - } - - /** - * Lazy copy node and mark children shared. - * - * @param ptr Node pointer. - * @param newParent New parent pointer. - * @param unlinked Array for unlinked values. - * @return Copy of node. - */ - private long lazyCopy(long ptr, long newParent, LongArray unlinked) { - assert ptr > 0; - assert (isShared(ptr)); - assert (!isShrinkingOrUnlinked(shrinkOVL(ptr))); - - if (snapshots.isEmpty()) { // Unshare node if there are no snapshots. - parent(ptr, newParent); - - return ptr; - } - - long n = mem.allocate(NODE_SIZE); - - mem.copyMemory(ptr, n, NODE_SIZE); - - markShared(left(n)); - markShared(right(n)); - - key(n).incrementRefCount(); - - GridOffHeapSmartPointer val = vOpt(n); - - if (val != null) - val.incrementRefCount(); - - parent(n, newParent); - - // Start recycling - unlinked.add(-ptr); // Minus to show that node should be added to older snapshot. - - return n; - } - - /** - * @param ptr Node pointer. - * @return OVL for given node. - */ - private long shrinkOVL(long ptr) { - return mem.readLongVolatile(ptr + SHRINK_OVL); - } - - /** - * @param ptr Node pointer. - * @return Node height. - */ - private int height(long ptr) { - return ptr == 0 ? 0 : (int)mem.readLongVolatile(ptr + HEIGHT); - } - - /** - * @param ptr Node pointer. - * @param shrinkOVL OVL. - */ - private void shrinkOVL(long ptr, long shrinkOVL) { - mem.writeLongVolatile(ptr + SHRINK_OVL, shrinkOVL); - } - - /** - * Reset value. - * - * @param ptr Node pointer. - */ - private void vOpt0(long ptr) { - mem.writeLongVolatile(ptr + V_OPT, 0); - } - - /** - * @param ptr Node pointer. - * @param newValue New value. - */ - private void vOpt(long ptr, GridOffHeapSmartPointer newValue) { - GridOffHeapSmartPointer old = vOpt(ptr); - - long newValPtr = 0; - - if (newValue != null) { - newValue.incrementRefCount(); - - newValPtr = newValue.pointer(); - } - - assert newValPtr >= 0; - - mem.writeLongVolatile(ptr + V_OPT, newValPtr); - - if (old != null) - old.decrementRefCount(); - } - - /** - * @param ptr Node pointer. - * @param key Key. - */ - protected void key(long ptr, K key) { - long keyPtr = 0; - - if (key != null) { - key.incrementRefCount(); - - keyPtr = key.pointer(); - } - - mem.writeLongVolatile(ptr + KEY, keyPtr); - } - - /** - * @param ptr Node pointer. - * @param h Height. - */ - private void height(long ptr, int h) { - mem.writeLongVolatile(ptr + HEIGHT, h); - } - - /** - * @param ptr Node pointer. - * @param dir Child direction. - * @return Child. - */ - private long child(long ptr, char dir) { - return dir == Left ? left(ptr) : right(ptr); - } - - /** - * @param ptr Node pointer. - * @param dir Child direction. - * @param node Child pointer. - */ - private void setChild(long ptr, char dir, long node) { - if (dir == Left) { - left(ptr, node); - } - else { - right(ptr, node); - } - } - - /** - * @param node Node pointer. - * @return If node is shared. - */ - private boolean isShared(final long node) { - assert node >= 0; - - // Need to check isUnlinked because node on unlink will have negative parent, - // but it does not mean that it is shared. - return node != 0 && parent(node) <= 0 && !isUnlinked(shrinkOVL(node)); - } - - /** - * @param node Node pointer. - * @return Given node. - */ - private long markShared(final long node) { - assert node >= 0; - - if (node != 0 && parent(node) > 0) - parent(node, 0); - - return node; - } - - /** - * @param ptr Node pointer. - * @param unlinked Array for unlinked nodes. - * @return Unshared left child. - */ - private long unsharedLeft(long ptr, LongArray unlinked) { - final long cl = left(ptr); - - if (!isShared(cl)) { - return cl; - } - else { - lazyCopyChildren(ptr, unlinked); - - return left(ptr); - } - } - - /** - * @param ptr Node pointer. - * @param unlinked Array for unlinked nodes. - * @return Unshared right child. - */ - private long unsharedRight(long ptr, LongArray unlinked) { - final long cr = right(ptr); - - if (!isShared(cr)) { - return cr; - } - else { - lazyCopyChildren(ptr, unlinked); - - return right(ptr); - } - } - - /** - * @param ptr Node pointer. - * @param dir Direction. - * @param unlinked Array for unlinked nodes. - * @return Unshared right child. - */ - private long unsharedChild(long ptr, final char dir, LongArray unlinked) { - return dir == Left ? unsharedLeft(ptr, unlinked) : unsharedRight(ptr, unlinked); - } - - /** - * @param ptr Node pointer. - * @param unlinked Array for unlinked nodes. - */ - private void lazyCopyChildren(long ptr, LongArray unlinked) { - KeyLock.Lock l = lock.lock(ptr); - - try { - final long cl = left(ptr); - - if (isShared(cl)) { - left(ptr, lazyCopy(cl, ptr, unlinked)); - } - - final long cr = right(ptr); - - if (isShared(cr)) { - right(ptr, lazyCopy(cr, ptr, unlinked)); - } - } - finally { - if (l != null) - l.unlock(); - } - } - - /** - * @param ptr Node pointer. - * @param ovl Known OVL. - */ - private void waitUntilShrinkCompleted(long ptr, final long ovl) { - if (isUnlinked(ovl) || !isShrinking(ovl)) { - return; - } - - for (int tries = 0; tries < SpinCount; ++tries) { - if (shrinkOVL(ptr) != ovl) { - return; - } - } - - for (int tries = 0; tries < YieldCount; ++tries) { - Thread.yield(); - - if (shrinkOVL(ptr) != ovl) { - return; - } - } - - // spin and yield failed, use the nuclear option - // we can't have gotten the lock unless the shrink was over - KeyLock.Lock l = lock.lock(ptr); - - if (l != null) - l.unlock(); - - assert(shrinkOVL(ptr) != ovl) : ptr + " " + ovl; - } - - /** - * @param ptr Node pointer. - * @return Validated height. - */ - private int validatedHeight(long ptr) { - final int hL = left(ptr) == 0 ? 0 : validatedHeight(left(ptr)); - final int hR = right(ptr) == 0 ? 0 : validatedHeight(right(ptr)); - - assert(Math.abs(hL - hR) <= 1); - final int h = 1 + Math.max(hL, hR); - - int resH = height(ptr); - - assert(h == resH); - - return resH; - } - - /** - * @param root Root node pointer. - * @param fromCmp Lower bound. - * @param fromIncl Include lower bound. - * @param toCmp Upper bound. - * @param toIncl Include upper bound. - * @return Size. - */ - private int computeFrozenSize(long root, Comparable<? super K> fromCmp, boolean fromIncl, - final Comparable<? super K> toCmp, final boolean toIncl) { - int result = 0; - - while (true) { - if (root == 0) { - return result; - } - - if (fromCmp != null) { - final int c = fromCmp.compareTo(key(root)); - - if (c > 0 || (c == 0 && !fromIncl)) { - // all matching nodes are on the right side - root = right(root); - - continue; - } - } - - if (toCmp != null) { - final int c = toCmp.compareTo(key(root)); - - if (c < 0 || (c == 0 && !toIncl)) { - // all matching nodes are on the left side - root = left(root); - - continue; - } - } - - // Current node matches. Nodes on left no longer need toCmp, nodes - // on right no longer need fromCmp. - if (!vOptIsNull(root)) { - ++result; - } - - result += computeFrozenSize(left(root), fromCmp, fromIncl, null, false); - - fromCmp = null; - - root = right(root); - } - } - - /** - * Entry of tree. - */ - private class Entree implements Map.Entry<K,V> { - /** */ - private final long ptr; - - /** - * @param ptr Pointer. - */ - private Entree(long ptr) { - this.ptr = ptr; - } - - /** {@inheritDoc} */ - @Override public K getKey() { - return key(ptr); - } - - /** {@inheritDoc} */ - @SuppressWarnings("unchecked") - @Override public V getValue() { - return vOpt(ptr); - } - - /** {@inheritDoc} */ - @Override public GridOffHeapSmartPointer setValue(final GridOffHeapSmartPointer v) { - throw new UnsupportedOperationException(); - } - - /** {@inheritDoc} */ - @Override public boolean equals(final Object o) { - if (!(o instanceof Map.Entry)) { - return false; - } - - final Map.Entry rhs = (Map.Entry)o; - - return key(ptr).equals(rhs.getKey()) && getValue().equals(rhs.getValue()); - } - - /** {@inheritDoc} */ - @Override public int hashCode() { - return (getKey() == null ? 0 : getKey().hashCode()) ^ (getValue() == null ? 0 : getValue().hashCode()); - } - - /** {@inheritDoc} */ - @Override public String toString() { - return key(ptr) + "=" + getValue(); - } - } - - /** - * Recycle queue for memory deallocation. - */ - private class RecycleQueue implements GridUnsafeCompoundMemory { - /** */ - private volatile long tail; - - /** */ - protected final AtomicLong head = new AtomicLong(Long.MAX_VALUE); - - /** */ - protected final AtomicLong size = new AtomicLong(); - - /** - * @return Size. - */ - long size() { - return size.get(); - } - - /** - * @param node Node pointer. - * @return {@code true} If operation succeeded. - */ - boolean add(long node) { - assert node > 0; - - return add(node, node, 1); - } - - /** {@inheritDoc} */ - @Override public void merge(GridUnsafeCompoundMemory compound) { - boolean res = add((RecycleQueue)compound); - - assert res; - } - - /** - * @param q Recycle queue. - * @return {@code true} If operation succeeded. - */ - public boolean add(RecycleQueue q) { - assert !q.isEmpty(); - - long node = q.head.get(); - long tail = q.tail; - long size = q.size(); - - assert node > 0; - assert tail > 0; - assert size > 0; - - return add(node, tail, size); - } - - /** - * @param node Head node pointer. - * @param tail Tail node pointer. - * @param size Size of the chain. - * @return {@code true} If succeeded. - */ - protected boolean add(long node, long tail, long size) { - for (;;) { - final long h = head.get(); - - assert h > 0 : h; - - writeLink(tail, h);// If h == Long.MAX_VALUE we still need to write it to tail. - - if (head.compareAndSet(h, node)) { - if (h == Long.MAX_VALUE) - this.tail = tail; - - this.size.addAndGet(size); - - return true; - } - } - } - - /** - * @return {@code true} If empty. - */ - boolean isEmpty() { - return head.get() == Long.MAX_VALUE; - } - - /** {@inheritDoc} */ - @Override public void deallocate() { - long h = head.get(); - - while (h != Long.MAX_VALUE) { - assert h > 0 : h; - - GridOffHeapSmartPointer k = key(h); - - if (k != null) { - k.decrementRefCount(); - - GridOffHeapSmartPointer v = vOpt(h); - - if (v != null) - v.decrementRefCount(); - } - - long prev = h; - - h = readLink(h); - - mem.release(prev, NODE_SIZE); - } - } - } - - /** - * Stoppable recycle queue. - */ - private class StoppableRecycleQueue extends RecycleQueue { - /** */ - protected final ReentrantReadWriteLock lock = new ReentrantReadWriteLock(); - - /** */ - private boolean stopped; - - /** {@inheritDoc} */ - @Override public boolean add(long node) { - Lock l = lock.readLock(); - - if (!l.tryLock()) - return false; - - try { - return !stopped && super.add(node); - } - finally { - l.unlock(); - } - } - - /** {@inheritDoc} */ - @Override public boolean add(RecycleQueue que) { - Lock l = lock.readLock(); - - if (!l.tryLock()) - return false; - - try { - return !stopped && super.add(que); - } - finally { - l.unlock(); - } - } - - /** {@inheritDoc} */ - @Override public void merge(GridUnsafeCompoundMemory compound) { - boolean res = super.add((RecycleQueue)compound); - - assert res; - } - - /** - * @return {@code true} If we stopped this queue. - */ - public boolean stop() { - Lock l = lock.writeLock(); - - l.lock(); - - try { - if (stopped) - return false; - - stopped = true; - - return true; - } - finally { - l.unlock(); - } - } - } - - /** - * @return New root holder. - */ - private long rootHolder() { - return newNode(null, 1, null, 0L, 0L, 0L); - } - - /** - * @param rootHolderSnapshot Snapshot of current root holder. - * @return Copy of given root holder. - */ - private long rootHolder(final long rootHolderSnapshot) { - return newNode(null, 1 + height(rootHolderSnapshot), null, 0L, 0L, right(rootHolderSnapshot)); - } - - /** */ - private final Comparator<? super K> comparator; - - /** */ - private transient volatile long holderRef; - - /** */ - private final GridOffHeapSmartPointerFactory<K> keyFactory; - - /** */ - private final GridOffHeapSmartPointerFactory<V> valFactory; - - /** */ - protected final GridUnsafeMemory mem; - - /** */ - protected final GridUnsafeGuard guard; - - /** */ - private final KeyLock lock = new KeyLock(); - - /** */ - private final AtomicLong snapshotsCnt = new AtomicLong(); - - /** */ - private final ConcurrentSkipListMap<Long, GridOffHeapSnapTreeMap> snapshots = - new ConcurrentSkipListMap<Long, GridOffHeapSnapTreeMap>(); - - /** */ - private Long snapshotId = 0L; - - /** Recycle queue for this snapshot. */ - private volatile StoppableRecycleQueue recycleBin; - - /** */ - private AtomicInteger reservations; - - /** */ - private volatile boolean closing; - - /** - * @param keyFactory Key factory. - * @param valFactory Value factory. - * @param mem Unsafe memory. - * @param guard Guard. - */ - public GridOffHeapSnapTreeMap(GridOffHeapSmartPointerFactory keyFactory, GridOffHeapSmartPointerFactory valFactory, - GridUnsafeMemory mem, GridUnsafeGuard guard) { - this(keyFactory, valFactory, mem, guard, null); - } - - /** - * @param keyFactory Key factory. - * @param valFactory Value factory. - * @param mem Unsafe memory. - * @param guard Guard. - * @param comparator Comparator. - */ - public GridOffHeapSnapTreeMap(GridOffHeapSmartPointerFactory keyFactory, GridOffHeapSmartPointerFactory valFactory, - GridUnsafeMemory mem, GridUnsafeGuard guard, Comparator<? super K> comparator) { - assert keyFactory != null; - assert valFactory != null; - assert mem != null; - assert guard != null; - - this.comparator = comparator; - this.keyFactory = keyFactory; - this.valFactory = valFactory; - this.mem = mem; - this.guard = guard; - this.holderRef = rootHolder(); - } - - /** {@inheritDoc} */ - @Override public boolean reserve() { - for (;;) { - int r = reservations.get(); - - if (r == -1) - return false; - - assert r >= 0 : r; - - if (reservations.compareAndSet(r, r + 1)) - return true; - } - } - - /** {@inheritDoc} */ - @Override public void release() { - for (;;) { - int r = reservations.get(); - - assert r > 0 : r; - - int z = r == 1 && closing ? -1 : r - 1; - - if (reservations.compareAndSet(r, z)) { - if (z == -1) - doClose(); - - return; - } - } - } - - /** - * Closes tree map and reclaims memory. - */ - @Override public void close() { - closing = true; - - if (reservations == null || reservations.compareAndSet(0, -1)) - doClose(); - } - - /** - * - */ - private void doClose() { - RecycleQueue q; - - if (snapshotId.longValue() == 0) { - assert recycleBin == null; - - q = new RecycleQueue(); - - deallocateSubTree(root(), q); - } - else { - GridOffHeapSnapTreeMap s = snapshots.remove(snapshotId); - - assert s == this; - - q = recycleBin; - - boolean res = recycleBin.stop(); - - assert res; - } - - mem.release(holderRef, NODE_SIZE); - - if (!q.isEmpty()) - doDeallocateSnapshot(q); - } - - /** - * Deallocates sub-tree under given node. - * - * @param node Node pointer. - * @param que Recycle queue. - */ - private void deallocateSubTree(long node, RecycleQueue que) { - if (node == 0) - return; - - deallocateSubTree(left(node), que); - deallocateSubTree(right(node), que); - - que.add(node); - } - - /** - * @return Clones this map and takes data snapshot. - */ - @SuppressWarnings("unchecked") - @Override public GridOffHeapSnapTreeMap<K,V> clone() { - final GridOffHeapSnapTreeMap copy; - try { - copy = (GridOffHeapSnapTreeMap) super.clone(); - } catch (final CloneNotSupportedException xx) { - throw new InternalError(); - } - assert(copy.comparator == comparator); - - copy.holderRef = rootHolder(holderRef); - markShared(root()); - - copy.reservations = new AtomicInteger(); - copy.size = new AtomicInteger(size()); - copy.recycleBin = new StoppableRecycleQueue(); - - copy.snapshotId = snapshotsCnt.decrementAndGet(); // To put in descending order. - - snapshots.put(copy.snapshotId, copy); - - return copy; - } - - /** - * @return Root node. - */ - long root() { - return right(holderRef); - } - - /** - * Counts all tree nodes. - * - * @param nonNull Only not routing nodes. - * @return Count. - */ - long nodes(boolean nonNull) { - return nodes(root(), nonNull); - } - - /** - * Counts all subtree nodes. - * - * @param node Root of subtree. - * @param nonNull Only not routing nodes. - * @return Count. - */ - private long nodes(long node, boolean nonNull) { - if (node == 0) - return 0; - - return (nonNull && vOptIsNull(node) ? 0 : 1) + nodes(left(node), nonNull) + nodes(right(node), nonNull); - } - - /** - * @return String representation of structure. - */ - String print() { - long root = root(); - - if (root == 0) - return "Empty tree"; - - ArrayList<SB> s = new ArrayList<SB>(height(root) + 1); - - print(root, s, 0, 0); - - SB res = new SB(); - - for (SB sb : s) - res.a(sb).a('\n'); - - return '\n' + res.toString(); - } - - /** - * @param node Node. - * @param s String builders. - * @param level Level. - * @param offset Offset. - * @return Length. - */ - private int print(long node, ArrayList<SB> s, int level, int offset) { - if (node == 0) - return s.get(level - 1).length(); - - SB sb = s.size() <= level ? null : s.get(level); - - if (sb == null) { - sb = new SB(); - - s.add(level, sb); - } - - int o = Math.max(print(left(node), s, level + 1, offset), offset); - - String v = print0(node); - - while(sb.length() < o) - sb.a(' '); - - sb.a(v); - - return print(right(node), s, level + 1, o + v.length()); - } - - /** - * Print node. - * - * @param node Node. - * @return Debug string representation. - */ - private String print0(long node) { - if (key(node) == null) - return "[" + node + "]"; - - return "[(" + node + ":" + shrinkOVL(node) + " " + parent(node) + ") " + key(node) + " = " + vOpt(node) + " ]"; - } - - /** - * Validates tree structure. - */ - void validate() { - long res = validate(root()); - - assert res == 0; - } - - /** - * Validates subtree structure. - * - * @param node Subtree root. - * @return Node at wrong position. - */ - private long validate(long node) { - if (node == 0) - return 0; - - long left = left(node); - - if (left != 0) { - if (comparable(key(left)).compareTo(key(node)) >= 0) - return node; - - long res = validate(left); - - if (res != 0) - return res; - } - - long right = right(node); - - if (right != 0) { - if (comparable(key(right)).compareTo(key(node)) <= 0) - return node; - - long res = validate(right); - - if (res != 0) - return res; - } - - return 0; - } - - /** */ - private AtomicInteger size = new AtomicInteger(); - - /** {@inheritDoc} */ - @Override public int size() { - return size.get(); - } - - /** {@inheritDoc} */ - @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 root() == 0; - } - - /** {@inheritDoc} */ - @Override public void clear() { - throw new UnsupportedOperationException(); - } - - /** {@inheritDoc} */ - @Override public Comparator<? super K> comparator() { - return comparator; - } - - /** {@inheritDoc} */ - @Override public boolean containsKey(final Object key) { - return getImpl((K)key) != null; - } - - /** {@inheritDoc} */ - @Override public V get(final Object key) { - return (V)getImpl((K)key); - } - - /** - * @param key Key. - * @return Comparable over given 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 GridOffHeapSmartPointer getImpl(final K key) { - LongArray unlinked = new LongArray(); - - try { - return doGet(key, unlinked); - } - finally { - deallocate(unlinked); - } - } - - /** - * @param key Key. - * @param unlinked Array for unlinked nodes. - * @return Found pointer. - */ - private GridOffHeapSmartPointer doGet(final K key, LongArray unlinked) { - final Comparable<? super K> k = comparable(key); - - while (true) { - final long right = unsharedRight(holderRef, unlinked); - - if (right == 0) { - return null; - } - else { - final int rightCmp = k.compareTo(key(right)); - - if (rightCmp == 0) { - // who cares how we got here - return vOpt(right); - } - - final long ovl = shrinkOVL(right); - - if (isShrinkingOrUnlinked(ovl)) { - waitUntilShrinkCompleted(right, ovl); - // RETRY - } - else if (right == right(holderRef)) { - // the reread of .right is the one protected by our read of ovl - GridOffHeapSmartPointer vo = attemptGet(k, right, (rightCmp < 0 ? Left : Right), ovl, unlinked); - - if (vo != SpecialRetry) { - return vo; - } - // else RETRY - } - } - } - } - - /** - * @param k Key. - * @param node Node pointer. - * @param dirToC Direction. - * @param nodeOVL OVL. - * @param unlinked Array for unlinked nodes. - * @return Found value. - */ - private GridOffHeapSmartPointer attemptGet(final Comparable<? super K> k, final long node, final char dirToC, - final long nodeOVL, LongArray unlinked) { - while (true) { - final long child = unsharedChild(node, dirToC, unlinked); - - if (child == 0) { - if (isOutdatedOVL(node, 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(key(child)); - - if (childCmp == 0) { - // how we got here is irrelevant - return vOpt(child); - } - - // child is non-null - final long childOVL = shrinkOVL(child); - - if (isShrinkingOrUnlinked(childOVL)) { - waitUntilShrinkCompleted(child, childOVL); - - if (isOutdatedOVL(node, nodeOVL)) { - return SpecialRetry; - } - // else RETRY - } - else if (child != child(node, dirToC)) { - // this .child is the one that is protected by childOVL - if (isOutdatedOVL(node, nodeOVL)) { - return SpecialRetry; - } - // else RETRY - } - else { - if (isOutdatedOVL(node, 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. - GridOffHeapSmartPointer vo = attemptGet(k, child, (childCmp < 0 ? Left : Right), childOVL, unlinked); - - if (vo != SpecialRetry) { - return vo; - } - // else RETRY - } - } - } - } - - /** {@inheritDoc} */ - @Override public K firstKey() { - return extremeKeyOrThrow(Left); - } - - /** {@inheritDoc} */ - @Override public Map.Entry<K,V> firstEntry() { - return (SimpleImmutableEntry<K,V>)extreme(false, Left); - } - - /** {@inheritDoc} */ - @Override public K lastKey() { - return extremeKeyOrThrow(Right); - } - - /** {@inheritDoc} */ - @Override public Map.Entry<K,V> lastEntry() { - return (SimpleImmutableEntry<K,V>) extreme(false, Right); - } - - /** - * @param dir Direction. - * @return Extreme key. - */ - 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 long right = right(holderRef); - - if (right == 0) { - return null; - } - else { - final long ovl = shrinkOVL(right); - if (isShrinkingOrUnlinked(ovl)) { - waitUntilShrinkCompleted(right, ovl); - // RETRY - } - else if (right == right(holderRef)) { - // 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 - } - } - } - } - - /** - * @param returnKey If we need to return key. - * @param dir Direction. - * @param node Node pointer. - * @param nodeOVL OVL. - * @return Some argument dependant result. - */ - private Object attemptExtreme(final boolean returnKey, - final char dir, - final long node, - final long nodeOVL) { - while (true) { - final long child = child(node, dir); - - if (child == 0) { - // 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 - V vo = vOpt(node); - - if (isOutdatedOVL(node, nodeOVL)) { - return SpecialRetry; - } - - assert(vo != null); - - return returnKey ? key(node) : new SimpleImmutableEntry<K,V>(key(node), vo); - } - else { - // child is non-null - final long childOVL = shrinkOVL(child); - - if (isShrinkingOrUnlinked(childOVL)) { - waitUntilShrinkCompleted(child, childOVL); - - if (isOutdatedOVL(node, nodeOVL)) { - return SpecialRetry; - } - // else RETRY - } - else if (child != child(node, dir)) { - // this .child is the one that is protected by childOVL - if (isOutdatedOVL(node, nodeOVL)) { - return SpecialRetry; - } - // else RETRY - } - else { - if (isOutdatedOVL(node, nodeOVL)) { - return SpecialRetry; - } - - final Object vo = attemptExtreme(returnKey, dir, child, childOVL); - - if (vo != SpecialRetry) { - return vo; - } - // else RETRY - } - } - } - } - - /** {@inheritDoc} */ - @Override public K lowerKey(final K key) { - return (K)boundedExtreme(null, false, comparable(key), false, true, Right); - } - - /** {@inheritDoc} */ - @Override public K floorKey(final K key) { - return (K)boundedExtreme(null, false, comparable(key), true, true, Right); - } - - /** {@inheritDoc} */ - @Override public K ceilingKey(final K key) { - return (K)boundedExtreme(comparable(key), true, null, false, true, Left); - } - - /** {@inheritDoc} */ - @Override public K higherKey(final K key) { - return (K)boundedExtreme(comparable(key), false, null, false, true, Left); - } - - /** {@inheritDoc} */ - @Override public Entry<K,V> lowerEntry(final K key) { - return (Entry<K,V>) boundedExtreme(null, false, comparable(key), false, false, Right); - } - - /** {@inheritDoc} */ - @Override public Entry<K,V> floorEntry(final K key) { - return (Entry<K,V>) boundedExtreme(null, false, comparable(key), true, false, Right); - } - - /** {@inheritDoc} */ - @Override public Entry<K,V> ceilingEntry(final K key) { - return (Entry<K,V>) boundedExtreme(comparable(key), true, null, false, false, Left); - } - - /** {@inheritDoc} */ - @Override 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. */ - 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 { - long holder = holderRef; - - final long node = (dir == Left) ? boundedMin(right(holder), minCmp, minIncl) : - boundedMax(right(holder), maxCmp, maxIncl); - - if (node == 0) { - return null; - } - - resultKey = key(node); - - if (returnKey) { - result = resultKey; - } - else { - // we must copy the node - result = new SimpleImmutableEntry<K,V>(key(node), vOpt(node)); - } - } - - 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; - } - - /** - * @param node Node. - * @param minCmp Lower bound. - * @param minIncl Include min bound. - * @return Bounded min. - */ - private long boundedMin(long node, final Comparable<? super K> minCmp, final boolean minIncl) { - while (node != 0) { - final int c = minCmp.compareTo(key(node)); - - if (c < 0) { - // there may be a matching node on the left branch - final long z = boundedMin(left(node), minCmp, minIncl); - - if (z != 0) { - return z; - } - } - - if (c < 0 || (c == 0 && minIncl)) { - // this node is a candidate, is it actually present? - if (!vOptIsNull(node)) { - return node; - } - } - - // the matching node is on the right branch if it is present - node = right(node); - } - - return 0L; - } - - /** - * @param node Node. - * @param maxCmp Upper bound. - * @param maxIncl Include upper bound. - * @return Bounded max. - */ - private long boundedMax(long node, final Comparable<? super K> maxCmp, final boolean maxIncl) { - while (node != 0) { - final int c = maxCmp.compareTo(key(node)); - - if (c > 0) { - // there may be a matching node on the right branch - final long z = boundedMax(right(node), maxCmp, maxIncl); - - if (z != 0) { - return z; - } - } - - if (c > 0 || (c == 0 && maxIncl)) { - // this node is a candidate, is it actually present? - if (!vOptIsNull(node)) { - return node; - } - } - - // the matching node is on the left branch if it is present - node = left(node); - } - - return 0; - } - - /** */ - private static final int UpdateAlways = 0; - - /** */ - private static final int UpdateIfAbsent = 1; - - /** */ - private static final int UpdateIfPresent = 2; - - /** */ - private static final int UpdateIfEq = 3; - - /** - * @param func Update type. - * @param prev Previous value. - * @param expected Expected value. - * @return If we should update value. - */ - 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; - } - - return prev.equals(expected); - } - } - } - - /** - * @param func Update type. - * @param prev Previous value. - * @return Result object. - */ - private static Object noUpdateResult(final int func, final Object prev) { - return func == UpdateIfEq ? Boolean.FALSE : prev; - } - - /** - * @param func Update type. - * @param prev Previous value. - * @return Result object. - */ - private static Object updateResult(final int func, final Object prev) { - return func == UpdateIfEq ? Boolean.TRUE : prev; - } - - /** - * @param func Update type. - * @param result Operation result. - * @param newValue New value. - * @return Size delta. - */ - 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); - } - } - - /** {@inheritDoc} */ - @Override public V put(final K key, final V value) { - return (V)update(key, UpdateAlways, null, value); - } - - /** {@inheritDoc} */ - @Override public V putIfAbsent(final K key, final V value) { - return (V)update(key, UpdateIfAbsent, null, value); - } - - /** {@inheritDoc} */ - @Override public V replace(final K key, final V value) { - return (V)update(key, UpdateIfPresent, null, value); - } - - /** {@inheritDoc} */ - @Override public boolean replace(final K key, final V oldValue, final V newValue) { - return (Boolean) update(key, UpdateIfEq, oldValue, newValue); - } - - /** {@inheritDoc} */ - @Override public V remove(final Object key) { - return (V)update((K)key, UpdateAlways, null, null); - } - - /** {@inheritDoc} */ - @Override public boolean remove(final Object key, final Object value) { - if (key == null) { - throw new NullPointerException(); - } - - if (value == null) { - return false; - } - - return (Boolean) update((K)key, UpdateIfEq, (V)value, null); - } - - /** - * @param key Key. - * @param func Update type. - * @param expected Expected value. - * @param newValue New value. - * @return Result object. - */ - private Object update(final K key, final int func, final V expected, final V newValue) { - final Comparable<? super K> k = comparable(key); - - LongArray unlinked = new LongArray(); - - int sd = 0; - - try { - final Object result = updateUnderRoot(key, k, func, expected, newValue, holderRef, unlinked); - - sd = sizeDelta(func, result, newValue); - - if (sd != 0) - size.addAndGet(sd); - - return result; - } - finally { - deallocate(unlinked); - } - } - - /** - * Deallocates given node pointers. - * - * @param unlinked Array of unlinked pointers. - */ - private void deallocate(LongArray unlinked) { - RecycleQueue toMem = null; - RecycleQueue toSnap = null; - - for (int i = 0; i < unlinked.idx; i++) { - long ptr = unlinked.arr[i]; - - if (ptr > 0) { // Unlinked. - if (toMem == null) - toMem = new RecycleQueue(); - - toMem.add(ptr); - } - else { // Deallocated by lazyCopy. - assert ptr != 0; - - if (toSnap == null) - toSnap = new RecycleQueue(); - - toSnap.add(-ptr); - } - } - - if (toSnap != null) { - for (GridOffHeapSnapTreeMap snap : snapshots.values()) { - if (snap.recycleBin.add(toSnap)) { - toSnap = null; - - break; - } - } - - if (toSnap != null) { - // Can't add to snapshot queues, will deallocate all together. - if (toMem == null) - toMem = toSnap; - else - toMem.add(toSnap); - } - } - - if (toMem != null) - guard.releaseLater(toMem); - } - - /** - * @param q Recycle queue. - */ - private void doDeallocateSnapshot(RecycleQueue q) { - for (GridOffHeapSnapTreeMap s : snapshots.tailMap(snapshotId, false).values()) { - // Try to add our garbage to older alive snapshot which can use the same nodes. - if (s.recycleBin.add(q)) - return; - } - - // No active updates. - q.deallocate(); - } - - /** - * Manages updates to the root holder. - * - * @param key Key. - * @param k Comparator. - * @param func Update type. - * @param expected Expected value. - * @param newValue New value. - * @param holder Root holder. - * @param unlinked Array for unlinked nodes. - * @return Result object. - */ - @SuppressWarnings("unchecked") - private Object updateUnderRoot(final K key, final Comparable<? super K> k, final int func, final V expected, - final V newValue, final long holder, LongArray unlinked) { - int i = 0; - - while (true) { - final long right = unsharedRight(holder, unlinked); - - if (right == 0) { - // key is not present - if (!shouldUpdate(func, null, expected)) { - return noUpdateResult(func, null); - } - - if (newValue == null || attemptInsertIntoEmpty(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 = shrinkOVL(right); - - if (isShrinkingOrUnlinked(ovl)) { - waitUntilShrinkCompleted(right, ovl); - // RETRY - } - else if (right == right(holder)) { - // this is the protected .right - final Object vo = attemptUpdate(key, k, func, expected, newValue, holder, right, ovl, unlinked); - - if (vo != SpecialRetry) { - return vo; - } - // else RETRY - } - } - } - } - - /** - * @param key Key. - * @param vOpt Value. - * @param holder Root holder. - * @return {@code true} If succeeded. - */ - private boolean attemptInsertIntoEmpty(final K key, final V vOpt, final long holder) { - KeyLock.Lock l = lock.lock(holder); - - try { - if (right(holder) == 0) { - right(holder, newNode(key, 1, vOpt, holder, 0L, 0L)); - - height(holder, 2); - - return true; - } - else { - return false; - } - } - finally { - if (l != null) - l.unlock(); - } - } - - /** - * Checks if we operate by valid node version. - * - * @param node Node pointer. - * @param nodeOVL Node version. - * @return {@code True} if node version changed or node was unlinked. - */ - private boolean isOutdatedOVL(long node, long nodeOVL) { - return shrinkOVL(node) != nodeOVL; - } - - /** 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 V expected, - final V newValue, final long parent, final long node, final long nodeOVL, LongArray unlinked) { - // 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 !isUnlinked(nodeOVL); - - final int cmp = k.compareTo(key(node)); - - if (cmp == 0) { - return attemptNodeUpdate(func, expected, newValue, parent, node, unlinked); - } - - final char dirToC = cmp < 0 ? Left : Right; - - int i = 0; - - while (true) { - if (isOutdatedOVL(node, nodeOVL)) { - return SpecialRetry; - } - - final long child = unsharedChild(node, dirToC, unlinked); - - if (child == 0) { - // 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. - KeyLock.Lock l = lock.lock(node); - - try { - if (isOutdatedOVL(node, nodeOVL)) { - return SpecialRetry; - } - - return null; - } - finally { - if (l != null) - l.unlock(); - } - } - else { - // Update will be an insert. - final boolean success; - final long damaged; - - KeyLock.Lock l = lock.lock(node); - - try { - // 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 (isOutdatedOVL(node, nodeOVL)) { - return SpecialRetry; - } - - if (child(node, dirToC) != 0) { - // 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 = 0; - } - 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 - setChild(node, dirToC, newNode((K)key, 1, newValue, - node, 0L, 0L)); - success = true; - - // attempt to fix node.height while we've still got - // the lock - damaged = fixHeight_nl(node); - } - } - finally { - if (l != null) - l.unlock(); - } - - if (success) { - fixHeightAndRebalance(damaged, unlinked); - - return updateResult(func, null); - } - // else RETRY - } - } - else { - // non-null child - final long childOVL = shrinkOVL(child); - - if (isShrinkingOrUnlinked(childOVL)) { - waitUntilShrinkCompleted(child, childOVL); - // RETRY - } - else if (child != child(node, 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 (isOutdatedOVL(node, 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, unlinked); - - 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 V expected, final V newValue, final long parent, - final long node, LongArray unlinked) { - if (newValue == null) { - // removal - if (vOptIsNull(node)) { - // This node is already removed, nothing to do. - return null; - } - } - - if (newValue == null && (left(node) == 0 || right(node) == 0)) { - // potential unlink, get ready by locking the parent - final Object prev; - final long damaged; - - KeyLock.Lock pl = lock.lock(parent); - - try { - if (isUnlinked(shrinkOVL(parent)) || parent(node) != parent) { - return SpecialRetry; - } - - KeyLock.Lock nl = lock.lock(node); - - try { - if (isUnlinked(shrinkOVL(node))) { - return SpecialRetry; - } - - assert parent(node) == parent && parent > 0; - - prev = vOpt(node); - - if (!shouldUpdate(func, prev, expected)) { - return noUpdateResult(func, prev); - } - - if (prev == null) { - return updateResult(func, prev); - } - - if (!attemptUnlink_nl(parent, node, unlinked)) { - return SpecialRetry; - } - } - finally { - if (nl != null) - nl.unlock(); - } - - // try to fix the parent while we've still got the lock - damaged = fixHeight_nl(parent); - } - finally { - if (pl != null) - pl.unlock(); - } - - fixHeightAndRebalance(damaged, unlinked); - - return updateResult(func, prev); - } - else { - // potential update (including remove-without-unlink) - KeyLock.Lock l = lock.lock(node); - - try { - // regular version changes don't bother us - if (isUnlinked(shrinkOVL(node))) { - return SpecialRetry; - } - - final Object prev = vOpt(node); - - if (!shouldUpdate(func, prev, expected)) { - return noUpdateResult(func, prev); - } - - // retry if we now detect that unlink is possible - if (newValue == null && (left(node) == 0 || right(node) == 0)) { - return SpecialRetry; - } - - // update in-place - vOpt(node, newValue); - - afterNodeUpdate_nl(node, newValue); - - return updateResult(func, prev); - } - finally { - if (l != null) - l.unlock(); - } - } - } - - /** - * Special protected method to be overridden by extending classes. - * @param node Node pointer. - * @param val Value. - */ - protected void afterNodeUpdate_nl(long node, V val) { - // No-op. - } - - /** - * Does not adjust the size or any heights. - */ - private boolean attemptUnlink_nl(final long parent, final long node, LongArray unlinked) { - // assert (Thread.holdsLock(parent)); - // assert (Thread.holdsLock(node)); - assert (!isUnlinked(shrinkOVL(parent))); - - final long parentL = left(parent); - final long parentR = right(parent); - - if (parentL != node && parentR != node) { - // node is no longer a child of parent - return false; - } - - long nodeOVL = shrinkOVL(node); - - assert (!isUnlinked(nodeOVL)); - assert (parent == parent(node)); - - final long left = unsharedLeft(node, unlinked); - final long right = unsharedRight(node, unlinked); - - if (left != 0 && right != 0) { - // splicing is no longer possible - return false; - } - - final long splice = left != 0 ? left : right; - - if (parentL == node) { - left(parent, splice); - } - else { - right(parent, splice); - } - - if (splice != 0) { - parent(splice, parent); - } - - shrinkOVL(node, UnlinkedOVL); - vOpt(node, null); - - unlinked.add(node); - - return true; - } - - /** {@inheritDoc} */ - @Override public Map.Entry<K,V> pollFirstEntry() { - LongArray unlinked = new LongArray(); - - try { - return pollExtremeEntry(Left, unlinked); - } - finally { - deallocate(unlinked); - } - } - - /** {@inheritDoc} */ - @Override public Map.Entry<K,V> pollLastEntry() { - LongArray unlinked = new LongArray(); - - try { - return pollExtremeEntry(Right, unlinked); - } - finally { - deallocate(unlinked); - } - } - - /** - * @param dir Direction. - * @param unlinked Array for unlinked. - * @return Entry. - */ - private Map.Entry<K,V> pollExtremeEntry(final char dir, LongArray unlinked) { - int sizeDelta = 0; - - final Map.Entry<K,V> prev = pollExtremeEntryUnderRoot(dir, holderRef, unlinked); - - if (prev != null) { - sizeDelta = -1; - } - - return prev; - } - - /** - * @param dir Direction. - * @param holder Root holder. - * @param unlinked Array for unlinked nodes. - * @return Entry. - */ - private Map.Entry<K,V> pollExtremeEntryUnderRoot(final char dir, final long holder, LongArray unlinked) { - while (true) { - final long right = unsharedRight(holder, unlinked); - - if (right == 0) { - // tree is empty, nothing to remove - return null; - } - else { - final long ovl = shrinkOVL(right); - - if (isShrinkingOrUnlinked(ovl)) { - waitUntilShrinkCompleted(right, ovl); - // RETRY - } - else if (right == right(holder)) { - // this is the protected .right - final Map.Entry<K,V> result = attemptRemoveExtreme(dir, holder, right, ovl, unlinked); - - if (result != SpecialRetry) { - return result; - } - // else RETRY - } - } - } - } - - /** - * @param dir Direction. - * @param parent Parent. - * @param node Node. - * @param nodeOVL OVL. - * @param unlinked Array for unlinked nodes. - * @return Entry. - */ - private Map.Entry<K,V> attemptRemoveExtreme(final char dir, final long parent, final long node, final long nodeOVL, - LongArray unlinked) { - assert !isUnlinked(nodeOVL); - - while (true) { - final long child = unsharedChild(node, dir, unlinked); - - if (isOutdatedOVL(node, nodeOVL)) { - return null; - } - - if (child == 0) { - // potential unlink, get ready by locking the parent - final Object vo; - final long damaged; - - KeyLock.Lock pl = lock.lock(parent); - - try { - if (isUnlinked(shrinkOVL(parent)) || parent(node) != parent) { - return null; - } - - KeyLock.Lock nl = lock.lock(node); - - try { - vo = vOpt(node); - - if (child(node, dir) != 0 || !attemptUnlink_nl(parent, node, unlinked)) { - return null; - } - // success! - } - finally { - if (nl != null) - nl.unlock(); - } - - // try to fix parent.height while we've still got the lock - damaged = fixHeight_nl(parent); - } - finally { - if (pl != null) - pl.unlock(); - } - - fixHeightAndRebalance(damaged, unlinked); - - return new SimpleImmutableEntry<K,V>(key(node), (V)vo); - } - else { - // keep going down - final long childOVL = shrinkOVL(child); - - if (isShrinkingOrUnlinked(childOVL)) { - waitUntilShrinkCompleted(child, childOVL); - // RETRY - } - else if (child != child(node, 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 (isOutdatedOVL(node, nodeOVL)) { - return null; - } - - final Map.Entry<K,V> result = attemptRemoveExtreme(dir, node, child, childOVL, unlinked); - - if (result != null) { - return result; - } - // else RETRY - } - } - } - } - - /** */ - private static final int UnlinkRequired = -1; - - /** */ - private static final int RebalanceRequired = -2; - - /** */ - private static final int NothingRequired = -3; - - /** - * @param node Node. - * @return Condition. - */ - private int nodeCondition(final long node) { - // Begin atomic. - final long nL = left(node); - final long nR = right(node); - - if ((nL == 0 || nR == 0) && vOptIsNull(node)) { - return UnlinkRequired; - } - - final int hN = height(node); - 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; - } - - /** - * @param node Node. - * @param unlinked Array for unlinked nodes. - */ - private void fixHeightAndRebalance(long node, LongArray unlinked) { - while (node != 0 && parent(node) > 0) { - final int condition = nodeCondition(node); - - if (condition == NothingRequired || isUnlinked(shrinkOVL(node))) { - // nothing to do, or no point in fixing this node - return; - } - - if (condition != UnlinkRequired && condition != RebalanceRequired) { - long n = node; - - KeyLock.Lock l = lock.lock(n); - - try { - if (isUnlinked(shrinkOVL(node))) - return; - - node = fixHeight_nl(node); - } - finally { - if (l != null) - l.unlock(); - } - } - else { - final long nParent = parent(node); - - if (nParent <= 0) - continue; - - KeyLock.Lock pl = lock.lock(nParent); - - try { - if (!isUnlinked(shrinkOVL(nParent)) && parent(node) == nParent) { - long n = node; - - KeyLock.Lock nl = lock.lock(n); - - try { - if (isUnlinked(shrinkOVL(node))) - return; - - node = rebalance_nl(nParent, node, unlinked); - } - finally { - if (nl != null) - nl.unlock(); - } - } - // else RETRY - } - finally { - if (pl != null) - pl.unlock(); - } - } - } - } - - /** - * 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 long fixHeight_nl(final long 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 0; - - default: - height(node, c); - - // we've damaged our parent, but we can't fix it now - return parent(node); - } - } - - /** - * nParent and n must be locked on entry. Returns a damaged node, or null - * if no more rebalancing is necessary. - */ - private long rebalance_nl(final long nParent, final long n, LongArray unlinked) { - final long nL = unsharedLeft(n, unlinked); - final long nR = unsharedRight(n, unlinked); - - if ((nL == 0 || nR == 0) && vOptIsNull(n)) { - if (attemptUnlink_nl(nParent, n, unlinked)) { - // 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 = height(n); - 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, unlinked); - } - else if (bal < -1) { - return rebalanceToLeft_nl(nParent, n, nR, hL0, unlinked); - } - else if (hNRepl != hN) { - // we've got more than enough locks to do a height change, no need to - // trigger a retry - height(n, hNRepl); - - // nParent is already locked, let's try to fix it too - return fixHeight_nl(nParent); - } - else { - // nothing to do - return 0; - } - } - - /** - * @param nParent Parent. - * @param n Node. - * @param nL Left child. - * @param hR0 Height of right child. - * @param unlinked Array for unlinked nodes. - * @return Node. - */ - private long rebalanceToRight_nl(final long nParent, final long n, final long nL, final int hR0, - LongArray unlinked) { - // L is too large, we will rotate-right. If L.R is taller - // than L.L, then we will first rotate-left L. - KeyLock.Lock nLl = lock.lock(nL); - - try { - final int hL = height(nL); - - if (hL - hR0 <= 1) { - return n; // retry - } - else { - final long nLR = unsharedRight(nL, unlinked); - final int hLL0 = height(left(nL)); - 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 { - KeyLock.Lock nLRl = lock.lock(nLR); - - try { - // If our hLR snapshot is incorrect then we might - // actually need to do a single rotate-right on n. - final int hLR = height(nLR); - - 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(left(nLR)); - final int b = hLL0 - hLRL; - - if (b >= -1 && b <= 1 && !((hLL0 == 0 || hLRL == 0) && vOptIsNull(nL))) { - // nParent.child.left won't be damaged after a double rotation - return rotateRightOverLeft_nl(nParent, n, nL, hR0, hLL0, nLR, hLRL, unlinked); - } - } - } - finally { - if (nLRl != null) - nLRl.unlock(); - } - - // focus on nL, if necessary n will be balanced later - return rebalanceToLeft_nl(n, nL, nLR, hLL0, unlinked); - } - } - } - finally { - if (nLl != null) - nLl.unlock(); - } - } - - /** - * @param nParent Parent. - * @param n Node. - * @param nR Right child. - * @param hL0 Head of left child. - * @param unlinked Array for unlinked nodes. - * @return Node. - */ - private long rebalanceToLeft_nl(final long nParent, final long n, final long nR, final int hL0, - LongArray unlinked) { - KeyLock.Lock nRl = lock.lock(nR); - - try { - final int hR = height(nR); - - if (hL0 - hR >= -1) { - return n; // retry - } - else { - final long nRL = unsharedLeft(nR, unlinked); - final int hRL0 = height(nRL); - final int hRR0 = height(right(nR)); - - if (hRR0 >= hRL0) { - return rotateLeft_nl(nParent, n, hL0, nR, nRL, hRL0, hRR0); - } - else { - KeyLock.Lock nRLl = lock.lock(nRL); - - try { - final int hRL = height(nRL); - - if (hRR0 >= hRL) { - return rotateLeft_nl(nParent, n, hL0, nR, nRL, hRL, hRR0); - } - else { - final int hRLR = height(right(nRL)); - final int b = hRR0 - hRLR; - - if (b >= -1 && b <= 1 && !((hRR0 == 0 || hRLR == 0) && vOptIsNull(nR))) { - return rotateLeftOverRight_nl(nParent, n, hL0, nR, nRL, hRR0, hRLR, unlinked); - } - } - } - finally { - if (nRLl != null) - nRLl.unlock(); - } - - return rebalanceToRight_nl(n, nR, nRL, hRR0, unlinked); - } - } - } - finally { - if (nRl != null) - nRl.unlock(); - } - } - - /** - * @param nParent Parent. - * @param n Node. - * @param nL Left child. - * @param hR Height of right. - * @param hLL Height of left-left child. - * @param nLR Left
<TRUNCATED>
