This is an automated email from the ASF dual-hosted git repository.
blambov 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 377e6aa04f Reverse cursor and iteration support for in-memory tries
377e6aa04f is described below
commit 377e6aa04fb67ea4220445988e85c9ebacb06db4
Author: Branimir Lambov <[email protected]>
AuthorDate: Wed Sep 25 14:28:55 2024 +0300
Reverse cursor and iteration support for in-memory tries
patch by Branimir Lambov; reviewed by Ariel Weisberg for CASSANDRA-19945
Co-authored-by: Michael J Marshall <[email protected]>
---
.../cassandra/db/tries/CollectionMergeTrie.java | 20 +-
.../org/apache/cassandra/db/tries/Direction.java | 168 ++++++++++
.../cassandra/db/tries/InMemoryReadTrie.java | 102 ++++--
.../apache/cassandra/db/tries/InMemoryTrie.java | 2 +-
.../org/apache/cassandra/db/tries/MergeTrie.java | 16 +-
.../apache/cassandra/db/tries/SingletonTrie.java | 2 +-
.../org/apache/cassandra/db/tries/SlicedTrie.java | 347 +++++++++++++++------
src/java/org/apache/cassandra/db/tries/Trie.java | 47 ++-
src/java/org/apache/cassandra/db/tries/Trie.md | 12 +-
.../cassandra/db/tries/TrieEntriesIterator.java | 8 +-
.../cassandra/db/tries/TrieValuesIterator.java | 2 +-
.../utils/bytecomparable/ByteComparable.md | 261 ++--------------
.../microbench/tries/InMemoryTrieReadBench.java | 8 +-
.../db/tries/CollectionMergeTrieTest.java | 16 +-
.../cassandra/db/tries/InMemoryTrieTestBase.java | 113 ++++---
.../apache/cassandra/db/tries/MergeTrieTest.java | 12 +-
.../apache/cassandra/db/tries/SlicedTrieTest.java | 17 +-
.../apache/cassandra/db/tries/TrieToDotTest.java | 3 +-
.../cassandra/db/tries/TrieToMermaidTest.java | 3 +-
.../bytecomparable/ByteSourceComparisonTest.java | 16 +-
20 files changed, 712 insertions(+), 463 deletions(-)
diff --git a/src/java/org/apache/cassandra/db/tries/CollectionMergeTrie.java
b/src/java/org/apache/cassandra/db/tries/CollectionMergeTrie.java
index 0336910494..aee5aef2c0 100644
--- a/src/java/org/apache/cassandra/db/tries/CollectionMergeTrie.java
+++ b/src/java/org/apache/cassandra/db/tries/CollectionMergeTrie.java
@@ -48,9 +48,9 @@ class CollectionMergeTrie<T> extends Trie<T>
}
@Override
- protected Cursor<T> cursor()
+ protected Cursor<T> cursor(Direction direction)
{
- return new CollectionMergeCursor<>(resolver, inputs);
+ return new CollectionMergeCursor<>(resolver, direction, inputs);
}
/**
@@ -58,13 +58,13 @@ class CollectionMergeTrie<T> extends Trie<T>
* - its depth is greater, or
* - its depth is equal, and the incoming transition is smaller.
*/
- static <T> boolean greaterCursor(Cursor<T> c1, Cursor<T> c2)
+ static <T> boolean greaterCursor(Direction direction, Cursor<T> c1,
Cursor<T> c2)
{
int c1depth = c1.depth();
int c2depth = c2.depth();
if (c1depth != c2depth)
return c1depth < c2depth;
- return c1.incomingTransition() > c2.incomingTransition();
+ return direction.lt(c2.incomingTransition(), c1.incomingTransition());
}
static <T> boolean equalCursor(Cursor<T> c1, Cursor<T> c2)
@@ -115,6 +115,7 @@ class CollectionMergeTrie<T> extends Trie<T>
static class CollectionMergeCursor<T> implements Cursor<T>
{
private final CollectionMergeResolver<T> resolver;
+ private final Direction direction;
/**
* The smallest cursor, tracked separately to improve performance in
single-source sections of the trie.
@@ -133,9 +134,10 @@ class CollectionMergeTrie<T> extends Trie<T>
*/
private final List<T> contents;
- public CollectionMergeCursor(CollectionMergeResolver<T> resolver,
Collection<? extends Trie<T>> inputs)
+ public CollectionMergeCursor(CollectionMergeResolver<T> resolver,
Direction direction, Collection<? extends Trie<T>> inputs)
{
this.resolver = resolver;
+ this.direction = direction;
int count = inputs.size();
// Get cursors for all inputs. Put one of them in head and the
rest in the heap.
heap = new Cursor[count - 1];
@@ -143,7 +145,7 @@ class CollectionMergeTrie<T> extends Trie<T>
int i = -1;
for (Trie<T> trie : inputs)
{
- Cursor<T> cursor = trie.cursor();
+ Cursor<T> cursor = trie.cursor(direction);
assert cursor.depth() == 0;
if (i >= 0)
heap[i] = cursor;
@@ -242,10 +244,10 @@ class CollectionMergeTrie<T> extends Trie<T>
if (next >= heap.length)
break;
// Select the smaller of the two children to push down to.
- if (next + 1 < heap.length && greaterCursor(heap[next],
heap[next + 1]))
+ if (next + 1 < heap.length && greaterCursor(direction,
heap[next], heap[next + 1]))
++next;
// If the child is greater or equal, the invariant has been
restored.
- if (!greaterCursor(item, heap[next]))
+ if (!greaterCursor(direction, item, heap[next]))
break;
heap[index] = heap[next];
index = next;
@@ -263,7 +265,7 @@ class CollectionMergeTrie<T> extends Trie<T>
{
int heap0Depth = heap[0].depth();
if (headDepth > heap0Depth ||
- (headDepth == heap0Depth && head.incomingTransition() <=
heap[0].incomingTransition()))
+ (headDepth == heap0Depth &&
direction.le(head.incomingTransition(), heap[0].incomingTransition())))
return headDepth; // head is still smallest
// otherwise we need to swap heap and heap[0]
diff --git a/src/java/org/apache/cassandra/db/tries/Direction.java
b/src/java/org/apache/cassandra/db/tries/Direction.java
new file mode 100644
index 0000000000..fc589b8f1a
--- /dev/null
+++ b/src/java/org/apache/cassandra/db/tries/Direction.java
@@ -0,0 +1,168 @@
+/*
+ * 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.db.tries;
+
+/**
+ * Class used to specify the direction of iteration. Provides methods used to
replace comparisons and values in typical
+ * loops and allow code to be written without explicit direction checks.
+ * <p>
+ * For example, iterating between l and r inclusive in forward direction is
usually done as<br/>
+ * {@code for (int i = l; i <= r; ++i) ...}
+ * <p>
+ * To loop over them in the specified direction dir, the loop above would
change to<br/>
+ * {@code for (int i = dir.select(l, r); dir.inLoop(i, l, r); i +=
dir.increase) ...}
+ */
+public enum Direction
+{
+ FORWARD(1)
+ {
+ public boolean inLoop(int index, int left, int right)
+ {
+ return index <= right;
+ }
+
+ public boolean lt(int a, int b)
+ {
+ return a < b;
+ }
+
+ public boolean le(int a, int b)
+ {
+ return a <= b;
+ }
+
+ public int min(int a, int b)
+ {
+ return Math.min(a, b);
+ }
+
+ public int max(int a, int b)
+ {
+ return Math.max(a, b);
+ }
+
+ public <T> T select(T forward, T reverse)
+ {
+ return forward;
+ }
+
+ public int select(int forward, int reverse)
+ {
+ return forward;
+ }
+
+ public boolean isForward()
+ {
+ return true;
+ }
+
+ public Direction opposite()
+ {
+ return REVERSE;
+ }
+ },
+ REVERSE(-1)
+ {
+ public boolean inLoop(int index, int left, int right)
+ {
+ return index >= left;
+ }
+
+ public boolean lt(int a, int b)
+ {
+ return a > b;
+ }
+
+ public boolean le(int a, int b)
+ {
+ return a >= b;
+ }
+
+ public int min(int a, int b)
+ {
+ return Math.max(a, b);
+ }
+
+ public int max(int a, int b)
+ {
+ return Math.min(a, b);
+ }
+
+ public <T> T select(T forward, T reverse)
+ {
+ return reverse;
+ }
+
+ public int select(int forward, int reverse)
+ {
+ return reverse;
+ }
+
+ public boolean isForward()
+ {
+ return false;
+ }
+
+ public Direction opposite()
+ {
+ return FORWARD;
+ }
+ };
+
+ /** Value that needs to be added to advance the iteration, i.e. value
corresponding to 1 */
+ public final int increase;
+
+ Direction(int increase)
+ {
+ this.increase = increase;
+ }
+
+ /** Returns the result of the operation corresponding to a < b for the
forward direction */
+ public abstract boolean lt(int a, int b);
+ /** Returns the result of the operation corresponding to a ≤ b for the
forward direction */
+ public abstract boolean le(int a, int b);
+ /** Returns the result of the operation corresponding to min(a, b) for the
forward direction */
+ public abstract int min(int a, int b);
+ /** Returns the result of the operation corresponding to max(a, b) for the
forward direction */
+ public abstract int max(int a, int b);
+
+ /**
+ * Use the first argument in forward direction and the second in reverse,
i.e. isForward() ? forward : reverse.
+ */
+ public abstract <T> T select(T forward, T reverse);
+
+ /**
+ * Use the first argument in forward direction and the second in reverse,
i.e. isForward() ? forward : reverse.
+ */
+ public abstract int select(int forward, int reverse);
+
+ /**
+ * Helper to perform loops over possible values in the given direction.
Returns whether the given index is still
+ * within bounds when iterating.
+ * <p>
+ * {@code for} loops implemented as<br/>
+ * {@code for (int i = dir.select(l, r); dir.inLoop(i, l, r); i +=
dir.increase) ...}<br/>
+ * will iterate over all values between l and r inclusive in the specified
direction.
+ */
+ public abstract boolean inLoop(int index, int left, int right);
+
+ public abstract boolean isForward();
+
+ public abstract Direction opposite();
+}
diff --git a/src/java/org/apache/cassandra/db/tries/InMemoryReadTrie.java
b/src/java/org/apache/cassandra/db/tries/InMemoryReadTrie.java
index 88f5987a33..863b11a9f4 100644
--- a/src/java/org/apache/cassandra/db/tries/InMemoryReadTrie.java
+++ b/src/java/org/apache/cassandra/db/tries/InMemoryReadTrie.java
@@ -542,10 +542,12 @@ public class InMemoryReadTrie<T> extends Trie<T>
private int currentNode;
private int incomingTransition;
private T content;
- private int depth = -1;
+ private final Direction direction;
+ int depth = -1;
- MemtableCursor()
+ MemtableCursor(Direction direction)
{
+ this.direction = direction;
descendInto(root, -1);
}
@@ -624,7 +626,7 @@ public class InMemoryReadTrie<T> extends Trie<T>
case SPLIT_OFFSET:
return descendInSplitSublevel(node,
SPLIT_START_LEVEL_LIMIT, 0, SPLIT_LEVEL_SHIFT * 2);
case SPARSE_OFFSET:
- return nextValidSparseTransition(node,
getUnsignedShort(node + SPARSE_ORDER_OFFSET));
+ return nextValidSparseTransition(node,
prepareOrderWord(node));
default:
return getChainTransition(node);
}
@@ -657,7 +659,7 @@ public class InMemoryReadTrie<T> extends Trie<T>
* @param shift This level's bit shift (6 for start, 3 for mid and 0
for tail).
* @return the depth reached after descending.
*/
- private int descendInSplitSublevel(int node, int limit, int collected,
int shift)
+ int descendInSplitSublevel(int node, int limit, int collected, int
shift)
{
while (true)
{
@@ -665,7 +667,9 @@ public class InMemoryReadTrie<T> extends Trie<T>
int childIndex;
int child = NONE;
// find the first non-null child
- for (childIndex = 0; childIndex < limit; ++childIndex)
+ for (childIndex = direction.select(0, limit - 1);
+ direction.inLoop(childIndex, 0, limit - 1);
+ childIndex += direction.increase)
{
child = getSplitBlockPointer(node, childIndex, limit);
if (!isNull(child))
@@ -693,11 +697,11 @@ public class InMemoryReadTrie<T> extends Trie<T>
/**
* Backtrack to a split sub-level. The level is identified by the
lowest non-0 bits in trans.
*/
- private int nextValidSplitTransition(int node, int trans)
+ int nextValidSplitTransition(int node, int trans)
{
assert trans >= 0 && trans <= 0xFF;
int childIndex = splitNodeChildIndex(trans);
- if (childIndex > 0)
+ if (childIndex != direction.select(0, SPLIT_OTHER_LEVEL_LIMIT - 1))
{
maybeAddSplitBacktrack(node,
childIndex,
@@ -708,7 +712,7 @@ public class InMemoryReadTrie<T> extends Trie<T>
return descendInto(child, trans);
}
int tailIndex = splitNodeTailIndex(trans);
- if (tailIndex > 0)
+ if (tailIndex != direction.select(0, SPLIT_OTHER_LEVEL_LIMIT - 1))
{
maybeAddSplitBacktrack(node,
tailIndex,
@@ -718,11 +722,11 @@ public class InMemoryReadTrie<T> extends Trie<T>
int tail = getSplitBlockPointer(node, tailIndex,
SPLIT_OTHER_LEVEL_LIMIT);
return descendInSplitSublevel(tail,
SPLIT_OTHER_LEVEL_LIMIT,
- trans,
+ trans & -(1 << SPLIT_LEVEL_SHIFT
* 1),
SPLIT_LEVEL_SHIFT * 0);
}
int midIndex = splitNodeMidIndex(trans);
- assert midIndex > 0;
+ assert midIndex != direction.select(0, SPLIT_START_LEVEL_LIMIT -
1);
maybeAddSplitBacktrack(node,
midIndex,
SPLIT_START_LEVEL_LIMIT,
@@ -731,7 +735,7 @@ public class InMemoryReadTrie<T> extends Trie<T>
int mid = getSplitBlockPointer(node, midIndex,
SPLIT_START_LEVEL_LIMIT);
return descendInSplitSublevel(mid,
SPLIT_OTHER_LEVEL_LIMIT,
- trans,
+ trans & -(1 << SPLIT_LEVEL_SHIFT *
2),
SPLIT_LEVEL_SHIFT * 1);
}
@@ -741,15 +745,26 @@ public class InMemoryReadTrie<T> extends Trie<T>
private void maybeAddSplitBacktrack(int node, int startAfter, int
limit, int collected, int shift)
{
int nextChildIndex;
- for (nextChildIndex = startAfter + 1; nextChildIndex < limit;
++nextChildIndex)
+ for (nextChildIndex = startAfter + direction.increase;
+ direction.inLoop(nextChildIndex, 0, limit - 1);
+ nextChildIndex += direction.increase)
{
if (!isNull(getSplitBlockPointer(node, nextChildIndex, limit)))
break;
}
- if (nextChildIndex < limit)
- addBacktrack(node, collected | (nextChildIndex << shift),
depth);
+ if (direction.inLoop(nextChildIndex, 0, limit - 1))
+ {
+ if (direction.isForward())
+ addBacktrack(node, collected | (nextChildIndex << shift),
depth);
+ else
+ {
+ // The (((x + 1) << shift) - 1) adjustment will put all 1s
in all lower bits
+ addBacktrack(node, collected | ((((nextChildIndex + 1) <<
shift)) - 1), depth);
+ }
+ }
}
+
private int nextValidSparseTransition(int node, int data)
{
UnsafeBuffer chunk = getChunk(node);
@@ -760,7 +775,7 @@ public class InMemoryReadTrie<T> extends Trie<T>
data = data / SPARSE_CHILD_COUNT;
// If there are remaining transitions, add backtracking entry.
- if (data > 0)
+ if (data != exhaustedOrderWord())
addBacktrack(node, data, depth);
// Follow the transition.
@@ -769,6 +784,53 @@ public class InMemoryReadTrie<T> extends Trie<T>
return descendInto(child, transition);
}
+ /**
+ * Prepare the sparse node order word for iteration. For forward
iteration, this means just reading it.
+ * For reverse, we also invert the data so that the peeling code above
still works.
+ */
+ int prepareOrderWord(int node)
+ {
+ int fwdState = getUnsignedShort(node + SPARSE_ORDER_OFFSET);
+ if (direction.isForward())
+ return fwdState;
+ else
+ {
+ // Produce an inverted state word.
+
+ // One subtlety is that in forward order we know we can
terminate the iteration when the state becomes
+ // 0 because 0 cannot be the largest child (we enforce 10
order for the first two children and then can
+ // only insert other digits in the word, thus 0 is always
preceded by a 1 (not necessarily immediately)
+ // in the order word) and thus we can't confuse a completed
iteration with one that still has the child
+ // at 0 to present.
+ // In reverse order 0 can be the last child that needs to be
iterated (e.g. for two children the order
+ // word is always 10, which is 01 inverted; if we treat it
exactly as the forward iteration, we will
+ // only list child 1 because we will interpret the state 0
after peeling the first digit as a completed
+ // iteration). To know when to stop we must thus use a
different marker - since we know 1 is never the
+ // last child to be iterated in reverse order (because it is
preceded by a 0 in the reversed order
+ // word), we can use another 1 as the termination marker. The
generated number may not fit a 16-bit word
+ // any more, but that does not matter as we don't need to
store it.
+ // For example, the code below translates 120 to 1021, and to
iterate we peel the lower order digits
+ // until the iteration state becomes just 1.
+
+ int revState = 1; // 1 can't be the smallest child
+ while (fwdState != 0)
+ {
+ revState = revState * SPARSE_CHILD_COUNT + fwdState %
SPARSE_CHILD_COUNT;
+ fwdState /= SPARSE_CHILD_COUNT;
+ }
+
+ return revState;
+ }
+ }
+
+ /**
+ * Returns the state which marks the exhaustion of the order word.
+ */
+ int exhaustedOrderWord()
+ {
+ return direction.select(0, 1);
+ }
+
private int getChainTransition(int node)
{
// No backtracking needed.
@@ -782,7 +844,7 @@ public class InMemoryReadTrie<T> extends Trie<T>
return descendInto(chunk.getInt(inChunkNode + 1), transition);
}
- private int descendInto(int child, int transition)
+ int descendInto(int child, int transition)
{
++depth;
incomingTransition = transition;
@@ -791,7 +853,7 @@ public class InMemoryReadTrie<T> extends Trie<T>
return depth;
}
- private int descendIntoChain(int child, int transition)
+ int descendIntoChain(int child, int transition)
{
++depth;
incomingTransition = transition;
@@ -806,9 +868,9 @@ public class InMemoryReadTrie<T> extends Trie<T>
return !isNullOrLeaf(node) && offset(node) <= CHAIN_MAX_OFFSET;
}
- public MemtableCursor cursor()
+ public MemtableCursor cursor(Direction direction)
{
- return new MemtableCursor();
+ return new MemtableCursor(direction);
}
/*
@@ -847,7 +909,7 @@ public class InMemoryReadTrie<T> extends Trie<T>
@Override
public String dump(Function<T, String> contentToString)
{
- MemtableCursor source = cursor();
+ MemtableCursor source = cursor(Direction.FORWARD);
class TypedNodesCursor implements Cursor<String>
{
@Override
diff --git a/src/java/org/apache/cassandra/db/tries/InMemoryTrie.java
b/src/java/org/apache/cassandra/db/tries/InMemoryTrie.java
index 9bda82057f..7ba7a0ae1c 100644
--- a/src/java/org/apache/cassandra/db/tries/InMemoryTrie.java
+++ b/src/java/org/apache/cassandra/db/tries/InMemoryTrie.java
@@ -821,7 +821,7 @@ public class InMemoryTrie<T> extends InMemoryReadTrie<T>
*/
public <U> void apply(Trie<U> mutation, final UpsertTransformer<T, U>
transformer) throws SpaceExhaustedException
{
- Cursor<U> mutationCursor = mutation.cursor();
+ Cursor<U> mutationCursor = mutation.cursor(Direction.FORWARD);
assert mutationCursor.depth() == 0 : "Unexpected non-fresh cursor.";
ApplyState state = applyState;
state.reset();
diff --git a/src/java/org/apache/cassandra/db/tries/MergeTrie.java
b/src/java/org/apache/cassandra/db/tries/MergeTrie.java
index f280776984..39597afd54 100644
--- a/src/java/org/apache/cassandra/db/tries/MergeTrie.java
+++ b/src/java/org/apache/cassandra/db/tries/MergeTrie.java
@@ -44,25 +44,27 @@ class MergeTrie<T> extends Trie<T>
}
@Override
- protected Cursor<T> cursor()
+ protected Cursor<T> cursor(Direction direction)
{
- return new MergeCursor<>(resolver, t1, t2);
+ return new MergeCursor<>(resolver, direction, t1, t2);
}
static class MergeCursor<T> implements Cursor<T>
{
private final MergeResolver<T> resolver;
+ private final Direction direction;
private final Cursor<T> c1;
private final Cursor<T> c2;
boolean atC1;
boolean atC2;
- MergeCursor(MergeResolver<T> resolver, Trie<T> t1, Trie<T> t2)
+ MergeCursor(MergeResolver<T> resolver, Direction direction, Trie<T>
t1, Trie<T> t2)
{
this.resolver = resolver;
- this.c1 = t1.cursor();
- this.c2 = t2.cursor();
+ this.direction = direction;
+ this.c1 = t1.cursor(direction);
+ this.c2 = t2.cursor(direction);
assert c1.depth() == 0;
assert c2.depth() == 0;
atC1 = atC2 = true;
@@ -116,8 +118,8 @@ class MergeTrie<T> extends Trie<T>
// c1depth == c2depth
int c1trans = c1.incomingTransition();
int c2trans = c2.incomingTransition();
- atC1 = c1trans <= c2trans;
- atC2 = c1trans >= c2trans;
+ atC1 = direction.le(c1trans, c2trans);
+ atC2 = direction.le(c2trans, c1trans);
return c1depth;
}
diff --git a/src/java/org/apache/cassandra/db/tries/SingletonTrie.java
b/src/java/org/apache/cassandra/db/tries/SingletonTrie.java
index 0336a851ff..980f85f074 100644
--- a/src/java/org/apache/cassandra/db/tries/SingletonTrie.java
+++ b/src/java/org/apache/cassandra/db/tries/SingletonTrie.java
@@ -34,7 +34,7 @@ class SingletonTrie<T> extends Trie<T>
this.value = value;
}
- public Cursor cursor()
+ public Cursor cursor(Direction direction)
{
return new Cursor();
}
diff --git a/src/java/org/apache/cassandra/db/tries/SlicedTrie.java
b/src/java/org/apache/cassandra/db/tries/SlicedTrie.java
index 75ae3df27e..0bd14899cb 100644
--- a/src/java/org/apache/cassandra/db/tries/SlicedTrie.java
+++ b/src/java/org/apache/cassandra/db/tries/SlicedTrie.java
@@ -61,151 +61,279 @@ public class SlicedTrie<T> extends Trie<T>
this.includeRight = includeRight;
}
+ static ByteSource add0(ByteSource src)
+ {
+ return new ByteSource()
+ {
+ boolean done = false;
+
+ @Override
+ public int next()
+ {
+ if (done)
+ return END_OF_STREAM;
+ int next = src.next();
+ if (next != END_OF_STREAM)
+ return next;
+ done = true;
+ return 0;
+ }
+ };
+ }
+
+ static ByteSource openAndMaybeAdd0(ByteComparable key, boolean shouldAdd0)
+ {
+ if (key == null)
+ return null;
+ ByteSource src = key.asComparableBytes(Trie.BYTE_COMPARABLE_VERSION);
+ if (shouldAdd0)
+ return add0(src);
+ else
+ return src;
+ }
+
@Override
- protected Cursor<T> cursor()
+ protected Cursor<T> cursor(Direction direction)
+ {
+ // The cursor is left-inclusive and right-exclusive by default. If we
need to change the inclusiveness, adjust
+ // the bound to the next possible value by adding a 00 byte at the end.
+ ByteSource leftSource = openAndMaybeAdd0(left, !includeLeft);
+ ByteSource rightSource = openAndMaybeAdd0(right, includeRight);
+
+ // Empty left bound is the same as having no left bound, adjust for
that.
+ int leftNext = -1;
+ if (leftSource != null)
+ {
+ leftNext = leftSource.next();
+ if (leftNext == ByteSource.END_OF_STREAM)
+ leftSource = null;
+ }
+
+ // Empty right bound means the result can only be empty. Make things
easier for the cursor by handling this.
+ int rightNext = -1;
+ if (rightSource != null)
+ {
+ rightNext = rightSource.next();
+ if (rightNext == ByteSource.END_OF_STREAM)
+ {
+ assert leftSource == null : "Invalid range " + sliceString();
+ return Trie.<T>empty().cursor(direction);
+ }
+ }
+
+ return new SlicedCursor<>(source.cursor(direction),
+ leftSource,
+ leftNext,
+ rightSource,
+ rightNext,
+ direction);
+ }
+
+ String sliceString()
{
- return new SlicedCursor<>(this);
+ return String.format("%s%s;%s%s",
+ includeLeft ? "[" : "(",
+
left.byteComparableAsString(Trie.BYTE_COMPARABLE_VERSION),
+
right.byteComparableAsString(Trie.BYTE_COMPARABLE_VERSION),
+ includeRight ? "]" : ")");
}
private enum State
{
- /** The cursor is still positioned on some prefix of the left bound.
Content should not be produced. */
- BEFORE_LEFT,
- /** The cursor is positioned inside the range, i.e. beyond the left
bound, possibly on a prefix of the right. */
+ /**
+ * The cursor is at the initial phase while it is walking prefixes of
both bounds.
+ * Content is not to be reported.
+ */
+ COMMON_PREFIX,
+ /**
+ * The cursor is positioned on some prefix of the start bound,
strictly before any prefix of the end bound in
+ * iteration order.
+ * Content should only be reported in the reverse direction (as these
prefixes are prefixes of the right bound
+ * and included in the slice).
+ */
+ START_PREFIX,
+ /**
+ * The cursor is positioned inside the range, i.e. strictly between
any prefixes of the start and end bounds.
+ * All content should be reported.
+ */
INSIDE,
- /** The cursor is positioned beyond the right bound. Exhaustion (depth
-1) has been reported. */
- AFTER_RIGHT
+ /**
+ * The cursor is positioned on some prefix of the end bound, strictly
after any prefix of the start bound.
+ * Content should only be reported in the forward direction.
+ */
+ END_PREFIX,
+ /** The cursor is positioned beyond the end bound. Exhaustion (depth
-1) has been reported. */
+ EXHAUSTED;
}
private static class SlicedCursor<T> implements Cursor<T>
{
- private final ByteSource left;
- private final ByteSource right;
- private final boolean includeLeft;
- private final boolean excludeRight;
+ private final ByteSource start;
+ private final ByteSource end;
private final Cursor<T> source;
+ private final Direction direction;
private State state;
- private int leftNext;
- private int leftNextDepth;
- private int rightNext;
- private int rightNextDepth;
+ private int startNext;
+ private int startNextDepth;
+ private int endNext;
+ private int endNextDepth;
- public SlicedCursor(SlicedTrie<T> slicedTrie)
+ public SlicedCursor(Cursor<T> source,
+ ByteSource leftSource,
+ int leftNext,
+ ByteSource rightSource,
+ int rightNext,
+ Direction direction)
{
- source = slicedTrie.source.cursor();
- if (slicedTrie.left != null)
- {
- left =
slicedTrie.left.asComparableBytes(BYTE_COMPARABLE_VERSION);
- includeLeft = slicedTrie.includeLeft;
- leftNext = left.next();
- leftNextDepth = 1;
- if (leftNext == ByteSource.END_OF_STREAM && includeLeft)
- state = State.INSIDE;
- else
- state = State.BEFORE_LEFT;
- }
- else
- {
- left = null;
- includeLeft = true;
- state = State.INSIDE;
- }
-
- if (slicedTrie.right != null)
- {
- right =
slicedTrie.right.asComparableBytes(BYTE_COMPARABLE_VERSION);
- excludeRight = !slicedTrie.includeRight;
- rightNext = right.next();
- rightNextDepth = 1;
- if (rightNext == ByteSource.END_OF_STREAM && excludeRight)
- state = State.BEFORE_LEFT; // This is a hack, we are
after the right bound but we don't want to
- // report depth -1 yet. So
just make sure root's content is not reported.
- }
- else
- {
- right = null;
- excludeRight = true;
- rightNextDepth = 0;
- }
+ this.source = source;
+ this.direction = direction;
+ start = direction.select(leftSource, rightSource);
+ end = direction.select(rightSource, leftSource);
+ startNext = direction.select(leftNext, rightNext);
+ endNext = direction.select(rightNext, leftNext);
+ startNextDepth = start != null ? 1 : 0;
+ endNextDepth = end != null ? 1 : 0;
+ state = start != null
+ ? end != null
+ ? State.COMMON_PREFIX
+ : State.START_PREFIX
+ : end != null
+ ? State.END_PREFIX
+ : State.INSIDE;
}
@Override
public int advance()
{
- assert (state != State.AFTER_RIGHT);
-
int newDepth = source.advance();
int transition = source.incomingTransition();
- if (state == State.BEFORE_LEFT)
+ switch (state)
{
- // Skip any transitions before the left bound
- while (newDepth == leftNextDepth && transition < leftNext)
- {
- newDepth = source.skipChildren();
- transition = source.incomingTransition();
- }
+ case COMMON_PREFIX:
+ case START_PREFIX:
+ // Skip any transitions before the start bound
+ while (newDepth == startNextDepth &&
direction.lt(transition, startNext))
+ {
+ newDepth = source.skipChildren();
+ transition = source.incomingTransition();
+ }
- // Check if we are still following the left bound
- if (newDepth == leftNextDepth && transition == leftNext)
- {
- assert leftNext != ByteSource.END_OF_STREAM;
- leftNext = left.next();
- ++leftNextDepth;
- if (leftNext == ByteSource.END_OF_STREAM && includeLeft)
- state = State.INSIDE; // report the content on the
left bound
- }
- else // otherwise we are beyond it
- state = State.INSIDE;
+ // Check if we are still following the start bound
+ if (newDepth == startNextDepth && transition == startNext)
+ {
+ assert startNext != ByteSource.END_OF_STREAM;
+ startNext = start.next();
+ ++startNextDepth;
+ State currState = state;
+ // In the forward direction the exact match for the
left bound and all descendant states are
+ // included in the set.
+ // In the reverse direction we will instead use the -1
as target transition and thus ascend on
+ // the next advance (skipping the exact right bound
and all its descendants).
+ if (startNext == ByteSource.END_OF_STREAM &&
direction.isForward())
+ state = State.INSIDE; // checkEndBound may adjust
this to END_PREFIX
+ if (currState == State.START_PREFIX)
+ return newDepth; // there is no need to check
the end bound as we descended along a
+ // strictly earlier path
+ }
+ else // otherwise we are beyond the start bound
+ state = State.INSIDE; // checkEndBound may adjust this
to END_PREFIX
+ // pass through
+ case INSIDE:
+ case END_PREFIX:
+ return checkEndBound(newDepth, transition);
+ default:
+ throw new AssertionError();
}
-
- return checkRightBound(newDepth, transition);
}
private int markDone()
{
- state = State.AFTER_RIGHT;
+ state = State.EXHAUSTED;
return -1;
}
- private int checkRightBound(int newDepth, int transition)
+ private int checkEndBound(int newDepth, int transition)
{
// Cursor positions compare by depth descending and transition
ascending.
- if (newDepth > rightNextDepth)
- return newDepth;
- if (newDepth < rightNextDepth)
+ if (newDepth > endNextDepth)
+ return newDepth; // happy and quick path in the interior of
the slice
+ // (state == State.INSIDE can be asserted
here (we skip it for efficiency))
+ if (newDepth < endNextDepth)
return markDone();
- // newDepth == rightDepth
- if (transition < rightNext)
+ // newDepth == endDepth
+ if (direction.lt(transition, endNext))
+ {
+ adjustStateStrictlyBeforeEnd();
return newDepth;
- if (transition > rightNext)
+ }
+ if (direction.lt(endNext, transition))
return markDone();
- // Following right bound
- rightNext = right.next();
- ++rightNextDepth;
- if (rightNext == ByteSource.END_OF_STREAM && excludeRight)
- return markDone(); // do not report any content on the right
bound
+ // Following end bound
+ endNext = end.next();
+ ++endNextDepth;
+ if (endNext == ByteSource.END_OF_STREAM)
+ {
+ // At the exact end bound.
+ if (direction.isForward())
+ {
+ // In forward direction the right bound is not included in
the slice.
+ return markDone();
+ }
+ else
+ {
+ // In reverse, the left bound and all its descendants are
included, thus we use the -1 as limiting
+ // transition. We can also see the bound as strictly ahead
of our current position as the current
+ // branch should be fully included.
+ adjustStateStrictlyBeforeEnd();
+ }
+ }
+ else
+ adjustStateAtEndPrefix();
return newDepth;
}
+ private void adjustStateAtEndPrefix()
+ {
+ switch (state)
+ {
+ case INSIDE:
+ state = State.END_PREFIX;
+ break;
+ }
+ }
+
+ private void adjustStateStrictlyBeforeEnd()
+ {
+ switch (state)
+ {
+ case COMMON_PREFIX:
+ state = State.START_PREFIX;
+ break;
+ case END_PREFIX:
+ state = State.INSIDE;
+ break;
+ }
+ }
+
@Override
public int advanceMultiple(TransitionsReceiver receiver)
{
switch (state)
{
- case BEFORE_LEFT:
+ case COMMON_PREFIX:
+ case START_PREFIX:
+ case END_PREFIX:
return advance(); // descend only one level to be able
to compare cursors correctly
case INSIDE:
int depth = source.depth();
- if (depth == rightNextDepth - 1) // this is possible
because right is already advanced;
- return advance(); // we need to check next byte
against right boundary in this case
int newDepth = source.advanceMultiple(receiver);
if (newDepth > depth)
- return newDepth; // successfully advanced
+ return newDepth; // successfully descended
// we ascended, check if we are still within boundaries
- return checkRightBound(newDepth,
source.incomingTransition());
+ return checkEndBound(newDepth,
source.incomingTransition());
default:
throw new AssertionError();
}
@@ -214,17 +342,27 @@ public class SlicedTrie<T> extends Trie<T>
@Override
public int skipChildren()
{
- assert (state != State.AFTER_RIGHT);
-
- // We are either inside or following the left bound. In the latter
case ascend takes us beyond it.
- state = State.INSIDE;
- return checkRightBound(source.skipChildren(),
source.incomingTransition());
+ switch (state)
+ {
+ case START_PREFIX:
+ // Skipping children takes us beyond the start path.
+ state = State.INSIDE;
+ case INSIDE:
+ // Check that we are still inside after we skip.
+ return checkEndBound(source.skipChildren(),
source.incomingTransition());
+ case COMMON_PREFIX:
+ case END_PREFIX:
+ // The skip takes us beyond the end bound; we are done.
+ return markDone();
+ default:
+ throw new AssertionError();
+ }
}
@Override
public int depth()
{
- return state == State.AFTER_RIGHT ? -1 : source.depth();
+ return state == State.EXHAUSTED ? -1 : source.depth();
}
@Override
@@ -236,7 +374,20 @@ public class SlicedTrie<T> extends Trie<T>
@Override
public T content()
{
- return state == State.INSIDE ? source.content() : null;
+ switch (state)
+ {
+ case INSIDE:
+ return source.content();
+ // Additionally, prefixes of the right bound (which are not
prefixes of the left) need to be reported:
+ case START_PREFIX:
+ // start prefixes in reverse direction (but making sure we
don't report the exact match);
+ return !direction.isForward() && startNext !=
ByteSource.END_OF_STREAM ? source.content() : null;
+ case END_PREFIX:
+ // end prefixes in forward direction.
+ return direction.isForward() ? source.content() : null;
+ default:
+ return null;
+ }
}
}
}
diff --git a/src/java/org/apache/cassandra/db/tries/Trie.java
b/src/java/org/apache/cassandra/db/tries/Trie.java
index a139e08e67..7f02e154e0 100644
--- a/src/java/org/apache/cassandra/db/tries/Trie.java
+++ b/src/java/org/apache/cassandra/db/tries/Trie.java
@@ -133,6 +133,12 @@ public abstract class Trie<T>
* (2, i)+ < (-1, -1) wi cursors not equal, advance smaller
(2 > -1)
* (3, n)+ < (-1, -1) win* cursors not equal, advance smaller
(3 > -1)
* (-1, -1) (-1, -1) both exhasted
+ *
+ * Cursors are created with a direction (forward or reverse), which
specifies the order in which a node's children
+ * are iterated (smaller first or larger first). Note that entries
returned in reverse direction are in
+ * lexicographic order for the inverted alphabet, which is not the same as
being presented in reverse. For example,
+ * a cursor for a trie containing "ab", "abc" and "cba", will visit the
nodes in order "cba", "ab", "abc", i.e.
+ * prefixes will still be reported before their descendants.
*/
protected interface Cursor<T>
{
@@ -232,7 +238,7 @@ public abstract class Trie<T>
int skipChildren();
}
- protected abstract Cursor<T> cursor();
+ protected abstract Cursor<T> cursor(Direction direction);
/**
* Used by {@link Cursor#advanceMultiple} to feed the transitions taken.
@@ -318,15 +324,24 @@ public abstract class Trie<T>
*/
public void forEachValue(ValueConsumer<T> consumer)
{
- process(consumer);
+ process(consumer, Direction.FORWARD);
}
+
/**
* Call the given consumer on all (path, content) pairs with non-null
content in the trie in order.
*/
public void forEachEntry(BiConsumer<ByteComparable, T> consumer)
{
- process(new TrieEntriesWalker.WithConsumer<T>(consumer));
+ forEachEntry(Direction.FORWARD, consumer);
+ }
+
+ /**
+ * Call the given consumer on all (path, content) pairs with non-null
content in the trie in order.
+ */
+ public void forEachEntry(Direction direction, BiConsumer<ByteComparable,
T> consumer)
+ {
+ process(new TrieEntriesWalker.WithConsumer<T>(consumer), direction);
// Note: we can't do the ValueConsumer trick here, because the
implementation requires state and cannot be
// implemented with default methods alone.
}
@@ -334,9 +349,9 @@ public abstract class Trie<T>
/**
* Process the trie using the given Walker.
*/
- public <R> R process(Walker<T, R> walker)
+ public <R> R process(Walker<T, R> walker, Direction direction)
{
- return process(walker, cursor());
+ return process(walker, cursor(direction));
}
static <T, R> R process(Walker<T, R> walker, Cursor<T> cursor)
@@ -367,7 +382,7 @@ public abstract class Trie<T>
*/
public String dump(Function<T, String> contentToString)
{
- return process(new TrieDumper<>(contentToString));
+ return process(new TrieDumper<>(contentToString), Direction.FORWARD);
}
/**
@@ -427,12 +442,28 @@ public abstract class Trie<T>
return this::entryIterator;
}
+ /**
+ * Returns the ordered entry set of this trie's content as an iterable.
+ */
+ public Iterable<Map.Entry<ByteComparable, T>> entrySet(Direction direction)
+ {
+ return () -> entryIterator(direction);
+ }
+
/**
* Returns the ordered entry set of this trie's content in an iterator.
*/
public Iterator<Map.Entry<ByteComparable, T>> entryIterator()
{
- return new TrieEntriesIterator.AsEntries<>(this);
+ return entryIterator(Direction.FORWARD);
+ }
+
+ /**
+ * Returns the ordered entry set of this trie's content in an iterator.
+ */
+ public Iterator<Map.Entry<ByteComparable, T>> entryIterator(Direction
direction)
+ {
+ return new TrieEntriesIterator.AsEntries<>(this, direction);
}
/**
@@ -580,7 +611,7 @@ public abstract class Trie<T>
private static final Trie<Object> EMPTY = new Trie<Object>()
{
- protected Cursor<Object> cursor()
+ protected Cursor<Object> cursor(Direction direction)
{
return new Cursor<Object>()
{
diff --git a/src/java/org/apache/cassandra/db/tries/Trie.md
b/src/java/org/apache/cassandra/db/tries/Trie.md
index 4265871e7b..81999b9db2 100644
--- a/src/java/org/apache/cassandra/db/tries/Trie.md
+++ b/src/java/org/apache/cassandra/db/tries/Trie.md
@@ -249,4 +249,14 @@ implicit representation using a pair of `depth` and
`incomingTransition` for eac
In slices we can also use `advanceMultiple` when we are certain to be strictly
inside the slice, i.e. beyond the
left bound and before a prefix of the right bound. As above, descending to any
depth in this case is safe as the
-result will remain smaller than the right bound.
\ No newline at end of file
+result will remain smaller than the right bound.
+
+## Reverse iteration
+
+Tries and trie cursors support reverse iteration. Reverse trie iteration
presents data in lexicographic order
+using the inverted alphabet. This is not always the same as the reverse order
of the data returned in the forward
+direction; the latter is only guaranteed if the entries in the trie can
contain no prefixes (i.e. the representation
+is prefix-free like the byte-ordered type translations).
+
+This difference is imposed by the cursor interfaces which necessarily have to
present parent nodes before their
+children and do not preserve or present any state on ascent.
\ No newline at end of file
diff --git a/src/java/org/apache/cassandra/db/tries/TrieEntriesIterator.java
b/src/java/org/apache/cassandra/db/tries/TrieEntriesIterator.java
index 7ab3e7de46..c46b2073ee 100644
--- a/src/java/org/apache/cassandra/db/tries/TrieEntriesIterator.java
+++ b/src/java/org/apache/cassandra/db/tries/TrieEntriesIterator.java
@@ -33,9 +33,9 @@ public abstract class TrieEntriesIterator<T, V> extends
TriePathReconstructor im
T next;
boolean gotNext;
- protected TrieEntriesIterator(Trie<T> trie)
+ protected TrieEntriesIterator(Trie<T> trie, Direction direction)
{
- cursor = trie.cursor();
+ cursor = trie.cursor(direction);
assert cursor.depth() == 0;
next = cursor.content();
gotNext = next != null;
@@ -67,9 +67,9 @@ public abstract class TrieEntriesIterator<T, V> extends
TriePathReconstructor im
*/
static class AsEntries<T> extends TrieEntriesIterator<T,
Map.Entry<ByteComparable, T>>
{
- public AsEntries(Trie<T> trie)
+ public AsEntries(Trie<T> trie, Direction direction)
{
- super(trie);
+ super(trie, direction);
}
@Override
diff --git a/src/java/org/apache/cassandra/db/tries/TrieValuesIterator.java
b/src/java/org/apache/cassandra/db/tries/TrieValuesIterator.java
index 29d3642b2e..99a3689b1a 100644
--- a/src/java/org/apache/cassandra/db/tries/TrieValuesIterator.java
+++ b/src/java/org/apache/cassandra/db/tries/TrieValuesIterator.java
@@ -30,7 +30,7 @@ class TrieValuesIterator<T> implements Iterator<T>
protected TrieValuesIterator(Trie<T> trie)
{
- cursor = trie.cursor();
+ cursor = trie.cursor(Direction.FORWARD);
assert cursor.depth() == 0;
next = cursor.content();
gotNext = next != null;
diff --git
a/src/java/org/apache/cassandra/utils/bytecomparable/ByteComparable.md
b/src/java/org/apache/cassandra/utils/bytecomparable/ByteComparable.md
index 8012e27b03..a1d943dded 100644
--- a/src/java/org/apache/cassandra/utils/bytecomparable/ByteComparable.md
+++ b/src/java/org/apache/cassandra/utils/bytecomparable/ByteComparable.md
@@ -76,253 +76,36 @@ are in the releavant `AbstractType` subclass.
Generally, we desire the following two properties from the byte-ordered
translations of values we use in the database:
- Comparison equivalence (1):
- <math xmlns="http://www.w3.org/1998/Math/MathML";>
- <semantics>
- <mstyle displaystyle="true">
- <mo>∀</mo>
- <mi>x</mi>
- <mo>,</mo>
- <mi>y</mi>
- <mo>∈</mo>
- <mi>T</mi>
- <mo>,</mo>
- <mrow>
- <mtext>compareBytesUnsigned</mtext>
- </mrow>
- <mrow>
- <mo>(</mo>
- <mi>T</mi>
- <mo>.</mo>
- <mrow>
- <mtext>byteOrdered</mtext>
- </mrow>
- <mrow>
- <mo>(</mo>
- <mi>x</mi>
- <mo>)</mo>
- </mrow>
- <mo>,</mo>
- <mi>T</mi>
- <mo>.</mo>
- <mrow>
- <mtext>byteOrdered</mtext>
- </mrow>
- <mrow>
- <mo>(</mo>
- <mi>y</mi>
- <mo>)</mo>
- </mrow>
- <mo>)</mo>
- </mrow>
- <mo>=</mo>
- <mi>T</mi>
- <mo>.</mo>
- <mrow>
- <mtext>compare</mtext>
- </mrow>
- <mrow>
- <mo>(</mo>
- <mi>x</mi>
- <mo>,</mo>
- <mi>y</mi>
- <mo>)</mo>
- </mrow>
- </mstyle>
- <!-- <annotation encoding="text/x-asciimath">forall x,y in T,
"compareBytesUnsigned"(T."byteOrdered"(x), T."byteOrdered"(y))=T."compare"(x,
y)</annotation> -->
- </semantics>
- </math>
+ $$\forall x,y \in T,
\mathrm{compareBytesUnsigned}(T.\mathrm{byteOrdered}(x),
T.\mathrm{byteOrdered}(y)) = T.\mathrm{compare}(x, y)$$
+
- Prefix-freedom (2):
- <math xmlns="http://www.w3.org/1998/Math/MathML";>
- <semantics>
- <mstyle displaystyle="true">
- <mo>∀</mo>
- <mi>x</mi>
- <mo>,</mo>
- <mi>y</mi>
- <mo>∈</mo>
- <mi>T</mi>
- <mo>,</mo>
- <mi>T</mi>
- <mo>.</mo>
- <mrow>
- <mtext>byteOrdered</mtext>
- </mrow>
- <mrow>
- <mo>(</mo>
- <mi>x</mi>
- <mo>)</mo>
- </mrow>
- <mrow>
- <mspace width="1ex" />
- <mtext> is not a prefix of </mtext>
- <mspace width="1ex" />
- </mrow>
- <mi>T</mi>
- <mo>.</mo>
- <mrow>
- <mtext>byteOrdered</mtext>
- </mrow>
- <mrow>
- <mo>(</mo>
- <mi>y</mi>
- <mo>)</mo>
- </mrow>
- </mstyle>
- <!-- <annotation encoding="text/x-asciimath">forall x,y in T,
T."byteOrdered"(x) " is not a prefix of " T."byteOrdered"(y)</annotation> -->
- </semantics>
- </math>
+ $$\forall x,y \in T, T.\mathrm{byteOrdered}(x) \text{ is not a prefix of }
T.\mathrm{byteOrdered}(y)$$
The former is the essential requirement, and the latter allows construction of
encodings of sequences of multiple
values, as well as a little more efficiency in the data structures.
To more efficiently encode byte-ordered blobs, however, we use a slightly
tweaked version of the above requirements:
-- Comparison equivalence (3):
- <math xmlns="http://www.w3.org/1998/Math/MathML";>
- <semantics>
- <mstyle displaystyle="true">
- <mo>∀</mo>
- <mi>x</mi>
- <mo>,</mo>
- <mi>y</mi>
- <mo>∈</mo>
- <mi>T</mi>
- <mo>,</mo>
- <mo>∀</mo>
- <msub>
- <mi>b</mi>
- <mn>1</mn>
- </msub>
- <mo>,</mo>
- <msub>
- <mi>b</mi>
- <mn>2</mn>
- </msub>
- <mo>∈</mo>
- <mrow>
- <mo>[</mo>
- <mn>0x10</mn>
- <mo>-</mo>
- <mn>0xEF</mn>
- <mo>]</mo>
- </mrow>
- <mo>,</mo>
- <mtext><br/></mtext>
- <mrow>
- <mtext>compareBytesUnsigned</mtext>
- </mrow>
- <mrow>
- <mo>(</mo>
- <mi>T</mi>
- <mo>.</mo>
- <mrow>
- <mtext>byteOrdered</mtext>
- </mrow>
- <mrow>
- <mo>(</mo>
- <mi>x</mi>
- <mo>)</mo>
- </mrow>
- <mo>+</mo>
- <msub>
- <mi>b</mi>
- <mn>1</mn>
- </msub>
- <mo>,</mo>
- <mi>T</mi>
- <mo>.</mo>
- <mrow>
- <mtext>byteOrdered</mtext>
- </mrow>
- <mrow>
- <mo>(</mo>
- <mi>y</mi>
- <mo>)</mo>
- </mrow>
- <mo>+</mo>
- <msub>
- <mi>b</mi>
- <mn>2</mn>
- </msub>
- <mo>)</mo>
- </mrow>
- <mo>=</mo>
- <mi>T</mi>
- <mo>.</mo>
- <mrow>
- <mtext>compare</mtext>
- </mrow>
- <mrow>
- <mo>(</mo>
- <mi>x</mi>
- <mo>,</mo>
- <mi>y</mi>
- <mo>)</mo>
- </mrow>
- </mstyle>
- <!-- <annotation encoding="text/x-asciimath">forall x,y in T, forall
b_1, b_2 in [0x10-0xEF],
- "compareBytesUnsigned"(T."byteOrdered"(x)+b_1,
T."byteOrdered"(y)+b_2)=T."compare"(x, y)</annotation> -->
- </semantics>
- </math>
+[//]: # (latex arrays don't work in github markdown, replace ```math...```
with $$...$$ to see math in IntelliJ)
+
+- Comparison equivalence (3):
+ ```math
+ \begin{array}{c}
+ \forall x,y \in T, \forall b_1, b_2 \in [0x10-0x\text{EF}],\cr
+ \mathrm{compareBytesUnsigned}(T.\mathrm{byteOrdered}(x)+b_1,
T.\mathrm{byteOrdered}(y)+b_2)
+ = \begin{cases}
+ T.\mathrm{compare}(x, y), &\mathrm{if\ } x \ne y \cr
+ \mathrm{Byte.compare}(b_1, b_2), &\mathrm{if\ } x = y
+ \end{cases}
+ \end{array}
+ ```
- Weak prefix-freedom (4):
- <math xmlns="http://www.w3.org/1998/Math/MathML";>
- <semantics>
- <mstyle displaystyle="true">
- <mo>∀</mo>
- <mi>x</mi>
- <mo>,</mo>
- <mi>y</mi>
- <mo>∈</mo>
- <mi>T</mi>
- <mo>,</mo>
- <mo>∀</mo>
- <mi>b</mi>
- <mo>∈</mo>
- <mrow>
- <mo>[</mo>
- <mn>0x10</mn>
- <mo>-</mo>
- <mn>0xEF</mn>
- <mo>]</mo>
- </mrow>
- <mo>,</mo>
- <mtext><br/></mtext>
- <mrow>
- <mo>(</mo>
- <mi>T</mi>
- <mo>.</mo>
- <mrow>
- <mtext>byteOrdered</mtext>
- </mrow>
- <mrow>
- <mo>(</mo>
- <mi>x</mi>
- <mo>)</mo>
- </mrow>
- <mo>+</mo>
- <mi>b</mi>
- <mo>)</mo>
- </mrow>
- <mrow>
- <mspace width="1ex" />
- <mtext> is not a prefix of </mtext>
- <mspace width="1ex" />
- </mrow>
- <mi>T</mi>
- <mo>.</mo>
- <mrow>
- <mtext>byteOrdered</mtext>
- </mrow>
- <mrow>
- <mo>(</mo>
- <mi>y</mi>
- <mo>)</mo>
- </mrow>
- </mstyle>
- <!-- <annotation encoding="text/x-asciimath">forall x,y in T, forall b
in [0x10-0xEF],
- (T."byteOrdered"(x)+b) " is not a prefix of "
T."byteOrdered"(y)</annotation> -->
- </semantics>
- </math>
+ ```math
+ \begin{array}{c}
+ \forall x,y \in T, \forall b \in [0x10-0x\text{EF}], \cr
+ T.\mathrm{byteOrdered}(x)+b \text{ is not a prefix of }
T.\mathrm{byteOrdered}(y)
+ \end{array}
+ ```
These versions allow the addition of a separator byte after each value, and
guarantee that the combination with
separator fulfills the original requirements. (3) is somewhat stronger than
(1) but is necessarily true if (2) is also
diff --git
a/test/microbench/org/apache/cassandra/test/microbench/tries/InMemoryTrieReadBench.java
b/test/microbench/org/apache/cassandra/test/microbench/tries/InMemoryTrieReadBench.java
index cff2e4a3eb..52fc63ad39 100644
---
a/test/microbench/org/apache/cassandra/test/microbench/tries/InMemoryTrieReadBench.java
+++
b/test/microbench/org/apache/cassandra/test/microbench/tries/InMemoryTrieReadBench.java
@@ -22,6 +22,7 @@ import java.util.Random;
import java.util.concurrent.TimeUnit;
import java.util.function.BiConsumer;
+import org.apache.cassandra.db.tries.Direction;
import org.apache.cassandra.db.tries.InMemoryTrie;
import org.apache.cassandra.db.tries.Trie;
import org.apache.cassandra.db.tries.TrieEntriesWalker;
@@ -44,6 +45,9 @@ public class InMemoryTrieReadBench
@Param({"1000", "100000", "10000000"})
int count = 1000;
+ @Param({"FORWARD"})
+ Direction direction = Direction.FORWARD;
+
final static InMemoryTrie.UpsertTransformer<Byte, Byte> resolver = (x, y)
-> y;
InMemoryTrie<Byte> trie;
@@ -145,7 +149,7 @@ public class InMemoryTrieReadBench
}
}
Counter counter = new Counter();
- trie.process(counter);
+ trie.process(counter, direction);
return counter.sum;
}
@@ -162,7 +166,7 @@ public class InMemoryTrieReadBench
public int iterateEntries()
{
int sum = 0;
- for (Map.Entry<ByteComparable, Byte> en : trie.entrySet())
+ for (Map.Entry<ByteComparable, Byte> en : trie.entrySet(direction))
sum += en.getValue();
return sum;
}
diff --git
a/test/unit/org/apache/cassandra/db/tries/CollectionMergeTrieTest.java
b/test/unit/org/apache/cassandra/db/tries/CollectionMergeTrieTest.java
index 94903a74d7..8c2049e54a 100644
--- a/test/unit/org/apache/cassandra/db/tries/CollectionMergeTrieTest.java
+++ b/test/unit/org/apache/cassandra/db/tries/CollectionMergeTrieTest.java
@@ -45,8 +45,8 @@ public class CollectionMergeTrieTest
{
ByteComparable[] src1 = generateKeys(rand, COUNT);
ByteComparable[] src2 = generateKeys(rand, COUNT);
- SortedMap<ByteComparable, ByteBuffer> content1 = new
TreeMap<>((bytes1, bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
- SortedMap<ByteComparable, ByteBuffer> content2 = new
TreeMap<>((bytes1, bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
+ SortedMap<ByteComparable, ByteBuffer> content1 = new
TreeMap<>(FORWARD_COMPARATOR);
+ SortedMap<ByteComparable, ByteBuffer> content2 = new
TreeMap<>(FORWARD_COMPARATOR);
InMemoryTrie<ByteBuffer> trie1 = makeInMemoryTrie(src1, content1,
true);
InMemoryTrie<ByteBuffer> trie2 = makeInMemoryTrie(src2, content2,
true);
@@ -63,8 +63,8 @@ public class CollectionMergeTrieTest
{
ByteComparable[] src1 = generateKeys(rand, COUNT);
ByteComparable[] src2 = generateKeys(rand, COUNT);
- SortedMap<ByteComparable, ByteBuffer> content1 = new
TreeMap<>((bytes1, bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
- SortedMap<ByteComparable, ByteBuffer> content2 = new
TreeMap<>((bytes1, bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
+ SortedMap<ByteComparable, ByteBuffer> content1 = new
TreeMap<>(FORWARD_COMPARATOR);
+ SortedMap<ByteComparable, ByteBuffer> content2 = new
TreeMap<>(FORWARD_COMPARATOR);
InMemoryTrie<ByteBuffer> trie1 = makeInMemoryTrie(src1, content1,
true);
InMemoryTrie<ByteBuffer> trie2 = makeInMemoryTrie(src2, content2,
true);
@@ -82,12 +82,12 @@ public class CollectionMergeTrieTest
public void testDistinct()
{
ByteComparable[] src1 = generateKeys(rand, COUNT);
- SortedMap<ByteComparable, ByteBuffer> content1 = new
TreeMap<>((bytes1, bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
+ SortedMap<ByteComparable, ByteBuffer> content1 = new
TreeMap<>(FORWARD_COMPARATOR);
InMemoryTrie<ByteBuffer> trie1 = makeInMemoryTrie(src1, content1,
true);
ByteComparable[] src2 = generateKeys(rand, COUNT);
src2 = removeDuplicates(src2, content1);
- SortedMap<ByteComparable, ByteBuffer> content2 = new
TreeMap<>((bytes1, bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
+ SortedMap<ByteComparable, ByteBuffer> content2 = new
TreeMap<>(FORWARD_COMPARATOR);
InMemoryTrie<ByteBuffer> trie2 = makeInMemoryTrie(src2, content2,
true);
content1.putAll(content2);
@@ -144,7 +144,7 @@ public class CollectionMergeTrieTest
public void testMultipleDistinct(int mergeCount, int count)
{
List<Trie<ByteBuffer>> tries = new ArrayList<>(mergeCount);
- SortedMap<ByteComparable, ByteBuffer> content = new TreeMap<>((bytes1,
bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
+ SortedMap<ByteComparable, ByteBuffer> content = new
TreeMap<>(FORWARD_COMPARATOR);
for (int i = 0; i < mergeCount; ++i)
{
@@ -160,7 +160,7 @@ public class CollectionMergeTrieTest
public void testMultipleWithDuplicates(int mergeCount, int count)
{
List<Trie<ByteBuffer>> tries = new ArrayList<>(mergeCount);
- SortedMap<ByteComparable, ByteBuffer> content = new TreeMap<>((bytes1,
bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
+ SortedMap<ByteComparable, ByteBuffer> content = new
TreeMap<>(FORWARD_COMPARATOR);
ByteComparable[][] keys = new ByteComparable[count][];
for (int i = 0; i < mergeCount; ++i)
keys[i] = generateKeys(rand, count);
diff --git a/test/unit/org/apache/cassandra/db/tries/InMemoryTrieTestBase.java
b/test/unit/org/apache/cassandra/db/tries/InMemoryTrieTestBase.java
index d1c1711423..151cd9f00e 100644
--- a/test/unit/org/apache/cassandra/db/tries/InMemoryTrieTestBase.java
+++ b/test/unit/org/apache/cassandra/db/tries/InMemoryTrieTestBase.java
@@ -21,6 +21,7 @@ package org.apache.cassandra.db.tries;
import java.nio.ByteBuffer;
import java.util.*;
import java.util.function.Function;
+import java.util.stream.Collectors;
import java.util.stream.Stream;
import com.google.common.collect.HashMultiset;
@@ -34,6 +35,7 @@ import org.apache.cassandra.io.compress.BufferType;
import org.apache.cassandra.utils.ByteBufferUtil;
import org.apache.cassandra.utils.bytecomparable.ByteComparable;
import org.apache.cassandra.utils.ObjectSizes;
+import org.apache.cassandra.utils.bytecomparable.ByteSource;
import static org.junit.Assert.assertEquals;
@@ -52,8 +54,27 @@ public abstract class InMemoryTrieTestBase
static final ByteComparable.Version VERSION =
InMemoryTrie.BYTE_COMPARABLE_VERSION;
+ public static final Comparator<ByteComparable> FORWARD_COMPARATOR =
(bytes1, bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION);
+ public static final Comparator<ByteComparable> REVERSE_COMPARATOR =
(bytes1, bytes2) -> ByteComparable.compare(invert(bytes1), invert(bytes2),
VERSION);
+
abstract boolean usePut();
+ static ByteComparable invert(ByteComparable b)
+ {
+ return version -> invert(b.asComparableBytes(version));
+ }
+
+ static ByteSource invert(ByteSource src)
+ {
+ return () ->
+ {
+ int v = src.next();
+ if (v == ByteSource.END_OF_STREAM)
+ return v;
+ return v ^ 0xFF;
+ };
+ }
+
@Test
public void testSingle()
{
@@ -146,12 +167,12 @@ public abstract class InMemoryTrieTestBase
Object content;
SpecStackEntry parent;
- public SpecStackEntry(Object[] spec, Object content, SpecStackEntry
parent)
+ public SpecStackEntry(Object[] spec, Object content, SpecStackEntry
parent, Direction direction)
{
this.children = spec;
this.content = content;
this.parent = parent;
- this.curChild = -1;
+ this.curChild = direction.select(-1, spec.length);
}
}
@@ -159,17 +180,19 @@ public abstract class InMemoryTrieTestBase
{
SpecStackEntry stack;
int depth;
+ Direction direction;
- CursorFromSpec(Object[] spec)
+ CursorFromSpec(Object[] spec, Direction direction)
{
- stack = new SpecStackEntry(spec, null, null);
+ this.direction = direction;
+ stack = new SpecStackEntry(spec, null, null, direction);
depth = 0;
}
public int advance()
{
SpecStackEntry current = stack;
- while (current != null && ++current.curChild >=
current.children.length)
+ while (current != null && !direction.inLoop(current.curChild +=
direction.increase, 0, current.children.length - 1))
{
current = current.parent;
--depth;
@@ -182,29 +205,9 @@ public abstract class InMemoryTrieTestBase
Object child = current.children[current.curChild];
if (child instanceof Object[])
- stack = new SpecStackEntry((Object[]) child, null, current);
+ stack = new SpecStackEntry((Object[]) child, null, current,
direction);
else
- stack = new SpecStackEntry(new Object[0], child, current);
-
- return ++depth;
- }
-
- public int advanceMultiple()
- {
- if (++stack.curChild >= stack.children.length)
- return skipChildren();
-
- Object child = stack.children[stack.curChild];
- while (child instanceof Object[])
- {
- stack = new SpecStackEntry((Object[]) child, null, stack);
- ++depth;
- if (stack.children.length == 0)
- return depth;
- child = stack.children[0];
- }
- stack = new SpecStackEntry(new Object[0], child, stack);
-
+ stack = new SpecStackEntry(new Object[0], child, current,
direction);
return ++depth;
}
@@ -238,9 +241,9 @@ public abstract class InMemoryTrieTestBase
return new Trie<ByteBuffer>()
{
@Override
- protected Cursor<ByteBuffer> cursor()
+ protected Cursor<ByteBuffer> cursor(Direction direction)
{
- return new CursorFromSpec(nodeDef);
+ return new CursorFromSpec(nodeDef, direction);
}
};
}
@@ -274,7 +277,7 @@ public abstract class InMemoryTrieTestBase
ByteBufferUtil.bytes(6) // 6
};
- SortedMap<ByteComparable, ByteBuffer> expected = new
TreeMap<>((bytes1, bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
+ SortedMap<ByteComparable, ByteBuffer> expected = new
TreeMap<>(FORWARD_COMPARATOR);
expected.put(comparable("00"), ByteBufferUtil.bytes(1));
expected.put(comparable("01"), ByteBufferUtil.bytes(2));
expected.put(comparable("2"), ByteBufferUtil.bytes(3));
@@ -297,7 +300,7 @@ public abstract class InMemoryTrieTestBase
public void testDirect()
{
ByteComparable[] src = generateKeys(rand, COUNT);
- SortedMap<ByteComparable, ByteBuffer> content = new TreeMap<>((bytes1,
bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
+ SortedMap<ByteComparable, ByteBuffer> content = new
TreeMap<>(FORWARD_COMPARATOR);
InMemoryTrie<ByteBuffer> trie = makeInMemoryTrie(src, content,
usePut());
int keysize = Arrays.stream(src)
.mapToInt(src1 -> ByteComparable.length(src1,
VERSION))
@@ -449,11 +452,13 @@ public abstract class InMemoryTrieTestBase
static void assertSameContent(Trie<ByteBuffer> trie,
SortedMap<ByteComparable, ByteBuffer> map)
{
- assertMapEquals(trie, map);
- assertForEachEntryEquals(trie, map);
+ assertMapEquals(trie, map, Direction.FORWARD);
+ assertForEachEntryEquals(trie, map, Direction.FORWARD);
assertValuesEqual(trie, map);
assertForEachValueEquals(trie, map);
assertUnorderedValuesEqual(trie, map);
+ assertMapEquals(trie, map, Direction.REVERSE);
+ assertForEachEntryEquals(trie, map, Direction.REVERSE);
}
private static void assertValuesEqual(Trie<ByteBuffer> trie,
SortedMap<ByteComparable, ByteBuffer> map)
@@ -478,10 +483,27 @@ public abstract class InMemoryTrieTestBase
assertEquals("", errors.toString());
}
- private static void assertForEachEntryEquals(Trie<ByteBuffer> trie,
SortedMap<ByteComparable, ByteBuffer> map)
+ static Collection<ByteComparable> maybeReversed(Direction direction,
Collection<ByteComparable> data)
+ {
+ return direction.isForward() ? data : reorderBy(data,
REVERSE_COMPARATOR);
+ }
+
+ static <V> Map<ByteComparable, V> maybeReversed(Direction direction,
Map<ByteComparable, V> data)
{
- Iterator<Map.Entry<ByteComparable, ByteBuffer>> it =
map.entrySet().iterator();
- trie.forEachEntry((key, value) -> {
+ return direction.isForward() ? data : reorderBy(data,
REVERSE_COMPARATOR);
+ }
+
+ private static <V> Map<ByteComparable, V> reorderBy(Map<ByteComparable, V>
data, Comparator<ByteComparable> comparator)
+ {
+ Map<ByteComparable, V> newMap = new TreeMap<>(comparator);
+ newMap.putAll(data);
+ return newMap;
+ }
+
+ private static void assertForEachEntryEquals(Trie<ByteBuffer> trie,
SortedMap<ByteComparable, ByteBuffer> map, Direction direction)
+ {
+ Iterator<Map.Entry<ByteComparable, ByteBuffer>> it =
maybeReversed(direction, map).entrySet().iterator();
+ trie.forEachEntry(direction, (key, value) -> {
Assert.assertTrue("Map exhausted first, key " + asString(key),
it.hasNext());
Map.Entry<ByteComparable, ByteBuffer> entry = it.next();
assertEquals(0, ByteComparable.compare(entry.getKey(), key,
Trie.BYTE_COMPARABLE_VERSION));
@@ -501,16 +523,21 @@ public abstract class InMemoryTrieTestBase
Assert.assertFalse("Trie exhausted first", it.hasNext());
}
- static void assertMapEquals(Trie<ByteBuffer> trie,
SortedMap<ByteComparable, ByteBuffer> map)
+ static void assertMapEquals(Trie<ByteBuffer> trie,
SortedMap<ByteComparable, ByteBuffer> map, Direction direction)
+ {
+ assertMapEquals(trie.entryIterator(direction),
maybeReversed(direction, map).entrySet().iterator());
+ }
+
+ static <E> Collection<E> reorderBy(Collection<E> original, Comparator<E>
comparator)
{
- assertMapEquals(trie.entrySet(), map.entrySet());
+ List<E> list = original.stream().collect(Collectors.toList());
+ list.sort(comparator);
+ return list;
}
- static void assertMapEquals(Iterable<Map.Entry<ByteComparable,
ByteBuffer>> container1,
- Iterable<Map.Entry<ByteComparable,
ByteBuffer>> container2)
+ static void assertMapEquals(Iterator<Map.Entry<ByteComparable,
ByteBuffer>> it1,
+ Iterator<Map.Entry<ByteComparable,
ByteBuffer>> it2)
{
- Iterator<Map.Entry<ByteComparable, ByteBuffer>> it1 =
container1.iterator();
- Iterator<Map.Entry<ByteComparable, ByteBuffer>> it2 =
container2.iterator();
List<ByteComparable> failedAt = new ArrayList<>();
StringBuilder b = new StringBuilder();
while (it1.hasNext() && it2.hasNext())
@@ -560,7 +587,7 @@ public abstract class InMemoryTrieTestBase
static ByteComparable[] generateKeys(Random rand, int count)
{
ByteComparable[] sources = new ByteComparable[count];
- TreeSet<ByteComparable> added = new TreeSet<>((bytes1, bytes2) ->
ByteComparable.compare(bytes1, bytes2, VERSION));
+ TreeSet<ByteComparable> added = new TreeSet<>(FORWARD_COMPARATOR);
for (int i = 0; i < count; ++i)
{
sources[i] = generateKey(rand);
diff --git a/test/unit/org/apache/cassandra/db/tries/MergeTrieTest.java
b/test/unit/org/apache/cassandra/db/tries/MergeTrieTest.java
index cc08401102..cfc5c0a461 100644
--- a/test/unit/org/apache/cassandra/db/tries/MergeTrieTest.java
+++ b/test/unit/org/apache/cassandra/db/tries/MergeTrieTest.java
@@ -40,8 +40,8 @@ public class MergeTrieTest
{
ByteComparable[] src1 = generateKeys(rand, COUNT);
ByteComparable[] src2 = generateKeys(rand, COUNT);
- SortedMap<ByteComparable, ByteBuffer> content1 = new
TreeMap<>((bytes1, bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
- SortedMap<ByteComparable, ByteBuffer> content2 = new
TreeMap<>((bytes1, bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
+ SortedMap<ByteComparable, ByteBuffer> content1 = new
TreeMap<>(FORWARD_COMPARATOR);
+ SortedMap<ByteComparable, ByteBuffer> content2 = new
TreeMap<>(FORWARD_COMPARATOR);
InMemoryTrie<ByteBuffer> trie1 = makeInMemoryTrie(src1, content1,
true);
InMemoryTrie<ByteBuffer> trie2 = makeInMemoryTrie(src2, content2,
true);
@@ -57,8 +57,8 @@ public class MergeTrieTest
{
ByteComparable[] src1 = generateKeys(rand, COUNT);
ByteComparable[] src2 = generateKeys(rand, COUNT);
- SortedMap<ByteComparable, ByteBuffer> content1 = new
TreeMap<>((bytes1, bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
- SortedMap<ByteComparable, ByteBuffer> content2 = new
TreeMap<>((bytes1, bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
+ SortedMap<ByteComparable, ByteBuffer> content1 = new
TreeMap<>(FORWARD_COMPARATOR);
+ SortedMap<ByteComparable, ByteBuffer> content2 = new
TreeMap<>(FORWARD_COMPARATOR);
InMemoryTrie<ByteBuffer> trie1 = makeInMemoryTrie(src1, content1,
true);
InMemoryTrie<ByteBuffer> trie2 = makeInMemoryTrie(src2, content2,
true);
@@ -76,12 +76,12 @@ public class MergeTrieTest
public void testDistinct()
{
ByteComparable[] src1 = generateKeys(rand, COUNT);
- SortedMap<ByteComparable, ByteBuffer> content1 = new
TreeMap<>((bytes1, bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
+ SortedMap<ByteComparable, ByteBuffer> content1 = new
TreeMap<>(FORWARD_COMPARATOR);
InMemoryTrie<ByteBuffer> trie1 = makeInMemoryTrie(src1, content1,
true);
ByteComparable[] src2 = generateKeys(rand, COUNT);
src2 = removeDuplicates(src2, content1);
- SortedMap<ByteComparable, ByteBuffer> content2 = new
TreeMap<>((bytes1, bytes2) -> ByteComparable.compare(bytes1, bytes2, VERSION));
+ SortedMap<ByteComparable, ByteBuffer> content2 = new
TreeMap<>(FORWARD_COMPARATOR);
InMemoryTrie<ByteBuffer> trie2 = makeInMemoryTrie(src2, content2,
true);
content1.putAll(content2);
diff --git a/test/unit/org/apache/cassandra/db/tries/SlicedTrieTest.java
b/test/unit/org/apache/cassandra/db/tries/SlicedTrieTest.java
index 07bae0ed9f..69d2a0a955 100644
--- a/test/unit/org/apache/cassandra/db/tries/SlicedTrieTest.java
+++ b/test/unit/org/apache/cassandra/db/tries/SlicedTrieTest.java
@@ -304,19 +304,26 @@ public class SlicedTrieTest
return new Trie<Integer>()
{
@Override
- protected Cursor<Integer> cursor()
+ protected Cursor<Integer> cursor(Direction direction)
{
- return new singleLevelCursor();
+ return new singleLevelCursor(direction);
}
class singleLevelCursor implements Cursor<Integer>
{
+ final Direction direction;
int current = -1;
+ singleLevelCursor(Direction direction)
+ {
+ this.direction = direction;
+ current = direction.select(-1, childs);
+ }
+
@Override
public int advance()
{
- ++current;
+ current += direction.increase;
return depth();
}
@@ -329,9 +336,9 @@ public class SlicedTrieTest
@Override
public int depth()
{
- if (current == -1)
+ if (current == direction.select(-1, childs))
return 0;
- if (current < childs)
+ if (direction.inLoop(current, 0, childs - 1))
return 1;
return -1;
}
diff --git a/test/unit/org/apache/cassandra/db/tries/TrieToDotTest.java
b/test/unit/org/apache/cassandra/db/tries/TrieToDotTest.java
index 41c66aaaeb..b4955dbc08 100644
--- a/test/unit/org/apache/cassandra/db/tries/TrieToDotTest.java
+++ b/test/unit/org/apache/cassandra/db/tries/TrieToDotTest.java
@@ -36,6 +36,7 @@ public class TrieToDotTest
System.out.println(trie.process(new TrieToDot(Object::toString,
x ->
Character.toString((char) ((int) x)),
- true)));
+ true),
+ Direction.FORWARD));
}
}
diff --git a/test/unit/org/apache/cassandra/db/tries/TrieToMermaidTest.java
b/test/unit/org/apache/cassandra/db/tries/TrieToMermaidTest.java
index bd691bbd6e..61b5f4f893 100644
--- a/test/unit/org/apache/cassandra/db/tries/TrieToMermaidTest.java
+++ b/test/unit/org/apache/cassandra/db/tries/TrieToMermaidTest.java
@@ -36,6 +36,7 @@ public class TrieToMermaidTest
System.out.println(trie.process(new TrieToMermaid(Object::toString,
x ->
Character.toString((char) ((int) x)),
- false)));
+ false),
+ Direction.FORWARD));
}
}
diff --git
a/test/unit/org/apache/cassandra/utils/bytecomparable/ByteSourceComparisonTest.java
b/test/unit/org/apache/cassandra/utils/bytecomparable/ByteSourceComparisonTest.java
index d49a483bfa..496f6355c1 100644
---
a/test/unit/org/apache/cassandra/utils/bytecomparable/ByteSourceComparisonTest.java
+++
b/test/unit/org/apache/cassandra/utils/bytecomparable/ByteSourceComparisonTest.java
@@ -432,7 +432,7 @@ public class ByteSourceComparisonTest extends
ByteSourceTestBase
safeStr(c.clusteringString(comp.subtypes())),
safeStr(e.clusteringString(comp.subtypes())), bsc, bse, v),
expected,
Integer.signum(ByteComparable.compare(bsc, bse, v)));
- maybeCheck41Properties(expected, bsc, bse, v);
+ maybeCheck50Properties(expected, bsc, bse, v);
maybeAssertNotPrefix(bsc, bse, v);
ClusteringComparator compR = new
ClusteringComparator(ReversedType.getInstance(t1),
ReversedType.getInstance(t2));
@@ -443,7 +443,7 @@ public class ByteSourceComparisonTest extends
ByteSourceTestBase
safeStr(c.clusteringString(comp.subtypes())),
safeStr(e.clusteringString(comp.subtypes())), bsrc, bsre, v),
expectedR,
Integer.signum(ByteComparable.compare(bsrc, bsre, v)));
- maybeCheck41Properties(expectedR, bsrc, bsre, v);
+ maybeCheck50Properties(expectedR, bsrc, bsre, v);
maybeAssertNotPrefix(bsrc, bsre, v);
}
}
@@ -644,7 +644,7 @@ public class ByteSourceComparisonTest extends
ByteSourceTestBase
@Test
public void testDecoratedKeyPrefixesVOSS50()
{
- // This should pass with the OSS 4.1 encoding
+ // This should pass with the OSS 5.0 encoding
testDecoratedKeyPrefixes(Version.OSS50);
}
@@ -864,13 +864,13 @@ public class ByteSourceComparisonTest extends
ByteSourceTestBase
private void maybeAssertNotPrefix(ByteComparable s1, ByteComparable s2,
Version version)
{
- if (version == Version.OSS50)
+ if (version != Version.LEGACY)
assertNotPrefix(s1.asComparableBytes(version),
s2.asComparableBytes(version));
}
- private void maybeCheck41Properties(int expectedComparison, ByteComparable
s1, ByteComparable s2, Version version)
+ private void maybeCheck50Properties(int expectedComparison, ByteComparable
s1, ByteComparable s2, Version version)
{
- if (version != Version.OSS50)
+ if (version == Version.LEGACY)
return;
if (s1 == null || s2 == null || 0 == expectedComparison)
@@ -985,7 +985,7 @@ public class ByteSourceComparisonTest extends
ByteSourceTestBase
assertEquals(String.format("Failed comparing %s(%s) and %s(%s)",
ByteBufferUtil.bytesToHex(b1), bs1.byteComparableAsString(version),
ByteBufferUtil.bytesToHex(b2), bs2.byteComparableAsString(version)),
expected,
actual);
- maybeCheck41Properties(expected, bs1, bs2, version);
+ maybeCheck50Properties(expected, bs1, bs2, version);
}
}
@@ -1139,7 +1139,7 @@ public class ByteSourceComparisonTest extends
ByteSourceTestBase
expected,
actual);
}
- maybeCheck41Properties(expected, bc1, bc2, version);
+ maybeCheck50Properties(expected, bc1, bc2, version);
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
