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 4d9e0bd33 [COLLECTIONS-885] PatriciaTrie. Prevent silent mutations,
prevents CMEs when iterating. (#672)
4d9e0bd33 is described below
commit 4d9e0bd33a050cef05b0f65289770d8bddefad3e
Author: John Griffin <[email protected]>
AuthorDate: Tue Mar 24 00:42:25 2026 -0400
[COLLECTIONS-885] PatriciaTrie. Prevent silent mutations, prevents CMEs
when iterating. (#672)
* [COLLECTIONS-885] PatriciaTrie. Prevent silent mutate when creating views
with subMap, headMap, tailMap, and prefixMap. Fixes shared usage where even
simple read access among multiple iterating threads results in
ConcurrentModificationExceptions.
* [COLLECTIONS-885] PatriciaTrie. Add threaded unit test to verify no
ConcurrentModificationExceptions thrown by concurrent iterators.
* [COLLECTIONS-885] PatriciaTrie. Rename new test method.
---
.../collections4/trie/AbstractBitwiseTrie.java | 4 +-
.../collections4/trie/AbstractPatriciaTrie.java | 155 +++++++-------
.../collections4/trie/PatriciaTrieTest.java | 231 +++++++++++++++++++++
3 files changed, 311 insertions(+), 79 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 5e7d69a2d..d03631322 100644
---
a/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java
+++
b/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java
@@ -169,9 +169,9 @@ public abstract class AbstractBitwiseTrie<K, V> extends
AbstractMap<K, V>
}
/**
- * A utility method for calling {@link KeyAnalyzer#compare(Object, Object)}
+ * A null-safe utility method for calling {@link
KeyAnalyzer#compare(Object, Object)}
*/
- final boolean compareKeys(final K key, final K other) {
+ final boolean keysAreEqual(final K key, final K other) {
if (key == null) {
return other == null;
}
diff --git
a/src/main/java/org/apache/commons/collections4/trie/AbstractPatriciaTrie.java
b/src/main/java/org/apache/commons/collections4/trie/AbstractPatriciaTrie.java
index a8a367c2c..472bbe17d 100644
---
a/src/main/java/org/apache/commons/collections4/trie/AbstractPatriciaTrie.java
+++
b/src/main/java/org/apache/commons/collections4/trie/AbstractPatriciaTrie.java
@@ -1331,24 +1331,6 @@ public abstract class AbstractPatriciaTrie<K, V> extends
AbstractBitwiseTrie<K,
* than or equal to the given key, or null if there is no such key.
*/
TrieEntry<K, V> ceilingEntry(final K key) {
- // Basically:
- // Follow the steps of adding an entry, but instead...
- //
- // - If we ever encounter a situation where we found an equal
- // key, we return it immediately.
- //
- // - If we hit an empty root, return the first iterable item.
- //
- // - If we have to add a new item, we temporarily add it,
- // find the successor to it, then remove the added item.
- //
- // These steps ensure that the returned value is either the
- // entry for the key itself, or the first entry directly after
- // the key.
-
- // TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
- // functions to perform the search.)
final int lengthInBits = lengthInBits(key);
if (lengthInBits == 0) {
@@ -1359,19 +1341,31 @@ public abstract class AbstractPatriciaTrie<K, V>
extends AbstractBitwiseTrie<K,
}
final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
- if (compareKeys(key, found.key)) {
+ if (keysAreEqual(key, found.key)) {
return found;
}
final int bitIndex = bitIndex(key, found.key);
if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
- final TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
- addEntry(added, lengthInBits);
- incrementSize(); // must increment because remove will decrement
- final TrieEntry<K, V> ceil = nextEntry(added);
- removeEntry(added);
- modCount -= 2; // we didn't really modify it.
- return ceil;
+ if (!isBitSet(key, bitIndex, lengthInBits)) {
+ // search key < found.key
+ // found is a ceiling candidate, walk backward to find the
smallest entry still >= key
+ TrieEntry<K, V> ceiling = found;
+ TrieEntry<K, V> prev = previousEntry(found);
+ while (prev != null && !prev.isEmpty() &&
getKeyAnalyzer().compare(key, prev.key) <= 0) {
+ ceiling = prev;
+ prev = previousEntry(prev);
+ }
+ return ceiling;
+ } else {
+ // search key > found.key
+ // walk forward to find the first entry.key > key
+ TrieEntry<K, V> next = nextEntry(found);
+ while (next != null && getKeyAnalyzer().compare(key, next.key)
> 0) {
+ next = nextEntry(next);
+ }
+ return next;
+ }
}
if (KeyAnalyzer.isNullBitKey(bitIndex)) {
if (!root.isEmpty()) {
@@ -1416,7 +1410,7 @@ public abstract class AbstractPatriciaTrie<K, V> extends
AbstractBitwiseTrie<K,
final K key = castKey(k);
final int lengthInBits = lengthInBits(key);
final TrieEntry<K, V> entry = getNearestEntryForKey(key, lengthInBits);
- return !entry.isEmpty() && compareKeys(key, entry.key);
+ return !entry.isEmpty() && keysAreEqual(key, entry.key);
}
/**
@@ -1463,9 +1457,6 @@ public abstract class AbstractPatriciaTrie<K, V> extends
AbstractBitwiseTrie<K,
* less than or equal to the given key, or null if there is no such key.
*/
TrieEntry<K, V> floorEntry(final K key) {
- // TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
- // functions to perform the search.)
final int lengthInBits = lengthInBits(key);
if (lengthInBits == 0) {
@@ -1476,19 +1467,30 @@ public abstract class AbstractPatriciaTrie<K, V>
extends AbstractBitwiseTrie<K,
}
final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
- if (compareKeys(key, found.key)) {
+ if (keysAreEqual(key, found.key)) {
return found;
}
final int bitIndex = bitIndex(key, found.key);
if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
- final TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
- addEntry(added, lengthInBits);
- incrementSize(); // must increment because remove will decrement
- final TrieEntry<K, V> floor = previousEntry(added);
- removeEntry(added);
- modCount -= 2; // we didn't really modify it.
- return floor;
+ if (isBitSet(key, bitIndex, lengthInBits)) {
+ TrieEntry<K, V> floor = found;
+ TrieEntry<K, V> next = nextEntry(found);
+ while (next != null && getKeyAnalyzer().compare(key, next.key)
>= 0) {
+ floor = next;
+ next = nextEntry(next);
+ }
+ return floor;
+ } else {
+ TrieEntry<K, V> prev = previousEntry(found);
+ while (prev != null && !prev.isEmpty() &&
getKeyAnalyzer().compare(key, prev.key) < 0) {
+ prev = previousEntry(prev);
+ }
+ if (prev == null || prev.isEmpty()) {
+ return null;
+ }
+ return prev;
+ }
}
if (KeyAnalyzer.isNullBitKey(bitIndex)) {
if (!root.isEmpty()) {
@@ -1561,7 +1563,7 @@ public abstract class AbstractPatriciaTrie<K, V> extends
AbstractBitwiseTrie<K,
final int lengthInBits = lengthInBits(key);
final TrieEntry<K, V> entry = getNearestEntryForKey(key, lengthInBits);
- return !entry.isEmpty() && compareKeys(key, entry.key) ? entry : null;
+ return !entry.isEmpty() && keysAreEqual(key, entry.key) ? entry : null;
}
/**
@@ -1632,9 +1634,6 @@ public abstract class AbstractPatriciaTrie<K, V> extends
AbstractBitwiseTrie<K,
* or null if no such entry exists.
*/
TrieEntry<K, V> higherEntry(final K key) {
- // TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
- // functions to perform the search.)
final int lengthInBits = lengthInBits(key);
if (lengthInBits == 0) {
@@ -1651,19 +1650,27 @@ public abstract class AbstractPatriciaTrie<K, V>
extends AbstractBitwiseTrie<K,
}
final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
- if (compareKeys(key, found.key)) {
+ if (keysAreEqual(key, found.key)) {
return nextEntry(found);
}
final int bitIndex = bitIndex(key, found.key);
if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
- final TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
- addEntry(added, lengthInBits);
- incrementSize(); // must increment because remove will decrement
- final TrieEntry<K, V> ceil = nextEntry(added);
- removeEntry(added);
- modCount -= 2; // we didn't really modify it.
- return ceil;
+ if (!isBitSet(key, bitIndex, lengthInBits)) {
+ TrieEntry<K, V> ceiling = found;
+ TrieEntry<K, V> prev = previousEntry(found);
+ while (prev != null && !prev.isEmpty() &&
getKeyAnalyzer().compare(key, prev.key) <= 0) {
+ ceiling = prev;
+ prev = previousEntry(prev);
+ }
+ return ceiling;
+ } else {
+ TrieEntry<K, V> next = nextEntry(found);
+ while (next != null && getKeyAnalyzer().compare(key, next.key)
> 0) {
+ next = nextEntry(next);
+ }
+ return next;
+ }
}
if (KeyAnalyzer.isNullBitKey(bitIndex)) {
if (!root.isEmpty()) {
@@ -1729,23 +1736,6 @@ public abstract class AbstractPatriciaTrie<K, V> extends
AbstractBitwiseTrie<K,
* strictly less than the given key, or null if there is no such key.
*/
TrieEntry<K, V> lowerEntry(final K key) {
- // Basically:
- // Follow the steps of adding an entry, but instead...
- //
- // - If we ever encounter a situation where we found an equal
- // key, we return it's previousEntry immediately.
- //
- // - If we hit root (empty or not), return null.
- //
- // - If we have to add a new item, we temporarily add it,
- // find the previousEntry to it, then remove the added item.
- //
- // These steps ensure that the returned value is always just before
- // the key or null (if there was nothing before it).
-
- // TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
- // functions to perform the search.)
final int lengthInBits = lengthInBits(key);
if (lengthInBits == 0) {
@@ -1753,19 +1743,30 @@ public abstract class AbstractPatriciaTrie<K, V>
extends AbstractBitwiseTrie<K,
}
final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
- if (compareKeys(key, found.key)) {
+ if (keysAreEqual(key, found.key)) {
return previousEntry(found);
}
final int bitIndex = bitIndex(key, found.key);
if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
- final TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
- addEntry(added, lengthInBits);
- incrementSize(); // must increment because remove will decrement
- final TrieEntry<K, V> prior = previousEntry(added);
- removeEntry(added);
- modCount -= 2; // we didn't really modify it.
- return prior;
+ if (isBitSet(key, bitIndex, lengthInBits)) {
+ TrieEntry<K, V> floor = found;
+ TrieEntry<K, V> next = nextEntry(found);
+ while (next != null && getKeyAnalyzer().compare(key, next.key)
>= 0) {
+ floor = next;
+ next = nextEntry(next);
+ }
+ return floor;
+ } else {
+ TrieEntry<K, V> prev = previousEntry(found);
+ while (prev != null && !prev.isEmpty() &&
getKeyAnalyzer().compare(key, prev.key) < 0) {
+ prev = previousEntry(prev);
+ }
+ if (prev == null || prev.isEmpty()) {
+ return null;
+ }
+ return prev;
+ }
}
if (KeyAnalyzer.isNullBitKey(bitIndex)) {
return null;
@@ -2028,7 +2029,7 @@ public abstract class AbstractPatriciaTrie<K, V> extends
AbstractBitwiseTrie<K,
}
final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
- if (compareKeys(key, found.key)) {
+ if (keysAreEqual(key, found.key)) {
if (found.isEmpty()) { // <- must be the root
incrementSize();
} else {
@@ -2104,7 +2105,7 @@ public abstract class AbstractPatriciaTrie<K, V> extends
AbstractBitwiseTrie<K,
TrieEntry<K, V> path = root;
while (true) {
if (current.bitIndex <= path.bitIndex) {
- if (!current.isEmpty() && compareKeys(key, current.key)) {
+ if (!current.isEmpty() && keysAreEqual(key, current.key)) {
return removeEntry(current);
}
return null;
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 d06325741..e1c754760 100644
--- a/src/test/java/org/apache/commons/collections4/trie/PatriciaTrieTest.java
+++ b/src/test/java/org/apache/commons/collections4/trie/PatriciaTrieTest.java
@@ -33,6 +33,14 @@ import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.SortedMap;
+import java.util.concurrent.CyclicBarrier;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.concurrent.Future;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.TimeoutException;
+
import org.apache.commons.collections4.Trie;
import org.apache.commons.collections4.map.AbstractSortedMapTest;
@@ -437,6 +445,229 @@ public class PatriciaTrieTest<V> extends
AbstractSortedMapTest<String, V> {
assertTrue(trie.prefixMap(prefixString).containsKey(longerString));
}
+ @Test
+ void testSubmap() {
+ 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");
+
+ // subMap should be entire trie
+ SortedMap<String, String> subMap = trie.subMap("a", "z");
+ assertEquals(5, subMap.size());
+ assertEquals("ga", subMap.get("ga"));
+ assertEquals("gb", subMap.get("gb"));
+ assertEquals("gc", subMap.get("gc"));
+ assertEquals("gd", subMap.get("gd"));
+ assertEquals("ge", subMap.get("ge"));
+
+ // subMap should be empty
+ subMap = trie.subMap("a", "a");
+ assertEquals(0, subMap.size());
+
+ // subMap() is not inclusive of the second key
+ // subMap should be 4 entries only - "ge" excluded
+ subMap = trie.subMap("ga", "ge");
+ assertEquals(4, subMap.size());
+ assertEquals("ga", subMap.get("ga"));
+ assertEquals("gb", subMap.get("gb"));
+ assertEquals("gc", subMap.get("gc"));
+ assertEquals("gd", subMap.get("gd"));
+ assertNull(subMap.get("ge"));
+
+ // subMap should be 5 entries
+ subMap = trie.subMap("ga", "gf");
+ assertEquals(5, subMap.size());
+ assertEquals("ga", subMap.get("ga"));
+ assertEquals("gb", subMap.get("gb"));
+ assertEquals("gc", subMap.get("gc"));
+ assertEquals("gd", subMap.get("gd"));
+ assertEquals("ge", subMap.get("ge"));
+
+ // subMap should be 4 entries - "ga" excluded
+ subMap = trie.subMap("gb", "z");
+ assertEquals(4, subMap.size());
+ assertNull(subMap.get("ga"));
+ assertEquals("gb", subMap.get("gb"));
+ assertEquals("gc", subMap.get("gc"));
+ assertEquals("gd", subMap.get("gd"));
+ assertEquals("ge", subMap.get("ge"));
+
+
+ // subMap should be 1 entry - "gc" only
+ subMap = trie.subMap("gc", "gd");
+ assertEquals(1, subMap.size());
+ assertNull(subMap.get("ga"));
+ assertNull(subMap.get("gb"));
+ assertEquals("gc", subMap.get("gc"));
+ assertNull(subMap.get("gd"));
+ assertNull(subMap.get("ge"));
+ }
+
+ @Test
+ void testTailMap() {
+ 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");
+
+ // tailMap should be entire trie
+ SortedMap<String, String> tailMap = trie.tailMap("a");
+ assertEquals(5, tailMap.size());
+ assertEquals("ga", tailMap.get("ga"));
+ assertEquals("gb", tailMap.get("gb"));
+ assertEquals("gc", tailMap.get("gc"));
+ assertEquals("gd", tailMap.get("gd"));
+ assertEquals("ge", tailMap.get("ge"));
+
+ // tailMap should be empty
+ tailMap = trie.tailMap("z");
+ assertEquals(0, tailMap.size());
+
+ // tailMap is inclusive of the search key
+ // tailMap should be the entire trie
+ tailMap = trie.tailMap("ga");
+ assertEquals(5, tailMap.size());
+ assertEquals("ga", tailMap.get("ga"));
+ assertEquals("gb", tailMap.get("gb"));
+ assertEquals("gc", tailMap.get("gc"));
+ assertEquals("gd", tailMap.get("gd"));
+ assertEquals("ge", tailMap.get("ge"));
+
+ // tailMap should be single entry "ge"
+ tailMap = trie.tailMap("ge");
+ assertEquals(1, tailMap.size());
+ assertNull(tailMap.get("ga"));
+ assertNull(tailMap.get("gb"));
+ assertNull(tailMap.get("gc"));
+ assertNull(tailMap.get("gd"));
+ 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(
