You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by sl...@apache.org on 2015/12/15 16:21:15 UTC
cassandra git commit: Efficent BTree removal
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 <ha...@gmail.com>
Authored: Tue Dec 1 09:46:03 2015 +0200
Committer: Sylvain Lebresne <sy...@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);
+ }
+ }
+}