ifesdjeen commented on code in PR #4240:
URL: https://github.com/apache/cassandra/pull/4240#discussion_r2200534180
##########
src/java/org/apache/cassandra/utils/btree/BTree.java:
##########
@@ -3982,204 +4092,130 @@ private void prependFromParent(LeafOrBranchBuilder
fill, BranchBuilder parent)
void reset()
{
- Arrays.fill(queuedToFinish, 0, update.leafDepth, null);
update.reset();
super.reset();
}
}
/**
* 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
*/
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)
+ {
+ int pdepth = update.depth - 1;
+ if (pdepth >= 0)
{
- int prev = upos;
- while (upos < usz)
- {
- 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;
- }
- leaf().copy(unode, prev, usz - prev);
+ Object[] pnode = update.nodes[pdepth];
+ int ppos = update.positions[pdepth];
+ if (ppos < shallowSizeOfBranch(pnode) &&
comparator.compare(remove.peek(), (K)pnode[ppos]) >= 0)
Review Comment:
Could you add a small comment about this edge case?
##########
src/java/org/apache/cassandra/service/accord/CommandsForRanges.java:
##########
@@ -224,7 +195,7 @@ static Object[] toMap(TxnId txnId, RangeRoute route)
case 1: return IntervalBTree.singleton(new
TxnIdInterval(route.get(0), txnId));
default:
{
- try (IntervalBTree.FastInteralTreeBuilder<TxnIdInterval>
builder = IntervalBTree.fastBuilder(COMPARATORS.endWithEndComparator()))
+ try (IntervalBTree.FastInteralTreeBuilder<TxnIdInterval>
builder = IntervalBTree.fastBuilder(COMPARATORS))
Review Comment:
nit: FastInteralTreeBuilder -> `FastIntervalTreeBuilder` (missing v)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: pr-unsubscr...@cassandra.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscr...@cassandra.apache.org
For additional commands, e-mail: pr-h...@cassandra.apache.org
