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 <[email protected]> Authored: Tue Dec 1 09:46:03 2015 +0200 Committer: Sylvain Lebresne <[email protected]> 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); + } + } +}
