This is an automated email from the ASF dual-hosted git repository.
benedict pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/cassandra.git
The following commit(s) were added to refs/heads/trunk by this push:
new 7e32d92d06 Fix/Improve IntervalBTree - Use AsymmetricComparator for
seeking - Reimplement AbstractTransformer for more efficienct operation when
only transforming a subset (i.e. Subtraction) - Reuse source node
IntervalMaxIndex calculations for first branch level (to save iterating leaves)
7e32d92d06 is described below
commit 7e32d92d06c769093c808cd48da51ffb0410d734
Author: Benedict Elliott Smith <[email protected]>
AuthorDate: Mon Jul 7 14:36:15 2025 +0100
Fix/Improve IntervalBTree
- Use AsymmetricComparator for seeking
- Reimplement AbstractTransformer for more efficienct operation when only
transforming a subset (i.e. Subtraction)
- Reuse source node IntervalMaxIndex calculations for first branch level
(to save iterating leaves)
patch by Benedict; reviewed by Alex Petrov for CASSANDRA-20756
---
.../service/accord/CommandsForRanges.java | 65 +-
.../org/apache/cassandra/utils/IntervalTree.java | 2 +-
.../org/apache/cassandra/utils/btree/BTree.java | 749 ++++++++++++---------
.../utils/btree/FullBTreeSearchIterator.java | 5 +-
.../cassandra/utils/btree/IntervalBTree.java | 312 ++++++---
.../org/apache/cassandra/utils/RangeTreeTest.java | 83 +--
.../cassandra/utils/btree/IntervalBTreeTest.java | 159 +++--
.../utils/btree/IntervalTreePerfTest.java | 239 +++++++
8 files changed, 1028 insertions(+), 586 deletions(-)
diff --git
a/src/java/org/apache/cassandra/service/accord/CommandsForRanges.java
b/src/java/org/apache/cassandra/service/accord/CommandsForRanges.java
index f484e9dc9d..aa331fbda4 100644
--- a/src/java/org/apache/cassandra/service/accord/CommandsForRanges.java
+++ b/src/java/org/apache/cassandra/service/accord/CommandsForRanges.java
@@ -48,21 +48,21 @@ import accord.primitives.Txn.Kind.Kinds;
import accord.primitives.TxnId;
import accord.primitives.Unseekable;
import accord.primitives.Unseekables;
+import accord.utils.AsymmetricComparator;
import accord.utils.Invariants;
+import accord.utils.SymmetricComparator;
import accord.utils.UnhandledEnum;
import org.agrona.collections.Object2ObjectHashMap;
import org.apache.cassandra.service.accord.api.TokenKey;
import org.apache.cassandra.utils.btree.IntervalBTree;
import static
accord.local.CommandSummaries.SummaryStatus.NOT_DIRECTLY_WITNESSED;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.intervalEndWithKeyEnd;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.intervalEndWithKeyStart;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.intervalStartWithKeyEnd;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.intervalStartWithKeyStart;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.keyEndWithIntervalEnd;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.keyEndWithIntervalStart;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.keyStartWithIntervalEnd;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.keyStartWithIntervalStart;
+import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndHelper.endWithStart;
+import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndHelper.keyEndWithStart;
+import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndHelper.keyStartWithEnd;
+import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndHelper.keyStartWithStart;
+import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndHelper.startWithEnd;
+import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndHelper.startWithStart;
// TODO (expected): move to accord-core, merge with existing logic there
public class CommandsForRanges extends TreeMap<Timestamp, Summary> implements
CommandSummaries.ByTxnIdSnapshot
@@ -101,47 +101,18 @@ public class CommandsForRanges extends TreeMap<Timestamp,
Summary> implements Co
static class IntervalComparators implements
IntervalBTree.IntervalComparators<TxnIdInterval>
{
@Override public Comparator<TxnIdInterval> totalOrder() { return
TxnIdInterval::compareTo; }
- @Override public Comparator<TxnIdInterval> startWithStartComparator()
{ return (a, b) -> a.start.compareTo(b.start); }
- @Override public Comparator<TxnIdInterval> startWithEndComparator() {
return (a, b) -> a.start.compareTo(b.end); }
- @Override public Comparator<TxnIdInterval> endWithStartComparator() {
return (a, b) -> a.end.compareTo(b.start); }
- @Override public Comparator<TxnIdInterval> endWithEndComparator() {
return (a, b) -> a.end.compareTo(b.end); }
+ @Override public Comparator<TxnIdInterval> endWithEndSorter() { return
(a, b) -> a.end.compareTo(b.end); }
+
+ @Override public SymmetricComparator<TxnIdInterval>
startWithStartSeeker() { return (a, b) ->
startWithStart(a.start.compareTo(b.start)); }
+ @Override public SymmetricComparator<TxnIdInterval>
startWithEndSeeker() { return (a, b) -> startWithEnd(a.start.compareTo(b.end));
}
+ @Override public SymmetricComparator<TxnIdInterval>
endWithStartSeeker() { return (a, b) -> endWithStart(a.end.compareTo(b.start));
}
}
- static class IntervalKeyComparators implements
IntervalBTree.IntervalComparators<Object>
+ static class IntervalKeyComparators implements
IntervalBTree.WithIntervalComparators<RoutingKey, TxnIdInterval>
{
- @Override public Comparator<Object> totalOrder() { throw new
UnsupportedOperationException(); }
-
- @Override
- public Comparator<Object> startWithStartComparator()
- {
- return (a, b) -> a.getClass() == TxnIdInterval.class
- ? intervalStartWithKeyStart(((TxnIdInterval)
a).start.compareTo((RoutingKey)b))
- :
keyStartWithIntervalStart(((RoutingKey)a).compareTo(((TxnIdInterval)b).start));
- }
-
- @Override
- public Comparator<Object> startWithEndComparator()
- {
- return (a, b) -> a.getClass() == TxnIdInterval.class
- ?
intervalStartWithKeyEnd(((TxnIdInterval)a).start.compareTo((RoutingKey)b))
- :
keyStartWithIntervalEnd(((RoutingKey)a).compareTo(((TxnIdInterval)b).end));
- }
-
- @Override
- public Comparator<Object> endWithStartComparator()
- {
- return (a, b) -> a.getClass() == TxnIdInterval.class
- ?
intervalEndWithKeyStart(((TxnIdInterval)a).end.compareTo((RoutingKey)b))
- :
keyEndWithIntervalStart(((RoutingKey)a).compareTo(((TxnIdInterval)b).start));
- }
-
- @Override
- public Comparator<Object> endWithEndComparator()
- {
- return (a, b) -> a.getClass() == TxnIdInterval.class
- ?
intervalEndWithKeyEnd(((TxnIdInterval)a).end.compareTo((RoutingKey)b))
- :
keyEndWithIntervalEnd(((RoutingKey)a).compareTo(((TxnIdInterval)b).end));
- }
+ @Override public AsymmetricComparator<RoutingKey, TxnIdInterval>
startWithStartSeeker() { return (a, b) ->
keyStartWithStart(a.compareTo(b.start));}
+ @Override public AsymmetricComparator<RoutingKey, TxnIdInterval>
startWithEndSeeker() { return (a, b) -> keyStartWithEnd(a.compareTo(b.end)); }
+ @Override public AsymmetricComparator<RoutingKey, TxnIdInterval>
endWithStartSeeker() { return (a, b) -> keyEndWithStart(a.compareTo(b.start)); }
}
public CommandsForRanges(Map<? extends Timestamp, ? extends Summary> m)
@@ -224,7 +195,7 @@ public class CommandsForRanges extends TreeMap<Timestamp,
Summary> implements Co
case 1: return IntervalBTree.singleton(new
TxnIdInterval(route.get(0), txnId));
default:
{
- try (IntervalBTree.FastInteralTreeBuilder<TxnIdInterval>
builder = IntervalBTree.fastBuilder(COMPARATORS.endWithEndComparator()))
+ try (IntervalBTree.FastIntervalTreeBuilder<TxnIdInterval>
builder = IntervalBTree.fastBuilder(COMPARATORS))
{
for (int i = 0 ; i < size ; ++i)
builder.add(new TxnIdInterval(route.get(i),
txnId));
diff --git a/src/java/org/apache/cassandra/utils/IntervalTree.java
b/src/java/org/apache/cassandra/utils/IntervalTree.java
index 03848a4147..e1527bf377 100644
--- a/src/java/org/apache/cassandra/utils/IntervalTree.java
+++ b/src/java/org/apache/cassandra/utils/IntervalTree.java
@@ -75,7 +75,7 @@ public class IntervalTree<C extends Comparable<? super C>, D
extends Comparable<
private final I[] intervalsByMaxOrder;
@SuppressWarnings("unchecked")
- protected IntervalTree(Collection<I> intervals)
+ public IntervalTree(Collection<I> intervals)
{
this.modCount = 0;
if (intervals == null || intervals.isEmpty())
diff --git a/src/java/org/apache/cassandra/utils/btree/BTree.java
b/src/java/org/apache/cassandra/utils/btree/BTree.java
index 08372f26a5..a8de1162ce 100644
--- a/src/java/org/apache/cassandra/utils/btree/BTree.java
+++ b/src/java/org/apache/cassandra/utils/btree/BTree.java
@@ -24,6 +24,8 @@ import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;
+import javax.annotation.Nullable;
+
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Preconditions;
import com.google.common.collect.Iterators;
@@ -41,6 +43,7 @@ import org.apache.cassandra.utils.caching.TinyThreadLocalPool;
import static java.lang.Math.max;
import static java.lang.Math.min;
import static
org.apache.cassandra.config.CassandraRelevantProperties.BTREE_BRANCH_SHIFT;
+import static org.apache.cassandra.utils.btree.BTree.Dir.ASC;
public class BTree
{
@@ -576,7 +579,7 @@ public class BTree
public static <V> Iterator<V> iterator(Object[] btree)
{
- return iterator(btree, Dir.ASC);
+ return iterator(btree, ASC);
}
public static <V> Iterator<V> iterator(Object[] btree, Dir dir)
@@ -593,7 +596,7 @@ public class BTree
public static <V> Iterable<V> iterable(Object[] btree)
{
- return iterable(btree, Dir.ASC);
+ return iterable(btree, ASC);
}
public static <V> Iterable<V> iterable(Object[] btree, Dir dir)
@@ -2339,6 +2342,8 @@ public class BTree
final LeafOrBranchBuilder child;
BranchBuilder parent;
+ @Nullable Object[] sourceNode;
+
/**
* The current buffer contents (if any) of the leaf or branch - always
sized to contain a complete
* node of the form being constructed. Always non-null, except
briefly during overflow.
@@ -2369,6 +2374,16 @@ public class BTree
this.child = child;
}
+ void setSourceNode(Object[] sourceNode)
+ {
+ this.sourceNode = sourceNode;
+ }
+
+ void clearSourceNode()
+ {
+ this.sourceNode = null;
+ }
+
/**
* Do we have enough keys in the builder to construct at least one
balanced node?
* We could have enough to build two.
@@ -2405,6 +2420,8 @@ public class BTree
return count == 0 && savedNextKey == null;
}
+ abstract void initialiseCopy(Object[] unode);
+
/**
* Drain the contents of this builder and build up to two nodes, as
necessary.
* If {@code unode != null} and we are building a single node that is
identical to it, use {@code unode} instead.
@@ -2412,7 +2429,9 @@ public class BTree
*
* @return the last node we construct
*/
- abstract Object[] drainAndPropagate(Object[] unode, BranchBuilder
propagateTo);
+ abstract Object[] drainAndPropagate(BranchBuilder propagateTo);
+
+ abstract void addKey(Object key);
/**
* Drain the contents of this builder and build at most one node.
@@ -2437,7 +2456,7 @@ public class BTree
return level.drain();
BranchBuilder parent = level.ensureParent();
- level.drainAndPropagate(null, parent);
+ level.drainAndPropagate(parent);
if (level.savedBuffer != null)
Arrays.fill(level.savedBuffer, null);
level = parent;
@@ -2541,7 +2560,8 @@ public class BTree
/**
* Add {@code nextKey} to the buffer, overflowing if necessary
*/
- public void addKey(Object nextKey)
+ @Override
+ final void addKey(Object nextKey)
{
if (count == MAX_KEYS)
overflow(nextKey);
@@ -2549,6 +2569,16 @@ public class BTree
buffer[count++] = nextKey;
}
+ final void setSourceNode(Object[] sourceNode)
+ {
+ super.setSourceNode(sourceNode);
+ }
+
+ final void clearSourceNode()
+ {
+ super.clearSourceNode();
+ }
+
/**
* Add {@code nextKey} to the buffer; the caller specifying overflow
is unnecessary
*/
@@ -2583,6 +2613,14 @@ public class BTree
}
}
+ void initialiseCopy(Object[] copy)
+ {
+ Invariants.require(isEmpty());
+ setSourceNode(copy);
+ count = sizeOfLeaf(copy);
+ System.arraycopy(copy, 0, buffer, 0, count);
+ }
+
/**
* Copy the contents of {@code source[from..to)} to {@code buffer},
overflowing as necessary.
*/
@@ -2762,7 +2800,7 @@ public class BTree
* This is only called when we have enough data to complete the node,
i.e. we have MIN_KEYS or more items added
* or the node is the BTree's root.
*/
- Object[] drainAndPropagate(Object[] unode, BranchBuilder propagateTo)
+ Object[] drainAndPropagate(BranchBuilder propagateTo)
{
Object[] leaf;
int sizeOfLeaf;
@@ -2772,10 +2810,11 @@ public class BTree
leaf = redistributeOverflowAndDrain();
sizeOfLeaf = MIN_KEYS;
}
- else if (!hasOverflow() && unode != null && count ==
sizeOfLeaf(unode) && areIdentical(buffer, 0, unode, 0, count))
+ else if (!hasOverflow() && sourceNode != null && count ==
sizeOfLeaf(sourceNode) && areIdentical(buffer, 0, sourceNode, 0, count))
{
// we have exactly the same contents as the original node, so
reuse it
- leaf = unode;
+ Invariants.require(sourceNode != null);
+ leaf = sourceNode;
sizeOfLeaf = count;
}
else
@@ -2787,10 +2826,11 @@ public class BTree
sizeOfLeaf = count;
leaf = drain();
if (allocated >= 0 && sizeOfLeaf > 0)
- allocated += ObjectSizes.sizeOfReferenceArray(sizeOfLeaf |
1) - (unode == null ? 0 : sizeOnHeapOfLeaf(unode));
+ allocated += ObjectSizes.sizeOfReferenceArray(sizeOfLeaf |
1) - (sourceNode == null ? 0 : sizeOnHeapOfLeaf(sourceNode));
}
count = 0;
+ clearSourceNode();
if (propagateTo != null)
propagateTo.addChild(leaf, sizeOfLeaf);
return leaf;
@@ -2806,9 +2846,20 @@ public class BTree
if (count == 0)
return empty();
- Object[] newLeaf = new Object[count | 1];
- System.arraycopy(buffer, 0, newLeaf, 0, count);
+ Object[] newLeaf;
+ if (sourceNode != null
+ && count == sizeOfLeaf(sourceNode)
+ && areIdentical(buffer, 0, sourceNode, 0, count))
+ {
+ newLeaf = sourceNode;
+ }
+ else
+ {
+ newLeaf = new Object[count | 1];
+ System.arraycopy(buffer, 0, newLeaf, 0, count);
+ }
count = 0;
+ clearSourceNode();
return newLeaf;
}
}
@@ -2816,6 +2867,7 @@ public class BTree
static class BranchBuilder extends LeafOrBranchBuilder
{
final LeafBuilder leaf;
+ boolean hasRightChild;
/**
* sizes of the children in {@link #buffer}. If null, we only produce
dense nodes.
@@ -2843,8 +2895,11 @@ public class BTree
* Ensure there is room to add another key to {@code
branchBuffers[branchIndex]}, and add it;
* invoke {@link #overflow} if necessary
*/
- void addKey(Object key)
+ @Override
+ final void addKey(Object key)
{
+ Invariants.require(hasRightChild);
+ hasRightChild = false;
if (count == MAX_KEYS)
overflow(key);
else
@@ -2855,9 +2910,12 @@ public class BTree
* To be invoked when there's a key already inserted to the buffer
that requires a corresponding
* right-hand child, for which the buffers are sized to ensure there
is always room.
*/
- void addChild(Object[] child, int sizeOfChild)
+ final void addChild(Object[] child, int sizeOfChild)
{
+ Invariants.require(child != null);
+ Invariants.require(!hasRightChild);
buffer[MAX_KEYS + count] = child;
+ hasRightChild = true;
recordSizeOfChild(sizeOfChild);
}
@@ -2867,10 +2925,20 @@ public class BTree
sizes[count] = sizeOfChild;
}
+ final void initialiseCopy(Object[] copy)
+ {
+ Invariants.require(isEmpty());
+ setSourceNode(copy);
+ count = shallowSizeOfBranch(copy);
+ hasRightChild = true;
+ System.arraycopy(copy, 0, buffer, 0, count);
+ System.arraycopy(copy, count, buffer, MAX_KEYS, count + 1);
+ }
+
/**
* See {@link BranchBuilder#addChild(Object[], int)}
*/
- void addChild(Object[] child)
+ final void addChild(Object[] child)
{
addChild(child, sizes == null ? 0 : size(child));
}
@@ -2878,19 +2946,16 @@ public class BTree
/**
* Insert a new child into a parent branch, when triggered by {@code
overflowLeaf} or {@code overflowBranch}
*/
- void addChildAndNextKey(Object[] newChild, int newChildSize, Object
nextKey)
+ final void addChildAndNextKey(Object[] newChild, int newChildSize,
Object nextKey)
{
- // we should always have room for a child to the right of any key
we have previously inserted
- buffer[MAX_KEYS + count] = newChild;
- recordSizeOfChild(newChildSize);
- // but there may not be room for another key
+ addChild(newChild, newChildSize);
addKey(nextKey);
}
/**
* Invoked when we want to add a key to the leaf buffer, but it is full
*/
- void propagateOverflow()
+ final void propagateOverflow()
{
// propagate the leaf we have saved in leaf().savedBuffer
if (leaf.allocated >= 0)
@@ -2908,6 +2973,8 @@ public class BTree
*/
void overflow(Object nextKey)
{
+ Invariants.require(!hasRightChild);
+
if (hasOverflow())
propagateOverflow();
@@ -3027,8 +3094,9 @@ public class BTree
* This is only called when we have enough data to complete the node,
i.e. we have MIN_KEYS or more items added
* or the node is the BTree's root.
*/
- Object[] drainAndPropagate(Object[] unode, BranchBuilder propagateTo)
+ Object[] drainAndPropagate(BranchBuilder propagateTo)
{
+ Invariants.require(hasRightChild);
int sizeOfBranch;
Object[] branch;
if (mustRedistribute())
@@ -3038,6 +3106,7 @@ public class BTree
}
else
{
+ Object[] unode = sourceNode;
int usz = unode != null ? shallowSizeOfBranch(unode) : -1;
if (!hasOverflow() && usz == count
&& areIdentical(buffer, 0, unode, 0, usz)
@@ -3053,7 +3122,7 @@ public class BTree
// the number of children here may be smaller than
MIN_KEYS if this is the root node, but there must
// be at least one key / two children.
- assert count > 0;
+ Invariants.require(count > 0);
branch = new Object[2 * (count + 1)];
System.arraycopy(buffer, 0, branch, 0, count);
System.arraycopy(buffer, MAX_KEYS, branch, count, count +
1);
@@ -3062,6 +3131,8 @@ public class BTree
}
count = 0;
+ hasRightChild = false;
+ clearSourceNode();
if (propagateTo != null)
propagateTo.addChild(branch, sizeOfBranch);
@@ -3073,23 +3144,43 @@ public class BTree
*/
Object[] drain()
{
+ Invariants.require(hasRightChild);
assert !hasOverflow();
- int keys = count;
- count = 0;
+ if (count == 0)
+ {
+ clearSourceNode();
+ hasRightChild = false;
+ return (Object[]) buffer[MAX_KEYS];
+ }
- Object[] branch = new Object[2 * (keys + 1)];
- if (keys == MAX_KEYS)
+ Object[] branch;
+ if (sourceNode != null
+ && count == shallowSizeOfBranch(sourceNode)
+ && areIdentical(buffer, 0, sourceNode, 0, count)
+ && areIdentical(buffer, MAX_KEYS, sourceNode, count, count +
1))
{
- Object[] tmp = buffer;
- buffer = branch;
- branch = tmp;
+ branch = sourceNode;
}
else
{
- System.arraycopy(buffer, 0, branch, 0, keys);
- System.arraycopy(buffer, MAX_KEYS, branch, keys, keys + 1);
+ branch = new Object[2 * (count + 1)];
+ if (count == MAX_KEYS)
+ {
+ Object[] tmp = buffer;
+ buffer = branch;
+ branch = tmp;
+ }
+ else
+ {
+ System.arraycopy(buffer, 0, branch, 0, count);
+ System.arraycopy(buffer, MAX_KEYS, branch, count, count +
1);
+ }
+ setDrainSizeMap(null, -1, branch, count);
}
- setDrainSizeMap(null, -1, branch, keys);
+
+ count = 0;
+ hasRightChild = false;
+ clearSourceNode();
return branch;
}
@@ -3198,6 +3289,7 @@ public class BTree
*/
void copyPreceding(Object[] unode, int usz, int offset, int length)
{
+ Invariants.require(!hasRightChild);
int[] uszmap = sizeMap(unode);
if (count + length > MAX_KEYS)
{
@@ -3227,6 +3319,7 @@ public class BTree
*/
private void copyPrecedingNoOverflow(Object[] unode, int usz, int[]
uszmap, int offset, int length)
{
+ Invariants.require(!hasRightChild);
if (length <= 1)
{
if (length == 0)
@@ -3266,7 +3359,9 @@ public class BTree
{
Arrays.fill(buffer, null);
count = 0;
+ hasRightChild = false;
inUse = false;
+ clearSourceNode();
}
}
@@ -3400,7 +3495,7 @@ public class BTree
BranchBuilder branch = leaf().parent;
while (branch != null && branch.inUse)
{
- assert branch.count == 0;
+ branch.count = 0;
clearBranchBuffer(branch.buffer);
if (branch.savedBuffer != null && branch.savedBuffer[0] !=
null)
Arrays.fill(branch.savedBuffer, null); // by definition
full, if non-empty
@@ -3546,8 +3641,9 @@ public class BTree
{
// ik fall inside it -- recursively merge the child with
the update, using next key as an upper bound
LeafOrBranchBuilder childBuilder = builder.child;
+ childBuilder.setSourceNode(childUNode);
ik = updateRecursive(ik, childUNode, nextUKey,
childBuilder);
- childBuilder.drainAndPropagate(childUNode, builder);
+ childBuilder.drainAndPropagate(builder);
if (find == usz) // this was the right-most child,
branch is complete and we can return immediately
return ik;
c = ik != null ? comparator.compare(nextUKey, ik) : -1;
@@ -3633,7 +3729,6 @@ public class BTree
return ik;
}
-
public void close()
{
reset();
@@ -3669,184 +3764,176 @@ public class BTree
* <p>
* The approach taken here hopefully balances simplicity, garbage
generation and execution time.
*/
- static abstract class AbstractTransformer<I, O> extends AbstractUpdater
implements AutoCloseable
+ static abstract class AbstractSeekingTransformer<I, O> extends
AbstractUpdater implements AutoCloseable
{
/**
* An iterator over the tree we are updating
*/
final SimpleTreeIterator update = new SimpleTreeIterator();
- /**
- * A queue of nodes from update that we are ready to "finish" if we
have buffered enough data from them
- * The stack pointer is maintained inside of {@link #apply()}
- */
- Object[][] queuedToFinish = new Object[1][];
-
- AbstractTransformer()
+ AbstractSeekingTransformer()
{
allocated = -1;
ensureParent();
parent.inUse = false;
}
- abstract O apply(I v);
+ abstract O apply(I in);
- Object[] apply(Object[] update)
+ LeafOrBranchBuilder initRoot(Object[] root)
{
- int height = this.update.init(update);
- if (queuedToFinish.length < height - 1)
- queuedToFinish = new Object[height - 1][];
- return apply();
+ int height = this.update.initToRoot(root);
+ LeafOrBranchBuilder level = leaf();
+ for (int d = 1; d < height; ++d)
+ level = level.ensureParent();
+ level.setSourceNode(root);
+ return level;
}
+ // for branch nodes, can seek to usz+1 indicating we should ascend
+ abstract int seekInBranch(Object[] unode, int upos, int usz);
+ // transform the leaf - false means we should directly propagate the
leaf to its parent
+ protected abstract boolean transformLeaf(Object[] unode, int upos, int
usz);
+
/**
* We base our operation on the shape of {@code update}, trying to
steal as much of the original tree as
* possible for our new tree
*/
- private Object[] apply()
+ Object[] apply(Object[] root)
{
+ LeafOrBranchBuilder level = initRoot(root);
Object[] unode = update.node();
- int upos = update.position(), usz = sizeOfLeaf(unode);
+ int upos = update.position(), usz = shallowSize(unode);
- while (true)
+ descend: while (true)
{
- // we always start the loop on a leaf node, for both input and
output
- boolean propagatedOriginalLeaf = false;
- if (leaf().count == 0)
+ // navigate to the highest level that may need transforming
+ if (level == leaf())
{
- if (upos == 0)
- { // fast path - buffer is empty and input unconsumed,
so may be able to propagate original
- I in;
- O out;
- do
- { // optimistic loop - find first point the
transformation modified our input
- in = (I) unode[upos];
- out = apply(in);
- } while (in == out && ++upos < usz);
+ Invariants.require(level.sourceNode == unode);
+ if (transformLeaf(unode, upos, usz)) upos = usz;
+ else
+ {
+ if (!update.ascendToParent())
+ return unode;
- if ((propagatedOriginalLeaf = (upos == usz)))
- {
- // if input is unmodified by transformation,
propagate the input node
- markUsed(parent).addChild(unode, usz);
- }
- else
- {
- // otherwise copy up to the first modified portion,
- // and fall-through to our below condition for
transforming the remainder
- leaf().copyNoOverflow(unode, 0, upos++);
- if (out != null)
- leaf().addKeyNoOverflow(out);
- }
+ markUsed(parent).addChild(unode, usz);
+ level.clearSourceNode();
+ level = level.parent;
+ unode = update.node();
+ upos = update.position();
+ usz = shallowSizeOfBranch(unode);
}
-
- if (!propagatedOriginalLeaf)
- transformLeafNoOverflow(unode, upos, usz);
}
else
{
- transformLeaf(unode, upos, usz);
- }
-
- // we've finished a leaf, and have to hand it to a parent
alongside its right-hand key
- // so now we try to do two things:
- // 1) find the next unfiltered key from our unfinished
parent
- // 2) determine how many parents are "finished" and whose
buffers we should also attempt to propagate
- // we do (1) unconditionally, because:
- // a) we need to handle the branch keys somewhere, and it
may as well happen in one place
- // b) we either need more keys for our incomplete leaf; or
- // c) we need a key to go after our last propagated node in
any unfinished parent
-
- int finishToHeight = 0;
- O nextKey;
- do
- {
- update.ascendToParent(); // always have a node above leaf
level, else we'd invoke transformLeaf
- BranchBuilder level = parent;
- unode = update.node();
- upos = update.position();
- usz = shallowSizeOfBranch(unode);
-
- while (upos == usz)
+ BranchBuilder branch = (BranchBuilder) level;
+ int pos = seekInBranch(unode, upos, usz);
+ if (pos < 0)
{
- queuedToFinish[level.height - 2] = unode;
- finishToHeight = max(finishToHeight, level.height);
+ pos = -1 -pos;
+ boolean done = pos > usz;
+ if (done)
+ pos = usz;
- if (!update.ascendToParent())
- return finishAndDrain(propagatedOriginalLeaf);
+ if (pos > upos)
+ {
+ branch.copyPreceding(unode, usz, upos, pos - upos);
+ upos = pos;
+ }
- level = level.ensureParent();
+ update.descend(unode, upos, usz);
unode = update.node();
upos = update.position();
- usz = shallowSizeOfBranch(unode);
+ usz = shallowSize(unode);
+ level = level.child;
+ level.setSourceNode(unode);
+ continue;
}
+ else
+ {
+ if (pos > upos)
+ {
+ branch.copyPreceding(unode, usz, upos, pos - upos);
+ upos = pos;
+ }
+ }
+ Invariants.require(branch.child.isEmpty());
+ branch.addChild((Object[]) unode[usz + upos]);
+ }
- nextKey = apply((I) unode[upos]);
- if (nextKey == null && leaf().count > MIN_KEYS) // if we
don't have a key, try to steal from leaf().buffer
- nextKey = (O) leaf().buffer[--leaf().count];
+ LeafOrBranchBuilder incomplete = level;
+ while (upos >= usz)
+ {
+ if (!update.ascendToParent())
+ return finishAndDrain(level);
- update.descendIntoNextLeaf(unode, upos, usz);
unode = update.node();
upos = update.position();
- usz = sizeOfLeaf(unode);
-
- // nextKey might have been filtered, so we may need to
look in this next leaf for it
- while (nextKey == null && upos < usz)
- nextKey = apply((I) unode[upos++]);
-
- // if we still found no key loop and try again on the next
parent, leaf, parent... ad infinitum
- } while (nextKey == null);
-
- // we always end with unode a leaf, though it may be that upos
== usz and that we will do nothing with it
-
- // we've found a non-null key, now decide what to do with it:
- // 1) if we have insufficient keys in our leaf, simply
append to the leaf and continue;
- // 2) otherwise, walk our parent branches finishing those
*before* {@code finishTo}
- // 2a) if any cannot be finished, append our new key to it
and stop finishing further parents; they
- // will be finished the next time we ascend to their level
with a complete chain of finishable branches
- // 2b) otherwise, add our new key to {@code finishTo}
+ usz = shallowSizeOfBranch(unode);
- if (!propagatedOriginalLeaf && !finish(leaf(), null))
- {
- leaf().addKeyNoOverflow(nextKey);
- continue;
+ if (incomplete == level && finish(level))
+ incomplete = level.parent;
+ level = level.parent;
}
- BranchBuilder finish = parent;
- while (true)
+ O next = apply((I) unode[upos++]);
+ if (next == null)
{
- if (finish.height <= finishToHeight)
+ // next has been filtered, so look for the (unfiltered)
successor node
+ successor: while (true)
{
- Object[] originalNode = queuedToFinish[finish.height -
2];
- if (finish(finish, originalNode))
+ level = descend(level, leaf(), unode, upos, usz);
+ unode = update.node();
+ upos = update.position();
+ usz = sizeOfLeaf(unode);
+
+ while (upos < usz)
{
- finish = finish.parent;
- continue;
+ if (null != (next = apply((I)unode[upos++])))
+ break successor;
}
- }
- // add our key to the last unpropagated parent branch
buffer
- finish.addKey(nextKey);
- break;
+ do
+ {
+ if (!update.ascendToParent())
+ return finishAndDrain(level);
+
+ unode = update.node();
+ upos = update.position();
+ usz = shallowSizeOfBranch(unode);
+ level = level.parent;
+ } while (upos >= usz);
+
+ next = apply((I) unode[upos++]);
+ if (next != null)
+ break;
+ }
}
- }
- }
- private void transformLeafNoOverflow(Object[] unode, int upos, int usz)
- {
- while (upos < usz)
- {
- O v = apply((I) unode[upos++]);
- leaf().maybeAddKeyNoOverflow(v);
+ incomplete.addKey(next);
+ if (level.height > incomplete.height)
+ {
+ level = descend(level, incomplete, unode, upos, usz);
+ unode = update.node();
+ upos = update.position();
+ usz = shallowSize(unode);
+ }
}
}
- private void transformLeaf(Object[] unode, int upos, int usz)
+ LeafOrBranchBuilder descend(LeafOrBranchBuilder from,
LeafOrBranchBuilder to, Object[] unode, int upos, int usz)
{
- while (upos < usz)
+ while (update.height() > to.height)
{
- O v = apply((I) unode[upos++]);
- leaf().maybeAddKey(v);
+ update.descend(unode, upos, usz);
+ unode = update.node();
+ upos = update.position();
+ usz = shallowSize(unode);
+ from = from.child;
+ from.setSourceNode(unode);
}
+ return to;
}
/**
@@ -3854,12 +3941,12 @@ public class BTree
* we refuse to construct a leaf and return null. Otherwise we
propagate the branch to its parent's buffer
* and return the branch we have constructed.
*/
- final boolean finish(LeafOrBranchBuilder level, Object[] unode)
+ final boolean finish(LeafOrBranchBuilder level)
{
if (!level.isSufficient())
return false;
- level.drainAndPropagate(unode, level.ensureParent());
+ level.drainAndPropagate(level.ensureParent());
return true;
}
@@ -3871,16 +3958,56 @@ public class BTree
* does not, we recursively apply the stealing procedure to obtain a
non-empty parent. If this process manages
* to reach the root and still find no preceding branch, this will
result in making this branch the new root.
*/
- final Object[] finishAndDrain(boolean skipLeaf)
+ final Object[] finishAndDrain(LeafOrBranchBuilder root)
{
- LeafOrBranchBuilder level = leaf();
- if (skipLeaf)
+ if (root == leaf())
+ return root.completeBuild();
+
+ BranchBuilder branch = (BranchBuilder) root;
+ // the logic after this loop expects that all builders are
populated and have the same number of keys as children
+ // so this loop simply checks to see if we can build without any
rebalancing,
+ // stopping at the first balanced (hasRightChild) and sufficient
for building branch.
+ // Otherwise it un
+ while (true)
{
- level = nonEmptyParentMaybeSteal(level);
- // handle an edge case, where we have propagated a single
complete leaf but have no other contents in any parent
- if (level == null)
- return (Object[]) leaf().parent.buffer[MAX_KEYS];
+ if (branch.hasRightChild)
+ {
+ for (LeafOrBranchBuilder child = branch.child ; child !=
null ; child = child.child)
+ Invariants.require(child.isEmpty());
+
+ boolean isSufficient = true;
+ for (BranchBuilder b = branch ; b != root && isSufficient
; b = b.parent)
+ isSufficient = b.isSufficient();
+
+ if (isSufficient)
+ {
+ for (BranchBuilder b = branch ; b != root ; b =
b.parent)
+ b.drainAndPropagate(b.parent);
+ return root.completeBuild();
+ }
+ else
+ {
+ while (true)
+ {
+ Object[] rightChild = (Object[])
branch.buffer[MAX_KEYS + branch.count];
+ branch.hasRightChild = false;
+ branch.child.initialiseCopy(rightChild);
+
+ if (branch.child == leaf())
+ break;
+ branch = (BranchBuilder) branch.child;
+ }
+ }
+ break;
+ }
+
+ if (branch.child == leaf())
+ break;
+
+ branch = (BranchBuilder) branch.child;
}
+
+ LeafOrBranchBuilder level = leaf();
while (true)
{
BranchBuilder parent = nonEmptyParentMaybeSteal(level);
@@ -3892,9 +4019,7 @@ public class BTree
}
else
{
-
- Object[] originalNode = level == leaf() ? null :
queuedToFinish[level.height - 2];
- Object[] result = level.drainAndPropagate(originalNode,
parent);
+ Object[] result = level.drainAndPropagate(parent);
if (parent == null)
return result;
}
@@ -3934,7 +4059,7 @@ public class BTree
if (exhausted)
return fill.drain();
- fill.drainAndPropagate(null, parent);
+ fill.drainAndPropagate(parent);
return null;
}
@@ -3982,7 +4107,6 @@ public class BTree
void reset()
{
- Arrays.fill(queuedToFinish, 0, update.leafDepth, null);
update.reset();
super.reset();
}
@@ -3990,8 +4114,10 @@ public class BTree
/**
* Implement set subtraction/difference using a modified version of the
Transformer logic
+ *
+ * TODO (desired): merge with Transformer
*/
- static abstract class Subtraction<K, T extends K> extends
AbstractTransformer<T, T> implements AutoCloseable
+ static abstract class AbstractSubtraction<K, T extends K> extends
AbstractSeekingTransformer<T, T> implements AutoCloseable
{
/**
* An iterator over the tree we are updating
@@ -3999,187 +4125,119 @@ public class BTree
PeekingSearchIterator<K, ? extends K> remove;
Comparator<K> comparator;
- Object[] apply(Object[] update, PeekingSearchIterator<K, ? extends K>
remove)
+ Object[] subtract(Object[] update, PeekingSearchIterator<K, ? extends
K> remove)
{
- int height = this.update.init(update);
this.remove = remove;
- if (queuedToFinish.length < height - 1)
- queuedToFinish = new Object[height - 1][];
- return apply();
+ return apply(update);
+ }
+
+ Object[] subtract(Object[] update, Object[] remove)
+ {
+ return subtract(update, slice(remove, comparator, ASC));
}
@Override
T apply(T v)
{
- throw new UnsupportedOperationException();
+ return remove.next(v) == null ? v : null;
}
- /**
- * We base our operation on the shape of {@code update}, trying to
steal as much of the original tree as
- * possible for our new tree
- */
- private Object[] apply()
+ @Override
+ int seekInBranch(Object[] unode, int upos, int usz)
{
- Object[] unode = update.node();
- int upos = update.position(), usz = sizeOfLeaf(unode);
- while (true)
- {
- // we always start the loop on a leaf node, for both input and
output
- boolean propagatedOriginalLeaf = false;
- if (leaf().count == 0 && upos == 0)
- {
- int prev = 0;
- if (!remove.hasNext() || comparator.compare((K)unode[usz -
1], remove.peek()) < 0)
- {
- // short-circuit common case of removal not
intersecting the current node, by comparing with last key
- upos = usz;
- }
+ if (!remove.hasNext())
+ return -1 - (1 + usz);
- while (upos < usz)
- {
- // fast path - buffer is empty and input unconsumed,
so may be able to propagate original
- if (null == remove.next((T)unode[upos]))
- {
- if (!remove.hasNext())
- break;
- upos = exponentialSearch(comparator, unode, upos +
1, usz, remove.peek());
- if (upos < 0)
- {
- upos = -1 - upos;
- continue;
- }
- }
-
- leaf().copyNoOverflow(unode, prev, upos - prev);
- ++upos;
- prev = upos;
- }
- if (propagatedOriginalLeaf = (prev == 0))
- {
- // if input is unmodified by transformation, propagate
the input node
- markUsed(parent).addChild(unode, usz);
- }
- else
- {
- leaf().copyNoOverflow(unode, prev, usz - prev);
- }
- }
- else
+ int i = exponentialSearch(comparator, unode, upos, usz,
remove.peek());
+ if (i == -1 - usz)
+ {
+ // if we sort after the last key in the branch, we may need to
descend into the right-most child
+ // but, for all branches besides the root we can try to look
at a parent node to decide this.
+ // we only look at the direct parent, and if we are its
right-most child already, we just assume we must descend
+ int pdepth = update.depth - 1;
+ if (pdepth >= 0)
{
- int prev = upos;
- while (upos < usz)
+ Object[] pnode = update.nodes[pdepth];
+ int ppos = update.positions[pdepth];
+ if (ppos < shallowSizeOfBranch(pnode) &&
comparator.compare(remove.peek(), (K)pnode[ppos]) >= 0)
{
- if (null == remove.next((T)unode[upos]))
- {
- if (!remove.hasNext())
- break;
- upos = exponentialSearch(comparator, unode, upos +
1, usz, remove.peek());
- if (upos < 0)
- {
- upos = -1 - upos;
- continue;
- }
- }
-
- leaf().copy(unode, prev, upos - prev);
- ++upos;
- prev = upos;
+ // increase our result index to point to *after* the
last child;
+ // (it's an inequality binary search semantic answer,
so will be negated)
+ --i;
}
- leaf().copy(unode, prev, usz - prev);
}
+ }
+ return i;
+ }
- // we've finished a leaf, and have to hand it to a parent
alongside its right-hand key
- // so now we try to do two things:
- // 1) find the next unfiltered key from our unfinished
parent
- // 2) determine how many parents are "finished" and whose
buffers we should also attempt to propagate
- // we do (1) unconditionally, because:
- // a) we need to handle the branch keys somewhere, and it
may as well happen in one place
- // b) we either need more keys for our incomplete leaf; or
- // c) we need a key to go after our last propagated node in
any unfinished parent
-
- int finishToHeight = 0;
- T next;
- do
+ @Override
+ protected boolean transformLeaf(Object[] unode, int upos, int usz)
+ {
+ int prev = upos;
+ if (remove.hasNext())
+ {
+ while (true)
{
- if (!update.ascendToParent())
- return finishAndDrain(propagatedOriginalLeaf);
-
- BranchBuilder level = parent;
- unode = update.node();
- upos = update.position();
- usz = shallowSizeOfBranch(unode);
-
- while (upos == usz)
+ // fast path - buffer is empty and input unconsumed, so
may be able to propagate original
+ upos = exponentialSearch(comparator, unode, upos, usz,
remove.peek());
+ if (upos < 0)
{
- queuedToFinish[level.height - 2] = unode;
- finishToHeight = max(finishToHeight, level.height);
-
- if (!update.ascendToParent())
- return finishAndDrain(propagatedOriginalLeaf);
-
- level = level.ensureParent();
- unode = update.node();
- upos = update.position();
- usz = shallowSizeOfBranch(unode);
+ upos = -1 - upos;
+ if (upos == usz)
+ break;
+ remove.next();
+ if (remove.hasNext()) continue;
+ else break;
}
- next = (T) unode[upos];
- if (null != remove.next(next))
- next = null;
-
- update.descendIntoNextLeaf(unode, upos, usz);
- unode = update.node();
- upos = update.position();
- usz = sizeOfLeaf(unode);
-
- // nextKey might have been filtered, so we may need to
look in this next leaf for it
- while (next == null && upos < usz)
- {
- next = (T)unode[upos++];
- if (null != remove.next(next))
- next = null;
- }
+ leaf().copy(unode, prev, upos - prev);
+ ++upos;
+ prev = upos;
+ remove.next();
+ if (!remove.hasNext())
+ break;
+ }
+ }
- // if we still found no key loop and try again on the next
parent, leaf, parent... ad infinitum
- } while (next == null);
+ if (prev == 0 && leaf().isEmpty())
+ // if input is unmodified by transformation, propagate the
input node
+ return false;
- // we always end with unode a leaf, though it may be that upos
== usz and that we will do nothing with it
+ leaf().copy(unode, prev, usz - prev);
+ return true;
+ }
+ }
- // we've found a non-null key, now decide what to do with it:
- // 1) if we have insufficient keys in our leaf, simply
append to the leaf and continue;
- // 2) otherwise, walk our parent branches finishing those
*before* {@code finishTo}
- // 2a) if any cannot be finished, append our new key to it
and stop finishing further parents; they
- // will be finished the next time we ascend to their level
with a complete chain of finishable branches
- // 2b) otherwise, add our new key to {@code finishTo}
+ private static abstract class AbstractTransformer<I, O> extends
AbstractSeekingTransformer<I, O>
+ {
+ @Override
+ final int seekInBranch(Object[] unode, int upos, int usz)
+ {
+ return -1 - upos;
+ }
- if (!propagatedOriginalLeaf && !finish(leaf(), null))
+ protected final boolean transformLeaf(Object[] unode, int upos, int
usz)
+ {
+ if (leaf().count == 0)
+ {
+ while (upos < usz)
{
- leaf().addKeyNoOverflow(next);
- continue;
+ O v = apply((I) unode[upos++]);
+ leaf().maybeAddKeyNoOverflow(v);
}
-
- BranchBuilder finish = parent;
- while (true)
+ }
+ else
+ {
+ while (upos < usz)
{
- if (finish.height <= finishToHeight)
- {
- Object[] originalNode = queuedToFinish[finish.height -
2];
- if (finish(finish, originalNode))
- {
- finish = finish.parent;
- continue;
- }
- }
-
- // add our key to the last unpropagated parent branch
buffer
- finish.addKey(next);
- break;
+ O v = apply((I) unode[upos++]);
+ leaf().maybeAddKey(v);
}
}
+ return true;
}
}
-
private static class Transformer<I, O> extends AbstractTransformer<I, O>
{
static final TinyThreadLocalPool<Transformer> POOL = new
TinyThreadLocalPool<>();
@@ -4284,15 +4342,9 @@ public class BTree
// Begins by immediately descending to first leaf; if empty terminates
immediately.
private static class SimpleTreeIterator extends SimpleTreeStack
{
- int init(Object[] tree)
+ int initToLeaf(Object[] tree)
{
- int maxHeight = maxRootHeight(size(tree));
- if (positions == null || maxHeight >= positions.length)
- {
- positions = new int[maxHeight + 1];
- nodes = new Object[maxHeight + 1][];
- }
- nodes[0] = tree;
+ init(tree);
if (isEmpty(tree))
{
// already done
@@ -4314,6 +4366,35 @@ public class BTree
return leafDepth + 1;
}
+ int initToRoot(Object[] tree)
+ {
+ init(tree);
+ positions[0] = 0;
+ leafDepth = depth = 0;
+ while (!isLeaf(tree))
+ {
+ tree = (Object[]) tree[shallowSizeOfBranch(tree)];
+ ++leafDepth;
+ }
+ return leafDepth + 1;
+ }
+
+ int height()
+ {
+ return 1 + leafDepth - depth;
+ }
+
+ void init(Object[] tree)
+ {
+ int maxHeight = maxRootHeight(size(tree));
+ if (positions == null || maxHeight >= positions.length)
+ {
+ positions = new int[maxHeight + 1];
+ nodes = new Object[maxHeight + 1][];
+ }
+ nodes[0] = tree;
+ }
+
void descendIntoNextLeaf(Object[] node, int pos, int sz)
{
positions[depth] = ++pos;
@@ -4328,6 +4409,16 @@ public class BTree
}
}
+ // return true iff entered leaf depth
+ boolean descend(Object[] node, int pos, int sz)
+ {
+ positions[depth] = pos;
+ ++depth;
+ nodes[depth] = (Object[]) node[sz + pos];
+ positions[depth] = 0;
+ return depth == leafDepth;
+ }
+
boolean ascendToParent()
{
if (depth < 0)
diff --git
a/src/java/org/apache/cassandra/utils/btree/FullBTreeSearchIterator.java
b/src/java/org/apache/cassandra/utils/btree/FullBTreeSearchIterator.java
index 7c2fd628c0..546fad8fa3 100644
--- a/src/java/org/apache/cassandra/utils/btree/FullBTreeSearchIterator.java
+++ b/src/java/org/apache/cassandra/utils/btree/FullBTreeSearchIterator.java
@@ -22,6 +22,8 @@ import static org.apache.cassandra.utils.btree.BTree.size;
import java.util.Comparator;
import java.util.NoSuchElementException;
+import accord.utils.Invariants;
+
public class FullBTreeSearchIterator<K, V> extends TreeCursor<K> implements
BTreeSearchIterator<K, V>
{
private final boolean forwards;
@@ -109,7 +111,8 @@ public class FullBTreeSearchIterator<K, V> extends
TreeCursor<K> implements BTre
if ((state & ON_ITEM) == 1)
{
state &= ~ON_ITEM;
- index = moveOne(forwards);
+ if (compareToLast(index = moveOne(forwards)) >= 0)
+ state = LAST;
}
return (V) currentValue();
}
diff --git a/src/java/org/apache/cassandra/utils/btree/IntervalBTree.java
b/src/java/org/apache/cassandra/utils/btree/IntervalBTree.java
index f04cf08917..7ea8b81989 100644
--- a/src/java/org/apache/cassandra/utils/btree/IntervalBTree.java
+++ b/src/java/org/apache/cassandra/utils/btree/IntervalBTree.java
@@ -18,16 +18,23 @@
package org.apache.cassandra.utils.btree;
+import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
+import java.util.List;
+import javax.annotation.Nullable;
+
+import accord.utils.AsymmetricComparator;
import accord.utils.Invariants;
import accord.utils.QuadFunction;
+import accord.utils.SortedArrays;
import io.netty.util.concurrent.FastThreadLocal;
import org.apache.cassandra.utils.caching.TinyThreadLocalPool;
+import static accord.utils.SortedArrays.Search.CEIL;
+import static accord.utils.SortedArrays.Search.FLOOR;
import static org.apache.cassandra.utils.btree.BTree.BRANCH_FACTOR;
-import static org.apache.cassandra.utils.btree.BTree.Dir.ASC;
import static org.apache.cassandra.utils.btree.BTree.getBranchKeyEnd;
import static org.apache.cassandra.utils.btree.BTree.getChildCount;
import static org.apache.cassandra.utils.btree.BTree.getChildStart;
@@ -37,7 +44,6 @@ import static org.apache.cassandra.utils.btree.BTree.isEmpty;
import static org.apache.cassandra.utils.btree.BTree.isLeaf;
import static org.apache.cassandra.utils.btree.BTree.size;
import static org.apache.cassandra.utils.btree.BTree.sizeMap;
-import static org.apache.cassandra.utils.btree.BTree.slice;
/**
* A very simple extension to BTree to provide an Augmented Interval BTree.
@@ -50,25 +56,42 @@ import static org.apache.cassandra.utils.btree.BTree.slice;
*/
public class IntervalBTree
{
- public interface IntervalComparators<V>
+ /**
+ * Defines additional SORT comparators that must be symmetric for
building/maintaining an interval tree
+ */
+ public interface IntervalComparators<I> extends WithIntervalComparators<I,
I>
{
- Comparator<V> totalOrder();
- Comparator<V> startWithStartComparator();
- Comparator<V> startWithEndComparator();
- Comparator<V> endWithStartComparator();
- Comparator<V> endWithEndComparator();
+ Comparator<I> totalOrder();
+ Comparator<I> endWithEndSorter();
}
- public static class InclusiveEndKeyComparatorHelper
+ /**
+ * Defines search comparators for finding an element in an IntervalBTree.
+ *
+ * A search for an element K will potentially include any interval I
+ * for which any comparator yields compare(K, I) == 0.
+ *
+ * These comparators DO NOT need to be symmetric in either type OR
comparison result,
+ * and should knowingly impose the inclusive/exclusive criteria of the
interval
+ * by returning non-zero answers as appropriate.
+ *
+ * Specifically, compare(a, a) should not return 0 if the relevant bound
is exclusive.
+ */
+ public interface WithIntervalComparators<K, I>
{
- public static int keyStartWithIntervalStart(int c) { return
equalsMeansBefore(c); }
- public static int intervalStartWithKeyStart(int c) { return
equalsMeansAfter(c); }
- public static int keyStartWithIntervalEnd(int c) { return
equalsMeansBefore(c); }
- public static int intervalStartWithKeyEnd(int c) { return
equalsMeansAfter(c); }
- public static int keyEndWithIntervalStart(int c) { return
equalsMeansAfter(c); }
- public static int intervalEndWithKeyStart(int c) { return
equalsMeansAfter(c); }
- public static int intervalEndWithKeyEnd(int c) { return
equalsMeansAfter(c); }
- public static int keyEndWithIntervalEnd(int c) { return
equalsMeansBefore(c); }
+ AsymmetricComparator<K, I> startWithStartSeeker();
+ AsymmetricComparator<K, I> startWithEndSeeker();
+ AsymmetricComparator<K, I> endWithStartSeeker();
+ }
+
+ public static class InclusiveEndHelper
+ {
+ public static int keyStartWithStart(int c) { return
equalsMeansAfter(c); }
+ public static int keyStartWithEnd(int c) { return c; }
+ public static int keyEndWithStart(int c) { return
equalsMeansBefore(c); }
+ public static int startWithStart(int c) { return equalsMeansAfter(c); }
+ public static int startWithEnd(int c) { return equalsMeansAfter(c); }
+ public static int endWithStart(int c) { return equalsMeansBefore(c); }
private static int equalsMeansAfter(int c) { return c == 0 ? 1 : c; }
private static int equalsMeansBefore(int c) { return c == 0 ? -1 : c; }
}
@@ -76,52 +99,55 @@ public class IntervalBTree
/**
* Apply the accumulation function over all intersecting intervals in the
tree
*/
- public static <R, P1, P2, V> V accumulate(Object[] btree,
IntervalComparators<R> comparators, R intersects, QuadFunction<P1, P2, R, V, V>
function, P1 p1, P2 p2, V accumulate)
+ public static <Find, Interval, P1, P2, V> V accumulate(Object[] btree,
WithIntervalComparators<Find, Interval> comparators, Find find,
QuadFunction<P1, P2, Interval, V, V> function, P1 p1, P2 p2, V accumulate)
{
if (isLeaf(btree))
{
- Comparator comparator = comparators.startWithEndComparator();
+ AsymmetricComparator<Find, Interval> startWithEnd =
comparators.startWithEndSeeker();
+ AsymmetricComparator<Find, Interval> endWithStart =
comparators.endWithStartSeeker();
int keyEnd = getLeafKeyEnd(btree);
for (int i = 0; i < keyEnd; ++i)
{
- R v = (R) btree[i];
- if (comparator.compare(v, intersects) < 0 &&
comparator.compare(intersects, v) < 0)
- accumulate = function.apply(p1, p2, v, accumulate);
+ Interval interval = (Interval) btree[i];
+ if (endWithStart.compare(find, interval) >= 0 &&
startWithEnd.compare(find, interval) <= 0)
+ accumulate = function.apply(p1, p2, interval, accumulate);
}
}
else
{
- int startKey = Arrays.binarySearch(btree, 0, getKeyEnd(btree),
intersects, (Comparator) comparators.startWithStartComparator());
+ // start/end represent those keys/children we are guaranteed to
intersect (and so may visit without any further comparisons)
+ int startKey = SortedArrays.binarySearch(btree, 0,
getKeyEnd(btree), find,
(AsymmetricComparator)comparators.startWithStartSeeker(), CEIL);
int startChild;
+
if (startKey >= 0) startChild = startKey + 1;
else startChild = (startKey = -1 - startKey);
- int endKey = Arrays.binarySearch(btree, startKey,
getKeyEnd(btree), intersects, (Comparator)
comparators.startWithEndComparator());
+ int endKey = SortedArrays.binarySearch(btree, startKey,
getKeyEnd(btree), find, (AsymmetricComparator)comparators.endWithStartSeeker(),
FLOOR);
int endChild;
- if (endKey >= 0) endChild = 1 + endKey;
+ if (endKey >= 0) { if (endKey < getKeyEnd(btree)) ++endKey;
endChild = 1 + endKey; }
else endChild = 1 + (endKey = -1 - endKey);
{ // descend anything with a max that overlaps us that we won't
already visit
if (startChild > 0 || startKey > 0)
- accumulate = accumulateMaxOnly(startChild + (startChild ==
endChild ? 1 : 0), startKey, btree, comparators, intersects, function, p1, p2,
accumulate);
+ accumulate = accumulateMaxOnly(startChild + (startChild ==
endChild ? 1 : 0), startKey, btree, comparators, find, function, p1, p2,
accumulate);
}
int childOffset = getChildStart(btree);
if (startChild == startKey && startChild < endChild)
- accumulate = accumulate((Object[]) btree[childOffset +
startChild++], comparators, intersects, function, p1, p2, accumulate);
+ accumulate = accumulate((Object[]) btree[childOffset +
startChild++], comparators, find, function, p1, p2, accumulate);
if (startKey < startChild && startKey < endKey)
- accumulate = function.apply(p1, p2, (R) btree[startKey++],
accumulate);
+ accumulate = function.apply(p1, p2, (Interval)
btree[startKey++], accumulate);
while (startChild < endChild - 1)
{
Invariants.require(startKey == startChild);
accumulate = accumulate((Object[]) btree[childOffset +
startChild++], function, p1, p2, accumulate);
- accumulate = function.apply(p1, p2, (R) btree[startKey++],
accumulate);
+ accumulate = function.apply(p1, p2, (Interval)
btree[startKey++], accumulate);
}
if (startKey < endKey)
- accumulate = function.apply(p1, p2, (R) btree[startKey],
accumulate);
+ accumulate = function.apply(p1, p2, (Interval)
btree[startKey], accumulate);
if (startChild < endChild)
- accumulate = accumulate((Object[]) btree[childOffset +
startChild], comparators, intersects, function, p1, p2, accumulate);
+ accumulate = accumulate((Object[]) btree[childOffset +
startChild], comparators, find, function, p1, p2, accumulate);
}
return accumulate;
}
@@ -146,45 +172,41 @@ public class IntervalBTree
return accumulate;
}
- private static <R, P1, P2, V> V accumulateMaxOnly(int ifChildBefore, int
ifKeyBefore, Object[] btree, IntervalComparators<R> comparators, R intersects,
QuadFunction<P1, P2, R, V, V> function, P1 p1, P2 p2, V accumulate)
+ private static <Find, Interval, P1, P2, V> V accumulateMaxOnly(int
ifChildBefore, int ifKeyBefore, Object[] btree, WithIntervalComparators<Find,
Interval> comparators, Find find, QuadFunction<P1, P2, Interval, V, V>
function, P1 p1, P2 p2, V accumulate)
{
+ AsymmetricComparator<Find, Interval> startWithEnd =
comparators.startWithEndSeeker();
+ AsymmetricComparator<Find, Interval> endWithStart =
comparators.endWithStartSeeker();
if (isLeaf(btree))
{
Invariants.require(ifChildBefore == Integer.MAX_VALUE);
- Comparator comparator = comparators.startWithEndComparator();
for (int i = 0, maxi = getLeafKeyEnd(btree); i < maxi; ++i)
{
- R v = (R) btree[i];
- if (comparator.compare(intersects, v) < 0)
- {
- Invariants.paranoid(comparator.compare(v, intersects) < 0);
- accumulate = function.apply(p1, p2, v, accumulate);
- }
+ Interval interval = (Interval) btree[i];
+ if (startWithEnd.compare(find, interval) <= 0 &&
endWithStart.compare(find, interval) >= 0)
+ accumulate = function.apply(p1, p2, interval, accumulate);
}
}
else
{
int keyEnd = getChildStart(btree);
+ ifKeyBefore = Math.min(ifKeyBefore, keyEnd);
+
IntervalMaxIndex intervalMaxIndex = getIntervalMaxIndex(btree);
- int descendMaxStart =
Arrays.binarySearch(intervalMaxIndex.sortedByEnd, intersects, (Comparator)
comparators.endWithStartComparator());
+ int descendMaxStart = SortedArrays.binarySearch((Interval[])
intervalMaxIndex.sortedByEnd, 0, intervalMaxIndex.sortedByEnd.length, find,
comparators.startWithEndSeeker(), CEIL);
if (descendMaxStart < 0)
descendMaxStart = -1 - descendMaxStart;
int[] sortedByEndIndex = intervalMaxIndex.sortedByEndIndex;
for (int i = descendMaxStart; i < sortedByEndIndex.length; ++i)
{
int index = sortedByEndIndex[i];
- if (index < ifChildBefore)
- accumulate = accumulateMaxOnly(Integer.MAX_VALUE,
Integer.MAX_VALUE, (Object[]) btree[keyEnd + index], comparators, intersects,
function, p1, p2, accumulate);
- }
- Comparator comparator = comparators.startWithEndComparator();
- for (int i = 0, maxi = Math.min(ifKeyBefore, keyEnd); i < maxi;
++i)
- {
- R v = (R) btree[i];
- if (comparator.compare(intersects, v) < 0)
+ if (index < ifKeyBefore)
{
- Invariants.paranoid(comparator.compare(v, intersects) < 0);
- accumulate = function.apply(p1, p2, v, accumulate);
+ Interval interval = (Interval) btree[index];
+ if (startWithEnd.compare(find, interval) <= 0 &&
endWithStart.compare(find, interval) >= 0)
+ accumulate = function.apply(p1, p2, interval,
accumulate);
}
+ if (index < ifChildBefore)
+ accumulate = accumulateMaxOnly(Integer.MAX_VALUE,
Integer.MAX_VALUE, (Object[]) btree[keyEnd + index], comparators, find,
function, p1, p2, accumulate);
}
}
return accumulate;
@@ -198,19 +220,107 @@ public class IntervalBTree
int index;
}
+ Object[] unpackedIndex;
SortEntry[] sort = new SortEntry[BRANCH_FACTOR];
- Comparator endSorter;
+ Comparator endSorter, totalOrder;
- public void override(Object[] branch)
+ void setComparators(IntervalComparators comparators)
+ {
+ this.endSorter = comparators.endWithEndSorter();
+ this.totalOrder = comparators.totalOrder();
+ }
+
+ void reset()
+ {
+ this.endSorter = this.totalOrder = null;
+ for (int i = 0 ; i < sort.length && sort[i] != null ; i++)
+ sort[i].sort = null;
+ }
+
+ public void override(Object[] branch, @Nullable List<Object[]>
sourceNodes)
{
- int[] sizeMap = sizeMap(branch);
int childStart = getChildStart(branch), childCount =
getChildCount(branch);
+ for (int i = childCount - 1 ; i >= 0 && sort[i] == null ; --i)
+ sort[i] = new SortEntry();
+
+ if (sourceNodes != null && sourceNodes.isEmpty())
+ sourceNodes = null;
+
+ if (sourceNodes != null)
+ {
+ int maxUnpackedSize = 0;
+ if (unpackedIndex == null)
+ unpackedIndex = new Object[BRANCH_FACTOR];
+
+ int i = 0;
+ for (Object[] sn : sourceNodes)
+ {
+ IntervalMaxIndex index = getIntervalMaxIndex(sn);
+ int snStart = getChildStart(sn), snCount =
getChildCount(sn);
+ for (int j = 0 ; j < index.sortedByEnd.length ; ++j)
+ unpackedIndex[index.sortedByEndIndex[j]] =
index.sortedByEnd[j];
+
+ int j = 0;
+ while (i < childCount && j < snCount)
+ {
+ if (branch[childStart + i] == sn[snStart + j]) //
child nodes are the same so we can copy max
+ {
+ sort[i].index = i;
+ if (j == snStart)
+ {
+ // in either case, the max we have represents
the max of the child;
+ // must only compare with new branch key (if
any) and take the branch if ends later
+ sort[i].sort = i == childStart ||
endSorter.compare(branch[i], unpackedIndex[j]) <= 0
+ ? unpackedIndex[j] : branch[i];
+ }
+ else if (unpackedIndex[j] != sn[j])
+ {
+ // previous max was not the branch, so must
have been within child
+ // like prior condition, must only compare
with new branch key (if any) and take the branch if ends later
+ // however, we have a chance to save a
comparison here if we also copied the key from the source node
+ sort[i].sort = i == childStart || branch[i] ==
sn[j] || endSorter.compare(branch[i], unpackedIndex[j]) <= 0
+ ? unpackedIndex[j] : branch[i];
+ }
+ else if (i != childStart &&
endSorter.compare(sn[j], branch[i]) <= 0)
+ {
+ // previous max was previous branch key; new
branch key has higher end so can simply use it
+ sort[i].sort = branch[i];
+ }
+ else
+ {
+ // otherwise we cannot infer anything directly
+ sort[i].sort = null;
+ }
+
+ ++i;
+ ++j;
+ }
+ else
+ {
+ if (i == childStart || j == snStart)
+ break; // if we've finished iteration of one
or the other, break and continue with any further source nodes (if any)
+
+ int c = totalOrder.compare(branch[i], sn[j]);
+ if (c <= 0) sort[i++].sort = null;
+ if (c >= 0) ++j;
+ }
+ }
+
+ maxUnpackedSize = Math.max(maxUnpackedSize, snCount);
+ }
+ while (i < childCount)
+ sort[i++].sort = null;
+ Arrays.fill(unpackedIndex, 0, maxUnpackedSize, null);
+ }
for (int i = 0; i < childCount; ++i)
{
+ if (sourceNodes != null && sort[i].sort != null)
+ continue;
+
Object[] child = (Object[]) branch[i + childStart];
Object max = maxChild(child);
- if (sort[i] == null)
- sort[i] = new SortEntry();
+ if (i < childStart && endSorter.compare(branch[i], max) > 0)
+ max = branch[i];
sort[i].index = i;
sort[i].sort = max;
}
@@ -222,25 +332,28 @@ public class IntervalBTree
sortedByEnd[i] = sort[i].sort;
sortedByEndIndex[i] = sort[i].index;
}
+
+ int[] sizeMap = sizeMap(branch);
branch[branch.length - 1] = new IntervalMaxIndex(sortedByEnd,
sortedByEndIndex, sizeMap);
}
private Object maxChild(Object[] child)
{
- Object max = child[0];
- for (int j = 1, jend = getKeyEnd(child); j < jend; ++j)
+ if (isLeaf(child))
{
- if (endSorter.compare(child[j], max) > 0)
- max = child[j];
+ Object max = child[0];
+ for (int i = 1, end = getLeafKeyEnd(child); i < end; ++i)
+ {
+ if (endSorter.compare(child[i], max) > 0)
+ max = child[i];
+ }
+ return max;
}
- if (!isLeaf(child))
+ else
{
- IntervalMaxIndex childIndex = getIntervalMaxIndex(child);
- Object maxChild =
childIndex.sortedByEnd[childIndex.sortedByEnd.length - 1];
- if (endSorter.compare(maxChild, max) > 0)
- max = maxChild;
+ IntervalMaxIndex index = getIntervalMaxIndex(child);
+ return index.sortedByEnd[index.sortedByEnd.length - 1];
}
- return max;
}
@Override
@@ -252,11 +365,13 @@ public class IntervalBTree
static class IntervalBranchBuilder extends BTree.BranchBuilder
{
+ List<Object[]> sourceNodes;
IntervalIndexAdapter adapter;
IntervalBranchBuilder(BTree.LeafOrBranchBuilder child)
{
super(child);
+ sourceNodes = child.height == 1 ? new ArrayList<>() : null;
}
@Override
@@ -282,7 +397,7 @@ public class IntervalBTree
int setDrainSizeMap(Object[] original, int keysInOriginal, Object[]
branch, int keysInBranch)
{
int result = super.setDrainSizeMap(original, keysInOriginal,
branch, keysInBranch);
- adapter.override(branch);
+ adapter.override(branch, sourceNodes);
return result;
}
@@ -290,21 +405,37 @@ public class IntervalBTree
void setRedistributedSizeMap(Object[] branch, int steal)
{
super.setRedistributedSizeMap(branch, steal);
- adapter.override(branch);
+ adapter.override(branch, sourceNodes);
}
@Override
int setOverflowSizeMap(Object[] branch, int keys)
{
int result = super.setOverflowSizeMap(branch, keys);
- adapter.override(branch);
+ adapter.override(branch, sourceNodes);
return result;
}
+
+ @Override
+ void setSourceNode(Object[] sourceNode)
+ {
+ if (sourceNodes != null)
+ sourceNodes.add(sourceNode);
+ super.setSourceNode(sourceNode);
+ }
+
+ @Override
+ void clearSourceNode()
+ {
+ super.clearSourceNode();
+ if (sourceNodes != null)
+ sourceNodes.clear();
+ }
}
- public static class FastInteralTreeBuilder<V> extends BTree.FastBuilder<V>
+ public static class FastIntervalTreeBuilder<V> extends BTree.FastBuilder<V>
{
- private static final TinyThreadLocalPool<FastInteralTreeBuilder<?>>
POOL = new TinyThreadLocalPool<>();
+ private static final TinyThreadLocalPool<FastIntervalTreeBuilder<?>>
POOL = new TinyThreadLocalPool<>();
final IntervalIndexAdapter adapter = new IntervalIndexAdapter();
@Override
@@ -319,6 +450,13 @@ public class IntervalBTree
super.initParent();
((IntervalBranchBuilder) parent).init(adapter);
}
+
+ @Override
+ public void close()
+ {
+ super.close();
+ adapter.reset();
+ }
}
static class IntervalUpdater<Compare, Existing extends Compare, Insert
extends Compare> extends BTree.Updater<Compare, Existing, Insert>
@@ -326,14 +464,14 @@ public class IntervalBTree
static final TinyThreadLocalPool<IntervalUpdater> POOL = new
TinyThreadLocalPool<>();
private final IntervalIndexAdapter adapter = new
IntervalIndexAdapter();
- static <Compare, Existing extends Compare, Insert extends Compare>
IntervalUpdater<Compare, Existing, Insert> get(Comparator<Compare> compareEnds)
+ static <Compare, Existing extends Compare, Insert extends Compare>
IntervalUpdater<Compare, Existing, Insert> get(IntervalComparators<Compare>
comparators)
{
TinyThreadLocalPool.TinyPool<IntervalUpdater> pool = POOL.get();
IntervalUpdater<Compare, Existing, Insert> updater = pool.poll();
if (updater == null)
updater = new IntervalUpdater<>();
updater.pool = pool;
- updater.adapter.endSorter = compareEnds;
+ updater.adapter.setComparators(comparators);
return updater;
}
@@ -353,7 +491,7 @@ public class IntervalBTree
@Override
public void close()
{
- adapter.endSorter = null;
+ adapter.reset();
}
}
@@ -367,23 +505,18 @@ public class IntervalBTree
return BTree.singleton(value);
}
- static class Subtraction<K, T extends K> extends BTree.Subtraction<K, T>
+ static class Subtraction<K, T extends K> extends
BTree.AbstractSubtraction<K, T>
{
static final FastThreadLocal<Subtraction> SHARED = new
FastThreadLocal<>();
private final IntervalIndexAdapter adapter = new
IntervalIndexAdapter();
- Subtraction()
- {
- ((IntervalBranchBuilder)parent).adapter = adapter;
- }
-
static <K, T extends K> Subtraction<K, T> get(IntervalComparators<K>
comparators)
{
Subtraction subtraction = SHARED.get();
if (subtraction == null)
SHARED.set(subtraction = new Subtraction());
subtraction.comparator = comparators.totalOrder();
- subtraction.adapter.endSorter = comparators.endWithEndComparator();
+ subtraction.adapter.setComparators(comparators);
return subtraction;
}
@@ -405,7 +538,7 @@ public class IntervalBTree
{
reset();
comparator = null;
- adapter.endSorter = null;
+ adapter.reset();
}
}
@@ -417,9 +550,9 @@ public class IntervalBTree
*/
public static <Compare> Object[] subtract(Object[] toUpdate, Object[]
subtract, IntervalComparators<Compare> comparators)
{
- try (Subtraction subtraction =
IntervalBTree.Subtraction.get(comparators))
+ try (Subtraction subtraction = Subtraction.get(comparators))
{
- return subtraction.apply(toUpdate, slice(subtract,
comparators.totalOrder(), ASC));
+ return subtraction.subtract(toUpdate, subtract);
}
}
@@ -456,24 +589,23 @@ public class IntervalBTree
}
}
- try (IntervalUpdater<Compare, Existing, Insert> updater =
IntervalUpdater.get(comparators.endWithEndComparator()))
+ try (IntervalUpdater<Compare, Existing, Insert> updater =
IntervalUpdater.get(comparators))
{
return updater.update(existing, insert, comparators.totalOrder(),
(UpdateFunction) UpdateFunction.noOp);
}
}
-
/**
* Build a tree of unknown size, in order.
*/
- public static <V> FastInteralTreeBuilder<V> fastBuilder(Comparator<V>
endSorter)
+ public static <V> FastIntervalTreeBuilder<V>
fastBuilder(IntervalComparators<V> comparators)
{
- TinyThreadLocalPool.TinyPool<FastInteralTreeBuilder<?>> pool =
FastInteralTreeBuilder.POOL.get();
- FastInteralTreeBuilder<V> builder = (FastInteralTreeBuilder<V>)
pool.poll();
+ TinyThreadLocalPool.TinyPool<FastIntervalTreeBuilder<?>> pool =
FastIntervalTreeBuilder.POOL.get();
+ FastIntervalTreeBuilder<V> builder = (FastIntervalTreeBuilder<V>)
pool.poll();
if (builder == null)
- builder = new FastInteralTreeBuilder<>();
+ builder = new FastIntervalTreeBuilder<>();
builder.pool = pool;
- builder.adapter.endSorter = endSorter;
+ builder.adapter.setComparators(comparators);
return builder;
}
diff --git a/test/unit/org/apache/cassandra/utils/RangeTreeTest.java
b/test/unit/org/apache/cassandra/utils/RangeTreeTest.java
index e576d667c2..48cd22d429 100644
--- a/test/unit/org/apache/cassandra/utils/RangeTreeTest.java
+++ b/test/unit/org/apache/cassandra/utils/RangeTreeTest.java
@@ -41,10 +41,12 @@ import accord.api.RoutingKey;
import accord.impl.IntKey;
import accord.impl.IntKey.Routing;
import accord.primitives.Range;
+import accord.utils.AsymmetricComparator;
import accord.utils.Gen;
import accord.utils.Gens;
import accord.utils.RandomSource;
import accord.utils.SearchableRangeList;
+import accord.utils.SymmetricComparator;
import accord.utils.btree.BTree;
import org.agrona.collections.IntArrayList;
import org.agrona.collections.LongArrayList;
@@ -52,14 +54,12 @@ import org.apache.cassandra.utils.btree.IntervalBTree;
import org.assertj.core.api.Assertions;
import static accord.utils.Property.qt;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.intervalEndWithKeyEnd;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.intervalEndWithKeyStart;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.intervalStartWithKeyEnd;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.intervalStartWithKeyStart;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.keyEndWithIntervalEnd;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.keyEndWithIntervalStart;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.keyStartWithIntervalEnd;
-import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndKeyComparatorHelper.keyStartWithIntervalStart;
+import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndHelper.endWithStart;
+import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndHelper.keyEndWithStart;
+import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndHelper.keyStartWithEnd;
+import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndHelper.keyStartWithStart;
+import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndHelper.startWithEnd;
+import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndHelper.startWithStart;
@RunWith(Parameterized.class)
public class RangeTreeTest
@@ -655,67 +655,20 @@ public class RangeTreeTest
};
}
- @Override
- public Comparator<Item> startWithStartComparator()
- {
- return (a, b) -> a.start.compareTo(b.start);
- }
-
- @Override
- public Comparator<Item> startWithEndComparator()
- {
- return (a, b) -> a.start.compareTo(b.end);
- }
+ @Override public SymmetricComparator<Item> endWithEndSorter() {
return (a, b) -> a.end.compareTo(b.end); }
- @Override
- public Comparator<Item> endWithStartComparator()
- {
- return (a, b) -> a.end.compareTo(b.start);
- }
-
- @Override
- public Comparator<Item> endWithEndComparator()
- {
- return (a, b) -> a.end.compareTo(b.end);
- }
+ @Override public SymmetricComparator<Item> startWithStartSeeker()
{ return (a, b) -> startWithStart(a.start.compareTo(b.start)); }
+ @Override public SymmetricComparator<Item> startWithEndSeeker() {
return (a, b) -> startWithEnd(a.start.compareTo(b.end)); }
+ @Override public SymmetricComparator<Item> endWithStartSeeker() {
return (a, b) -> endWithStart(a.end.compareTo(b.start)); }
}
- static class ItemKeyComparators implements
IntervalBTree.IntervalComparators<Object>
+ static class ItemKeyComparators implements
IntervalBTree.WithIntervalComparators<RoutingKey, Item>
{
private static final ItemKeyComparators INSTANCE = new
ItemKeyComparators();
- @Override public Comparator<Object> totalOrder() { throw new
UnsupportedOperationException(); }
- @Override
- public Comparator<Object> startWithStartComparator()
- {
- return (a, b) -> a.getClass() == Item.class
- ? intervalStartWithKeyStart(((Item)
a).start.compareTo((RoutingKey)b))
- :
keyStartWithIntervalStart(((RoutingKey)a).compareTo(((Item)b).start));
- }
-
- @Override
- public Comparator<Object> startWithEndComparator()
- {
- return (a, b) -> a.getClass() == Item.class
- ?
intervalStartWithKeyEnd(((Item)a).start.compareTo((RoutingKey)b))
- :
keyStartWithIntervalEnd(((RoutingKey)a).compareTo(((Item)b).end));
- }
-
- @Override
- public Comparator<Object> endWithStartComparator()
- {
- return (a, b) -> a.getClass() == Item.class
- ?
intervalEndWithKeyStart(((Item)a).end.compareTo((RoutingKey)b))
- :
keyEndWithIntervalStart(((RoutingKey)a).compareTo(((Item)b).start));
- }
-
- @Override
- public Comparator<Object> endWithEndComparator()
- {
- return (a, b) -> a.getClass() == Item.class
- ?
intervalEndWithKeyEnd(((Item)a).end.compareTo((RoutingKey)b))
- :
keyEndWithIntervalEnd(((RoutingKey)a).compareTo(((Item)b).end));
- }
+ @Override public AsymmetricComparator<RoutingKey, Item>
startWithStartSeeker() { return (a, b) ->
keyStartWithStart(a.compareTo(b.start)); }
+ @Override public AsymmetricComparator<RoutingKey, Item>
startWithEndSeeker() { return (a, b) -> keyStartWithEnd(a.compareTo(b.end)); }
+ @Override public AsymmetricComparator<RoutingKey, Item>
endWithStartSeeker() { return (a, b) -> keyEndWithStart(a.compareTo(b.start)); }
}
static class Item extends Entry
@@ -754,13 +707,13 @@ public class RangeTreeTest
@Override
public List<Map.Entry<Range, Integer>> intersectsToken(Routing key)
{
- return IntervalBTree.<Object, Object, Object,
List<Map.Entry<Range, Integer>>>accumulate(btree, ItemKeyComparators.INSTANCE,
key, (i1, i2, item, list) -> { list.add((Item)item); return list; }, null,
null, new ArrayList<>());
+ return IntervalBTree.<RoutingKey, Item, Object, Object,
List<Map.Entry<Range, Integer>>>accumulate(btree, ItemKeyComparators.INSTANCE,
key, (i1, i2, item, list) -> { list.add((Item)item); return list; }, null,
null, new ArrayList<>());
}
@Override
public List<Map.Entry<Range, Integer>> intersects(Range range)
{
- return IntervalBTree.<Item, Object, Object, List<Map.Entry<Range,
Integer>>>accumulate(btree, ItemComparators.INSTANCE, new Item(range.start(),
range.end(), range, 0, 0), (i1, i2, item, list) -> { list.add(item); return
list; }, null, null, new ArrayList<>());
+ return IntervalBTree.<Item, Item, Object, Object,
List<Map.Entry<Range, Integer>>>accumulate(btree, ItemComparators.INSTANCE, new
Item(range.start(), range.end(), range, 0, 0), (i1, i2, item, list) -> {
list.add(item); return list; }, null, null, new ArrayList<>());
}
@Override
diff --git a/test/unit/org/apache/cassandra/utils/btree/IntervalBTreeTest.java
b/test/unit/org/apache/cassandra/utils/btree/IntervalBTreeTest.java
index 421e3a037f..7a421e13d5 100644
--- a/test/unit/org/apache/cassandra/utils/btree/IntervalBTreeTest.java
+++ b/test/unit/org/apache/cassandra/utils/btree/IntervalBTreeTest.java
@@ -27,15 +27,28 @@ import java.util.TreeSet;
import org.junit.Test;
+import accord.utils.DefaultRandom;
import accord.utils.Invariants;
+import accord.utils.RandomSource;
+import accord.utils.SymmetricComparator;
+import org.apache.cassandra.config.CassandraRelevantProperties;
import static org.apache.cassandra.utils.btree.BTree.getChildCount;
import static org.apache.cassandra.utils.btree.BTree.getChildStart;
import static org.apache.cassandra.utils.btree.BTree.getKeyEnd;
import static org.apache.cassandra.utils.btree.BTree.isLeaf;
+import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndHelper.endWithStart;
+import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndHelper.startWithEnd;
+import static
org.apache.cassandra.utils.btree.IntervalBTree.InclusiveEndHelper.startWithStart;
public class IntervalBTreeTest
{
+ static
+ {
+ // build deeper trees to explore more behaviours
+ CassandraRelevantProperties.BTREE_BRANCH_SHIFT.setInt(3);
+ }
+
static class TestInterval implements Comparable<TestInterval>
{
final int start, end;
@@ -68,97 +81,118 @@ public class IntervalBTreeTest
{
static final TestComparators INSTANCE = new TestComparators();
- @Override
- public Comparator<TestInterval> totalOrder()
- {
- return TestInterval::compareTo;
- }
-
- @Override
- public Comparator<TestInterval> startWithStartComparator()
- {
- return (a, b) -> Integer.compare(a.start, b.start);
- }
-
- @Override
- public Comparator<TestInterval> startWithEndComparator()
- {
- return (a, b) -> Integer.compare(a.start, b.end);
- }
-
- @Override
- public Comparator<TestInterval> endWithStartComparator()
- {
- return (a, b) -> Integer.compare(a.end, b.start);
- }
-
- @Override
- public Comparator<TestInterval> endWithEndComparator()
- {
- return (a, b) -> Integer.compare(a.end, b.end);
- }
+ @Override public Comparator<TestInterval> totalOrder() { return
TestInterval::compareTo; }
+ @Override public SymmetricComparator<TestInterval> endWithEndSorter()
{ return (a, b) -> Integer.compare(a.end, b.end); }
+ @Override public SymmetricComparator<TestInterval>
startWithStartSeeker() { return (a, b) ->
startWithStart(Integer.compare(a.start, b.start)); }
+ @Override public SymmetricComparator<TestInterval>
startWithEndSeeker() { return (a, b) -> startWithEnd(Integer.compare(a.start,
b.end)); }
+ @Override public SymmetricComparator<TestInterval>
endWithStartSeeker() { return (a, b) -> endWithStart(Integer.compare(a.end,
b.start)); }
}
@Test
public void testN()
{
-// testOne(4391017837511000309L);
+ testOne(7817231705170378212L);
Random seeds = new Random();
- for (int i = 0 ; i < 1000 ; ++i)
+ for (int i = 0 ; i < 200 ; ++i)
testOne(seeds.nextLong());
}
+ // TODO (expected): test extreme patterns
public static void testOne(long seed)
{
try
{
+ List<TestInterval> tmp = new ArrayList<>();
List<TestInterval> list = new ArrayList<>();
- Random random = new Random();
+ RandomSource random = new DefaultRandom();
random.setSeed(seed);
System.out.println(seed);
- int count = 1 << random.nextInt(11);
- int maxRemoveSize = count == 1 ? 1 : 1 + random.nextInt(count - 1);
+ int count = random.nextFloat() < 0.001 ? random.nextInt(1, 4) : 4
<< random.nextInt(10);
+ int keyDomain = count == 1 ? 2 : 1 + log2uniform(random, count);
+ int valueDomain = count == 1 ? 1 :
random.nextInt((int)Math.sqrt(count), count);
+ int maxRemoveSize = log2uniform(random, count);
+ int maxRunLength = log2uniform(random, count);
+ float runChance = random.nextFloat();
count = count + random.nextInt(count);
TreeSet<TestInterval> unique = new TreeSet<>();
for (int i = 0 ; i < count ; ++i)
{
- TestInterval interval = newInterval(random, 0, 10000);
+ TestInterval interval = newInterval(random, keyDomain,
valueDomain);
if (unique.add(interval))
list.add(interval);
+
+ if (maxRunLength > 1 && random.decide(runChance) && count - i
> 1)
+ {
+ boolean startRun = random.nextBoolean();
+ int runLength = random.nextBoolean() ? log2uniform(random,
maxRunLength - 1)
+ : random.nextInt(0,
maxRunLength - 1);
+ runLength = Math.min(runLength, count - (i + 1));
+ runLength = Math.min(runLength, startRun ? keyDomain - (1
+ interval.start) : interval.end);
+ while (--runLength >= 0)
+ {
+ int start = startRun ? interval.start :
random.nextInt(interval.end);
+ int end = startRun ? random.nextInt(interval.start +
1, keyDomain) : interval.end;
+ int value = random.nextInt(valueDomain);
+ TestInterval interval2 = new TestInterval(start, end,
value);
+ if (unique.add(interval2))
+ {
+ list.add(interval2);
+ ++i;
+ }
+ }
+ }
}
Object[] tree = BTree.empty();
- for (TestInterval v : list)
+ if (random.nextBoolean())
+ {
+ for (TestInterval v : list)
+ {
+ tree = IntervalBTree.update(tree, BTree.singleton(v),
TestComparators.INSTANCE);
+ }
+ }
+ else
{
- tree = IntervalBTree.update(tree, BTree.singleton(v),
TestComparators.INSTANCE);
+ tmp.addAll(list);
+ tmp.sort(TestComparators.INSTANCE.totalOrder());
+ try (BTree.FastBuilder<TestInterval> builder =
IntervalBTree.fastBuilder(TestComparators.INSTANCE))
+ {
+ for (TestInterval add : tmp)
+ builder.add(add);
+ tree = builder.build();
+ }
}
+ validate(tree, TestComparators.INSTANCE.endWithEndSorter());
- for (int i1 = 0 ; i1 < list.size() ; ++i1)
+ for (int i = 0 ; i < list.size() ; ++i)
{
- TestInterval iv = list.get(i1);
+ TestInterval iv = list.get(i);
TreeSet<TestInterval> collect = collect(list, 0, iv);
remove(tree, collect, iv);
Invariants.require(collect.isEmpty());
- iv = newInterval(random, 0, 10000);
+ iv = newInterval(random, keyDomain, valueDomain);
collect = collect(list, 0, iv);
remove(tree, collect, iv);
Invariants.require(collect.isEmpty());
}
- Collections.shuffle(list, random);
+ Collections.shuffle(list, random.asJdkRandom());
for (int i = 0 ; i < list.size() ;)
{
int remaining = list.size() - i;
- int c = remaining == 1 ? 1 : 1 +
random.nextInt(Math.min(remaining, maxRemoveSize));
+ int removeCount = remaining == 1 ? 1 : 1 +
random.nextInt(Math.min(remaining, maxRemoveSize));
+ remaining -= removeCount;
TestInterval iv = list.get(i++);
Object[] remove;
{
- remove = IntervalBTree.singleton(iv);
+ tmp.clear();
+ tmp.add(iv);
+ int c = removeCount;
while (--c > 0)
- remove = IntervalBTree.update(remove,
IntervalBTree.singleton(list.get(i++)), TestComparators.INSTANCE);
+ tmp.add(list.get(i++));
int notPresentCount;
switch (random.nextInt(4))
@@ -172,17 +206,25 @@ public class IntervalBTreeTest
while (--notPresentCount > 0)
{
- TestInterval add = newInterval(random, 0, 10000);
+ TestInterval add = newInterval(random, keyDomain,
valueDomain);
if (!unique.contains(add))
- remove = IntervalBTree.update(remove,
IntervalBTree.singleton(add), TestComparators.INSTANCE);
+ tmp.add(add);
+ }
+
+ tmp.sort(TestComparators.INSTANCE.totalOrder());
+ try (BTree.FastBuilder<TestInterval> builder =
IntervalBTree.fastBuilder(TestComparators.INSTANCE))
+ {
+ for (TestInterval add : tmp)
+ builder.add(add);
+ remove = builder.build();
}
}
tree = IntervalBTree.subtract(tree, remove,
TestComparators.INSTANCE);
- validate(tree,
TestComparators.INSTANCE.endWithEndComparator());
+ validate(tree, TestComparators.INSTANCE.endWithEndSorter());
TreeSet<TestInterval> collect = collect(list, i, iv);
remove(tree, collect, iv);
Invariants.require(collect.isEmpty());
- iv = newInterval(random, 0, 10000);
+ iv = newInterval(random, keyDomain, valueDomain);
collect = collect(list, i, iv);
remove(tree, collect, iv);
Invariants.require(collect.isEmpty());
@@ -194,6 +236,16 @@ public class IntervalBTreeTest
}
}
+ private static int log2uniform(RandomSource random, int max)
+ {
+ int logn = 31 - Integer.numberOfLeadingZeros(max);
+ int loglogn = 31 - Integer.numberOfLeadingZeros(logn);
+ int scale = 1 << random.nextInt(loglogn, logn);
+ if (scale == max)
+ return max;
+ return random.nextInt(scale, Math.min(scale * 2, max));
+ }
+
private static TreeSet<TestInterval> collect(List<TestInterval> list, int
from, TestInterval intersects)
{
TreeSet<TestInterval> collect = new TreeSet<>();
@@ -214,11 +266,11 @@ public class IntervalBTreeTest
}, removeFrom, null, null);
}
- private static TestInterval newInterval(Random random, int from, int to)
+ private static TestInterval newInterval(RandomSource random, int
keyDomain, int valueDomain)
{
- int end = 1 + from + random.nextInt(to - (1 + from));
- int start = from + random.nextInt(end - from);
- return new TestInterval(start, end, random.nextInt(10000));
+ int end = 1 + random.nextInt(keyDomain - 1);
+ int start = random.nextInt(end);
+ return new TestInterval(start, end, random.nextInt(valueDomain));
}
static Object validate(Object[] tree, Comparator endSorter)
@@ -235,6 +287,8 @@ public class IntervalBTreeTest
for (int i = 0 ; i < getChildCount(tree) ; ++i)
{
Object childMax = validate((Object[])tree[getChildStart(tree) +
i], endSorter);
+ if (i < getChildStart(tree) && endSorter.compare(childMax,
tree[i]) < 0)
+ childMax = tree[i];
if (endSorter.compare(childMax, max) > 0)
max = childMax;
Invariants.require(endSorter.compare(childMax, tmp[i]) == 0);
@@ -252,5 +306,4 @@ public class IntervalBTreeTest
}
return max;
}
-
}
diff --git
a/test/unit/org/apache/cassandra/utils/btree/IntervalTreePerfTest.java
b/test/unit/org/apache/cassandra/utils/btree/IntervalTreePerfTest.java
new file mode 100644
index 0000000000..db32a8acd8
--- /dev/null
+++ b/test/unit/org/apache/cassandra/utils/btree/IntervalTreePerfTest.java
@@ -0,0 +1,239 @@
+///*
+// * 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.nio.ByteBuffer;
+//import java.util.ArrayList;
+//import java.util.Collections;
+//import java.util.HashSet;
+//import java.util.List;
+//import java.util.Random;
+//import java.util.concurrent.ThreadLocalRandom;
+//
+//import com.google.common.base.Stopwatch;
+//import org.junit.Test;
+//import org.slf4j.Logger;
+//import org.slf4j.LoggerFactory;
+//
+//import org.apache.cassandra.db.BufferDecoratedKey;
+//import org.apache.cassandra.db.DecoratedKey;
+//import org.apache.cassandra.db.PartitionPosition;
+//import org.apache.cassandra.dht.Murmur3Partitioner.LongToken;
+//import org.apache.cassandra.dht.Token;
+//import org.apache.cassandra.utils.Interval;
+//import org.apache.cassandra.utils.IntervalTree;
+//
+//import static java.lang.String.format;
+//import static java.util.concurrent.TimeUnit.NANOSECONDS;
+//
+//public class IntervalTreePerfTest
+//{
+// private static final Logger logger =
LoggerFactory.getLogger(IntervalTreePerfTest.class);
+//
+// private static final byte[] bigArray = new byte[1024 * 1024 * 64];
+//
+// static
+// {
+// Random r = new Random();
+// r.nextBytes(bigArray);
+// }
+//
+//
+// private static List<Interval<PartitionPosition, Integer>>
randomIntervals(int range, int increment, int count)
+// {
+// List<PartitionPosition> a = random(range, increment, count);
+// List<PartitionPosition> b = random(range, increment, count);
+// List<Interval<PartitionPosition, Integer>> r = new ArrayList<>();
+// for (int i = 0 ; i < count ; i++)
+// {
+// r.add(a.get(i).compareTo(b.get(i)) < 0 ?
Interval.create(a.get(i), b.get(i), i)
+// : Interval.create(b.get(i), a.get(i),
i));
+// }
+// return r;
+// }
+//
+// private static List<PartitionPosition> random(int range, int increment,
int count)
+// {
+// List<PartitionPosition> random = new ArrayList<>();
+// for (int i = 0 ; i < count ; i++)
+// {
+// int base = i * increment;
+// Token token = new
LongToken(ThreadLocalRandom.current().nextInt(base, base + range));
+// ByteBuffer key = ByteBuffer.allocate(16);
+//
key.putLong(token.getLongValue()).putLong(token.getLongValue()).flip();
+// DecoratedKey dk = new BufferDecoratedKey(token, key);
+// random.add(dk);
+// }
+// return random;
+// }
+//
+// @Test
+// public void test()
+// {
+// long checksum = 0;
+// int iterations = 1000;
+// int totalTableCount = 100000;
+// int additionalIntervalsCount = 1000;
+// long rangePersstable = Long.MAX_VALUE / 5;
+// int range = 1000000;
+//
+// List<Interval<PartitionPosition, Integer>> randomIntervals = new
ArrayList<>();
+// List<Interval<PartitionPosition, Integer>> additionalIntervals = new
ArrayList<>();
+// List<Interval<PartitionPosition, Integer>> insertIntervals =
randomIntervals;
+// for (int level = 0; level <= 7; level++)
+// {
+// for (int i = 0; i < (Long.MAX_VALUE / rangePersstable) * 2; i++)
+// {
+// long start = Long.MIN_VALUE + (rangePersstable * i);
+// if (randomIntervals.size() == totalTableCount)
+// insertIntervals = additionalIntervals;
+// if (additionalIntervals.size() == additionalIntervalsCount)
+// break;
+// Token startToken = new LongToken(start);
+// ByteBuffer startKey = ByteBuffer.allocate(16);
+// startKey.putLong(start).putLong(start).flip();
+// DecoratedKey startDK = new BufferDecoratedKey(startToken,
startKey);
+// Token endToken = new LongToken(start + rangePersstable);
+// ByteBuffer endKey = ByteBuffer.allocate(16);
+// endKey.putLong(start + rangePersstable).putLong(start +
rangePersstable).flip();
+// DecoratedKey endDK = new BufferDecoratedKey(endToken,
endKey);
+// insertIntervals.add(new Interval<>(startDK, endDK, null));
+// }
+// rangePersstable /= 10;
+// }
+// Collections.shuffle(randomIntervals);
+// Collections.shuffle(additionalIntervals);
+//
+// long min = Long.MAX_VALUE;
+// long max = Long.MIN_VALUE;
+// long total = 0;
+// logger.info("Testing interval tree 3 adding " +
additionalIntervals.size() + " intervals");
+// IntervalTree<PartitionPosition, Integer, Interval<PartitionPosition,
Integer>> tree3 = new IntervalTree<>(randomIntervals);
+// for (Interval<PartitionPosition, Integer> i : additionalIntervals)
+// {
+// for (byte b : bigArray)
+// checksum += b;
+// Stopwatch sw = Stopwatch.createStarted();
+// tree3.update(null, new Interval[] {i});
+// long elapsed = sw.elapsed(NANOSECONDS);
+// total += elapsed;
+// min = Math.min(min, elapsed);
+// max = Math.max (max, elapsed);
+// }
+// logger.info(format("tree 3 update average %.3f, min %.3f, max %.3f",
NANOSECONDS.toMicros(total / additionalIntervals.size()) / 1000.0,
NANOSECONDS.toMicros(min) / 1000.0, NANOSECONDS.toMicros(max) / 1000.0));
+//
+// logger.info("Testing leveled compaction building " +
randomIntervals.size() + " intervals");
+// long searchMin = Long.MAX_VALUE;
+// long searchMax = Long.MIN_VALUE;
+// long searchTotal = 0;
+// Token searchToken = new LongToken(0);
+// ByteBuffer searchKey =
ByteBuffer.allocate(16).putLong(0).putLong(0).flip();
+// DecoratedKey searchDK = new BufferDecoratedKey(searchToken,
searchKey);
+//
+// min = Long.MAX_VALUE;
+// max = Long.MIN_VALUE;
+// total = 0;
+// for (int i = 0 ; i < iterations; i++)
+// {
+// Stopwatch sw = Stopwatch.createStarted();
+// Object[] tree = buildBtree();
+// long elapsed = sw.elapsed(NANOSECONDS);
+// min = Math.min(min, elapsed);
+// max = Math.max(max, elapsed);
+// total += elapsed;
+// for (byte b : bigArray)
+// checksum += b;
+// sw = Stopwatch.createStarted();
+// List<Integer> result = IntervalBTree.<Object, Object, Object,
List<Integer>>accumulate(tree, , searchDK, (i1,i2,k,l) ->
{l.add((Integer)((Interval)k).data)}, null, null, new ArrayList<>());
+// long searchElapsed = sw.elapsed(NANOSECONDS);
+// searchMin = Math.min(searchMin, searchElapsed);
+// searchMax = Math.max(searchMax, searchElapsed);
+// searchTotal += searchElapsed;
+//// sw = Stopwatch.createStarted();
+//// tree.finish();
+//// System.out.println("Finishing took " +
sw.elapsed(TimeUnit.MILLISECONDS) + "ms");
+// }
+// logger.info(format("Legacy tree Average %.3f, min %.3f, max %.3f",
NANOSECONDS.toMicros(total / iterations) / 1000.0, NANOSECONDS.toMicros(min) /
1000.0, NANOSECONDS.toMicros(max) / 1000.0));
+// logger.info("Legacy tree search Average {}, min {}, max {}",
NANOSECONDS.toMicros(searchTotal / iterations),
NANOSECONDS.toMicros(searchMin), NANOSECONDS.toMicros(searchMax));
+//
+// logger.info("Testing random ranges");
+// randomIntervals = new ArrayList<>(new
HashSet<>(randomIntervals(range, 0, 100000)));
+//
+// min = Long.MAX_VALUE;
+// max = Long.MIN_VALUE;
+// total = 0;
+// logger.info("Testing interval tree 3 adding " +
additionalIntervals.size() + " intervals");
+// tree3 = new IntervalTree<>(randomIntervals);
+// for (Interval<PartitionPosition, Integer> i : additionalIntervals)
+// {
+// for (byte b : bigArray)
+// checksum += b;
+// Stopwatch sw = Stopwatch.createStarted();
+// tree3.update(null, new Interval[] {i});
+// long elapsed = sw.elapsed(NANOSECONDS);
+// total += elapsed;
+// min = Math.min(min, elapsed);
+// max = Math.max (max, elapsed);
+// }
+// logger.info(format("tree 3 update average %.3f, min %.3f, max %.3f",
NANOSECONDS.toMicros(total / additionalIntervals.size()) / 1000.0,
NANOSECONDS.toMicros(min) / 1000.0, NANOSECONDS.toMicros(max) / 1000.0));
+//
+// min = Long.MAX_VALUE;
+// max = Long.MIN_VALUE;
+// searchMin = Long.MAX_VALUE;
+// searchMax = Long.MIN_VALUE;
+// total = 0;
+// searchTotal = 0;
+// for (int i = 0 ; i < iterations; i++)
+// {
+// Stopwatch sw = Stopwatch.createStarted();
+// Object[] tree = buildBtree(randomIntervals)
+// IntervalTree<PartitionPosition, Integer,
Interval<PartitionPosition, Integer>> tree = new
LegacyIntervalTree<>(randomIntervals);
+// long elapsed = sw.elapsed(NANOSECONDS);
+// min = Math.min(min, elapsed);
+// max = Math.max(max, elapsed);
+// total += elapsed;
+// for (byte b : bigArray)
+// checksum += b;
+// sw = Stopwatch.createStarted();
+// List<Integer> result = tree.search(searchDK);
+// long searchElapsed = sw.elapsed(NANOSECONDS);
+// searchMin = Math.min(searchMin, searchElapsed);
+// searchMax = Math.max(searchMax, searchElapsed);
+// searchTotal += searchElapsed;
+//// sw = Stopwatch.createStarted();
+//// tree.finish();
+//// System.out.println("Finishing took " +
sw.elapsed(TimeUnit.MILLISECONDS) + "ms");
+// }
+// logger.info("Legacy tree Average {}, min {}, max {}",
NANOSECONDS.toMicros(total / iterations), NANOSECONDS.toMicros(min),
NANOSECONDS.toMicros(max));
+// logger.info("Checksum {}", checksum);
+// }
+//
+// private static Object[] buildBtree(List<Interval<PartitionPosition,
Integer>> intervals)
+// {
+// List<Interval<PartitionPosition, Integer>> sorted = new
ArrayList<>(intervals);
+// sorted.sort(Interval.minOrdering());
+// try (IntervalBTree.FastInteralTreeBuilder<Interval> builder =
(IntervalBTree.FastInteralTreeBuilder)
IntervalBTree.fastBuilder(Interval.maxOrdering()))
+// {
+// for (Interval interval : intervals)
+// builder.add(interval);
+// return builder.build();
+// }
+// }
+//}
\ No newline at end of file
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
