RawRadixTree

Branch alias Branch = WordVariant!(SparseBranch*, DenseBranch*): Mutable branch node.
DefaultBranch alias DefaultBranch = SparseBranch: Undocumented in source.
DenseBranch_PopHist alias DenseBranch_PopHist = size_t[radix + 1]: Radix-Branch population histogram. Index maps to population with value range (0 .. radix).
DenseLeaf1_PopHist alias DenseLeaf1_PopHist = size_t[radix]: 256-Branch population histogram.
Node alias Node = WordVariant!(OneLeafMax7, TwoLeaf3, TriLeaf2, HeptLeaf1, SparseLeaf1!Value*, DenseLeaf1!Value*, SparseBranch*, DenseBranch*): Mutable node.
SparseBranch_PopHist alias SparseBranch_PopHist = size_t[SparseBranch.maxCapacity + 1]: 4-Branch population histogram. Index maps to population with value range (0 .. 4).
SparseLeaf1_PopHist alias SparseLeaf1_PopHist = size_t[radix]: Sparse-Branch population histogram.
SubCount alias SubCount = Mod!(radix + 1): Undocumented in source.
SubCount alias SubCount = uint: Undocumented in source.

Functions

containsAt inout(Value*) containsAt(Leaf1!Value curr, UKey key)
inout(Value*) containsAt(Node curr, UKey key)
containsAt bool containsAt(Leaf1!Value curr, UKey key)
bool containsAt(Node curr, UKey key)
countHeapNodesAt size_t countHeapNodesAt(Node curr): Undocumented in source. Be warned that the author may not have intended to support it.
expand Branch expand(A alloc, SparseBranch* curr, size_t capacityIncrement): Destructively expand curr to a branch node able to store capacityIncrement more sub-nodes.
expand Leaf1!Value expand(A alloc, SparseLeaf1!Value* curr, size_t capacityIncrement): Destructively expand curr to a leaf node able to store capacityIncrement more sub-nodes.
expand Branch expand(A alloc, OneLeafMax7 curr, size_t capacityIncrement): Destructively expand curr to make room for capacityIncrement more keys and return it.
expand Branch expand(A alloc, TwoLeaf3 curr, size_t capacityIncrement): Destructively expand curr to make room for capacityIncrement more keys and return it.
expand Branch expand(A alloc, TriLeaf2 curr, size_t capacityIncrement): Destructively expand curr to make room for capacityIncrement more keys and return it.
expand Node expand(A alloc, HeptLeaf1 curr, size_t capacityIncrement): Destructively expand curr making room for nextKey and return it.
getLeaf1 inout(Leaf1!Value) getLeaf1(Branch curr): Get leaves of node curr.
getPrefix auto getPrefix(Branch curr): Get prefix of node curr.
getSub Node getSub(Branch curr, UIx subIx)
Node getSub(SparseBranch* curr, UIx subIx)
Node getSub(DenseBranch* curr, UIx subIx): Get sub-Node of branch Node curr at index subIx.
getSubCount SubCount getSubCount(Branch curr): Get number of sub-nodes of node curr.
insertAt Node insertAt(A alloc, Node curr, Elt!Value elt, ElementRef elementRef): Insert key into sub-tree under root curr.
insertAt Node insertAt(A alloc, OneLeafMax7 curr, UKey key, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertAt Node insertAt(A alloc, TwoLeaf3 curr, UKey key, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertAt Node insertAt(A alloc, TriLeaf2 curr, UKey key, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertAt Leaf1!Value insertAt(A alloc, HeptLeaf1 curr, UIx key, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertAt Node insertAt(A alloc, HeptLeaf1 curr, UKey key, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertAtAbovePrefix Branch insertAtAbovePrefix(A alloc, Branch curr, Elt!Value elt, ElementRef elementRef): Insert key into sub-tree under branch curr above prefix, that is the prefix of curr is stripped from key prior to insertion.
insertAtBelowPrefix Branch insertAtBelowPrefix(A alloc, Branch curr, Elt!Value elt, ElementRef elementRef): Insert key into sub-tree under branch curr below prefix, that is the prefix of curr is not stripped from key prior to insertion.
insertAtLeaf Node insertAtLeaf(A alloc, Leaf1!Value curr, Elt!Value elt, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertAtLeaf1 Branch insertAtLeaf1(A alloc, Branch curr, UIx key, Value value, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertAtLeaf1 Branch insertAtLeaf1(A alloc, Branch curr, UIx key, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertAtSubNode Branch insertAtSubNode(A alloc, Branch curr, UKey key, Value value, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertAtSubNode Branch insertAtSubNode(A alloc, Branch curr, UKey key, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertIxAtLeaftoLeaf Leaf1!Value insertIxAtLeaftoLeaf(A alloc, Leaf1!Value curr, IxElt!Value elt, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertNew Node insertNew(A alloc, UKey key, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertNewAtAbovePrefix Branch insertNewAtAbovePrefix(A alloc, Branch curr, Elt!Value elt): Like insertAtAbovePrefix but also asserts that key is currently not stored under curr.
insertNewAtBelowPrefix Branch insertNewAtBelowPrefix(A alloc, Branch curr, Elt!Value elt): Undocumented in source. Be warned that the author may not have intended to support it.
insertNewBranch Branch insertNewBranch(A alloc, Elt!Value elt, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
isHeapAllocatedNode bool isHeapAllocatedNode(Node curr): Undocumented in source. Be warned that the author may not have intended to support it.
matchCommonPrefixAt inout(Node) matchCommonPrefixAt(Node curr, UKey key, UKey keyRest): Undocumented in source. Be warned that the author may not have intended to support it.
popFrontNPrefix void popFrontNPrefix(Branch curr, size_t n): Pop n from prefix.
prefixAt inout(Node) prefixAt(Node curr, UKey keyPrefix, UKey keyPrefixRest): Undocumented in source. Be warned that the author may not have intended to support it.
printAt void printAt(Node curr, size_t depth, uint subIx): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(A alloc, SparseLeaf1!Value* curr): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(A alloc, DenseLeaf1!Value* curr): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(A alloc, SparseBranch* curr): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(A alloc, DenseBranch* curr): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(A alloc, OneLeafMax7 curr): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(A alloc, TwoLeaf3 curr): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(A alloc, TriLeaf2 curr): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(A alloc, HeptLeaf1 curr): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(A alloc, Leaf1!Value curr): Release Leaf1!Value curr.
release void release(A alloc, Node curr): Release Node curr.
setLeaf1 void setLeaf1(Branch curr, Leaf1!Value leaf1): Set direct leaves node of node curr to leaf1.
setPrefix void setPrefix(Branch curr, Ix[] prefix): Set prefix of branch node curr to prefix.
setSub Branch setSub(A alloc, SparseBranch* curr, UIx subIx, Node subNode)
Branch setSub(DenseBranch* curr, UIx subIx, Node subNode): Destructively expand curr to a leaf node able to store capacityIncrement more sub-nodes.
setSub Branch setSub(A alloc, Branch curr, UIx subIx, Node subNode): Set sub-Node of branch Node curr at index ix to subNode.
split Node split(A alloc, OneLeafMax7 curr, UKey prefix, UKey key): Split curr using prefix.
treedup Leaf1!Value treedup(Leaf1!Value curr, A alloc): Returns a duplicate of this tree with root at curr. Shallowly duplicates the values in the map case.
treedup Node treedup(Node curr, A alloc): Returns a duplicate of this tree with root at curr. Shallowly duplicates the values in the map case.

Manifest constants

isValue enum isValue;: Undocumented in source.

Structs

IxSub struct IxSub: Undocumented in source.
RawRadixTree struct RawRadixTree: Undocumented in source.
Stats struct Stats: Tree Population and Memory-Usage Statistics.

Parameters

Value: value type.
A_: memory allocator for bin array and large bins (LargeBin)
In set-case (Value is void) this container contains specific memory optimizations for representing a set pointers or integral types (of fixed length).
Radix-trees are suitable for storing ordered sets/maps with variable-length keys and provide completion of all its keys matching a given key-prefix. This enables, for instance, efficient storage and retrieval of large sets of long URLs with high probability of sharing a common prefix, typically a domain and path.
Branch packing of leaves is more efficient when Key.sizeof is fixed, that is, the member hasFixedKeyLength returns true.
For optimal performance, the individual bit-chunks should be arranged starting with most sparse chunks first. For integers this means most significant chunk (byte) first. This includes IEEE-compliant floating point numbers.
For a good introduction to adaptive radix trees (ART) see

RawRadixTree

Members

Aliases

Functions

Manifest constants

Structs

Parameters

See Also

Meta

Source