This is an automated email from the ASF dual-hosted git repository.
dcapwell 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 1192d253 Accord: when Keys has token conflicts, this lead to issues
with Routes and containsAll (#182)
1192d253 is described below
commit 1192d253f36d072b056f1d16e292bdf202018758
Author: dcapwell <[email protected]>
AuthorDate: Sat Mar 15 14:55:05 2025 -0700
Accord: when Keys has token conflicts, this lead to issues with Routes and
containsAll (#182)
patch by Benedict Elliott Smith, David Capwell; reviewed by Benedict
Elliott Smith for CASSANDRA-20443
---
.../main/java/accord/primitives/AbstractKeys.java | 5 +--
.../src/main/java/accord/primitives/Keys.java | 5 ++-
accord-core/src/test/java/accord/KeysTest.java | 36 ++++++++++++++++++++++
.../src/test/java/accord/impl/IntHashKey.java | 23 ++++++++++++--
accord-core/src/test/java/accord/utils/Gens.java | 12 ++++++++
5 files changed, 76 insertions(+), 5 deletions(-)
diff --git a/accord-core/src/main/java/accord/primitives/AbstractKeys.java
b/accord-core/src/main/java/accord/primitives/AbstractKeys.java
index 637072ec..376ade8a 100644
--- a/accord-core/src/main/java/accord/primitives/AbstractKeys.java
+++ b/accord-core/src/main/java/accord/primitives/AbstractKeys.java
@@ -312,8 +312,9 @@ public abstract class AbstractKeys<K extends RoutableKey>
implements Iterable<K>
else
{
copy = new RoutingKey[keys.length];
- for (int i = 0; i < keys.length; i++)
- copy[i] = keys[i].toUnseekable();
+ int resultCount = copyToRoutingKeys(keys, 0, copy, 0, keys.length);
+ if (resultCount < copy.length)
+ copy = Arrays.copyOf(copy, resultCount);
}
int insertPos = Arrays.binarySearch(copy, withKey);
diff --git a/accord-core/src/main/java/accord/primitives/Keys.java
b/accord-core/src/main/java/accord/primitives/Keys.java
index 5304b737..2b57254c 100644
--- a/accord-core/src/main/java/accord/primitives/Keys.java
+++ b/accord-core/src/main/java/accord/primitives/Keys.java
@@ -94,7 +94,10 @@ public class Keys extends AbstractKeys<Key> implements
Seekables<Key, Keys>
@Override
public final boolean containsAll(AbstractUnseekableKeys that)
{
- return that.size() == SortedArrays.foldlIntersection(0,
RoutableKey::compareAsRoutingKey, that.keys, 0, that.keys.length, keys, 0,
keys.length, (k, p, v, l, r) -> v + 1, 0, 0, 0);
+ return that.size() == SortedArrays.foldlIntersection(0,
RoutableKey::compareAsRoutingKey,
+ keys, 0,
keys.length,
+ that.keys, 0,
that.keys.length,
+ (k, p, v, l, r)
-> v + 1, 0, 0, 0);
}
@Override
diff --git a/accord-core/src/test/java/accord/KeysTest.java
b/accord-core/src/test/java/accord/KeysTest.java
index 3538e21a..f25dc8c3 100644
--- a/accord-core/src/test/java/accord/KeysTest.java
+++ b/accord-core/src/test/java/accord/KeysTest.java
@@ -22,6 +22,7 @@ import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
+import java.util.TreeSet;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.IntFunction;
@@ -29,6 +30,7 @@ import java.util.stream.IntStream;
import accord.api.Key;
import accord.api.RoutingKey;
+import accord.impl.IntHashKey;
import accord.impl.IntKey;
import accord.impl.IntKey.Raw;
import accord.primitives.AbstractKeys;
@@ -40,6 +42,7 @@ import accord.primitives.Routables;
import accord.primitives.RoutingKeys;
import accord.utils.Gen;
import accord.utils.Gens;
+import accord.utils.RandomSource;
import accord.utils.RandomTestRunner;
import org.agrona.collections.IntHashSet;
@@ -315,4 +318,37 @@ public class KeysTest
return a;
});
}
+
+ @Test
+ public void containsAllWithoutConflict()
+ {
+ Gen.IntGen valueGen = Gens.ints().between(0, Short.MAX_VALUE);
+ Gen<Key> keyGen = rs -> IntKey.key(valueGen.nextInt(rs));
+ qt().check(rs -> testContains(keyGen, rs));
+ }
+
+ @Test
+ public void containsAllWithConflict()
+ {
+ Gen.IntGen valueGen = Gens.ints().between(0, Short.MAX_VALUE);
+ Gen.IntGen hashGen = Gens.ints().between(0, 3);
+ Gen<Key> keyGen = rs -> IntHashKey.key(valueGen.nextInt(rs),
hashGen.nextInt(rs));
+ qt().check(rs -> testContains(keyGen, rs));
+ }
+
+ private static void testContains(Gen<Key> keyGen, RandomSource rs)
+ {
+ int numKeys = rs.nextInt(2, 100);
+ List<Key> keysList =
Gens.lists(keyGen).unique().ofSize(numKeys).next(rs);
+ Keys keys = Keys.ofUnique(keysList.toArray(Key[]::new));
+ assert keys.size() == keysList.size();
+ TreeSet<RoutingKey> tokens = new TreeSet<>();
+ for (var k : keys)
+ tokens.add(k.toUnseekable());
+ Gen<List<RoutingKey>> selectGen = Gens.select(new ArrayList<>(tokens));
+ for (int i = 0; i < 1000; i++)
+ {
+
Assertions.assertTrue(keys.containsAll(RoutingKeys.of(selectGen.next(rs).toArray(RoutingKey[]::new))));
+ }
+ }
}
diff --git a/accord-core/src/test/java/accord/impl/IntHashKey.java
b/accord-core/src/test/java/accord/impl/IntHashKey.java
index d248d923..c55ccba6 100644
--- a/accord-core/src/test/java/accord/impl/IntHashKey.java
+++ b/accord-core/src/test/java/accord/impl/IntHashKey.java
@@ -116,6 +116,11 @@ public abstract class IntHashKey implements RoutableKey
super(key);
}
+ public Key(int key, int token)
+ {
+ super(key, token);
+ }
+
@Override
public Object suffix()
{
@@ -208,11 +213,22 @@ public abstract class IntHashKey implements RoutableKey
this.hash = hash;
}
+ private IntHashKey(int key, int hash)
+ {
+ this.key = key;
+ this.hash = hash;
+ }
+
public static Key key(int k)
{
return new Key(k);
}
+ public static Key key(int k, int hash)
+ {
+ return new Key(k, hash);
+ }
+
public static Hash forHash(int hash)
{
return new Hash(hash);
@@ -291,8 +307,11 @@ public abstract class IntHashKey implements RoutableKey
}
@Override
- public int compareTo(@Nonnull RoutableKey that)
+ public int compareTo(@Nonnull RoutableKey other)
{
- return Integer.compare(this.hash, ((IntHashKey)that).hash);
+ IntHashKey that = (IntHashKey) other;
+ int rc = Integer.compare(this.hash, that.hash);
+ if (rc != 0) return rc;
+ return Integer.compare(this.key, that.key);
}
}
diff --git a/accord-core/src/test/java/accord/utils/Gens.java
b/accord-core/src/test/java/accord/utils/Gens.java
index 27dc5525..d3adac61 100644
--- a/accord-core/src/test/java/accord/utils/Gens.java
+++ b/accord-core/src/test/java/accord/utils/Gens.java
@@ -285,6 +285,18 @@ public class Gens {
};
}
+ public static <T> Gen<List<T>> select(List<T> input)
+ {
+ return rs -> {
+ int size = rs.nextInt(0, input.size() + 1);
+ List<T> remaining = new ArrayList<>(input);
+ List<T> list = new ArrayList<>(size);
+ for (int i = 0; i < size; i++)
+ list.add(remaining.remove(rs.nextInt(0, remaining.size())));
+ return list;
+ };
+ }
+
public static Gen<Gen.IntGen> randomWeights(int[] array)
{
return rs -> {
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
