griffinjm opened a new pull request, #672: URL: https://github.com/apache/commons-collections/pull/672
Some methods in AbstractPatriciaTrie use a pattern where they silently mutate the trie when searching for a key which is not an exact match for an existing key in the Trie. Said methods are invoked by subMap/tailMap/headMap/prefixMap under the hood. This results in CMEs for even simple shared read access. ``` ceilingEntry() floorEntry() higherEntry() lowerEntry() operations: 1. insert a phantom node into the trie with the search key 2. increment the modCount 3. find the neighbor of that phantom node via nextEntry()/previousEntry() 4. remove the phantom node 5. increment the modCount again 6. then decrement modCount by 2 to hide the 2 modifications (add + remove) ``` The referenced modCount is used as a fail-fast mechanism in the iterators. This fix prevents the issue by instead: 1. Finding the nearest entry via getNearestEntryForKey(). 2. Determining whether the search key is less than or greater than the found entry using isBitSet() at the first differing bit. 3. Walking forward (nextEntry()) or backward (previousEntry()) to locate the correct ceiling/floor neighbor. See https://issues.apache.org/jira/browse/COLLECTIONS-885 for all details. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
