cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From slebre...@apache.org
Subject cassandra git commit: Efficent BTree removal
Date Tue, 15 Dec 2015 15:21:15 GMT
Repository: cassandra
Updated Branches:
  refs/heads/trunk d5f1175f3 -> 1c62850c9


Efficent BTree removal

patch by haaawk; reviewed by blambov for CASSANDRA-9991


Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/1c62850c
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/1c62850c
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/1c62850c

Branch: refs/heads/trunk
Commit: 1c62850c9e49e318eab70ab0c59b05bfea3f37ca
Parents: d5f1175
Author: Piotr Jastrzebski <haaawk@gmail.com>
Authored: Tue Dec 1 09:46:03 2015 +0200
Committer: Sylvain Lebresne <sylvain@datastax.com>
Committed: Tue Dec 15 16:19:41 2015 +0100

----------------------------------------------------------------------
 CHANGES.txt                                     |   1 +
 src/java/org/apache/cassandra/db/Columns.java   |   3 +-
 .../org/apache/cassandra/utils/btree/BTree.java |  45 +++
 .../cassandra/utils/btree/BTreeRemoval.java     | 338 ++++++++++++++++
 .../cassandra/utils/btree/BTreeRemovalTest.java | 385 +++++++++++++++++++
 5 files changed, 771 insertions(+), 1 deletion(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/cassandra/blob/1c62850c/CHANGES.txt
----------------------------------------------------------------------
diff --git a/CHANGES.txt b/CHANGES.txt
index 0294efc..4149d91 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -1,4 +1,5 @@
 3.2
+ * More efficient BTree removal (CASSANDRA-9991)
  * Make tablehistograms accept the same syntax as tablestats (CASSANDRA-10149)
  * Group pending compactions based on table (CASSANDRA-10718)
  * Add compressor name in sstablemetadata output (CASSANDRA-9879)

http://git-wip-us.apache.org/repos/asf/cassandra/blob/1c62850c/src/java/org/apache/cassandra/db/Columns.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/Columns.java b/src/java/org/apache/cassandra/db/Columns.java
index cad295c..e3c30fa 100644
--- a/src/java/org/apache/cassandra/db/Columns.java
+++ b/src/java/org/apache/cassandra/db/Columns.java
@@ -38,6 +38,7 @@ import org.apache.cassandra.utils.ByteBufferUtil;
 import org.apache.cassandra.utils.SearchIterator;
 import org.apache.cassandra.utils.btree.BTree;
 import org.apache.cassandra.utils.btree.BTreeSearchIterator;
+import org.apache.cassandra.utils.btree.BTreeRemoval;
 import org.apache.cassandra.utils.btree.UpdateFunction;
 
 /**
@@ -343,7 +344,7 @@ public class Columns extends AbstractCollection<ColumnDefinition>
implements Col
         if (!contains(column))
             return this;
 
-        Object[] newColumns = BTree.<ColumnDefinition>transformAndFilter(columns, (c)
-> c.equals(column) ? null : c);
+        Object[] newColumns = BTreeRemoval.<ColumnDefinition>remove(columns, Comparator.naturalOrder(),
column);
         return new Columns(newColumns);
     }
 

http://git-wip-us.apache.org/repos/asf/cassandra/blob/1c62850c/src/java/org/apache/cassandra/utils/btree/BTree.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/btree/BTree.java b/src/java/org/apache/cassandra/utils/btree/BTree.java
index fe08011..1c3d2e2 100644
--- a/src/java/org/apache/cassandra/utils/btree/BTree.java
+++ b/src/java/org/apache/cassandra/utils/btree/BTree.java
@@ -67,6 +67,8 @@ public class BTree
     // NB we encode Path indexes as Bytes, so this needs to be less than Byte.MAX_VALUE /
2
     static final int FAN_FACTOR = 1 << FAN_SHIFT;
 
+    static final int MINIMAL_NODE_SIZE = FAN_FACTOR >> 1;
+
     // An empty BTree Leaf - which is the same as an empty BTree
     static final Object[] EMPTY_LEAF = new Object[1];
 
@@ -296,6 +298,40 @@ public class BTree
 
     /**
      * Modifies the provided btree directly. THIS SHOULD NOT BE USED WITHOUT EXTREME CARE
as BTrees are meant to be immutable.
+     * Finds and replaces the item provided by index in the tree.
+     */
+    public static <V> void replaceInSitu(Object[] tree, int index, V replace)
+    {
+        // WARNING: if semantics change, see also InternalCursor.seekTo, which mirrors this
implementation
+        if ((index < 0) | (index >= size(tree)))
+            throw new IndexOutOfBoundsException(index + " not in range [0.." + size(tree)
+ ")");
+
+        while (!isLeaf(tree))
+        {
+            final int[] sizeMap = getSizeMap(tree);
+            int boundary = Arrays.binarySearch(sizeMap, index);
+            if (boundary >= 0)
+            {
+                // exact match, in this branch node
+                assert boundary < sizeMap.length - 1;
+                tree[boundary] = replace;
+                return;
+            }
+
+            boundary = -1 -boundary;
+            if (boundary > 0)
+            {
+                assert boundary < sizeMap.length;
+                index -= (1 + sizeMap[boundary - 1]);
+            }
+            tree = (Object[]) tree[getChildStart(tree) + boundary];
+        }
+        assert index < getLeafKeyEnd(tree);
+        tree[index] = replace;
+    }
+
+    /**
+     * Modifies the provided btree directly. THIS SHOULD NOT BE USED WITHOUT EXTREME CARE
as BTrees are meant to be immutable.
      * Finds and replaces the provided item in the tree. Both should sort as equal to each
other (although this is not enforced)
      */
     public static <V> void replaceInSitu(Object[] node, Comparator<? super V>
comparator, V find, V replace)
@@ -1073,11 +1109,20 @@ public class BTree
             return node.length >= FAN_FACTOR / 2 && node.length <= FAN_FACTOR
+ 1;
         }
 
