This is an automated email from the ASF dual-hosted git repository.
ggregory pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-collections.git
The following commit(s) were added to refs/heads/master by this push:
new aefd2691e Sort members
aefd2691e is described below
commit aefd2691e92be194f4a134df67979dc41d9ca925
Author: Gary Gregory <[email protected]>
AuthorDate: Tue Mar 24 08:16:36 2026 -0700
Sort members
---
.../collections4/trie/AbstractBitwiseTrie.java | 28 +--
.../collections4/trie/PatriciaTrieTest.java | 240 ++++++++++-----------
2 files changed, 134 insertions(+), 134 deletions(-)
diff --git
a/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java
b/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java
index d03631322..2b070ac67 100644
---
a/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java
+++
b/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java
@@ -168,20 +168,6 @@ public abstract class AbstractBitwiseTrie<K, V> extends
AbstractMap<K, V>
return (K) key;
}
- /**
- * A null-safe utility method for calling {@link
KeyAnalyzer#compare(Object, Object)}
- */
- final boolean keysAreEqual(final K key, final K other) {
- if (key == null) {
- return other == null;
- }
- if (other == null) {
- return false;
- }
-
- return keyAnalyzer.compare(key, other) == 0;
- }
-
/**
* Gets the {@link KeyAnalyzer} that constructed the {@link Trie}.
*
@@ -203,6 +189,20 @@ public abstract class AbstractBitwiseTrie<K, V> extends
AbstractMap<K, V>
return keyAnalyzer.isBitSet(key, bitIndex, lengthInBits);
}
+ /**
+ * A null-safe utility method for calling {@link
KeyAnalyzer#compare(Object, Object)}
+ */
+ final boolean keysAreEqual(final K key, final K other) {
+ if (key == null) {
+ return other == null;
+ }
+ if (other == null) {
+ return false;
+ }
+
+ return keyAnalyzer.compare(key, other) == 0;
+ }
+
/**
* Returns the length of the given key in bits
*
diff --git
a/src/test/java/org/apache/commons/collections4/trie/PatriciaTrieTest.java
b/src/test/java/org/apache/commons/collections4/trie/PatriciaTrieTest.java
index e1c754760..516e6d2bc 100644
--- a/src/test/java/org/apache/commons/collections4/trie/PatriciaTrieTest.java
+++ b/src/test/java/org/apache/commons/collections4/trie/PatriciaTrieTest.java
@@ -69,6 +69,125 @@ public class PatriciaTrieTest<V> extends
AbstractSortedMapTest<String, V> {
return new PatriciaTrie<>();
}
+ @Test
+ void testConcurrentTrieIterationAndSubMapIteration() throws
InterruptedException, ExecutionException, TimeoutException {
+ final PatriciaTrie<Integer> trie = new PatriciaTrie<>();
+ // populate with enough entries to make concurrent collisions likely
+ // call subMap with both keys missing to ensure phantom node addition
done twice
+ final int subKeyFirst = 1;
+ final int subKeySecond = 4;
+ final String subKeyFirstStr = String.format("key%04d", subKeyFirst);
+ final String subKeySecondStr = String.format("key%04d", subKeySecond);
+ for (int i = 0; i <= 501; i++) {
+ if (i != subKeyFirst && i != subKeySecond) {
+ trie.put(String.format("key%04d", i), i);
+ }
+ }
+
+ final int iterations = 100;
+ final CyclicBarrier barrier = new CyclicBarrier(2);
+
+ final ExecutorService executor = Executors.newFixedThreadPool(2);
+ try {
+ // Thread 1: repeatedly iterate the entire trie
+ final Future<?> iteratorTask = executor.submit(() -> {
+ barrier.await(1, TimeUnit.SECONDS);
+ for (int i = 0; i < iterations &&
!Thread.currentThread().isInterrupted(); i++) {
+ int count = 0;
+ for (final Map.Entry<String, Integer> entry :
trie.entrySet()) {
+ // verify the iterated keys and values are not from
the phantom node
+ assertNotNull(entry.getKey());
+ assertNotNull(entry.getValue());
+ count++;
+ }
+ assertEquals(500, count, "Iterator skipped or duplicated
entries");
+ }
+ return null;
+ });
+
+ // Thread 2: repeatedly create and iterate subMap views
+ // (this triggers ceilingEntry with keys NOT in the trie)
+ final Future<?> subMapTask = executor.submit(() -> {
+ barrier.await(1, TimeUnit.SECONDS);
+ for (int i = 0; i < iterations &&
!Thread.currentThread().isInterrupted(); i++) {
+ // Use boundary keys that do NOT exist in the trie
+ // to force the ceiling/floor walk algorithm
+ final SortedMap<String, Integer> sub =
trie.subMap(subKeyFirstStr, subKeySecondStr);
+ int count = 0;
+ for (final Map.Entry<String, Integer> entry :
sub.entrySet()) {
+ // verify the iterated keys and values are not from
the phantom node
+ assertNotNull(entry.getKey());
+ assertNotNull(entry.getValue());
+ count++;
+ }
+ assertEquals(2, count, "subMap returned wrong number of
entries");
+ }
+ return null;
+ });
+
+ // get() unwraps ExecutionException
+ // if either task threw an exception or an assertion Error, (or
any Throwable),
+ // then the original exception propagates with its full stacktrace
+ // and TimeoutException surfaces hangs
+ subMapTask.get(10, TimeUnit.SECONDS);
+ iteratorTask.get(10, TimeUnit.SECONDS);
+ } finally {
+ executor.shutdownNow();
+ executor.awaitTermination(5, TimeUnit.SECONDS);
+ }
+ }
+
+ @Test
+ void testHeadMap() {
+ final PatriciaTrie<String> trie = new PatriciaTrie<>();
+ trie.put("ga", "ga");
+ trie.put("gb", "gb");
+ trie.put("gc", "gc");
+ trie.put("gd", "gd");
+ trie.put("ge", "ge");
+
+ // headMap should be entire trie
+ SortedMap<String, String> headMap = trie.headMap("z");
+ assertEquals(5, headMap.size());
+ assertEquals("ga", headMap.get("ga"));
+ assertEquals("gb", headMap.get("gb"));
+ assertEquals("gc", headMap.get("gc"));
+ assertEquals("gd", headMap.get("gd"));
+ assertEquals("ge", headMap.get("ge"));
+
+ // headMap should be empty
+ headMap = trie.headMap("a");
+ assertEquals(0, headMap.size());
+
+ // headMap() is not inclusive of the key
+ // headMap should be 4 entries only - "ge" excluded
+ headMap = trie.headMap("ge");
+ assertEquals(4, headMap.size());
+ assertEquals("ga", headMap.get("ga"));
+ assertEquals("gb", headMap.get("gb"));
+ assertEquals("gc", headMap.get("gc"));
+ assertEquals("gd", headMap.get("gd"));
+ assertNull(headMap.get("ge"));
+
+ // headMap should be 5 entries
+ headMap = trie.headMap("gf");
+ assertEquals(5, headMap.size());
+ assertEquals("ga", headMap.get("ga"));
+ assertEquals("gb", headMap.get("gb"));
+ assertEquals("gc", headMap.get("gc"));
+ assertEquals("gd", headMap.get("gd"));
+ assertEquals("ge", headMap.get("ge"));
+
+ // headMap should be 1 entry - "ga" only
+ headMap = trie.headMap("gb");
+ assertEquals(1, headMap.size());
+ assertEquals("ga", headMap.get("ga"));
+ assertNull(headMap.get("gb"));
+ assertNull(headMap.get("gc"));
+ assertNull(headMap.get("gd"));
+ assertNull(headMap.get("ge"));
+ }
+
@Test
void testPrefixMap() {
final PatriciaTrie<String> trie = new PatriciaTrie<>();
@@ -506,6 +625,7 @@ public class PatriciaTrieTest<V> extends
AbstractSortedMapTest<String, V> {
assertNull(subMap.get("ge"));
}
+
@Test
void testTailMap() {
final PatriciaTrie<String> trie = new PatriciaTrie<>();
@@ -548,126 +668,6 @@ public class PatriciaTrieTest<V> extends
AbstractSortedMapTest<String, V> {
assertEquals("ge", tailMap.get("ge"));
}
- @Test
- void testHeadMap() {
- final PatriciaTrie<String> trie = new PatriciaTrie<>();
- trie.put("ga", "ga");
- trie.put("gb", "gb");
- trie.put("gc", "gc");
- trie.put("gd", "gd");
- trie.put("ge", "ge");
-
- // headMap should be entire trie
- SortedMap<String, String> headMap = trie.headMap("z");
- assertEquals(5, headMap.size());
- assertEquals("ga", headMap.get("ga"));
- assertEquals("gb", headMap.get("gb"));
- assertEquals("gc", headMap.get("gc"));
- assertEquals("gd", headMap.get("gd"));
- assertEquals("ge", headMap.get("ge"));
-
- // headMap should be empty
- headMap = trie.headMap("a");
- assertEquals(0, headMap.size());
-
- // headMap() is not inclusive of the key
- // headMap should be 4 entries only - "ge" excluded
- headMap = trie.headMap("ge");
- assertEquals(4, headMap.size());
- assertEquals("ga", headMap.get("ga"));
- assertEquals("gb", headMap.get("gb"));
- assertEquals("gc", headMap.get("gc"));
- assertEquals("gd", headMap.get("gd"));
- assertNull(headMap.get("ge"));
-
- // headMap should be 5 entries
- headMap = trie.headMap("gf");
- assertEquals(5, headMap.size());
- assertEquals("ga", headMap.get("ga"));
- assertEquals("gb", headMap.get("gb"));
- assertEquals("gc", headMap.get("gc"));
- assertEquals("gd", headMap.get("gd"));
- assertEquals("ge", headMap.get("ge"));
-
- // headMap should be 1 entry - "ga" only
- headMap = trie.headMap("gb");
- assertEquals(1, headMap.size());
- assertEquals("ga", headMap.get("ga"));
- assertNull(headMap.get("gb"));
- assertNull(headMap.get("gc"));
- assertNull(headMap.get("gd"));
- assertNull(headMap.get("ge"));
- }
-
-
- @Test
- void testConcurrentTrieIterationAndSubMapIteration() throws
InterruptedException, ExecutionException, TimeoutException {
- final PatriciaTrie<Integer> trie = new PatriciaTrie<>();
- // populate with enough entries to make concurrent collisions likely
- // call subMap with both keys missing to ensure phantom node addition
done twice
- final int subKeyFirst = 1;
- final int subKeySecond = 4;
- final String subKeyFirstStr = String.format("key%04d", subKeyFirst);
- final String subKeySecondStr = String.format("key%04d", subKeySecond);
- for (int i = 0; i <= 501; i++) {
- if (i != subKeyFirst && i != subKeySecond) {
- trie.put(String.format("key%04d", i), i);
- }
- }
-
- final int iterations = 100;
- final CyclicBarrier barrier = new CyclicBarrier(2);
-
- final ExecutorService executor = Executors.newFixedThreadPool(2);
- try {
- // Thread 1: repeatedly iterate the entire trie
- final Future<?> iteratorTask = executor.submit(() -> {
- barrier.await(1, TimeUnit.SECONDS);
- for (int i = 0; i < iterations &&
!Thread.currentThread().isInterrupted(); i++) {
- int count = 0;
- for (final Map.Entry<String, Integer> entry :
trie.entrySet()) {
- // verify the iterated keys and values are not from
the phantom node
- assertNotNull(entry.getKey());
- assertNotNull(entry.getValue());
- count++;
- }
- assertEquals(500, count, "Iterator skipped or duplicated
entries");
- }
- return null;
- });
-
- // Thread 2: repeatedly create and iterate subMap views
- // (this triggers ceilingEntry with keys NOT in the trie)
- final Future<?> subMapTask = executor.submit(() -> {
- barrier.await(1, TimeUnit.SECONDS);
- for (int i = 0; i < iterations &&
!Thread.currentThread().isInterrupted(); i++) {
- // Use boundary keys that do NOT exist in the trie
- // to force the ceiling/floor walk algorithm
- final SortedMap<String, Integer> sub =
trie.subMap(subKeyFirstStr, subKeySecondStr);
- int count = 0;
- for (final Map.Entry<String, Integer> entry :
sub.entrySet()) {
- // verify the iterated keys and values are not from
the phantom node
- assertNotNull(entry.getKey());
- assertNotNull(entry.getValue());
- count++;
- }
- assertEquals(2, count, "subMap returned wrong number of
entries");
- }
- return null;
- });
-
- // get() unwraps ExecutionException
- // if either task threw an exception or an assertion Error, (or
any Throwable),
- // then the original exception propagates with its full stacktrace
- // and TimeoutException surfaces hangs
- subMapTask.get(10, TimeUnit.SECONDS);
- iteratorTask.get(10, TimeUnit.SECONDS);
- } finally {
- executor.shutdownNow();
- executor.awaitTermination(5, TimeUnit.SECONDS);
- }
- }
-
// void testCreate() throws Exception {
// resetEmpty();
// writeExternalFormToDisk(
