Repository: cassandra Updated Branches: refs/heads/cassandra-2.1 0cb1e3d24 -> 948964b52 refs/heads/trunk c1647c59e -> c0aa7467e
clean up Path and Cursor now that we know stack allocation doesn't work as expected patch by Benedict Elliott Smith; reviewed by jbellis for CASSANDRA-6692 Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/948964b5 Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/948964b5 Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/948964b5 Branch: refs/heads/cassandra-2.1 Commit: 948964b52fc58d6aa08f369be9e2d3a058cfea95 Parents: 0cb1e3d Author: Jonathan Ellis <[email protected]> Authored: Wed Mar 12 18:40:06 2014 -0500 Committer: Jonathan Ellis <[email protected]> Committed: Wed Mar 12 18:40:06 2014 -0500 ---------------------------------------------------------------------- .../org/apache/cassandra/utils/btree/BTree.java | 23 ++++++++------ .../apache/cassandra/utils/btree/Cursor.java | 23 ++------------ .../org/apache/cassandra/utils/btree/Path.java | 32 +++++++++++--------- .../apache/cassandra/utils/LongBTreeTest.java | 2 +- 4 files changed, 34 insertions(+), 46 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/948964b5/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 ad5065e..5ca5006 100644 --- a/src/java/org/apache/cassandra/utils/btree/BTree.java +++ b/src/java/org/apache/cassandra/utils/btree/BTree.java @@ -60,12 +60,6 @@ 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 QUICK_MERGE_LIMIT = Math.min(FAN_FACTOR, 16) * 2; - - // Maximum depth of any B-Tree. In reality this is just an arbitrary limit, and is currently imposed on iterators only, - // but a maximum depth sufficient to store at worst Integer.MAX_VALUE items seems reasonable - // 2^n = (2^k).(2^(n/k)) => 2^31 <= 2^(FAN_SHIFT-1) . 2^ceil(31 / (FAN_SHIFT - 1)) - static final int MAX_DEPTH = (int) Math.ceil(31d / (FAN_SHIFT - 1)); // An empty BTree Leaf - which is the same as an empty BTree static final Object[] EMPTY_LEAF = new Object[0]; @@ -202,7 +196,7 @@ public class BTree */ public static <V> Cursor<V> slice(Object[] btree, boolean forwards) { - Cursor<V> r = Cursor.newCursor(); + Cursor<V> r = new Cursor<>(); r.reset(btree, forwards); return r; } @@ -220,7 +214,7 @@ public class BTree */ public static <V> Cursor<V> slice(Object[] btree, Comparator<V> comparator, V start, V end, boolean forwards) { - Cursor<V> r = Cursor.newCursor(); + Cursor<V> r = new Cursor<>(); r.reset(btree, comparator, start, end, forwards); return r; } @@ -238,7 +232,7 @@ public class BTree */ public static <V> Cursor<V> slice(Object[] btree, Comparator<V> comparator, V start, boolean startInclusive, V end, boolean endInclusive, boolean forwards) { - Cursor<V> r = Cursor.newCursor(); + Cursor<V> r = new Cursor<>(); r.reset(btree, comparator, start, startInclusive, end, endInclusive, forwards); return r; } @@ -342,6 +336,17 @@ public class BTree return tree.length == 0; } + public static int depth(Object[] tree) + { + int depth = 1; + while (!isLeaf(tree)) + { + depth++; + tree = (Object[]) tree[getKeyEnd(tree)]; + } + return depth; + } + // Special class for making certain operations easier, so we can define a +/- Inf private static interface Special extends Comparable<Object> { } static final Special POSITIVE_INFINITY = new Special() http://git-wip-us.apache.org/repos/asf/cassandra/blob/948964b5/src/java/org/apache/cassandra/utils/btree/Cursor.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/utils/btree/Cursor.java b/src/java/org/apache/cassandra/utils/btree/Cursor.java index fba5eec..bc88442 100644 --- a/src/java/org/apache/cassandra/utils/btree/Cursor.java +++ b/src/java/org/apache/cassandra/utils/btree/Cursor.java @@ -21,7 +21,6 @@ package org.apache.cassandra.utils.btree; import java.util.Comparator; import java.util.Iterator; -import static org.apache.cassandra.utils.btree.BTree.MAX_DEPTH; import static org.apache.cassandra.utils.btree.BTree.NEGATIVE_INFINITY; import static org.apache.cassandra.utils.btree.BTree.POSITIVE_INFINITY; import static org.apache.cassandra.utils.btree.BTree.getLeafKeyEnd; @@ -44,20 +43,6 @@ public final class Cursor<V> extends Path implements Iterator<V> * the first one. */ - /** - * Returns a cursor that can be reused to iterate over trees - * - * @param <V> - * @return - */ - static <V> Cursor<V> newCursor() - { - // try to encourage stack allocation - may be misguided. but no harm - Object[][] stack = new Object[MAX_DEPTH][]; - byte[] index = new byte[MAX_DEPTH]; - return new Cursor(stack, index); - } - // the last node covered by the requested range private Object[] endNode; // the index within endNode that signals we're finished -- that is, endNode[endIndex] is NOT part of the Cursor @@ -65,11 +50,6 @@ public final class Cursor<V> extends Path implements Iterator<V> private boolean forwards; - private Cursor(Object[][] stack, byte[] index) - { - super(stack, index); - } - /** * Reset this cursor for the provided tree, to iterate over its entire range * @@ -113,6 +93,7 @@ public final class Cursor<V> extends Path implements Iterator<V> private void _reset(Object[] btree, Comparator<V> comparator, Object lowerBound, boolean inclusiveLowerBound, Object upperBound, boolean inclusiveUpperBound, boolean forwards) { + ensureDepth(btree); if (lowerBound == null) lowerBound = NEGATIVE_INFINITY; if (upperBound == null) @@ -120,7 +101,7 @@ public final class Cursor<V> extends Path implements Iterator<V> this.forwards = forwards; - Path findLast = Path.newPath(); + Path findLast = new Path(this.path.length); if (forwards) { findLast.find(btree, comparator, upperBound, inclusiveUpperBound ? Op.HIGHER : Op.CEIL, true); http://git-wip-us.apache.org/repos/asf/cassandra/blob/948964b5/src/java/org/apache/cassandra/utils/btree/Path.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/utils/btree/Path.java b/src/java/org/apache/cassandra/utils/btree/Path.java index cbdb160..148c713 100644 --- a/src/java/org/apache/cassandra/utils/btree/Path.java +++ b/src/java/org/apache/cassandra/utils/btree/Path.java @@ -20,7 +20,6 @@ package org.apache.cassandra.utils.btree; import java.util.Comparator; -import static org.apache.cassandra.utils.btree.BTree.MAX_DEPTH; import static org.apache.cassandra.utils.btree.BTree.getBranchKeyEnd; import static org.apache.cassandra.utils.btree.BTree.getKeyEnd; import static org.apache.cassandra.utils.btree.BTree.getLeafKeyEnd; @@ -46,25 +45,28 @@ class Path LOWER // the greatest element strictly less than the given element } - static Path newPath() - { - // try to encourage stack allocation - probably misguided/unnecessary. but no harm - Object[][] path = new Object[MAX_DEPTH][]; - byte[] index = new byte[MAX_DEPTH]; - return new Path(path, index); - } - // the path to the searched-for key - final Object[][] path; + Object[][] path; // the index within the node of our path at a given depth - final byte[] indexes; + byte[] indexes; // current depth. nothing in path[i] for i > depth is valid. - byte depth; + byte depth = -1; + + Path() { } + Path(int depth) + { + this.path = new Object[depth][]; + this.indexes = new byte[depth]; + } - Path(Object[][] path, byte[] indexes) + void ensureDepth(Object[] btree) { - this.path = path; - this.indexes = indexes; + int depth = BTree.depth(btree); + if (path == null || path.length < depth) + { + path = new Object[depth][]; + indexes = new byte[depth]; + } } /** http://git-wip-us.apache.org/repos/asf/cassandra/blob/948964b5/test/long/org/apache/cassandra/utils/LongBTreeTest.java ---------------------------------------------------------------------- diff --git a/test/long/org/apache/cassandra/utils/LongBTreeTest.java b/test/long/org/apache/cassandra/utils/LongBTreeTest.java index d3673fa..514d166 100644 --- a/test/long/org/apache/cassandra/utils/LongBTreeTest.java +++ b/test/long/org/apache/cassandra/utils/LongBTreeTest.java @@ -184,7 +184,7 @@ public class LongBTreeTest if (quickEquality) testEqual("", BTree.<Integer>slice(btree, true), canon.keySet().iterator()); else - r.addAll(testAllSlices("RND", btree, canon.navigableKeySet())); + r.addAll(testAllSlices("RND", btree, new TreeSet<>(canon.keySet()))); if (!BTree.isWellFormed(btree)) System.out.println("ERROR: Not well formed");
