This is an automated email from the ASF dual-hosted git repository. dcapwell pushed a commit to branch CASSANDRA-21077 in repository https://gitbox.apache.org/repos/asf/cassandra-accord.git
commit 67820204aeac10ffafbfc29f262798077bc190dd Author: David Capwell <[email protected]> AuthorDate: Fri Dec 12 15:59:28 2025 -0800 done --- .../src/main/java/accord/utils/LargeBitSet.java | 28 ++++++++++++--- .../src/main/java/accord/utils/SmallBitSet.java | 23 +++++++++++-- .../test/java/accord/utils/SimpleBitSetTest.java | 40 ++++++++++++++++++++++ 3 files changed, 84 insertions(+), 7 deletions(-) diff --git a/accord-core/src/main/java/accord/utils/LargeBitSet.java b/accord-core/src/main/java/accord/utils/LargeBitSet.java index 5d519e4e..794a1881 100644 --- a/accord-core/src/main/java/accord/utils/LargeBitSet.java +++ b/accord-core/src/main/java/accord/utils/LargeBitSet.java @@ -25,6 +25,8 @@ import static java.lang.Long.numberOfTrailingZeros; public class LargeBitSet implements SimpleBitSet { + private static final int UNKNOWN = -1; + public static class SerializationSupport { public static long[] getArray(LargeBitSet bs) @@ -55,7 +57,7 @@ public class LargeBitSet implements SimpleBitSet { Arrays.fill(bits, 0, size / 64, -1L); if ((size & 63) != 0) - bits[indexOf(size - 1)] = -1L >>> (64 - (size & 63)); + bits[indexOfSafe(size - 1)] = -1L >>> (64 - (size & 63)); count = size; } } @@ -87,9 +89,10 @@ public class LargeBitSet implements SimpleBitSet Arrays.fill(bits, 0, length, 0L); } + @Override public boolean set(int i) { - int index = indexOf(i); + int index = indexOfSafe(i); long bit = bit(i); if (0 != (bits[index] & bit)) return false; @@ -98,13 +101,14 @@ public class LargeBitSet implements SimpleBitSet return true; } + @Override public void setRange(int fromInclusive, int toExclusive) { Invariants.requireArgument(fromInclusive <= toExclusive, "from > to (%s > %s)", fromInclusive, toExclusive); if (fromInclusive == toExclusive) return; - int fromIndex = fromInclusive >>> 6; + int fromIndex = indexOfSafe(fromInclusive); int toIndex = (toExclusive + 63) >>> 6; if (fromIndex + 1 == toIndex) { @@ -163,9 +167,10 @@ public class LargeBitSet implements SimpleBitSet count += Long.bitCount(nextBits) - Long.bitCount(prevBits); } + @Override public boolean unset(int i) { - int index = indexOf(i); + int index = indexOfSafe(i); long bit = bit(i); if (0 == (bits[index] & bit)) return false; @@ -174,9 +179,12 @@ public class LargeBitSet implements SimpleBitSet return true; } + @Override public final boolean get(int i) { int index = indexOf(i); + if (index == UNKNOWN) + return false; long bit = bit(i); return 0 != (bits[index] & bit); } @@ -320,7 +328,9 @@ public class LargeBitSet implements SimpleBitSet private int nextSetBitInternal(int i, int exclIndexBound, int ifNotFound) { Invariants.requireArgument(i >= 0); - Invariants.requireArgument(i <= size()); + + if (i > size()) + return ifNotFound; if (count == 0) return ifNotFound; @@ -443,6 +453,14 @@ public class LargeBitSet implements SimpleBitSet { int index = i >>> 6; if (index >= length) + return UNKNOWN; + return index; + } + + private int indexOfSafe(int i) + { + int index = indexOf(i); + if (index == UNKNOWN) throw new IndexOutOfBoundsException(String.format("%d >= %d", index, length)); return index; } diff --git a/accord-core/src/main/java/accord/utils/SmallBitSet.java b/accord-core/src/main/java/accord/utils/SmallBitSet.java index 75c12171..b6b0f40b 100644 --- a/accord-core/src/main/java/accord/utils/SmallBitSet.java +++ b/accord-core/src/main/java/accord/utils/SmallBitSet.java @@ -40,9 +40,22 @@ public class SmallBitSet implements SimpleBitSet return bits; } + private static long bitSafe(int i) + { + validateIndex(i); + return bit(i); + } + + private static void validateIndex(int i) + { + if (i >= 64 || i < 0) + throw new IndexOutOfBoundsException("Unable to access bit " + i + "; must be between 0 and 63"); + } + + @Override public boolean set(int i) { - long bit = bit(i); + long bit = bitSafe(i); boolean result = 0 == (bits & bit); bits |= bit; return result; @@ -51,6 +64,7 @@ public class SmallBitSet implements SimpleBitSet @Override public void setRange(int fromInclusive, int toExclusive) { + validateIndex(fromInclusive); Invariants.requireArgument(fromInclusive <= toExclusive, "from > to (%s > %s)", fromInclusive, toExclusive); if (fromInclusive == toExclusive) return; @@ -59,15 +73,18 @@ public class SmallBitSet implements SimpleBitSet bits |= maskTo & (-1L << fromInclusive); } + @Override public boolean get(int i) { + if (i >= 64) return false; long bit = bit(i); return 0 != (bits & bit); } + @Override public boolean unset(int i) { - long bit = bit(i); + long bit = bitSafe(i); boolean result = 0 != (bits & bit); bits &= ~bit; return result; @@ -88,6 +105,8 @@ public class SmallBitSet implements SimpleBitSet @Override public int nextSetBit(int fromIndex) { + if (fromIndex >= 64) + return -1; long bits = this.bits & bitsEqualOrGreater(fromIndex); if (bits == 0) return -1; diff --git a/accord-core/src/test/java/accord/utils/SimpleBitSetTest.java b/accord-core/src/test/java/accord/utils/SimpleBitSetTest.java index f0609d46..02af685c 100644 --- a/accord-core/src/test/java/accord/utils/SimpleBitSetTest.java +++ b/accord-core/src/test/java/accord/utils/SimpleBitSetTest.java @@ -20,6 +20,7 @@ package accord.utils; import java.util.BitSet; +import java.util.List; import org.junit.jupiter.api.Test; @@ -101,6 +102,45 @@ class SimpleBitSetTest .build()); } + @Test + public void outOfRange() + { + SmallBitSet model = new SmallBitSet(); + LargeBitSet target = new LargeBitSet(64); + + for (var set : List.of(model, target)) + set.setRange(0, 64); + + // get methods do not reject, but return false or -1 + Assertions.assertThat(target.getSetBitCount()).isEqualTo(model.getSetBitCount()); + Assertions.assertThat(target.isEmpty()).isEqualTo(model.isEmpty()); + + for (int index : new int[] {64, 65, Integer.MAX_VALUE}) + { + Assertions.assertThat(target.get(index)) + .describedAs("get(%s)", index) + .isEqualTo(model.get(index)) + .isEqualTo(false); + Assertions.assertThat(target.nextSetBit(index)) + .describedAs("nextSetBit(%s)", index) + .isEqualTo(model.nextSetBit(index)) + .isEqualTo(-1); + } + + // set methods reject + for (int index : new int[] {64, 65, Integer.MAX_VALUE}) + { + Assertions.assertThatThrownBy(() -> target.set(index)); + Assertions.assertThatThrownBy(() -> model.set(index)); + + Assertions.assertThatThrownBy(() -> target.setRange(index, 100)); + Assertions.assertThatThrownBy(() -> model.setRange(index, 100)); + + Assertions.assertThatThrownBy(() -> target.unset(index)); + Assertions.assertThatThrownBy(() -> model.unset(index)); + } + } + private static class State implements SimpleBitSet { private final BitSet model; --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