+        final int keyCount = getBranchKeyEnd(node);
+        if ((!isRoot && keyCount < FAN_FACTOR / 2) || keyCount > FAN_FACTOR
+ 1)
+            return false;
+
         int type = 0;
+        int size = -1;
+        int[] sizeMap = getSizeMap(node);
         // compare each child node with the branch element at the head of this node it corresponds
with
         for (int i = getChildStart(node); i < getChildEnd(node) ; i++)
         {
             Object[] child = (Object[]) node[i];
+            size += size(child) + 1;
+            if (sizeMap[i - getChildStart(node)] != size)
+                return false;
             Object localmax = i < node.length - 2 ? node[i - getChildStart(node)] : max;
             if (!isWellFormed(cmp, child, false, min, localmax))
                 return false;

http://git-wip-us.apache.org/repos/asf/cassandra/blob/1c62850c/src/java/org/apache/cassandra/utils/btree/BTreeRemoval.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/btree/BTreeRemoval.java b/src/java/org/apache/cassandra/utils/btree/BTreeRemoval.java
new file mode 100644
index 0000000..74fa402
--- /dev/null
+++ b/src/java/org/apache/cassandra/utils/btree/BTreeRemoval.java
@@ -0,0 +1,338 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.cassandra.utils.btree;
+
+import java.util.Arrays;
+import java.util.Comparator;
+
+public class BTreeRemoval
+{
+    /**
+     * Remove |elem| from |btree|. If it's not present then return |btree| itself.
+     */
+    public static <V> Object[] remove(final Object[] btree, final Comparator<? super
V> comparator, final V elem)
+    {
+        if (BTree.isEmpty(btree))
+            return btree;
+        int index = -1;
+        V elemToSwap = null;
+        int lb = 0;
+        Object[] node = btree;
+        while (true)
+        {
+            int keyEnd = BTree.getKeyEnd(node);
+            int i = Arrays.binarySearch((V[]) node, 0, keyEnd, elem, comparator);
+
+            if (i >= 0)
+            {
+                if (BTree.isLeaf(node))
+                    index = lb + i;
+                else
+                {
+                    final int indexInNode = BTree.getSizeMap(node)[i];
+                    index = lb + indexInNode - 1;
+                    elemToSwap = BTree.findByIndex(node, indexInNode - 1);
+                }
+                break;
+            }
+            if (BTree.isLeaf(node))
+                return btree;
+
+            i = -1 - i;
+            if (i > 0)
+                lb += BTree.getSizeMap(node)[i - 1] + 1;
+
+            node = (Object[]) node[keyEnd + i];
+        }
+        if (BTree.size(btree) == 1)
+            return BTree.empty();
+        Object[] result = removeFromLeaf(btree, index);
+        if (elemToSwap != null)
+            BTree.replaceInSitu(result, index, elemToSwap);
+        return result;
+    }
+
+    /**
+     * Remove |elem| from |btree|. It has to be present and it has to reside in a leaf node.
+     */
+    private static <V> Object[] removeFromLeaf(Object[] node, int index)
+    {
+        Object[] result = null;
+        Object[] prevNode = null;
+        int prevI = -1;
+        boolean needsCopy = true;
+        while (!BTree.isLeaf(node))
+        {
+            final int keyEnd = BTree.getBranchKeyEnd(node);
+            int i = -1 - Arrays.binarySearch(BTree.getSizeMap(node), index);
+            if (i > 0)
+                index -= (1 + BTree.getSizeMap(node)[i - 1]);
+            Object[] nextNode = (Object[]) node[keyEnd + i];
+            boolean nextNodeNeedsCopy = true;
+            if (BTree.getKeyEnd(nextNode) > BTree.MINIMAL_NODE_SIZE)
+                node = copyIfNeeded(node, needsCopy);
+            else if (i > 0 && BTree.getKeyEnd((Object[]) node[keyEnd + i - 1])
> BTree.MINIMAL_NODE_SIZE)
+            {
+                node = copyIfNeeded(node, needsCopy);
+                final Object[] leftNeighbour = (Object[]) node[keyEnd + i - 1];
+                index++;
+                if (!BTree.isLeaf(leftNeighbour))
+                    index += BTree.size((Object[])leftNeighbour[BTree.getChildEnd(leftNeighbour)
- 1]);
+                nextNode = rotateLeft(node, i);
+            }
+            else if (i < keyEnd && BTree.getKeyEnd((Object[]) node[keyEnd + i
+ 1]) > BTree.MINIMAL_NODE_SIZE)
+            {
+                node = copyIfNeeded(node, needsCopy);
+                nextNode = rotateRight(node, i);
+            }
+            else
+            {
+                nextNodeNeedsCopy = false;
+                if (i > 0)
+                {
+                    final Object[] leftNeighbour = (Object[]) node[keyEnd + i - 1];
+                    final V nodeKey = (V) node[i - 1];
+                    node = keyEnd == 1 ? null : copyWithKeyAndChildRemoved(node, i - 1, i
- 1, false);
+                    nextNode = merge(leftNeighbour, nextNode, nodeKey);
+                    i = i - 1;
+                    index += BTree.size(leftNeighbour) + 1;
+                }
+                else
+                {
+                    final Object[] rightNeighbour = (Object[]) node[keyEnd + i + 1];
+                    final V nodeKey = (V) node[i];
+                    node = keyEnd == 1 ? null : copyWithKeyAndChildRemoved(node, i, i, false);
+                    nextNode = merge(nextNode, rightNeighbour, nodeKey);
+                }
+            }
+
+            if (node != null)
+            {
+                final int[] sizeMap = BTree.getSizeMap(node);
+                for (int j = i; j < sizeMap.length; ++j)
+                    sizeMap[j] -= 1;
+                if (prevNode != null)
+                    prevNode[prevI] = node;
+                else
+                    result = node;
+                prevNode = node;
+                prevI = BTree.getChildStart(node) + i;
+            }
+
+            node = nextNode;
+            needsCopy = nextNodeNeedsCopy;
+        }
+        final int keyEnd = BTree.getLeafKeyEnd(node);
+        final Object[] newLeaf = new Object[(keyEnd & 1) == 1 ? keyEnd : keyEnd - 1];
+        copyKeys(node, newLeaf, 0, index);
+        if (prevNode != null)
+            prevNode[prevI] = newLeaf;
+        else
+            result = newLeaf;
+        return result;
+    }
+
+    private static <V> Object[] rotateRight(final Object[] node, final int i) {
+        final int keyEnd = BTree.getBranchKeyEnd(node);
+        final Object[] nextNode = (Object[]) node[keyEnd + i];
+        final Object[] rightNeighbour = (Object[]) node[keyEnd + i + 1];
+        final boolean leaves = BTree.isLeaf(nextNode);
+        final int nextKeyEnd = BTree.getKeyEnd(nextNode);
+        final Object[] newChild = leaves ? null : (Object[]) rightNeighbour[BTree.getChildStart(rightNeighbour)];
+        final Object[] newNextNode =
+                copyWithKeyAndChildInserted(nextNode, nextKeyEnd, node[i], BTree.getChildCount(nextNode),
newChild);
+        node[i] = rightNeighbour[0];
+        node[keyEnd + i + 1] = copyWithKeyAndChildRemoved(rightNeighbour, 0, 0, true);
+        BTree.getSizeMap(node)[i] +=
+                leaves ? 1 : 1 + BTree.size((Object[]) newNextNode[BTree.getChildEnd(newNextNode)
- 1]);
+        return newNextNode;
+    }
+
+    private static Object[] rotateLeft(final Object[] node, final int i) {
+        final int keyEnd = BTree.getBranchKeyEnd(node);
+        final Object[] nextNode = (Object[]) node[keyEnd + i];
+        final Object[] leftNeighbour = (Object[]) node[keyEnd + i - 1];
+        final int leftNeighbourEndKey = BTree.getKeyEnd(leftNeighbour);
+        final boolean leaves = BTree.isLeaf(nextNode);
+        final Object[] newChild = leaves ? null : (Object[]) leftNeighbour[BTree.getChildEnd(leftNeighbour)
- 1];
+        final Object[] newNextNode = copyWithKeyAndChildInserted(nextNode, 0, node[i - 1],
0, newChild);
+        node[i - 1] = leftNeighbour[leftNeighbourEndKey - 1];
+        node[keyEnd + i - 1] = copyWithKeyAndChildRemoved(leftNeighbour, leftNeighbourEndKey
- 1, leftNeighbourEndKey, true);
+        BTree.getSizeMap(node)[i - 1] -= leaves ? 1 : 1 + BTree.getSizeMap(newNextNode)[0];
+        return newNextNode;
+    }
+
+    private static <V> Object[] copyWithKeyAndChildInserted(final Object[] node, final
int keyIndex, final V key, final int childIndex, final Object[] child)
+    {
+        final boolean leaf = BTree.isLeaf(node);
+        final int keyEnd = BTree.getKeyEnd(node);
+        final Object[] copy;
+        if (leaf)
+            copy = new Object[keyEnd + ((keyEnd & 1) == 1 ? 2 : 1)];
+        else
+            copy = new Object[node.length + 2];
+
+        if (keyIndex > 0)
+            System.arraycopy(node, 0, copy, 0, keyIndex);
+        copy[keyIndex] = key;
+        if (keyIndex < keyEnd)
+            System.arraycopy(node, keyIndex, copy, keyIndex + 1, keyEnd - keyIndex);
+
+        if (!leaf)
+        {
+            if (childIndex > 0)
+                System.arraycopy(node,
+                                 BTree.getChildStart(node),
+                                 copy,
+                                 keyEnd + 1,
+                                 childIndex);
+            copy[keyEnd + 1 + childIndex] = child;
+            if (childIndex <= keyEnd)
+                System.arraycopy(node,
+                                 BTree.getChildStart(node) + childIndex,
+                                 copy,
+                                 keyEnd + childIndex + 2,
+                                 keyEnd - childIndex + 1);
+            final int[] sizeMap = BTree.getSizeMap(node);
+            final int[] newSizeMap = new int[sizeMap.length + 1];
+            if (childIndex > 0)
+                System.arraycopy(sizeMap, 0, newSizeMap, 0, childIndex);
+            final int childSize = BTree.size(child);
+            newSizeMap[childIndex] = childSize + ((childIndex == 0) ? 0 : newSizeMap[childIndex
- 1] + 1);
+            for (int i = childIndex + 1; i < newSizeMap.length; ++i)
+                newSizeMap[i] = sizeMap[i - 1] + childSize + 1;
+            copy[copy.length - 1] = newSizeMap;
+        }
+        return copy;
+    }
+
+    private static <V> Object[] copyWithKeyAndChildRemoved(final Object[] node, final
int keyIndex, final int childIndex, final boolean substractSize)
+    {
+        final boolean leaf = BTree.isLeaf(node);
+        final int keyEnd = BTree.getKeyEnd(node);
+        final Object[] newNode;
+        if (leaf)
+            newNode = new Object[keyEnd - ((keyEnd & 1) == 1 ? 0 : 1)];
+        else
+            newNode = new Object[node.length - 2];
+        int offset = copyKeys(node, newNode, 0, keyIndex);
+        if (!leaf)
+        {
+            offset = copyChildren(node, newNode, offset, childIndex);
+            final int[] nodeSizeMap = BTree.getSizeMap(node);
+            final int[] newNodeSizeMap = new int[nodeSizeMap.length - 1];
+            int pos = 0;
+            final int sizeToRemove = BTree.size((Object[])node[BTree.getChildStart(node)
+ childIndex]) + 1;
+            for (int i = 0; i < nodeSizeMap.length; ++i)
+                if (i != childIndex)
+                    newNodeSizeMap[pos++] = nodeSizeMap[i] -
+                        ((substractSize && i > childIndex) ? sizeToRemove : 0);
+            newNode[offset] = newNodeSizeMap;
+        }
+        return newNode;
+    }
+
+    private static <V> Object[] merge(final Object[] left, final Object[] right, final
V nodeKey) {
+        assert BTree.getKeyEnd(left) == BTree.MINIMAL_NODE_SIZE;
+        assert BTree.getKeyEnd(right) == BTree.MINIMAL_NODE_SIZE;
+        final boolean leaves = BTree.isLeaf(left);
+        final Object[] result;
+        if (leaves)
+            result = new Object[BTree.MINIMAL_NODE_SIZE * 2 + 1];
+        else
+            result = new Object[left.length + right.length];
+        int offset = 0;
+        offset = copyKeys(left, result, offset);
+        result[offset++] = nodeKey;
+        offset = copyKeys(right, result, offset);
+        if (!leaves)
+        {
+            offset = copyChildren(left, result, offset);
+            offset = copyChildren(right, result, offset);
+            final int[] leftSizeMap = BTree.getSizeMap(left);
+            final int[] rightSizeMap = BTree.getSizeMap(right);
+            final int[] newSizeMap = new int[leftSizeMap.length + rightSizeMap.length];
+            offset = 0;
+            offset = copySizeMap(leftSizeMap, newSizeMap, offset, 0);
+            offset = copySizeMap(rightSizeMap, newSizeMap, offset, leftSizeMap[leftSizeMap.length
- 1] + 1);
+            result[result.length - 1] = newSizeMap;
+        }
+        return result;
+    }
+
+    private static int copyKeys(final Object[] from, final Object[] to, final int offset)
+    {
+        final int keysCount = BTree.getKeyEnd(from);
+        System.arraycopy(from, 0, to, offset, keysCount);
+        return offset + keysCount;
+    }
+
+    private static int copyKeys(final Object[] from, final Object[] to, final int offset,
final int skipIndex)
+    {
+        final int keysCount = BTree.getKeyEnd(from);
+        if (skipIndex > 0)
+            System.arraycopy(from, 0, to, offset, skipIndex);
+        if (skipIndex + 1 < keysCount)
+            System.arraycopy(from, skipIndex + 1, to, offset + skipIndex, keysCount - skipIndex
- 1);
+        return offset + keysCount - 1;
+    }
+
+    private static int copyChildren(final Object[] from, final Object[] to, final int offset)
+    {
+        assert !BTree.isLeaf(from);
+        final int start = BTree.getChildStart(from);
+        final int childCount = BTree.getChildCount(from);
+        System.arraycopy(from, start, to, offset, childCount);
+        return offset + childCount;
+    }
+
+    private static int copyChildren(final Object[] from, final Object[] to, final int offset,
final int skipIndex)
+    {
+        assert !BTree.isLeaf(from);
+        final int start = BTree.getChildStart(from);
+        final int childCount = BTree.getChildCount(from);
+        if (skipIndex > 0)
+            System.arraycopy(from, start, to, offset, skipIndex);
+        if (skipIndex + 1 <= childCount)
+            System.arraycopy(from, start + skipIndex + 1, to, offset + skipIndex, childCount
- skipIndex - 1);
+        return offset + childCount - 1;
+    }
+
+    private static int copySizeMap(final int[] from, final int[] to, final int offset, final
int extra)
+    {
+        for (int i = 0; i < from.length; ++i)
+            to[offset + i] = from[i] + extra;
+        return offset + from.length;
+    }
+
+    private static Object[] copyIfNeeded(final Object[] node, boolean needCopy)
+    {
+        if (!needCopy) return node;
+        final Object[] copy = new Object[node.length];
+        System.arraycopy(node, 0, copy, 0, node.length);
+        if (!BTree.isLeaf(node))
+        {
+            final int[] sizeMap = BTree.getSizeMap(node);
+            final int[] copySizeMap = new int[sizeMap.length];
+            System.arraycopy(sizeMap, 0, copySizeMap, 0, sizeMap.length);
+            copy[copy.length - 1] = copySizeMap;
+        }
+        return copy;
+    }
+}

http://git-wip-us.apache.org/repos/asf/cassandra/blob/1c62850c/test/unit/org/apache/cassandra/utils/btree/BTreeRemovalTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/utils/btree/BTreeRemovalTest.java b/test/unit/org/apache/cassandra/utils/btree/BTreeRemovalTest.java
new file mode 100644
index 0000000..a9cf383
--- /dev/null
+++ b/test/unit/org/apache/cassandra/utils/btree/BTreeRemovalTest.java
@@ -0,0 +1,385 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.cassandra.utils.btree;
+
+import static org.apache.cassandra.utils.btree.BTreeRemoval.remove;
+import static org.junit.Assert.assertArrayEquals;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+
+import java.util.Comparator;
+import java.util.Random;
+import java.util.SortedSet;
+import java.util.TreeSet;
+
+import org.junit.Test;
+
+import com.google.common.collect.Iterables;
+
+public class BTreeRemovalTest
+{
+    static
+    {
+        System.setProperty("cassandra.btree.fanfactor", "8");
+    }
+
+    private static final Comparator<Integer> CMP = new Comparator<Integer>()
+    {
+        public int compare(Integer o1, Integer o2)
+        {
+            return Integer.compare(o1, o2);
+        }
+    };
+
+    private static Object[] copy(final Object[] btree)
+    {
+        final Object[] result = new Object[btree.length];
+        System.arraycopy(btree, 0, result, 0, btree.length);
+        if (!BTree.isLeaf(btree))
+        {
+            for (int i = BTree.getChildStart(btree); i < BTree.getChildEnd(btree); ++i)
+                result[i] = copy((Object[]) btree[i]);
+            final int[] sizeMap = BTree.getSizeMap(btree);
+            final int[] resultSizeMap = new int[sizeMap.length];
+            System.arraycopy(sizeMap, 0, resultSizeMap, 0, sizeMap.length);
+            result[result.length - 1] = resultSizeMap;
+        }
+        return result;
+    }
+
+    private static Object[] assertRemove(final Object[] btree, final int key)
+    {
+        final Object[] btreeBeforeRemoval = copy(btree);
+        final Object[] result = remove(btree, CMP, key);
+        assertBTree(btreeBeforeRemoval, btree);
+        assertTrue(BTree.isWellFormed(result, CMP));
+        assertEquals(BTree.size(btree) - 1, BTree.size(result));
+        assertNull(BTree.find(result, CMP, key));
+
+        for (Integer k : BTree.<Integer>iterable(btree))
+            if (k != key)
+                assertNotNull(BTree.find(result, CMP, k));
+
+        return result;
+    }
+
+    private static void assertBTree(final Object[] expected, final Object[] result)
+    {
+        assertEquals(BTree.isEmpty(expected), BTree.isEmpty(result));
+        assertEquals(BTree.isLeaf(expected), BTree.isLeaf(result));
+        assertEquals(expected.length, result.length);
+        if (BTree.isLeaf(expected))
+        {
+            assertArrayEquals(expected, result);
+        }
+        else
+        {
+            for (int i = 0; i < BTree.getBranchKeyEnd(expected); ++i)
+                assertEquals(expected[i], result[i]);
+            for (int i = BTree.getChildStart(expected); i < BTree.getChildEnd(expected);
++i)
+                assertBTree((Object[]) expected[i], (Object[]) result[i]);
+            assertArrayEquals(BTree.getSizeMap(expected), BTree.getSizeMap(result));
+        }
+    }
+
+    private static Object[] generateLeaf(int from, int size)
+    {
+        final Object[] result = new Object[(size & 1) == 1 ? size : size + 1];
+        for (int i = 0; i < size; ++i)
+            result[i] = from + i;
+        return result;
+    }
+
+    private static Object[] generateBranch(int[] keys, Object[][] children)
+    {
+        assert keys.length > 0;
+        assert children.length > 1;
+        assert children.length == keys.length + 1;
+        final Object[] result = new Object[keys.length + children.length + 1];
+        for (int i = 0; i < keys.length; ++i)
+            result[i] = keys[i];
+        for (int i = 0; i < children.length; ++i)
+            result[keys.length + i] = children[i];
+        final int[] sizeMap = new int[children.length];
+        sizeMap[0] = BTree.size(children[0]);
+        for (int i = 1; i < children.length; ++i)
+            sizeMap[i] = sizeMap[i - 1] + BTree.size(children[i]) + 1;
+        result[result.length - 1] = sizeMap;
+        return result;
+    }
+
+    private static Object[] generateSampleTwoLevelsTree(final int[] leafSizes)
+    {
+        assert leafSizes.length > 1;
+        final Object[][] leaves = new Object[leafSizes.length][];
+        for (int i = 0; i < leaves.length; ++i)
+            leaves[i] = generateLeaf(10 * i + 1, leafSizes[i]);
+        final int[] keys = new int[leafSizes.length - 1];
+        for (int i = 0; i < keys.length; ++i)
+            keys[i] = 10 * (i + 1);
+        final Object[] btree = generateBranch(keys, leaves);
+        assertTrue(BTree.isWellFormed(btree, CMP));
+        return btree;
+    }
+
+    private static Object[] generateSampleThreeLevelsTree(final int[] middleNodeSizes)
+    {
+        assert middleNodeSizes.length > 1;
+        final Object[][] middleNodes = new Object[middleNodeSizes.length][];
+        for (int i = 0; i < middleNodes.length; ++i)
+        {
+            final Object[][] leaves = new Object[middleNodeSizes[i]][];
+            for (int j = 0; j < middleNodeSizes[i]; ++j)
+                leaves[j] = generateLeaf(100 * i + 10 * j + 1, 4);
+            final int[] keys = new int[middleNodeSizes[i] - 1];
+            for (int j = 0; j < keys.length; ++j)
+                keys[j] = 100 * i + 10 * (j + 1);
+            middleNodes[i] = generateBranch(keys, leaves);
+        }
+        final int[] keys = new int[middleNodeSizes.length - 1];
+        for (int i = 0; i < keys.length; ++i)
+            keys[i] = 100 * (i + 1);
+        final Object[] btree = generateBranch(keys, middleNodes);
+        assertTrue(BTree.isWellFormed(btree, CMP));
+        return btree;
+    }
+
+    @Test
+    public void testRemoveFromEmpty()
+    {
+        assertBTree(BTree.empty(), remove(BTree.empty(), CMP, 1));
+    }
+
+    @Test
+    public void testRemoveNonexistingElement()
+    {
+        final Object[] btree = new Object[] {1, 2, 3, 4, null};
+        assertBTree(btree, remove(btree, CMP, 5));
+    }
+
+    @Test
+    public void testRemoveLastElement()
+    {
+        final Object[] btree = new Object[] {1};
+        assertBTree(BTree.empty(), remove(btree, CMP, 1));
+    }
+
+    @Test
+    public void testRemoveFromRootWhichIsALeaf()
+    {
+        for (int size = 1; size < 9; ++size)
+        {
+            final Object[] btree = new Object[(size & 1) == 1 ? size : size + 1];
+            for (int i = 0; i < size; ++i)
+                btree[i] = i + 1;
+            for (int i = 0; i < size; ++i)
+            {
+                final Object[] result = remove(btree, CMP, i + 1);
+                assertTrue("size " + size, BTree.isWellFormed(result, CMP));
+                for (int j = 0; j < i; ++j)
+                    assertEquals("size " + size + "elem " + j, btree[j], result[j]);
+                for (int j = i; j < size - 1; ++j)
+                    assertEquals("size " + size + "elem " + j, btree[j + 1], result[j]);
+                for (int j = size - 1; j < result.length; ++j)
+                    assertNull("size " + size + "elem " + j, result[j]);
+            }
+
+            {
+                final Object[] result = remove(btree, CMP, 0);
+                assertTrue("size " + size, BTree.isWellFormed(result, CMP));
+                assertBTree(btree, result);
+            }
+
+            {
+                final Object[] result = remove(btree, CMP, size + 1);
+                assertTrue("size " + size, BTree.isWellFormed(result, CMP));
+                assertBTree(btree, result);
+            }
+        }
+    }
+
+    @Test
+    public void testRemoveFromNonMinimalLeaf()
+    {
+        for (int size = 5; size < 9; ++size)
+        {
+            final Object[] btree = generateSampleTwoLevelsTree(new int[] {size, 4, 4, 4,
4});
+
+            for (int i = 1; i < size + 1; ++i)
+                assertRemove(btree, i);
+        }
+    }
+
+    @Test
+    public void testRemoveFromMinimalLeafRotateLeft()
+    {
+        final Object[] btree = generateSampleTwoLevelsTree(new int[] {4, 5, 5, 5, 5});
+
+        for (int i = 11; i < 15; ++i)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void testRemoveFromMinimalLeafRotateRight1()
+    {
+        final Object[] btree = generateSampleTwoLevelsTree(new int[] {4, 5, 5, 5, 5});
+
+        for (int i = 1; i < 5; ++i)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void testRemoveFromMinimalLeafRotateRight2()
+    {
+        final Object[] btree = generateSampleTwoLevelsTree(new int[] {4, 4, 5, 5, 5});
+
+        for (int i = 11; i < 15; ++i)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void testRemoveFromMinimalLeafMergeWithLeft1()
+    {
+        final Object[] btree = generateSampleTwoLevelsTree(new int[] {4, 4, 4, 4, 4});
+
+        for (int i = 11; i < 15; ++i)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void testRemoveFromMinimalLeafMergeWithLeft2()
+    {
+        final Object[] btree = generateSampleTwoLevelsTree(new int[] {4, 4, 4, 4, 4});
+
+        for (int i = 41; i < 45; ++i)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void testRemoveFromMinimalLeafMergeWithRight()
+    {
+        final Object[] btree = generateSampleTwoLevelsTree(new int[] {4, 4, 4, 4, 4});
+
+        for (int i = 1; i < 5; ++i)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void testRemoveFromMinimalLeafWhenSingleKeyRootMergeWithLeft()
+    {
+        final Object[] btree = generateSampleTwoLevelsTree(new int[] {4, 4});
+
+        for (int i = 1; i < 5; ++i)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void testRemoveFromMinimalLeafWhenSingleKeyRootMergeWithRight()
+    {
+        final Object[] btree = generateSampleTwoLevelsTree(new int[] {4, 4});
+
+        for (int i = 11; i < 15; ++i)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void testRemoveFromMinimalLeafWithBranchLeftRotation()
+    {
+        final Object[] btree = generateSampleThreeLevelsTree(new int[] {6, 5, 5, 5, 5});
+        for (int i = 101; i < 105; ++i)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void testRemoveFromMinimalLeafWithBranchRightRotation1()
+    {
+        final Object[] btree = generateSampleThreeLevelsTree(new int[] {5, 6, 5, 5, 5});
+        for (int i = 1; i < 5; ++i)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void testRemoveFromMinimalLeafWithBranchRightRotation2()
+    {
+        final Object[] btree = generateSampleThreeLevelsTree(new int[] {5, 5, 6, 5, 5});
+        for (int i = 101; i < 105; ++i)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void testRemoveFromMinimalLeafWithBranchMergeWithLeft1()
+    {
+        final Object[] btree = generateSampleThreeLevelsTree(new int[] {5, 5, 5, 5, 5});
+        for (int i = 101; i < 105; ++i)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void testRemoveFromMinimalLeafWithBranchMergeWithLeft2()
+    {
+        final Object[] btree = generateSampleThreeLevelsTree(new int[] {5, 5, 5, 5, 5});
+        for (int i = 401; i < 405; ++i)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void testRemoveFromMinimalLeafWithBranchMergeWithRight()
+    {
+        final Object[] btree = generateSampleThreeLevelsTree(new int[] {5, 5, 5, 5, 5});
+        for (int i = 1; i < 5; ++i)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void testRemoveFromMiddleBranch()
+    {
+        final Object[] btree = generateSampleThreeLevelsTree(new int[] {5, 5, 5, 5, 5});
+        for (int i = 10; i < 50; i += 10)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void testRemoveFromRootBranch()
+    {
+        final Object[] btree = generateSampleThreeLevelsTree(new int[] {5, 5, 5, 5, 5});
+        for (int i = 100; i < 500; i += 100)
+            assertRemove(btree, i);
+    }
+
+    @Test
+    public void randomizedTest()
+    {
+        Random rand = new Random(2);
+        SortedSet<Integer> data = new TreeSet<>();
+        for (int i = 0; i < 1000; ++i)
+            data.add(rand.nextInt());
+        Object[] btree = BTree.build(data, UpdateFunction.<Integer>noOp());
+
+        assertTrue(BTree.isWellFormed(btree, CMP));
+        assertTrue(Iterables.elementsEqual(data, BTree.iterable(btree)));
+        while (btree != BTree.empty())
+        {
+            int idx = rand.nextInt(BTree.size(btree));
+            Integer val = BTree.findByIndex(btree, idx);
+            assertTrue(data.remove(val));
+            btree = assertRemove(btree, val);
+        }
+    }
+}


Mime
View raw message