RawRadixTree

Adaptive radix tree (ART) container storing untyped (raw) keys.

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

template RawRadixTree (

Value = void

) {

enum isValue;

alias Node = WordVariant!(OneLeafMax7, TwoLeaf3, TriLeaf2, HeptLeaf1, SparseLeaf1!Value*, DenseLeaf1!Value*, SparseBranch*, DenseBranch*);

alias Branch = WordVariant!(SparseBranch*, DenseBranch*);

alias SparseLeaf1_PopHist = size_t[radix];

alias DenseLeaf1_PopHist = size_t[radix];

alias SparseBranch_PopHist = size_t[SparseBranch.maxCapacity + 1];

alias DenseBranch_PopHist = size_t[radix + 1];

struct Stats;

Branch expand(SparseBranch* curr, size_t capacityIncrement);

Leaf1!Value expand(SparseLeaf1!Value* curr, size_t capacityIncrement);

Branch setSub(SparseBranch* curr, UIx subIx, Node subNode);

Branch setSub(DenseBranch* curr, UIx subIx, Node subNode);

Branch setSub(Branch curr, UIx subIx, Node subNode);

Node getSub(Branch curr, UIx subIx);

Node getSub(SparseBranch* curr, UIx subIx);

Node getSub(DenseBranch* curr, UIx subIx);

inout(Leaf1!Value) getLeaf1(Branch curr);

void setLeaf1(Branch curr, Leaf1!Value leaf1);

auto getPrefix(Branch curr);

void setPrefix(Branch curr, Ix[] prefix);

void popFrontNPrefix(Branch curr, size_t n);

SubCount getSubCount(Branch curr);

inout(Value*) containsAt(Leaf1!Value curr, UKey key);

inout(Value*) containsAt(Node curr, UKey key);

bool containsAt(Leaf1!Value curr, UKey key);

bool containsAt(Node curr, UKey key);

Leaf1!Value dupAt(Leaf1!Value curr);

Node dupAt(Node curr);

Node insertAt(Node curr, Elt!Value elt, ElementRef elementRef);

Branch insertAtAbovePrefix(Branch curr, Elt!Value elt, ElementRef elementRef);

Branch insertNewAtAbovePrefix(Branch curr, Elt!Value elt);

Branch insertAtBelowPrefix(Branch curr, Elt!Value elt, ElementRef elementRef);

Node split(OneLeafMax7 curr, UKey prefix, UKey key);

Branch expand(OneLeafMax7 curr, size_t capacityIncrement);

Branch expand(TwoLeaf3 curr, size_t capacityIncrement);

Branch expand(TriLeaf2 curr, size_t capacityIncrement);

Node expand(HeptLeaf1 curr, size_t capacityIncrement);

void release(Leaf1!Value curr);

void release(Node curr);

struct RawRadixTree;

}

Members

Aliases

Branch alias Branch = WordVariant!(SparseBranch*, DenseBranch*): Mutable branch node.
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.

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)
dupAt Leaf1!Value dupAt(Leaf1!Value curr): Returns a duplicate of this tree with root at curr. Shallowly duplicates the values in the map case.
dupAt Node dupAt(Node curr): Returns a duplicate of this tree with root at curr. Shallowly duplicates the values in the map case.
expand Branch expand(SparseBranch* curr, size_t capacityIncrement): Destructively expand curr to a branch node able to store capacityIncrement more sub-nodes.
expand Leaf1!Value expand(SparseLeaf1!Value* curr, size_t capacityIncrement): Destructively expand curr to a leaf node able to store capacityIncrement more sub-nodes.
expand Branch expand(OneLeafMax7 curr, size_t capacityIncrement): Destructively expand curr to make room for capacityIncrement more keys and return it.
expand Branch expand(TwoLeaf3 curr, size_t capacityIncrement): Destructively expand curr to make room for capacityIncrement more keys and return it.
expand Branch expand(TriLeaf2 curr, size_t capacityIncrement): Destructively expand curr to make room for capacityIncrement more keys and return it.
expand Node expand(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(Node curr, Elt!Value elt, ElementRef elementRef): Insert key into sub-tree under root curr.
insertAtAbovePrefix Branch insertAtAbovePrefix(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(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.
insertNewAtAbovePrefix Branch insertNewAtAbovePrefix(Branch curr, Elt!Value elt): Like insertAtAbovePrefix but also asserts that key is currently not stored under curr.
popFrontNPrefix void popFrontNPrefix(Branch curr, size_t n): Pop n from prefix.
release void release(Leaf1!Value curr): Release Leaf1!Value curr.
release void release(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(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(Branch curr, UIx subIx, Node subNode): Set sub-Node of branch Node curr at index ix to subNode.
split Node split(OneLeafMax7 curr, UKey prefix, UKey key): Split curr using prefix.

Structs

RawRadixTree struct RawRadixTree
Stats struct Stats: Tree Population and Memory-Usage Statistics.

RawRadixTree

Members

Aliases

Functions

Structs

See Also

Meta

Source