Merge branch 'cassandra-2.2' into cassandra-3.0
Conflicts:
src/java/org/apache/cassandra/utils/btree/TreeBuilder.java
test/unit/org/apache/cassandra/db/NativeCellTest.java
Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/79f230f3
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/79f230f3
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/79f230f3
Branch: refs/heads/trunk
Commit: 79f230f30d3834aa1b9f2d009c51b6dfc4c37288
Parents: 1e8007b 82aa796
Author: Benedict Elliott Smith <bened...@apache.org>
Authored: Mon Nov 2 18:59:24 2015 +0000
Committer: Benedict Elliott Smith <bened...@apache.org>
Committed: Mon Nov 2 18:59:24 2015 +0000
----------------------------------------------------------------------
.../cassandra/utils/btree/NodeBuilder.java | 11 +-
.../cassandra/utils/btree/TreeBuilder.java | 2 +-
.../cassandra/utils/memory/MemoryUtil.java | 2 +-
.../org/apache/cassandra/db/NativeCellTest.java | 280 +++++++++++++++++++
4 files changed, 288 insertions(+), 7 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/79f230f3/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/79f230f3/src/java/org/apache/cassandra/utils/btree/TreeBuilder.java
----------------------------------------------------------------------
diff --cc src/java/org/apache/cassandra/utils/btree/TreeBuilder.java
index cb3ddc5,0000000..024902e
mode 100644,000000..100644
--- a/src/java/org/apache/cassandra/utils/btree/TreeBuilder.java
+++ b/src/java/org/apache/cassandra/utils/btree/TreeBuilder.java
@@@ -1,119 -1,0 +1,119 @@@
+/*
+ * 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.Comparator;
+
+import static org.apache.cassandra.utils.btree.BTree.EMPTY_LEAF;
+import static org.apache.cassandra.utils.btree.BTree.FAN_SHIFT;
+import static org.apache.cassandra.utils.btree.BTree.POSITIVE_INFINITY;
+
+/**
+ * A class for constructing a new BTree, either from an existing one and some
set of modifications
+ * or a new tree from a sorted collection of items.
+ * <p/>
+ * This is a fairly heavy-weight object, so a ThreadLocal instance is created
for making modifications to a tree
+ */
+final class TreeBuilder
+{
+ private final NodeBuilder rootBuilder = new NodeBuilder();
+
+ /**
+ * At the highest level, we adhere to the classic b-tree insertion
algorithm:
+ *
+ * 1. Add to the appropriate leaf
+ * 2. Split the leaf if necessary, add the median to the parent
+ * 3. Split the parent if necessary, etc.
+ *
+ * There is one important difference: we don't actually modify the
original tree, but copy each node that we
+ * modify. Note that every node on the path to the key being inserted or
updated will be modified; this
+ * implies that at a minimum, the root node will be modified for every
update, so every root is a "snapshot"
+ * of a tree that can be iterated or sliced without fear of concurrent
modifications.
+ *
+ * The NodeBuilder class handles the details of buffering the copied
contents of the original tree and
+ * adding in our changes. Since NodeBuilder maintains parent/child
references, it also handles parent-splitting
+ * (easy enough, since any node affected by the split will already be
copied into a NodeBuilder).
+ *
+ * One other difference from the simple algorithm is that we perform
modifications in bulk;
+ * we assume @param source has been sorted, e.g. by BTree.update, so the
update of each key resumes where
+ * the previous left off.
+ */
+ public <C, K extends C, V extends C> Object[] update(Object[] btree,
Comparator<C> comparator, Iterable<K> source, UpdateFunction<K, V> updateF)
+ {
+ assert updateF != null;
+
+ NodeBuilder current = rootBuilder;
+ current.reset(btree, POSITIVE_INFINITY, updateF, comparator);
+
+ for (K key : source)
+ {
+ while (true)
+ {
+ if (updateF.abortEarly())
+ {
+ rootBuilder.clear();
+ return null;
+ }
+ NodeBuilder next = current.update(key);
+ if (next == null)
+ break;
+ // we were in a subtree from a previous key that didn't
contain this new key;
+ // retry against the correct subtree
+ current = next;
+ }
+ }
+
+ // finish copying any remaining keys from the original btree
+ while (true)
+ {
+ NodeBuilder next = current.finish();
+ if (next == null)
+ break;
+ current = next;
+ }
+
+ // updating with POSITIVE_INFINITY means that current should be back
to the root
+ assert current.isRoot();
+
+ Object[] r = current.toNode();
+ current.clear();
+ return r;
+ }
+
+ public <C, K extends C, V extends C> Object[] build(Iterable<K> source,
UpdateFunction<K, V> updateF, int size)
+ {
+ assert updateF != null;
+
+ NodeBuilder current = rootBuilder;
+ // we descend only to avoid wasting memory; in update() we will often
descend into existing trees
+ // so here we want to descend also, so we don't have lg max(N) depth
in both directions
+ while ((size >>= FAN_SHIFT) > 0)
+ current = current.ensureChild();
+
+ current.reset(EMPTY_LEAF, POSITIVE_INFINITY, updateF, null);
+ for (K key : source)
- current.addNewKey(updateF.apply(key));
++ current.addNewKey(key);
+
+ current = current.ascendToRoot();
+
+ Object[] r = current.toNode();
+ current.clear();
+ return r;
+ }
+}
http://git-wip-us.apache.org/repos/asf/cassandra/blob/79f230f3/src/java/org/apache/cassandra/utils/memory/MemoryUtil.java
----------------------------------------------------------------------
