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 875937c8 CASSANDRA-20883: bitset changes to support cassandra
serializers
875937c8 is described below
commit 875937c8844e854a55765c64ac34a2bd4a6bc187
Author: David Capwell <dcapw...@apple.com>
AuthorDate: Wed Sep 3 10:00:51 2025 -0700
CASSANDRA-20883: bitset changes to support cassandra serializers
patch by David Capwell and Benedict for CASSANDRA-20883
---
.gitignore | 7 +
.../src/main/java/accord/utils/SimpleBitSet.java | 1 +
.../{SimpleBitSet.java => SimpleBitSets.java} | 22 ++-
.../src/main/java/accord/utils/SmallBitSet.java | 25 +++
.../src/main/java/accord/utils/SortedArrays.java | 213 +++++++++++++++++++++
.../test/java/accord/utils/SimpleBitSetTest.java | 173 +++++++++++++++++
6 files changed, 431 insertions(+), 10 deletions(-)
diff --git a/.gitignore b/.gitignore
index bd3d7a7f..34cc6f2d 100644
--- a/.gitignore
+++ b/.gitignore
@@ -4,3 +4,10 @@ build/
accord-core/build/
accord-maelstrom/build/
.rat-excludes.txt
+
+# Coding tools like NeoVim and Visual Studio Code will store their metadata at
the following paths
+accord-core/bin/
+accord-maelstrom/bin/
+.project
+.settings
+.classpath
diff --git a/accord-core/src/main/java/accord/utils/SimpleBitSet.java
b/accord-core/src/main/java/accord/utils/SimpleBitSet.java
index 24428971..8df24a80 100644
--- a/accord-core/src/main/java/accord/utils/SimpleBitSet.java
+++ b/accord-core/src/main/java/accord/utils/SimpleBitSet.java
@@ -26,6 +26,7 @@ public interface SimpleBitSet
void clear();
boolean isEmpty();
int nextSetBit(int fromIndex);
+ int getSetBitCount();
static SimpleBitSet allocate(int size)
{
diff --git a/accord-core/src/main/java/accord/utils/SimpleBitSet.java
b/accord-core/src/main/java/accord/utils/SimpleBitSets.java
similarity index 70%
copy from accord-core/src/main/java/accord/utils/SimpleBitSet.java
copy to accord-core/src/main/java/accord/utils/SimpleBitSets.java
index 24428971..bdd99c69 100644
--- a/accord-core/src/main/java/accord/utils/SimpleBitSet.java
+++ b/accord-core/src/main/java/accord/utils/SimpleBitSets.java
@@ -18,18 +18,20 @@
package accord.utils;
-public interface SimpleBitSet
+public final class SimpleBitSets
{
- boolean get(int i);
- boolean set(int i);
- boolean unset(int i);
- void clear();
- boolean isEmpty();
- int nextSetBit(int fromIndex);
+ private SimpleBitSets() {}
- static SimpleBitSet allocate(int size)
+ public static SimpleBitSet allSet(int bits)
{
- if (size <= 64) return new SmallBitSet();
- else return new LargeBitSet(size);
+ SimpleBitSet set = SimpleBitSet.allocate(bits);
+ for (int i = 0; i < bits; i++)
+ set.set(i);
+ return set;
+ }
+
+ public static SimpleBitSet allUnset(int bits)
+ {
+ return SimpleBitSet.allocate(bits);
}
}
diff --git a/accord-core/src/main/java/accord/utils/SmallBitSet.java
b/accord-core/src/main/java/accord/utils/SmallBitSet.java
index f10f6706..a0e692f9 100644
--- a/accord-core/src/main/java/accord/utils/SmallBitSet.java
+++ b/accord-core/src/main/java/accord/utils/SmallBitSet.java
@@ -26,6 +26,20 @@ public class SmallBitSet implements SimpleBitSet
{
private long bits;
+ public SmallBitSet()
+ {
+ }
+
+ public SmallBitSet(long bits)
+ {
+ this.bits = bits;
+ }
+
+ public long bits()
+ {
+ return bits;
+ }
+
public boolean set(int i)
{
long bit = bit(i);
@@ -69,4 +83,15 @@ public class SmallBitSet implements SimpleBitSet
return numberOfTrailingZeros(bits);
}
+ @Override
+ public int getSetBitCount()
+ {
+ return Long.bitCount(bits);
+ }
+
+ @Override
+ public boolean equals(Object that)
+ {
+ return that instanceof SmallBitSet && this.bits == ((SmallBitSet)
that).bits;
+ }
}
diff --git a/accord-core/src/main/java/accord/utils/SortedArrays.java
b/accord-core/src/main/java/accord/utils/SortedArrays.java
index 6ffd16d3..8a613af5 100644
--- a/accord-core/src/main/java/accord/utils/SortedArrays.java
+++ b/accord-core/src/main/java/accord/utils/SortedArrays.java
@@ -50,6 +50,8 @@ import static accord.utils.SortedArrays.Search.FAST;
// - Exploit exponentialSearch in union/intersection/etc
public class SortedArrays
{
+ private static final int[] NO_INTS = new int[0];
+
public static class SortedArrayList<T extends Comparable<? super T>>
extends AbstractList<T> implements SortedList<T>
{
final T[] array;
@@ -468,6 +470,187 @@ public class SortedArrays
}
}
+ /**
+ * A linear intersection where we only want results from the left inputs,
and the right inputs may either be a different type or otherwise only used for
filtering
+ */
+ public static int[] linearIntersection(int[] left, int leftStart, int
leftEnd, int[] right, int rightStart, int rightEnd, ArrayBuffers.IntBuffers
buffers)
+ {
+ if (leftEnd - leftStart > rightEnd - rightStart)
+ {
+ int[] tmp = left;
+ int tmpStart = leftStart, tmpEnd = leftEnd;
+ left = right;
+ leftStart = rightStart;
+ leftEnd = rightEnd;
+ right = tmp;
+ rightStart = tmpStart;
+ rightEnd = tmpEnd;
+ }
+
+ int leftIdx = leftStart;
+ int rightIdx = rightStart;
+
+ int[] result = null;
+ int resultSize = 0;
+
+ boolean hasMatch = false;
+ {
+ while (leftIdx < leftEnd && rightIdx < rightEnd)
+ {
+ int leftKey = left[leftIdx];
+ int rightKey = right[rightIdx];
+ int cmp = Integer.compare(leftKey, rightKey);
+
+ if (cmp >= 0)
+ {
+ rightIdx += 1;
+ leftIdx += cmp == 0 ? 1 : 0;
+ if (cmp == 0)
+ hasMatch = true;
+ }
+ else
+ {
+ resultSize = leftIdx++;
+ result = buffers.getInts(resultSize + Math.min(leftEnd -
leftIdx, rightEnd - rightIdx));
+ System.arraycopy(left, 0, result, 0, resultSize);
+ break;
+ }
+ }
+
+ if (result == null)
+ {
+ if (!hasMatch)
+ return left.length == 0 ? left : NO_INTS;
+ if (leftStart == 0 && leftEnd == left.length)
+ return left;
+ return Arrays.copyOfRange(left, leftStart, leftEnd);
+ }
+ }
+
+ try
+ {
+ while (leftIdx < leftEnd && rightIdx < rightEnd)
+ {
+ int leftKey = left[leftIdx];
+ int rightKey = right[rightIdx];
+ int cmp = Integer.compare(leftKey, rightKey);
+
+ if (cmp == 0)
+ {
+ leftIdx++;
+ rightIdx++;
+ result[resultSize++] = leftKey;
+ }
+ else if (cmp < 0) leftIdx++;
+ else rightIdx++;
+ }
+
+ return buffers.complete(result, resultSize);
+ }
+ finally
+ {
+ buffers.discard(result, resultSize);
+ }
+ }
+
+ public static int[] linearUnion(int[] left, int leftStart, int leftEnd,
int[] right, int rightStart, int rightEnd, ArrayBuffers.IntBuffers buffers)
+ {
+ if (leftEnd - leftStart < rightEnd - rightStart)
+ {
+ int[] tmp = left;
+ int tmpStart = leftStart, tmpEnd = leftEnd;
+ left = right;
+ leftStart = rightStart;
+ leftEnd = rightEnd;
+ right = tmp;
+ rightStart = tmpStart;
+ rightEnd = tmpEnd;
+ }
+
+ int leftIdx = leftStart;
+ int rightIdx = rightStart;
+
+ int[] result;
+ int resultSize;
+
+ // first, pick the superset candidate and merge the two until we find
the first missing item
+ // if none found, return the superset candidate
+ {
+ int cmp;
+ boolean unfinished;
+ while (unfinished = (leftIdx < leftEnd && rightIdx < rightEnd))
+ {
+ int leftKey = left[leftIdx];
+ int rightKey = right[rightIdx];
+
+ cmp = Integer.compare(leftKey, rightKey);
+ if (cmp > 0) break;
+
+ leftIdx += 1;
+ rightIdx += cmp == 0 ? 1 : 0;
+ }
+
+ if (unfinished)
+ {
+ resultSize = leftIdx - leftStart;
+ result = buffers.getInts(resultSize + (leftEnd - leftIdx) +
(rightEnd - (rightIdx - 1)));
+ System.arraycopy(left, leftStart, result, 0, resultSize);
+ result[resultSize++] = right[rightIdx++];
+ }
+ else
+ {
+ if (rightIdx == rightEnd) // all elements matched, so can
return the other array
+ {
+ if (leftStart == 0 && leftEnd == left.length)
+ return left;
+
+ return Arrays.copyOfRange(left, leftStart, leftEnd);
+ }
+ // no elements matched or only a subset matched
+ result = buffers.getInts((leftEnd - leftStart) + (rightEnd -
rightIdx));
+ resultSize = leftIdx - leftStart;
+ System.arraycopy(left, leftStart, result, 0, resultSize);
+ }
+ }
+
+ try
+ {
+ while (leftIdx < leftEnd && rightIdx < rightEnd)
+ {
+ int leftKey = left[leftIdx];
+ int rightKey = right[rightIdx];
+ int cmp = Integer.compare(leftKey, rightKey);
+
+ int minKey;
+ if (cmp <= 0)
+ {
+ leftIdx++;
+ rightIdx += cmp == 0 ? 1 : 0;
+ minKey = leftKey;
+ }
+ else
+ {
+ rightIdx++;
+ minKey = rightKey;
+ }
+ result[resultSize++] = minKey;
+ }
+
+ while (leftIdx < leftEnd)
+ result[resultSize++] = left[leftIdx++];
+
+ while (rightIdx < rightEnd)
+ result[resultSize++] = right[rightIdx++];
+
+ return buffers.completeAndDiscard(result, resultSize);
+ }
+ catch (Throwable t)
+ {
+ buffers.discard(result, resultSize);
+ throw t;
+ }
+ }
+
// applies the update function to all entries in left, and any matching
entries in right
public static <O, T extends O> O[] linearUpdate(T[] left, int leftStart,
int leftUpdateEnd, int leftEnd, T[] right, int rightStart, int rightEnd,
AsymmetricComparator<? super T, ? super T> comparator, BiFunction<? super T, ?
super T, ? extends T> update, IntFunction<T[]> allocate)
{
@@ -1096,6 +1279,36 @@ public class SortedArrays
}
}
+ public static boolean hasIntersection(int[] left, int[] right)
+ {
+ return hasIntersection(left, 0, left.length, right, 0, right.length);
+ }
+
+ public static boolean hasIntersection(int[] left, int leftIndex, int
leftEnd, int[] right, int rightIndex, int rightEnd)
+ {
+ if (leftIndex == leftEnd || rightIndex == rightEnd)
+ return false;
+
+ while (true)
+ {
+ leftIndex = SortedArrays.exponentialSearch(left, leftIndex,
leftEnd, right[rightIndex]);
+ if (leftIndex >= 0)
+ return true;
+
+ leftIndex = -1 - leftIndex;
+ if (leftIndex == leftEnd)
+ return false;
+
+ rightIndex = SortedArrays.exponentialSearch(right, rightIndex,
rightEnd, left[leftIndex]);
+ if (rightIndex >= 0)
+ return true;
+
+ rightIndex = -1 - rightIndex;
+ if (rightIndex == rightEnd)
+ return false;
+ }
+ }
+
private static <T> T[] resizeIfNecessary(T[] input, int size)
{
if (size < input.length)
diff --git a/accord-core/src/test/java/accord/utils/SimpleBitSetTest.java
b/accord-core/src/test/java/accord/utils/SimpleBitSetTest.java
new file mode 100644
index 00000000..6c750eaa
--- /dev/null
+++ b/accord-core/src/test/java/accord/utils/SimpleBitSetTest.java
@@ -0,0 +1,173 @@
+/*
+ * 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.BitSet;
+
+import org.junit.jupiter.api.Test;
+
+import org.assertj.core.api.Assertions;
+
+import static accord.utils.Property.commands;
+import static accord.utils.Property.stateful;
+
+class SimpleBitSetTest
+{
+ private static Property.Command<State, Void, ?> get(RandomSource rs, State
state)
+ {
+ int idx = rs.nextInt(0, state.size);
+ return new Property.SimpleCommand<>("Get(" + idx + ')', s2 ->
s2.get(idx));
+ }
+
+ private static Property.Command<State, Void, ?> set(RandomSource rs, State
state)
+ {
+ int idx = rs.nextInt(0, state.size);
+ return new Property.SimpleCommand<>("Set(" + idx + ')', s2 ->
s2.set(idx));
+ }
+
+ private static Property.Command<State, Void, ?> unset(RandomSource rs,
State state)
+ {
+ int idx = rs.nextInt(0, state.size);
+ return new Property.SimpleCommand<>("Unset(" + idx + ')', s2 ->
s2.unset(idx));
+ }
+
+ private static Property.Command<State, Void, ?> clear(RandomSource rs,
State state)
+ {
+ return new Property.SimpleCommand<>("Clear", State::clear);
+ }
+
+ private static Property.Command<State, Void, ?> isEmpty(RandomSource rs,
State state)
+ {
+ return new Property.SimpleCommand<>("Is Empty", State::isEmpty);
+ }
+
+ private static Property.Command<State, Void, ?> nextSetBit(RandomSource
rs, State state)
+ {
+ int idx = rs.nextInt(0, state.size);
+ return new Property.SimpleCommand<>("NextSetBit(" + idx + ')', s2 ->
s2.nextSetBit(idx));
+ }
+
+ @Test
+ public void test()
+ {
+ stateful().withExamples(1000).check(commands(() -> State::new)
+ .add(SimpleBitSetTest::get)
+ .add(SimpleBitSetTest::set)
+ .add(SimpleBitSetTest::unset)
+ .add(SimpleBitSetTest::clear)
+ .add(SimpleBitSetTest::isEmpty)
+ .add(SimpleBitSetTest::nextSetBit)
+ .build());
+ }
+
+ private static class State implements SimpleBitSet
+ {
+ private final BitSet model;
+ private final SimpleBitSet sut;
+ private final int size;
+
+ private State(RandomSource rs)
+ {
+ this.size = rs.nextInt(1, (1 << 7) + 1); // small vs large have
roughly equal probability
+ this.model = new BitSet(size);
+ this.sut = SimpleBitSet.allocate(size);
+ }
+
+ @Override
+ public boolean get(int i)
+ {
+ boolean expected = model.get(i);
+ boolean actual = sut.get(i);
+ Assertions.assertThat(actual).isEqualTo(expected);
+ return actual;
+ }
+
+ @Override
+ public boolean set(int i)
+ {
+ boolean expected = !model.get(i);
+ model.set(i);
+ boolean actual = sut.set(i);
+
+ Assertions.assertThat(actual).isEqualTo(expected);
+
+ return actual;
+ }
+
+ @Override
+ public boolean unset(int i)
+ {
+ boolean expected = model.get(i);
+ model.clear(i);
+ boolean actual = sut.unset(i);
+
+ Assertions.assertThat(actual).isEqualTo(expected);
+
+ return actual;
+ }
+
+ @Override
+ public void clear()
+ {
+ model.clear();
+ sut.clear();
+ }
+
+ @Override
+ public boolean isEmpty()
+ {
+ boolean expected = model.isEmpty();
+ boolean actual = sut.isEmpty();
+
+ Assertions.assertThat(actual).isEqualTo(expected);
+
+ return actual;
+ }
+
+ @Override
+ public int nextSetBit(int fromIndex)
+ {
+ int expected;
+ for (expected = fromIndex; expected < size; expected++)
+ {
+ if (model.get(expected))
+ break;
+ }
+ if (expected == size)
+ expected = -1;
+ int actual = sut.nextSetBit(fromIndex);
+
+ Assertions.assertThat(actual).isEqualTo(expected);
+ return actual;
+ }
+
+ @Override
+ public int getSetBitCount()
+ {
+ return sut.getSetBitCount();
+ }
+
+ @Override
+ public String toString()
+ {
+ return sut.getClass().getSimpleName();
+ }
+ }
+}
\ No newline at end of file
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
