dcapwell commented on code in PR #50:
URL: https://github.com/apache/cassandra-accord/pull/50#discussion_r1235963901
##########
accord-core/src/main/java/accord/local/Commands.java:
##########
@@ -885,7 +963,7 @@ public void accept(SafeCommandStore safeStore)
if (prev != null)
{
- if (cur.has(until) || (cur.hasBeen(PreCommitted) &&
cur.executeAt().compareTo(prev.executeAt()) > 0))
+ if (cur.has(until) || cur.hasBeen(Truncated) ||
(cur.hasBeen(PreCommitted) && cur.executeAt().compareTo(prev.executeAt()) > 0
&& !prev.txnId().rw().awaitsFutureDeps()))
Review Comment:
with `cur.hasBeen(Truncated)` this now allows `Invalidated` as well, where
as before we would only allow `Invalidated` IFF
`cur.executeAt().compareTo(prev.executeAt()) > 0`, so this is a subtle semantic
change...
##########
accord-core/src/main/java/accord/coordinate/CheckShards.java:
##########
@@ -86,13 +94,27 @@ protected Action process(Id from, CheckStatusReply reply)
CheckStatusOk ok = (CheckStatusOk) reply;
if (merged == null) merged = ok;
else merged = merged.merge(ok);
+ if (merged.truncated)
+ truncated = true;
return checkSufficient(from, ok);
}
else
{
- onFailure(from, new IllegalStateException("Submitted command to a
replica that did not own the range"));
- return Action.Abort;
+ switch ((CheckStatus.CheckStatusNack)reply)
+ {
+ default: throw new AssertionError();
Review Comment:
```suggestion
default: throw new AssertionError(String.format("Unexpected
status: %s", reply));
```
##########
accord-core/src/main/java/accord/local/Commands.java:
##########
@@ -368,36 +413,36 @@ public static void
applyRecipientLocalSyncPoint(SafeCommandStore safeStore, TxnI
}
// TODO (expected, ?): commitInvalidate may need to update cfks _if_
possible
- public static void commitInvalidate(SafeCommandStore safeStore, TxnId
txnId)
+ public static void commitInvalidate(SafeCommandStore safeStore,
SafeCommand safeCommand)
{
- SafeCommand safeCommand = safeStore.command(txnId);
Command command = safeCommand.current();
if (command.hasBeen(PreCommitted))
{
- logger.trace("{}: skipping commit invalidated - already committed
({})", txnId, command.status());
- if (!command.hasBeen(Invalidated))
- safeStore.agent().onInconsistentTimestamp(command,
Timestamp.NONE, command.executeAt());
-
+ if (command.is(Truncated))
+ {
+ logger.trace("{}: skipping commit invalidated - already
truncated ({})", safeCommand.txnId(), command.status());
+ }
+ else
+ {
+ logger.trace("{}: skipping commit invalidated - already
committed ({})", safeCommand.txnId(), command.status());
+ if (!command.is(Invalidated) && !(command.is(Truncated) &&
command.executeAt().equals(Timestamp.NONE)))
+ safeStore.agent().onInconsistentTimestamp(command,
Timestamp.NONE, command.executeAt());
+ }
return;
}
- ProgressShard shard = progressShard(safeStore, command);
- safeStore.progressLog().invalidated(command, shard);
+ safeStore.progressLog().clear(command.txnId());
Review Comment:
not clear why this change yet... we stop tracking in SPL when commit
invalidate happens?
##########
accord-core/src/main/java/accord/local/Commands.java:
##########
@@ -113,29 +114,29 @@ public static boolean owns(SafeCommandStore safeStore,
long epoch, RoutingKey so
return safeStore.ranges().allAt(epoch).contains(someKey);
}
- public static RoutingKey noProgressKey()
- {
- return NO_PROGRESS_KEY;
- }
+ public enum AcceptOutcome { Success, Redundant, RejectedBallot, Truncated }
- public enum AcceptOutcome {Success, Redundant, RejectedBallot}
-
- public static AcceptOutcome preaccept(SafeCommandStore safeStore, TxnId
txnId, long acceptEpoch, PartialTxn partialTxn, Route<?> route, @Nullable
RoutingKey progressKey)
+ public static AcceptOutcome preaccept(SafeCommandStore safeStore,
SafeCommand safeCommand, TxnId txnId, long acceptEpoch, PartialTxn partialTxn,
FullRoute<?> route, @Nullable RoutingKey progressKey)
{
- return preacceptOrRecover(safeStore, txnId, acceptEpoch, partialTxn,
route, progressKey, Ballot.ZERO);
+ return preacceptOrRecover(safeStore, safeCommand, txnId, acceptEpoch,
partialTxn, route, progressKey, Ballot.ZERO);
}
- public static AcceptOutcome recover(SafeCommandStore safeStore, TxnId
txnId, PartialTxn partialTxn, Route<?> route, @Nullable RoutingKey progressKey,
Ballot ballot)
+ public static AcceptOutcome recover(SafeCommandStore safeStore,
SafeCommand safeCommand, TxnId txnId, PartialTxn partialTxn, FullRoute<?>
route, @Nullable RoutingKey progressKey, Ballot ballot)
{
// for recovery we only ever propose either the original epoch or an
Accept that we witness; otherwise we invalidate
- return preacceptOrRecover(safeStore, txnId, txnId.epoch(), partialTxn,
route, progressKey, ballot);
+ return preacceptOrRecover(safeStore, safeCommand, txnId,
txnId.epoch(), partialTxn, route, progressKey, ballot);
}
- private static AcceptOutcome preacceptOrRecover(SafeCommandStore
safeStore, TxnId txnId, long acceptEpoch, PartialTxn partialTxn, Route<?>
route, @Nullable RoutingKey progressKey, Ballot ballot)
+ private static AcceptOutcome preacceptOrRecover(SafeCommandStore
safeStore, SafeCommand safeCommand, TxnId txnId, long acceptEpoch, PartialTxn
partialTxn, FullRoute<?> route, @Nullable RoutingKey progressKey, Ballot ballot)
Review Comment:
if passing in the command do we still want the `txnId`? It *must* belong to
that command right? I feel we should keep `TxnId` or drop it in favor of
`SafeCommand`, but should not mix
##########
accord-core/src/main/java/accord/local/Commands.java:
##########
@@ -444,13 +486,23 @@ public static void listenerUpdate(SafeCommandStore
safeStore, SafeCommand safeLi
{
Command listener = safeListener.current();
Command updated = safeUpdated.current();
+ if (listener.is(NotDefined) || listener.is(Truncated))
+ {
+ // This listener must be a stale vestige
+ // TODO (desired): would be nice to ensure these are deregistered
explicitly, but would be costly
+ Invariants.checkState(listener.saveStatus() == Uninitialised ||
listener.is(Truncated));
Review Comment:
```suggestion
Invariants.checkState(listener.saveStatus() == Uninitialised ||
listener.is(Truncated), "Listener status expected to be Uninitialised or
Truncated, but was %s", listener.saveStatus());
```
##########
accord-core/src/main/java/accord/utils/DeterministicSet.java:
##########
@@ -0,0 +1,179 @@
+/*
+ * 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 java.util.AbstractSet;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+
+import com.google.common.collect.Iterables;
+
+public class DeterministicSet<T> extends AbstractSet<T>
Review Comment:
is this needed when JDK offers `LinkedHashSet` and `LinkedHashMap`? As far
as I can tell, the only diff with this class is `equals` is iteration order,
where as `LinkedHashSet` walks in iterator order, but does a prob (as its
comparing against a map, which might not be ordered)
Best I see is this one comment
```
// LinkedHashSet isn't always suitable, due to
ConcurrentModificationException
public class DeterministicIdentitySet<T> extends DeterministicSet<T>
```
##########
accord-core/src/main/java/accord/utils/ReducingRangeMap.java:
##########
@@ -19,154 +19,163 @@
import accord.api.RoutingKey;
import accord.primitives.*;
-import com.google.common.annotations.VisibleForTesting;
import java.util.function.BiFunction;
import java.util.function.Predicate;
import static accord.utils.SortedArrays.Search.FAST;
+import static accord.utils.SortedArrays.exponentialSearch;
public class ReducingRangeMap<V> extends ReducingIntervalMap<RoutingKey, V>
{
- final RoutingKeys endKeys;
+ public static class SerializerSupport
+ {
+ public static <V> ReducingRangeMap<V> create(boolean inclusiveEnds,
RoutingKey[] ends, V[] values)
+ {
+ return new ReducingRangeMap<>(inclusiveEnds, ends, values);
+ }
+ }
- public ReducingRangeMap(V value)
+ public ReducingRangeMap()
{
- super(value);
- this.endKeys = RoutingKeys.EMPTY;
+ super();
}
- ReducingRangeMap(boolean inclusiveEnds, RoutingKey[] ends, V[] values)
+ protected ReducingRangeMap(boolean inclusiveEnds, RoutingKey[] ends, V[]
values)
{
super(inclusiveEnds, ends, values);
- this.endKeys = RoutingKeys.ofSortedUnique(ends);
}
- public V foldl(Routables<?, ?> routables, BiFunction<V, V, V> fold, V
initialValue)
+ public V foldl(Routables<?> routables, BiFunction<V, V, V> fold, V
accumulator)
+ {
+ return foldl(routables, (a, b, f, ignore) -> f.apply(a, b),
accumulator, fold, null, ignore -> false);
+ }
+
+ public <V2> V2 foldl(Routables<?> routables, BiFunction<V, V2, V2> fold,
V2 accumulator, Predicate<V2> terminate)
+ {
+ return foldl(routables, (a, b, f, ignore) -> f.apply(a, b),
accumulator, fold, null, terminate);
+ }
+
+ public <V2, P1> V2 foldl(Routables<?> routables, TriFunction<V, V2, P1,
V2> fold, V2 accumulator, P1 p1, Predicate<V2> terminate)
{
- return foldl(routables, fold, initialValue, ignore -> false);
+ return foldl(routables, (a, b, f, p) -> f.apply(a, b, p), accumulator,
fold, p1, terminate);
}
- public <V2> V2 foldl(Routables<?, ?> routables, BiFunction<V, V2, V2>
fold, V2 initialValue, Predicate<V2> terminate)
+ public <V2, P1, P2> V2 foldl(Routables<?> routables, QuadFunction<V, V2,
P1, P2, V2> fold, V2 accumulator, P1 p1, P2 p2, Predicate<V2> terminate)
+ {
+ return foldl(routables, (v, v2, param1, param2, i, j) -> fold.apply(v,
v2, param1, param2), accumulator, p1, p2, terminate);
+ }
+
+ public <V2, P1, P2> V2 foldl(Routables<?> routables,
IndexedRangeQuadFunction<V, V2, P1, P2, V2> fold, V2 accumulator, P1 p1, P2 p2,
Predicate<V2> terminate)
{
switch (routables.domain())
{
default: throw new AssertionError();
- case Key: return foldl((AbstractKeys<?, ?>) routables, fold,
initialValue, terminate);
- case Range: return foldl((AbstractRanges<?>) routables, fold,
initialValue, terminate);
+ case Key: return foldl((AbstractKeys<?>) routables, fold,
accumulator, p1, p2, terminate);
+ case Range: return foldl((AbstractRanges<?>) routables, fold,
accumulator, p1, p2, terminate);
}
}
// TODO (required): test
- public <V2> V2 foldl(AbstractKeys<?, ?> keys, BiFunction<V, V2, V2>
reduce, V2 accumulator, Predicate<V2> terminate)
+ public <V2, P1, P2> V2 foldl(AbstractKeys<?> keys,
IndexedRangeQuadFunction<V, V2, P1, P2, V2> fold, V2 accumulator, P1 p1, P2 p2,
Predicate<V2> terminate)
{
- int i = 0, j = 0;
+ if (values.length == 0)
+ return accumulator;
+
+ int i = 0, j = keys.findNext(0, starts[0], FAST);
+ if (j < 0) j = -1 - j;
+ else if (inclusiveEnds) ++j;
+
while (j < keys.size())
{
- i = endKeys.findNext(i, keys.get(j), FAST);
- if (i < 0) i = -1 - i;
- else if (!inclusiveEnds) ++i;
+ i = exponentialSearch(starts, i, starts.length, keys.get(j));
+ if (i < 0) i = -2 - i;
+ else if (inclusiveEnds) --i;
- accumulator = reduce.apply(values[i], accumulator);
- if (terminate.test(accumulator))
+ if (i >= values.length)
return accumulator;
- if (i == endKeys.size())
- return j + 1 == keys.size() ? accumulator :
reduce.apply(values[i], accumulator);
+ int nextj = keys.findNext(j, starts[i + 1], FAST);
+ if (nextj < 0) nextj = -1 -nextj;
+ else if (inclusiveEnds) ++nextj;
- j = keys.findNext(j + 1, endKeys.get(i), FAST);
- if (j < 0) j = -1 - j;
+ if (j != nextj && values[i] != null)
+ {
+ accumulator = fold.apply(values[i], accumulator, p1, p2, j,
nextj);
+ if (terminate.test(accumulator))
+ return accumulator;
+ }
+ ++i;
+ j = nextj;
}
return accumulator;
}
// TODO (required): test
- public <V2> V2 foldl(AbstractRanges<?> ranges, BiFunction<V, V2, V2>
reduce, V2 accumulator, Predicate<V2> terminate)
+ public <V2, P1, P2> V2 foldl(AbstractRanges<?> ranges,
IndexedRangeQuadFunction<V, V2, P1, P2, V2> fold, V2 accumulator, P1 p1, P2 p2,
Predicate<V2> terminate)
Review Comment:
can you fix the TODO by adding the tests?
##########
accord-core/src/main/java/accord/utils/ReducingIntervalMap.java:
##########
@@ -93,35 +99,47 @@ public boolean equals(Object o)
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
ReducingIntervalMap that = (ReducingIntervalMap) o;
- return Arrays.equals(ends, that.ends) && Arrays.equals(values,
that.values);
+ return Arrays.equals(starts, that.starts) && Arrays.equals(values,
that.values);
}
public int hashCode()
{
return Arrays.hashCode(values);
}
+ public boolean inclusiveEnds()
+ {
+ return inclusiveEnds;
+ }
+
public V get(K key)
{
- int idx = Arrays.binarySearch(ends, key);
- if (idx < 0) idx = -1 - idx;
- else if (!inclusiveEnds) ++idx;
+ int idx = find(key);
+ if (idx < 0 || idx >= values.length)
+ return null;
return values[idx];
}
- public V value(int idx)
+ public K startAt(int idx)
+ {
+ if (idx < 0 || idx > size() - 1)
+ throw new IndexOutOfBoundsException();
+ return starts[idx];
+ }
+
+ public V valueAt(int idx)
{
if (idx < 0 || idx > size())
throw new IndexOutOfBoundsException();
return values[idx];
}
- public int indexOf(K key)
+ private int find(K key)
{
- int idx = Arrays.binarySearch(ends, key);
- if (idx < 0) idx = -1 - idx;
- else if (!inclusiveEnds) --idx;
+ int idx = Arrays.binarySearch(starts, key);
+ if (idx < 0) idx = -2 - idx;
+ else if (inclusiveEnds) --idx;
Review Comment:
took a bit to understand this, so wrote a unit test to help see things...
can we add the following test
```
/*
* 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 org.agrona.collections.IntHashSet;
import org.assertj.core.api.Assertions;
import org.junit.jupiter.api.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import static accord.utils.Property.qt;
class ReducingIntervalMapTest
{
@Test
public void multi()
{
qt().forAll(nonOverlappingRanges()).check(ranges -> {
IntBuilder builder = new IntBuilder(ranges.get(0).inclusiveEnds,
ranges.size());
for (Range range : ranges)
{
builder.append(range.start, range.start, (i1, i2) -> i1);
builder.append(range.end, null, (i1, i2) -> {throw new
IllegalStateException("end of range");});
}
ReducingIntervalMap<Integer, Integer> map = builder.build();
for (int i = 0; i < ranges.size(); i++)
{
Range previous = i == 0 ? null : ranges.get(i - 1);
Range range = ranges.get(i);
Range next = i == ranges.size() - 1 ? null : ranges.get(i +
1);
if (previous == null)
Assertions.assertThat(map.get(range.start - 1)).isNull();
if (!range.inclusiveEnds)
Assertions.assertThat(map.get(range.start)).isEqualTo(range.start);
if (range.start + 1 != range.end)
{
long covers = (long) range.end - (long) range.start + 1;
int mid = Math.toIntExact(covers / 2);
int idx = range.start + mid;
Assertions.assertThat(map.get(idx)).describedAs("Unable
to find %d", idx).isEqualTo(range.start);
}
if (range.inclusiveEnds)
Assertions.assertThat(map.get(range.end)).isEqualTo(range.start);
if (next == null)
Assertions.assertThat(map.get(range.end + 1)).isNull();
}
});
}
private static class IntBuilder extends
ReducingIntervalMap.Builder<Integer, Integer, ReducingIntervalMap<Integer,
Integer>>
{
protected IntBuilder(boolean inclusiveEnds, int capacity) {
super(inclusiveEnds, capacity);
}
@Override
protected ReducingIntervalMap<Integer, Integer> buildInternal() {
return new ReducingIntervalMap(inclusiveEnds, starts.toArray(new
Integer[0]), values.toArray(new Integer[0]));
}
}
private static class Range
{
final boolean inclusiveEnds;
final int start, end;
private Range(boolean inclusiveEnds, int start, int end)
{
this.inclusiveEnds = inclusiveEnds;
this.start = start;
this.end = end;
}
@Override
public String toString() {
return "Range{" +
"inclusiveEnds=" + inclusiveEnds +
", start=" + start +
", end=" + end +
'}';
}
}
private static Gen<List<Range>> nonOverlappingRanges()
{
return rand -> {
boolean inclusiveEnds = rand.nextBoolean();
int size = rand.nextInt(1, 10);
IntHashSet unique = new IntHashSet();
int[] ints = new int[size + 1];
for (int i = 0; i < ints.length; i++)
{
int value = rand.nextInt();
while (!unique.add(value))
value = rand.nextInt();
ints[i] = value;
}
Arrays.sort(ints);
List<Range> ranges = new ArrayList<>(size);
for (int i = 0; i < size; i++)
ranges.add(new Range(inclusiveEnds, ints[i], ints[i + 1]));
return ranges;
};
}
}
```
##########
accord-core/src/main/java/accord/utils/SimpleBitSet.java:
##########
@@ -0,0 +1,348 @@
+/*
+ * 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 java.util.Arrays;
+
+import static java.lang.Long.highestOneBit;
+import static java.lang.Long.lowestOneBit;
+import static java.lang.Long.numberOfTrailingZeros;
+
+public class SimpleBitSet
+{
+ public static class SerializationSupport
+ {
+ public static long[] getArray(SimpleBitSet bs)
+ {
+ return bs.bits;
+ }
+
+ public static SimpleBitSet construct(long[] bits)
+ {
+ return new SimpleBitSet(bits);
+ }
+ }
+
+ final long[] bits;
+ int count;
+
+ public SimpleBitSet(int size)
+ {
+ bits = new long[(size + 63)/64];
+ }
+
+ public SimpleBitSet(int size, boolean set)
+ {
+ this(size);
+ if (set)
+ {
+ Arrays.fill(bits, 0, size / 64, -1L);
+ if ((size & 63) != 0)
+ bits[indexOf(size - 1)] = -1L >>> (64 - (size & 63));
+ count = size;
+ }
+ }
+
+ public SimpleBitSet(SimpleBitSet copy)
+ {
+ bits = copy.bits.clone();
+ count = copy.count;
+ }
+
+ SimpleBitSet(long[] bits)
+ {
+ this.bits = bits;
+ for (long v : bits)
+ count += Long.bitCount(v);
+ }
+
+ public boolean set(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 != (bits[index] & bit))
+ return false;
+ bits[index] |= bit;
+ ++count;
+ return true;
+ }
+
+ public void setRange(int from, int to)
+ {
+ if (to <= from)
+ {
+ Invariants.checkArgument(to >= from, "to < from (%s < %s)", to,
from);
+ return;
+ }
+
+ int fromIndex = from >>> 6;
+ int toIndex = (to + 63) >>> 6;
+ if (fromIndex + 1 == toIndex)
+ {
+ long addBits = (-1L >>> (64 - (to & 63))) & (-1L << (from & 63));
+ orBitsAtIndex(fromIndex, addBits);
+ }
+ else if (count == 0)
+ {
+ bits[toIndex - 1] = -1L >>> (64 - (to & 63));
+ for (int i = fromIndex + 1, maxi = toIndex - 1; i < maxi ; ++i)
+ bits[i] = -1L;
+ bits[fromIndex] = -1L << (from & 63);
+ count = to - from;
+ }
+ else
+ {
+ orBitsAtIndex(fromIndex, -1L << (from & 63));
+ for (int i = fromIndex + 1, maxi = toIndex - 1; i < maxi ; ++i)
+ {
+ count += 64 - Long.bitCount(bits[i]);
+ bits[i] = -1L;
+ }
+ orBitsAtIndex(toIndex - 1, -1L >>> (64 - (to & 63)));
+ }
+ }
+
+ private void orBitsAtIndex(int index, long setBits)
+ {
+ long prevBits = bits[index];
+ bits[index] = setBits | prevBits;
+ count += Long.bitCount(setBits) - Long.bitCount(prevBits);
+ }
+
+ public boolean unset(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 == (bits[index] & bit))
+ return false;
+ bits[index] &= ~bit;
+ --count;
+ return true;
+ }
+
+ public boolean get(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ return 0 != (bits[index] & bit);
+ }
+
+ public int size()
+ {
+ return bits.length * 64;
+ }
+
+ public int setBitCount()
+ {
+ return count;
+ }
+
+ public boolean isEmpty()
+ {
+ return count == 0;
+ }
+
+ public int prevSetBit(int i)
+ {
+ if (count == 0)
+ return -1;
+
+ int index = indexOf(i);
+ long bits = this.bits[index] & bitsEqualOrLesser(i);
+ while (true)
+ {
+ if (bits != 0)
+ return index * 64 + numberOfTrailingZeros(highestOneBit(bits));
+
+ if (--index < 0)
+ return -1;
+
+ bits = this.bits[index];
+ }
+ }
+
+ public int prevSetBitNotBefore(int i, int inclBound, int ifNotFound)
+ {
+ if (count == 0)
+ return ifNotFound;
+
+ int index = indexOf(i);
+ int inclIndexBound = lowerLimitOf(inclBound);
+ long bits = this.bits[index] & bitsEqualOrLesser(i);
+ while (true)
+ {
+ if (bits != 0)
+ {
+ int result = index * 64 +
numberOfTrailingZeros(highestOneBit(bits));
+ return result > inclBound ? result : ifNotFound;
+ }
+
+ if (--index < inclIndexBound)
+ return -1;
+
+ bits = this.bits[index];
+ }
+ }
+
+ public int nextSetBit(int i, int ifNotFound)
+ {
+ if (count == 0)
+ return ifNotFound;
+
+ int index = indexOf(i);
+ long bits = this.bits[index] & bitsEqualOrGreater(i);
+ while (true)
+ {
+ if (bits != 0)
+ return index * 64 + numberOfTrailingZeros(lowestOneBit(bits));
+
+ if (++index >= this.bits.length)
+ return ifNotFound;
+
+ bits = this.bits[index];
+ }
+ }
+
+ public int nextSetBitBefore(int i, int exclBound, int ifNotFound)
+ {
+ if (count == 0)
+ return ifNotFound;
+
+ int index = indexOf(i);
+ int exclIndexBound = upperLimitOf(exclBound);
+ long bits = this.bits[index] & bitsEqualOrGreater(i);
+ while (true)
+ {
+ if (bits != 0)
+ {
+ int result = index * 64 +
numberOfTrailingZeros(lowestOneBit(bits));
+ return result < exclBound ? result : ifNotFound;
+ }
+
+ if (++index >= exclIndexBound)
+ return ifNotFound;
+
+ bits = this.bits[index];
+ }
+ }
+
+ public <P1> void forEach(P1 p1, IndexedConsumer<P1> forEach)
+ {
+ forEach(forEach, p1, IndexedConsumer::accept);
+ }
+
+ public <P1, P2> void forEach(P1 p1, P2 p2, IndexedBiConsumer<P1, P2>
forEach)
+ {
+ forEach(forEach, p1, p2, IndexedBiConsumer::accept);
+ }
+
+ public <P1, P2, P3> void forEach(P1 p1, P2 p2, P3 p3,
IndexedTriConsumer<P1, P2, P3> forEach)
+ {
+ forEach(forEach, p1, p2, p3, IndexedTriConsumer::accept);
+ }
+
+ // the bitset is permitted to mutate as we iterate
+ public <P1, P2, P3, P4> void forEach(P1 p1, P2 p2, P3 p3, P4 p4,
IndexedQuadConsumer<P1, P2, P3, P4> forEach)
+ {
+ int i = 0;
+ while (i < bits.length && count > 0)
+ {
+ long mask = -1L;
+ long register;
+ while ((register = (bits[i] & mask)) != 0)
+ {
+ int bitIndex = numberOfTrailingZeros(register);
+ mask = (-1L << bitIndex) << 1;
+ forEach.accept(p1, p2, p3, p4, i * 64 + bitIndex);
+ }
+ ++i;
+ }
+ }
+
+ public <P1> void reverseForEach(IndexedConsumer<P1> forEach, P1 p1)
+ {
+ reverseForEach(forEach, p1, IndexedConsumer::accept);
+ }
+
+ public <P1, P2> void reverseForEach(P1 p1, P2 p2, IndexedBiConsumer<P1,
P2> forEach)
+ {
+ reverseForEach(forEach, p1, p2, IndexedBiConsumer::accept);
+ }
+
+ public <P1, P2, P3> void reverseForEach(P1 p1, P2 p2, P3 p3,
IndexedTriConsumer<P1, P2, P3> forEach)
+ {
+ reverseForEach(forEach, p1, p2, p3, IndexedTriConsumer::accept);
+ }
+
+ // the bitset is permitted to mutate as we iterate
+ public <P1, P2, P3, P4> void reverseForEach(P1 p1, P2 p2, P3 p3, P4 p4,
IndexedQuadConsumer<P1, P2, P3, P4> forEach)
+ {
+ int i = bits.length - 1;
+ while (i >= 0 && count > 0)
+ {
+ long mask = -1L;
+ long register;
+ while ((register = (bits[i] & mask)) != 0)
+ {
+ int bitIndex = 63 - Long.numberOfLeadingZeros(register);
+ mask = (1L << bitIndex) - 1;
+ forEach.accept(p1, p2, p3, p4, i * 64 + bitIndex);
+ }
+ --i;
+ }
+ }
+
+ private int indexOf(int i)
+ {
+ int index = i >>> 6;
+ if (index >= bits.length)
+ throw new IndexOutOfBoundsException();
Review Comment:
```suggestion
throw new IndexOutOfBoundsException(String.format("%d >= %d",
index, bits.length));
```
##########
accord-core/src/main/java/accord/utils/RelationMultiMap.java:
##########
@@ -397,6 +397,76 @@ public void close()
}
}
+ public static class SortedRelationList<T extends Comparable<? super T>>
extends AbstractList<T> implements SortedList<T>
+ {
+ public static final SortedRelationList EMPTY = new
SortedRelationList(new Comparable[0], new int[0], 0, 0);
+
+ final T[] values;
+ final int[] ids;
+ final int startIndex, endIndex;
+
+ public SortedRelationList(T[] values, int[] ids, int startIndex, int
endIndex)
+ {
+ this.values = values;
+ this.ids = ids;
+ this.startIndex = startIndex;
+ this.endIndex = endIndex;
+ }
+
+ @Override
+ public T get(int index)
+ {
+ if (index >= endIndex)
+ throw new IndexOutOfBoundsException();
+ return values[ids[startIndex + index]];
Review Comment:
```suggestion
return values[getValueIndex(index)];
```
##########
accord-core/src/main/java/accord/utils/SimpleBitSet.java:
##########
@@ -0,0 +1,348 @@
+/*
+ * 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 java.util.Arrays;
+
+import static java.lang.Long.highestOneBit;
+import static java.lang.Long.lowestOneBit;
+import static java.lang.Long.numberOfTrailingZeros;
+
+public class SimpleBitSet
+{
+ public static class SerializationSupport
+ {
+ public static long[] getArray(SimpleBitSet bs)
+ {
+ return bs.bits;
+ }
+
+ public static SimpleBitSet construct(long[] bits)
+ {
+ return new SimpleBitSet(bits);
+ }
+ }
+
+ final long[] bits;
+ int count;
+
+ public SimpleBitSet(int size)
+ {
+ bits = new long[(size + 63)/64];
+ }
+
+ public SimpleBitSet(int size, boolean set)
+ {
+ this(size);
+ if (set)
+ {
+ Arrays.fill(bits, 0, size / 64, -1L);
+ if ((size & 63) != 0)
+ bits[indexOf(size - 1)] = -1L >>> (64 - (size & 63));
+ count = size;
+ }
+ }
+
+ public SimpleBitSet(SimpleBitSet copy)
+ {
+ bits = copy.bits.clone();
+ count = copy.count;
+ }
+
+ SimpleBitSet(long[] bits)
+ {
+ this.bits = bits;
+ for (long v : bits)
+ count += Long.bitCount(v);
+ }
+
+ public boolean set(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 != (bits[index] & bit))
+ return false;
+ bits[index] |= bit;
+ ++count;
+ return true;
+ }
+
+ public void setRange(int from, int to)
+ {
+ if (to <= from)
+ {
+ Invariants.checkArgument(to >= from, "to < from (%s < %s)", to,
from);
Review Comment:
if `to <= from` then we check `to >= from`... which means we require `to ==
from`?
```suggestion
Invariants.checkArgument(to == from, "to < from (%s < %s)", to,
from);
```
##########
accord-core/src/main/java/accord/utils/SimpleBitSet.java:
##########
@@ -0,0 +1,348 @@
+/*
+ * 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 java.util.Arrays;
+
+import static java.lang.Long.highestOneBit;
+import static java.lang.Long.lowestOneBit;
+import static java.lang.Long.numberOfTrailingZeros;
+
+public class SimpleBitSet
+{
+ public static class SerializationSupport
+ {
+ public static long[] getArray(SimpleBitSet bs)
+ {
+ return bs.bits;
+ }
+
+ public static SimpleBitSet construct(long[] bits)
+ {
+ return new SimpleBitSet(bits);
+ }
+ }
+
+ final long[] bits;
+ int count;
+
+ public SimpleBitSet(int size)
+ {
+ bits = new long[(size + 63)/64];
+ }
+
+ public SimpleBitSet(int size, boolean set)
+ {
+ this(size);
+ if (set)
+ {
+ Arrays.fill(bits, 0, size / 64, -1L);
+ if ((size & 63) != 0)
+ bits[indexOf(size - 1)] = -1L >>> (64 - (size & 63));
+ count = size;
+ }
+ }
+
+ public SimpleBitSet(SimpleBitSet copy)
+ {
+ bits = copy.bits.clone();
+ count = copy.count;
+ }
+
+ SimpleBitSet(long[] bits)
+ {
+ this.bits = bits;
+ for (long v : bits)
+ count += Long.bitCount(v);
+ }
+
+ public boolean set(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 != (bits[index] & bit))
+ return false;
+ bits[index] |= bit;
+ ++count;
+ return true;
+ }
+
+ public void setRange(int from, int to)
+ {
+ if (to <= from)
+ {
+ Invariants.checkArgument(to >= from, "to < from (%s < %s)", to,
from);
+ return;
+ }
+
+ int fromIndex = from >>> 6;
Review Comment:
```suggestion
int fromIndex = indexOf(from);
```
##########
accord-core/src/main/java/accord/utils/DeterministicSet.java:
##########
@@ -0,0 +1,179 @@
+/*
+ * 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 java.util.AbstractSet;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+
+import com.google.common.collect.Iterables;
+
+public class DeterministicSet<T> extends AbstractSet<T>
Review Comment:
So, if this class is to avoid that exception, it doesn't actually handle
concurrent modifications, which leads to bugs
```
@Test
public void iterationOrder()
{
DeterministicSet<Integer> set = new DeterministicSet<>();
set.add(1);
set.add(2);
set.add(3);
Iterator<Integer> it = set.iterator();
Assertions.assertThat(next(it)).isEqualTo(3);
set.remove(2);
// SHOULD iterator return 2, or should it skip? Concurrent
Modification is hard...
Assertions.assertThat(next(it)).isEqualTo(2);
Assertions.assertThat(next(it)).isEqualTo(1);
}
private static <T> T next(Iterator<T> it)
{
assert it.hasNext();
return it.next();
}
```
this class isn't safe to modify concurrently (even in the same thread), so
rather than detecting that this case happened, we silently corrupt the iterator
```
java.lang.NullPointerException
at accord.utils.DeterministicSet$1.next(DeterministicSet.java:90)
at accord.utils.DeterministicSetTest.next(DeterministicSetTest.java:46)
at
accord.utils.DeterministicSetTest.iterationOrder(DeterministicSetTest.java:40)
```
##########
accord-core/src/main/java/accord/utils/SimpleBitSet.java:
##########
@@ -0,0 +1,348 @@
+/*
+ * 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 java.util.Arrays;
+
+import static java.lang.Long.highestOneBit;
+import static java.lang.Long.lowestOneBit;
+import static java.lang.Long.numberOfTrailingZeros;
+
+public class SimpleBitSet
+{
+ public static class SerializationSupport
+ {
+ public static long[] getArray(SimpleBitSet bs)
+ {
+ return bs.bits;
+ }
+
+ public static SimpleBitSet construct(long[] bits)
+ {
+ return new SimpleBitSet(bits);
+ }
+ }
+
+ final long[] bits;
+ int count;
+
+ public SimpleBitSet(int size)
+ {
+ bits = new long[(size + 63)/64];
+ }
+
+ public SimpleBitSet(int size, boolean set)
+ {
+ this(size);
+ if (set)
+ {
+ Arrays.fill(bits, 0, size / 64, -1L);
+ if ((size & 63) != 0)
+ bits[indexOf(size - 1)] = -1L >>> (64 - (size & 63));
+ count = size;
+ }
+ }
+
+ public SimpleBitSet(SimpleBitSet copy)
+ {
+ bits = copy.bits.clone();
+ count = copy.count;
+ }
+
+ SimpleBitSet(long[] bits)
+ {
+ this.bits = bits;
+ for (long v : bits)
+ count += Long.bitCount(v);
+ }
+
+ public boolean set(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 != (bits[index] & bit))
+ return false;
+ bits[index] |= bit;
+ ++count;
+ return true;
+ }
+
+ public void setRange(int from, int to)
+ {
+ if (to <= from)
+ {
+ Invariants.checkArgument(to >= from, "to < from (%s < %s)", to,
from);
+ return;
+ }
+
+ int fromIndex = from >>> 6;
+ int toIndex = (to + 63) >>> 6;
+ if (fromIndex + 1 == toIndex)
+ {
+ long addBits = (-1L >>> (64 - (to & 63))) & (-1L << (from & 63));
+ orBitsAtIndex(fromIndex, addBits);
+ }
+ else if (count == 0)
+ {
+ bits[toIndex - 1] = -1L >>> (64 - (to & 63));
+ for (int i = fromIndex + 1, maxi = toIndex - 1; i < maxi ; ++i)
+ bits[i] = -1L;
+ bits[fromIndex] = -1L << (from & 63);
+ count = to - from;
+ }
+ else
+ {
+ orBitsAtIndex(fromIndex, -1L << (from & 63));
+ for (int i = fromIndex + 1, maxi = toIndex - 1; i < maxi ; ++i)
+ {
+ count += 64 - Long.bitCount(bits[i]);
+ bits[i] = -1L;
+ }
+ orBitsAtIndex(toIndex - 1, -1L >>> (64 - (to & 63)));
+ }
+ }
+
+ private void orBitsAtIndex(int index, long setBits)
+ {
+ long prevBits = bits[index];
+ bits[index] = setBits | prevBits;
+ count += Long.bitCount(setBits) - Long.bitCount(prevBits);
+ }
+
+ public boolean unset(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 == (bits[index] & bit))
+ return false;
+ bits[index] &= ~bit;
+ --count;
+ return true;
+ }
+
+ public boolean get(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ return 0 != (bits[index] & bit);
+ }
+
+ public int size()
+ {
+ return bits.length * 64;
+ }
+
+ public int setBitCount()
+ {
+ return count;
+ }
+
+ public boolean isEmpty()
+ {
+ return count == 0;
+ }
+
+ public int prevSetBit(int i)
+ {
+ if (count == 0)
+ return -1;
+
+ int index = indexOf(i);
+ long bits = this.bits[index] & bitsEqualOrLesser(i);
+ while (true)
+ {
+ if (bits != 0)
+ return index * 64 + numberOfTrailingZeros(highestOneBit(bits));
+
+ if (--index < 0)
+ return -1;
+
+ bits = this.bits[index];
+ }
+ }
+
+ public int prevSetBitNotBefore(int i, int inclBound, int ifNotFound)
+ {
+ if (count == 0)
+ return ifNotFound;
+
+ int index = indexOf(i);
+ int inclIndexBound = lowerLimitOf(inclBound);
+ long bits = this.bits[index] & bitsEqualOrLesser(i);
+ while (true)
+ {
+ if (bits != 0)
+ {
+ int result = index * 64 +
numberOfTrailingZeros(highestOneBit(bits));
+ return result > inclBound ? result : ifNotFound;
+ }
+
+ if (--index < inclIndexBound)
+ return -1;
+
+ bits = this.bits[index];
+ }
+ }
+
+ public int nextSetBit(int i, int ifNotFound)
+ {
+ if (count == 0)
+ return ifNotFound;
+
+ int index = indexOf(i);
+ long bits = this.bits[index] & bitsEqualOrGreater(i);
+ while (true)
+ {
+ if (bits != 0)
+ return index * 64 + numberOfTrailingZeros(lowestOneBit(bits));
+
+ if (++index >= this.bits.length)
+ return ifNotFound;
+
+ bits = this.bits[index];
+ }
+ }
+
+ public int nextSetBitBefore(int i, int exclBound, int ifNotFound)
+ {
+ if (count == 0)
+ return ifNotFound;
+
+ int index = indexOf(i);
+ int exclIndexBound = upperLimitOf(exclBound);
+ long bits = this.bits[index] & bitsEqualOrGreater(i);
+ while (true)
+ {
+ if (bits != 0)
+ {
+ int result = index * 64 +
numberOfTrailingZeros(lowestOneBit(bits));
+ return result < exclBound ? result : ifNotFound;
+ }
+
+ if (++index >= exclIndexBound)
+ return ifNotFound;
+
+ bits = this.bits[index];
+ }
+ }
+
+ public <P1> void forEach(P1 p1, IndexedConsumer<P1> forEach)
+ {
+ forEach(forEach, p1, IndexedConsumer::accept);
+ }
+
+ public <P1, P2> void forEach(P1 p1, P2 p2, IndexedBiConsumer<P1, P2>
forEach)
+ {
+ forEach(forEach, p1, p2, IndexedBiConsumer::accept);
+ }
+
+ public <P1, P2, P3> void forEach(P1 p1, P2 p2, P3 p3,
IndexedTriConsumer<P1, P2, P3> forEach)
+ {
+ forEach(forEach, p1, p2, p3, IndexedTriConsumer::accept);
+ }
+
+ // the bitset is permitted to mutate as we iterate
+ public <P1, P2, P3, P4> void forEach(P1 p1, P2 p2, P3 p3, P4 p4,
IndexedQuadConsumer<P1, P2, P3, P4> forEach)
+ {
+ int i = 0;
+ while (i < bits.length && count > 0)
+ {
+ long mask = -1L;
+ long register;
+ while ((register = (bits[i] & mask)) != 0)
+ {
+ int bitIndex = numberOfTrailingZeros(register);
+ mask = (-1L << bitIndex) << 1;
+ forEach.accept(p1, p2, p3, p4, i * 64 + bitIndex);
+ }
+ ++i;
+ }
Review Comment:
```suggestion
for (int i = 0; i < bits.length && count > 0; i++)
{
long mask = -1L;
long register;
while ((register = (bits[i] & mask)) != 0)
{
int bitIndex = numberOfTrailingZeros(register);
mask = (-1L << bitIndex) << 1;
forEach.accept(p1, p2, p3, p4, i * 64 + bitIndex);
}
}
```
##########
accord-core/src/main/java/accord/local/Commands.java:
##########
@@ -406,30 +451,27 @@ public static ApplyOutcome apply(SafeCommandStore
safeStore, TxnId txnId, long u
}
else if (command.hasBeen(PreCommitted) &&
!executeAt.equals(command.executeAt()))
{
+ if (command.is(Truncated) && command.executeAt() == null)
+ return ApplyOutcome.Redundant;
safeStore.agent().onInconsistentTimestamp(command,
command.executeAt(), executeAt);
}
Ranges coordinateRanges = coordinateRanges(safeStore, txnId);
Review Comment:
there is a lot of duplicate from commit (as we are doing commit)... would be
good to refactor so we can reuse the logic between the 2 functions
##########
accord-core/src/main/java/accord/local/Commands.java:
##########
@@ -610,247 +665,236 @@ private static boolean maybeExecute(SafeCommandStore
safeStore, SafeCommand safe
}
}
- protected static WaitingOn populateWaitingOn(SafeCommandStore safeStore,
TxnId txnId, Timestamp executeAt, PartialDeps partialDeps)
+ protected static WaitingOn initialiseWaitingOn(SafeCommandStore safeStore,
TxnId waitingId, Timestamp executeWaitingAt, PartialDeps partialDeps, Route<?>
route)
{
- Ranges ranges = applyRanges(safeStore, executeAt);
- if (ranges.isEmpty())
- return WaitingOn.EMPTY;
-
- return populateWaitingOn(safeStore, ranges, txnId, executeAt,
partialDeps);
+ Unseekables<?> executionParticipants =
route.participants().slice(safeStore.ranges().allAt(executeWaitingAt));
+ WaitingOn.Update update = new WaitingOn.Update(executionParticipants,
partialDeps);
Review Comment:
it looks possible that `executionParticipants` is empty, which looks to
trigger
```
if (!participants.containsAll(deps.keyDeps.keys()))
{
// TODO (now): we don't need to wait on these as we have
lost ownership of them locally
System.out.println();
}
```
and doesn't update `waitingOnCommit`
##########
accord-core/src/main/java/accord/local/Commands.java:
##########
@@ -50,36 +48,39 @@
import accord.primitives.Unseekables;
import accord.primitives.Writes;
import accord.utils.Invariants;
-import accord.utils.SortedArrays;
import accord.utils.async.AsyncChain;
import accord.utils.async.AsyncChains;
-import net.nicoulaj.compilecommand.annotations.Inline;
-import javax.annotation.Nonnull;
import javax.annotation.Nullable;
import static accord.api.ProgressLog.ProgressShard.Home;
import static accord.api.ProgressLog.ProgressShard.Local;
import static accord.api.ProgressLog.ProgressShard.No;
import static accord.api.ProgressLog.ProgressShard.UnmanagedHome;
import static accord.api.ProgressLog.ProgressShard.Unsure;
+import static accord.local.Command.Truncated.truncated;
import static accord.local.Commands.EnsureAction.Add;
import static accord.local.Commands.EnsureAction.Check;
import static accord.local.Commands.EnsureAction.Ignore;
import static accord.local.Commands.EnsureAction.Set;
import static accord.local.Commands.EnsureAction.TrySet;
+import static accord.local.RedundantStatus.LIVE;
+import static accord.local.SaveStatus.Uninitialised;
import static accord.local.Status.Accepted;
import static accord.local.Status.AcceptedInvalidate;
import static accord.local.Status.Applied;
+import static accord.local.Status.Applying;
import static accord.local.Status.Committed;
import static accord.local.Status.Durability;
+import static accord.local.Status.Durability.Universal;
import static accord.local.Status.Invalidated;
import static accord.local.Status.Known;
import static accord.local.Status.Known.ExecuteAtOnly;
+import static accord.local.Status.NotDefined;
import static accord.local.Status.PreApplied;
import static accord.local.Status.PreCommitted;
import static accord.local.Status.ReadyToExecute;
-import static accord.primitives.Routables.Slice.Minimal;
+import static accord.local.Status.Truncated;
import static accord.primitives.Route.isFullRoute;
public class Commands
Review Comment:
General comment for these changes, `SafeCommand safeCommand, TxnId txnId`
isn't safe as we can mix the command and txn_id, so we may have subtle bugs...
we should either have `SafeCommand` *or* `TxnId` but not both
##########
accord-core/src/main/java/accord/utils/SimpleBitSet.java:
##########
@@ -0,0 +1,348 @@
+/*
+ * 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 java.util.Arrays;
+
+import static java.lang.Long.highestOneBit;
+import static java.lang.Long.lowestOneBit;
+import static java.lang.Long.numberOfTrailingZeros;
+
+public class SimpleBitSet
+{
+ public static class SerializationSupport
+ {
+ public static long[] getArray(SimpleBitSet bs)
+ {
+ return bs.bits;
+ }
+
+ public static SimpleBitSet construct(long[] bits)
+ {
+ return new SimpleBitSet(bits);
+ }
+ }
+
+ final long[] bits;
+ int count;
+
+ public SimpleBitSet(int size)
+ {
+ bits = new long[(size + 63)/64];
+ }
+
+ public SimpleBitSet(int size, boolean set)
+ {
+ this(size);
+ if (set)
+ {
+ Arrays.fill(bits, 0, size / 64, -1L);
+ if ((size & 63) != 0)
+ bits[indexOf(size - 1)] = -1L >>> (64 - (size & 63));
+ count = size;
+ }
+ }
+
+ public SimpleBitSet(SimpleBitSet copy)
+ {
+ bits = copy.bits.clone();
+ count = copy.count;
+ }
+
+ SimpleBitSet(long[] bits)
+ {
+ this.bits = bits;
+ for (long v : bits)
+ count += Long.bitCount(v);
+ }
+
+ public boolean set(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 != (bits[index] & bit))
+ return false;
+ bits[index] |= bit;
+ ++count;
+ return true;
+ }
+
+ public void setRange(int from, int to)
+ {
+ if (to <= from)
+ {
+ Invariants.checkArgument(to >= from, "to < from (%s < %s)", to,
from);
+ return;
+ }
+
+ int fromIndex = from >>> 6;
+ int toIndex = (to + 63) >>> 6;
+ if (fromIndex + 1 == toIndex)
+ {
+ long addBits = (-1L >>> (64 - (to & 63))) & (-1L << (from & 63));
+ orBitsAtIndex(fromIndex, addBits);
+ }
+ else if (count == 0)
+ {
+ bits[toIndex - 1] = -1L >>> (64 - (to & 63));
+ for (int i = fromIndex + 1, maxi = toIndex - 1; i < maxi ; ++i)
+ bits[i] = -1L;
+ bits[fromIndex] = -1L << (from & 63);
+ count = to - from;
+ }
+ else
+ {
+ orBitsAtIndex(fromIndex, -1L << (from & 63));
+ for (int i = fromIndex + 1, maxi = toIndex - 1; i < maxi ; ++i)
+ {
+ count += 64 - Long.bitCount(bits[i]);
+ bits[i] = -1L;
+ }
+ orBitsAtIndex(toIndex - 1, -1L >>> (64 - (to & 63)));
+ }
+ }
+
+ private void orBitsAtIndex(int index, long setBits)
+ {
+ long prevBits = bits[index];
+ bits[index] = setBits | prevBits;
+ count += Long.bitCount(setBits) - Long.bitCount(prevBits);
+ }
+
+ public boolean unset(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 == (bits[index] & bit))
+ return false;
+ bits[index] &= ~bit;
+ --count;
+ return true;
+ }
+
+ public boolean get(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ return 0 != (bits[index] & bit);
+ }
+
+ public int size()
+ {
+ return bits.length * 64;
+ }
+
+ public int setBitCount()
+ {
+ return count;
+ }
+
+ public boolean isEmpty()
+ {
+ return count == 0;
+ }
+
+ public int prevSetBit(int i)
+ {
+ if (count == 0)
+ return -1;
+
+ int index = indexOf(i);
+ long bits = this.bits[index] & bitsEqualOrLesser(i);
+ while (true)
+ {
+ if (bits != 0)
+ return index * 64 + numberOfTrailingZeros(highestOneBit(bits));
+
+ if (--index < 0)
+ return -1;
+
+ bits = this.bits[index];
+ }
+ }
+
+ public int prevSetBitNotBefore(int i, int inclBound, int ifNotFound)
+ {
+ if (count == 0)
+ return ifNotFound;
+
+ int index = indexOf(i);
+ int inclIndexBound = lowerLimitOf(inclBound);
+ long bits = this.bits[index] & bitsEqualOrLesser(i);
+ while (true)
+ {
+ if (bits != 0)
+ {
+ int result = index * 64 +
numberOfTrailingZeros(highestOneBit(bits));
+ return result > inclBound ? result : ifNotFound;
+ }
+
+ if (--index < inclIndexBound)
+ return -1;
+
+ bits = this.bits[index];
+ }
Review Comment:
if you really want to exit early in
```
if (--index < 0)
return -1;
```
can change `prevSetBit` to delegate to `prevSetBitNotBefore` instead...
##########
accord-core/src/main/java/accord/local/Commands.java:
##########
@@ -444,13 +486,23 @@ public static void listenerUpdate(SafeCommandStore
safeStore, SafeCommand safeLi
{
Command listener = safeListener.current();
Command updated = safeUpdated.current();
+ if (listener.is(NotDefined) || listener.is(Truncated))
+ {
+ // This listener must be a stale vestige
+ // TODO (desired): would be nice to ensure these are deregistered
explicitly, but would be costly
+ Invariants.checkState(listener.saveStatus() == Uninitialised ||
listener.is(Truncated));
+ Invariants.checkState(updated.hasBeen(Applied) ||
updated.is(NotDefined));
Review Comment:
```suggestion
Invariants.checkState(updated.hasBeen(Applied) ||
updated.is(NotDefined), "Updated status expected to be Applied or NotDefined,
but was %s", updated);
```
##########
accord-core/src/main/java/accord/utils/ReducingIntervalMap.java:
##########
@@ -93,35 +99,47 @@ public boolean equals(Object o)
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
ReducingIntervalMap that = (ReducingIntervalMap) o;
- return Arrays.equals(ends, that.ends) && Arrays.equals(values,
that.values);
+ return Arrays.equals(starts, that.starts) && Arrays.equals(values,
that.values);
}
public int hashCode()
{
return Arrays.hashCode(values);
Review Comment:
should equality and hashCode also take into account inclusive ends/starts?
`[1, 2) -> 7 != [1, 2] -> 7`, and shouldn't hashCode include starts?
##########
accord-core/src/main/java/accord/utils/SimpleBitSet.java:
##########
@@ -0,0 +1,348 @@
+/*
+ * 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 java.util.Arrays;
+
+import static java.lang.Long.highestOneBit;
+import static java.lang.Long.lowestOneBit;
+import static java.lang.Long.numberOfTrailingZeros;
+
+public class SimpleBitSet
+{
+ public static class SerializationSupport
+ {
+ public static long[] getArray(SimpleBitSet bs)
+ {
+ return bs.bits;
+ }
+
+ public static SimpleBitSet construct(long[] bits)
+ {
+ return new SimpleBitSet(bits);
+ }
+ }
+
+ final long[] bits;
+ int count;
+
+ public SimpleBitSet(int size)
+ {
+ bits = new long[(size + 63)/64];
+ }
+
+ public SimpleBitSet(int size, boolean set)
+ {
+ this(size);
+ if (set)
+ {
+ Arrays.fill(bits, 0, size / 64, -1L);
+ if ((size & 63) != 0)
+ bits[indexOf(size - 1)] = -1L >>> (64 - (size & 63));
+ count = size;
+ }
+ }
+
+ public SimpleBitSet(SimpleBitSet copy)
+ {
+ bits = copy.bits.clone();
+ count = copy.count;
+ }
+
+ SimpleBitSet(long[] bits)
+ {
+ this.bits = bits;
+ for (long v : bits)
+ count += Long.bitCount(v);
+ }
+
+ public boolean set(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 != (bits[index] & bit))
+ return false;
+ bits[index] |= bit;
+ ++count;
+ return true;
+ }
+
+ public void setRange(int from, int to)
+ {
+ if (to <= from)
+ {
+ Invariants.checkArgument(to >= from, "to < from (%s < %s)", to,
from);
+ return;
+ }
+
+ int fromIndex = from >>> 6;
+ int toIndex = (to + 63) >>> 6;
+ if (fromIndex + 1 == toIndex)
+ {
+ long addBits = (-1L >>> (64 - (to & 63))) & (-1L << (from & 63));
+ orBitsAtIndex(fromIndex, addBits);
+ }
+ else if (count == 0)
+ {
+ bits[toIndex - 1] = -1L >>> (64 - (to & 63));
+ for (int i = fromIndex + 1, maxi = toIndex - 1; i < maxi ; ++i)
+ bits[i] = -1L;
+ bits[fromIndex] = -1L << (from & 63);
+ count = to - from;
+ }
+ else
+ {
+ orBitsAtIndex(fromIndex, -1L << (from & 63));
+ for (int i = fromIndex + 1, maxi = toIndex - 1; i < maxi ; ++i)
+ {
+ count += 64 - Long.bitCount(bits[i]);
+ bits[i] = -1L;
+ }
+ orBitsAtIndex(toIndex - 1, -1L >>> (64 - (to & 63)));
+ }
+ }
+
+ private void orBitsAtIndex(int index, long setBits)
+ {
+ long prevBits = bits[index];
+ bits[index] = setBits | prevBits;
+ count += Long.bitCount(setBits) - Long.bitCount(prevBits);
+ }
+
+ public boolean unset(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 == (bits[index] & bit))
+ return false;
+ bits[index] &= ~bit;
+ --count;
+ return true;
+ }
+
+ public boolean get(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ return 0 != (bits[index] & bit);
+ }
+
+ public int size()
+ {
+ return bits.length * 64;
Review Comment:
same as `waitingOn.prevSetBitNotBefore(waitingOn.size() - 1, keyDepsCount,
-1);, `waitingOn.prevSetBitNotBefore(keyDepsCount, -1);`
##########
accord-core/src/main/java/accord/local/Command.java:
##########
@@ -870,88 +870,306 @@ public Result result()
public static class WaitingOn
{
- public static final WaitingOn EMPTY = new
WaitingOn(ImmutableSortedSet.of(), ImmutableSortedMap.of());
- public final ImmutableSortedSet<TxnId> waitingOnCommit;
- public final ImmutableSortedMap<Timestamp, TxnId> waitingOnApply;
+ public static final WaitingOn EMPTY = new WaitingOn(Deps.NONE,
ImmutableBitSet.EMPTY, ImmutableBitSet.EMPTY, ImmutableBitSet.EMPTY);
- public WaitingOn(ImmutableSortedSet<TxnId> waitingOnCommit,
ImmutableSortedMap<Timestamp, TxnId> waitingOnApply)
+ public final Deps deps;
+ // note that transactions default to waitingOnCommit, so presence in
the set does not mean the transaction is uncommitted
+ public final ImmutableBitSet waitingOnCommit, waitingOnApply,
appliedOrInvalidated;
+
+ public WaitingOn(Deps deps)
{
+ this.deps = deps;
+ this.waitingOnCommit = new ImmutableBitSet(deps.txnIdCount(),
true);
+ this.waitingOnApply = new ImmutableBitSet(deps.txnIdCount(),
false);
+ this.appliedOrInvalidated = new ImmutableBitSet(deps.txnIdCount(),
false);
+ }
+
+ public WaitingOn(Deps deps, ImmutableBitSet waitingOnCommit,
ImmutableBitSet waitingOnApply, ImmutableBitSet appliedOrInvalidated)
+ {
+ this.deps = deps;
this.waitingOnCommit = waitingOnCommit;
this.waitingOnApply = waitingOnApply;
+ this.appliedOrInvalidated = appliedOrInvalidated;
}
- public static class Update
+ public boolean isWaitingOnCommit()
{
- private boolean hasChanges = false;
- private NavigableSet<TxnId> waitingOnCommit;
- private NavigableMap<Timestamp, TxnId> waitingOnApply;
+ return !waitingOnCommit.isEmpty();
+ }
- public Update()
- {
+ public boolean isWaitingOnApply()
+ {
+ return !waitingOnApply.isEmpty();
+ }
- }
+ public boolean isWaitingOn(TxnId txnId)
+ {
+ int index = deps.indexOf(txnId);
+ return index >= 0 && (waitingOnCommit.get(index) ||
waitingOnApply.get(index));
+ }
+
+ public TxnId nextWaitingOnCommit()
+ {
+ int i = waitingOnCommit.prevSetBit(waitingOnCommit.size() - 1);
+ return i < 0 ? null : deps.txnId(i);
+ }
+
+ public TxnId nextWaitingOnApply()
+ {
+ int i = waitingOnApply.prevSetBit(waitingOnApply.size() - 1);
+ return i < 0 ? null : deps.txnId(i);
+ }
+
+ public TxnId nextWaitingOn()
+ {
+ TxnId next = nextWaitingOnApply();
+ return next != null ? next : nextWaitingOnCommit();
+ }
+
+ public boolean isAppliedOrInvalidatedRangeIdx(int i)
+ {
+ return appliedOrInvalidated.get(i + deps.keyDeps.txnIdCount());
+ }
+
+ public TxnId minWaitingOnTxnId()
+ {
+ return minWaitingOnTxnId(deps, waitingOnCommit, waitingOnApply);
+ }
+
+ static TxnId minWaitingOnTxnId(Deps deps, SimpleBitSet
waitingOnCommit, SimpleBitSet waitingOnApply)
+ {
+ int keyDepsCount = deps.keyDeps.txnIdCount();
+ int minWaitingOnKeys =
Math.min(waitingOnCommit.nextSetBitBefore(0, keyDepsCount, Integer.MAX_VALUE),
waitingOnApply.nextSetBitBefore(0, keyDepsCount, Integer.MAX_VALUE));
+ int minWaitingOnRanges =
Math.min(waitingOnCommit.nextSetBit(keyDepsCount, Integer.MAX_VALUE),
waitingOnApply.nextSetBit(keyDepsCount, Integer.MAX_VALUE));
+ return TxnId.nonNullOrMin(minWaitingOnKeys == Integer.MAX_VALUE ?
null : deps.txnId(minWaitingOnKeys),
+ minWaitingOnRanges == Integer.MAX_VALUE
? null : deps.txnId(minWaitingOnRanges));
+ }
+
+ static TxnId minWaitingOn(Deps deps, SimpleBitSet waitingOn)
+ {
+ int keyDepsCount = deps.keyDeps.txnIdCount();
+ int minWaitingOnKeys = waitingOn.nextSetBitBefore(0, keyDepsCount,
-1);
+ int minWaitingOnRanges = waitingOn.nextSetBit(keyDepsCount, -1);
+ return TxnId.nonNullOrMin(minWaitingOnKeys < 0 ? null :
deps.keyDeps.txnId(minWaitingOnKeys),
+ minWaitingOnRanges < 0 ? null :
deps.rangeDeps.txnId(minWaitingOnRanges - keyDepsCount));
+ }
+
+ static TxnId maxWaitingOn(Deps deps, SimpleBitSet waitingOn)
+ {
+ int keyDepsCount = deps.keyDeps.txnIdCount();
+ int maxWaitingOnRanges =
waitingOn.prevSetBitNotBefore(waitingOn.size() - 1, keyDepsCount, -1);
+ int maxWaitingOnKeys = waitingOn.prevSetBit(keyDepsCount);
+ return TxnId.nonNullOrMax(maxWaitingOnKeys < 0 ? null :
deps.keyDeps.txnId(maxWaitingOnKeys),
+ maxWaitingOnRanges < 0 ? null :
deps.rangeDeps.txnId(maxWaitingOnRanges - keyDepsCount));
+ }
+
+ public ImmutableSortedSet<TxnId> computeWaitingOnCommit()
+ {
+ return computeWaitingOnCommit(deps, waitingOnCommit);
+ }
+
+ public ImmutableSortedSet<TxnId> computeWaitingOnApply()
+ {
+ return computeWaitingOnApply(deps, waitingOnCommit,
waitingOnApply);
+ }
+
+ private static ImmutableSortedSet<TxnId> computeWaitingOnCommit(Deps
deps, SimpleBitSet waitingOnCommit)
+ {
+ ImmutableSortedSet.Builder<TxnId> builder = new
ImmutableSortedSet.Builder<>(TxnId::compareTo);
+ waitingOnCommit.forEach(builder, deps, (b, d, i) ->
b.add(d.txnId(i)));
+ return builder.build();
+ }
+
+ private static ImmutableSortedSet<TxnId> computeWaitingOnApply(Deps
deps, SimpleBitSet waitingOnCommit, SimpleBitSet waitingOnApply)
+ {
+ ImmutableSortedSet.Builder<TxnId> builder = new
ImmutableSortedSet.Builder<>(TxnId::compareTo);
+ waitingOnApply.forEach(builder, deps, waitingOnCommit, (b, d, s,
i) -> {
+ if (!s.get(i))
+ b.add(d.txnId(i));
+ });
+ return builder.build();
+ }
+
+ private static String toString(Deps deps, SimpleBitSet
waitingOnCommit, SimpleBitSet waitingOnApply)
+ {
+ return "onApply=" + computeWaitingOnApply(deps, waitingOnCommit,
waitingOnApply).descendingSet() + ", onCommit=" + computeWaitingOnCommit(deps,
waitingOnCommit).descendingSet();
+ }
+
+ public String toString()
+ {
+ return toString(deps, waitingOnCommit, waitingOnApply);
+ }
+
+ public static class Update
+ {
+ final Deps deps;
+ private SimpleBitSet waitingOnCommit, waitingOnApply,
appliedOrInvalidated;
public Update(WaitingOn waitingOn)
{
+ this.deps = waitingOn.deps;
this.waitingOnCommit = waitingOn.waitingOnCommit;
this.waitingOnApply = waitingOn.waitingOnApply;
+ this.appliedOrInvalidated = waitingOn.appliedOrInvalidated;
}
public Update(Committed committed)
{
- this.waitingOnCommit = committed.waitingOnCommit();
- this.waitingOnApply = committed.waitingOnApply();
+ this(committed.waitingOn);
+ }
+
+ public Update(Unseekables<?> participants, Deps deps)
+ {
+ this.deps = deps;
+ this.waitingOnCommit = new SimpleBitSet(deps.txnIdCount(),
false);
+ this.waitingOnCommit.setRange(0, deps.keyDeps.txnIdCount());
+ if (!participants.containsAll(deps.keyDeps.keys()))
+ {
+ // TODO (now): we don't need to wait on these as we have
lost ownership of them locally
+ System.out.println();
Review Comment:
was this for debug testing?
##########
accord-core/src/main/java/accord/utils/ReducingIntervalMap.java:
##########
@@ -44,34 +45,39 @@ public class ReducingIntervalMap<K extends Comparable<?
super K>, V>
// for simplicity at construction, we permit this to be overridden by the
first insertion
final boolean inclusiveEnds;
- final K[] ends;
+ // starts is 1 longer than values, so that starts[0] == start of values[0]
+ final K[] starts;
final V[] values;
- public ReducingIntervalMap(V value)
+ public ReducingIntervalMap()
{
- this(false, value);
+ this(false);
}
- public ReducingIntervalMap(boolean inclusiveEnds, V value)
+ public ReducingIntervalMap(boolean inclusiveEnds)
Review Comment:
this class is lacking tests and spent a long time testing the new merge
changes... can you work on tests for this class to show these changes are
needed and safe?
##########
accord-core/src/main/java/accord/utils/RelationMultiMap.java:
##########
@@ -397,6 +397,76 @@ public void close()
}
}
+ public static class SortedRelationList<T extends Comparable<? super T>>
extends AbstractList<T> implements SortedList<T>
Review Comment:
I feel that you should pull this out into a top-level class... feels wrong
to be under `RelationMultiMap`... Map != List?
##########
accord-core/src/main/java/accord/utils/ReducingRangeMap.java:
##########
@@ -19,154 +19,163 @@
import accord.api.RoutingKey;
import accord.primitives.*;
-import com.google.common.annotations.VisibleForTesting;
import java.util.function.BiFunction;
import java.util.function.Predicate;
import static accord.utils.SortedArrays.Search.FAST;
+import static accord.utils.SortedArrays.exponentialSearch;
public class ReducingRangeMap<V> extends ReducingIntervalMap<RoutingKey, V>
{
- final RoutingKeys endKeys;
+ public static class SerializerSupport
+ {
+ public static <V> ReducingRangeMap<V> create(boolean inclusiveEnds,
RoutingKey[] ends, V[] values)
+ {
+ return new ReducingRangeMap<>(inclusiveEnds, ends, values);
+ }
+ }
- public ReducingRangeMap(V value)
+ public ReducingRangeMap()
{
- super(value);
- this.endKeys = RoutingKeys.EMPTY;
+ super();
}
- ReducingRangeMap(boolean inclusiveEnds, RoutingKey[] ends, V[] values)
+ protected ReducingRangeMap(boolean inclusiveEnds, RoutingKey[] ends, V[]
values)
{
super(inclusiveEnds, ends, values);
- this.endKeys = RoutingKeys.ofSortedUnique(ends);
}
- public V foldl(Routables<?, ?> routables, BiFunction<V, V, V> fold, V
initialValue)
+ public V foldl(Routables<?> routables, BiFunction<V, V, V> fold, V
accumulator)
+ {
+ return foldl(routables, (a, b, f, ignore) -> f.apply(a, b),
accumulator, fold, null, ignore -> false);
+ }
+
+ public <V2> V2 foldl(Routables<?> routables, BiFunction<V, V2, V2> fold,
V2 accumulator, Predicate<V2> terminate)
+ {
+ return foldl(routables, (a, b, f, ignore) -> f.apply(a, b),
accumulator, fold, null, terminate);
+ }
+
+ public <V2, P1> V2 foldl(Routables<?> routables, TriFunction<V, V2, P1,
V2> fold, V2 accumulator, P1 p1, Predicate<V2> terminate)
{
- return foldl(routables, fold, initialValue, ignore -> false);
+ return foldl(routables, (a, b, f, p) -> f.apply(a, b, p), accumulator,
fold, p1, terminate);
}
- public <V2> V2 foldl(Routables<?, ?> routables, BiFunction<V, V2, V2>
fold, V2 initialValue, Predicate<V2> terminate)
+ public <V2, P1, P2> V2 foldl(Routables<?> routables, QuadFunction<V, V2,
P1, P2, V2> fold, V2 accumulator, P1 p1, P2 p2, Predicate<V2> terminate)
+ {
+ return foldl(routables, (v, v2, param1, param2, i, j) -> fold.apply(v,
v2, param1, param2), accumulator, p1, p2, terminate);
+ }
+
+ public <V2, P1, P2> V2 foldl(Routables<?> routables,
IndexedRangeQuadFunction<V, V2, P1, P2, V2> fold, V2 accumulator, P1 p1, P2 p2,
Predicate<V2> terminate)
{
switch (routables.domain())
{
default: throw new AssertionError();
- case Key: return foldl((AbstractKeys<?, ?>) routables, fold,
initialValue, terminate);
- case Range: return foldl((AbstractRanges<?>) routables, fold,
initialValue, terminate);
+ case Key: return foldl((AbstractKeys<?>) routables, fold,
accumulator, p1, p2, terminate);
+ case Range: return foldl((AbstractRanges<?>) routables, fold,
accumulator, p1, p2, terminate);
}
}
// TODO (required): test
- public <V2> V2 foldl(AbstractKeys<?, ?> keys, BiFunction<V, V2, V2>
reduce, V2 accumulator, Predicate<V2> terminate)
+ public <V2, P1, P2> V2 foldl(AbstractKeys<?> keys,
IndexedRangeQuadFunction<V, V2, P1, P2, V2> fold, V2 accumulator, P1 p1, P2 p2,
Predicate<V2> terminate)
Review Comment:
can you fix the TODO by adding the tests?
##########
accord-core/src/main/java/accord/utils/RelationMultiMap.java:
##########
@@ -397,6 +397,76 @@ public void close()
}
}
+ public static class SortedRelationList<T extends Comparable<? super T>>
extends AbstractList<T> implements SortedList<T>
+ {
+ public static final SortedRelationList EMPTY = new
SortedRelationList(new Comparable[0], new int[0], 0, 0);
+
+ final T[] values;
+ final int[] ids;
+ final int startIndex, endIndex;
+
+ public SortedRelationList(T[] values, int[] ids, int startIndex, int
endIndex)
+ {
+ this.values = values;
+ this.ids = ids;
+ this.startIndex = startIndex;
+ this.endIndex = endIndex;
+ }
+
+ @Override
+ public T get(int index)
+ {
+ if (index >= endIndex)
+ throw new IndexOutOfBoundsException();
Review Comment:
```suggestion
throw new IndexOutOfBoundsException(String.format("%d >=
%d", index, endIndex));
```
##########
accord-core/src/main/java/accord/utils/RelationMultiMap.java:
##########
@@ -397,6 +397,76 @@ public void close()
}
}
+ public static class SortedRelationList<T extends Comparable<? super T>>
extends AbstractList<T> implements SortedList<T>
+ {
+ public static final SortedRelationList EMPTY = new
SortedRelationList(new Comparable[0], new int[0], 0, 0);
+
+ final T[] values;
+ final int[] ids;
+ final int startIndex, endIndex;
+
+ public SortedRelationList(T[] values, int[] ids, int startIndex, int
endIndex)
+ {
+ this.values = values;
+ this.ids = ids;
+ this.startIndex = startIndex;
+ this.endIndex = endIndex;
+ }
+
+ @Override
+ public T get(int index)
+ {
+ if (index >= endIndex)
+ throw new IndexOutOfBoundsException();
+ return values[ids[startIndex + index]];
+ }
+
+ public int getValueIndex(int index)
+ {
+ if (index >= endIndex)
+ throw new IndexOutOfBoundsException();
Review Comment:
```suggestion
throw new IndexOutOfBoundsException(String.format("%d >=
%d", index, endIndex));
```
##########
accord-core/src/main/java/accord/utils/ReducingRangeMap.java:
##########
@@ -19,154 +19,163 @@
import accord.api.RoutingKey;
import accord.primitives.*;
-import com.google.common.annotations.VisibleForTesting;
import java.util.function.BiFunction;
import java.util.function.Predicate;
import static accord.utils.SortedArrays.Search.FAST;
+import static accord.utils.SortedArrays.exponentialSearch;
public class ReducingRangeMap<V> extends ReducingIntervalMap<RoutingKey, V>
{
- final RoutingKeys endKeys;
+ public static class SerializerSupport
+ {
+ public static <V> ReducingRangeMap<V> create(boolean inclusiveEnds,
RoutingKey[] ends, V[] values)
+ {
+ return new ReducingRangeMap<>(inclusiveEnds, ends, values);
+ }
+ }
- public ReducingRangeMap(V value)
+ public ReducingRangeMap()
{
- super(value);
- this.endKeys = RoutingKeys.EMPTY;
+ super();
}
- ReducingRangeMap(boolean inclusiveEnds, RoutingKey[] ends, V[] values)
+ protected ReducingRangeMap(boolean inclusiveEnds, RoutingKey[] ends, V[]
values)
{
super(inclusiveEnds, ends, values);
- this.endKeys = RoutingKeys.ofSortedUnique(ends);
}
- public V foldl(Routables<?, ?> routables, BiFunction<V, V, V> fold, V
initialValue)
+ public V foldl(Routables<?> routables, BiFunction<V, V, V> fold, V
accumulator)
+ {
+ return foldl(routables, (a, b, f, ignore) -> f.apply(a, b),
accumulator, fold, null, ignore -> false);
+ }
+
+ public <V2> V2 foldl(Routables<?> routables, BiFunction<V, V2, V2> fold,
V2 accumulator, Predicate<V2> terminate)
+ {
+ return foldl(routables, (a, b, f, ignore) -> f.apply(a, b),
accumulator, fold, null, terminate);
+ }
+
+ public <V2, P1> V2 foldl(Routables<?> routables, TriFunction<V, V2, P1,
V2> fold, V2 accumulator, P1 p1, Predicate<V2> terminate)
{
- return foldl(routables, fold, initialValue, ignore -> false);
+ return foldl(routables, (a, b, f, p) -> f.apply(a, b, p), accumulator,
fold, p1, terminate);
}
- public <V2> V2 foldl(Routables<?, ?> routables, BiFunction<V, V2, V2>
fold, V2 initialValue, Predicate<V2> terminate)
+ public <V2, P1, P2> V2 foldl(Routables<?> routables, QuadFunction<V, V2,
P1, P2, V2> fold, V2 accumulator, P1 p1, P2 p2, Predicate<V2> terminate)
+ {
+ return foldl(routables, (v, v2, param1, param2, i, j) -> fold.apply(v,
v2, param1, param2), accumulator, p1, p2, terminate);
+ }
+
+ public <V2, P1, P2> V2 foldl(Routables<?> routables,
IndexedRangeQuadFunction<V, V2, P1, P2, V2> fold, V2 accumulator, P1 p1, P2 p2,
Predicate<V2> terminate)
{
switch (routables.domain())
{
default: throw new AssertionError();
- case Key: return foldl((AbstractKeys<?, ?>) routables, fold,
initialValue, terminate);
- case Range: return foldl((AbstractRanges<?>) routables, fold,
initialValue, terminate);
+ case Key: return foldl((AbstractKeys<?>) routables, fold,
accumulator, p1, p2, terminate);
+ case Range: return foldl((AbstractRanges<?>) routables, fold,
accumulator, p1, p2, terminate);
}
}
// TODO (required): test
- public <V2> V2 foldl(AbstractKeys<?, ?> keys, BiFunction<V, V2, V2>
reduce, V2 accumulator, Predicate<V2> terminate)
+ public <V2, P1, P2> V2 foldl(AbstractKeys<?> keys,
IndexedRangeQuadFunction<V, V2, P1, P2, V2> fold, V2 accumulator, P1 p1, P2 p2,
Predicate<V2> terminate)
{
- int i = 0, j = 0;
+ if (values.length == 0)
+ return accumulator;
+
+ int i = 0, j = keys.findNext(0, starts[0], FAST);
+ if (j < 0) j = -1 - j;
+ else if (inclusiveEnds) ++j;
+
while (j < keys.size())
{
- i = endKeys.findNext(i, keys.get(j), FAST);
- if (i < 0) i = -1 - i;
- else if (!inclusiveEnds) ++i;
+ i = exponentialSearch(starts, i, starts.length, keys.get(j));
+ if (i < 0) i = -2 - i;
+ else if (inclusiveEnds) --i;
- accumulator = reduce.apply(values[i], accumulator);
- if (terminate.test(accumulator))
+ if (i >= values.length)
return accumulator;
- if (i == endKeys.size())
- return j + 1 == keys.size() ? accumulator :
reduce.apply(values[i], accumulator);
+ int nextj = keys.findNext(j, starts[i + 1], FAST);
+ if (nextj < 0) nextj = -1 -nextj;
+ else if (inclusiveEnds) ++nextj;
- j = keys.findNext(j + 1, endKeys.get(i), FAST);
- if (j < 0) j = -1 - j;
+ if (j != nextj && values[i] != null)
+ {
+ accumulator = fold.apply(values[i], accumulator, p1, p2, j,
nextj);
+ if (terminate.test(accumulator))
+ return accumulator;
+ }
+ ++i;
+ j = nextj;
}
return accumulator;
}
// TODO (required): test
- public <V2> V2 foldl(AbstractRanges<?> ranges, BiFunction<V, V2, V2>
reduce, V2 accumulator, Predicate<V2> terminate)
+ public <V2, P1, P2> V2 foldl(AbstractRanges<?> ranges,
IndexedRangeQuadFunction<V, V2, P1, P2, V2> fold, V2 accumulator, P1 p1, P2 p2,
Predicate<V2> terminate)
{
- int i = 0, j = 0;
+ if (values.length == 0)
+ return accumulator;
+
+ // TODO (desired): first searches should be binarySearch
+ int j = ranges.findNext(0, starts[0], FAST);
+ if (j < 0) j = -1 - j;
+ else if (inclusiveEnds && ranges.get(j).end().equals(starts[0])) ++j;
+
+ int i = 0;
while (j < ranges.size())
{
Range range = ranges.get(j);
- i = endKeys.findNext(i, range.start(), FAST);
- if (i < 0) i = -1 - i;
- else if (inclusiveEnds) ++i;
+ RoutingKey start = range.start();
+ int nexti = exponentialSearch(starts, i, starts.length, start);
+ if (nexti < 0) i = Math.max(i, -2 - nexti);
+ else if (nexti > i && !inclusiveStarts()) i = nexti - 1;
+ else i = nexti;
+
+ if (i >= values.length)
+ return accumulator;
- int nexti = endKeys.findNext(i, range.end(), FAST);
- if (nexti < 0) nexti = -nexti;
- else if (inclusiveEnds) ++nexti;
+ int toj, nextj = ranges.findNext(j, starts[i + 1], FAST);
+ if (nextj < 0) toj = nextj = -1 -nextj;
+ else
+ {
+ toj = nextj + 1;
+ if (inclusiveEnds && ranges.get(nextj).end().equals(starts[i +
1]))
+ ++nextj;
+ }
- while (i < nexti)
+ if (toj > j && values[i] != null)
{
- accumulator = reduce.apply(values[i++], accumulator);
+ accumulator = fold.apply(values[i], accumulator, p1, p2, j,
toj);
if (terminate.test(accumulator))
return accumulator;
}
- if (i > endKeys.size())
- return accumulator;
-
- j = ranges.findNext(j + 1, endKeys.get(i - 1), FAST);
- if (j < 0) j = -1 - j;
+ ++i;
+ j = nextj;
}
return accumulator;
}
- /**
- * returns a copy of this ReducingRangeMap limited to the ranges supplied,
with all other ranges reporting the "zero" value
- */
- @VisibleForTesting
- static <V> ReducingRangeMap<V> trim(ReducingRangeMap<V> existing, Ranges
ranges, BiFunction<V, V, V> reduce)
+ public static <V> ReducingRangeMap<V> create(Ranges ranges, V value)
{
- boolean inclusiveEnds = inclusiveEnds(existing.inclusiveEnds,
existing.size() > 0, ranges.size() > 0 && ranges.get(0).endInclusive(),
ranges.size() > 0);
- ReducingRangeMap.Builder<V> builder = new
ReducingRangeMap.Builder<>(inclusiveEnds, existing.size());
+ if (value == null)
+ throw new IllegalArgumentException();
Review Comment:
```suggestion
throw new NullPointerException("value");
```
##########
accord-core/src/main/java/accord/utils/SimpleBitSet.java:
##########
@@ -0,0 +1,348 @@
+/*
+ * 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 java.util.Arrays;
+
+import static java.lang.Long.highestOneBit;
+import static java.lang.Long.lowestOneBit;
+import static java.lang.Long.numberOfTrailingZeros;
+
+public class SimpleBitSet
+{
+ public static class SerializationSupport
+ {
+ public static long[] getArray(SimpleBitSet bs)
+ {
+ return bs.bits;
+ }
+
+ public static SimpleBitSet construct(long[] bits)
+ {
+ return new SimpleBitSet(bits);
+ }
+ }
+
+ final long[] bits;
+ int count;
+
+ public SimpleBitSet(int size)
+ {
+ bits = new long[(size + 63)/64];
+ }
+
+ public SimpleBitSet(int size, boolean set)
+ {
+ this(size);
+ if (set)
+ {
+ Arrays.fill(bits, 0, size / 64, -1L);
+ if ((size & 63) != 0)
+ bits[indexOf(size - 1)] = -1L >>> (64 - (size & 63));
+ count = size;
+ }
+ }
+
+ public SimpleBitSet(SimpleBitSet copy)
+ {
+ bits = copy.bits.clone();
+ count = copy.count;
+ }
+
+ SimpleBitSet(long[] bits)
+ {
+ this.bits = bits;
+ for (long v : bits)
+ count += Long.bitCount(v);
+ }
+
+ public boolean set(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 != (bits[index] & bit))
+ return false;
+ bits[index] |= bit;
+ ++count;
+ return true;
+ }
+
+ public void setRange(int from, int to)
+ {
+ if (to <= from)
+ {
+ Invariants.checkArgument(to >= from, "to < from (%s < %s)", to,
from);
+ return;
+ }
+
+ int fromIndex = from >>> 6;
+ int toIndex = (to + 63) >>> 6;
+ if (fromIndex + 1 == toIndex)
+ {
+ long addBits = (-1L >>> (64 - (to & 63))) & (-1L << (from & 63));
+ orBitsAtIndex(fromIndex, addBits);
+ }
+ else if (count == 0)
+ {
+ bits[toIndex - 1] = -1L >>> (64 - (to & 63));
+ for (int i = fromIndex + 1, maxi = toIndex - 1; i < maxi ; ++i)
+ bits[i] = -1L;
+ bits[fromIndex] = -1L << (from & 63);
+ count = to - from;
+ }
+ else
+ {
+ orBitsAtIndex(fromIndex, -1L << (from & 63));
+ for (int i = fromIndex + 1, maxi = toIndex - 1; i < maxi ; ++i)
+ {
+ count += 64 - Long.bitCount(bits[i]);
+ bits[i] = -1L;
+ }
+ orBitsAtIndex(toIndex - 1, -1L >>> (64 - (to & 63)));
+ }
+ }
+
+ private void orBitsAtIndex(int index, long setBits)
+ {
+ long prevBits = bits[index];
+ bits[index] = setBits | prevBits;
+ count += Long.bitCount(setBits) - Long.bitCount(prevBits);
+ }
+
+ public boolean unset(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 == (bits[index] & bit))
+ return false;
+ bits[index] &= ~bit;
+ --count;
+ return true;
+ }
+
+ public boolean get(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ return 0 != (bits[index] & bit);
+ }
+
+ public int size()
+ {
+ return bits.length * 64;
Review Comment:
this was unexpected when I started testing, normally `size` is how many
elements, not how large the storage is... `setBitCount` is dead code, and
`size` is always used as follows
```
waitingOnCommit.prevSetBit(waitingOnCommit.size() - 1);
```
which could be cleaned up and done as `waitingOnCommit.prevSetBit()` where
we know to check the last element?
##########
accord-core/src/main/java/accord/utils/SimpleBitSet.java:
##########
@@ -0,0 +1,348 @@
+/*
+ * 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 java.util.Arrays;
+
+import static java.lang.Long.highestOneBit;
+import static java.lang.Long.lowestOneBit;
+import static java.lang.Long.numberOfTrailingZeros;
+
+public class SimpleBitSet
Review Comment:
please add tests for this class
##########
accord-core/src/main/java/accord/utils/SimpleBitSet.java:
##########
@@ -0,0 +1,348 @@
+/*
+ * 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 java.util.Arrays;
+
+import static java.lang.Long.highestOneBit;
+import static java.lang.Long.lowestOneBit;
+import static java.lang.Long.numberOfTrailingZeros;
+
+public class SimpleBitSet
+{
+ public static class SerializationSupport
+ {
+ public static long[] getArray(SimpleBitSet bs)
+ {
+ return bs.bits;
+ }
+
+ public static SimpleBitSet construct(long[] bits)
+ {
+ return new SimpleBitSet(bits);
+ }
+ }
+
+ final long[] bits;
+ int count;
+
+ public SimpleBitSet(int size)
+ {
+ bits = new long[(size + 63)/64];
+ }
+
+ public SimpleBitSet(int size, boolean set)
+ {
+ this(size);
+ if (set)
+ {
+ Arrays.fill(bits, 0, size / 64, -1L);
+ if ((size & 63) != 0)
+ bits[indexOf(size - 1)] = -1L >>> (64 - (size & 63));
+ count = size;
+ }
+ }
+
+ public SimpleBitSet(SimpleBitSet copy)
+ {
+ bits = copy.bits.clone();
+ count = copy.count;
+ }
+
+ SimpleBitSet(long[] bits)
+ {
+ this.bits = bits;
+ for (long v : bits)
+ count += Long.bitCount(v);
+ }
+
+ public boolean set(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 != (bits[index] & bit))
+ return false;
+ bits[index] |= bit;
+ ++count;
+ return true;
+ }
+
+ public void setRange(int from, int to)
Review Comment:
can you add the following test
```
@Test
public void setRange()
{
int size = 64 * 8;
SimpleBitSet set = new SimpleBitSet(size);
Gen.IntGen indexGen = Gens.ints().between(0, size - 1);
qt().withPure(false).forAll(indexGen, indexGen).check((a, b) -> {
if (a > b)
{
int tmp = b;
b = a;
a = tmp;
}
int covers = b - a; // no +1 as to is exclusive
set.setRange(a, b);
Assertions.assertThat(set.setBitCount()).isEqualTo(covers);
for (int i = a; i < b; i++)
Assertions.assertThat(set.get(i)).isTrue();
Assertions.assertThat(set.get(b)).isFalse();
for (int i = a; i <= b; i++)
set.unset(i);
});
}
```
##########
accord-core/src/main/java/accord/utils/SimpleBitSet.java:
##########
@@ -0,0 +1,348 @@
+/*
+ * 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 java.util.Arrays;
+
+import static java.lang.Long.highestOneBit;
+import static java.lang.Long.lowestOneBit;
+import static java.lang.Long.numberOfTrailingZeros;
+
+public class SimpleBitSet
+{
+ public static class SerializationSupport
+ {
+ public static long[] getArray(SimpleBitSet bs)
+ {
+ return bs.bits;
+ }
+
+ public static SimpleBitSet construct(long[] bits)
+ {
+ return new SimpleBitSet(bits);
+ }
+ }
+
+ final long[] bits;
+ int count;
+
+ public SimpleBitSet(int size)
+ {
+ bits = new long[(size + 63)/64];
+ }
+
+ public SimpleBitSet(int size, boolean set)
+ {
+ this(size);
+ if (set)
+ {
+ Arrays.fill(bits, 0, size / 64, -1L);
+ if ((size & 63) != 0)
+ bits[indexOf(size - 1)] = -1L >>> (64 - (size & 63));
+ count = size;
+ }
+ }
+
+ public SimpleBitSet(SimpleBitSet copy)
+ {
+ bits = copy.bits.clone();
+ count = copy.count;
+ }
+
+ SimpleBitSet(long[] bits)
+ {
+ this.bits = bits;
+ for (long v : bits)
+ count += Long.bitCount(v);
+ }
+
+ public boolean set(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 != (bits[index] & bit))
+ return false;
+ bits[index] |= bit;
+ ++count;
+ return true;
+ }
+
+ public void setRange(int from, int to)
+ {
+ if (to <= from)
+ {
+ Invariants.checkArgument(to >= from, "to < from (%s < %s)", to,
from);
Review Comment:
The following test fails,
```
@Test
public void setRange()
{
int size = 64 * 8;
SimpleBitSet set = new SimpleBitSet(size);
set.setRange(10, 10);
Assertions.assertThat(set.get(10)).isTrue();
}
```
when `from == to` we no-op, *should* we reject this case and simplify the
condition?
##########
accord-core/src/main/java/accord/utils/SortedArrays.java:
##########
@@ -712,6 +715,88 @@ public static <A, R> A[] sliceWithMultipleMatches(A[]
slice, R[] select, IntFunc
}
}
+ /**
+ * Given two sorted arrays {@code slice} and {@code select}, where each
array's contents is unique and non-overlapping
+ * with itself, but may match multiple entries in the other array, return
a new array containing the elements of {@code slice}
+ * that match elements of {@code select} as per the provided comparators.
+ */
+ public static <A, R> A[] subtractWithMultipleMatches(A[] input, R[]
subtract, IntFunction<A[]> factory, AsymmetricComparator<A, R> cmp1,
AsymmetricComparator<R, A> cmp2)
Review Comment:
please add tests for this
##########
accord-core/src/test/java/accord/burn/BurnTest.java:
##########
@@ -322,7 +326,7 @@ public static void main(String[] args)
{
int count = 1;
int operations = 1000;
- Long overrideSeed = -3309027396608571728L;
+ Long overrideSeed = -1320173654115300201L;
Review Comment:
please revert
##########
accord-core/src/main/java/accord/utils/SimpleBitSet.java:
##########
@@ -0,0 +1,348 @@
+/*
+ * 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 java.util.Arrays;
+
+import static java.lang.Long.highestOneBit;
+import static java.lang.Long.lowestOneBit;
+import static java.lang.Long.numberOfTrailingZeros;
+
+public class SimpleBitSet
+{
+ public static class SerializationSupport
+ {
+ public static long[] getArray(SimpleBitSet bs)
+ {
+ return bs.bits;
+ }
+
+ public static SimpleBitSet construct(long[] bits)
+ {
+ return new SimpleBitSet(bits);
+ }
+ }
+
+ final long[] bits;
+ int count;
+
+ public SimpleBitSet(int size)
+ {
+ bits = new long[(size + 63)/64];
+ }
+
+ public SimpleBitSet(int size, boolean set)
+ {
+ this(size);
+ if (set)
+ {
+ Arrays.fill(bits, 0, size / 64, -1L);
+ if ((size & 63) != 0)
+ bits[indexOf(size - 1)] = -1L >>> (64 - (size & 63));
+ count = size;
+ }
+ }
+
+ public SimpleBitSet(SimpleBitSet copy)
+ {
+ bits = copy.bits.clone();
+ count = copy.count;
+ }
+
+ SimpleBitSet(long[] bits)
+ {
+ this.bits = bits;
+ for (long v : bits)
+ count += Long.bitCount(v);
+ }
+
+ public boolean set(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 != (bits[index] & bit))
+ return false;
+ bits[index] |= bit;
+ ++count;
+ return true;
+ }
+
+ public void setRange(int from, int to)
+ {
+ if (to <= from)
+ {
+ Invariants.checkArgument(to >= from, "to < from (%s < %s)", to,
from);
+ return;
+ }
+
+ int fromIndex = from >>> 6;
+ int toIndex = (to + 63) >>> 6;
+ if (fromIndex + 1 == toIndex)
+ {
+ long addBits = (-1L >>> (64 - (to & 63))) & (-1L << (from & 63));
+ orBitsAtIndex(fromIndex, addBits);
+ }
+ else if (count == 0)
+ {
+ bits[toIndex - 1] = -1L >>> (64 - (to & 63));
+ for (int i = fromIndex + 1, maxi = toIndex - 1; i < maxi ; ++i)
+ bits[i] = -1L;
+ bits[fromIndex] = -1L << (from & 63);
+ count = to - from;
+ }
+ else
+ {
+ orBitsAtIndex(fromIndex, -1L << (from & 63));
+ for (int i = fromIndex + 1, maxi = toIndex - 1; i < maxi ; ++i)
+ {
+ count += 64 - Long.bitCount(bits[i]);
+ bits[i] = -1L;
+ }
+ orBitsAtIndex(toIndex - 1, -1L >>> (64 - (to & 63)));
+ }
+ }
+
+ private void orBitsAtIndex(int index, long setBits)
+ {
+ long prevBits = bits[index];
+ bits[index] = setBits | prevBits;
+ count += Long.bitCount(setBits) - Long.bitCount(prevBits);
+ }
+
+ public boolean unset(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 == (bits[index] & bit))
+ return false;
+ bits[index] &= ~bit;
+ --count;
+ return true;
+ }
+
+ public boolean get(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ return 0 != (bits[index] & bit);
+ }
+
+ public int size()
+ {
+ return bits.length * 64;
+ }
+
+ public int setBitCount()
+ {
+ return count;
+ }
+
+ public boolean isEmpty()
+ {
+ return count == 0;
+ }
+
+ public int prevSetBit(int i)
+ {
+ if (count == 0)
+ return -1;
+
+ int index = indexOf(i);
+ long bits = this.bits[index] & bitsEqualOrLesser(i);
+ while (true)
+ {
+ if (bits != 0)
+ return index * 64 + numberOfTrailingZeros(highestOneBit(bits));
+
+ if (--index < 0)
+ return -1;
+
+ bits = this.bits[index];
+ }
+ }
+
+ public int prevSetBitNotBefore(int i, int inclBound, int ifNotFound)
+ {
+ if (count == 0)
+ return ifNotFound;
+
+ int index = indexOf(i);
+ int inclIndexBound = lowerLimitOf(inclBound);
+ long bits = this.bits[index] & bitsEqualOrLesser(i);
+ while (true)
+ {
+ if (bits != 0)
+ {
+ int result = index * 64 +
numberOfTrailingZeros(highestOneBit(bits));
+ return result > inclBound ? result : ifNotFound;
+ }
+
+ if (--index < inclIndexBound)
+ return -1;
+
+ bits = this.bits[index];
+ }
Review Comment:
```suggestion
int result = prevSetBit(i);
return result > inclBound ? result : ifNotFound;
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
