You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by be...@apache.org on 2023/01/26 12:43:19 UTC
[cassandra-accord] branch trunk updated: Introduce RangeDeps (#21)
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-accord.git
The following commit(s) were added to refs/heads/trunk by this push:
new 686326e Introduce RangeDeps (#21)
686326e is described below
commit 686326eedc8d2553c98a30abc81a925be3942b8c
Author: Benedict Elliott Smith <be...@apache.org>
AuthorDate: Thu Jan 26 12:43:14 2023 +0000
Introduce RangeDeps (#21)
Refactor Deps into KeyDeps and RangeDeps
patch by Benedict; reviewed by Aleksey Yeschenko for CASSANDRA-18173
---
accord-core/src/main/java/accord/api/Agent.java | 1 +
accord-core/src/main/java/accord/api/Key.java | 6 +
accord-core/src/main/java/accord/api/Result.java | 1 +
.../src/main/java/accord/api/TopologySorter.java | 2 +
.../java/accord/api/UncaughtExceptionListener.java | 1 +
.../main/java/accord/coordinate/Coordinate.java | 3 +-
.../java/accord/coordinate/ReadCoordinator.java | 3 +-
.../src/main/java/accord/coordinate/Recover.java | 2 +-
.../src/main/java/accord/impl/InMemoryCommand.java | 1 +
.../java/accord/impl/InMemoryCommandStore.java | 10 +
.../main/java/accord/impl/SimpleProgressLog.java | 1 +
.../src/main/java/accord/local/Command.java | 4 +-
accord-core/src/main/java/accord/local/Node.java | 4 +
.../main/java/accord/local/SafeCommandStore.java | 1 -
.../src/main/java/accord/messages/Accept.java | 2 +
.../src/main/java/accord/messages/Apply.java | 3 +
.../main/java/accord/messages/BeginRecovery.java | 10 +-
.../src/main/java/accord/messages/CheckStatus.java | 2 +
.../src/main/java/accord/messages/Commit.java | 2 +
.../src/main/java/accord/messages/Defer.java | 2 +-
.../src/main/java/accord/messages/GetDeps.java | 1 +
.../main/java/accord/messages/InformDurable.java | 1 +
.../java/accord/messages/InformHomeDurable.java | 1 +
.../src/main/java/accord/messages/PreAccept.java | 10 +-
.../src/main/java/accord/messages/ReadData.java | 1 +
.../src/main/java/accord/messages/TxnRequest.java | 1 +
.../main/java/accord/messages/WaitOnCommit.java | 1 +
.../main/java/accord/primitives/AbstractKeys.java | 13 +-
.../java/accord/primitives/AbstractRanges.java | 17 +-
.../accord/primitives/AbstractRoutableKeys.java | 11 -
.../accord/primitives/AbstractUnseekableKeys.java | 19 +
.../src/main/java/accord/primitives/Ballot.java | 1 +
.../src/main/java/accord/primitives/Deps.java | 1306 ++------------------
.../main/java/accord/primitives/FullKeyRoute.java | 1 +
.../java/accord/primitives/FullRangeRoute.java | 1 +
.../src/main/java/accord/primitives/KeyDeps.java | 537 ++++++++
.../src/main/java/accord/primitives/KeyRoute.java | 2 +-
.../main/java/accord/primitives/PartialDeps.java | 63 +-
.../java/accord/primitives/PartialKeyRoute.java | 5 +-
.../java/accord/primitives/PartialRangeRoute.java | 4 +
.../main/java/accord/primitives/PartialRoute.java | 1 +
.../main/java/accord/primitives/PartialTxn.java | 3 +
.../src/main/java/accord/primitives/Range.java | 51 +-
.../src/main/java/accord/primitives/RangeDeps.java | 663 ++++++++++
.../src/main/java/accord/primitives/Ranges.java | 2 +-
.../main/java/accord/primitives/RoutableKey.java | 3 +
.../src/main/java/accord/primitives/Route.java | 3 +
.../main/java/accord/primitives/RoutingKeys.java | 7 +-
.../src/main/java/accord/primitives/Seekable.java | 4 +
.../src/main/java/accord/primitives/Seekables.java | 2 +
.../src/main/java/accord/primitives/TxnId.java | 1 +
.../main/java/accord/primitives/Unseekables.java | 2 +
.../main/java/accord/primitives/package-info.java | 4 +-
.../src/main/java/accord/topology/Topology.java | 4 +-
.../src/main/java/accord/utils/ArrayBuffers.java | 123 +-
.../accord/utils/DeterministicIdentitySet.java | 9 +-
.../java/accord/utils/IntrusiveLinkedList.java | 1 +
.../src/main/java/accord/utils/MapReduce.java | 1 +
.../main/java/accord/utils/MapReduceConsume.java | 1 +
.../main/java/accord/utils/RelationMultiMap.java | 1004 +++++++++++++++
.../java/accord/utils/SearchableRangeList.java | 292 +++++
.../accord/utils/SearchableRangeListBuilder.java | 1077 ++++++++++++++++
.../src/main/java/accord/utils/SortedArrays.java | 97 +-
.../java/accord/utils/SymmetricComparator.java | 7 +
.../java/accord/coordinate/CoordinateTest.java | 5 +-
.../test/java/accord/messages/PreAcceptTest.java | 10 +-
.../DepsTest.java => primitives/KeyDepsTest.java} | 127 +-
.../test/java/accord/primitives/RangeDepsTest.java | 229 ++++
.../src/main/java/accord/maelstrom/Json.java | 65 +-
69 files changed, 4426 insertions(+), 1429 deletions(-)
diff --git a/accord-core/src/main/java/accord/api/Agent.java b/accord-core/src/main/java/accord/api/Agent.java
index 83f51a7..0045eb0 100644
--- a/accord-core/src/main/java/accord/api/Agent.java
+++ b/accord-core/src/main/java/accord/api/Agent.java
@@ -47,6 +47,7 @@ public interface Agent extends UncaughtExceptionListener
*/
void onInconsistentTimestamp(Command command, Timestamp prev, Timestamp next);
+ @Override
void onUncaughtException(Throwable t);
void onHandledException(Throwable t);
diff --git a/accord-core/src/main/java/accord/api/Key.java b/accord-core/src/main/java/accord/api/Key.java
index 5307828..8c4078c 100644
--- a/accord-core/src/main/java/accord/api/Key.java
+++ b/accord-core/src/main/java/accord/api/Key.java
@@ -18,6 +18,7 @@
package accord.api;
+import accord.primitives.Range;
import accord.primitives.RoutableKey;
import accord.primitives.Seekable;
@@ -26,4 +27,9 @@ import accord.primitives.Seekable;
*/
public interface Key extends Seekable, RoutableKey
{
+ @Override
+ default Key asKey() { return this; }
+
+ @Override
+ default Range asRange() { throw new UnsupportedOperationException(); }
}
diff --git a/accord-core/src/main/java/accord/api/Result.java b/accord-core/src/main/java/accord/api/Result.java
index a5ac298..d8b8fd6 100644
--- a/accord-core/src/main/java/accord/api/Result.java
+++ b/accord-core/src/main/java/accord/api/Result.java
@@ -28,5 +28,6 @@ import accord.primitives.ProgressToken;
*/
public interface Result extends Outcome
{
+ @Override
default ProgressToken asProgressToken() { return ProgressToken.APPLIED; }
}
diff --git a/accord-core/src/main/java/accord/api/TopologySorter.java b/accord-core/src/main/java/accord/api/TopologySorter.java
index c3587b2..c78f049 100644
--- a/accord-core/src/main/java/accord/api/TopologySorter.java
+++ b/accord-core/src/main/java/accord/api/TopologySorter.java
@@ -15,7 +15,9 @@ public interface TopologySorter
interface StaticSorter extends Supplier, TopologySorter
{
+ @Override
default TopologySorter get(Topology topologies) { return this; }
+ @Override
default TopologySorter get(Topologies topologies) { return this; }
}
diff --git a/accord-core/src/main/java/accord/api/UncaughtExceptionListener.java b/accord-core/src/main/java/accord/api/UncaughtExceptionListener.java
index 60105f0..8395ea6 100644
--- a/accord-core/src/main/java/accord/api/UncaughtExceptionListener.java
+++ b/accord-core/src/main/java/accord/api/UncaughtExceptionListener.java
@@ -5,6 +5,7 @@ import java.util.function.BiConsumer;
public interface UncaughtExceptionListener extends BiConsumer<Object, Throwable>
{
void onUncaughtException(Throwable t);
+ @Override
default void accept(Object ignore, Throwable t)
{
if (t != null)
diff --git a/accord-core/src/main/java/accord/coordinate/Coordinate.java b/accord-core/src/main/java/accord/coordinate/Coordinate.java
index dec539c..aa70507 100644
--- a/accord-core/src/main/java/accord/coordinate/Coordinate.java
+++ b/accord-core/src/main/java/accord/coordinate/Coordinate.java
@@ -53,7 +53,7 @@ public class Coordinate extends AsyncFuture<Result> implements Callback<PreAccep
final Txn txn;
final FullRoute<?> route;
- private FastPathTracker tracker;
+ private final FastPathTracker tracker;
private boolean preAcceptIsDone;
private final List<PreAcceptOk> successes;
@@ -108,6 +108,7 @@ public class Coordinate extends AsyncFuture<Result> implements Callback<PreAccep
tryFailure(failure);
}
+ @Override
public synchronized void onSuccess(Id from, PreAcceptReply reply)
{
if (preAcceptIsDone)
diff --git a/accord-core/src/main/java/accord/coordinate/ReadCoordinator.java b/accord-core/src/main/java/accord/coordinate/ReadCoordinator.java
index 837b2cc..3892b04 100644
--- a/accord-core/src/main/java/accord/coordinate/ReadCoordinator.java
+++ b/accord-core/src/main/java/accord/coordinate/ReadCoordinator.java
@@ -55,7 +55,7 @@ abstract class ReadCoordinator<Reply extends accord.messages.Reply> extends Read
final TxnId txnId;
private boolean isDone;
private Throwable failure;
- Map<Id, Object> debug = DEBUG ? new HashMap<>() : null;
+ final Map<Id, Object> debug = DEBUG ? new HashMap<>() : null;
ReadCoordinator(Node node, Topologies topologies, TxnId txnId)
{
@@ -102,6 +102,7 @@ abstract class ReadCoordinator<Reply extends accord.messages.Reply> extends Read
}
}
+ @Override
public void onSlowResponse(Id from)
{
handle(recordSlowResponse(from));
diff --git a/accord-core/src/main/java/accord/coordinate/Recover.java b/accord-core/src/main/java/accord/coordinate/Recover.java
index 3ad5d67..ccad4e7 100644
--- a/accord-core/src/main/java/accord/coordinate/Recover.java
+++ b/accord-core/src/main/java/accord/coordinate/Recover.java
@@ -100,7 +100,7 @@ public class Recover implements Callback<RecoverReply>, BiConsumer<Result, Throw
for (int i = 0 ; i < waitOn.txnIdCount() ; ++i)
{
TxnId txnId = waitOn.txnId(i);
- new AwaitCommit(node, txnId, waitOn.someRoutables(txnId)).addCallback((success, failure) -> {
+ new AwaitCommit(node, txnId, waitOn.someUnseekables(txnId)).addCallback((success, failure) -> {
if (future.isDone())
return;
if (success != null && remaining.decrementAndGet() == 0)
diff --git a/accord-core/src/main/java/accord/impl/InMemoryCommand.java b/accord-core/src/main/java/accord/impl/InMemoryCommand.java
index d72b574..8525046 100644
--- a/accord-core/src/main/java/accord/impl/InMemoryCommand.java
+++ b/accord-core/src/main/java/accord/impl/InMemoryCommand.java
@@ -309,6 +309,7 @@ public class InMemoryCommand extends Command
return waitingOnCommit != null && !waitingOnCommit.isEmpty();
}
+ @Override
public boolean isWaitingOnDependency()
{
return isWaitingOnCommit() || isWaitingOnApply();
diff --git a/accord-core/src/main/java/accord/impl/InMemoryCommandStore.java b/accord-core/src/main/java/accord/impl/InMemoryCommandStore.java
index 7977d2c..b2444ec 100644
--- a/accord-core/src/main/java/accord/impl/InMemoryCommandStore.java
+++ b/accord-core/src/main/java/accord/impl/InMemoryCommandStore.java
@@ -79,17 +79,20 @@ public class InMemoryCommandStore
this.commandStore = commandStore;
}
+ @Override
public Command ifPresent(TxnId txnId)
{
return commands.get(txnId);
}
// TODO (required): mimic caching to test C* behaviour
+ @Override
public Command ifLoaded(TxnId txnId)
{
return commands.get(txnId);
}
+ @Override
public Command command(TxnId txnId)
{
return commands.computeIfAbsent(txnId, id -> new InMemoryCommand(commandStore, id));
@@ -100,6 +103,7 @@ public class InMemoryCommandStore
return commands.containsKey(txnId);
}
+ @Override
public CommandsForKey commandsForKey(Key key)
{
return commandsForKey.computeIfAbsent(key, k -> new InMemoryCommandsForKey((Key) k));
@@ -110,11 +114,13 @@ public class InMemoryCommandStore
return commandsForKey.containsKey(key);
}
+ @Override
public CommandsForKey maybeCommandsForKey(Key key)
{
return commandsForKey.get(key);
}
+ @Override
public void addAndInvokeListener(TxnId txnId, CommandListener listener)
{
command(txnId).addListener(listener);
@@ -221,6 +227,7 @@ public class InMemoryCommandStore
}
}
+ @Override
public <T> T mapReduce(Routables<?, ?> keysOrRanges, Ranges slice, Function<CommandsForKey, T> map, BinaryOperator<T> reduce, T initialValue)
{
switch (keysOrRanges.kindOfContents()) {
@@ -241,6 +248,7 @@ public class InMemoryCommandStore
}
}
+ @Override
public void forEach(Routables<?, ?> keysOrRanges, Ranges slice, Consumer<CommandsForKey> forEach)
{
switch (keysOrRanges.kindOfContents()) {
@@ -259,6 +267,7 @@ public class InMemoryCommandStore
}
}
+ @Override
public void forEach(Routable keyOrRange, Ranges slice, Consumer<CommandsForKey> forEach)
{
switch (keyOrRange.domain())
@@ -294,6 +303,7 @@ public class InMemoryCommandStore
return submit(context, i -> { consumer.accept(i); return null; });
}
+ @Override
public synchronized <T> Future<T> submit(PreLoadContext context, Function<? super SafeCommandStore, T> function)
{
AsyncPromise<T> promise = new AsyncPromise<>();
diff --git a/accord-core/src/main/java/accord/impl/SimpleProgressLog.java b/accord-core/src/main/java/accord/impl/SimpleProgressLog.java
index e27553f..fa9d48b 100644
--- a/accord-core/src/main/java/accord/impl/SimpleProgressLog.java
+++ b/accord-core/src/main/java/accord/impl/SimpleProgressLog.java
@@ -156,6 +156,7 @@ public class SimpleProgressLog implements ProgressLog.Factory
}
// exists only on home shard
+ // TODO (expected): should not take any prompt action if we're ourselves already coordinating the transaction
class CoordinateState extends Monitoring
{
CoordinateStatus status = CoordinateStatus.NotWitnessed;
diff --git a/accord-core/src/main/java/accord/local/Command.java b/accord-core/src/main/java/accord/local/Command.java
index 4f7697f..16c7a71 100644
--- a/accord-core/src/main/java/accord/local/Command.java
+++ b/accord-core/src/main/java/accord/local/Command.java
@@ -408,7 +408,7 @@ public abstract class Command implements CommandListener, BiConsumer<SafeCommand
{
Ranges ranges = safeStore.ranges().since(executeAt().epoch());
if (ranges != null) {
- partialDeps().forEachOn(ranges, txnId -> {
+ partialDeps().forEach(ranges, txnId -> {
Command command = safeStore.ifLoaded(txnId);
if (command == null)
{
@@ -764,7 +764,7 @@ public abstract class Command implements CommandListener, BiConsumer<SafeCommand
}
Unseekables<?, ?> someKeys = cur.maxUnseekables();
- if (someKeys == null && prev != null) someKeys = prev.partialDeps().someRoutables(cur.txnId());
+ if (someKeys == null && prev != null) someKeys = prev.partialDeps().someUnseekables(cur.txnId());
Invariants.checkState(someKeys != null);
logger.trace("{} blocked on {} until {}", txnIds[0], cur.txnId(), until);
safeStore.progressLog().waiting(cur.txnId(), until, someKeys);
diff --git a/accord-core/src/main/java/accord/local/Node.java b/accord-core/src/main/java/accord/local/Node.java
index 9047034..15de0dc 100644
--- a/accord-core/src/main/java/accord/local/Node.java
+++ b/accord-core/src/main/java/accord/local/Node.java
@@ -159,6 +159,7 @@ public class Node implements ConfigurationService.Listener, NodeTimeService
return messageSink;
}
+ @Override
public long epoch()
{
return topology().epoch();
@@ -235,6 +236,7 @@ public class Node implements ConfigurationService.Listener, NodeTimeService
});
}
+ @Override
public Timestamp uniqueNow(Timestamp atLeast)
{
if (now.get().compareTo(atLeast) < 0)
@@ -247,6 +249,7 @@ public class Node implements ConfigurationService.Listener, NodeTimeService
return uniqueNow();
}
+ @Override
public long now()
{
return nowSupplier.getAsLong();
@@ -505,6 +508,7 @@ public class Node implements ConfigurationService.Listener, NodeTimeService
return agent;
}
+ @Override
public Id id()
{
return id;
diff --git a/accord-core/src/main/java/accord/local/SafeCommandStore.java b/accord-core/src/main/java/accord/local/SafeCommandStore.java
index 04ace5c..1dc118c 100644
--- a/accord-core/src/main/java/accord/local/SafeCommandStore.java
+++ b/accord-core/src/main/java/accord/local/SafeCommandStore.java
@@ -61,7 +61,6 @@ public interface SafeCommandStore
void forEach(Routables<?, ?> keys, Ranges slice, Consumer<CommandsForKey> forEach);
void forEach(Routable keyOrRange, Ranges slice, Consumer<CommandsForKey> forEach);
-
CommandStore commandStore();
DataStore dataStore();
Agent agent();
diff --git a/accord-core/src/main/java/accord/messages/Accept.java b/accord-core/src/main/java/accord/messages/Accept.java
index 7ea2631..bb9cffd 100644
--- a/accord-core/src/main/java/accord/messages/Accept.java
+++ b/accord-core/src/main/java/accord/messages/Accept.java
@@ -114,6 +114,7 @@ public class Accept extends TxnRequest.WithUnsynced<Accept.AcceptReply>
node.reply(replyTo, replyContext, reply);
}
+ @Override
public void process()
{
node.mapReduceConsumeLocal(this, minEpoch, executeAt.epoch(), this);
@@ -220,6 +221,7 @@ public class Accept extends TxnRequest.WithUnsynced<Accept.AcceptReply>
this.someKey = someKey;
}
+ @Override
public void process()
{
node.mapReduceConsumeLocal(this, someKey, txnId.epoch(), this);
diff --git a/accord-core/src/main/java/accord/messages/Apply.java b/accord-core/src/main/java/accord/messages/Apply.java
index c692d8d..7dac560 100644
--- a/accord-core/src/main/java/accord/messages/Apply.java
+++ b/accord-core/src/main/java/accord/messages/Apply.java
@@ -70,12 +70,14 @@ public class Apply extends TxnRequest<ApplyReply>
this.result = result;
}
+ @Override
public void process()
{
// note, we do not also commit here if txnId.epoch != executeAt.epoch, as the scope() for a commit would be different
node.mapReduceConsumeLocal(this, txnId.epoch(), untilEpoch, this);
}
+ @Override
public ApplyReply apply(SafeCommandStore safeStore)
{
Command command = safeStore.command(txnId);
@@ -91,6 +93,7 @@ public class Apply extends TxnRequest<ApplyReply>
}
}
+ @Override
public ApplyReply reduce(ApplyReply a, ApplyReply b)
{
return a.compareTo(b) >= 0 ? a : b;
diff --git a/accord-core/src/main/java/accord/messages/BeginRecovery.java b/accord-core/src/main/java/accord/messages/BeginRecovery.java
index dad40c5..2d4bd1d 100644
--- a/accord-core/src/main/java/accord/messages/BeginRecovery.java
+++ b/accord-core/src/main/java/accord/messages/BeginRecovery.java
@@ -297,7 +297,7 @@ public class BeginRecovery extends TxnRequest<BeginRecovery.RecoverReply>
private static Deps acceptedStartedBeforeWithoutWitnessing(SafeCommandStore commandStore, TxnId txnId, Ranges ranges, Seekables<?, ?> keys)
{
- try (Deps.OrderedBuilder builder = Deps.orderedBuilder(true))
+ try (Deps.Builder builder = Deps.builder())
{
commandStore.forEach(keys, ranges, forKey -> {
// accepted txns with an earlier txnid that do not have our txnid as a dependency
@@ -312,10 +312,9 @@ public class BeginRecovery extends TxnRequest<BeginRecovery.RecoverReply>
* Which is to say, we expect the previously proposed dependencies (if any) to be used to evaluate this
* condition.
*/
- builder.nextKey(forKey.key());
forKey.uncommitted().before(txnId, RorWs, WITHOUT, txnId, HAS_BEEN, Accepted).forEach((command) -> {
if (command.executeAt.compareTo(txnId) > 0)
- builder.add(command.txnId);
+ builder.add(forKey.key(), command.txnId);
});
});
return builder.build();
@@ -324,7 +323,7 @@ public class BeginRecovery extends TxnRequest<BeginRecovery.RecoverReply>
private static Deps committedStartedBeforeAndWitnessed(SafeCommandStore commandStore, TxnId txnId, Ranges ranges, Seekables<?, ?> keys)
{
- try (Deps.OrderedBuilder builder = Deps.orderedBuilder(true))
+ try (Deps.Builder builder = Deps.builder())
{
commandStore.forEach(keys, ranges, forKey -> {
/*
@@ -332,9 +331,8 @@ public class BeginRecovery extends TxnRequest<BeginRecovery.RecoverReply>
* so that we can remove these from the set of acceptedStartedBeforeAndDidNotWitness
* on other nodes, to minimise the number of transactions we try to wait for on recovery
*/
- builder.nextKey(forKey.key());
forKey.committedById().before(txnId, RorWs, WITH, txnId, HAS_BEEN, Committed)
- .forEach(builder::add);
+ .forEach(id -> builder.add(forKey.key(), id));
});
return builder.build();
}
diff --git a/accord-core/src/main/java/accord/messages/CheckStatus.java b/accord-core/src/main/java/accord/messages/CheckStatus.java
index d3242dd..0399e1e 100644
--- a/accord-core/src/main/java/accord/messages/CheckStatus.java
+++ b/accord-core/src/main/java/accord/messages/CheckStatus.java
@@ -100,6 +100,7 @@ public class CheckStatus extends AbstractEpochRequest<CheckStatus.CheckStatusOk>
this.includeInfo = includeInfo;
}
+ @Override
public void process()
{
node.mapReduceConsumeLocal(this, query, startEpoch, endEpoch, this);
@@ -272,6 +273,7 @@ public class CheckStatus extends AbstractEpochRequest<CheckStatus.CheckStatusOk>
* reply, the info would potentially be unsafe to act upon when given a higher status
* (e.g. Accepted executeAt is very different to Committed executeAt))
*/
+ @Override
public CheckStatusOk merge(CheckStatusOk that)
{
CheckStatusOk max = super.merge(that);
diff --git a/accord-core/src/main/java/accord/messages/Commit.java b/accord-core/src/main/java/accord/messages/Commit.java
index 55c1c88..a498cd7 100644
--- a/accord-core/src/main/java/accord/messages/Commit.java
+++ b/accord-core/src/main/java/accord/messages/Commit.java
@@ -138,6 +138,7 @@ public class Commit extends TxnRequest<ReadNack>
return Keys.EMPTY;
}
+ @Override
public void process()
{
node.mapReduceConsumeLocal(this, txnId.epoch(), executeAt.epoch(), this);
@@ -268,6 +269,7 @@ public class Commit extends TxnRequest<ReadNack>
return waitForEpoch;
}
+ @Override
public void process(Node node, Id from, ReplyContext replyContext)
{
node.forEachLocal(this, scope, txnId.epoch(), invalidateUntilEpoch,
diff --git a/accord-core/src/main/java/accord/messages/Defer.java b/accord-core/src/main/java/accord/messages/Defer.java
index ede92ba..6fa9579 100644
--- a/accord-core/src/main/java/accord/messages/Defer.java
+++ b/accord-core/src/main/java/accord/messages/Defer.java
@@ -18,7 +18,7 @@ class Defer implements CommandListener
final Function<Command, Ready> waitUntil;
final TxnRequest<?> request;
- IntHashSet waitingOn = new IntHashSet(); // TODO (easy): use Agrona when available
+ final IntHashSet waitingOn = new IntHashSet(); // TODO (easy): use Agrona when available
int waitingOnCount;
boolean isDone;
diff --git a/accord-core/src/main/java/accord/messages/GetDeps.java b/accord-core/src/main/java/accord/messages/GetDeps.java
index de4d518..13e9bc4 100644
--- a/accord-core/src/main/java/accord/messages/GetDeps.java
+++ b/accord-core/src/main/java/accord/messages/GetDeps.java
@@ -42,6 +42,7 @@ public class GetDeps extends TxnRequest.WithUnsynced<PartialDeps>
this.kind = kind;
}
+ @Override
public void process()
{
node.mapReduceConsumeLocal(this, minEpoch, executeAt.epoch(), this);
diff --git a/accord-core/src/main/java/accord/messages/InformDurable.java b/accord-core/src/main/java/accord/messages/InformDurable.java
index 5586c22..20066e4 100644
--- a/accord-core/src/main/java/accord/messages/InformDurable.java
+++ b/accord-core/src/main/java/accord/messages/InformDurable.java
@@ -45,6 +45,7 @@ public class InformDurable extends TxnRequest<Reply> implements PreLoadContext
this.durability = durability;
}
+ @Override
public void process()
{
Timestamp at = txnId;
diff --git a/accord-core/src/main/java/accord/messages/InformHomeDurable.java b/accord-core/src/main/java/accord/messages/InformHomeDurable.java
index 1f91153..d0282f4 100644
--- a/accord-core/src/main/java/accord/messages/InformHomeDurable.java
+++ b/accord-core/src/main/java/accord/messages/InformHomeDurable.java
@@ -29,6 +29,7 @@ public class InformHomeDurable implements Request
this.persistedOn = persistedOn;
}
+ @Override
public void process(Node node, Id replyToNode, ReplyContext replyContext)
{
// TODO (expected, efficiency): do not load txnId first
diff --git a/accord-core/src/main/java/accord/messages/PreAccept.java b/accord-core/src/main/java/accord/messages/PreAccept.java
index 310c0a0..bb90b40 100644
--- a/accord-core/src/main/java/accord/messages/PreAccept.java
+++ b/accord-core/src/main/java/accord/messages/PreAccept.java
@@ -88,6 +88,7 @@ public class PreAccept extends WithUnsynced<PreAccept.PreAcceptReply>
node.mapReduceConsumeLocal(this, minEpoch, maxEpoch, this);
}
+ @Override
public PreAcceptReply apply(SafeCommandStore safeStore)
{
// note: this diverges from the paper, in that instead of waiting for JoinShard,
@@ -210,24 +211,23 @@ public class PreAccept extends WithUnsynced<PreAccept.PreAcceptReply>
static PartialDeps calculatePartialDeps(SafeCommandStore commandStore, TxnId txnId, Seekables<?, ?> keys, Txn.Kind kindOfTxn, Timestamp executeAt, Ranges ranges)
{
- try (PartialDeps.OrderedBuilder builder = PartialDeps.orderedBuilder(ranges, false))
+ try (PartialDeps.Builder builder = PartialDeps.builder(ranges))
{
return calculateDeps(commandStore, txnId, keys, kindOfTxn, executeAt, ranges, builder);
}
}
- private static <T extends Deps> T calculateDeps(SafeCommandStore commandStore, TxnId txnId, Seekables<?, ?> keys, Txn.Kind kindOfTxn, Timestamp executeAt, Ranges ranges, Deps.AbstractOrderedBuilder<T> builder)
+ private static <T extends Deps> T calculateDeps(SafeCommandStore commandStore, TxnId txnId, Seekables<?, ?> keys, Txn.Kind kindOfTxn, Timestamp executeAt, Ranges ranges, Deps.AbstractBuilder<T> builder)
{
TestKind testKind = kindOfTxn.isWrite() ? RorWs : Ws;
commandStore.forEach(keys, ranges, forKey -> {
- builder.nextKey(forKey.key());
forKey.uncommitted().before(executeAt, testKind, ANY_DEPS, null, ANY_STATUS, null)
.forEach(info -> {
- if (!info.txnId.equals(txnId)) builder.add(info.txnId);
+ if (!info.txnId.equals(txnId)) builder.add(forKey.key(), info.txnId);
});
forKey.committedByExecuteAt().before(executeAt, testKind, ANY_DEPS, null, ANY_STATUS, null)
.forEach(id -> {
- if (!id.equals(txnId)) builder.add(id);
+ if (!id.equals(txnId)) builder.add(forKey.key(), id);
});
});
diff --git a/accord-core/src/main/java/accord/messages/ReadData.java b/accord-core/src/main/java/accord/messages/ReadData.java
index d204de2..fee7e27 100644
--- a/accord-core/src/main/java/accord/messages/ReadData.java
+++ b/accord-core/src/main/java/accord/messages/ReadData.java
@@ -320,6 +320,7 @@ public class ReadData extends AbstractEpochRequest<ReadData.ReadNack> implements
return READ_RSP;
}
+ @Override
public boolean isOk()
{
return true;
diff --git a/accord-core/src/main/java/accord/messages/TxnRequest.java b/accord-core/src/main/java/accord/messages/TxnRequest.java
index 58bc8d4..5b9b928 100644
--- a/accord-core/src/main/java/accord/messages/TxnRequest.java
+++ b/accord-core/src/main/java/accord/messages/TxnRequest.java
@@ -129,6 +129,7 @@ public abstract class TxnRequest<R> implements Request, PreLoadContext, MapReduc
* to permit a recipient to process a request before knowing of a topology change if the sender determines it is
* safe to do so.
*/
+ @Override
public long waitForEpoch()
{
return waitForEpoch;
diff --git a/accord-core/src/main/java/accord/messages/WaitOnCommit.java b/accord-core/src/main/java/accord/messages/WaitOnCommit.java
index 490bc65..b7c20f9 100644
--- a/accord-core/src/main/java/accord/messages/WaitOnCommit.java
+++ b/accord-core/src/main/java/accord/messages/WaitOnCommit.java
@@ -65,6 +65,7 @@ public class WaitOnCommit implements Request, MapReduceConsume<SafeCommandStore,
this.scope = scope;
}
+ @Override
public void process(Node node, Id replyToNode, ReplyContext replyContext)
{
this.node = node;
diff --git a/accord-core/src/main/java/accord/primitives/AbstractKeys.java b/accord-core/src/main/java/accord/primitives/AbstractKeys.java
index 9b11cc4..6fc570a 100644
--- a/accord-core/src/main/java/accord/primitives/AbstractKeys.java
+++ b/accord-core/src/main/java/accord/primitives/AbstractKeys.java
@@ -35,11 +35,18 @@ public abstract class AbstractKeys<K extends RoutableKey, KS extends Routables<K
return Arrays.equals(keys, that.keys);
}
- public final int indexOf(K key)
+ @Override
+ public int indexOf(K key)
+ {
+ return Arrays.binarySearch(keys, key);
+ }
+
+ public int indexOf(RoutingKey key)
{
return Arrays.binarySearch(keys, key);
}
+ @Override
public final K get(int indexOf)
{
return keys[indexOf];
@@ -51,21 +58,25 @@ public abstract class AbstractKeys<K extends RoutableKey, KS extends Routables<K
return Key;
}
+ @Override
public final boolean isEmpty()
{
return keys.length == 0;
}
+ @Override
public final int size()
{
return keys.length;
}
+ @Override
public final boolean contains(RoutableKey key)
{
return Arrays.binarySearch(keys, key) >= 0;
}
+ @Override
public final boolean containsAll(Routables<?, ?> keysOrRanges)
{
return keysOrRanges.size() == Routables.foldl(keysOrRanges, this, (k, p, v, i) -> v + 1, 0, 0, 0);
diff --git a/accord-core/src/main/java/accord/primitives/AbstractRanges.java b/accord-core/src/main/java/accord/primitives/AbstractRanges.java
index 9d5a4fa..740233b 100644
--- a/accord-core/src/main/java/accord/primitives/AbstractRanges.java
+++ b/accord-core/src/main/java/accord/primitives/AbstractRanges.java
@@ -50,16 +50,19 @@ public abstract class AbstractRanges<RS extends Routables<Range, ?>> implements
return SortedArrays.binarySearch(ranges, 0, ranges.length, key, (k, r) -> -r.compareTo(k), FAST);
}
+ @Override
public int indexOf(Range find)
{
return SortedArrays.binarySearch(ranges, 0, ranges.length, find, Range::compareIntersecting, FAST);
}
+ @Override
public boolean contains(RoutableKey key)
{
return indexOf(key) >= 0;
}
+ @Override
public boolean containsAll(Routables<?, ?> that)
{
switch (that.kindOfContents())
@@ -90,6 +93,7 @@ public abstract class AbstractRanges<RS extends Routables<Range, ?>> implements
return ((int) supersetLinearMerge(this.ranges, that.ranges)) == that.size();
}
+ @Override
public int size()
{
return ranges.length;
@@ -128,6 +132,7 @@ public abstract class AbstractRanges<RS extends Routables<Range, ?>> implements
return findNextIntersection(0, keys, 0) >= 0;
}
+ @Override
public boolean intersects(AbstractRanges<?> that)
{
return SortedArrays.findNextIntersection(this.ranges, 0, that.ranges, 0, Range::compareIntersecting) >= 0;
@@ -139,12 +144,14 @@ public abstract class AbstractRanges<RS extends Routables<Range, ?>> implements
}
// returns ri in low 32 bits, ki in top, or -1 if no match found
+ @Override
public long findNextIntersection(int ri, AbstractKeys<?, ?> keys, int ki)
{
return swapHighLow32b(SortedArrays.findNextIntersectionWithMultipleMatches(keys.keys, ki, ranges, ri));
}
// returns ki in bottom 32 bits, ri in top, or -1 if no match found
+ @Override
public long findNextIntersection(int thisi, AbstractRanges<?> that, int thati)
{
return SortedArrays.findNextIntersectionWithMultipleMatches(ranges, thisi, that.ranges, thati, Range::compareIntersecting, Range::compareIntersecting);
@@ -411,20 +418,20 @@ public abstract class AbstractRanges<RS extends Routables<Range, ?>> implements
if (ranges.length == 0)
return input;
- ObjectBuffers<Range> cachedKeyRanges = cachedRanges();
- Range[] buffer = cachedKeyRanges.get(ranges.length);
+ ObjectBuffers<Range> cachedRanges = cachedRanges();
+ Range[] buffer = cachedRanges.get(ranges.length);
try
{
int count = copyAndMergeTouching(ranges, 0, buffer, 0, ranges.length);
if (count == buffer.length)
return input;
- Range[] result = cachedKeyRanges.complete(buffer, count);
- cachedKeyRanges.discard(buffer, count);
+ Range[] result = cachedRanges.complete(buffer, count);
+ cachedRanges.discard(buffer, count);
return constructor.apply(result);
}
catch (Throwable t)
{
- cachedKeyRanges.forceDiscard(buffer, ranges.length);
+ cachedRanges.forceDiscard(buffer, ranges.length);
throw t;
}
}
diff --git a/accord-core/src/main/java/accord/primitives/AbstractRoutableKeys.java b/accord-core/src/main/java/accord/primitives/AbstractRoutableKeys.java
deleted file mode 100644
index a7ae455..0000000
--- a/accord-core/src/main/java/accord/primitives/AbstractRoutableKeys.java
+++ /dev/null
@@ -1,11 +0,0 @@
-package accord.primitives;
-
-import accord.api.RoutingKey;
-
-public abstract class AbstractRoutableKeys<KS extends Unseekables<RoutingKey, ?>> extends AbstractKeys<RoutingKey, KS> implements Iterable<RoutingKey>, Unseekables<RoutingKey, KS>
-{
- AbstractRoutableKeys(RoutingKey[] keys)
- {
- super(keys);
- }
-}
diff --git a/accord-core/src/main/java/accord/primitives/AbstractUnseekableKeys.java b/accord-core/src/main/java/accord/primitives/AbstractUnseekableKeys.java
new file mode 100644
index 0000000..6176193
--- /dev/null
+++ b/accord-core/src/main/java/accord/primitives/AbstractUnseekableKeys.java
@@ -0,0 +1,19 @@
+package accord.primitives;
+
+import accord.api.RoutingKey;
+
+import java.util.Arrays;
+
+public abstract class AbstractUnseekableKeys<KS extends Unseekables<RoutingKey, ?>> extends AbstractKeys<RoutingKey, KS> implements Iterable<RoutingKey>, Unseekables<RoutingKey, KS>
+{
+ AbstractUnseekableKeys(RoutingKey[] keys)
+ {
+ super(keys);
+ }
+
+ @Override
+ public final int indexOf(RoutingKey key)
+ {
+ return Arrays.binarySearch(keys, key);
+ }
+}
diff --git a/accord-core/src/main/java/accord/primitives/Ballot.java b/accord-core/src/main/java/accord/primitives/Ballot.java
index 7e66668..121dd0a 100644
--- a/accord-core/src/main/java/accord/primitives/Ballot.java
+++ b/accord-core/src/main/java/accord/primitives/Ballot.java
@@ -54,6 +54,7 @@ public class Ballot extends Timestamp
super(msb, lsb, node);
}
+ @Override
public Ballot merge(Timestamp that)
{
return merge(this, that, Ballot::fromBits);
diff --git a/accord-core/src/main/java/accord/primitives/Deps.java b/accord-core/src/main/java/accord/primitives/Deps.java
index f72b33b..5b4a984 100644
--- a/accord-core/src/main/java/accord/primitives/Deps.java
+++ b/accord-core/src/main/java/accord/primitives/Deps.java
@@ -18,1311 +18,223 @@
package accord.primitives;
-import java.util.*;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-import java.util.function.Function;
-import java.util.function.Predicate;
-
-import java.util.stream.Collectors;
-
import accord.api.Key;
-import accord.utils.ArrayBuffers;
-import accord.api.RoutingKey;
-import accord.utils.SortedArrays;
import accord.utils.Invariants;
-import static accord.utils.ArrayBuffers.*;
-import static accord.utils.SortedArrays.*;
-import static accord.utils.SortedArrays.Search.FAST;
+import java.util.AbstractList;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.function.Consumer;
+import java.util.function.Function;
+import java.util.function.Predicate;
/**
- * A collection of dependencies for a transaction, organised by the key the dependency is adopted via.
- * An inverse map from TxnId to Key may also be constructed and stored in this collection.
+ * A collection of transaction dependencies, keyed by the key or range on which they were adopted
*/
-// TODO (desired, consider): switch to RoutingKey? Would mean adopting execution dependencies less precisely, but saving ser/deser of large keys
-public class Deps implements Iterable<Map.Entry<Key, TxnId>>
+public class Deps
{
- private static final boolean DEBUG_CHECKS = true;
-
- private static final TxnId[] NO_TXNIDS = new TxnId[0];
- private static final int[] NO_INTS = new int[0];
- public static final Deps NONE = new Deps(Keys.EMPTY, NO_TXNIDS, NO_INTS);
+ public static final Deps NONE = new Deps(KeyDeps.NONE, RangeDeps.NONE);
- public static class SerializerSupport
+ public static Builder builder()
{
- private SerializerSupport() {}
-
- public static int keyToTxnIdCount(Deps deps)
- {
- return deps.keyToTxnId.length;
- }
-
- public static int keyToTxnId(Deps deps, int idx)
- {
- return deps.keyToTxnId[idx];
- }
-
- public static Deps create(Keys keys, TxnId[] txnIds, int[] keyToTxnId)
- {
- return new Deps(keys, txnIds, keyToTxnId);
- }
- }
-
- public static Deps none(Keys keys)
- {
- int[] keysToTxnId = new int[keys.size()];
- Arrays.fill(keysToTxnId, keys.size());
- return new Deps(keys, NO_TXNIDS, keysToTxnId);
- }
-
- /**
- * Expects Command to be provided in TxnId order
- */
- public static OrderedBuilder orderedBuilder(boolean hasOrderedTxnId)
- {
- return new OrderedBuilder(hasOrderedTxnId);
+ return new Builder();
}
// TODO (expected, efficiency): cache this object per thread
- public static abstract class AbstractOrderedBuilder<T extends Deps> implements AutoCloseable
+ public static abstract class AbstractBuilder<T extends Deps> implements AutoCloseable
{
- final ObjectBuffers<TxnId> cachedTxnIds = cachedTxnIds();
- final ObjectBuffers<Key> cachedKeys = cachedKeys();
- final IntBuffers cachedInts = cachedInts();
-
- final boolean hasOrderedTxnId;
- Key[] keys;
- int[] keyLimits;
- // txnId -> Offset
- TxnId[] keyToTxnId;
- int keyCount;
- int keyOffset;
- int totalCount;
-
- public AbstractOrderedBuilder(boolean hasOrderedTxnId)
- {
- this.keys = cachedKeys.get(16);
- this.keyLimits = cachedInts.getInts(keys.length);
- this.hasOrderedTxnId = hasOrderedTxnId;
- this.keyToTxnId = cachedTxnIds.get(16);
- }
-
- public boolean isEmpty()
- {
- return totalCount() == 0;
- }
-
- private int totalCount()
- {
- return totalCount;
- }
+ final KeyDeps.Builder keyBuilder;
+ RangeDeps.Builder rangeBuilder;
- public void nextKey(Key key)
+ AbstractBuilder()
{
- if (keyCount > 0 && keys[keyCount - 1].compareTo(key) >= 0)
- {
- throw new IllegalArgumentException("Key " + key + " has already been visited or was provided out of order ("
- + Arrays.toString(Arrays.copyOf(keys, keyCount)) + ")");
- }
-
- finishKey();
-
- if (keyCount == keys.length)
- {
- Key[] newKeys = cachedKeys.get(keyCount * 2);
- System.arraycopy(keys, 0, newKeys, 0, keyCount);
- cachedKeys.forceDiscard(keys, keyCount);
- keys = newKeys;
- int[] newKeyLimits = cachedInts.getInts(keyCount * 2);
- System.arraycopy(keyLimits, 0, newKeyLimits, 0, keyCount);
- cachedInts.forceDiscard(keyLimits, keyCount);
- keyLimits = newKeyLimits;
- }
- keys[keyCount++] = key;
+ this.keyBuilder = KeyDeps.builder();
}
- private void finishKey()
+ public AbstractBuilder<T> add(Seekable keyOrRange, TxnId txnId)
{
- if (totalCount == keyOffset && keyCount > 0)
- --keyCount; // remove this key; no data
-
- if (keyCount == 0)
- return;
-
- if (totalCount != keyOffset && !hasOrderedTxnId)
+ switch (keyOrRange.domain())
{
- // TODO (low priority, efficiency): this allocates a significant amount of memory: would be preferable to be able to sort using a pre-defined scratch buffer
- Arrays.sort(keyToTxnId, keyOffset, totalCount);
- for (int i = keyOffset + 1 ; i < totalCount ; ++i)
- {
- if (keyToTxnId[i - 1].equals(keyToTxnId[i]))
- throw new IllegalArgumentException("TxnId for " + keys[keyCount - 1] + " are not unique: " + Arrays.asList(keyToTxnId).subList(keyOffset, totalCount));
- }
+ default: throw new AssertionError();
+ case Key:
+ keyBuilder.add(keyOrRange.asKey(), txnId);
+ break;
+ case Range:
+ if (rangeBuilder == null)
+ rangeBuilder = RangeDeps.builder();
+ rangeBuilder.add(keyOrRange.asRange(), txnId);
+ break;
}
-
- keyLimits[keyCount - 1] = totalCount;
- keyOffset = totalCount;
- }
-
- public void add(Key key, TxnId txnId)
- {
- if (keyCount == 0 || !keys[keyCount - 1].equals(key))
- nextKey(key);
- add(txnId);
- }
-
- /**
- * Add this command as a dependency for each intersecting key
- */
- public void add(TxnId txnId)
- {
- if (hasOrderedTxnId && totalCount > keyOffset && keyToTxnId[totalCount - 1].compareTo(txnId) >= 0)
- throw new IllegalArgumentException("TxnId provided out of order");
-
- if (totalCount >= keyToTxnId.length)
- {
- TxnId[] newTxnIds = cachedTxnIds.get(keyToTxnId.length * 2);
- System.arraycopy(keyToTxnId, 0, newTxnIds, 0, totalCount);
- cachedTxnIds.forceDiscard(keyToTxnId, totalCount);
- keyToTxnId = newTxnIds;
- }
-
- keyToTxnId[totalCount++] = txnId;
- }
-
- public T build()
- {
- if (totalCount == 0)
- return build(Keys.EMPTY, NO_TXNIDS, NO_INTS);
-
- finishKey();
-
- TxnId[] uniqueTxnId = cachedTxnIds.get(totalCount);
- System.arraycopy(keyToTxnId, 0, uniqueTxnId, 0, totalCount);
- Arrays.sort(uniqueTxnId, 0, totalCount);
- int txnIdCount = 1;
- for (int i = 1 ; i < totalCount ; ++i)
- {
- if (!uniqueTxnId[txnIdCount - 1].equals(uniqueTxnId[i]))
- uniqueTxnId[txnIdCount++] = uniqueTxnId[i];
- }
-
- TxnId[] txnIds = cachedTxnIds.complete(uniqueTxnId, txnIdCount);
- cachedTxnIds.discard(uniqueTxnId, totalCount);
-
- int[] result = new int[keyCount + totalCount];
- int offset = keyCount;
- for (int k = 0 ; k < keyCount ; ++k)
- {
- result[k] = keyCount + keyLimits[k];
- int from = k == 0 ? 0 : keyLimits[k - 1];
- int to = keyLimits[k];
- offset = (int)SortedArrays.foldlIntersection(txnIds, 0, txnIdCount, keyToTxnId, from, to, (key, p, v, li, ri) -> {
- result[(int)v] = li;
- return v + 1;
- }, keyCount, offset, -1);
- }
-
- return build(Keys.ofSortedUnchecked(cachedKeys.complete(keys, keyCount)), txnIds, result);
+ return this;
}
- abstract T build(Keys keys, TxnId[] txnIds, int[] keyToTxnId);
+ public abstract T build();
@Override
public void close()
{
- cachedKeys.discard(keys, keyCount);
- cachedInts.forceDiscard(keyLimits, keyCount);
- cachedTxnIds.forceDiscard(keyToTxnId, totalCount);
- }
- }
-
- public static class OrderedBuilder extends AbstractOrderedBuilder<Deps>
- {
- public OrderedBuilder(boolean hasOrderedTxnId)
- {
- super(hasOrderedTxnId);
- }
-
- @Override
- Deps build(Keys keys, TxnId[] txnIds, int[] keysToTxnIds)
- {
- return new Deps(keys, txnIds, keysToTxnIds);
+ keyBuilder.close();
+ if (rangeBuilder != null)
+ rangeBuilder.close();
}
}
- /**
- * An object for managing a sequence of efficient linear merges Deps objects.
- * Its primary purpose is to manage input and output buffers, so that we reuse output buffers
- * as input to the next merge, and if any input is a superset of the other inputs that this input
- * is returned unmodified.
- *
- * This is achieved by using PassThroughXBuffers so that the result buffers (and their sizes) are returned
- * unmodified, and the buffers are cached as far as possible. In general, the buffers should be taken
- * out of pre-existing caches, but if the buffers are too large then we cache any additional buffers we
- * allocate for the duration of the merge.
- */
- private static class LinearMerger extends PassThroughObjectAndIntBuffers<TxnId> implements DepsConstructor<Key, TxnId, Object>
+ public static class Builder extends AbstractBuilder<Deps>
{
- final PassThroughObjectBuffers<Key> keyBuffers;
- Key[] bufKeys;
- TxnId[] bufTxnIds;
- int[] buf = null;
- int bufKeysLength, bufTxnIdsLength = 0, bufLength = 0;
- Deps from = null;
-
- LinearMerger()
+ public Builder()
{
- super(cachedTxnIds(), cachedInts());
- keyBuffers = new PassThroughObjectBuffers<>(cachedKeys());
+ super();
}
@Override
- public Object construct(Key[] keys, int keysLength, TxnId[] txnIds, int txnIdsLength, int[] out, int outLength)
- {
- if (from == null)
- {
- // if our input buffers were themselves buffers, we want to discard them unless they have been returned back to us
- discard(keys, txnIds, out);
- }
- else if (buf != out)
- {
- // the output is not equal to a prior input
- from = null;
- }
-
- if (from == null)
- {
- bufKeys = keys;
- bufKeysLength = keysLength;
- bufTxnIds = txnIds;
- bufTxnIdsLength = txnIdsLength;
- buf = out;
- bufLength = outLength;
- }
- else
- {
- Invariants.checkState(keys == bufKeys && keysLength == bufKeysLength);
- Invariants.checkState(txnIds == bufTxnIds && txnIdsLength == bufTxnIdsLength);
- Invariants.checkState(outLength == bufLength);
- }
- return null;
- }
-
- void update(Deps deps)
- {
- if (buf == null)
- {
- bufKeys = deps.keys.keys;
- bufKeysLength = deps.keys.keys.length;
- bufTxnIds = deps.txnIds;
- bufTxnIdsLength = deps.txnIds.length;
- buf = deps.keyToTxnId;
- bufLength = deps.keyToTxnId.length;
- from = deps;
- return;
- }
-
- linearUnion(
- bufKeys, bufKeysLength, bufTxnIds, bufTxnIdsLength, buf, bufLength,
- deps.keys.keys, deps.keys.keys.length, deps.txnIds, deps.txnIds.length, deps.keyToTxnId, deps.keyToTxnId.length,
- keyBuffers, this, this, this
- );
- if (buf == deps.keyToTxnId)
- {
- Invariants.checkState(deps.keys.keys == bufKeys && deps.keys.keys.length == bufKeysLength);
- Invariants.checkState(deps.txnIds == bufTxnIds && deps.txnIds.length == bufTxnIdsLength);
- Invariants.checkState(deps.keyToTxnId.length == bufLength);
- from = deps;
- }
- }
-
- Deps get()
- {
- if (buf == null)
- return NONE;
-
- if (from != null)
- return from;
-
- return new Deps(
- Keys.ofSortedUnchecked(keyBuffers.realComplete(bufKeys, bufKeysLength)),
- realComplete(bufTxnIds, bufTxnIdsLength),
- realComplete(buf, bufLength));
- }
-
- /**
- * Free any buffers we no longer need
- */
- void discard()
+ public Deps build()
{
- if (from == null)
- discard(null, null, null);
- }
-
- /**
- * Free buffers unless they are equal to the corresponding parameter
- */
- void discard(Key[] freeKeysIfNot, TxnId[] freeTxnIdsIfNot, int[] freeBufIfNot)
- {
- if (from != null)
- return;
-
- if (bufKeys != freeKeysIfNot)
- {
- keyBuffers.realDiscard(bufKeys, bufKeysLength);
- bufKeys = null;
- }
- if (bufTxnIds != freeTxnIdsIfNot)
- {
- realDiscard(bufTxnIds, bufTxnIdsLength);
- bufTxnIds = null;
- }
- if (buf != freeBufIfNot)
- {
- realDiscard(buf, bufLength);
- buf = null;
- }
+ return new Deps(keyBuilder.build(), rangeBuilder == null ? RangeDeps.NONE : rangeBuilder.build());
}
}
- public static <T> Deps merge(List<T> merge, Function<T, Deps> getter)
- {
- LinearMerger linearMerger = new LinearMerger();
- try
- {
- int mergeIndex = 0, mergeSize = merge.size();
- while (mergeIndex < mergeSize)
- {
- Deps deps = getter.apply(merge.get(mergeIndex++));
- if (deps == null || deps.isEmpty())
- continue;
-
- linearMerger.update(deps);
- }
-
- return linearMerger.get();
- }
- finally
- {
- linearMerger.discard();
- }
- }
-
- final Keys keys; // unique Keys
- final TxnId[] txnIds; // unique TxnId TODO (low priority, efficiency): this could be a BTree?
-
- /**
- * This represents a map of {@code Key -> [TxnId] } where each TxnId is actually a pointer into the txnIds array.
- * The beginning of the array (the first keys.size() entries) are offsets into this array.
- * <p/>
- * Example:
- * <p/>
- * {@code
- * int keyIdx = keys.indexOf(key);
- * int startOfTxnOffset = keyIdx == 0 ? keys.size() : keyToTxnId[keyIdx - 1];
- * int endOfTxnOffset = keyToTxnId[keyIdx];
- * for (int i = startOfTxnOffset; i < endOfTxnOffset; i++)
- * {
- * TxnId id = txnIds[keyToTxnId[i]]
- * ...
- * }
- * }
- */
- final int[] keyToTxnId; // Key -> [TxnId]
- // Lazy loaded in ensureTxnIdToKey()
- int[] txnIdToKey; // TxnId -> [Key]
+ public final KeyDeps keyDeps;
+ public final RangeDeps rangeDeps;
- Deps(Keys keys, TxnId[] txnIds, int[] keyToTxnId)
+ public Deps(KeyDeps keyDeps, RangeDeps rangeDeps)
{
- this.keys = keys;
- this.txnIds = txnIds;
- this.keyToTxnId = keyToTxnId;
- if (!(keys.isEmpty() || keyToTxnId[keys.size() - 1] == keyToTxnId.length))
- throw new IllegalArgumentException(String.format("Last key (%s) in keyToTxnId does not point (%d) to the end of the array (%d);\nkeyToTxnId=%s", keys.get(keys.size() - 1), keyToTxnId[keys.size() - 1], keyToTxnId.length, Arrays.toString(keyToTxnId)));
- if (DEBUG_CHECKS)
- checkValid();
+ this.keyDeps = keyDeps;
+ this.rangeDeps = rangeDeps;
}
- public PartialDeps slice(Ranges ranges)
- {
- if (isEmpty())
- return new PartialDeps(ranges, keys, txnIds, keyToTxnId);
-
- Keys select = keys.slice(ranges);
-
- if (select.isEmpty())
- return new PartialDeps(ranges, Keys.EMPTY, NO_TXNIDS, NO_INTS);
-
- if (select.size() == keys.size())
- return new PartialDeps(ranges, keys, txnIds, keyToTxnId);
-
- int i = 0;
- int offset = select.size();
- for (int j = 0 ; j < select.size() ; ++j)
- {
- int findi = keys.findNext(i, select.get(j), FAST);
- if (findi < 0)
- continue;
-
- i = findi;
- offset += keyToTxnId[i] - (i == 0 ? keys.size() : keyToTxnId[i - 1]);
- }
-
- int[] src = keyToTxnId;
- int[] trg = new int[offset];
-
- i = 0;
- offset = select.size();
- for (int j = 0 ; j < select.size() ; ++j)
- {
- int findi = keys.findNext(i, select.get(j), FAST);
- if (findi >= 0)
- {
- i = findi;
- int start = i == 0 ? keys.size() : src[i - 1];
- int count = src[i] - start;
- System.arraycopy(src, start, trg, offset, count);
- offset += count;
- }
- trg[j] = offset;
- }
-
- TxnId[] txnIds = trimUnusedTxnId(select, this.txnIds, trg);
- return new PartialDeps(ranges, select, txnIds, trg);
- }
-
- /**
- * Returns the set of {@link TxnId}s that are referenced by {@code keysToTxnId}, and <strong>updates</strong>
- * {@code keysToTxnId} to point to the new offsets in the returned set.
- * @param keys object referenced by {@code keysToTxnId} index
- * @param txnIds to trim to the seen {@link TxnId}s
- * @param keysToTxnId to use as reference for trimming, this index will be updated to reflect the trimmed offsets.
- * @return smallest set of {@link TxnId} seen in {@code keysToTxnId}
- */
- private static TxnId[] trimUnusedTxnId(Keys keys, TxnId[] txnIds, int[] keysToTxnId)
+ public boolean contains(TxnId txnId)
{
- IntBuffers cache = ArrayBuffers.cachedInts();
- // we use remapTxnId twice:
- // - first we use the end to store a bitmap of those TxnId we are actually using
- // - then we use it to store the remap index (incrementally replacing the bitmap)
- int bitMapOffset = txnIds.length + 1 - (txnIds.length+31)/32;
- int[] remapTxnId = cache.getInts(txnIds.length + 1);
- try
- {
- Arrays.fill(remapTxnId, bitMapOffset, txnIds.length + 1, 0);
- for (int i = keys.size() ; i < keysToTxnId.length ; ++i)
- setBit(remapTxnId, bitMapOffset, keysToTxnId[i]);
-
- int offset = 0;
- for (int i = 0 ; i < txnIds.length ; ++i)
- {
- if (hasSetBit(remapTxnId, bitMapOffset, i)) remapTxnId[i] = offset++;
- else remapTxnId[i] = -1;
- }
-
- TxnId[] result = txnIds;
- if (offset < txnIds.length)
- {
- result = new TxnId[offset];
- for (int i = 0 ; i < txnIds.length ; ++i)
- {
- if (remapTxnId[i] >= 0)
- result[remapTxnId[i]] = txnIds[i];
- }
- // Update keysToTxnId to point to the new remapped TxnId offsets
- for (int i = keys.size() ; i < keysToTxnId.length ; ++i)
- keysToTxnId[i] = remapTxnId[keysToTxnId[i]];
- }
-
- return result;
- }
- finally
- {
- cache.forceDiscard(remapTxnId, txnIds.length);
- }
+ return keyDeps.contains(txnId) || rangeDeps.contains(txnId);
}
public Deps with(Deps that)
{
- if (isEmpty() || that.isEmpty())
- return isEmpty() ? that : this;
-
- return linearUnion(
- this.keys.keys, this.keys.keys.length, this.txnIds, this.txnIds.length, this.keyToTxnId, this.keyToTxnId.length,
- that.keys.keys, that.keys.keys.length, that.txnIds, that.txnIds.length, that.keyToTxnId, that.keyToTxnId.length,
- cachedKeys(), cachedTxnIds(), cachedInts(),
- (keys, keysLength, txnIds, txnIdsLength, out, outLength) ->
- new Deps(Keys.ofSortedUnchecked(cachedKeys().complete(keys, keysLength)),
- cachedTxnIds().complete(txnIds, txnIdsLength),
- cachedInts().complete(out, outLength))
- );
- }
-
- /**
- * Turn a set of key, value and mapping buffers into a merge result;
- * K and V are either Key and TxnId, or vice versa, depending on which mapping direction was present
- */
- interface DepsConstructor<K, V, T>
- {
- T construct(K[] keys, int keysLength, V[] values, int valuesLength, int[] out, int outLength);
- }
-
- private static boolean arraysEqual(int[] left, int[] right, int length)
- {
- if (left.length < length || right.length < length)
- return false;
-
- for (int i=0; i<length; i++)
- if (left[i] !=right[i])
- return false;
-
- return true;
- }
-
- private static <T> boolean arraysEqual(T[] left, T[] right, int length)
- {
- if (left.length < length || right.length < length)
- return false;
-
- for (int i=0; i<length; i++)
- if (!Objects.equals(left[i], right[i]))
- return false;
-
- return true;
- }
-
- // TODO (low priority, efficiency): this method supports merging keyToTxnId OR txnIdToKey; we can perhaps save time
- // and effort when constructing Deps on remote hosts by only producing txnIdToKey with OrderedCollector and serializing
- // only this, and merging on the recipient before inverting, so that we only have to invert the final assembled deps
- private static <K extends Comparable<? super K>, V extends Comparable<? super V>, T>
- T linearUnion(K[] leftKeys, int leftKeysLength, V[] leftValues, int leftValuesLength, int[] left, int leftLength,
- K[] rightKeys, int rightKeysLength, V[] rightValues, int rightValuesLength, int[] right, int rightLength,
- ObjectBuffers<K> keyBuffers, ObjectBuffers<V> valueBuffers, IntBuffers intBuffers, DepsConstructor<K, V, T> constructor)
- {
- K[] outKeys = null;
- V[] outValues = null;
- int[] remapLeft = null, remapRight = null, out = null;
- int outLength = 0, outKeysLength = 0, outTxnIdsLength = 0;
-
- try
- {
- outKeys = SortedArrays.linearUnion(leftKeys, leftKeysLength, rightKeys, rightKeysLength, keyBuffers);
- outKeysLength = keyBuffers.lengthOfLast(outKeys);
- outValues = SortedArrays.linearUnion(leftValues, leftValuesLength, rightValues, rightValuesLength, valueBuffers);
- outTxnIdsLength = valueBuffers.lengthOfLast(outValues);
-
- remapLeft = remapToSuperset(leftValues, leftValuesLength, outValues, outTxnIdsLength, intBuffers);
- remapRight = remapToSuperset(rightValues, rightValuesLength, outValues, outTxnIdsLength, intBuffers);
-
- if (remapLeft == null && remapRight == null && leftLength == rightLength && leftKeysLength == rightKeysLength
- && arraysEqual(left, right, rightLength)
- && arraysEqual(leftKeys, rightKeys, rightKeysLength)
- )
- {
- return constructor.construct(leftKeys, leftKeysLength, leftValues, leftValuesLength, left, leftLength);
- }
-
- int lk = 0, rk = 0, ok = 0, l = leftKeysLength, r = rightKeysLength;
- outLength = outKeysLength;
-
- if (remapLeft == null && outKeys == leftKeys)
- {
- // "this" knows all the TxnId and Keys already, but do both agree on what Keys map to TxnIds?
- noOp: while (lk < leftKeysLength && rk < rightKeysLength)
- {
- int ck = leftKeys[lk].compareTo(rightKeys[rk]);
- if (ck < 0)
- {
- // "this" knows of a key not present in "that"
- outLength += left[lk] - l; // logically append the key's TxnIds to the size
- l = left[lk];
- assert outLength == l && ok == lk && left[ok] == outLength;
- ok++;
- lk++;
- }
- else if (ck > 0)
- {
- // if this happened there is a bug with keys.union or keys are not actually sorted
- throwUnexpectedMissingKeyException(leftKeys, lk, leftKeysLength, rightKeys, rk, rightKeysLength, true);
- }
- else
- {
- // both "this" and "that" know of the key
- while (l < left[lk] && r < right[rk])
- {
- int nextLeft = left[l];
- int nextRight = remap(right[r], remapRight);
-
- if (nextLeft < nextRight)
- {
- // "this" knows of the txn that "that" didn't
- outLength++;
- l++;
- }
- else if (nextRight < nextLeft)
- {
- out = copy(left, outLength, leftLength + rightLength - r, intBuffers);
- break noOp;
- }
- else
- {
- outLength++;
- l++;
- r++;
- }
- }
-
- if (l < left[lk])
- {
- outLength += left[lk] - l;
- l = left[lk];
- }
- else if (r < right[rk])
- {
- // "that" thinks a key includes a TxnId as a dependency but "this" doesn't, need to include this knowledge
- out = copy(left, outLength, leftLength + rightLength - r, intBuffers);
- break;
- }
-
- assert outLength == l && ok == lk && left[ok] == outLength;
- ok++;
- rk++;
- lk++;
- }
- }
-
- if (out == null)
- return constructor.construct(leftKeys, leftKeysLength, leftValues, leftValuesLength, left, leftLength);
- }
- else if (remapRight == null && outKeys == rightKeys)
- {
- // "that" knows all the TxnId and keys already, but "this" does not
- noOp: while (lk < leftKeysLength && rk < rightKeysLength)
- {
- int ck = leftKeys[lk].compareTo(rightKeys[rk]);
- if (ck < 0)
- {
- // if this happened there is a bug with keys.union or keys are not actually sorted
- throwUnexpectedMissingKeyException(leftKeys, lk, leftKeysLength, rightKeys, rk, rightKeysLength, false);
- }
- else if (ck > 0)
- {
- outLength += right[rk] - r;
- r = right[rk];
- assert outLength == r && ok == rk && right[ok] == outLength;
- ok++;
- rk++;
- }
- else
- {
- // both "this" and "that" know of the key
- while (l < left[lk] && r < right[rk])
- {
- int nextLeft = remap(left[l], remapLeft);
- int nextRight = right[r];
-
- if (nextLeft < nextRight)
- {
- // "this" thinks a TxnID depends on Key but "that" doesn't, need to include this knowledge
- out = copy(right, outLength, rightLength + leftLength - l, intBuffers);
- break noOp;
- }
- else if (nextRight < nextLeft)
- {
- // "that" knows of the txn that "this" didn't
- outLength++;
- r++;
- }
- else
- {
- outLength++;
- l++;
- r++;
- }
- }
-
- if (l < left[lk])
- {
- out = copy(right, outLength, rightLength + leftLength - l, intBuffers);
- break;
- }
- else if (r < right[rk])
- {
- outLength += right[rk] - r;
- r = right[rk];
- }
-
- assert outLength == r && ok == rk && right[ok] == outLength;
- ok++;
- rk++;
- lk++;
- }
- }
-
- if (out == null)
- return constructor.construct(rightKeys, rightKeysLength, rightValues, rightValuesLength, right, rightLength);
- }
- else
- {
- out = intBuffers.getInts(leftLength + rightLength);
- }
-
- while (lk < leftKeysLength && rk < rightKeysLength)
- {
- int ck = leftKeys[lk].compareTo(rightKeys[rk]);
- if (ck < 0)
- {
- while (l < left[lk])
- out[outLength++] = remap(left[l++], remapLeft);
- out[ok++] = outLength;
- lk++;
- }
- else if (ck > 0)
- {
- while (r < right[rk])
- out[outLength++] = remap(right[r++], remapRight);
- out[ok++] = outLength;
- rk++;
- }
- else
- {
- while (l < left[lk] && r < right[rk])
- {
- int nextLeft = remap(left[l], remapLeft);
- int nextRight = remap(right[r], remapRight);
-
- if (nextLeft <= nextRight)
- {
- out[outLength++] = nextLeft;
- l += 1;
- r += nextLeft == nextRight ? 1 : 0;
- }
- else
- {
- out[outLength++] = nextRight;
- ++r;
- }
- }
-
- while (l < left[lk])
- out[outLength++] = remap(left[l++], remapLeft);
-
- while (r < right[rk])
- out[outLength++] = remap(right[r++], remapRight);
-
- out[ok++] = outLength;
- rk++;
- lk++;
- }
- }
-
- while (lk < leftKeysLength)
- {
- while (l < left[lk])
- out[outLength++] = remap(left[l++], remapLeft);
- out[ok++] = outLength;
- lk++;
- }
-
- while (rk < rightKeysLength)
- {
- while (r < right[rk])
- out[outLength++] = remap(right[r++], remapRight);
- out[ok++] = outLength;
- rk++;
- }
-
- return constructor.construct(outKeys, outKeysLength, outValues, outTxnIdsLength, out, outLength);
- }
- finally
- {
- if (outKeys != null)
- keyBuffers.discard(outKeys, outKeysLength);
- if (outValues != null)
- valueBuffers.discard(outValues, outTxnIdsLength);
- if (out != null)
- intBuffers.discard(out, outLength);
- if (remapLeft != null)
- intBuffers.forceDiscard(remapLeft, leftValuesLength);
- if (remapRight != null)
- intBuffers.forceDiscard(remapRight, rightValuesLength);
- }
- }
-
- private static <A> void throwUnexpectedMissingKeyException(A[] leftKeys, int leftKeyIndex, int leftKeyLength, A[] rightKeys, int rightKeyIndex, int rightKeyLength, boolean isMissingLeft)
- {
- StringBuilder sb = new StringBuilder();
- String missing = isMissingLeft ? "left" : "right";
- String extra = isMissingLeft ? "right" : "left";
- sb.append(missing).append(" knows all keys, yet ").append(extra).append(" knew of an extra key at indexes left[")
- .append(leftKeyIndex).append("] = ").append(leftKeys[leftKeyIndex])
- .append(", right[").append(rightKeyIndex).append("] = ").append(rightKeys[rightKeyIndex]).append("\n");
- sb.append("leftKeys = ").append(Arrays.stream(leftKeys, 0, leftKeyLength).map(Object::toString).collect(Collectors.joining())).append('\n');
- sb.append("rightKeys = ").append(Arrays.stream(rightKeys, 0, rightKeyLength).map(Object::toString).collect(Collectors.joining())).append('\n');
- throw new IllegalStateException(sb.toString());
- }
-
- private static int[] copy(int[] src, int to, int length, IntBuffers bufferManager)
- {
- if (length == 0)
- return NO_INTS;
-
- int[] result = bufferManager.getInts(length);
- if (result.length < length)
- throw new IllegalStateException();
- System.arraycopy(src, 0, result, 0, to);
- return result;
+ return new Deps(this.keyDeps.with(that.keyDeps), this.rangeDeps.with(that.rangeDeps));
}
public Deps without(Predicate<TxnId> remove)
{
- if (isEmpty())
- return this;
-
- IntBuffers cache = ArrayBuffers.cachedInts();
- TxnId[] oldTxnIds = txnIds;
- int[] oldKeyToTxnId = keyToTxnId;
- int[] remapTxnIds = cache.getInts(oldTxnIds.length);
- int[] newKeyToTxnId = null;
- TxnId[] newTxnIds;
- int o = 0;
- try
- {
- int count = 0;
- for (int i = 0 ; i < oldTxnIds.length ; ++i)
- {
- if (remove.test(oldTxnIds[i])) remapTxnIds[i] = -1;
- else remapTxnIds[i] = count++;
- }
-
- if (count == oldTxnIds.length)
- return this;
-
- if (count == 0)
- return NONE;
-
- newTxnIds = new TxnId[count];
- for (int i = 0 ; i < oldTxnIds.length ; ++i)
- {
- if (remapTxnIds[i] >= 0)
- newTxnIds[remapTxnIds[i]] = oldTxnIds[i];
- }
-
- newKeyToTxnId = cache.getInts(oldKeyToTxnId.length);
- int k = 0, i = keys.size();
- o = i;
- while (i < oldKeyToTxnId.length)
- {
- while (oldKeyToTxnId[k] == i)
- newKeyToTxnId[k++] = o;
-
- int remapped = remapTxnIds[oldKeyToTxnId[i]];
- if (remapped >= 0)
- newKeyToTxnId[o++] = remapped;
- ++i;
- }
-
- while (k < keys.size())
- newKeyToTxnId[k++] = o;
- }
- catch (Throwable t)
- {
- cache.forceDiscard(newKeyToTxnId, o);
- throw t;
- }
- finally
- {
- cache.forceDiscard(remapTxnIds, oldTxnIds.length);
- }
-
- newKeyToTxnId = cache.completeAndDiscard(newKeyToTxnId, o);
- return new Deps(keys, newTxnIds, newKeyToTxnId);
+ return new Deps(keyDeps.without(remove), rangeDeps.without(remove));
}
- public boolean contains(TxnId txnId)
+ public PartialDeps slice(Ranges covering)
{
- return Arrays.binarySearch(txnIds, txnId) >= 0;
+ return new PartialDeps(covering, keyDeps.slice(covering), rangeDeps.slice(covering));
}
- // return true iff we map any keys to any txnId
- // if the mapping is empty we return false, whether or not we have any keys or txnId by themselves
public boolean isEmpty()
{
- return keyToTxnId.length == keys.size();
- }
-
- public Keys someKeys(TxnId txnId)
- {
- int txnIdIndex = Arrays.binarySearch(txnIds, txnId);
- if (txnIdIndex < 0)
- return Keys.EMPTY;
-
- ensureTxnIdToKey();
-
- int start = txnIdIndex == 0 ? txnIds.length : txnIdToKey[txnIdIndex - 1];
- int end = txnIdToKey[txnIdIndex];
- if (start == end)
- return Keys.EMPTY;
-
- Key[] result = new Key[end - start];
- for (int i = start ; i < end ; ++i)
- result[i - start] = keys.get(txnIdToKey[i]);
- return Keys.of(result);
- }
-
- public Unseekables<RoutingKey, ?> someRoutables(TxnId txnId)
- {
- return toUnseekables(txnId, array -> {
- if (array.length == 0)
- throw new IllegalStateException("Cannot create a RouteFragment without any keys");
- return new RoutingKeys(array);
- });
- }
-
- private <R> R toUnseekables(TxnId txnId, Function<RoutingKey[], R> constructor)
- {
- int txnIdIndex = Arrays.binarySearch(txnIds, txnId);
- if (txnIdIndex < 0)
- constructor.apply(RoutingKeys.EMPTY.keys);
-
- ensureTxnIdToKey();
-
- int start = txnIdIndex == 0 ? txnIds.length : txnIdToKey[txnIdIndex - 1];
- int end = txnIdToKey[txnIdIndex];
- RoutingKey[] result = new RoutingKey[end - start];
- if (start == end)
- constructor.apply(RoutingKeys.EMPTY.keys);
-
- result[0] = keys.get(txnIdToKey[start]).toUnseekable();
- int resultCount = 1;
- for (int i = start + 1 ; i < end ; ++i)
- {
- RoutingKey next = keys.get(txnIdToKey[i]).toUnseekable();
- if (!next.equals(result[resultCount - 1]))
- result[resultCount++] = next;
- }
-
- if (resultCount < result.length)
- result = Arrays.copyOf(result, resultCount);
- return constructor.apply(result);
- }
-
- void ensureTxnIdToKey()
- {
- if (txnIdToKey != null)
- return;
-
- txnIdToKey = invert(keyToTxnId, keyToTxnId.length, keys.size(), txnIds.length);
- }
-
- private static int[] invert(int[] src, int srcLength, int srcKeyCount, int trgKeyCount)
- {
- int[] trg = new int[trgKeyCount + srcLength - srcKeyCount];
-
- // first pass, count number of txnId per key
- for (int i = srcKeyCount ; i < srcLength ; ++i)
- trg[src[i]]++;
-
- // turn into offsets (i.e. add txnIds.size() and then sum them)
- trg[0] += trgKeyCount;
- for (int i = 1; i < trgKeyCount ; ++i)
- trg[i] += trg[i - 1];
-
- // shuffle forwards one, so we have the start index rather than end
- System.arraycopy(trg, 0, trg, 1, trgKeyCount - 1);
- trg[0] = trgKeyCount;
-
- // convert the offsets to end, and set the key at the target positions
- int k = 0;
- for (int i = srcKeyCount ; i < srcLength ; ++i)
- {
- // if at the end offset, switch to the next key
- while (i == src[k])
- ++k;
-
- // find the next key offset for the TxnId and set the offset to this key
- trg[trg[src[i]]++] = k;
- }
-
- return trg;
- }
-
- public void forEachOn(Ranges ranges, Predicate<Key> include, BiConsumer<Key, TxnId> forEach)
- {
- Routables.foldl(keys, ranges, (key, value, index) -> {
- if (!include.test(key))
- return null;
-
- for (int t = startOffset(index), end = endOffset(index); t < end ; ++t)
- {
- TxnId txnId = txnIds[keyToTxnId[t]];
- forEach.accept(key, txnId);
- }
- return null;
- }, null);
- }
-
- /**
- * For each {@link TxnId} that references a key within the {@link Ranges}; the {@link TxnId} will be seen exactly once.
- * @param ranges to match on
- * @param forEach function to call on each unique {@link TxnId}
- */
- public void forEachOn(Ranges ranges, Consumer<TxnId> forEach)
- {
- // Find all keys within the ranges, but record existence within an int64 bitset. Since the bitset is limited
- // to 64, this search must be called multiple times searching for different TxnIds in txnIds; this also has
- // the property that forEach is called in TxnId order.
- //TODO (expected, efficiency): reconsider this, probably not worth trying to save allocations at cost of multiple loop
- // use BitSet, or perhaps extend so we can have no nested allocations when few bits
- for (int offset = 0 ; offset < txnIds.length ; offset += 64)
- {
- long bitset = Routables.foldl(keys, ranges, (key, off, value, keyIndex) -> {
- int index = startOffset(keyIndex);
- int end = endOffset(keyIndex);
- if (off > 0)
- {
- // TODO (low priority, efficiency): interpolation search probably great here
- index = Arrays.binarySearch(keyToTxnId, index, end, (int)off);
- if (index < 0)
- index = -1 - index;
- }
-
- while (index < end)
- {
- long next = keyToTxnId[index++] - off;
- if (next >= 64)
- break;
- value |= 1L << next;
- }
-
- return value;
- }, offset, 0, -1L);
-
- while (bitset != 0)
- {
- int i = Long.numberOfTrailingZeros(bitset);
- TxnId txnId = txnIds[offset + i];
- forEach.accept(txnId);
- bitset ^= Long.lowestOneBit(bitset);
- }
- }
- }
-
- public void forEach(Key key, Consumer<TxnId> forEach)
- {
- int keyIndex = keys.indexOf(key);
- if (keyIndex < 0)
- return;
-
- int index = startOffset(keyIndex);
- int end = endOffset(keyIndex);
- while (index < end)
- forEach.accept(txnIds[keyToTxnId[index++]]);
- }
-
- public Keys keys()
- {
- return keys;
+ return keyDeps.isEmpty() && rangeDeps.isEmpty();
}
public int txnIdCount()
{
- return txnIds.length;
- }
-
- public int totalCount()
- {
- return keyToTxnId.length - keys.size();
+ return keyDeps.txnIdCount() + rangeDeps.txnIdCount();
}
public TxnId txnId(int i)
{
- return txnIds[i];
+ return i < keyDeps.txnIdCount()
+ ? keyDeps.txnId(i)
+ : rangeDeps.txnId(i - keyDeps.txnIdCount());
}
- public Collection<TxnId> txnIds()
+ public List<TxnId> txnIds()
{
- return Arrays.asList(txnIds);
- }
-
- public List<TxnId> txnIds(Key key)
- {
- int keyIndex = keys.indexOf(key);
- if (keyIndex < 0)
- return Collections.emptyList();
-
- int start = startOffset(keyIndex);
- int end = endOffset(keyIndex);
- int size = end - start;
-
- return new AbstractList<TxnId>()
- {
+ final int txnIdCount = txnIdCount();
+ final int keyDepsCount = keyDeps.txnIdCount();
+ return new AbstractList<TxnId>() {
@Override
public TxnId get(int index)
{
- if (index > end)
- throw new IndexOutOfBoundsException();
- return txnIds[keyToTxnId[start + index]];
+ return index < keyDepsCount
+ ? keyDeps.txnId(index)
+ : rangeDeps.txnId(index - keyDepsCount);
}
@Override
public int size()
{
- return size;
+ return txnIdCount;
}
};
}
- private int startOffset(int keyIndex)
- {
- return keyIndex == 0 ? keys.size() : keyToTxnId[keyIndex - 1];
- }
-
- private int endOffset(int keyIndex)
+ public List<TxnId> txnIds(Seekable keyOrRange)
{
- return keyToTxnId[keyIndex];
- }
-
- @Override
- public Iterator<Map.Entry<Key, TxnId>> iterator()
- {
- return new Iterator<Map.Entry<Key, TxnId>>()
+ List<TxnId> keyIds, rangeIds;
+ switch (keyOrRange.domain())
{
- int i = keys.size(), k = 0;
-
- @Override
- public boolean hasNext()
+ default: throw new AssertionError();
+ case Key:
{
- return i < keyToTxnId.length;
+ Key key = keyOrRange.asKey();
+ keyIds = keyDeps.txnIds(key);
+ rangeIds = rangeDeps.txnIds(key);
+ break;
}
-
- @Override
- public Map.Entry<Key, TxnId> next()
+ case Range:
{
- Entry result = new Entry(keys.get(k), txnIds[keyToTxnId[i++]]);
- if (i == keyToTxnId[k])
- ++k;
- return result;
+ Range range = keyOrRange.asRange();
+ keyIds = keyDeps.txnIds(range);
+ rangeIds = rangeDeps.txnIds(range);
}
- };
- }
-
- @Override
- public String toString()
- {
- return toSimpleString();
- }
+ }
- public String toSimpleString()
- {
- if (keys.isEmpty())
- return "{}";
+ if (rangeIds.isEmpty()) return keyIds;
+ if (keyIds.isEmpty()) return rangeIds;
- StringBuilder builder = new StringBuilder("{");
- for (int k = 0, t = keys.size(); k < keys.size() ; ++k)
+ List<TxnId> output = new ArrayList<>(keyIds.size() + rangeIds.size());
+ int ki = 0, ri = 0;
+ while (ki < keyIds.size() && ri < rangeIds.size())
{
- if (builder.length() > 1)
- builder.append(", ");
-
- builder.append(keys.get(k));
- builder.append(":[");
- boolean first = true;
- while (t < keyToTxnId[k])
- {
- if (first) first = false;
- else builder.append(", ");
- builder.append(txnIds[keyToTxnId[t++]]);
- }
- builder.append("]");
+ int c = keyIds.get(ki).compareTo(rangeIds.get(ri));
+ Invariants.checkState(c != 0);
+ if (c < 0) output.add(keyIds.get(ki++));
+ else output.add(rangeIds.get(ri++));
}
- builder.append("}");
- return builder.toString();
+ while (ki < keyIds.size())
+ output.add(keyIds.get(ki++));
+ while (ri < rangeIds.size())
+ output.add(rangeIds.get(ri++));
+ return output;
}
- @Override
- public boolean equals(Object o)
+ public Unseekables<?, ?> someUnseekables(TxnId txnId)
{
- if (this == o) return true;
- if (o == null || getClass() != o.getClass()) return false;
- return equals((Deps) o);
+ if (keyDeps.contains(txnId))
+ return keyDeps.someUnseekables(txnId);
+ else
+ return rangeDeps.someUnseekables(txnId);
}
- public boolean equals(Deps that)
+ // NOTE: filter only applied to keyDeps
+ public void forEach(Ranges ranges, Consumer<TxnId> forEach)
{
- return this.txnIds.length == that.txnIds.length
- && this.keys.size() == that.keys.size()
- && Arrays.equals(this.keyToTxnId, that.keyToTxnId)
- && Arrays.equals(this.txnIds, that.txnIds)
- && this.keys.equals(that.keys);
+ keyDeps.forEachUniqueTxnId(ranges, forEach);
+ rangeDeps.forEachUniqueTxnId(ranges, forEach);
}
- public static class Entry implements Map.Entry<Key, TxnId>
+ public static <T> Deps merge(List<T> list, Function<T, Deps> getter)
{
- final Key key;
- final TxnId txnId;
-
- public Entry(Key key, TxnId txnId)
- {
- this.key = key;
- this.txnId = txnId;
- }
-
- @Override
- public Key getKey()
- {
- return key;
- }
-
- @Override
- public TxnId getValue()
- {
- return txnId;
- }
-
- @Override
- public TxnId setValue(TxnId value)
- {
- throw new UnsupportedOperationException();
- }
-
- @Override
- public String toString()
- {
- return key + "->" + txnId;
- }
+ return new Deps(KeyDeps.merge(list, getter, deps -> deps.keyDeps),
+ RangeDeps.merge(list, getter, deps -> deps.rangeDeps));
}
- private void checkValid()
+ @Override
+ public String toString()
{
- int k = 0;
- for (int i = keys.size() ; i < keyToTxnId.length ; ++i)
- {
- boolean first = true;
- while (i < keyToTxnId[k])
- {
- if (first) first = false;
- else if (keyToTxnId[i - 1] == keyToTxnId[i])
- {
- Key key = keys.get(i);
- TxnId txnId = txnIds[keyToTxnId[i]];
- throw new IllegalStateException(String.format("Duplicate TxnId (%s) found for key %s", txnId, key));
- }
- i++;
- }
- ++k;
- }
+ return keyDeps.toString() + ", " + rangeDeps.toString();
}
- private static void setBit(int[] array, int offset, int index)
+ @Override
+ public boolean equals(Object that)
{
- array[offset + index / 32] |= (1 << (index & 31));
+ return this == that || (that instanceof Deps && equals((Deps)that));
}
- private static boolean hasSetBit(int[] array, int offset, int index)
+ public boolean equals(Deps that)
{
- return (array[offset + index / 32] & (1 << (index & 31))) != 0;
+ return this.keyDeps.equals(that.keyDeps) && this.rangeDeps.equals(that.rangeDeps);
}
-
}
diff --git a/accord-core/src/main/java/accord/primitives/FullKeyRoute.java b/accord-core/src/main/java/accord/primitives/FullKeyRoute.java
index 469ed59..0806df5 100644
--- a/accord-core/src/main/java/accord/primitives/FullKeyRoute.java
+++ b/accord-core/src/main/java/accord/primitives/FullKeyRoute.java
@@ -49,6 +49,7 @@ public class FullKeyRoute extends KeyRoute implements FullRoute<RoutingKey>
return slice(ranges);
}
+ @Override
public FullKeyRoute toMaximalUnseekables()
{
return this;
diff --git a/accord-core/src/main/java/accord/primitives/FullRangeRoute.java b/accord-core/src/main/java/accord/primitives/FullRangeRoute.java
index 7e39fd7..848311d 100644
--- a/accord-core/src/main/java/accord/primitives/FullRangeRoute.java
+++ b/accord-core/src/main/java/accord/primitives/FullRangeRoute.java
@@ -56,6 +56,7 @@ public class FullRangeRoute extends RangeRoute implements FullRoute<Range>
return slice(ranges);
}
+ @Override
public FullRangeRoute toMaximalUnseekables()
{
return this;
diff --git a/accord-core/src/main/java/accord/primitives/KeyDeps.java b/accord-core/src/main/java/accord/primitives/KeyDeps.java
new file mode 100644
index 0000000..1ac6b65
--- /dev/null
+++ b/accord-core/src/main/java/accord/primitives/KeyDeps.java
@@ -0,0 +1,537 @@
+/*
+ * 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 accord.primitives;
+
+import accord.api.Key;
+import accord.api.RoutingKey;
+import accord.utils.ArrayBuffers;
+import accord.utils.SymmetricComparator;
+
+import java.util.*;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+import java.util.function.Function;
+import java.util.function.Predicate;
+
+import static accord.utils.ArrayBuffers.*;
+import static accord.utils.RelationMultiMap.*;
+import static accord.utils.SortedArrays.Search.FAST;
+
+/**
+ * A collection of dependencies for a transaction, organised by the key the dependency is adopted via.
+ * An inverse map from TxnId to Key may also be constructed and stored in this collection.
+ */
+// TODO (desired, consider): switch to RoutingKey? Would mean adopting execution dependencies less precisely, but saving ser/deser of large keys
+public class KeyDeps implements Iterable<Map.Entry<Key, TxnId>>
+{
+ public static final KeyDeps NONE = new KeyDeps(Keys.EMPTY, NO_TXNIDS, NO_INTS);
+
+ public static class SerializerSupport
+ {
+ private SerializerSupport() {}
+
+ public static int keysToTxnIdsCount(KeyDeps deps)
+ {
+ return deps.keysToTxnIds.length;
+ }
+
+ public static int keysToTxnIds(KeyDeps deps, int idx)
+ {
+ return deps.keysToTxnIds[idx];
+ }
+
+ public static KeyDeps create(Keys keys, TxnId[] txnIds, int[] keyToTxnId)
+ {
+ return new KeyDeps(keys, txnIds, keyToTxnId);
+ }
+ }
+
+ public static KeyDeps none(Keys keys)
+ {
+ int[] keysToTxnId = new int[keys.size()];
+ Arrays.fill(keysToTxnId, keys.size());
+ return new KeyDeps(keys, NO_TXNIDS, keysToTxnId);
+ }
+
+ /**
+ * Expects Command to be provided in TxnId order
+ */
+ public static Builder builder()
+ {
+ return new Builder();
+ }
+
+ public static class Builder extends AbstractBuilder<Key, TxnId, KeyDeps>
+ {
+ public Builder()
+ {
+ super(ADAPTER);
+ }
+
+ @Override
+ protected KeyDeps none()
+ {
+ return KeyDeps.NONE;
+ }
+
+ @Override
+ protected KeyDeps build(Key[] keys, TxnId[] txnIds, int[] keysToTxnIds)
+ {
+ return new KeyDeps(Keys.ofSorted(keys), txnIds, keysToTxnIds);
+ }
+ }
+
+ public static <T1, T2> KeyDeps merge(List<T1> merge, Function<T1, T2> getter1, Function<T2, KeyDeps> getter2)
+ {
+ try (LinearMerger<Key, TxnId, KeyDeps> linearMerger = new LinearMerger<>(ADAPTER))
+ {
+ int mergeIndex = 0, mergeSize = merge.size();
+ while (mergeIndex < mergeSize)
+ {
+ T2 intermediate = getter1.apply(merge.get(mergeIndex++));
+ if (intermediate == null)
+ continue;
+
+ KeyDeps deps = getter2.apply(intermediate);
+ if (deps == null || deps.isEmpty())
+ continue;
+
+ linearMerger.update(deps, deps.keys.keys, deps.txnIds, deps.keysToTxnIds);
+ }
+
+ return linearMerger.get(KeyDeps::new, NONE);
+ }
+ }
+
+ final Keys keys; // unique Keys
+ final TxnId[] txnIds; // unique TxnId
+
+ /**
+ * This represents a map of {@code Key -> [TxnId] } where each TxnId is actually a pointer into the txnIds array.
+ * The beginning of the array (the first keys.size() entries) are offsets into this array.
+ * <p/>
+ * Example:
+ * <p/>
+ * {@code
+ * int keyIdx = keys.indexOf(key);
+ * int startOfTxnOffset = keyIdx == 0 ? keys.size() : keyToTxnId[keyIdx - 1];
+ * int endOfTxnOffset = keyToTxnId[keyIdx];
+ * for (int i = startOfTxnOffset; i < endOfTxnOffset; i++)
+ * {
+ * TxnId id = txnIds[keyToTxnId[i]]
+ * ...
+ * }
+ * }
+ */
+ final int[] keysToTxnIds; // Key -> [TxnId]
+ // Lazy loaded in ensureTxnIdToKey()
+ int[] txnIdsToKeys; // TxnId -> [Key] TODO (low priority, efficiency): this could be a BTree?
+
+ KeyDeps(Key[] keys, TxnId[] txnIds, int[] keysToTxnIds)
+ {
+ this(Keys.ofSorted(keys), txnIds, keysToTxnIds);
+ }
+
+ KeyDeps(Keys keys, TxnId[] txnIds, int[] keysToTxnIds)
+ {
+ this.keys = keys;
+ this.txnIds = txnIds;
+ this.keysToTxnIds = keysToTxnIds;
+ if (!(keys.isEmpty() || keysToTxnIds[keys.size() - 1] == keysToTxnIds.length))
+ throw new IllegalArgumentException(String.format("Last key (%s) in keyToTxnId does not point (%d) to the end of the array (%d);\nkeyToTxnId=%s", keys.get(keys.size() - 1), keysToTxnIds[keys.size() - 1], keysToTxnIds.length, Arrays.toString(keysToTxnIds)));
+ checkValid(keys.keys, txnIds, keysToTxnIds);
+ }
+
+ public KeyDeps slice(Ranges ranges)
+ {
+ if (isEmpty())
+ return new KeyDeps(keys, txnIds, keysToTxnIds);
+
+ // TODO (low priority, efficiency): can slice in parallel with selecting keyToTxnId contents to avoid duplicate merging
+ Keys select = keys.slice(ranges);
+
+ if (select.isEmpty())
+ return new KeyDeps(Keys.EMPTY, NO_TXNIDS, NO_INTS);
+
+ if (select.size() == keys.size())
+ return new KeyDeps(keys, txnIds, keysToTxnIds);
+
+ int i = 0;
+ int offset = select.size();
+ for (int j = 0 ; j < select.size() ; ++j)
+ {
+ int findi = keys.findNext(i, select.get(j), FAST);
+ if (findi < 0)
+ continue;
+
+ i = findi;
+ offset += keysToTxnIds[i] - (i == 0 ? keys.size() : keysToTxnIds[i - 1]);
+ }
+
+ int[] src = keysToTxnIds;
+ int[] trg = new int[offset];
+
+ i = 0;
+ offset = select.size();
+ for (int j = 0 ; j < select.size() ; ++j)
+ {
+ int findi = keys.findNext(i, select.get(j), FAST);
+ if (findi >= 0)
+ {
+ i = findi;
+ int start = i == 0 ? keys.size() : src[i - 1];
+ int count = src[i] - start;
+ System.arraycopy(src, start, trg, offset, count);
+ offset += count;
+ }
+ trg[j] = offset;
+ }
+
+ TxnId[] txnIds = trimUnusedValues(select.keys, this.txnIds, trg, TxnId[]::new);
+ return new KeyDeps(select, txnIds, trg);
+ }
+
+ public KeyDeps with(KeyDeps that)
+ {
+ if (isEmpty() || that.isEmpty())
+ return isEmpty() ? that : this;
+
+ return linearUnion(
+ this.keys.keys, this.keys.keys.length, this.txnIds, this.txnIds.length, this.keysToTxnIds, this.keysToTxnIds.length,
+ that.keys.keys, that.keys.keys.length, that.txnIds, that.txnIds.length, that.keysToTxnIds, that.keysToTxnIds.length,
+ Key::compareTo, TxnId::compareTo,
+ cachedKeys(), cachedTxnIds(), cachedInts(),
+ (keys, keysLength, txnIds, txnIdsLength, out, outLength) ->
+ new KeyDeps(Keys.ofSortedUnchecked(cachedKeys().complete(keys, keysLength)),
+ cachedTxnIds().complete(txnIds, txnIdsLength),
+ cachedInts().complete(out, outLength))
+ );
+ }
+
+ public KeyDeps without(Predicate<TxnId> remove)
+ {
+ return remove(this, keys.keys, txnIds, keysToTxnIds, remove,
+ NONE, TxnId[]::new, keys, KeyDeps::new);
+ }
+
+ public boolean contains(TxnId txnId)
+ {
+ return Arrays.binarySearch(txnIds, txnId) >= 0;
+ }
+
+ // return true iff we map any keys to any txnId
+ // if the mapping is empty we return false, whether or not we have any keys or txnId by themselves
+ public boolean isEmpty()
+ {
+ return keysToTxnIds.length == keys.size();
+ }
+
+ public Keys someKeys(TxnId txnId)
+ {
+ int txnIdIndex = Arrays.binarySearch(txnIds, txnId);
+ if (txnIdIndex < 0)
+ return Keys.EMPTY;
+
+ ensureTxnIdToKey();
+
+ int start = txnIdIndex == 0 ? txnIds.length : txnIdsToKeys[txnIdIndex - 1];
+ int end = txnIdsToKeys[txnIdIndex];
+ if (start == end)
+ return Keys.EMPTY;
+
+ Key[] result = new Key[end - start];
+ for (int i = start ; i < end ; ++i)
+ result[i - start] = keys.get(txnIdsToKeys[i]);
+ return Keys.of(result);
+ }
+
+ public Unseekables<RoutingKey, ?> someUnseekables(TxnId txnId)
+ {
+ int txnIdIndex = Arrays.binarySearch(txnIds, txnId);
+ if (txnIdIndex < 0)
+ throw new IllegalStateException("Cannot create a RouteFragment without any keys");
+
+ ensureTxnIdToKey();
+
+ int start = txnIdIndex == 0 ? txnIds.length : txnIdsToKeys[txnIdIndex - 1];
+ int end = txnIdsToKeys[txnIdIndex];
+ if (start == end)
+ throw new IllegalStateException("Cannot create a RouteFragment without any keys");
+
+ RoutingKey[] result = new RoutingKey[end - start];
+ result[0] = keys.get(txnIdsToKeys[start]).toUnseekable();
+ int resultCount = 1;
+ for (int i = start + 1 ; i < end ; ++i)
+ {
+ RoutingKey next = keys.get(txnIdsToKeys[i]).toUnseekable();
+ if (!next.equals(result[resultCount - 1]))
+ result[resultCount++] = next;
+ }
+
+ if (resultCount < result.length)
+ result = Arrays.copyOf(result, resultCount);
+ return new RoutingKeys(result);
+ }
+
+ void ensureTxnIdToKey()
+ {
+ if (txnIdsToKeys != null)
+ return;
+
+ txnIdsToKeys = invert(keysToTxnIds, keysToTxnIds.length, keys.size(), txnIds.length);
+ }
+
+ public void forEach(Ranges ranges, BiConsumer<Key, TxnId> forEach)
+ {
+ Routables.foldl(keys, ranges, (key, value, index) -> {
+ for (int t = startOffset(index), end = endOffset(index); t < end ; ++t)
+ {
+ TxnId txnId = txnIds[keysToTxnIds[t]];
+ forEach.accept(key, txnId);
+ }
+ return null;
+ }, null);
+ }
+
+ /**
+ * For each {@link TxnId} that references a key within the {@link Ranges}; the {@link TxnId} will be seen exactly once.
+ * @param ranges to match on
+ * @param forEach function to call on each unique {@link TxnId}
+ */
+ public void forEachUniqueTxnId(Ranges ranges, Consumer<TxnId> forEach)
+ {
+ // Find all keys within the ranges, but record existence within an int64 bitset. Since the bitset is limited
+ // to 64, this search must be called multiple times searching for different TxnIds in txnIds; this also has
+ // the property that forEach is called in TxnId order.
+ //TODO (expected, efficiency): reconsider this, probably not worth trying to save allocations at cost of multiple loop
+ // use BitSet, or perhaps extend so we can have no nested allocations when few bits
+ for (int offset = 0 ; offset < txnIds.length ; offset += 64)
+ {
+ long bitset = Routables.foldl(keys, ranges, (key, off, value, keyIndex) -> {
+ int index = startOffset(keyIndex);
+ int end = endOffset(keyIndex);
+ if (off > 0)
+ {
+ // TODO (low priority, efficiency): interpolation search probably great here
+ index = Arrays.binarySearch(keysToTxnIds, index, end, (int)off);
+ if (index < 0)
+ index = -1 - index;
+ }
+
+ while (index < end)
+ {
+ long next = keysToTxnIds[index++] - off;
+ if (next >= 64)
+ break;
+ value |= 1L << next;
+ }
+
+ return value;
+ }, offset, 0, -1L);
+
+ while (bitset != 0)
+ {
+ int i = Long.numberOfTrailingZeros(bitset);
+ TxnId txnId = txnIds[offset + i];
+ forEach.accept(txnId);
+ bitset ^= Long.lowestOneBit(bitset);
+ }
+ }
+ }
+
+ public void forEach(Key key, Consumer<TxnId> forEach)
+ {
+ int keyIndex = keys.indexOf(key);
+ if (keyIndex < 0)
+ return;
+
+ int index = startOffset(keyIndex);
+ int end = endOffset(keyIndex);
+ while (index < end)
+ forEach.accept(txnIds[keysToTxnIds[index++]]);
+ }
+
+ public Keys keys()
+ {
+ return keys;
+ }
+
+ public int txnIdCount()
+ {
+ return txnIds.length;
+ }
+
+ public int totalCount()
+ {
+ return keysToTxnIds.length - keys.size();
+ }
+
+ public TxnId txnId(int i)
+ {
+ return txnIds[i];
+ }
+
+ public Collection<TxnId> txnIds()
+ {
+ return Arrays.asList(txnIds);
+ }
+
+ public List<TxnId> txnIds(Key key)
+ {
+ int keyIndex = keys.indexOf(key);
+ if (keyIndex < 0)
+ return Collections.emptyList();
+
+ int start = startOffset(keyIndex);
+ int end = endOffset(keyIndex);
+ int size = end - start;
+ return txnIds(keysToTxnIds, start, size);
+ }
+
+ public List<TxnId> txnIds(Range range)
+ {
+ int startIndex = keys.indexOf(range.start());
+ if (startIndex < 0) startIndex = -1 - startIndex;
+ else if (!range.startInclusive()) ++startIndex;
+
+ int endIndex = keys.indexOf(range.end());
+ if (endIndex < 0) endIndex = -1 - endIndex;
+ else if (range.endInclusive()) ++endIndex;
+
+ if (startIndex == endIndex)
+ return Collections.emptyList();
+
+ int maxLength = Math.min(txnIds.length, startOffset(endIndex) - startOffset(startIndex));
+ int[] scratch = cachedInts().getInts(maxLength);
+ int count = 0;
+ for (int i = startIndex ; i < endIndex ; ++i)
+ {
+ int ri = startOffset(i), re = endOffset(i);
+ if (ri == re)
+ continue;
+
+ System.arraycopy(scratch, 0, scratch, maxLength - count, count);
+ int li = maxLength - count, le = maxLength;
+ count = 0;
+ while (li < le && ri < re)
+ {
+ int c = scratch[li] - keysToTxnIds[ri];
+ if (c <= 0)
+ {
+ scratch[count++] = scratch[li++];
+ if (c == 0) ++ri;
+ }
+ else
+ {
+ scratch[count++] = keysToTxnIds[ri++];
+ }
+ }
+ while (li < le)
+ scratch[count++] = scratch[li++];
+ while (ri < re)
+ scratch[count++] = keysToTxnIds[ri++];
+
+ if (count == maxLength)
+ break;
+ }
+
+ int[] ids = cachedInts().completeAndDiscard(scratch, count);
+ return txnIds(ids, 0, count);
+ }
+
+ private List<TxnId> txnIds(int[] ids, int start, int size)
+ {
+ return new AbstractList<TxnId>()
+ {
+ @Override
+ public TxnId get(int index)
+ {
+ if (index > size)
+ throw new IndexOutOfBoundsException();
+ return txnIds[ids[start + index]];
+ }
+
+ @Override
+ public int size()
+ {
+ return size;
+ }
+ };
+ }
+
+ private int startOffset(int keyIndex)
+ {
+ return keyIndex == 0 ? keys.size() : keysToTxnIds[keyIndex - 1];
+ }
+
+ private int endOffset(int keyIndex)
+ {
+ return keysToTxnIds[keyIndex];
+ }
+
+ public boolean equals(Object that)
+ {
+ return this == that || (that instanceof KeyDeps && equals((KeyDeps)that));
+ }
+
+ public boolean equals(KeyDeps that)
+ {
+ return testEquality(this.keys.keys, this.txnIds, this.keysToTxnIds, that.keys.keys, that.txnIds, that.keysToTxnIds);
+ }
+
+ @Override
+ public Iterator<Map.Entry<Key, TxnId>> iterator()
+ {
+ return newIterator(keys.keys, txnIds, keysToTxnIds);
+ }
+
+ @Override
+ public String toString()
+ {
+ return toSimpleString(keys.keys, txnIds, keysToTxnIds);
+ }
+
+ private static final KeyDepsAdapter ADAPTER = new KeyDepsAdapter();
+ static class KeyDepsAdapter implements Adapter<Key, TxnId>
+ {
+ @Override
+ public final SymmetricComparator<? super Key> keyComparator()
+ {
+ return Key::compareTo;
+ }
+
+ @Override
+ public final SymmetricComparator<? super TxnId> valueComparator()
+ {
+ return TxnId::compareTo;
+ }
+
+ @Override
+ public final ObjectBuffers<Key> cachedKeys()
+ {
+ return ArrayBuffers.cachedKeys();
+ }
+
+ @Override
+ public final ObjectBuffers<TxnId> cachedValues()
+ {
+ return ArrayBuffers.cachedTxnIds();
+ }
+ }
+}
diff --git a/accord-core/src/main/java/accord/primitives/KeyRoute.java b/accord-core/src/main/java/accord/primitives/KeyRoute.java
index ccb2a9f..39f0653 100644
--- a/accord-core/src/main/java/accord/primitives/KeyRoute.java
+++ b/accord-core/src/main/java/accord/primitives/KeyRoute.java
@@ -7,7 +7,7 @@ import accord.utils.SortedArrays;
import javax.annotation.Nonnull;
-public abstract class KeyRoute extends AbstractRoutableKeys<Route<RoutingKey>> implements Route<RoutingKey>
+public abstract class KeyRoute extends AbstractUnseekableKeys<Route<RoutingKey>> implements Route<RoutingKey>
{
public final RoutingKey homeKey;
diff --git a/accord-core/src/main/java/accord/primitives/PartialDeps.java b/accord-core/src/main/java/accord/primitives/PartialDeps.java
index addf11e..4a633ad 100644
--- a/accord-core/src/main/java/accord/primitives/PartialDeps.java
+++ b/accord-core/src/main/java/accord/primitives/PartialDeps.java
@@ -1,49 +1,38 @@
package accord.primitives;
-import com.google.common.base.Preconditions;
+import accord.utils.Invariants;
public class PartialDeps extends Deps
{
- public static final PartialDeps NONE = new PartialDeps(Ranges.EMPTY, Deps.NONE.keys, Deps.NONE.txnIds, Deps.NONE.keyToTxnId);
+ public static final PartialDeps NONE = new PartialDeps(Ranges.EMPTY, KeyDeps.NONE, RangeDeps.NONE);
- public static class SerializerSupport
+ public static Builder builder(Ranges covering)
{
- private SerializerSupport() {}
-
- public static PartialDeps create(Ranges covering, Keys keys, TxnId[] txnIds, int[] keyToTxnId)
- {
- return new PartialDeps(covering, keys, txnIds, keyToTxnId);
- }
+ return new Builder(covering);
}
-
- public static class OrderedBuilder extends AbstractOrderedBuilder<PartialDeps>
+ public static class Builder extends AbstractBuilder<PartialDeps>
{
final Ranges covering;
- public OrderedBuilder(Ranges covering, boolean hasOrderedTxnId)
+ public Builder(Ranges covering)
{
- super(hasOrderedTxnId);
this.covering = covering;
}
@Override
- PartialDeps build(Keys keys, TxnId[] txnIds, int[] keysToTxnIds)
+ public PartialDeps build()
{
- return new PartialDeps(covering, keys, txnIds, keysToTxnIds);
+ return new PartialDeps(covering, keyBuilder.build(), rangeBuilder == null ? RangeDeps.NONE : rangeBuilder.build());
}
}
- public static OrderedBuilder orderedBuilder(Ranges ranges, boolean hasOrderedTxnId)
- {
- return new OrderedBuilder(ranges, hasOrderedTxnId);
- }
-
public final Ranges covering;
- PartialDeps(Ranges covering, Keys keys, TxnId[] txnIds, int[] keyToTxnId)
+ public PartialDeps(Ranges covering, KeyDeps keyDeps, RangeDeps rangeDeps)
{
- super(keys, txnIds, keyToTxnId);
+ super(keyDeps, rangeDeps);
this.covering = covering;
- Preconditions.checkState(covering.containsAll(keys));
+ Invariants.checkState(covering.containsAll(keyDeps.keys));
+ Invariants.checkState(rangeDeps.isCoveredBy(covering));
}
public boolean covers(Unseekables<?, ?> keysOrRanges)
@@ -53,15 +42,17 @@ public class PartialDeps extends Deps
public PartialDeps with(PartialDeps that)
{
- Deps merged = with((Deps) that);
- return new PartialDeps(covering.union(that.covering), merged.keys, merged.txnIds, merged.keyToTxnId);
+ Invariants.checkArgument((this.rangeDeps == null) == (that.rangeDeps == null));
+ return new PartialDeps(that.covering.union(this.covering),
+ this.keyDeps.with(that.keyDeps),
+ this.rangeDeps == null ? null : this.rangeDeps.with(that.rangeDeps));
}
public Deps reconstitute(FullRoute<?> route)
{
if (!covers(route))
throw new IllegalArgumentException();
- return new Deps(keys, txnIds, keyToTxnId);
+ return new Deps(keyDeps, rangeDeps);
}
// PartialRoute<?>might cover a wider set of ranges, some of which may have no involved keys
@@ -73,7 +64,24 @@ public class PartialDeps extends Deps
if (covers(route.covering()))
return this;
- return new PartialDeps(route.covering(), keys, txnIds, keyToTxnId);
+ return new PartialDeps(route.covering(), keyDeps, rangeDeps);
+ }
+
+ @Override
+ public boolean equals(Object that)
+ {
+ return this == that || (that instanceof PartialDeps && equals((PartialDeps) that));
+ }
+
+ @Override
+ public boolean equals(Deps that)
+ {
+ return that instanceof PartialDeps && equals((PartialDeps) that);
+ }
+
+ public boolean equals(PartialDeps that)
+ {
+ return this.covering.equals(that.covering) && super.equals(that);
}
@Override
@@ -81,5 +89,4 @@ public class PartialDeps extends Deps
{
return covering + ":" + super.toString();
}
-
}
diff --git a/accord-core/src/main/java/accord/primitives/PartialKeyRoute.java b/accord-core/src/main/java/accord/primitives/PartialKeyRoute.java
index da9143a..212bffb 100644
--- a/accord-core/src/main/java/accord/primitives/PartialKeyRoute.java
+++ b/accord-core/src/main/java/accord/primitives/PartialKeyRoute.java
@@ -26,6 +26,7 @@ public class PartialKeyRoute extends KeyRoute implements PartialRoute<RoutingKey
this.covering = covering;
}
+ @Override
public PartialKeyRoute sliceStrict(Ranges newRanges)
{
if (!covering.containsAll(newRanges))
@@ -55,7 +56,7 @@ public class PartialKeyRoute extends KeyRoute implements PartialRoute<RoutingKey
}
@Override
- public AbstractRoutableKeys<?> with(RoutingKey withKey)
+ public AbstractUnseekableKeys<?> with(RoutingKey withKey)
{
if (contains(withKey))
return this;
@@ -63,6 +64,7 @@ public class PartialKeyRoute extends KeyRoute implements PartialRoute<RoutingKey
return new RoutingKeys(toRoutingKeysArray(withKey));
}
+ @Override
public PartialKeyRoute slice(Ranges newRanges)
{
if (newRanges.containsAll(covering))
@@ -78,6 +80,7 @@ public class PartialKeyRoute extends KeyRoute implements PartialRoute<RoutingKey
return covering;
}
+ @Override
public PartialKeyRoute union(PartialRoute<RoutingKey> with)
{
if (!(with instanceof PartialKeyRoute))
diff --git a/accord-core/src/main/java/accord/primitives/PartialRangeRoute.java b/accord-core/src/main/java/accord/primitives/PartialRangeRoute.java
index 42a9aac..204d939 100644
--- a/accord-core/src/main/java/accord/primitives/PartialRangeRoute.java
+++ b/accord-core/src/main/java/accord/primitives/PartialRangeRoute.java
@@ -50,6 +50,7 @@ public class PartialRangeRoute extends RangeRoute implements PartialRoute<Range>
return ranges.intersects(covering);
}
+ @Override
public PartialRangeRoute sliceStrict(Ranges newRange)
{
if (!covering.containsAll(newRange))
@@ -64,6 +65,7 @@ public class PartialRangeRoute extends RangeRoute implements PartialRoute<Range>
throw new UnsupportedOperationException();
}
+ @Override
public PartialRangeRoute slice(Ranges newRanges)
{
if (newRanges.containsAll(covering))
@@ -72,6 +74,7 @@ public class PartialRangeRoute extends RangeRoute implements PartialRoute<Range>
return slice(newRanges, this, homeKey, PartialRangeRoute::new);
}
+ @Override
public Unseekables<Range, ?> with(RoutingKey withKey)
{
throw new UnsupportedOperationException();
@@ -84,6 +87,7 @@ public class PartialRangeRoute extends RangeRoute implements PartialRoute<Range>
return union((PartialRangeRoute) that);
}
+ @Override
public PartialRangeRoute union(PartialRoute<Range> with)
{
if (!(with instanceof PartialRangeRoute))
diff --git a/accord-core/src/main/java/accord/primitives/PartialRoute.java b/accord-core/src/main/java/accord/primitives/PartialRoute.java
index cb93004..50ebea5 100644
--- a/accord-core/src/main/java/accord/primitives/PartialRoute.java
+++ b/accord-core/src/main/java/accord/primitives/PartialRoute.java
@@ -2,6 +2,7 @@ package accord.primitives;
public interface PartialRoute<T extends Unseekable> extends Route<T>
{
+ @Override
boolean isEmpty();
Ranges covering();
diff --git a/accord-core/src/main/java/accord/primitives/PartialTxn.java b/accord-core/src/main/java/accord/primitives/PartialTxn.java
index f9588b1..71e7554 100644
--- a/accord-core/src/main/java/accord/primitives/PartialTxn.java
+++ b/accord-core/src/main/java/accord/primitives/PartialTxn.java
@@ -50,6 +50,7 @@ public interface PartialTxn extends Txn
return covering;
}
+ @Override
public PartialTxn with(PartialTxn add)
{
if (!add.kind().equals(kind()))
@@ -78,6 +79,7 @@ public interface PartialTxn extends Txn
return covering.containsAll(ranges);
}
+ @Override
public Txn reconstitute(FullRoute<?> route)
{
if (!covers(route) || query() == null)
@@ -86,6 +88,7 @@ public interface PartialTxn extends Txn
return new Txn.InMemory(kind(), keys(), read(), query(), update());
}
+ @Override
public PartialTxn reconstitutePartial(PartialRoute<?> route)
{
if (!covers(route))
diff --git a/accord-core/src/main/java/accord/primitives/Range.java b/accord-core/src/main/java/accord/primitives/Range.java
index 463a910..98fb673 100644
--- a/accord-core/src/main/java/accord/primitives/Range.java
+++ b/accord-core/src/main/java/accord/primitives/Range.java
@@ -18,6 +18,7 @@
package accord.primitives;
+import accord.api.Key;
import accord.api.RoutingKey;
import accord.utils.Invariants;
import accord.utils.SortedArrays;
@@ -67,6 +68,12 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
{
return new EndInclusive(start, end);
}
+
+ @Override
+ public String toString()
+ {
+ return "Range(" + start() + ", " + end() + ']';
+ }
}
public static class StartInclusive extends Range
@@ -103,6 +110,12 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
{
return new StartInclusive(start, end);
}
+
+ @Override
+ public String toString()
+ {
+ return "Range[" + start() + ", " + end() + ')';
+ }
}
public static Range range(RoutingKey start, RoutingKey end, boolean startInclusive, boolean endInclusive)
@@ -163,7 +176,7 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
if (start.compareTo(end) >= 0)
throw new IllegalArgumentException(start + " >= " + end);
if (startInclusive() == endInclusive())
- throw new IllegalStateException("KeyRange must have one side inclusive, and the other exclusive. KeyRange of different types should not be mixed.");
+ throw new IllegalStateException("Range must have one side inclusive, and the other exclusive. Range of different types should not be mixed.");
this.start = start;
this.end = end;
}
@@ -178,6 +191,7 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
return end;
}
+ @Override
public final Domain domain() { return Domain.Range; }
public abstract boolean startInclusive();
@@ -185,6 +199,18 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
public abstract Range subRange(RoutingKey start, RoutingKey end);
+ @Override
+ public Key asKey()
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public Range asRange()
+ {
+ return this;
+ }
+
@Override
public boolean equals(Object o)
{
@@ -200,16 +226,11 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
return start.hashCode() * 31 + end.hashCode();
}
- @Override
- public String toString()
- {
- return "Range[" + start + ", " + end + ']';
- }
-
/**
* Returns a negative integer, zero, or a positive integer as the provided key is greater than, contained by,
* or less than this range.
*/
+ @Override
public abstract int compareTo(RoutableKey key);
public boolean contains(RoutableKey key)
@@ -224,7 +245,7 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
public int compareIntersecting(Range that)
{
if (that.getClass() != this.getClass())
- throw new IllegalArgumentException("Cannot mix KeyRange of different types");
+ throw new IllegalArgumentException("Cannot mix Range of different types");
if (this.start.compareTo(that.end) >= 0)
return 1;
if (this.end.compareTo(that.start) <= 0)
@@ -232,6 +253,18 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
return 0;
}
+ /**
+ * Sorts by start then end
+ */
+ public int compare(Range that)
+ {
+ if (that.getClass() != this.getClass())
+ throw new IllegalArgumentException("Cannot mix Range of different types");
+ int c = this.start.compareTo(that.start);
+ if (c == 0) c = this.end.compareTo(that.end);
+ return c;
+ }
+
public boolean contains(Range that)
{
return that.start.compareTo(this.start) >= 0 && that.end.compareTo(this.end) <= 0;
@@ -297,7 +330,7 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
}
@Override
- public Unseekable toUnseekable()
+ public Range toUnseekable()
{
return this;
}
diff --git a/accord-core/src/main/java/accord/primitives/RangeDeps.java b/accord-core/src/main/java/accord/primitives/RangeDeps.java
new file mode 100644
index 0000000..74da4cd
--- /dev/null
+++ b/accord-core/src/main/java/accord/primitives/RangeDeps.java
@@ -0,0 +1,663 @@
+package accord.primitives;
+
+import accord.api.Key;
+import accord.utils.*;
+import accord.utils.RelationMultiMap.AbstractBuilder;
+import accord.utils.RelationMultiMap.Adapter;
+import net.nicoulaj.compilecommand.annotations.DontInline;
+import net.nicoulaj.compilecommand.annotations.Inline;
+
+import javax.annotation.Nonnull;
+import javax.annotation.Nullable;
+import java.util.*;
+import java.util.function.Consumer;
+import java.util.function.Function;
+import java.util.function.Predicate;
+
+import static accord.utils.ArrayBuffers.*;
+import static accord.utils.RelationMultiMap.*;
+import static accord.utils.RelationMultiMap.remove;
+import static accord.utils.SearchableRangeListBuilder.Links.LINKS;
+import static accord.utils.SearchableRangeListBuilder.Strategy.ACCURATE;
+import static accord.utils.SortedArrays.Search.CEIL;
+
+/**
+ * <p>Maintains a lazily-constructed, bidirectional map between Range and TxnId.
+ * <p>Ranges are stored sorted by start then end, and indexed by a secondary {@link SearchableRangeList} structure.
+ * <p>The relationship between Range and TxnId is maintained via {@code int[]} utilising {@link RelationMultiMap}
+ * functionality.
+ */
+public class RangeDeps implements Iterable<Map.Entry<Range, TxnId>>
+{
+ public static class SerializerSupport
+ {
+ private SerializerSupport() {}
+
+ public static int rangesToTxnIdsCount(RangeDeps deps)
+ {
+ return deps.rangesToTxnIds.length;
+ }
+
+ public static int rangesToTxnIds(RangeDeps deps, int idx)
+ {
+ return deps.rangesToTxnIds[idx];
+ }
+
+ public static RangeDeps create(Range[] ranges, TxnId[] txnIds, int[] rangesToTxnIds)
+ {
+ return new RangeDeps(ranges, txnIds, rangesToTxnIds);
+ }
+ }
+
+ private static final Range[] NO_RANGES = new Range[0];
+ public static final RangeDeps NONE = new RangeDeps(new Range[0], new TxnId[0], new int[0], new int[0]);
+
+ final TxnId[] txnIds;
+ // the list of ranges and their mappings to txnIds
+ // unique, and sorted by start()
+ final Range[] ranges;
+ /**
+ * See {@link RelationMultiMap}.
+ * TODO consider alternative layout depending on real-world data distributions:
+ * if most ranges have at most TxnId (or vice-versa) might be better to use negative values
+ * to index into the dynamic portion of the array. We started with this, but decided it was
+ * hard to justify the extra work for two layouts for the moment.
+ */
+ final int[] rangesToTxnIds;
+ int[] txnIdsToRanges;
+
+ private SearchableRangeList searchable;
+
+ public static <T1, T2> RangeDeps merge(List<T1> merge, Function<T1, T2> getter1, Function<T2, RangeDeps> getter2)
+ {
+ try (LinearMerger<Range, TxnId, RangeDeps> linearMerger = new LinearMerger<>(ADAPTER))
+ {
+ int mergeIndex = 0, mergeSize = merge.size();
+ while (mergeIndex < mergeSize)
+ {
+ T2 intermediate = getter1.apply(merge.get(mergeIndex++));
+ if (intermediate == null)
+ continue;
+
+ RangeDeps deps = getter2.apply(intermediate);
+ if (deps == null || deps.isEmpty())
+ continue;
+
+ linearMerger.update(deps, deps.ranges, deps.txnIds, deps.rangesToTxnIds);
+ }
+
+ return linearMerger.get(RangeDeps::new, NONE);
+ }
+ }
+
+ private RangeDeps(Range[] ranges, TxnId[] txnIds, int[] rangesToTxnIds)
+ {
+ this(ranges, txnIds, rangesToTxnIds, null);
+ }
+
+ private RangeDeps(Range[] ranges, TxnId[] txnIds, int[] rangesToTxnIds, int[] txnIdsToRanges)
+ {
+ Invariants.checkArgument(rangesToTxnIds.length >= ranges.length);
+ Invariants.checkArgument(ranges.length > 0 || rangesToTxnIds.length == 0);
+ Invariants.paranoid(SortedArrays.isSorted(ranges, Range::compare));
+ this.ranges = ranges;
+ this.txnIds = txnIds;
+ this.rangesToTxnIds = rangesToTxnIds;
+ this.txnIdsToRanges = txnIdsToRanges;
+ }
+
+ @Inline
+ public <P1, P2, P3> int forEach(Key key, IndexedTriConsumer<P1, P2, P3> forEachScanOrCheckpoint, IndexedRangeTriConsumer<P1, P2, P3> forEachRange, P1 p1, P2 p2, P3 p3, int minIndex)
+ {
+ return ensureSearchable().forEach(key, forEachScanOrCheckpoint, forEachRange, p1, p2, p3, minIndex);
+ }
+
+ private int forEach(Key key, Consumer<TxnId> forEach, int minIndex, @Nullable BitSet visited)
+ {
+ return forEach(key, RangeDeps::visitTxnIdsForRangeIndex, RangeDeps::visitTxnIdsForRangeIndex,
+ this, forEach, visited, minIndex);
+ }
+
+ @Inline
+ public <P1, P2, P3> int forEach(Range range, IndexedTriConsumer<P1, P2, P3> forEachScanOrCheckpoint, IndexedRangeTriConsumer<P1, P2, P3> forEachRange, P1 p1, P2 p2, P3 p3, int minIndex)
+ {
+ return ensureSearchable().forEach(range, forEachScanOrCheckpoint, forEachRange, p1, p2, p3, minIndex);
+ }
+
+ private <P1, P2, P3> void forEach(Ranges ranges, IndexedTriConsumer<P1, P2, P3> forEachScanOrCheckpoint, IndexedRangeTriConsumer<P1, P2, P3> forEachRange, P1 p1, P2 p2, P3 p3)
+ {
+ int minIndex = 0;
+ for (int i = 0; i < ranges.size() ; ++i)
+ minIndex = forEach(ranges.get(i), forEachScanOrCheckpoint, forEachRange, p1, p2, p3, minIndex);
+ }
+
+ private int forEach(Range range, Consumer<TxnId> forEach, int minIndex, @Nullable BitSet visited)
+ {
+ return forEach(range, RangeDeps::visitTxnIdsForRangeIndex, RangeDeps::visitTxnIdsForRangeIndex,
+ this, forEach, visited, minIndex);
+ }
+
+ private void visitTxnIdsForRangeIndex(Consumer<TxnId> forEach, @Nullable BitSet visited, int rangeIndex)
+ {
+ for (int i = startOffset(ranges, rangesToTxnIds, rangeIndex), end = endOffset(rangesToTxnIds, rangeIndex) ; i < end ; ++i)
+ visitTxnIdx(rangesToTxnIds[i], forEach, visited);
+ }
+
+ private void visitTxnIdsForRangeIndex(Consumer<TxnId> forEach, @Nullable BitSet visited, int start, int end)
+ {
+ if (end == 0)
+ return;
+ for (int i = startOffset(ranges, rangesToTxnIds, start) ; i < endOffset(rangesToTxnIds, end - 1) ; ++i)
+ visitTxnIdx(rangesToTxnIds[i], forEach, visited);
+ }
+
+ // TODO (low priority, efficiency): ideally we would accept something like a BitHashSet or IntegerTrie
+ // as O(N) space needed for BitSet here (but with a very low constant multiplier)
+ private void visitTxnIdx(int txnIdx, Consumer<TxnId> forEach, @Nullable BitSet visited)
+ {
+ if (visited == null || !visited.get(txnIdx))
+ {
+ if (visited != null)
+ visited.set(txnIdx);
+ forEach.accept(txnIds[txnIdx]);
+ }
+ }
+
+ /**
+ * Each matching TxnId will be provided precisely once
+ */
+ public void forEachUniqueTxnId(Key key, Consumer<TxnId> forEach)
+ {
+ forEach(key, forEach, 0, new BitSet());
+ }
+
+ /**
+ * The same TxnId may be provided as a parameter multiple times
+ */
+ public void forEach(Range range, Consumer<TxnId> forEach)
+ {
+ forEach(range, forEach, 0, null);
+ }
+
+ /**
+ * The same TxnId may be provided as a parameter multiple times
+ */
+ public void forEach(Ranges ranges, Consumer<TxnId> forEach)
+ {
+ int minIndex = 0;
+ for (int i = 0; i < ranges.size() ; ++i)
+ minIndex = forEach(ranges.get(i), forEach, minIndex, null);
+ }
+
+ /**
+ * Each matching TxnId will be provided precisely once
+ */
+ public void forEachUniqueTxnId(Range range, Consumer<TxnId> forEach)
+ {
+ forEach(range, forEach, 0, new BitSet());
+ }
+
+ /**
+ * Each matching TxnId will be provided precisely once
+ *
+ * @param ranges to match on
+ * @param forEach function to call on each unique {@link TxnId}
+ */
+ public void forEachUniqueTxnId(Ranges ranges, Consumer<TxnId> forEach)
+ {
+ int minIndex = 0;
+ for (int i = 0; i < ranges.size() ; ++i)
+ minIndex = forEach(ranges.get(i), forEach, minIndex, new BitSet());
+ }
+
+ // return true iff we map any ranges to any txnId
+ // if the mapping is empty we return false, whether or not we have any ranges or txnId by themselves
+ public boolean isEmpty()
+ {
+ return RelationMultiMap.isEmpty(ranges, rangesToTxnIds);
+ }
+
+ public Unseekables<Range, ?> someUnseekables(TxnId txnId)
+ {
+ int txnIdIndex = Arrays.binarySearch(txnIds, txnId);
+ if (txnIdIndex < 0)
+ throw new IllegalStateException("Cannot create a RouteFragment without any keys");
+
+ ensureTxnIdToRange();
+
+ int start = txnIdIndex == 0 ? txnIds.length : txnIdsToRanges[txnIdIndex - 1];
+ int end = txnIdsToRanges[txnIdIndex];
+ if (start == end)
+ throw new IllegalStateException("Cannot create a RouteFragment without any keys");
+
+ Range[] result = new Range[end - start];
+ result[0] = ranges[txnIdsToRanges[start]].toUnseekable();
+ int resultCount = 1;
+ for (int i = start + 1 ; i < end ; ++i)
+ {
+ Range next = ranges[txnIdsToRanges[i]];
+ if (!next.equals(result[resultCount - 1]))
+ result[resultCount++] = next;
+ }
+
+ if (resultCount < result.length)
+ result = Arrays.copyOf(result, resultCount);
+ return new Ranges(result);
+ }
+
+ void ensureTxnIdToRange()
+ {
+ if (txnIdsToRanges != null)
+ return;
+
+ txnIdsToRanges = invert(rangesToTxnIds, rangesToTxnIds.length, ranges.length, txnIds.length);
+ }
+
+ public RangeDeps slice(Ranges select)
+ {
+ if (isEmpty())
+ return new RangeDeps(NO_RANGES, txnIds, NO_INTS);
+
+ try (RangeAndMapCollector collector = new RangeAndMapCollector(ensureSearchable().maxScanAndCheckpointMatches))
+ {
+ forEach(select, collector, collector, ranges, rangesToTxnIds, null);
+
+ if (collector.rangesCount == 0)
+ return new RangeDeps(NO_RANGES, NO_TXNIDS, NO_INTS);
+
+ if (collector.rangesCount == this.ranges.length)
+ return this;
+
+ Range[] ranges = collector.getRanges();
+ int[] rangesToTxnIds = collector.getRangesToTxnIds();
+ TxnId[] txnIds = trimUnusedValues(ranges, this.txnIds, rangesToTxnIds, TxnId[]::new);
+ return new RangeDeps(ranges, txnIds, rangesToTxnIds);
+ }
+ }
+
+ public RangeDeps with(RangeDeps that)
+ {
+ if (isEmpty() || that.isEmpty())
+ return isEmpty() ? that : this;
+
+ return linearUnion(
+ this.ranges, this.ranges.length, this.txnIds, this.txnIds.length, this.rangesToTxnIds, this.rangesToTxnIds.length,
+ that.ranges, that.ranges.length, that.txnIds, that.txnIds.length, that.rangesToTxnIds, that.rangesToTxnIds.length,
+ rangeComparator(), TxnId::compareTo,
+ cachedRanges(), cachedTxnIds(), cachedInts(),
+ (ranges, rangesLength, txnIds, txnIdsLength, out, outLength) ->
+ new RangeDeps(cachedRanges().complete(ranges, rangesLength),
+ cachedTxnIds().complete(txnIds, txnIdsLength),
+ cachedInts().complete(out, outLength))
+ );
+ }
+
+ public RangeDeps without(Predicate<TxnId> remove)
+ {
+ return remove(this, ranges, txnIds, rangesToTxnIds, remove,
+ NONE, TxnId[]::new, ranges, RangeDeps::new);
+ }
+
+ public boolean contains(TxnId txnId)
+ {
+ return Arrays.binarySearch(txnIds, txnId) >= 0;
+ }
+
+ public boolean isCoveredBy(Ranges covering)
+ {
+ // check that every entry intersects with some entry in covering
+ int prev = 0;
+ for (Range range : covering)
+ {
+ int start = SortedArrays.binarySearch(ranges, 0, ranges.length, range.start(), (a, b) -> a.compareTo(b.start()), CEIL);
+ if (start < 0) start = -1 - start;
+ int end = SortedArrays.binarySearch(ranges, 0, ranges.length, range.end(), (a, b) -> a.compareTo(b.start()), CEIL);
+ if (end < 0) end = -1 - end;
+ for (int i = prev; i < start ; ++i)
+ {
+ if (range.compareIntersecting(ranges[i]) != 0)
+ return false;
+ }
+ prev = end;
+ }
+ return prev == ranges.length;
+ }
+
+ public List<TxnId> txnIds(Key key)
+ {
+ List<TxnId> result = new ArrayList<>();
+ forEachUniqueTxnId(key, result::add);
+ result.sort(TxnId::compareTo);
+ return result;
+ }
+
+ public List<TxnId> txnIds(Range key)
+ {
+ List<TxnId> result = new ArrayList<>();
+ forEachUniqueTxnId(key, result::add);
+ result.sort(TxnId::compareTo);
+ return result;
+ }
+
+ public TxnId txnId(int i)
+ {
+ return txnIds[i];
+ }
+
+ public int txnIdCount()
+ {
+ return txnIds.length;
+ }
+
+ public Range range(int i)
+ {
+ return ranges[i];
+ }
+
+ public int rangeCount()
+ {
+ return ranges.length;
+ }
+
+ @Override
+ public boolean equals(Object that)
+ {
+ return this == that || (that instanceof RangeDeps && equals((RangeDeps)that));
+ }
+
+ public boolean equals(RangeDeps that)
+ {
+ return testEquality(this.ranges, this.txnIds, this.rangesToTxnIds, that.ranges, that.txnIds, that.rangesToTxnIds);
+ }
+
+ @Override
+ public String toString()
+ {
+ return RelationMultiMap.toSimpleString(ranges, txnIds, rangesToTxnIds);
+ }
+
+ @Nonnull
+ @Override
+ public Iterator<Map.Entry<Range, TxnId>> iterator()
+ {
+ return newIterator(ranges, txnIds, rangesToTxnIds);
+ }
+
+ private SearchableRangeList ensureSearchable()
+ {
+ if (searchable == null)
+ buildSearchable();
+ return searchable;
+ }
+
+ @DontInline
+ private void buildSearchable()
+ {
+ searchable = SearchableRangeList.build(ranges);
+ }
+
+ public boolean isSearchable()
+ {
+ return searchable != null;
+ }
+
+ static class RangeCollector implements
+ IndexedRangeTriConsumer<Range[], int[], Object>,
+ IndexedTriConsumer<Range[], int[], Object>,
+ AutoCloseable
+ {
+ int[] oooBuffer;
+ Range[] rangesOut;
+ int oooCount, rangesCount;
+
+ RangeCollector(int maxScanAndCheckpointCount)
+ {
+ oooBuffer = cachedInts().getInts(maxScanAndCheckpointCount);
+ rangesOut = cachedRanges().get(32);
+ }
+
+ @Override
+ public void accept(Range[] o, int[] o2, Object o3, int index)
+ {
+ oooBuffer[oooCount++] = index;
+ }
+
+ @Override
+ public void accept(Range[] ranges, int[] rangesToTxnIds, Object o3, int fromIndex, int toIndex)
+ {
+ if (oooCount > 0)
+ {
+ Arrays.sort(oooBuffer, 0, oooCount);
+ int oooCount = Arrays.binarySearch(oooBuffer, 0, this.oooCount, fromIndex);
+ if (oooCount < 0) oooCount = -1 - oooCount;
+ copy(ranges, rangesToTxnIds, oooCount, fromIndex, toIndex);
+ this.oooCount = 0;
+ }
+ else if (fromIndex < toIndex)
+ {
+ copy(ranges, rangesToTxnIds, 0, fromIndex, toIndex);
+ }
+ }
+
+ protected void copy(Range[] ranges, int[] rangesToTxnIds, int oooCount, int start, int end)
+ {
+ int count = oooCount + (end - start);
+ if (rangesCount + count >= rangesOut.length)
+ rangesOut = cachedRanges().resize(rangesOut, rangesCount, rangesCount + count + (rangesCount /2));
+ for (int i = 0 ; i < oooCount ; ++i)
+ rangesOut[rangesCount++] = ranges[oooBuffer[i]];
+ for (int i = start ; i < end ; ++i)
+ rangesOut[rangesCount++] = ranges[i];
+ }
+
+ Range[] getRanges()
+ {
+ Range[] result = cachedRanges().completeAndDiscard(rangesOut, rangesCount);
+ rangesOut = null;
+ return result;
+ }
+
+ @Override
+ public void close()
+ {
+ if (oooBuffer != null)
+ {
+ cachedInts().forceDiscard(oooBuffer);
+ oooBuffer = null;
+ }
+ if (rangesOut != null)
+ {
+ cachedRanges().forceDiscard(rangesOut, rangesCount);
+ rangesOut = null;
+ }
+ }
+ }
+
+ static class RangeAndMapCollector extends RangeCollector
+ {
+ int[] headers;
+ int[] lists;
+ int headerCount, listOffset;
+
+ RangeAndMapCollector(int maxScanAndCheckpointCount)
+ {
+ super(maxScanAndCheckpointCount);
+ headers = cachedInts().getInts(32);
+ lists = cachedInts().getInts(32);
+ }
+
+ @Override
+ protected void copy(Range[] ranges, int[] rangesToTxnIds, int oooCount, int start, int end)
+ {
+ super.copy(ranges, rangesToTxnIds, oooCount, start, end);
+ int count = oooCount + (end - start);
+ if (headerCount + count >= headers.length)
+ headers = cachedInts().resize(headers, headerCount, headerCount + count + (headerCount /2));
+ for (int i = 0 ; i < oooCount ; ++i)
+ {
+ int ri = oooBuffer[i];
+ copyToDynamic(rangesToTxnIds, startOffset(ranges, rangesToTxnIds, ri), endOffset(rangesToTxnIds, ri));
+ headers[headerCount++] = listOffset;
+ }
+ int startOffset = startOffset(ranges, rangesToTxnIds, start);
+ for (int i = start ; i < end ; ++i)
+ headers[this.headerCount++] = listOffset + rangesToTxnIds[i] - startOffset;
+ copyToDynamic(rangesToTxnIds, startOffset, startOffset(ranges, rangesToTxnIds, end));
+ }
+
+ protected void copyToDynamic(int[] rangesToTxnIds, int start, int end)
+ {
+ int count = end - start;
+ if (count + listOffset >= lists.length)
+ lists = cachedInts().resize(lists, listOffset, listOffset + (listOffset /2) + count);
+ System.arraycopy(rangesToTxnIds, start, lists, listOffset, count);
+ listOffset += count;
+ }
+
+ public int[] getRangesToTxnIds()
+ {
+ int[] out = new int[headerCount + listOffset];
+ for (int i = 0; i < headerCount; ++i)
+ out[i] = headers[i] + headerCount;
+ System.arraycopy(lists, 0, out, headerCount, listOffset);
+ return out;
+ }
+ }
+
+ public static RangeDeps of(Map<TxnId, Ranges> txnIdRanges)
+ {
+ if (txnIdRanges.isEmpty())
+ return NONE;
+
+ try (BuilderByTxnId builder = new BuilderByTxnId())
+ {
+ for (Map.Entry<TxnId, Ranges> e : txnIdRanges.entrySet())
+ {
+ builder.nextKey(e.getKey());
+ Ranges ranges = e.getValue();
+ for (int i = 0 ; i < ranges.size() ; ++i)
+ builder.add(ranges.get(i));
+ }
+ return builder.build();
+ }
+ }
+
+ public static Builder builder()
+ {
+ return new Builder();
+ }
+
+ public static class Builder extends AbstractBuilder<Range, TxnId, RangeDeps>
+ {
+ public Builder()
+ {
+ super(ADAPTER);
+ }
+
+ @Override
+ protected RangeDeps none()
+ {
+ return RangeDeps.NONE;
+ }
+
+ @Override
+ protected RangeDeps build(Range[] ranges, TxnId[] txnIds, int[] keyToValue)
+ {
+ return new RangeDeps(ranges, txnIds, keyToValue);
+ }
+ }
+
+ public static BuilderByTxnId byTxnIdBuilder()
+ {
+ return new BuilderByTxnId();
+ }
+
+ public static class BuilderByTxnId extends AbstractBuilder<TxnId, Range, RangeDeps>
+ {
+ public BuilderByTxnId()
+ {
+ super(REVERSE_ADAPTER);
+ }
+
+ @Override
+ protected RangeDeps none()
+ {
+ return RangeDeps.NONE;
+ }
+
+ @Override
+ protected RangeDeps build(TxnId[] txnIds, Range[] ranges, int[] txnIdsToRanges)
+ {
+ return new RangeDeps(ranges, txnIds, invert(txnIdsToRanges, txnIdsToRanges.length, txnIds.length, ranges.length), txnIdsToRanges);
+ }
+ }
+
+ public static SymmetricComparator<? super Range> rangeComparator()
+ {
+ return RangeDeps::compare;
+ }
+
+ public static int compare(Range left, Range right)
+ {
+ int c = left.start().compareTo(right.start());
+ if (c == 0) c = left.end().compareTo(right.end());
+ return c;
+ }
+
+ private static final RangeDepsAdapter ADAPTER = new RangeDepsAdapter();
+ private static final class RangeDepsAdapter implements Adapter<Range, TxnId>
+ {
+ @Override
+ public SymmetricComparator<? super Range> keyComparator()
+ {
+ return rangeComparator();
+ }
+
+ @Override
+ public SymmetricComparator<? super TxnId> valueComparator()
+ {
+ return TxnId::compareTo;
+ }
+
+ @Override
+ public ObjectBuffers<Range> cachedKeys()
+ {
+ return ArrayBuffers.cachedRanges();
+ }
+
+ @Override
+ public ObjectBuffers<TxnId> cachedValues()
+ {
+ return ArrayBuffers.cachedTxnIds();
+ }
+ }
+
+ private static final ReverseRangeDepsAdapter REVERSE_ADAPTER = new ReverseRangeDepsAdapter();
+ private static final class ReverseRangeDepsAdapter implements Adapter<TxnId, Range>
+ {
+ @Override
+ public SymmetricComparator<? super TxnId> keyComparator()
+ {
+ return TxnId::compareTo;
+ }
+
+ @Override
+ public SymmetricComparator<? super Range> valueComparator()
+ {
+ return rangeComparator();
+ }
+
+ @Override
+ public ObjectBuffers<TxnId> cachedKeys()
+ {
+ return ArrayBuffers.cachedTxnIds();
+ }
+
+ @Override
+ public ObjectBuffers<Range> cachedValues()
+ {
+ return ArrayBuffers.cachedRanges();
+ }
+ }
+
+}
diff --git a/accord-core/src/main/java/accord/primitives/Ranges.java b/accord-core/src/main/java/accord/primitives/Ranges.java
index 6101195..2b8a2bc 100644
--- a/accord-core/src/main/java/accord/primitives/Ranges.java
+++ b/accord-core/src/main/java/accord/primitives/Ranges.java
@@ -128,7 +128,7 @@ public class Ranges extends AbstractRanges<Ranges> implements Iterable<Range>, S
}
/**
- * Subtracts the given set of key ranges from this
+ * Subtracts the given set of ranges from this
*/
public Ranges difference(AbstractRanges<?> that)
{
diff --git a/accord-core/src/main/java/accord/primitives/RoutableKey.java b/accord-core/src/main/java/accord/primitives/RoutableKey.java
index f8de9d6..c48124d 100644
--- a/accord-core/src/main/java/accord/primitives/RoutableKey.java
+++ b/accord-core/src/main/java/accord/primitives/RoutableKey.java
@@ -44,10 +44,13 @@ public interface RoutableKey extends Routable, Comparable<RoutableKey>
* @param that the object to be compared.
* @return
*/
+ @Override
int compareTo(@Nonnull RoutableKey that);
+ @Override
default Domain domain() { return Domain.Key; }
+ @Override
RoutingKey toUnseekable();
@Override default RoutingKey someIntersectingRoutingKey() { return toUnseekable(); }
diff --git a/accord-core/src/main/java/accord/primitives/Route.java b/accord-core/src/main/java/accord/primitives/Route.java
index a349b4e..01b5ebd 100644
--- a/accord-core/src/main/java/accord/primitives/Route.java
+++ b/accord-core/src/main/java/accord/primitives/Route.java
@@ -10,8 +10,11 @@ public interface Route<K extends Unseekable> extends Unseekables<K, Route<K>>
default boolean isRoute() { return true; }
boolean covers(Ranges ranges);
+ @Override
boolean intersects(AbstractRanges<?> ranges);
+ @Override
Route<K> union(Route<K> route);
+ @Override
PartialRoute<K> slice(Ranges ranges);
PartialRoute<K> sliceStrict(Ranges ranges);
diff --git a/accord-core/src/main/java/accord/primitives/RoutingKeys.java b/accord-core/src/main/java/accord/primitives/RoutingKeys.java
index fd30ecf..0e29954 100644
--- a/accord-core/src/main/java/accord/primitives/RoutingKeys.java
+++ b/accord-core/src/main/java/accord/primitives/RoutingKeys.java
@@ -5,7 +5,7 @@ import accord.utils.SortedArrays;
import static accord.utils.ArrayBuffers.cachedRoutingKeys;
-public class RoutingKeys extends AbstractRoutableKeys<AbstractRoutableKeys<?>> implements Unseekables<RoutingKey, AbstractRoutableKeys<?>>
+public class RoutingKeys extends AbstractUnseekableKeys<AbstractUnseekableKeys<?>> implements Unseekables<RoutingKey, AbstractUnseekableKeys<?>>
{
public static class SerializationSupport
{
@@ -27,11 +27,13 @@ public class RoutingKeys extends AbstractRoutableKeys<AbstractRoutableKeys<?>> i
return new RoutingKeys(sort(keys));
}
- public RoutingKeys union(AbstractRoutableKeys<?> that)
+ @Override
+ public RoutingKeys union(AbstractUnseekableKeys<?> that)
{
return wrap(SortedArrays.linearUnion(keys, that.keys, cachedRoutingKeys()), that);
}
+ @Override
public RoutingKeys with(RoutingKey with)
{
if (contains(with))
@@ -45,6 +47,7 @@ public class RoutingKeys extends AbstractRoutableKeys<AbstractRoutableKeys<?>> i
return UnseekablesKind.RoutingKeys;
}
+ @Override
public RoutingKeys slice(Ranges ranges)
{
return wrap(slice(ranges, RoutingKey[]::new));
diff --git a/accord-core/src/main/java/accord/primitives/Seekable.java b/accord-core/src/main/java/accord/primitives/Seekable.java
index cc84767..f702353 100644
--- a/accord-core/src/main/java/accord/primitives/Seekable.java
+++ b/accord-core/src/main/java/accord/primitives/Seekable.java
@@ -1,8 +1,12 @@
package accord.primitives;
+import accord.api.Key;
+
/**
* Something that can be found within the cluster AND found on disk, queried and returned
*/
public interface Seekable extends Routable
{
+ Key asKey();
+ Range asRange();
}
diff --git a/accord-core/src/main/java/accord/primitives/Seekables.java b/accord-core/src/main/java/accord/primitives/Seekables.java
index da3a532..0bed766 100644
--- a/accord-core/src/main/java/accord/primitives/Seekables.java
+++ b/accord-core/src/main/java/accord/primitives/Seekables.java
@@ -7,7 +7,9 @@ import accord.api.RoutingKey;
*/
public interface Seekables<K extends Seekable, U extends Seekables<K, ?>> extends Routables<K, U>
{
+ @Override
U slice(Ranges ranges);
+ @Override
Seekables<K, U> union(U with);
Unseekables<?, ?> toUnseekables();
diff --git a/accord-core/src/main/java/accord/primitives/TxnId.java b/accord-core/src/main/java/accord/primitives/TxnId.java
index e2b40bb..5f51c20 100644
--- a/accord-core/src/main/java/accord/primitives/TxnId.java
+++ b/accord-core/src/main/java/accord/primitives/TxnId.java
@@ -82,6 +82,7 @@ public class TxnId extends Timestamp
return domain(flags());
}
+ @Override
public TxnId merge(Timestamp that)
{
return merge(this, that, TxnId::fromBits);
diff --git a/accord-core/src/main/java/accord/primitives/Unseekables.java b/accord-core/src/main/java/accord/primitives/Unseekables.java
index 68e0206..8cdb2ee 100644
--- a/accord-core/src/main/java/accord/primitives/Unseekables.java
+++ b/accord-core/src/main/java/accord/primitives/Unseekables.java
@@ -22,7 +22,9 @@ public interface Unseekables<K extends Unseekable, U extends Unseekables<K, ?>>
}
}
+ @Override
U slice(Ranges ranges);
+ @Override
Unseekables<K, U> union(U with);
Unseekables<K, ?> with(RoutingKey withKey);
UnseekablesKind kind();
diff --git a/accord-core/src/main/java/accord/primitives/package-info.java b/accord-core/src/main/java/accord/primitives/package-info.java
index f25136d..f75bcb8 100644
--- a/accord-core/src/main/java/accord/primitives/package-info.java
+++ b/accord-core/src/main/java/accord/primitives/package-info.java
@@ -1,9 +1,11 @@
package accord.primitives;
/**
- * Routable: a RoutingKey or Range (of RoutingKey). Something that can address a replica in the cluster.
+ * Routable: a RoutingKey, Key or Range. Something that can address a replica in the cluster.
+ * Unseekable: a RoutingKey or Range (of RoutingKey). Something that can ONLY address a replica in the cluster.
* Seekable: a Key or Range (of either RoutingKey or Key). Something that can address some physical data on a node.
* Routables: a collection of Routable
+ * Unseekables: a collection of Unseekable
* Seekables: a collection of Seekable
* Route: a collection of Routable including a homeKey. Represents a consistent slice (or slices) of token ranges.
* Either a PartialRoute or a FullRoute.
diff --git a/accord-core/src/main/java/accord/topology/Topology.java b/accord-core/src/main/java/accord/topology/Topology.java
index a502bd4..c055a82 100644
--- a/accord-core/src/main/java/accord/topology/Topology.java
+++ b/accord-core/src/main/java/accord/topology/Topology.java
@@ -177,7 +177,7 @@ public class Topology
return info != null ? info.ranges : Ranges.EMPTY;
}
- // TODO: optimised HomeKey concept containing the Key, Shard and Topology to avoid lookups when topology hasn't changed
+ // TODO (low priority, efficiency): optimised HomeKey concept containing the Key, Shard and Topology to avoid lookups when topology hasn't changed
public Shard forKey(RoutingKey key)
{
int i = ranges.indexOf(key);
@@ -294,7 +294,7 @@ public class Topology
}
catch (Throwable t)
{
- cachedInts.forceDiscard(newSubset, count);
+ cachedInts.forceDiscard(newSubset);
throw t;
}
diff --git a/accord-core/src/main/java/accord/utils/ArrayBuffers.java b/accord-core/src/main/java/accord/utils/ArrayBuffers.java
index d1ad72a..c021f25 100644
--- a/accord-core/src/main/java/accord/utils/ArrayBuffers.java
+++ b/accord-core/src/main/java/accord/utils/ArrayBuffers.java
@@ -90,13 +90,30 @@ public class ArrayBuffers
public interface IntBufferAllocator
{
/**
- * Return an {@code int[]} of size at least {@code minSize}, possibly from a pool
+ * Return an {@code int[]} of size at least {@code minSize}, possibly from a pool.
+ * This array may not be zero initialized, and its contents should be treated as random.
*/
int[] getInts(int minSize);
}
public interface IntBuffers extends IntBufferAllocator
{
+ /**
+ * Return an {@code int[]} of size at least {@code minSize}, possibly from a pool,
+ * and copy the contents of {@code copyAndDiscard} into it.
+ *
+ * The remainder of the array may not be zero-initialized, and should be assumed to contain random data.
+ *
+ * The parameter will be returned to the pool, if eligible.
+ */
+ default int[] resize(int[] copyAndDiscard, int usedSize, int minSize)
+ {
+ int[] newBuf = getInts(minSize);
+ System.arraycopy(copyAndDiscard, 0, newBuf, 0, usedSize);
+ forceDiscard(copyAndDiscard);
+ return newBuf;
+ }
+
/**
* To be invoked on the result buffer with the number of elements contained;
* either the buffer will be returned and the size optionally captured, or else the result may be
@@ -134,29 +151,59 @@ public class ArrayBuffers
* Indicate this buffer is definitely unused, and return it to a pool if possible
* @return true if the buffer is discarded (and discard-able), false if it was retained
*/
- boolean forceDiscard(int[] buffer, int usedSize);
+ boolean forceDiscard(int[] buffer);
}
public interface ObjectBuffers<T>
{
/**
- * Return an {@code T[]} of size at least {@code minSize}, possibly from a pool
+ * Return an {@code T[]} of size at least {@code minSize}, possibly from a pool.
+ * This array will be null-initialized and can be assumed to be empty.
*/
T[] get(int minSize);
+ /**
+ * Return an {@code T[]} of size at least {@code minSize}, possibly from a pool,
+ * and copy the contents of {@code copyAndDiscard} into it.
+ *
+ * The remainder of the array can be assumed to be null initialized.
+ *
+ * The parameter will be returned to the pool, if eligible.
+ */
+ default T[] resize(T[] copyAndDiscard, int usedSize, int minSize)
+ {
+ T[] newBuf = get(minSize);
+ System.arraycopy(copyAndDiscard, 0, newBuf, 0, usedSize);
+ forceDiscard(copyAndDiscard, usedSize);
+ return newBuf;
+ }
+
/**
* To be invoked on the result buffer with the number of elements contained;
* either the buffer will be returned and the size optionally captured, or else the result may be
* shrunk to the size of the contents, depending on implementation.
*/
- T[] complete(T[] buffer, int size);
+ T[] complete(T[] buffer, int usedSize);
+
+ /**
+ * Equivalent to
+ * int[] result = complete(buffer, usedSize);
+ * discard(buffer, usedSize);
+ * return result;
+ */
+ default T[] completeAndDiscard(T[] buffer, int usedSize)
+ {
+ T[] result = complete(buffer, usedSize);
+ discard(buffer, usedSize);
+ return result;
+ }
/**
* To be invoked on an input buffer that constitutes the result, with the number of elements it contained;
* either the buffer will be returned and the size optionally captured, or else the result may be
* shrunk to the size of the contents, depending on implementation.
*/
- T[] completeWithExisting(T[] buffer, int size);
+ T[] completeWithExisting(T[] buffer, int usedSize);
/**
* The buffer is no longer needed by the caller, which is discarding the array;
@@ -172,7 +219,7 @@ public class ArrayBuffers
*
* @return true if the buffer is discarded (and discard-able), false if it was retained or is believed to be in use
*/
- boolean discard(T[] buffer, int size);
+ boolean discard(T[] buffer, int usedSize);
/**
* Indicate this buffer is definitely unused, and return it to a pool if possible
@@ -181,7 +228,7 @@ public class ArrayBuffers
*
* @return true if the buffer is discarded (and discard-able), false if it was retained
*/
- boolean forceDiscard(T[] buffer, int size);
+ boolean forceDiscard(T[] buffer, int usedSize);
/**
* Returns the {@code size} parameter provided to the most recent {@link #complete(Object[], int)} or {@link #completeWithExisting(Object[], int)}
@@ -216,11 +263,11 @@ public class ArrayBuffers
@Override
public boolean discard(int[] buffer, int usedSize)
{
- return forceDiscard(buffer, usedSize);
+ return forceDiscard(buffer);
}
@Override
- public boolean forceDiscard(int[] buffer, int usedSize)
+ public boolean forceDiscard(int[] buffer)
{
// if FULLY_UNCACHED we want our caller to also not cache us, so we indicate the buffer has been retained
return !FULLY_UNCACHED;
@@ -242,18 +289,18 @@ public class ArrayBuffers
}
@Override
- public T[] complete(T[] buffer, int size)
+ public T[] complete(T[] buffer, int usedSize)
{
- if (size == buffer.length)
+ if (usedSize == buffer.length)
return buffer;
- return Arrays.copyOf(buffer, size);
+ return Arrays.copyOf(buffer, usedSize);
}
@Override
- public T[] completeWithExisting(T[] buffer, int size)
+ public T[] completeWithExisting(T[] buffer, int usedSize)
{
- return checkArgument(buffer, buffer.length == size);
+ return checkArgument(buffer, buffer.length == usedSize);
}
@Override
@@ -263,13 +310,13 @@ public class ArrayBuffers
}
@Override
- public boolean discard(T[] buffer, int size)
+ public boolean discard(T[] buffer, int usedSize)
{
- return forceDiscard(buffer, size);
+ return forceDiscard(buffer, usedSize);
}
@Override
- public boolean forceDiscard(T[] buffer, int size)
+ public boolean forceDiscard(T[] buffer, int usedSize)
{
// if FULLY_UNCACHED we want our caller to also not cache us, so we indicate the buffer has been retained
return !FULLY_UNCACHED;
@@ -368,9 +415,9 @@ public class ArrayBuffers
}
@Override
- public boolean forceDiscard(int[] buffer, int usedSize)
+ public boolean forceDiscard(int[] buffer)
{
- return discardInternal(buffer, buffer.length, usedSize, true);
+ return discardInternal(buffer, buffer.length, -1, true);
}
@Override
@@ -390,34 +437,37 @@ public class ArrayBuffers
this.allocator = allocator;
}
- public T[] complete(T[] buffer, int size)
+ @Override
+ public T[] complete(T[] buffer, int usedSize)
{
- if (size == buffer.length)
+ if (usedSize == buffer.length)
return buffer;
- return Arrays.copyOf(buffer, size);
+ return Arrays.copyOf(buffer, usedSize);
}
@Override
- public T[] completeWithExisting(T[] buffer, int size)
+ public T[] completeWithExisting(T[] buffer, int usedSize)
{
return buffer;
}
+ @Override
public int lengthOfLast(T[] buffer)
{
return buffer.length;
}
- public boolean discard(T[] buffer, int size)
+ @Override
+ public boolean discard(T[] buffer, int usedSize)
{
- return discardInternal(buffer, buffer.length, size, false);
+ return discardInternal(buffer, buffer.length, usedSize, false);
}
@Override
- public boolean forceDiscard(T[] buffer, int size)
+ public boolean forceDiscard(T[] buffer, int usedSize)
{
- return discardInternal(buffer, buffer.length, size, true);
+ return discardInternal(buffer, buffer.length, usedSize, true);
}
@Override
@@ -455,16 +505,16 @@ public class ArrayBuffers
}
@Override
- public T[] complete(T[] buffer, int size)
+ public T[] complete(T[] buffer, int usedSize)
{
- length = size;
+ length = usedSize;
return buffer;
}
@Override
- public T[] completeWithExisting(T[] buffer, int size)
+ public T[] completeWithExisting(T[] buffer, int usedSize)
{
- length = size;
+ length = usedSize;
return buffer;
}
@@ -477,16 +527,16 @@ public class ArrayBuffers
}
@Override
- public boolean discard(T[] buffer, int size)
+ public boolean discard(T[] buffer, int usedSize)
{
return true;
}
@Override
- public boolean forceDiscard(T[] buffer, int size)
+ public boolean forceDiscard(T[] buffer, int usedSize)
{
length = -1;
- if (!objs.forceDiscard(buffer, size))
+ if (!objs.forceDiscard(buffer, usedSize))
return false;
return discardInternal(buffer);
@@ -513,6 +563,7 @@ public class ArrayBuffers
return true;
}
+ @Override
public int lengthOfLast(T[] buffer)
{
if (length == -1)
@@ -561,9 +612,9 @@ public class ArrayBuffers
}
@Override
- public boolean forceDiscard(int[] buffer, int usedSize)
+ public boolean forceDiscard(int[] buffer)
{
- if (!ints.forceDiscard(buffer, usedSize))
+ if (!ints.forceDiscard(buffer))
return false;
if (savedInts != null && savedInts.length >= buffer.length)
diff --git a/accord-core/src/main/java/accord/utils/DeterministicIdentitySet.java b/accord-core/src/main/java/accord/utils/DeterministicIdentitySet.java
index e380e39..1bb9410 100644
--- a/accord-core/src/main/java/accord/utils/DeterministicIdentitySet.java
+++ b/accord-core/src/main/java/accord/utils/DeterministicIdentitySet.java
@@ -105,6 +105,7 @@ public class DeterministicIdentitySet<T> extends AbstractSet<T>
}
// we add to the front, and iterate in reverse order, so that we can add and remove while iterating without modifying the set we iterate over
+ @Override
public boolean add(T item)
{
Entry<T> entry = lookup.computeIfAbsent(item, Entry::new);
@@ -117,6 +118,7 @@ public class DeterministicIdentitySet<T> extends AbstractSet<T>
return true;
}
+ @Override
public boolean remove(Object item)
{
Entry<T> entry = lookup.remove(item);
@@ -129,6 +131,7 @@ public class DeterministicIdentitySet<T> extends AbstractSet<T>
return true;
}
+ @Override
public void forEach(Consumer<? super T> consumer)
{
Entry<T> cur = head.next;
@@ -152,10 +155,4 @@ public class DeterministicIdentitySet<T> extends AbstractSet<T>
cur = cur.next;
}
}
-
- @Override
- public String toString()
- {
- return super.toString();
- }
}
diff --git a/accord-core/src/main/java/accord/utils/IntrusiveLinkedList.java b/accord-core/src/main/java/accord/utils/IntrusiveLinkedList.java
index 8b822e9..b9cefb4 100644
--- a/accord-core/src/main/java/accord/utils/IntrusiveLinkedList.java
+++ b/accord-core/src/main/java/accord/utils/IntrusiveLinkedList.java
@@ -77,6 +77,7 @@ public class IntrusiveLinkedList<O extends IntrusiveLinkedListNode> extends Intr
return next == this;
}
+ @Override
public Iterator<O> iterator()
{
return new Iterator<O>()
diff --git a/accord-core/src/main/java/accord/utils/MapReduce.java b/accord-core/src/main/java/accord/utils/MapReduce.java
index 5cc4adc..ac6ddf8 100644
--- a/accord-core/src/main/java/accord/utils/MapReduce.java
+++ b/accord-core/src/main/java/accord/utils/MapReduce.java
@@ -5,6 +5,7 @@ import java.util.function.Function;
public interface MapReduce<I, O> extends Function<I, O>
{
// TODO (desired, safety): ensure mutual exclusivity when calling each of these methods
+ @Override
O apply(I in);
O reduce(O o1, O o2);
}
diff --git a/accord-core/src/main/java/accord/utils/MapReduceConsume.java b/accord-core/src/main/java/accord/utils/MapReduceConsume.java
index c0a2f92..5ec710b 100644
--- a/accord-core/src/main/java/accord/utils/MapReduceConsume.java
+++ b/accord-core/src/main/java/accord/utils/MapReduceConsume.java
@@ -5,6 +5,7 @@ import java.util.function.Consumer;
public interface MapReduceConsume<I, O> extends MapReduce<I, O>, BiConsumer<O, Throwable>
{
+ @Override
void accept(O result, Throwable failure);
static <I> MapReduceConsume<I, Void> forEach(Consumer<I> forEach, BiConsumer<Object, Throwable> consume)
diff --git a/accord-core/src/main/java/accord/utils/RelationMultiMap.java b/accord-core/src/main/java/accord/utils/RelationMultiMap.java
new file mode 100644
index 0000000..cd3c8fb
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/RelationMultiMap.java
@@ -0,0 +1,1004 @@
+/*
+ * 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 accord.utils;
+
+import accord.primitives.*;
+import net.nicoulaj.compilecommand.annotations.Inline;
+
+import java.util.*;
+import java.util.function.IntFunction;
+import java.util.function.Predicate;
+import java.util.stream.Collectors;
+
+import static accord.utils.ArrayBuffers.*;
+import static accord.utils.SortedArrays.remap;
+import static accord.utils.SortedArrays.remapToSuperset;
+
+/**
+ * Instead of creating a parent object and having generic key/value methods, we introduce a bunch of static helper methods.
+ * This class helps maintain three sorted arrays: keys (of type K[]), values (of type V[]) and keysToValues (of type int[])
+ * <p>
+ * keysToValues represents a map of {@code Key -> [Value] } where each Value is a pointer into a sorted values array.
+ * The beginning of the array (the first keys.length entries) are offsets into this array.
+ * <p>
+ * Example:
+ * <p>
+ * {@code
+ * int keyIdx = Arrays.binarySearch(keys, key);
+ * int startOfValues = keyIdx == 0 ? keys.length : keysToValues[keyIdx - 1];
+ * int endOfValues = keysToValues[keyIdx];
+ * for (int i = startOfValues; i < endOfValues; i++)
+ * {
+ * V id = value[keysToValues[i]]
+ * ...
+ * }
+ * }
+ */
+public class RelationMultiMap
+{
+ private static final boolean DEBUG_CHECKS = true;
+ public static final int[] NO_INTS = new int[0];
+ public static final TxnId[] NO_TXNIDS = new TxnId[0];
+
+ /**
+ * Turn a set of key, value and mapping buffers into a merge result;
+ * K and V are either Key and TxnId, or vice versa, depending on which mapping direction was present
+ */
+ public interface Constructor<K, V, T>
+ {
+ T construct(K[] keys, int keysLength, V[] values, int valuesLength, int[] out, int outLength);
+ }
+ public interface SimpleConstructor<K, V, T>
+ {
+ T construct(K keys, V values, int[] out);
+ }
+
+ public interface Adapter<K, V>
+ {
+ SymmetricComparator<? super K> keyComparator();
+ SymmetricComparator<? super V> valueComparator();
+ ObjectBuffers<K> cachedKeys();
+ ObjectBuffers<V> cachedValues();
+ }
+
+
+ // TODO (expected, efficiency): cache this object per thread
+ public static abstract class AbstractBuilder<K, V, T> implements AutoCloseable
+ {
+ final Adapter<K, V> adapter;
+ final ObjectBuffers<K> cachedKeys;
+ final ObjectBuffers<V> cachedValues;
+ final IntBuffers cachedInts = cachedInts();
+
+ K[] keys;
+ int[] keyLimits;
+ // txnId -> Offset
+ V[] keysToValues;
+ int keyCount;
+ int keyOffset;
+ int totalCount;
+ boolean hasOrderedKeys = true;
+ boolean hasOrderedValues = true;
+
+ public AbstractBuilder(Adapter<K, V> adapter)
+ {
+ this.adapter = adapter;
+ this.cachedKeys = adapter.cachedKeys();
+ this.cachedValues = adapter.cachedValues();
+ this.keys = cachedKeys.get(16);
+ this.keyLimits = cachedInts.getInts(keys.length);
+ this.keysToValues = cachedValues.get(16);
+ }
+
+ public boolean isEmpty()
+ {
+ return totalCount() == 0;
+ }
+
+ private int totalCount()
+ {
+ return totalCount;
+ }
+
+ public void nextKey(K key)
+ {
+ if (keyCount > 0 && adapter.keyComparator().compare(keys[keyCount - 1], key) >= 0)
+ hasOrderedKeys = false;
+
+ finishKey();
+
+ if (keyCount == keys.length)
+ {
+ K[] newKeys = cachedKeys.get(keyCount * 2);
+ System.arraycopy(keys, 0, newKeys, 0, keyCount);
+ cachedKeys.forceDiscard(keys, keyCount);
+ keys = newKeys;
+ int[] newKeyLimits = cachedInts.getInts(keyCount * 2);
+ System.arraycopy(keyLimits, 0, newKeyLimits, 0, keyCount);
+ cachedInts.forceDiscard(keyLimits);
+ keyLimits = newKeyLimits;
+ }
+ keys[keyCount++] = key;
+ hasOrderedValues = true;
+ }
+
+ private void finishKey()
+ {
+ if (totalCount == keyOffset && keyCount > 0)
+ {
+ --keyCount; // remove this key; no data
+ return;
+ }
+
+ if (keyCount == 0)
+ return;
+
+ if (!hasOrderedValues)
+ {
+ // TODO (low priority, efficiency): this allocates a significant amount of memory: would be preferable to be able to sort using a pre-defined scratch buffer
+ Arrays.sort(keysToValues, keyOffset, totalCount);
+ for (int i = keyOffset + 1 ; i < totalCount ; ++i)
+ {
+ if (keysToValues[i - 1].equals(keysToValues[i]))
+ throw new IllegalArgumentException("TxnId for " + keys[keyCount - 1] + " are not unique: " + Arrays.asList(keysToValues).subList(keyOffset, totalCount));
+ }
+ }
+
+ keyLimits[keyCount - 1] = totalCount;
+ keyOffset = totalCount;
+ }
+
+ public void add(K key, V value)
+ {
+ if (keyCount == 0 || !keys[keyCount - 1].equals(key))
+ nextKey(key);
+ add(value);
+ }
+
+ /**
+ * Add this command as a dependency for each intersecting key
+ */
+ public void add(V value)
+ {
+ if (hasOrderedValues && totalCount > keyOffset && adapter.valueComparator().compare(keysToValues[totalCount - 1], value) >= 0)
+ hasOrderedValues = false;
+
+ if (totalCount >= keysToValues.length)
+ {
+ V[] newValues = cachedValues.get(keysToValues.length * 2);
+ System.arraycopy(keysToValues, 0, newValues, 0, totalCount);
+ cachedValues.forceDiscard(keysToValues, totalCount);
+ keysToValues = newValues;
+ }
+
+ keysToValues[totalCount++] = value;
+ }
+
+ public T build()
+ {
+ if (totalCount == 0)
+ return none();
+
+ finishKey();
+
+ V[] uniqueValues = cachedValues.get(totalCount);
+ System.arraycopy(keysToValues, 0, uniqueValues, 0, totalCount);
+ Arrays.sort(uniqueValues, 0, totalCount, adapter.valueComparator());
+ int valueCount = 1;
+ for (int i = 1 ; i < totalCount ; ++i)
+ {
+ if (!uniqueValues[valueCount - 1].equals(uniqueValues[i]))
+ uniqueValues[valueCount++] = uniqueValues[i];
+ }
+
+ V[] values = cachedValues.complete(uniqueValues, valueCount);
+ cachedValues.discard(uniqueValues, totalCount);
+
+ int[] sortedKeyIndexes;
+ K[] sortedKeys;
+ if (hasOrderedKeys)
+ {
+ sortedKeyIndexes = null;
+ sortedKeys = cachedKeys.completeAndDiscard(keys, keyCount);
+ }
+ else
+ {
+ sortedKeyIndexes = new int[keyCount];
+ sortedKeys = Arrays.copyOf(keys, keyCount);
+ Arrays.sort(sortedKeys);
+
+ for (int i = 1 ; i < keyCount ; ++i)
+ {
+ if (sortedKeys[i-1].equals(sortedKeys[i]))
+ throw new IllegalArgumentException("Key " + sortedKeys[i] + " has been visited more than once ("
+ + Arrays.toString(Arrays.copyOf(keys, keyCount)) + ")");
+ }
+ for (int i = 0 ; i < keyCount ; ++i)
+ sortedKeyIndexes[Arrays.binarySearch(sortedKeys, keys[i])] = i;
+ cachedKeys.forceDiscard(keys, keyCount);
+ }
+
+ int[] result = new int[keyCount + totalCount];
+ int offset = keyCount;
+ for (int ki = 0 ; ki < keyCount ; ++ki)
+ {
+ int k = sortedKeyIndexes == null ? ki : sortedKeyIndexes[ki];
+ int from = k == 0 ? 0 : keyLimits[k - 1];
+ int to = keyLimits[k];
+ offset = (int)SortedArrays.foldlIntersection(adapter.valueComparator(), values, 0, valueCount, keysToValues, from, to, (key, p, v, li, ri) -> {
+ result[(int)v] = li;
+ return v + 1;
+ }, 0, offset, -1);
+ result[ki] = offset;
+ }
+
+ return build(sortedKeys, values, result);
+ }
+
+ protected abstract T none();
+ protected abstract T build(K[] keys, V[] values, int[] keyToValue);
+
+ @Override
+ public void close()
+ {
+ cachedInts.forceDiscard(keyLimits);
+ cachedValues.forceDiscard(keysToValues, totalCount);
+ }
+ }
+
+ /**
+ * An object for managing a sequence of efficient linear merges Deps objects.
+ * Its primary purpose is to manage input and output buffers, so that we reuse output buffers
+ * as input to the next merge, and if any input is a superset of the other inputs that this input
+ * is returned unmodified.
+ *
+ * This is achieved by using PassThroughXBuffers so that the result buffers (and their sizes) are returned
+ * unmodified, and the buffers are cached as far as possible. In general, the buffers should be taken
+ * out of pre-existing caches, but if the buffers are too large then we cache any additional buffers we
+ * allocate for the duration of the merge.
+ */
+ public static class LinearMerger<K, V, T> extends PassThroughObjectAndIntBuffers<V> implements Constructor<K, V, Object>, AutoCloseable
+ {
+ final Adapter<K, V> adapter;
+ final PassThroughObjectBuffers<K> keyBuffers;
+ K[] bufKeys;
+ V[] bufValues;
+ int[] buf = null;
+ int bufKeysLength, bufValuesLength = 0, bufLength = 0;
+ T from = null;
+
+ public LinearMerger(Adapter<K, V> adapter)
+ {
+ super(adapter.cachedValues(), cachedInts());
+ keyBuffers = new PassThroughObjectBuffers<>(adapter.cachedKeys());
+ this.adapter = adapter;
+ }
+
+ @Override
+ public Object construct(K[] keys, int keysLength, V[] txnIds, int txnIdsLength, int[] out, int outLength)
+ {
+ if (from == null)
+ {
+ // if our input buffers were themselves buffers, we want to discard them unless they have been returned back to us
+ discard(keys, txnIds, out);
+ }
+ else if (buf != out)
+ {
+ // the output is not equal to a prior input
+ from = null;
+ }
+
+ if (from == null)
+ {
+ bufKeys = keys;
+ bufKeysLength = keysLength;
+ bufValues = txnIds;
+ bufValuesLength = txnIdsLength;
+ buf = out;
+ bufLength = outLength;
+ }
+ else
+ {
+ Invariants.checkState(keys == bufKeys && keysLength == bufKeysLength);
+ Invariants.checkState(txnIds == bufValues && txnIdsLength == bufValuesLength);
+ Invariants.checkState(outLength == bufLength);
+ }
+ return null;
+ }
+
+ public void update(T merge, K[] keys, V[] values, int[] keysToValues)
+ {
+ if (buf == null)
+ {
+ bufKeys = keys;
+ bufKeysLength = keys.length;
+ bufValues = values;
+ bufValuesLength = values.length;
+ buf = keysToValues;
+ bufLength = keysToValues.length;
+ from = merge;
+ return;
+ }
+
+ linearUnion(
+ bufKeys, bufKeysLength, bufValues, bufValuesLength, buf, bufLength,
+ keys, keys.length, values, values.length, keysToValues, keysToValues.length,
+ adapter.keyComparator(), adapter.valueComparator(),
+ keyBuffers, this, this, this
+ );
+ if (buf == keysToValues)
+ {
+ Invariants.checkState(keys == bufKeys && keys.length == bufKeysLength);
+ Invariants.checkState(values == bufValues && values.length == bufValuesLength);
+ Invariants.checkState(keysToValues.length == bufLength);
+ from = merge;
+ }
+ }
+
+ public T get(SimpleConstructor<K[], V[], T> constructor, T none)
+ {
+ if (buf == null)
+ return none;
+
+ if (from != null)
+ return from;
+
+ return constructor.construct(keyBuffers.realComplete(bufKeys, bufKeysLength),
+ realComplete(bufValues, bufValuesLength),
+ realComplete(buf, bufLength));
+ }
+
+ /**
+ * Free buffers unless they are equal to the corresponding parameter
+ */
+ void discard(K[] freeKeysIfNot, V[] freeValuesIfNot, int[] freeBufIfNot)
+ {
+ if (from != null)
+ return;
+
+ if (bufKeys != freeKeysIfNot)
+ {
+ keyBuffers.realDiscard(bufKeys, bufKeysLength);
+ bufKeys = null;
+ }
+ if (bufValues != freeValuesIfNot)
+ {
+ realDiscard(bufValues, bufValuesLength);
+ bufValues = null;
+ }
+ if (buf != freeBufIfNot)
+ {
+ realDiscard(buf, bufLength);
+ buf = null;
+ }
+ }
+
+ @Override
+ public void close()
+ {
+ if (from == null)
+ discard(null, null, null);
+ }
+ }
+
+ /**
+ * Returns the set of {@link TxnId}s that are referenced by {@code keysToTxnId}, and <strong>updates</strong>
+ * {@code keysToTxnId} to point to the new offsets in the returned set.
+ * @param keys object referenced by {@code keysToTxnId} index
+ * @param values to trim to the seen {@link TxnId}s
+ * @param keysToTxnId to use as reference for trimming, this index will be updated to reflect the trimmed offsets.
+ * @return smallest set of {@link TxnId} seen in {@code keysToTxnId}
+ *
+ * TODO (desired, efficiency): algorithmic complexity is poor if have shrunk TxnId dramatically.
+ */
+ public static <K, V> V[] trimUnusedValues(K[] keys, V[] values, int[] keysToTxnId, IntFunction<V[]> valueAllocator)
+ {
+ IntBuffers cache = ArrayBuffers.cachedInts();
+ // we use remapTxnId twice:
+ // - first we use the end to store a bitmap of those TxnId we are actually using
+ // - then we use it to store the remap index (incrementally replacing the bitmap)
+ int bitMapOffset = values.length + 1 - (values.length+31)/32;
+ int[] remapTxnId = cache.getInts(values.length + 1);
+ try
+ {
+ Arrays.fill(remapTxnId, bitMapOffset, values.length + 1, 0);
+ for (int i = keys.length ; i < keysToTxnId.length ; ++i)
+ setBit(remapTxnId, bitMapOffset, keysToTxnId[i]);
+
+ int offset = 0;
+ for (int i = 0 ; i < values.length ; ++i)
+ {
+ if (hasSetBit(remapTxnId, bitMapOffset, i)) remapTxnId[i] = offset++;
+ else remapTxnId[i] = -1;
+ }
+
+ V[] result = values;
+ if (offset < values.length)
+ {
+ result = valueAllocator.apply(offset);
+ for (int i = 0 ; i < values.length ; ++i)
+ {
+ if (remapTxnId[i] >= 0)
+ result[remapTxnId[i]] = values[i];
+ }
+ // Update keysToTxnId to point to the new remapped TxnId offsets
+ for (int i = keys.length ; i < keysToTxnId.length ; ++i)
+ keysToTxnId[i] = remapTxnId[keysToTxnId[i]];
+ }
+
+ return result;
+ }
+ finally
+ {
+ cache.forceDiscard(remapTxnId);
+ }
+ }
+
+ static boolean arraysEqual(int[] left, int[] right, int length)
+ {
+ if (left.length < length || right.length < length)
+ return false;
+
+ for (int i=0; i<length; i++)
+ if (left[i] !=right[i])
+ return false;
+
+ return true;
+ }
+
+ static <T> boolean arraysEqual(T[] left, T[] right, int length)
+ {
+ if (left.length < length || right.length < length)
+ return false;
+
+ for (int i=0; i<length; i++)
+ if (!Objects.equals(left[i], right[i]))
+ return false;
+
+ return true;
+ }
+
+ // TODO (low priority, efficiency): this method supports merging keyToTxnId OR txnIdToKey; we can perhaps save time
+ // and effort when constructing Deps on remote hosts by only producing txnIdToKey with OrderedCollector and serializing
+ // only this, and merging on the recipient before inverting, so that we only have to invert the final assembled deps
+ @Inline
+ public static <K, V, T>
+ T linearUnion(K[] leftKeys, int leftKeysLength, V[] leftValues, int leftValuesLength, int[] left, int leftLength,
+ K[] rightKeys, int rightKeysLength, V[] rightValues, int rightValuesLength, int[] right, int rightLength,
+ SymmetricComparator<? super K> keyComparator, SymmetricComparator<? super V> valueComparator,
+ ObjectBuffers<K> keyBuffers, ObjectBuffers<V> valueBuffers, IntBuffers intBuffers, Constructor<K, V, T> constructor)
+ {
+ K[] outKeys = null;
+ V[] outValues = null;
+ int[] remapLeft = null, remapRight = null, out = null;
+ int outLength = 0, outKeysLength = 0, outValuesLength = 0;
+
+ try
+ {
+ outKeys = SortedArrays.linearUnion(leftKeys, leftKeysLength, rightKeys, rightKeysLength, keyComparator, keyBuffers);
+ outKeysLength = keyBuffers.lengthOfLast(outKeys);
+ outValues = SortedArrays.linearUnion(leftValues, leftValuesLength, rightValues, rightValuesLength, valueComparator, valueBuffers);
+ outValuesLength = valueBuffers.lengthOfLast(outValues);
+
+ remapLeft = remapToSuperset(leftValues, leftValuesLength, outValues, outValuesLength, valueComparator, intBuffers);
+ remapRight = remapToSuperset(rightValues, rightValuesLength, outValues, outValuesLength, valueComparator, intBuffers);
+
+ if (remapLeft == null && remapRight == null && leftLength == rightLength && leftKeysLength == rightKeysLength
+ && arraysEqual(left, right, rightLength)
+ && arraysEqual(leftKeys, rightKeys, rightKeysLength)
+ )
+ {
+ return constructor.construct(leftKeys, leftKeysLength, leftValues, leftValuesLength, left, leftLength);
+ }
+
+ int lk = 0, rk = 0, ok = 0, l = leftKeysLength, r = rightKeysLength;
+ outLength = outKeysLength;
+
+ if (remapLeft == null && outKeys == leftKeys)
+ {
+ // "this" knows all the TxnId and Keys already, but do both agree on what Keys map to TxnIds?
+ noOp: while (lk < leftKeysLength && rk < rightKeysLength)
+ {
+ int ck = keyComparator.compare(leftKeys[lk], rightKeys[rk]);
+ if (ck < 0)
+ {
+ // "this" knows of a key not present in "that"
+ outLength += left[lk] - l; // logically append the key's TxnIds to the size
+ l = left[lk];
+ assert outLength == l && ok == lk && left[ok] == outLength;
+ ok++;
+ lk++;
+ }
+ else if (ck > 0)
+ {
+ // if this happened there is a bug with keys.union or keys are not actually sorted
+ throwUnexpectedMissingKeyException(leftKeys, lk, leftKeysLength, rightKeys, rk, rightKeysLength, true);
+ }
+ else
+ {
+ // both "this" and "that" know of the key
+ while (l < left[lk] && r < right[rk])
+ {
+ int nextLeft = left[l];
+ int nextRight = remap(right[r], remapRight);
+
+ if (nextLeft < nextRight)
+ {
+ // "this" knows of the txn that "that" didn't
+ outLength++;
+ l++;
+ }
+ else if (nextRight < nextLeft)
+ {
+ out = copy(left, outLength, leftLength + rightLength - r, intBuffers);
+ break noOp;
+ }
+ else
+ {
+ outLength++;
+ l++;
+ r++;
+ }
+ }
+
+ if (l < left[lk])
+ {
+ outLength += left[lk] - l;
+ l = left[lk];
+ }
+ else if (r < right[rk])
+ {
+ // "that" thinks a key includes a TxnId as a dependency but "this" doesn't, need to include this knowledge
+ out = copy(left, outLength, leftLength + rightLength - r, intBuffers);
+ break;
+ }
+
+ assert outLength == l && ok == lk && left[ok] == outLength;
+ ok++;
+ rk++;
+ lk++;
+ }
+ }
+
+ if (out == null)
+ return constructor.construct(leftKeys, leftKeysLength, leftValues, leftValuesLength, left, leftLength);
+ }
+ else if (remapRight == null && outKeys == rightKeys)
+ {
+ // "that" knows all the TxnId and keys already, but "this" does not
+ noOp: while (lk < leftKeysLength && rk < rightKeysLength)
+ {
+ int ck = keyComparator.compare(leftKeys[lk], rightKeys[rk]);
+ if (ck < 0)
+ {
+ // if this happened there is a bug with keys.union or keys are not actually sorted
+ throwUnexpectedMissingKeyException(leftKeys, lk, leftKeysLength, rightKeys, rk, rightKeysLength, false);
+ }
+ else if (ck > 0)
+ {
+ outLength += right[rk] - r;
+ r = right[rk];
+ assert outLength == r && ok == rk && right[ok] == outLength;
+ ok++;
+ rk++;
+ }
+ else
+ {
+ // both "this" and "that" know of the key
+ while (l < left[lk] && r < right[rk])
+ {
+ int nextLeft = remap(left[l], remapLeft);
+ int nextRight = right[r];
+
+ if (nextLeft < nextRight)
+ {
+ // "this" thinks a TxnID depends on Key but "that" doesn't, need to include this knowledge
+ out = copy(right, outLength, rightLength + leftLength - l, intBuffers);
+ break noOp;
+ }
+ else if (nextRight < nextLeft)
+ {
+ // "that" knows of the txn that "this" didn't
+ outLength++;
+ r++;
+ }
+ else
+ {
+ outLength++;
+ l++;
+ r++;
+ }
+ }
+
+ if (l < left[lk])
+ {
+ out = copy(right, outLength, rightLength + leftLength - l, intBuffers);
+ break;
+ }
+ else if (r < right[rk])
+ {
+ outLength += right[rk] - r;
+ r = right[rk];
+ }
+
+ assert outLength == r && ok == rk && right[ok] == outLength;
+ ok++;
+ rk++;
+ lk++;
+ }
+ }
+
+ if (out == null)
+ return constructor.construct(rightKeys, rightKeysLength, rightValues, rightValuesLength, right, rightLength);
+ }
+ else
+ {
+ out = intBuffers.getInts(leftLength + rightLength);
+ }
+
+ while (lk < leftKeysLength && rk < rightKeysLength)
+ {
+ int ck = keyComparator.compare(leftKeys[lk], rightKeys[rk]);
+ if (ck < 0)
+ {
+ while (l < left[lk])
+ out[outLength++] = remap(left[l++], remapLeft);
+ out[ok++] = outLength;
+ lk++;
+ }
+ else if (ck > 0)
+ {
+ while (r < right[rk])
+ out[outLength++] = remap(right[r++], remapRight);
+ out[ok++] = outLength;
+ rk++;
+ }
+ else
+ {
+ while (l < left[lk] && r < right[rk])
+ {
+ int nextLeft = remap(left[l], remapLeft);
+ int nextRight = remap(right[r], remapRight);
+
+ if (nextLeft <= nextRight)
+ {
+ out[outLength++] = nextLeft;
+ l += 1;
+ r += nextLeft == nextRight ? 1 : 0;
+ }
+ else
+ {
+ out[outLength++] = nextRight;
+ ++r;
+ }
+ }
+
+ while (l < left[lk])
+ out[outLength++] = remap(left[l++], remapLeft);
+
+ while (r < right[rk])
+ out[outLength++] = remap(right[r++], remapRight);
+
+ out[ok++] = outLength;
+ rk++;
+ lk++;
+ }
+ }
+
+ while (lk < leftKeysLength)
+ {
+ while (l < left[lk])
+ out[outLength++] = remap(left[l++], remapLeft);
+ out[ok++] = outLength;
+ lk++;
+ }
+
+ while (rk < rightKeysLength)
+ {
+ while (r < right[rk])
+ out[outLength++] = remap(right[r++], remapRight);
+ out[ok++] = outLength;
+ rk++;
+ }
+
+ return constructor.construct(outKeys, outKeysLength, outValues, outValuesLength, out, outLength);
+ }
+ finally
+ {
+ if (outKeys != null)
+ keyBuffers.discard(outKeys, outKeysLength);
+ if (outValues != null)
+ valueBuffers.discard(outValues, outValuesLength);
+ if (out != null)
+ intBuffers.discard(out, outLength);
+ if (remapLeft != null)
+ intBuffers.forceDiscard(remapLeft);
+ if (remapRight != null)
+ intBuffers.forceDiscard(remapRight);
+ }
+ }
+
+ static <A> void throwUnexpectedMissingKeyException(A[] leftKeys, int leftKeyIndex, int leftKeyLength, A[] rightKeys, int rightKeyIndex, int rightKeyLength, boolean isMissingLeft)
+ {
+ StringBuilder sb = new StringBuilder();
+ String missing = isMissingLeft ? "left" : "right";
+ String extra = isMissingLeft ? "right" : "left";
+ sb.append(missing).append(" knows all keys, yet ").append(extra).append(" knew of an extra key at indexes left[")
+ .append(leftKeyIndex).append("] = ").append(leftKeys[leftKeyIndex])
+ .append(", right[").append(rightKeyIndex).append("] = ").append(rightKeys[rightKeyIndex]).append("\n");
+ sb.append("leftKeys = ").append(Arrays.stream(leftKeys, 0, leftKeyLength).map(Object::toString).collect(Collectors.joining())).append('\n');
+ sb.append("rightKeys = ").append(Arrays.stream(rightKeys, 0, rightKeyLength).map(Object::toString).collect(Collectors.joining())).append('\n');
+ throw new IllegalStateException(sb.toString());
+ }
+
+ static int[] copy(int[] src, int to, int length, IntBuffers bufferManager)
+ {
+ if (length == 0)
+ return NO_INTS;
+
+ int[] result = bufferManager.getInts(length);
+ if (result.length < length)
+ throw new IllegalStateException();
+ System.arraycopy(src, 0, result, 0, to);
+ return result;
+ }
+
+ public static <K, K2, V, T> T remove(T from, K[] keys, V[] oldValues, int[] oldKeysToValues, Predicate<V> remove, T none, IntFunction<V[]> newValueArray,
+ K2 passthroughKeys, SimpleConstructor<K2, V[], T> constructor)
+ {
+ if (isEmpty(keys, oldKeysToValues))
+ return from;
+
+ IntBuffers cache = ArrayBuffers.cachedInts();
+ int[] remapValue = cache.getInts(oldValues.length);
+ int[] newKeyToValue = null;
+ V[] newValues;
+ int o;
+ try
+ {
+ int count = 0;
+ for (int i = 0 ; i < oldValues.length ; ++i)
+ {
+ if (remove.test(oldValues[i])) remapValue[i] = -1;
+ else remapValue[i] = count++;
+ }
+
+ if (count == oldValues.length)
+ return from;
+
+ if (count == 0)
+ return none;
+
+ newValues = newValueArray.apply(count);
+ for (int i = 0 ; i < oldValues.length ; ++i)
+ {
+ if (remapValue[i] >= 0)
+ newValues[remapValue[i]] = oldValues[i];
+ }
+
+ newKeyToValue = cache.getInts(oldKeysToValues.length);
+ int k = 0, i = keys.length;
+ o = i;
+ while (i < oldKeysToValues.length)
+ {
+ while (oldKeysToValues[k] == i)
+ newKeyToValue[k++] = o;
+
+ int remapped = remapValue[oldKeysToValues[i]];
+ if (remapped >= 0)
+ newKeyToValue[o++] = remapped;
+ ++i;
+ }
+
+ while (k < keys.length)
+ newKeyToValue[k++] = o;
+ }
+ catch (Throwable t)
+ {
+ cache.forceDiscard(newKeyToValue);
+ throw t;
+ }
+ finally
+ {
+ cache.forceDiscard(remapValue);
+ }
+
+ newKeyToValue = cache.completeAndDiscard(newKeyToValue, o);
+ return constructor.construct(passthroughKeys, newValues, newKeyToValue);
+ }
+
+ @Inline
+ public static int[] invert(int[] src, int srcLength, int srcKeyCount, int trgKeyCount)
+ {
+ int[] trg = new int[trgKeyCount + srcLength - srcKeyCount];
+
+ // first pass, count number of txnId per key
+ for (int i = srcKeyCount ; i < srcLength ; ++i)
+ trg[src[i]]++;
+
+ // turn into offsets (i.e. add txnIds.size() and then sum them)
+ trg[0] += trgKeyCount;
+ for (int i = 1; i < trgKeyCount ; ++i)
+ trg[i] += trg[i - 1];
+
+ // shuffle forwards one, so we have the start index rather than end
+ System.arraycopy(trg, 0, trg, 1, trgKeyCount - 1);
+ trg[0] = trgKeyCount;
+
+ // convert the offsets to end, and set the key at the target positions
+ int k = 0;
+ for (int i = srcKeyCount ; i < srcLength ; ++i)
+ {
+ // if at the end offset, switch to the next key
+ while (i == src[k])
+ ++k;
+
+ // find the next key offset for the TxnId and set the offset to this key
+ trg[trg[src[i]]++] = k;
+ }
+
+ return trg;
+ }
+
+ public static <K, V> Iterator<Map.Entry<K, V>> newIterator(K[] keys, V[] values, int[] keysToValues)
+ {
+ return new Iterator<Map.Entry<K, V>>()
+ {
+ int i = keys.length, k = 0;
+
+ @Override
+ public boolean hasNext()
+ {
+ return i < keysToValues.length;
+ }
+
+ @Override
+ public Map.Entry<K, V> next()
+ {
+ Entry<K, V> result = new Entry<>(keys[k], values[keysToValues[i++]]);
+ if (i == keysToValues[k])
+ ++k;
+ return result;
+ }
+ };
+ }
+
+ public static <K, V> String toSimpleString(K[] keys, V[] values, int[] keysToValues)
+ {
+ if (isEmpty(keys, keysToValues))
+ return "{}";
+
+ StringBuilder builder = new StringBuilder("{");
+ for (int k = 0, t = keys.length; k < keys.length ; ++k)
+ {
+ if (builder.length() > 1)
+ builder.append(", ");
+
+ builder.append(keys[k]);
+ builder.append(":[");
+ boolean first = true;
+ while (t < keysToValues[k])
+ {
+ if (first) first = false;
+ else builder.append(", ");
+ builder.append(values[keysToValues[t++]]);
+ }
+ builder.append("]");
+ }
+ builder.append("}");
+ return builder.toString();
+ }
+
+ public static boolean isEmpty(Object[] keys, int[] keysToValues)
+ {
+ return keys.length == keysToValues.length;
+ }
+
+ public static int startOffset(Object[] keys, int[] keysToValues, int keyIndex)
+ {
+ return keyIndex == 0 ? keys.length : keysToValues[keyIndex - 1];
+ }
+
+ public static int endOffset(int[] keysToValues, int keyIndex)
+ {
+ return keysToValues[keyIndex];
+ }
+
+ @Inline
+ public static <K, V> boolean testEquality(K[] thisKeys, V[] thisValues, int[] thisKeysToValues,
+ K[] thatKeys, V[] thatValues, int[] thatKeysToValues)
+ {
+ return thisValues.length == thatValues.length
+ && thisKeys.length == thatKeys.length
+ && Arrays.equals(thisKeysToValues, thatKeysToValues)
+ && Arrays.equals(thisValues, thatValues)
+ && Arrays.equals(thisKeys, thatKeys);
+ }
+
+ public static class Entry<K, V> implements Map.Entry<K, V>
+ {
+ final K key;
+ final V value;
+
+ public Entry(K key, V value)
+ {
+ this.key = key;
+ this.value = value;
+ }
+
+ @Override
+ public K getKey()
+ {
+ return key;
+ }
+
+ @Override
+ public V getValue()
+ {
+ return value;
+ }
+
+ @Override
+ public V setValue(V value)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public String toString()
+ {
+ return key + "->" + value;
+ }
+ }
+
+ @Inline
+ public static <K, V> void checkValid(K[] keys, V[] values, int[] keysToValues)
+ {
+ if (!DEBUG_CHECKS)
+ return;
+
+ int k = 0;
+ for (int i = keys.length; i < keysToValues.length ; ++i)
+ {
+ boolean first = true;
+ while (i < keysToValues[k])
+ {
+ if (first) first = false;
+ else if (keysToValues[i - 1] == keysToValues[i])
+ {
+ K key = keys[i];
+ V value = values[keysToValues[i]];
+ throw new IllegalStateException(String.format("Duplicate value (%s) found for key %s", value, key));
+ }
+ i++;
+ }
+ ++k;
+ }
+ }
+
+ private static void setBit(int[] array, int offset, int index)
+ {
+ array[offset + index / 32] |= (1 << (index & 31));
+ }
+
+ private static boolean hasSetBit(int[] array, int offset, int index)
+ {
+ return (array[offset + index / 32] & (1 << (index & 31))) != 0;
+ }
+}
diff --git a/accord-core/src/main/java/accord/utils/SearchableRangeList.java b/accord-core/src/main/java/accord/utils/SearchableRangeList.java
new file mode 100644
index 0000000..3c6e3d4
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/SearchableRangeList.java
@@ -0,0 +1,292 @@
+package accord.utils;
+
+import accord.api.Key;
+import accord.primitives.Range;
+import accord.primitives.RoutableKey;
+import accord.utils.SearchableRangeListBuilder.Links;
+import accord.utils.SearchableRangeListBuilder.Strategy;
+import net.nicoulaj.compilecommand.annotations.Inline;
+
+import java.util.*;
+
+import static accord.utils.SearchableRangeListBuilder.Links.LINKS;
+import static accord.utils.SearchableRangeListBuilder.Strategy.ACCURATE;
+import static accord.utils.SortedArrays.Search.*;
+
+/**
+ * Based on CINTIA, the Checkpoint INTerval Array
+ * [Transactions on Big Data; Ruslan Mavlyutov and Philippe Cudre-Mauroux of U. of Fribourg]
+ * <p>
+ * CINTIA is a very simple augmentation of a sorted list of intervals that permits efficient intersection queries.
+ * The key insight is to augment the list of intervals (sorted by their start bound) with periodic checkpoints
+ * containing a list of the intervals that remain open from an earlier point in the list.
+ * The sorted interval list can easily return all intersections whose start overlaps a provided interval, and a
+ * backwards walk through the list to the prior checkpoint, plus a walk of the checkpoint, can answer all intersections
+ * that started prior, but whose ends overlap the query interval.
+ * <p>
+ * Besides this key insight, which honestly isn't that different to Cassandra packing active range tombstone bounds
+ * into index files, we largely take our own approach.
+ * <p>
+ * <ul>
+ * <li> We sort the intervals by start then end bound, so that we may easily find all overlaps that <i>start</i> in a queried range
+ * <li> Checkpoints are maintained in an auxiliary structure, keyed by the index of the first range they cover so that
+ * we have good locality and may perform fast binary search on the lower range index we find in step one
+ * <li> By being maintained separately we may dynamically decide when to insert a checkpoint.
+ * This potentially permits a single checkpoint to cover a large area.
+ * <li> Our scan runs for some fixed distance from the first overlapping range we find by simple binary search,
+ * with each checkpoint defining the scan distance. This permits checkpoints to cover longer regions, and
+ * also to avoid serializing ranges that occur before the checkpoint but that are easily scanned.
+ * <li> We write our dynamic checkpoints based on some simple maths that yield linear space overhead and O(k)
+ * additional work where k is the number of overlapping ranges with any given point
+ * <ul>
+ * <li> We perform a greedy iteration of the ranges, with some initial {@code goalScanDistance}; any range that can be found
+ * from every overlapping range index by a backwards scan shorter than this will record only the actual distance required.
+ * <li> Other ranges are "tenured" and will trigger a checkpoint to be written either immediately (if the last checkpoint was
+ * long ago enough), or else within the maximum scan distance from the first location the range was first encountered
+ * <li> The maximum scan distance is proportional to the larger of: the logarithm of the total number of ranges in the collection,
+ * and the number of tenured ranges written to the last checkpoint, discounted by the number of ranges since removed.
+ * This guarantees O(lg(N)+k) where k is the size of the result set for a query, while ensuring our O(N) space requirements.
+ * Essentially, we require that the distance between two checkpoints be at least as large as the number of duplicate
+ * elements we may serialize, so we can write at most O(N) duplicate entries, and we can write unique entries at most
+ * once, i.e. O(N) in total. Since we sort the checkpoints in descending order, we will never visit more than O(k)
+ * entries, where k is the number of matches. The number of scanned entries is similarly capped by the same logic;
+ * for each entry we remove from the tenured collection we bring our threshold for writing a new checkpoint down,
+ * so that by the time we are permitted to write a checkpoint we must have fewer tenured entries than we may scan.
+ * TODO (low priority, efficiency): probably we want to take the maximum of the current tenured.size() and the
+ * discounted minimum span when deciding IF we want to write a new checkpoint, even if our complexity permits
+ * writing solely based on the discounted minimum span.
+ * </ul>
+ * <li>We additionally permit our checkpoints to reference earlier checkpoints whose end bounds are still open.
+ * We permit this to a depth of at most one, i.e. we do not transitively explore checkpoints referenced by
+ * earlier checkpoints.
+ * </ul>
+ */
+public class SearchableRangeList
+{
+ // scan distance can be kept very small as we guarantee to use at most linear extra space even with a scan distance of zero
+ static final int MAX_SCAN_DISTANCE = 255;
+ private static final int BIT30 = 0x40000000;
+ private static final int BIT29 = 0x20000000;
+
+ private static final SearchableRangeList EMPTY_CHECKPOINTS = new SearchableRangeList(new Range[0], new int[0], new int[] { 0, 0 }, new int[0], 0);
+
+ final Range[] ranges;
+
+ /**
+ * The lower bound for each checkpoint.
+ * The checkpoint {@code i} applies to all ranges (incl) starting from {@code lowerBounds[i]},
+ * but before (excl) {@code lowerBounds[i+1]}.
+ */
+ final int[] lowerBounds;
+
+ /**
+ * Logically one entry per checkpoint, mapping {@link #lowerBounds} to {@link #checkpointLists},
+ * however we also encode an additional byte per entry representing the scan distance for the
+ * ranges handled by this checkpoint. These are grouped into an integer per four mappings, i.e.
+ * we encode batches of five ints, with the first int containing the four scan distances for the
+ * next four checkpoints, and the following four ints containing the respective offsets into
+ * {@link #checkpointLists}.
+ * <p>
+ * [0.........32b.........64b.........96b........128b........160b........192b]
+ * [ d1 d2 d3 d4 mapping1 mapping2 mapping3 mapping4 d5 d6 d7 d8 ]
+ */
+ final int[] headers;
+
+ /**
+ * A list of indexes in {@link #ranges} contained by each checkpoint; checkpoints are
+ * mapped from {@link #lowerBounds} by {@link #headers}.
+ * <p>
+ * Entries are sorted in descending order by the end of the range they cover, so that
+ * a search of this collection my terminate as soon as it encounters a range that does
+ * not cover the item we are searching for.
+ * <p>
+ * This collection may contain negative values, in which case these point to other
+ * checkpoints, whose <i>direct</i> contents (i.e. the positive values of) we may
+ * search.
+ * <ul> if negative, points to an earlier checkpoint, and:
+ * <li>if the 30th bit is set, the low 20 bits point to checkpointsList,
+ * and the 9 bits in-between provide the length of the range</li>
+ * <li>otherwise, if the 29th bit is set, the lower 29 bits points to checkpointsList,
+ * and can be iterated safely without an endIndex</li>
+ * <li>otherwise, the low 29 bits provide the length of the run, and the low 31 bits
+ * of the following entry (which will also be negative) provide a pointer to
+ * checkpointsList</li>
+ * </ul>
+ */
+ final int[] checkpointLists;
+
+ public final int maxScanAndCheckpointMatches;
+
+ SearchableRangeList(Range[] ranges, int[] lowerBounds, int[] headers, int[] checkpointLists, int maxScanAndCheckpointMatches)
+ {
+ this.ranges = ranges;
+ this.lowerBounds = lowerBounds;
+ this.headers = headers;
+ this.checkpointLists = checkpointLists;
+ this.maxScanAndCheckpointMatches = maxScanAndCheckpointMatches;
+ }
+
+ @Inline
+ public <P1, P2, P3> int forEach(Range range, IndexedTriConsumer<P1, P2, P3> forEachScanOrCheckpoint, IndexedRangeTriConsumer<P1, P2, P3> forEachRange, P1 p1, P2 p2, P3 p3, int minIndex)
+ {
+ if (ranges.length == 0 || minIndex == ranges.length)
+ return minIndex;
+
+ int end = SortedArrays.binarySearch(ranges, minIndex, ranges.length, range.end(), (a, b) -> a.compareTo(b.start()), CEIL);
+ if (end < 0) end = -1 - end;
+ if (end <= minIndex) return minIndex;
+
+ int floor = SortedArrays.binarySearch(ranges, minIndex, ranges.length, range.start(), (a, b) -> a.compareTo(b.start()), CEIL);
+ int start = floor;
+ if (floor < 0)
+ {
+ // if there's no precise match on start, step backwards;
+ // if this range does not overlap us, step forwards again for start
+ // but retain the floor index for performing scan and checkpoint searches from
+ // as this contains all ranges that might overlap us (whereas those that end
+ // after us but before the next range's start would be missed by the next range index)
+ start = floor = -2 - floor;
+ if (start < 0)
+ start = floor = 0;
+ else if (ranges[start].end().compareTo(range.start()) <= 0)
+ ++start;
+ }
+
+ return forEach(start, end, floor, range.start(), forEachScanOrCheckpoint, forEachRange, p1, p2, p3, minIndex);
+ }
+
+ @Inline
+ public <P1, P2, P3> int forEach(Key key, IndexedTriConsumer<P1, P2, P3> forEachScanOrCheckpoint, IndexedRangeTriConsumer<P1, P2, P3> forEachRange, P1 p1, P2 p2, P3 p3, int minIndex)
+ {
+ if (ranges.length == 0 || minIndex == ranges.length)
+ return minIndex;
+
+ int end = SortedArrays.binarySearch(ranges, minIndex, ranges.length, key, (a, b) -> a.compareTo(b.start()), FLOOR);
+ if (end < 0) end = -1 - end;
+ if (end <= minIndex) return minIndex;
+
+ int floor = SortedArrays.binarySearch(ranges, minIndex, ranges.length, key, (a, b) -> a.compareTo(b.start()), CEIL);
+ int start = floor;
+ if (floor < 0)
+ {
+ // if there's no precise match on start, step backwards;
+ // if this range does not overlap us, step forwards again for start
+ // but retain the floor index for performing scan and checkpoint searches from
+ // as this contains all ranges that might overlap us (whereas those that end
+ // after us but before the next range's start would be missed by the next range index)
+ start = floor = -2 - floor;
+ if (start < 0)
+ start = floor = 0;
+ else if (ranges[start].end().compareTo(key) <= 0)
+ ++start;
+ }
+
+ // Key cannot equal RoutingKey, so can ignore inclusivity/exclusivity of end bound
+ return forEach(start, end, floor, key, forEachScanOrCheckpoint, forEachRange, p1, p2, p3, minIndex);
+ }
+
+ @Inline
+ private <P1, P2, P3> int forEach(int start, int end, int floor, RoutableKey startBound,
+ IndexedTriConsumer<P1, P2, P3> forEachScanOrCheckpoint, IndexedRangeTriConsumer<P1, P2, P3> forEachRange,
+ P1 p1, P2 p2, P3 p3, int minIndex)
+ {
+ if (start < minIndex) start = minIndex;
+
+ // find the checkpoint array, so we know how far to step back
+ int checkpoint = Arrays.binarySearch(lowerBounds, floor);
+ if (checkpoint < 0) checkpoint = -2 - checkpoint;
+ if (checkpoint < 0) return end;
+
+ int headerBaseIndex = (checkpoint / 4) * 5;
+ int headerSubIndex = checkpoint & 3;
+ int headerListIndex = headerBaseIndex + 1 + headerSubIndex;
+
+ int scanDistance = (headers[headerBaseIndex] >>> (8 * headerSubIndex)) & 0xff;
+ int checkpointStart = headers[headerListIndex];
+ int checkpointEnd = headers[headerListIndex + (headerSubIndex + 5)/4]; // skip the next header
+
+ if (scanDistance == MAX_SCAN_DISTANCE)
+ {
+ scanDistance = -checkpointLists[checkpointStart++];
+ Invariants.checkState(scanDistance >= MAX_SCAN_DISTANCE);
+ }
+
+ // NOTE: we visit in approximately ascending order, and this is a requirement for correctness of RangeDeps builders
+ // Only the checkpoint is visited in uncertain order, but it is visited entirely, before the scan matches
+ // and the range matches
+ int minScanIndex = Math.max(floor - scanDistance, minIndex);
+ for (int i = checkpointStart; i < checkpointEnd ; ++i)
+ {
+ int ri = checkpointLists[i];
+ if (ri < 0)
+ {
+ int subStart, subEnd;
+ if ((ri & BIT30) != 0)
+ {
+ subStart = ri & 0xfffff;
+ subEnd = subStart + ((ri >>> 20) & 0x1ff);
+ }
+ else if ((ri & BIT29) != 0)
+ {
+ subStart = ri & 0x1fffffff;
+ subEnd = Integer.MAX_VALUE;
+ }
+ else
+ {
+ int length = ri & 0x1fffffff;
+ subStart = checkpointLists[++i];
+ subEnd = subStart + length;
+ }
+
+ for (int j = subStart ; j < subEnd ; ++j)
+ {
+ ri = checkpointLists[j];
+ if (ri < 0)
+ continue;
+
+ if (ranges[ri].end().compareTo(startBound) <= 0)
+ break;
+
+ if (ri >= minIndex && ri < minScanIndex)
+ forEachScanOrCheckpoint.accept(p1, p2, p3, ri);
+ }
+ }
+ else
+ {
+ // if startBound is key, we cannot be equal to it;
+ // if startBound is a Range start, we also cannot be equal to it due to the requirement that
+ // endInclusive() != startInclusive(), so equality really means inequality
+ if (ranges[ri].end().compareTo(startBound) <= 0)
+ break;
+
+ if (ri >= minIndex && ri < minScanIndex)
+ forEachScanOrCheckpoint.accept(p1, p2, p3, ri);
+ }
+ }
+
+ for (int i = minScanIndex; i < floor ; ++i)
+ {
+ if (ranges[i].end().compareTo(startBound) > 0)
+ forEachScanOrCheckpoint.accept(p1, p2, p3, i);
+ }
+
+ forEachRange.accept(p1, p2, p3, start, end);
+ return end;
+ }
+
+ public static SearchableRangeList build(Range[] ranges)
+ {
+ if (ranges.length == 0)
+ return EMPTY_CHECKPOINTS;
+
+ return new SearchableRangeListBuilder(ranges, ACCURATE, LINKS).build();
+ }
+
+ public static SearchableRangeList build(Range[] ranges, int maxScanDistance, Strategy strategy, Links links)
+ {
+ if (ranges.length == 0)
+ return EMPTY_CHECKPOINTS;
+
+ return new SearchableRangeListBuilder(ranges, maxScanDistance, strategy, links).build();
+ }
+}
diff --git a/accord-core/src/main/java/accord/utils/SearchableRangeListBuilder.java b/accord-core/src/main/java/accord/utils/SearchableRangeListBuilder.java
new file mode 100644
index 0000000..4629498
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/SearchableRangeListBuilder.java
@@ -0,0 +1,1077 @@
+package accord.utils;
+
+import accord.api.RoutingKey;
+import accord.primitives.Range;
+import accord.utils.ArrayBuffers.IntBuffers;
+
+import javax.annotation.Nonnull;
+import java.util.Arrays;
+import java.util.Objects;
+import java.util.TreeSet;
+import java.util.stream.Collectors;
+
+import static accord.utils.ArrayBuffers.cachedInts;
+import static accord.utils.SearchableRangeList.MAX_SCAN_DISTANCE;
+import static accord.utils.SearchableRangeListBuilder.Links.LINKS;
+import static accord.utils.SearchableRangeListBuilder.Strategy.ACCURATE;
+import static accord.utils.SortedArrays.Search.CEIL;
+
+/**
+ * Builder for {@link SearchableRangeList}
+ */
+public class SearchableRangeListBuilder
+{
+ public enum Strategy
+ {
+ /**
+ * Do not tenure any ranges that are scannable from the currently in-effect max scan distance.
+ * This means we probably do less work on construction, but that our measure of the match count
+ * at any point is inaccurate, and so our heuristics for when to write checkpoints may be wrong,
+ * leading to more checkpoints than necessary.
+ */
+ FAST,
+
+ /**
+ * Tenure every range covering more than goalScanDistance. Any within max scan distance will also
+ * update the scan distance, so that they will be filtered when a checkpoint is written. But
+ * in the meantime they permit accurate tracking of the number of matches a query can return,
+ * permitting our complexity calculations (that determine when checkpoints should be written, and
+ * what our maximum scan distance should be), to be accurate. This can avoid bouncing between
+ * two extremes, where a low max scan distance tenures and correctly detects a desirable larger scan
+ * distance, which we rollover and this prevents us tenuring and tracking the number of matches, so
+ * that we then pick a low max scan distance (and thereby also write a new checkpoint)
+ */
+ ACCURATE
+ }
+
+ /**
+ * Should we maintain pointers to prior checkpoints that we may reference instead of reserializing
+ * the remaining contents. This is cheap to visit as we stop enumerating as soon as we encounter
+ * an entry that no longer covers us. We use some simple heuristics when deciding whether to do
+ * this, namely that there are at least two entries (so we save one checkpoint entry) and that
+ * there is at least one direct entry for each indirect/link entry in the range we will link.
+ */
+ public enum Links
+ {
+ LINKS,
+ NO_LINKS
+ }
+
+ private static final int BIT31 = 0x80000000;
+ private static final int BIT30 = 0x40000000;
+ private static final int BIT29 = 0x20000000;
+ static final int MIN_INDIRECT_LINK_LENGTH = 2;
+
+ final boolean isAccurate;
+ final boolean withLinks;
+ final Range[] ranges;
+
+ int[] bounds;
+ int[] headers;
+ int[] lists;
+ int checkpointCount, headerPointer, listCount;
+
+ final Scan scan = new Scan();
+ final TenuredSet tenured = new TenuredSet();
+ final PendingCheckpoint pending = new PendingCheckpoint();
+
+ // track the maximum possible number of entries we can match with both a scan + checkpoint lookup
+ // this is an over-estimate and may be used by consumers to allocate out-of-order buffers for visitations
+ int maxScanAndCheckpointMatches;
+
+ public SearchableRangeListBuilder(Range[] ranges, Strategy strategy, Links links)
+ {
+ this(ranges, Math.min(MAX_SCAN_DISTANCE, 34 - Integer.numberOfLeadingZeros(ranges.length)), strategy, links);
+ }
+
+ public SearchableRangeListBuilder(Range[] ranges, int goalScanDistance, Strategy strategy, Links links)
+ {
+ this.isAccurate = strategy == ACCURATE;
+ this.withLinks = links == LINKS;
+ Invariants.checkArgument(goalScanDistance <= MAX_SCAN_DISTANCE);
+ Invariants.checkArgument(goalScanDistance > 0);
+ this.ranges = ranges;
+ init(ranges, goalScanDistance);
+ }
+
+ void init(Range[] ranges, int goalScanDistance)
+ {
+ // we write checkpoints at least goalScanDistance apart
+ scan.init(goalScanDistance);
+ IntBuffers cachedInts = cachedInts();
+ // ask for int buffers in descending order of size
+ this.lists = cachedInts.getInts(ranges.length); // this one might need to grow
+ // +2 to round-up each division, and +2 to account for the final entry (which might require an empty scan distance header)
+ this.headers = cachedInts.getInts(((ranges.length / goalScanDistance) * 5) / 4 + 4);
+ this.bounds = cachedInts.getInts(ranges.length / goalScanDistance + 1);
+ }
+
+ /**
+ * Walk over each range, looking ahead by {@link #maxScanDistance} to decide if a range should
+ * be tenured (written to a checkpoint) or scanned; the maximum scan distance is determined by the
+ * number of open tenured entries, i.e. the minimum number of results we can expect to be returned
+ * (or, if greater, the logarithm of the number of ranges in the collection).
+ * <p>
+ * Once we encounter a range that should be tenured, either write a checkpoint immediately
+ * or make a note of the position we must scan to from the last entry in this checkpoint
+ * and wait until it is permitted to write a checkpoint. This range will be tenured either
+ * way for the following checkpoint.
+ * <p>
+ * The only reason not to write a checkpoint immediately is in the case we would breach
+ * our linear space complexity limit, which is imposed by ensuring we have a space between
+ * checkpoints at least as large as the number of entries written to the last checkpoint,
+ * discounted by the number of entries we have removed from the tenured collection since
+ * the last checkpoint.
+ */
+ public SearchableRangeList build()
+ {
+ for (int ri = 0 ; ri < ranges.length ; ++ri)
+ {
+ // write a checkpoint if we meet our linear space complexity requirements
+ // and we either have a tenured range that we must scan,
+ // or the scan distance is now much larger than the minimum number of search results
+ if (shouldWriteCheckpoint(ri))
+ writeCheckpoint(ri);
+
+ // either tenure or update scan distance, potentially writing a checkpoint
+ tenureOrScan(ri);
+ tenured.untenure(ri);
+ }
+
+ // write our final pending checkpoint
+ writeCheckpoint(ranges.length);
+ closeHeaders();
+
+ IntBuffers cachedInts = cachedInts();
+ int[] lists = cachedInts.completeAndDiscard(this.lists, listCount);
+ int[] headers = cachedInts.completeAndDiscard(this.headers, headerPointer);
+ int[] bounds = cachedInts.completeAndDiscard(this.bounds, checkpointCount);
+ return new SearchableRangeList(ranges, bounds, headers, lists, maxScanAndCheckpointMatches);
+ }
+
+ /**
+ * Categorise the candidateIdx as either scannable, and if so update the scan distance;
+ * or unscannable, in which case add it to the {@link #tenured} collection.
+ * Note, that in ACCURATE mode we tenure the item if it is outside of the goalScanDistance
+ * so we may track O(k) accurately above the O(lg2(N)) search and default scan distance,
+ * but we still update the scan distance so that the checkpoint will exclude this entry.
+ */
+ private void tenureOrScan(int index)
+ {
+ Invariants.checkArgument(index >= 0);
+
+ // then either migrate the index to pendingTenured, or ensure it will be scanned
+ RoutingKey end = ranges[index].end();
+ int scanLimit = scanLimit(index, isAccurate ? scan.goal : maxScanDistance());
+ if (shouldTenure(end, scanLimit))
+ {
+ int lastIndex = tenured.tenure(end, index, ranges, scanLimit + 1);
+ if (lastIndex - index > maxScanDistance()) scan.tenured(index);
+ else if (!isAccurate) throw new IllegalStateException();
+ else scan.updateScanDistance(index, lastIndex - index, this);
+ }
+ else
+ {
+ // TODO (low priority, efficiency): if the prior checkpoint has a scan distance >= this one,
+ // and <= 50% more than this one and there's no scanMustReachIndex nor tenuredRanges, don't
+ // write a new checkpoint (perhaps split shouldWriteCheckpoint logic in two)
+ scan.update(end, index, ranges, scanLimit, this);
+ }
+ }
+
+ /**
+ * We are forbidden from writing a checkpoint nearer than this to a prior checkpoint.
+ * This imposes our linear space complexity bounds, while not harming our O(log2(N) + K)
+ * complexity bounds, as we guarantee minimumSpan is never more than the number of query
+ * results.
+ */
+ private int minimumSpan()
+ {
+ return Math.max(scan.goal(), tenured.minimumSpan());
+ }
+
+ private int maxScanDistance()
+ {
+ // minimumSpan() reduces overtime, but there is no reason to reduce our scan distance
+ // for tenuring below the scan distance we will write
+ return Math.max(scan.watermark(), minimumSpan());
+ }
+
+ /**
+ * The index after the last index we can scan from {@code atIndex} with at most {@code maxScanDistance}.
+ */
+ private int scanLimit(int atIndex, int maxScanDistance)
+ {
+ return Math.min(1 + atIndex + maxScanDistance, ranges.length);
+ }
+
+ private boolean shouldTenure(RoutingKey end, int scanLimit)
+ {
+ return scanLimit < ranges.length && end.compareTo(ranges[scanLimit].start()) > 0;
+ }
+
+ private boolean canWriteCheckpoint(int atIndex)
+ {
+ return atIndex - pending.atIndex >= minimumSpan();
+ }
+
+ private boolean shouldWriteCheckpoint(int atIndex)
+ {
+ if (!canWriteCheckpoint(atIndex))
+ return false;
+
+ // TODO (desired, efficiency): consider these triggers
+ if (scan.mustCheckpointToScanTenured(atIndex, maxScanDistance()))
+ return true;
+
+ if (scan.hasMaybeDivergedFromMatchSize(tenured))
+ return true;
+
+ return false;
+ }
+
+ /**
+ * Write a checkpoint for ranges[prevCheckpointIndex...ri)
+ *
+ * 1) Finalise the scan distance
+ * 2) Write the header
+ * 3) Filter the pending tenured ranges to remove those we can scan
+ * 4) Write this list out
+ * 5) Setup a link to this list, if it is large enough
+ * 6) Rollover the scan, tenured and pending structures for the new pending checkpoint
+ */
+ private void writeCheckpoint(int nextCheckpointIndex)
+ {
+ int lastIndex = nextCheckpointIndex - 1;
+ int scanDistance = scan.finalise(lastIndex);
+ scanDistance = extendScanDistance(lastIndex, scanDistance);
+
+ if (pending.atIndex < 0)
+ {
+ // we don't have any checkpoints pending, so don't try to finalise it
+ // but if the new checkpoint doesn't cover index 0, insert a new empty
+ // checkpoint for the scan distance
+ if (nextCheckpointIndex > 0)
+ {
+ // setup an initial empty checkpoint to store the first scan distance
+ maxScanAndCheckpointMatches = scanDistance;
+ writeHeader(scanDistance, 0);
+ }
+ }
+ else
+ {
+ writeHeader(scanDistance, pending.atIndex);
+ int maxCheckpointMatchCount = pending.filter(scanDistance, lastIndex);
+ int listIndex = writeList(pending);
+ if (withLinks)
+ pending.setupLinkChain(tenured, listIndex, listCount);
+ maxScanAndCheckpointMatches = Math.max(maxScanAndCheckpointMatches, scanDistance + maxCheckpointMatchCount);
+ }
+
+ savePendingCheckpointAndResetScanDistance(nextCheckpointIndex);
+ }
+
+ private void savePendingCheckpointAndResetScanDistance(int checkpointIndex)
+ {
+ // use the tail of checkpointListBuf to buffer ranges we plan to tenure
+ ensureCapacity(tenured.count() + scan.watermark());
+
+ scan.reset();
+
+ if (isAccurate)
+ {
+ // TODO (low priority, efficiency): we can shift back the existing scanDistance if it's far enough from
+ // the next checkpoint. this might permit us to skip some comparisons
+ scan.resetPeakMax(tenured);
+ for (Tenured tenured : this.tenured)
+ {
+ int distanceToEnd = (tenured.lastIndex - checkpointIndex);
+ if (distanceToEnd >= scan.peakMax)
+ break;
+
+ int scanDistance = tenured.lastIndex - tenured.index;
+ if (scanDistance <= scan.peakMax)
+ scan.updateScanDistance(tenured.index, scanDistance, null);
+ }
+
+ if (scan.watermark() < scan.goal)
+ {
+ int ri = Scan.minScanIndex(checkpointIndex, scan.goal);
+ while (ri < checkpointIndex)
+ {
+ RoutingKey end = ranges[ri].end();
+ int scanLimit = scanLimit(ri, scan.peakMax);
+ if (!shouldTenure(end, scanLimit))
+ scan.update(end, ri, ranges, scanLimit, null);
+ ++ri;
+ }
+ }
+ }
+ else
+ {
+ // the maximum scan distance that could ever have been adopted for last chunk
+ int oldPeakMax = scan.peakMax();
+ // the minimum scan distance we will start with for processing the proceeding ranges
+ // note: this may increase if we decide to tenure additional ranges, at which point it will be the actual newPeakMax
+ int newMinPeakMax = scan.newPeakMax(tenured);
+ int minUntenuredIndex = scan.minUntenuredIndex(checkpointIndex, tenured);
+ int minScanIndex = Scan.minScanIndex(checkpointIndex, newMinPeakMax);
+
+ // we now make sure tenured and scan are correct for the new parameters.
+ // 1) if our peakMax is lower then we need to go back and find items to tenure that we previously marked for scanning
+ // 2) we must also reset our scan distances
+
+ // since our peakMax is determined by tenured.count(), but we are tenuring items here we keep things simple
+ // and do not account for those items we tenure but would later permit to scan as our peakMax grows
+
+ int ri = Math.min(minUntenuredIndex, minScanIndex);
+ while (ri < checkpointIndex)
+ {
+ RoutingKey end = ranges[ri].end();
+ int newPeakMax = scan.newPeakMax(tenured);
+ int scanLimit = scanLimit(ri, newPeakMax);
+ if (shouldTenure(end, scanLimit))
+ {
+ // note: might have already been tenured
+ // in this case our untenureLimit may be incorrect, but we won't use it
+ if (ri >= minUntenuredIndex && newPeakMax < oldPeakMax)
+ tenured.tenure(end, ri, ranges, scanLimit + 1, scanLimit(ri, oldPeakMax));
+ }
+ else
+ {
+ // this might effectively remove a previously tenured item
+ scan.update(end, ri, ranges, scanLimit, null);
+ }
+ ++ri;
+ }
+
+ scan.resetPeakMax(tenured);
+ }
+
+ pending.atIndex = checkpointIndex;
+ pending.clear();
+ tenured.rollover(pending);
+ }
+
+ private int extendScanDistance(int lastIndex, int scanDistance)
+ {
+ // now we've established our lower bound on scan distance, see how many checkpoints we can remove
+ // by increasing our scan distance so that it remains proportional to the number of results returned
+ // TODO (low priority, efficiency): can reduce cost here by using scanDistances array for upper bounds to scan distance
+ int maxScanDistance = scan.goal() + 2 * Math.min(tenured.count(), tenured.countAtPrevCheckpoint());
+ if (maxScanDistance >= 1 + scanDistance + scanDistance/4 && pending.count() >= (maxScanDistance - scanDistance)/2)
+ {
+ int removeCount = 0;
+ int extendedScanDistance = scanDistance;
+ int target = (maxScanDistance - scanDistance)/2;
+ for (int i = 0 ; i < pending.count() ; ++i)
+ {
+ Tenured t = pending.get(i);
+ if (t.index < 0)
+ continue;
+
+ int distance = Math.min(lastIndex, t.lastIndex) - t.index;
+ if (distance <= scanDistance)
+ continue; // already scanned or untenured
+
+ if (distance <= maxScanDistance)
+ {
+ ++removeCount;
+ extendedScanDistance = Math.max(extendedScanDistance, distance);
+ if (extendedScanDistance == maxScanDistance && removeCount >= target)
+ break;
+ }
+ }
+
+ // TODO (low priority, efficiency): should perhaps also gate this decision on the span we're covering
+ // algorithmically, however, so long as we are under maxScanDistance we are fine
+ if (removeCount >= (extendedScanDistance - scanDistance)/2)
+ scanDistance = extendedScanDistance;
+ }
+ return scanDistance;
+ }
+
+ int writeList(PendingCheckpoint pending)
+ {
+ int startIndex = listCount;
+ for (int i = pending.count() - 1 ; i >= 0 ; --i)
+ {
+ Tenured t = pending.get(i);
+ if (t.index >= 0)
+ {
+ lists[listCount++] = t.index;
+ }
+ else
+ {
+ int index = t.index & ~BIT31;
+ int length = t.linkLength & ~BIT31;
+ if (length <= 0xff && index <= 0xfffff)
+ {
+ lists[listCount++] = BIT31 | BIT30 | (length << 20) | index;
+ }
+ else if (t.linkLength >= 0 && length < BIT30)
+ {
+ lists[listCount++] = BIT31 | BIT29 | index;
+ }
+ else
+ {
+ lists[listCount++] = BIT31 | length;
+ lists[listCount++] = BIT31 | pending.count();
+ }
+ }
+ }
+ return startIndex;
+ }
+
+ void writeHeader(int scanDistance, int lowerBound)
+ {
+ int headerScanDistance = Math.min(scanDistance, MAX_SCAN_DISTANCE);
+
+ if ((checkpointCount & 3) == 0)
+ headers[headerPointer++] = headerScanDistance;
+ else
+ headers[headerPointer - (1 + (checkpointCount & 3))] |= headerScanDistance << (8 * (checkpointCount & 3));
+
+ bounds[checkpointCount++] = lowerBound;
+ headers[headerPointer++] = listCount;
+
+ if (scanDistance >= MAX_SCAN_DISTANCE)
+ lists[listCount++] = -scanDistance; // serialize as a negative value so we ignore it in most cases automatically
+ }
+
+ void closeHeaders()
+ {
+ // write our final checkpoint header
+ if ((checkpointCount & 3) == 0) headers[headerPointer++] = 0;
+ headers[headerPointer++] = listCount;
+ }
+
+ void ensureCapacity(int maxPendingSize)
+ {
+ if (listCount + maxPendingSize >= lists.length)
+ lists = cachedInts().resize(lists, listCount, lists.length + lists.length/2 + maxPendingSize);
+ }
+
+ static class Scan
+ {
+ /** the scan distance we are aiming for; should be proportional to log2(N) */
+ int goal;
+
+ /** the indexes at which we increased the scan distance, and the new scan distance */
+ int[] distances = new int[16];
+ /** the number of unique scan distances we have adopted since the last checkpoint */
+ int count;
+ /** the highest scan distance we have adopted (==scanDistance(scanDistanceCount-1)) */
+ int watermark;
+ /**
+ * the first index we have tenured a range from, but for which we did not immediately write a new checkpoint
+ * we *must* scan at least from the last index in the checkpoint to here
+ */
+ int scanTenuredAtIndex = -1;
+
+ /** The maximum (i.e. initial) scan distance limit we have used since the last attempted checkpoint write */
+ int peakMax;
+
+ void init(int goalScanDistance)
+ {
+ goal = peakMax = goalScanDistance;
+ }
+
+ private void update(RoutingKey end, int atIndex, Range[] ranges, int scanLimit, SearchableRangeListBuilder checkpoint)
+ {
+ int newScanDistance = find(end, atIndex, ranges, scanLimit, watermark);
+ updateScanDistance(atIndex, newScanDistance, checkpoint);
+ }
+
+ private void updateScanDistance(int atIndex, int newScanDistance, SearchableRangeListBuilder checkpoint)
+ {
+ if (newScanDistance > watermark)
+ {
+ // TODO (desired, efficiency): we don't mind slight increases to the watermark;
+ // should really look at scan distance history and ensure we haven't e.g. doubled since
+ // some earlier point (and should track the match count + scan distance at each bump
+ // to check overall work hasn't increased too much)
+ if (checkpoint != null && checkpoint.canWriteCheckpoint(atIndex))
+ checkpoint.writeCheckpoint(atIndex);
+
+ watermark = newScanDistance;
+ if (count * 2 == distances.length)
+ distances = Arrays.copyOf(distances, distances.length * 2);
+ distances[count * 2] = newScanDistance;
+ distances[count * 2 + 1] = atIndex;
+ ++count;
+ }
+ }
+
+ private int find(RoutingKey end, int atIndex, Range[] ranges, int scanLimit, int currentScanDistance)
+ {
+ int lowerIndex = SortedArrays.exponentialSearch(ranges, atIndex + currentScanDistance, scanLimit, end, (e, s) -> e.compareTo(s.start()), CEIL);
+ if (lowerIndex < 0) lowerIndex = -2 - lowerIndex;
+ else lowerIndex -= 1;
+ return lowerIndex - atIndex;
+ }
+
+ boolean isAboveGoal()
+ {
+ return watermark > goal;
+ }
+
+ int watermark()
+ {
+ return watermark;
+ }
+
+ int goal()
+ {
+ return goal;
+ }
+
+ int distanceToTenured(int lastIndex)
+ {
+ return scanTenuredAtIndex >= 0 ? lastIndex - scanTenuredAtIndex : 0;
+ }
+
+ boolean mustCheckpointToScanTenured(int checkpointIndex, int maxScanDistance)
+ {
+ return scanTenuredAtIndex >= 0 && checkpointIndex - scanTenuredAtIndex >= maxScanDistance;
+ }
+
+ /**
+ * Are we scanning a much longer distance than the minimum number of matches we know a query will return?
+ * Note: with Strategy.FAST, {@code tenured.count()} gets less accurate as scan distance increases, so this
+ * will bounce around triggering checkpoints due to the larger scan distance, resetting the scan distance
+ * and starting again
+ */
+ boolean hasMaybeDivergedFromMatchSize(TenuredSet tenured)
+ {
+ return isAboveGoal() && tenured.count() < watermark()/2;
+ }
+
+ private int distance(int i)
+ {
+ return distances[i*2];
+ }
+
+ private int index(int i)
+ {
+ return distances[i*2+1];
+ }
+
+ int finalise(int lastIndex)
+ {
+ Invariants.checkState(distanceToTenured(lastIndex) <= Math.max(watermark(), peakMax()));
+
+ int scanDistance = watermark;
+ // then, compute the minimum scan distance implied by any tenured ranges we did not immediately
+ // write a checkpoint for - we *must* scan back as far as this record
+ int minScanDistance = scanTenuredAtIndex >= 0 ? lastIndex - scanTenuredAtIndex : 0;
+ if (minScanDistance > scanDistance)
+ {
+ // if this minimum is larger than the largest scan distance we picked up for non-tenured ranges
+ // then we are done, as there's nothing we can save
+ scanDistance = minScanDistance;
+ }
+ else if (scanDistance > 0)
+ {
+ // otherwise, we can look to see if any of the scan distances we computed overflow the checkpoint,
+ // i.e. where no records served by this checkpoint need to scan the full distance to reach it
+ int distanceToLastScanIndex = lastIndex - index(count -1);
+ // if the distance to the last scan index is larger than its scan distance, we have overflowed;
+ if (distanceToLastScanIndex < scanDistance)
+ {
+ minScanDistance = Math.max(distanceToLastScanIndex, minScanDistance);
+ // loop until we find one that doesn't overflow, as this is another minimum scan distance
+ int i = count - 1;
+ while (--i >= 0)
+ {
+ int distance = lastIndex - index(i);
+ if (distance >= distance(i)) break;
+ else if (distance > minScanDistance) minScanDistance = distance;
+ }
+ if (i >= 0) scanDistance = Math.max(minScanDistance, distance(i));
+ else scanDistance = minScanDistance;
+ }
+ }
+
+ return scanDistance;
+ }
+
+ void reset()
+ {
+ // we could in theory reset our scan distance using the contents of scanDistance[]
+ // but it's a bit complicated, as we want to have the first item to increment the scan distance
+ // so that we can use it in writeScanDistance to shrink the scan distance;
+ // jumping straight to the highest scan distance breaks this
+ count = 0;
+ scanTenuredAtIndex = -1;
+ watermark = 0;
+ }
+
+ void resetPeakMax(TenuredSet tenured)
+ {
+ peakMax = newPeakMax(tenured);
+ }
+
+ int peakMax()
+ {
+ return peakMax;
+ }
+
+ int newPeakMax(TenuredSet tenured)
+ {
+ return Math.max(goal, tenured.count());
+ }
+
+ /**
+ * The minimum index containing a range that might need to be tenured, if we have a smaller max scan distance than before
+ */
+ int minUntenuredIndex(int checkpointIndex, TenuredSet tenured)
+ {
+ int minUntenuredIndex = Math.max(0, (checkpointIndex - 1) - watermark());
+ // the maximum scan distance that cxould ever have been adopted for the ranges processed since last checkpoint
+ int oldPeakMax = peakMax;
+ int newMinPeakMax = newPeakMax(tenured);
+ if (newMinPeakMax < oldPeakMax)
+ {
+ // minimise range we unnecessarily re-tenure over
+ // TODO (low priority, efficiency): see if can also use to reduce range we re-scan e.g. can recycle
+ // scanDistances contents if we know we won't need to step back further at next checkpoint
+ for (int i = count - 1; i >= 0 ; --i)
+ {
+ if (index(i) <= minUntenuredIndex)
+ break;
+ if (distance(i) <= newMinPeakMax)
+ return i + 1 == count ? index(i) : index(i + 1) - 1;
+ }
+ }
+ return minUntenuredIndex;
+ }
+
+ /**
+ * Record that a range at this index has been tenured, so that we can track how far back
+ * we need to scan to determine how long we can defer writing a new checkpoint while still
+ * being able to scan it.
+ *
+ * TODO (low priority, efficiency): when a checkpoint is written, we should consider moving it
+ * earlier if the scan distance is increased primarily because of this index, and the tenured
+ * collection is otherwise unchanged (so can be written with minimal overhead)
+ */
+ void tenured(int atIndex)
+ {
+ if (scanTenuredAtIndex < 0)
+ scanTenuredAtIndex = atIndex;
+ }
+
+ static int minScanIndex(int checkpointIndex, int scanDistance)
+ {
+ return Math.max(0, (checkpointIndex - 1) - scanDistance);
+ }
+
+ @Override
+ public String toString()
+ {
+ return "Scan{watermark=" + watermark + ", tenured=" + scanTenuredAtIndex + '}';
+ }
+ }
+
+ /**
+ * Record-keeping for a range we have decided is not scannable
+ */
+ static class Tenured implements Comparable<Tenured>
+ {
+ /**
+ * The end of the tenured range covered by the contents referred to be {@link #index}
+ */
+ RoutingKey end;
+
+ /**
+ * <ul>
+ * <li>If positive, this points to {@code ranges[index]}</li>
+ * <li>If negative, this points to an entry in {@link #lists};
+ * see {@link SearchableRangeList#checkpointLists}</li>
+ * </ul>
+ */
+ int index;
+
+ /**
+ * The last index in {@link #ranges} covered by this tenured range
+ */
+ int lastIndex;
+
+ /**
+ * set when this record is serialized in a checkpoint list to either:
+ * <ul>
+ * <li>point to itself, in which case no action should be
+ * taken on removal (it is only retained for size bookkeeping); or</li>
+ * <li>point to the next item in the checkpoint list; the first
+ * such element removed triggers the clearing of the checkpoint
+ * list so that its entries are re-inserted in the next checkpoint</li>
+ * </ul>
+ */
+ Tenured next;
+
+ /**
+ * Only set for link entries, i.e. where {@code index < 0}.
+ * <ul>
+ * <li>if positive, the length is optional as we will terminate safely using the end bound filtering</li>
+ * <li>if negative, the low 31 bits <b>must</b> be retrieved as the length for safe iteration</li>
+ * </ul>
+ */
+ int linkLength;
+
+ Tenured(RoutingKey end, int index)
+ {
+ this.end = end;
+ this.index = index;
+ }
+
+ @Override
+ public int compareTo(@Nonnull Tenured that)
+ {
+ int c = this.end.compareTo(that.end);
+ // we sort indexes in reverse order so later tenured items find the earlier ones with same end when searching
+ // for higher entries for the range of indexes to search, and
+ if (c == 0) c = -Integer.compare(this.index, that.index);
+ return c;
+ }
+
+ @Override
+ public String toString()
+ {
+ return "Tenured{end=" + end + ", index=" + index + '}';
+ }
+ }
+
+ /**
+ * The set of ranges that we intend to write to checkpoints that remain open at the current point in the iteration
+ * This collection may be filtered before serialization, but every member will be visited either by scanning
+ * or visiting the checkpoint list
+ * TODO (low priority, efficiency): save garbage by using an insertion-sorted array for collections where
+ * this is sufficient. later, introduce a mutable b-tree supporting object recycling. we would also like
+ * to use a collection that permits us to insert and return a finger into the tree so we can find the
+ * successor as part of insertion, and that permits constant-time first() calls
+ */
+ static class TenuredSet extends TreeSet<Tenured>
+ {
+ /**
+ * the number of direct tenured entries (i.e. ignoring link entries)
+ * this is used to provide a minimum bound on the number of results a range query can return
+ * note: with Strategy.FAST this gets less accurate as the span distance increases
+ */
+ int directCount;
+ int directCountAtPrevCheckpoint;
+ int minSpan;
+
+ // a stack of recently used EndAndIndex objects - used only for the duration of a single build
+ Tenured reuse, pendingReuse, pendingReuseTail;
+
+ int count()
+ {
+ return directCount;
+ }
+
+ int countAtPrevCheckpoint()
+ {
+ return directCountAtPrevCheckpoint;
+ }
+
+ /**
+ * We require a checkpoint to cover a distance at least as large as the number of tenured ranges leftover
+ * since the prior checkpoint, to ensure these require at most linear additional space, while not requiring
+ * more than O(k) additional complexity on search (i.e., we will scan a number of elements at most equal
+ * to the number we have to visit in the checkpoint).
+ *
+ * We achieve this by recording the minimum number of match results as of the prior checkpoint (i.e. {@link #count()})
+ * and discounting it by one each time we untenure a range, so that for each tenured range from the prior checkpoint
+ * we have either untenured a range or processed at least one additional input.
+ */
+ int minimumSpan()
+ {
+ return minSpan;
+ }
+
+ private int tenure(RoutingKey end, int index, Range[] ranges, int minUntenureIndex)
+ {
+ return tenure(newTenured(end, index), ranges, minUntenureIndex, ranges.length);
+ }
+
+ private void tenure(RoutingKey end, int index, Range[] ranges, int minUntenureIndex, int untenureLimit)
+ {
+ tenure(newTenured(end, index), ranges, minUntenureIndex, untenureLimit);
+ }
+
+ private int tenure(Tenured tenure, Range[] ranges, int untenureMinIndex, int untenureLimit)
+ {
+ if (!add(tenure))
+ return tenure.lastIndex;
+
+ Tenured next = higher(tenure);
+ if (next != null)
+ untenureLimit = Math.min(untenureLimit, next.lastIndex + 1);
+ int untenureIndex = SortedArrays.binarySearch(ranges, untenureMinIndex, untenureLimit, tenure.end, (e, s) -> e.compareTo(s.start()), CEIL);
+ if (untenureIndex < 0) untenureIndex = -1 - untenureIndex;
+ tenure.lastIndex = untenureIndex - 1;
+ Invariants.checkState(tenure.end.compareTo(ranges[tenure.lastIndex].start()) > 0);
+ Invariants.checkState(tenure.lastIndex + 1 == ranges.length || tenure.end.compareTo(ranges[tenure.lastIndex + 1].start()) <= 0);
+ ++directCount;
+ return untenureIndex - 1;
+ }
+
+ private Tenured newTenured(RoutingKey end, int index)
+ {
+ Tenured result = reuse;
+ if (result == null)
+ return new Tenured(end, index);
+
+ reuse = result.next;
+ result.end = end;
+ result.index = index;
+ result.lastIndex = 0;
+ result.next = null;
+ return result;
+ }
+
+ private Tenured addLinkEntry(RoutingKey end, int index, int lastIndex, int length)
+ {
+ Invariants.checkArgument(index < 0);
+ Tenured result = newTenured(end, index);
+ result.linkLength = length;
+ result.lastIndex = lastIndex;
+ add(result);
+ return result;
+ }
+
+ /**
+ * Retire any active tenured ranges that no longer cover the pointer into ranges;
+ * if this crosses our checkpoint threshold, write a new checkpoint.
+ */
+ void untenure(int index)
+ {
+ while (!isEmpty() && first().lastIndex < index)
+ {
+ Tenured removed = pollFirst();
+
+ // if removed.next == null, this is not referenced by a link
+ // if removed.next == removed, it is referenced by a link but does not modify the link on removal
+ if (removed.next != null && removed.next != removed)
+ {
+ // this is a member of a link's chain, which may serve one of two purposes:
+ // 1) it may be the entry nominated to invalidate the link, due to the link
+ // membership shrinking below the required threshold; in which case we
+ // must clear the chain to reactivate its members for insertion into the
+ // next checkpoint, and remove the chain link itself
+ // 2) it may be nominated as an entry to update the chain link info, to make
+ // it more succinct: if every entry of the chain remains active, and there
+ // are *many* entries then we need two integers to represent the chain, but
+ // as soon as any entry is invalid we can rely on this entry to terminate
+ // iteration, so we update the bookkeeping on the first entry we remove in
+ // this case
+
+ // first clear the chain starting at the removed entry
+ Tenured prev = removed, next = removed.next;
+ while (next.next != null)
+ {
+ prev = next;
+ next = next.next;
+ prev.next = null;
+ }
+ Invariants.checkState(next.index < 0);
+ if (prev.end == next.end)
+ {
+ // if this is the last entry in the link, the link is expired and should be removed/reused
+ remove(next);
+ if (pendingReuseTail == null)
+ pendingReuseTail = next;
+ next.next = pendingReuse;
+ pendingReuse = next;
+ }
+ else if (next.linkLength < 0)
+ {
+ // otherwise, flag the link as safely consumed without knowing the length
+ next.linkLength = next.linkLength & Integer.MAX_VALUE;
+ }
+ }
+
+ // this was not a link reference; update our bookkeeping and save it for reuse
+ Invariants.checkState(removed.index >= 0);
+ --directCount;
+ --minSpan;
+ if (pendingReuseTail == null)
+ pendingReuseTail = removed;
+ removed.next = pendingReuse;
+ pendingReuse = removed;
+ }
+ }
+
+ /**
+ * Write out any direct entries that are not pointed to by a chain entry, and any chain entries;
+ * rollover any per-checkpoint data and free up for reuse discarded Tenured objects
+ */
+ void rollover(PendingCheckpoint pending)
+ {
+ for (Tenured tenured : this)
+ {
+ if (tenured.next == null)
+ pending.add(tenured);
+ }
+ // make freed Tenured objects available for reuse
+ if (pendingReuse != null)
+ {
+ pendingReuseTail.next = reuse;
+ reuse = pendingReuse;
+ pendingReuseTail = pendingReuse = null;
+ }
+ directCountAtPrevCheckpoint = minSpan = directCount;
+ }
+ }
+
+ /**
+ * we write checkpoints out before knowing the scan distance needed for the range, as a checkpoint precedes
+ * the ranges it covers; so we record the position and contents of the checkpoint, and once the scan distance is
+ * known (i.e. when the next checkpoint is written) we re-process the list to remove items we can now scan before
+ * serializing to checkpointListsBuf.
+ */
+ static class PendingCheckpoint
+ {
+ int atIndex = -1;
+ int count;
+
+ Tenured[] contents = new Tenured[10];
+
+ int openDirectCount, firstOpenDirect, openIndirectCount;
+ boolean hasClosedDirect;
+
+ int count()
+ {
+ return count;
+ }
+
+ Tenured get(int i)
+ {
+ return contents[i];
+ }
+
+ void add(Tenured tenured)
+ {
+ if (contents.length == count)
+ contents = Arrays.copyOf(contents, 2 * contents.length);
+ contents[count++] = tenured;
+ }
+
+ void clear()
+ {
+ count = 0;
+ }
+
+ /**
+ * Remove pending entries that will be scanned by the scanDistance, and update
+ * our bookkeeping for creating links
+ */
+ int filter(int scanDistance, int lastIndex)
+ {
+ int matchCountModifier = 0;
+ int maxi = count;
+ count = 0;
+ openDirectCount = 0;
+ openIndirectCount = 0;
+ firstOpenDirect = -1;
+// lastClosedDirect = -1;
+
+ for (int i = 0; i < maxi ; ++i)
+ {
+ Tenured t = get(i);
+ if (t.index >= 0)
+ {
+ if (t.index + scanDistance >= lastIndex)
+ continue; // last index will find it with a scan
+
+ if (t.lastIndex <= t.index + scanDistance)
+ continue; // all indexes will find it with a scan
+
+ if (t.lastIndex > lastIndex)
+ {
+ // this range remains open for the next checkpoint;
+ // we may want to reference this list from there
+ // so track count and position of first one to make a determination
+ ++openDirectCount;
+ if (firstOpenDirect < 0) firstOpenDirect = count;
+ }
+ else hasClosedDirect = true;
+ }
+ else
+ {
+ // note: we over count here, as we count pointers within the chain
+ matchCountModifier += (t.linkLength & Integer.MAX_VALUE) - 1; // (subtract 1 to discount the pointer)
+ if (t.lastIndex > lastIndex)
+ ++openIndirectCount;
+ }
+
+ if (i == count) ++count;
+ else contents[count++] = t;
+ }
+
+ return count + matchCountModifier;
+ }
+
+ /**
+ * Setup a link for referencing this chain later, if permitted.
+ * Must have at least two items, and at least as many direct records as indirect
+ */
+ void setupLinkChain(TenuredSet tenured, int startIndex, int endIndex)
+ {
+ int minSizeToReference = openIndirectCount + MIN_INDIRECT_LINK_LENGTH;
+ if (openDirectCount >= minSizeToReference)
+ {
+ int i = firstOpenDirect;
+ Tenured prev = get(i++);
+
+ while (openDirectCount > minSizeToReference)
+ {
+ Tenured e = get(i++);
+ if (e.index < 0)
+ {
+ --minSizeToReference;
+ continue;
+ }
+
+ Invariants.checkState(prev.next == null);
+ prev.next = prev;
+ prev = e;
+ --openDirectCount;
+ }
+
+ while (i < count)
+ {
+ Tenured next = get(i++);
+ if (next.index < 0)
+ continue;
+
+ Invariants.checkState(prev.next == null);
+ prev.next = next;
+ prev = next;
+ }
+
+ // may be more than one entry per item (though usually not)
+ int length = endIndex - startIndex;
+ Tenured chainEntry = tenured.addLinkEntry(prev.end, BIT31 | startIndex, prev.lastIndex, length);
+ prev.next = chainEntry;
+ if (hasClosedDirect && (startIndex > 0xfffff || (length > 0xff)))
+ {
+ // TODO (expected, testing): make sure this is tested, as not a common code path (may never be executed in normal operation)
+ // we have no closed ranges so iteration needs to know the end bound, but we cannot encode our bounds cheaply
+ // so link the first bound to the chain entry, so that on removal it triggers an update of endIndex to note
+ // that it can be iterated safely without an end bound
+ get(firstOpenDirect).next = chainEntry;
+ }
+ }
+ }
+
+ @Override
+ public String toString()
+ {
+ return Arrays.stream(contents, 0, count)
+ .map(Objects::toString)
+ .collect(Collectors.joining(",", "[", "]"));
+ }
+ }
+}
diff --git a/accord-core/src/main/java/accord/utils/SortedArrays.java b/accord-core/src/main/java/accord/utils/SortedArrays.java
index 542f8e2..85c49c7 100644
--- a/accord-core/src/main/java/accord/utils/SortedArrays.java
+++ b/accord-core/src/main/java/accord/utils/SortedArrays.java
@@ -29,7 +29,13 @@ import net.nicoulaj.compilecommand.annotations.Inline;
import javax.annotation.Nullable;
import static accord.utils.ArrayBuffers.uncached;
+import static accord.utils.SortedArrays.Search.FAST;
+// TODO (low priority, efficiency): improvements:
+// - Either by manually duplicating or using compiler inlining directives to
+// - compile separate versions for Comparators vs Comparable.compareTo
+// - compile dedicated binarySearch and exponentialSearch functions for FLOOR, CEIL, HIGHER, LOWER
+// - Exploit exponentialSearch in union/intersection/etc
public class SortedArrays
{
/**
@@ -71,6 +77,11 @@ public class SortedArrays
* and it would not be much costlier.
*/
public static <T extends Comparable<? super T>> T[] linearUnion(T[] left, int leftLength, T[] right, int rightLength, ObjectBuffers<T> buffers)
+ {
+ return linearUnion(left, leftLength, right, rightLength, Comparable::compareTo, buffers);
+ }
+
+ public static <T> T[] linearUnion(T[] left, int leftLength, T[] right, int rightLength, AsymmetricComparator<? super T, ? super T> comparator, ObjectBuffers<T> buffers)
{
int leftIdx = 0;
int rightIdx = 0;
@@ -86,7 +97,7 @@ public class SortedArrays
{
T leftKey = left[leftIdx];
T rightKey = right[rightIdx];
- int cmp = leftKey == rightKey ? 0 : leftKey.compareTo(rightKey);
+ int cmp = leftKey == rightKey ? 0 : comparator.compare(leftKey, rightKey);
if (cmp <= 0)
{
@@ -119,7 +130,7 @@ public class SortedArrays
{
T leftKey = left[leftIdx];
T rightKey = right[rightIdx];
- int cmp = leftKey == rightKey ? 0 : leftKey.compareTo(rightKey);
+ int cmp = leftKey == rightKey ? 0 : comparator.compare(leftKey, rightKey);
if (cmp >= 0)
{
@@ -153,7 +164,7 @@ public class SortedArrays
{
T leftKey = left[leftIdx];
T rightKey = right[rightIdx];
- int cmp = leftKey == rightKey ? 0 : leftKey.compareTo(rightKey);
+ int cmp = leftKey == rightKey ? 0 : comparator.compare(leftKey, rightKey);
T minKey;
if (cmp == 0)
@@ -220,7 +231,7 @@ public class SortedArrays
*
* TODO (low priority, efficiency): introduce exponential search optimised version
*/
- public static <T> T[] linearIntersection(T[] left, int leftLength, T[] right, int rightLength, Comparator<T> comparator, ObjectBuffers<T> buffers)
+ public static <T> T[] linearIntersection(T[] left, int leftLength, T[] right, int rightLength, AsymmetricComparator<? super T, ? super T> comparator, ObjectBuffers<T> buffers)
{
int leftIdx = 0;
int rightIdx = 0;
@@ -544,7 +555,7 @@ public class SortedArrays
*/
public static <T1, T2 extends Comparable<? super T1>> int exponentialSearch(T1[] in, int from, int to, T2 find)
{
- return exponentialSearch(in, from, to, find, Comparable::compareTo, Search.FAST);
+ return exponentialSearch(in, from, to, find, Comparable::compareTo, FAST);
}
public enum Search
@@ -736,6 +747,7 @@ public class SortedArrays
* Given two sorted arrays where an item in each array may match at most one in the other, find the next
* index in each array containing an equal item.
*/
+ @Inline
public static <T extends Comparable<? super T>> long findNextIntersection(T[] as, int ai, T[] bs, int bi)
{
return findNextIntersection(as, ai, as.length, bs, bi, bs.length);
@@ -745,18 +757,30 @@ public class SortedArrays
* Given two sorted arrays where an item in each array may match at most one in the other, find the next
* index in each array containing an equal item.
*/
+ @Inline
public static <T extends Comparable<? super T>> long findNextIntersection(T[] as, int ai, int alim, T[] bs, int bi, int blim)
{
- return findNextIntersection(as, ai, alim, bs, bi, blim, Comparable::compareTo, Comparable::compareTo, Search.FAST);
+ return findNextIntersection(as, ai, alim, bs, bi, blim, Comparable::compareTo, Comparable::compareTo, FAST);
+ }
+
+ /**
+ * Given two sorted arrays where an item in each array may match at most one in the other, find the next
+ * index in each array containing an equal item.
+ */
+ @Inline
+ public static <T> long findNextIntersection(T[] as, int ai, int alim, T[] bs, int bi, int blim, AsymmetricComparator<? super T, ? super T> comparator)
+ {
+ return findNextIntersection(as, ai, alim, bs, bi, blim, comparator, comparator, FAST);
}
/**
* Given two sorted arrays where an item in each array may match at most one in the other, find the next
* index in each array containing an equal item.
*/
+ @Inline
public static <T> long findNextIntersection(T[] as, int ai, T[] bs, int bi, AsymmetricComparator<T, T> comparator)
{
- return findNextIntersection(as, ai, as.length, bs, bi, bs.length, comparator, comparator, Search.FAST);
+ return findNextIntersection(as, ai, as.length, bs, bi, bs.length, comparator, comparator, FAST);
}
/**
@@ -765,7 +789,8 @@ public class SortedArrays
* Works with CEIL or FAST; FAST to be used if precisely one match for each item in either list, CEIL if one item
* in either list may be matched to multiple in the other list.
*/
- private static <T1, T2> long findNextIntersection(T1[] as, int ai, int asLength, T2[] bs, int bi, int bsLength, AsymmetricComparator<T1, T2> cmp1, AsymmetricComparator<T2, T1> cmp2, Search op)
+ @Inline
+ private static <T1, T2> long findNextIntersection(T1[] as, int ai, int asLength, T2[] bs, int bi, int bsLength, AsymmetricComparator<? super T1, ? super T2> cmp1, AsymmetricComparator<? super T2, ? super T1> cmp2, Search op)
{
if (ai == asLength)
return -1;
@@ -808,6 +833,13 @@ public class SortedArrays
@Nullable
public static <T extends Comparable<? super T>> int[] remapToSuperset(T[] src, int srcLength, T[] trg, int trgLength,
IntBufferAllocator allocator)
+ {
+ return remapToSuperset(src, srcLength, trg, trgLength, Comparable::compareTo, allocator);
+ }
+
+ @Nullable
+ public static <T> int[] remapToSuperset(T[] src, int srcLength, T[] trg, int trgLength, AsymmetricComparator<? super T, ? super T> comparator,
+ IntBufferAllocator allocator)
{
if (src == trg || trgLength == srcLength)
return null;
@@ -819,7 +851,7 @@ public class SortedArrays
{
if (src[i] != trg[j] && !src[i].equals(trg[j]))
{
- j = SortedArrays.exponentialSearch(trg, j, trgLength, src[i]);
+ j = SortedArrays.exponentialSearch(trg, j, trgLength, src[i], comparator, FAST);
if (j < 0)
{
if (i > 0 && src[i] == src[i-1])
@@ -845,10 +877,16 @@ public class SortedArrays
*/
@Inline
public static <T extends Comparable<? super T>> long foldlIntersection(T[] as, int ai, int alim, T[] bs, int bi, int blim, IndexedFoldIntersectToLong<? super T> fold, long param, long initialValue, long terminalValue)
+ {
+ return foldlIntersection(Comparable::compareTo, as, ai, alim, bs, bi, blim, fold, param, initialValue, terminalValue);
+ }
+
+ @Inline
+ public static <T> long foldlIntersection(AsymmetricComparator<? super T, ? super T> comparator, T[] as, int ai, int alim, T[] bs, int bi, int blim, IndexedFoldIntersectToLong<? super T> fold, long param, long initialValue, long terminalValue)
{
while (true)
{
- long abi = findNextIntersection(as, ai, alim, bs, bi, blim);
+ long abi = findNextIntersection(as, ai, alim, bs, bi, blim, comparator);
if (abi < 0)
break;
@@ -865,4 +903,43 @@ public class SortedArrays
return initialValue;
}
+
+ public static <T extends Comparable<T>> void assertSorted(T[] array)
+ {
+ if (!isSorted(array))
+ throw new IllegalArgumentException(Arrays.toString(array) + " is not sorted");
+ }
+
+ public static <T extends Comparable<T>> boolean isSorted(T[] array)
+ {
+ return isSorted(array, Comparable::compareTo);
+ }
+
+ public static <T> boolean isSorted(T[] array, Comparator<T> comparator)
+ {
+ return isSorted(array, comparator, 1);
+ }
+
+
+ public static <T extends Comparable<T>> boolean isSortedUnique(T[] array)
+ {
+ return isSortedUnique(array, Comparable::compareTo);
+ }
+
+ public static <T> boolean isSortedUnique(T[] array, Comparator<T> comparator)
+ {
+ return isSorted(array, comparator, 0);
+ }
+
+ private static <T> boolean isSorted(T[] array, Comparator<T> comparator, int compareTo)
+ {
+ for (int i = 1 ; i < array.length ; ++i)
+ {
+ if (comparator.compare(array[i - 1], array[i]) >= compareTo)
+ return false;
+ }
+ return true;
+ }
+
+
}
diff --git a/accord-core/src/main/java/accord/utils/SymmetricComparator.java b/accord-core/src/main/java/accord/utils/SymmetricComparator.java
new file mode 100644
index 0000000..ff66ca6
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/SymmetricComparator.java
@@ -0,0 +1,7 @@
+package accord.utils;
+
+import java.util.Comparator;
+
+public interface SymmetricComparator<T> extends AsymmetricComparator<T, T>, Comparator<T>
+{
+}
diff --git a/accord-core/src/test/java/accord/coordinate/CoordinateTest.java b/accord-core/src/test/java/accord/coordinate/CoordinateTest.java
index 8017b21..08471f6 100644
--- a/accord-core/src/test/java/accord/coordinate/CoordinateTest.java
+++ b/accord-core/src/test/java/accord/coordinate/CoordinateTest.java
@@ -22,10 +22,7 @@ import accord.local.Node;
import accord.impl.mock.MockCluster;
import accord.api.Result;
import accord.impl.mock.MockStore;
-import accord.primitives.Keys;
-import accord.primitives.FullKeyRoute;
-import accord.primitives.Txn;
-import accord.primitives.TxnId;
+import accord.primitives.*;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
diff --git a/accord-core/src/test/java/accord/messages/PreAcceptTest.java b/accord-core/src/test/java/accord/messages/PreAcceptTest.java
index f1f1117..6619555 100644
--- a/accord-core/src/test/java/accord/messages/PreAcceptTest.java
+++ b/accord-core/src/test/java/accord/messages/PreAcceptTest.java
@@ -109,7 +109,8 @@ public class PreAcceptTest
messageSink.assertHistorySizes(0, 1);
Assertions.assertEquals(ID2, messageSink.responses.get(0).to);
- Assertions.assertEquals(new PreAccept.PreAcceptOk(txnId, txnId, PartialDeps.NONE),
+ PartialDeps expectedDeps = new PartialDeps(Ranges.of(range(0, 12)), KeyDeps.NONE, RangeDeps.NONE);
+ Assertions.assertEquals(new PreAccept.PreAcceptOk(txnId, txnId, expectedDeps),
messageSink.responses.get(0).payload);
}
finally
@@ -168,7 +169,7 @@ public class PreAcceptTest
messageSink.assertHistorySizes(0, 1);
Assertions.assertEquals(ID3, messageSink.responses.get(0).to);
- PartialDeps expectedDeps = Deps.NONE.slice(ranges(range(0, 12)));
+ PartialDeps expectedDeps = new PartialDeps(Ranges.of(range(0, 12)), KeyDeps.NONE, RangeDeps.NONE);
Assertions.assertEquals(new PreAccept.PreAcceptOk(txnId2, Timestamp.fromValues(1, 110, ID1), expectedDeps),
messageSink.responses.get(0).payload);
}
@@ -199,7 +200,7 @@ public class PreAcceptTest
messageSink.assertHistorySizes(0, 1);
Assertions.assertEquals(ID2, messageSink.responses.get(0).to);
- PartialDeps expectedDeps = PartialDeps.NONE;
+ PartialDeps expectedDeps = new PartialDeps(Ranges.of(range(0, 12)), KeyDeps.NONE, RangeDeps.NONE);
Assertions.assertEquals(new PreAccept.PreAcceptOk(txnId, txnId, expectedDeps),
messageSink.responses.get(0).payload);
}
@@ -237,7 +238,8 @@ public class PreAcceptTest
messageSink.assertHistorySizes(0, 1);
Assertions.assertEquals(ID2, messageSink.responses.get(0).to);
- Assertions.assertEquals(new PreAccept.PreAcceptOk(txnId, Timestamp.fromValues(2, 110, ID1), Deps.NONE.slice(ranges(range(0, 12)))),
+ PartialDeps expectedDeps = new PartialDeps(Ranges.of(range(0, 12)), KeyDeps.NONE, RangeDeps.NONE);
+ Assertions.assertEquals(new PreAccept.PreAcceptOk(txnId, Timestamp.fromValues(2, 110, ID1), expectedDeps),
messageSink.responses.get(0).payload);
}
finally
diff --git a/accord-core/src/test/java/accord/txn/DepsTest.java b/accord-core/src/test/java/accord/primitives/KeyDepsTest.java
similarity index 83%
rename from accord-core/src/test/java/accord/txn/DepsTest.java
rename to accord-core/src/test/java/accord/primitives/KeyDepsTest.java
index 9c480ad..c490041 100644
--- a/accord-core/src/test/java/accord/txn/DepsTest.java
+++ b/accord-core/src/test/java/accord/primitives/KeyDepsTest.java
@@ -16,30 +16,24 @@
* limitations under the License.
*/
-package accord.txn;
-
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.List;
-import java.util.Map;
-import java.util.Random;
-import java.util.Set;
-import java.util.TreeMap;
-import java.util.TreeSet;
+package accord.primitives;
+
+import java.util.*;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.BiConsumer;
+import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.IntStream;
import accord.impl.IntHashKey.Hash;
-import accord.primitives.*;
-import accord.primitives.Deps.OrderedBuilder;
+import accord.primitives.KeyDeps.Builder;
import accord.utils.Gen;
import accord.utils.Gens;
+import accord.utils.RelationMultiMap.Entry;
import com.google.common.collect.Sets;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
@@ -50,7 +44,6 @@ import org.slf4j.LoggerFactory;
import accord.api.Key;
import accord.impl.IntHashKey;
import accord.local.Node.Id;
-import accord.primitives.Deps.Entry;
import static accord.utils.Gens.lists;
import static accord.utils.Property.qt;
@@ -58,9 +51,9 @@ import static accord.utils.Utils.toArray;
// TODO (expected, testing): test Keys with no contents, "without", "with" where TxnId and Keys are the same, but Key -> [TxnId] does not match;
// ensure high code coverage
-public class DepsTest
+public class KeyDepsTest
{
- private static final Logger logger = LoggerFactory.getLogger(DepsTest.class);
+ private static final Logger logger = LoggerFactory.getLogger(KeyDepsTest.class);
@Test
public void testRandom()
@@ -87,7 +80,7 @@ public class DepsTest
List<Deps> deps = new ArrayList<>(count);
while (count-- > 0)
deps.add(supplier.get());
- testOneDeps(random, DepsTest.Deps.merge(deps), 200);
+ testOneDeps(random, KeyDepsTest.Deps.merge(deps), 200);
}
@Test
@@ -118,12 +111,12 @@ public class DepsTest
// no matches
Assertions.assertSame(deps.test, deps.test.without(ignore -> false));
// all match
- Assertions.assertSame(accord.primitives.Deps.NONE, deps.test.without(ignore -> true));
+ Assertions.assertSame(accord.primitives.KeyDeps.NONE, deps.test.without(ignore -> true));
// remove specific TxnId
for (TxnId txnId : deps.test.txnIds())
{
- accord.primitives.Deps without = deps.test.without(i -> i.equals(txnId));
+ accord.primitives.KeyDeps without = deps.test.without(i -> i.equals(txnId));
// Was the TxnId removed?
List<TxnId> expectedTxnId = new ArrayList<>(deps.test.txnIds());
expectedTxnId.remove(txnId);
@@ -150,7 +143,7 @@ public class DepsTest
});
}
- private static List<TxnId> get(accord.primitives.Deps deps, Key key)
+ private static List<TxnId> get(accord.primitives.KeyDeps deps, Key key)
{
List<TxnId> ids = new ArrayList<>();
deps.forEach(key, ids::add);
@@ -161,7 +154,7 @@ public class DepsTest
public void testIterator()
{
qt().forAll(Deps::generate).check(deps -> {
- try (OrderedBuilder builder = accord.primitives.Deps.orderedBuilder(true))
+ try (Builder builder = accord.primitives.KeyDeps.builder())
{
for (Map.Entry<Key, TxnId> e : deps.test)
builder.add(e.getKey(), e.getValue());
@@ -181,7 +174,7 @@ public class DepsTest
throw new AssertionError(start + " == " + end);
TreeSet<TxnId> seen = new TreeSet<>();
- deps.test.forEachOn(Ranges.of(Range.range(start.toUnseekable(), end.toUnseekable(), false, true)), txnId -> {
+ deps.test.forEachUniqueTxnId(Ranges.of(Range.range(start.toUnseekable(), end.toUnseekable(), false, true)), txnId -> {
if (!seen.add(txnId))
throw new AssertionError("Seen " + txnId + " multiple times");
});
@@ -205,7 +198,7 @@ public class DepsTest
Key end = keys.get(keys.size() - 1);
TreeSet<TxnId> seen = new TreeSet<>();
- deps.test.forEachOn(Ranges.of(Range.range(start.toUnseekable(), end.toUnseekable(), true, false)), txnId -> {
+ deps.test.forEachUniqueTxnId(Ranges.of(Range.range(start.toUnseekable(), end.toUnseekable(), true, false)), txnId -> {
if (!seen.add(txnId))
throw new AssertionError("Seen " + txnId + " multiple times");
});
@@ -229,7 +222,7 @@ public class DepsTest
Key end = keys.get(0);
TreeSet<TxnId> seen = new TreeSet<>();
- deps.test.forEachOn(Ranges.of(Range.range(start.toUnseekable(), end.toUnseekable(), true, false)), txnId -> {
+ deps.test.forEachUniqueTxnId(Ranges.of(Range.range(start.toUnseekable(), end.toUnseekable(), true, false)), txnId -> {
if (!seen.add(txnId))
throw new AssertionError("Seen " + txnId + " multiple times");
});
@@ -240,14 +233,14 @@ public class DepsTest
@Test
public void testMergeFull()
{
- qt().forAll(lists(Deps::generate).ofSizeBetween(0, 20)).check(DepsTest::testMergedProperty);
+ qt().forAll(lists(Deps::generate).ofSizeBetween(0, 20)).check(KeyDepsTest::testMergedProperty);
}
@Test
public void testMergeFullConcurrent()
{
// pure=false due to shared buffer pool
- Runnable test = () -> qt().withPure(false).forAll(lists(Deps::generate).ofSizeBetween(0, 20)).check(DepsTest::testMergedProperty);
+ Runnable test = () -> qt().withPure(false).forAll(lists(Deps::generate).ofSizeBetween(0, 20)).check(KeyDepsTest::testMergedProperty);
int numThreads = Runtime.getRuntime().availableProcessors() * 4;
ExecutorService executor = Executors.newFixedThreadPool(numThreads);
List<Future<?>> futures = new ArrayList<>(numThreads);
@@ -276,33 +269,35 @@ public class DepsTest
expected.testSimpleEquality();
// slightly redundant due to Deps.merge using this method... it is here for completeness
- Assertions.assertEquals(expected.test, accord.primitives.Deps.merge(list, a -> a.test));
- Assertions.assertEquals(expected.test, list.stream().map(a -> a.test).reduce(accord.primitives.Deps.NONE, accord.primitives.Deps::with));
+ Assertions.assertEquals(expected.test, accord.primitives.KeyDeps.merge(list, a -> a.test, Function.identity()));
+ Assertions.assertEquals(expected.test, list.stream().map(a -> a.test).reduce(accord.primitives.KeyDeps.NONE, accord.primitives.KeyDeps::with));
}
@Test
- public void orderedBuilder()
+ public void builder()
{
qt().forAll(Deps::generate, Gens.random()).check((deps, random) -> {
- OrderedBuilder builder = accord.primitives.Deps.orderedBuilder(false);
- for (Key key : deps.canonical.keySet())
+ try (Builder builder = accord.primitives.KeyDeps.builder();)
{
- builder.nextKey(key);
- List<TxnId> ids = new ArrayList<>(deps.canonical.get(key));
- Collections.shuffle(ids, random);
- ids.forEach(builder::add);
- }
+ for (Key key : deps.canonical.keySet())
+ {
+ builder.nextKey(key);
+ List<TxnId> ids = new ArrayList<>(deps.canonical.get(key));
+ Collections.shuffle(ids, random);
+ ids.forEach(builder::add);
+ }
- Assertions.assertEquals(deps.test, builder.build());
+ Assertions.assertEquals(deps.test, builder.build());
+ }
});
}
static class Deps
{
- final Map<Key, Set<TxnId>> canonical;
- final accord.primitives.Deps test;
+ final Map<Key, NavigableSet<TxnId>> canonical;
+ final accord.primitives.KeyDeps test;
- Deps(Map<Key, Set<TxnId>> canonical, accord.primitives.Deps test)
+ Deps(Map<Key, NavigableSet<TxnId>> canonical, accord.primitives.KeyDeps test)
{
this.canonical = canonical;
this.test = test;
@@ -347,7 +342,7 @@ public class DepsTest
txnIds = new ArrayList<>(tmp);
}
- Map<Key, Set<TxnId>> canonical = new TreeMap<>();
+ TreeMap<Key, NavigableSet<TxnId>> canonical = new TreeMap<>();
for (int i = 0 ; i < totalCount ; ++i)
{
Key key = populateKeys.get(random.nextInt(uniqueKeys));
@@ -355,22 +350,24 @@ public class DepsTest
canonical.computeIfAbsent(key, ignore -> new TreeSet<>()).add(txnId);
}
- try (OrderedBuilder builder = accord.primitives.Deps.orderedBuilder(false))
+ boolean inOrderKeys = random.nextBoolean();
+ boolean inOrderValues = random.nextBoolean();
+ try (Builder builder = accord.primitives.KeyDeps.builder())
{
- canonical.forEach((key, ids) -> {
+ (inOrderKeys ? canonical : canonical.descendingMap()).forEach((key, ids) -> {
builder.nextKey(key);
- ids.forEach(builder::add);
+ (inOrderValues ? ids : ids.descendingSet()).forEach(builder::add);
});
- accord.primitives.Deps test = builder.build();
+ accord.primitives.KeyDeps test = builder.build();
return new Deps(canonical, test);
}
}
Deps select(Ranges ranges)
{
- Map<Key, Set<TxnId>> canonical = new TreeMap<>();
- for (Map.Entry<Key, Set<TxnId>> e : this.canonical.entrySet())
+ Map<Key, NavigableSet<TxnId>> canonical = new TreeMap<>();
+ for (Map.Entry<Key, NavigableSet<TxnId>> e : this.canonical.entrySet())
{
if (ranges.contains(e.getKey()))
canonical.put(e.getKey(), e.getValue());
@@ -381,10 +378,10 @@ public class DepsTest
Deps with(Deps that)
{
- Map<Key, Set<TxnId>> canonical = new TreeMap<>();
- for (Map.Entry<Key, Set<TxnId>> e : this.canonical.entrySet())
+ Map<Key, NavigableSet<TxnId>> canonical = new TreeMap<>();
+ for (Map.Entry<Key, NavigableSet<TxnId>> e : this.canonical.entrySet())
canonical.computeIfAbsent(e.getKey(), ignore -> new TreeSet<>()).addAll(e.getValue());
- for (Map.Entry<Key, Set<TxnId>> e : that.canonical.entrySet())
+ for (Map.Entry<Key, NavigableSet<TxnId>> e : that.canonical.entrySet())
canonical.computeIfAbsent(e.getKey(), ignore -> new TreeSet<>()).addAll(e.getValue());
return new Deps(canonical, test.with(that.test));
@@ -393,7 +390,7 @@ public class DepsTest
void testSimpleEquality()
{
Assertions.assertArrayEquals(canonical.keySet().toArray(new Key[0]), ((Keys)test.keys()).stream().toArray(Key[]::new));
- for (Map.Entry<Key, Set<TxnId>> e : canonical.entrySet())
+ for (Map.Entry<Key, NavigableSet<TxnId>> e : canonical.entrySet())
{
List<TxnId> canonical = new ArrayList<>(e.getValue());
List<TxnId> test = new ArrayList<>();
@@ -412,7 +409,7 @@ public class DepsTest
StringBuilder builder = new StringBuilder();
builder.append("{");
- for (Map.Entry<Key, Set<TxnId>> e : canonical.entrySet())
+ for (Map.Entry<Key, NavigableSet<TxnId>> e : canonical.entrySet())
{
if (builder.length() > 1)
builder.append(", ");
@@ -421,13 +418,13 @@ public class DepsTest
builder.append(e.getValue());
}
builder.append("}");
- Assertions.assertEquals(builder.toString(), test.toSimpleString());
+ Assertions.assertEquals(builder.toString(), test.toString());
}
TreeMap<TxnId, List<Key>> invertCanonical()
{
TreeMap<TxnId, List<Key>> result = new TreeMap<>();
- for (Map.Entry<Key, Set<TxnId>> e : canonical.entrySet())
+ for (Map.Entry<Key, NavigableSet<TxnId>> e : canonical.entrySet())
{
e.getValue().forEach(txnId -> result.computeIfAbsent(txnId, ignore -> new ArrayList<>())
.add(e.getKey()));
@@ -438,14 +435,14 @@ public class DepsTest
static Deps merge(List<Deps> deps)
{
- Map<Key, Set<TxnId>> canonical = new TreeMap<>();
+ Map<Key, NavigableSet<TxnId>> canonical = new TreeMap<>();
for (Deps that : deps)
{
- for (Map.Entry<Key, Set<TxnId>> e : that.canonical.entrySet())
+ for (Map.Entry<Key, NavigableSet<TxnId>> e : that.canonical.entrySet())
canonical.computeIfAbsent(e.getKey(), ignore -> new TreeSet<>()).addAll(e.getValue());
}
- return new Deps(canonical, accord.primitives.Deps.merge(deps, d -> d.test));
+ return new Deps(canonical, accord.primitives.KeyDeps.merge(deps, d -> d.test, Function.identity()));
}
}
@@ -474,7 +471,7 @@ public class DepsTest
Random random = random(seed);
int totalCount = 1 + random.nextInt(totalCountRange - 1);
testOneDeps(random,
- DepsTest.Deps.generate(random, uniqueTxnIds, epochRange, hlcRange, 0, nodeRange, uniqueKeys, emptyKeys, keyRange, totalCount),
+ KeyDepsTest.Deps.generate(random, uniqueTxnIds, epochRange, hlcRange, 0, nodeRange, uniqueKeys, emptyKeys, keyRange, totalCount),
keyRange);
}
@@ -483,13 +480,13 @@ public class DepsTest
{
return () -> {
if (random.nextInt(100) == 0)
- return new Deps(new TreeMap<>(), accord.primitives.Deps.NONE);
+ return new Deps(new TreeMap<>(), accord.primitives.KeyDeps.NONE);
int uniqueTxnIds = 1 + random.nextInt(uniqueTxnIdsRange - 1);
int uniqueKeys = 1 + random.nextInt(uniqueKeysRange - 1);
int emptyKeys = 1 + random.nextInt(emptyKeysRange - 1);
int totalCount = random.nextInt(Math.min(totalCountRange, uniqueKeys * uniqueTxnIds));
- return DepsTest.Deps.generate(random, uniqueTxnIds,
+ return KeyDepsTest.Deps.generate(random, uniqueTxnIds,
epochRange, hlcRange, flagRange, nodeRange,
uniqueKeys, emptyKeys, keyRange, totalCount);
};
@@ -500,25 +497,25 @@ public class DepsTest
deps.testSimpleEquality();
{
Deps nestedSelect = null;
- // generate some random KeyRanges, and slice using them
+ // generate some random Ranges, and slice using them
for (int i = 0, count = 1 + random.nextInt(4); i < count ; ++i)
{
Ranges ranges = randomKeyRanges(random, 1 + random.nextInt(5), keyRange);
{ // test forEach(key, txnId)
- List<Entry> canonical = new ArrayList<>();
+ List<Entry<Key, TxnId>> canonical = new ArrayList<>();
for (Key key : deps.canonical.keySet())
{
if (ranges.contains(key))
- deps.canonical.get(key).forEach(txnId -> canonical.add(new Entry(key, txnId)));
+ deps.canonical.get(key).forEach(txnId -> canonical.add(new Entry<>(key, txnId)));
}
- deps.test.forEachOn(ranges, ignore -> true, new BiConsumer<Key, TxnId>()
+ deps.test.forEach(ranges, new BiConsumer<>()
{
int i = 0;
@Override
public void accept(Key key, TxnId txnId)
{
- Entry entry = canonical.get(i);
+ Entry<Key, TxnId> entry = canonical.get(i);
Assertions.assertEquals(entry.getKey(), key);
Assertions.assertEquals(entry.getValue(), txnId);
++i;
@@ -534,7 +531,7 @@ public class DepsTest
if (ranges.contains(key))
canonical.addAll(deps.canonical.get(key));
}
- deps.test.forEachOn(ranges, test::add);
+ deps.test.forEachUniqueTxnId(ranges, test::add);
test.sort(Timestamp::compareTo);
Assertions.assertEquals(new ArrayList<>(canonical), test);
}
diff --git a/accord-core/src/test/java/accord/primitives/RangeDepsTest.java b/accord-core/src/test/java/accord/primitives/RangeDepsTest.java
new file mode 100644
index 0000000..ed62bbf
--- /dev/null
+++ b/accord-core/src/test/java/accord/primitives/RangeDepsTest.java
@@ -0,0 +1,229 @@
+package accord.primitives;
+
+import accord.impl.IntKey;
+import accord.local.Node;
+import accord.primitives.Routable.Domain;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+import java.util.*;
+
+import static accord.primitives.Txn.Kind.Write;
+
+public class RangeDepsTest
+{
+ static class GenerateRanges
+ {
+ final int rangeDomain;
+ final float minRangesDomain, maxRangesDomain, minRangesSpan, maxRangesSpan;
+
+ GenerateRanges(int rangeDomain, float minRangesDomain, float maxRangesDomain, float minRangesSpan, float maxRangesSpan)
+ {
+ this.rangeDomain = rangeDomain;
+ this.minRangesDomain = minRangesDomain;
+ this.maxRangesDomain = maxRangesDomain;
+ this.minRangesSpan = minRangesSpan;
+ this.maxRangesSpan = maxRangesSpan;
+ }
+
+ private Range[] generateRanges(Random random, int rangeCount)
+ {
+ Range[] ranges = new Range[rangeCount];
+ int txnDomain = Math.max(ranges.length, (int) (((random.nextFloat() * (maxRangesDomain - minRangesDomain)) + minRangesDomain) * rangeDomain));
+ int txnSpan = Math.max(txnDomain, (int) (((random.nextFloat() * (maxRangesSpan - minRangesSpan)) + minRangesSpan) * rangeDomain));
+ int gapSpan = txnSpan - txnDomain;
+ int start = rangeDomain == txnSpan ? 0 : random.nextInt(rangeDomain - txnSpan);
+ int end = start + txnSpan;
+ int[] gaps = new int[ranges.length];
+ int[] gapSpans = new int[ranges.length];
+ for (int i = 0 ; i < ranges.length ; ++i)
+ {
+ gaps[i] = start + random.nextInt(end - start);
+ gapSpans[i] = i == ranges.length - 1 || gapSpan <= 1 ? gapSpan : 1 + random.nextInt(Math.max(1, 2 * gapSpan/(ranges.length - i)));
+ }
+ Arrays.sort(gaps);
+ for (int i = 0 ; i < ranges.length ; ++i)
+ {
+ end = Math.max(start + 1, gaps[i]);
+ ranges[i] = r(start, end);
+ start = end + gapSpans[i];
+ }
+ return ranges;
+ }
+ }
+
+ static class Validate
+ {
+ final GenerateRanges generate;
+ final Map<TxnId, Ranges> canonical;
+ final RangeDeps test;
+
+ Validate(GenerateRanges generate, Map<TxnId, Ranges> canonical, RangeDeps test)
+ {
+ this.generate = generate;
+ this.canonical = canonical;
+ this.test = test;
+ }
+
+ Set<TxnId> canonicalOverlaps(Range range)
+ {
+ Set<TxnId> set = new TreeSet<>();
+ for (Map.Entry<TxnId, Ranges> e : canonical.entrySet())
+ {
+ if (e.getValue().intersects(range))
+ set.add(e.getKey());
+ }
+ return set;
+ }
+
+ Set<TxnId> testOverlaps(Range range)
+ {
+ Set<TxnId> set = new TreeSet<>();
+ test.forEachUniqueTxnId(range, set::add);
+ return set;
+ }
+
+ void validate(Random random)
+ {
+ Assertions.assertEquals(canonical.size(), test.txnIdCount());
+ Assertions.assertArrayEquals(canonical.keySet().stream().toArray(TxnId[]::new), test.txnIds);
+ for (int i = 0 ; i < test.rangeCount() ; ++i)
+ {
+ Assertions.assertEquals(canonicalOverlaps(test.range(i)), testOverlaps(test.range(i)));
+ }
+ for (int i = 0 ; i < test.rangeCount() ; ++i)
+ {
+ Range range = generate.generateRanges(random, 1)[0];
+ Assertions.assertEquals(canonicalOverlaps(range), testOverlaps(range));
+ }
+ }
+ }
+
+ private static final boolean EXHAUSTIVE = false;
+
+ // TODO (expected, testing): generate ranges of different sizes at different ratios
+ private static Validate generate(Random random, GenerateRanges generate, int txnIdCount, int rangeCount)
+ {
+ Map<TxnId, Ranges> map = new TreeMap<>();
+ for (int txnId = 0; txnId < txnIdCount ; ++txnId)
+ {
+ int thisRangeCount = txnIdCount == 1 ? rangeCount : 1 + random.nextInt((2 * rangeCount / txnIdCount) - 1);
+ Range[] ranges = generate.generateRanges(random, thisRangeCount);
+ map.put(id(txnId), Ranges.of(ranges));
+ }
+ return new Validate(generate, map, RangeDeps.of(map));
+ }
+
+ private static Validate generateIdenticalTxns(Random random, GenerateRanges generate, int txnIdCount, int rangeCount)
+ {
+ Map<TxnId, Ranges> map = new TreeMap<>();
+ Range[] ranges = generate.generateRanges(random, rangeCount / txnIdCount);
+ for (int txnId = 0; txnId < txnIdCount ; ++txnId)
+ map.put(id(txnId), Ranges.of(ranges));
+ return new Validate(generate, map, RangeDeps.of(map));
+ }
+
+ private static Validate generateNemesisRanges(int width, int nemesisTxnIdCount, int rangeCount, int nonNemesisEntryPerNemesisEntry)
+ {
+ Map<Integer, List<Range>> build = new TreeMap<>();
+ int nonNemesisTxnIdCount = nemesisTxnIdCount * nonNemesisEntryPerNemesisEntry;
+ rangeCount /= (1 + nonNemesisEntryPerNemesisEntry);
+ int rangeDomain = 0;
+ for (int i = 0 ; i < rangeCount ; ++i)
+ {
+ build.computeIfAbsent(i % nemesisTxnIdCount, ignore -> new ArrayList<>()).add(r(i, i + width));
+ for (int j = 0 ; j < nonNemesisEntryPerNemesisEntry ; ++j)
+ build.computeIfAbsent(nemesisTxnIdCount + (i % nonNemesisTxnIdCount), ignore -> new ArrayList<>()).add(r(i, i + 1));
+ rangeDomain = i + width;
+ }
+ Map<TxnId, Ranges> result = new TreeMap<>();
+ for (int txnId = 0; txnId < nemesisTxnIdCount + nonNemesisTxnIdCount ; ++txnId)
+ result.put(id(txnId), Ranges.of(build.get(txnId).toArray(new Range[0])));
+ return new Validate(new GenerateRanges(rangeDomain, 0f, 1f, 0f, 1f), result, RangeDeps.of(result));
+ }
+
+
+ // TODO (now): broaden patterns of random contents, sizes of collection etc.
+ @Test
+ public void testRandom()
+ {
+ Random random = new Random();
+// long[] seeds = new long[]{-6268194734307361517L, -1531261279965735959L};
+// Validate[] validates = new Validate[seeds.length];
+ for (int i = 0 ; i < 1000 ; ++i)
+ {
+ long seed = random.nextLong();
+// long seed = -5637243003494330136L;
+ System.out.println("Seed: " + seed);
+ random.setSeed(seed);
+ generate(random, new GenerateRanges(1000, 0.01f, 0.3f, 0.1f, 1f), 100, 1000)
+ .validate(random);
+ }
+ }
+
+ @Test
+ public void testIdenticalTransactions()
+ {
+ Random random = new Random();
+ for (int copies = 1 ; copies < 500 ; ++copies)
+ {
+ long seed = random.nextLong();
+// long seed = -4951029115911714505L;
+ System.out.println("Seed: " + seed + ", copies: " + copies);
+ random.setSeed(seed);
+ generateIdenticalTxns(random, new GenerateRanges(1000, 0.01f, 0.3f, 0.1f, 1f), copies, 1000)
+ .validate(random);
+ }
+ }
+
+ @Test
+ public void testNemesisRanges()
+ {
+ testNemesisRanges(0);
+ }
+
+ @Test
+ public void testHalfNemesisRanges()
+ {
+ testNemesisRanges(1);
+ }
+
+ private static void testNemesisRanges(int nonNemesisEntryPerNemesisEntry)
+ {
+ Random random = new Random();
+ long seed = random.nextLong();
+ System.out.println("Seed: " + seed);
+ random.setSeed(seed);
+
+ if (EXHAUSTIVE)
+ {
+ for (int width = 1 ; width < 512 ; ++width)
+ {
+ for (int txnIdCount = 1; txnIdCount < 100 ; txnIdCount *= 2)
+ {
+ // TODO (now): verify that we write only a small number of checkpoints
+ generateNemesisRanges(width, txnIdCount, 1000, nonNemesisEntryPerNemesisEntry)
+ .validate(random);
+ }
+ }
+ }
+ else
+ {
+ for (int i = 0 ; i < 1000 ; ++i)
+ {
+ generateNemesisRanges(1 + random.nextInt(511), 1 + random.nextInt(99), 1000, nonNemesisEntryPerNemesisEntry)
+ .validate(random);
+ }
+ }
+ }
+
+ private static TxnId id(int i)
+ {
+ return new TxnId(1, i, Write, Domain.Key, new Node.Id(1));
+ }
+
+ private static Range r(int i, int j)
+ {
+ return new IntKey.Range(new IntKey.Routing(i), new IntKey.Routing(j));
+ }
+}
diff --git a/accord-maelstrom/src/main/java/accord/maelstrom/Json.java b/accord-maelstrom/src/main/java/accord/maelstrom/Json.java
index 98a8345..ba08474 100644
--- a/accord-maelstrom/src/main/java/accord/maelstrom/Json.java
+++ b/accord-maelstrom/src/main/java/accord/maelstrom/Json.java
@@ -21,8 +21,10 @@ package accord.maelstrom;
import java.io.IOException;
import java.util.*;
+import accord.api.RoutingKey;
import accord.local.Node;
import accord.api.Result;
+import accord.primitives.*;
import com.google.gson.Gson;
import com.google.gson.GsonBuilder;
import com.google.gson.TypeAdapter;
@@ -31,13 +33,6 @@ import com.google.gson.stream.JsonToken;
import com.google.gson.stream.JsonWriter;
import accord.local.Node.Id;
import accord.api.Key;
-import accord.primitives.Deps;
-import accord.primitives.Txn;
-import accord.primitives.TxnId;
-import accord.primitives.Writes;
-import accord.primitives.Ballot;
-import accord.primitives.Keys;
-import accord.primitives.Timestamp;
import accord.messages.ReadData.ReadOk;
public class Json
@@ -320,7 +315,7 @@ public class Json
public void write(JsonWriter out, Deps value) throws IOException
{
out.beginArray();
- for (Map.Entry<Key, TxnId> e : value)
+ for (Map.Entry<Key, TxnId> e : value.keyDeps)
{
out.beginArray();
((MaelstromKey)e.getKey()).datum.write(out);
@@ -328,37 +323,53 @@ public class Json
out.endArray();
}
out.endArray();
+ out.beginArray();
+ for (Map.Entry<Range, TxnId> e : value.rangeDeps)
+ {
+ out.beginArray();
+ ((MaelstromKey)e.getKey().start()).datum.write(out);
+ ((MaelstromKey)e.getKey().end()).datum.write(out);
+ GSON.toJson(e.getValue(), TxnId.class, out);
+ out.endArray();
+ }
+ out.endArray();
}
@Override
public Deps read(JsonReader in) throws IOException
{
- in.beginArray();
- if (!in.hasNext())
+ KeyDeps keyDeps;
+ try (KeyDeps.Builder builder = KeyDeps.builder())
{
+ in.beginArray();
+ while (in.hasNext())
+ {
+ in.beginArray();
+ Key key = MaelstromKey.readKey(in);
+ TxnId txnId = GSON.fromJson(in, TxnId.class);
+ builder.add(key, txnId);
+ in.endArray();
+ }
in.endArray();
- return Deps.NONE;
+ keyDeps = builder.build();
}
-
- TreeMap<Key, List<TxnId>> byKey = new TreeMap<>();
- while (in.hasNext())
+ RangeDeps rangeDeps;
+ try (RangeDeps.Builder builder = RangeDeps.builder())
{
in.beginArray();
- Key key = MaelstromKey.readKey(in);
- TxnId txnId = GSON.fromJson(in, TxnId.class);
- byKey.computeIfAbsent(key, ignore -> new ArrayList<>()).add(txnId);
+ while (in.hasNext())
+ {
+ in.beginArray();
+ RoutingKey start = MaelstromKey.readRouting(in);
+ RoutingKey end = MaelstromKey.readRouting(in);
+ TxnId txnId = GSON.fromJson(in, TxnId.class);
+ builder.add(new MaelstromKey.Range(start, end), txnId);
+ in.endArray();
+ }
in.endArray();
+ rangeDeps = builder.build();
}
- in.endArray();
-
- try (Deps.OrderedBuilder builder = Deps.orderedBuilder(true))
- {
- byKey.forEach((key, txnIds) -> {
- builder.nextKey(key);
- txnIds.forEach(builder::add);
- });
- return builder.build();
- }
+ return new Deps(keyDeps, rangeDeps);
}
};
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cassandra.apache.org
For additional commands, e-mail: commits-help@cassandra.apache.org