Package org.apache.cassandra.db.tries

Class SlicedTrie<T>

java.lang.Object
org.apache.cassandra.db.tries.Trie<T>
org.apache.cassandra.db.tries.SlicedTrie<T>
public class SlicedTrie<T> extends Trie<T>
Represents a sliced view of a trie, i.e. the content within the given pair of bounds. Applied by advancing three tries in parallel: the left bound, the source and the right bound. While the source bound is smallest, we don't issue any content and skip over any children. As soon as the left bound becomes strictly smaller, we stop processing it (as it's a singleton trie it will remain smaller until it's exhausted) and start issuing the nodes and content from the source. As soon as the right bound becomes strictly smaller, we finish the walk. We don't explicitly construct tries for the two bounds; tracking the current depth (= prefix length) and transition as characters are requested from the key is sufficient as it is a trie with just a single descent path. Because we need the next character to tell if it's been exhausted, we keep these one position ahead. The source is always advanced, thus this gives us the thing to compare it against after the advance. We also track the current state to make some decisions a little simpler. See Trie.md for further details.