buildTrieRecursive
private static void buildTrieRecursive(long nodeOffset,
Buffer node,
int byteStringOffset,
java.util.List<ByteString> byteStrings,
int fromIndex,
int toIndex,
java.util.List<java.lang.Integer> indexes)
Builds a trie encoded as an int array. Nodes in the trie are of two types: SELECT and SCAN.
SELECT nodes are encoded as:
- selectChoiceCount: the number of bytes to choose between (a positive int)
- prefixIndex: the result index at the current position or -1 if the current position is not
a result on its own
- a sorted list of selectChoiceCount bytes to match against the input string
- a heterogeneous list of selectChoiceCount result indexes (>= 0) or offsets (< 0) of the
next node to follow. Elements in this list correspond to elements in the preceding list.
Offsets are negative and must be multiplied by -1 before being used.
SCAN nodes are encoded as:
- scanByteCount: the number of bytes to match in sequence. This count is negative and must
be multiplied by -1 before being used.
- prefixIndex: the result index at the current position or -1 if the current position is not
a result on its own
- a list of scanByteCount bytes to match
- nextStep: the result index (>= 0) or offset (< 0) of the next node to follow. Offsets are
negative and must be multiplied by -1 before being used.
This structure is used to improve locality and performance when selecting from a list of
options.