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

) {

import std.bitmanip : bitfields;;

import std.algorithm.iteration : filter;;

import std.meta : AliasSeq, staticMap;;

import std.meta : AliasSeq, staticMap;;

struct StaticBitArray(uint capacity, Block = DefaultBlock) via import nxt.static_bitarray : StaticBitArray;;

alias SubCount = Mod!(radix + 1);

alias SubCount = uint;

alias DefaultBranch = SparseBranch;

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];

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);

static if(isValue)

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

static if(isValue)

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

static if(!(isValue))

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

static if(!(isValue))

bool containsAt(Node curr, UKey key);

inout(Node) prefixAt(Node curr, UKey keyPrefix, UKey keyPrefixRest);

inout(Node) matchCommonPrefixAt(Node curr, UKey key, UKey keyRest);

size_t countHeapNodesAt(Node curr);

Leaf1!Value dupAt(Leaf1!Value curr);

Node dupAt(Node curr);

static if(!isValue)

Node insertNew(UKey key, ElementRef elementRef);

Branch insertNewBranch(Elt!Value elt, ElementRef elementRef);

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);

static if(isValue)

Branch insertAtSubNode(Branch curr, UKey key, Value value, ElementRef elementRef);

static if(!(isValue))

Branch insertAtSubNode(Branch curr, UKey key, ElementRef elementRef);

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

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

Leaf1!Value insertIxAtLeaftoLeaf(Leaf1!Value curr, IxElt!Value elt, ElementRef elementRef);

static if(isValue)

Branch insertAtLeaf1(Branch curr, UIx key, Value value, ElementRef elementRef);

static if(!(isValue))

Branch insertAtLeaf1(Branch curr, UIx key, ElementRef elementRef);

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

static if(!isValue)

Node insertAt(OneLeafMax7 curr, UKey key, ElementRef elementRef);

static if(!isValue)

Node insertAt(TwoLeaf3 curr, UKey key, ElementRef elementRef);

static if(!isValue)

Node insertAt(TriLeaf2 curr, UKey key, ElementRef elementRef);

static if(!isValue)

Leaf1!Value insertAt(HeptLeaf1 curr, UIx key, ElementRef elementRef);

static if(!isValue)

Node insertAt(HeptLeaf1 curr, UKey key, ElementRef elementRef);

static if(!isValue)

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

static if(!isValue)

Branch expand(OneLeafMax7 curr, size_t capacityIncrement);

static if(!isValue)

Branch expand(TwoLeaf3 curr, size_t capacityIncrement);

static if(!isValue)

Branch expand(TriLeaf2 curr, size_t capacityIncrement);

static if(!isValue)

Node expand(HeptLeaf1 curr, size_t capacityIncrement);

void release(SparseLeaf1!Value* curr);

void release(DenseLeaf1!Value* curr);

void release(SparseBranch* curr);

void release(DenseBranch* curr);

void release(OneLeafMax7 curr);

void release(TwoLeaf3 curr);

void release(TriLeaf2 curr);

void release(HeptLeaf1 curr);

void release(Leaf1!Value curr);

void release(Node curr);

bool isHeapAllocatedNode(Node curr);

void printAt(Node curr, size_t depth, uint subIx);

struct RawRadixTree;

}

Members

Aliases

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.
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.
insertAt Node insertAt(OneLeafMax7 curr, UKey key, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertAt Node insertAt(TwoLeaf3 curr, UKey key, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertAt Node insertAt(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(HeptLeaf1 curr, UIx key, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertAt Node insertAt(HeptLeaf1 curr, UKey key, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
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.
insertAtLeaf Node insertAtLeaf(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(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(Branch curr, UIx key, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertAtSubNode Branch insertAtSubNode(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(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(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(UKey key, ElementRef elementRef): Undocumented in source. Be warned that the author may not have intended to support it.
insertNewAtAbovePrefix Branch insertNewAtAbovePrefix(Branch curr, Elt!Value elt): Like insertAtAbovePrefix but also asserts that key is currently not stored under curr.
insertNewAtBelowPrefix Branch insertNewAtBelowPrefix(Branch curr, Elt!Value elt): Undocumented in source. Be warned that the author may not have intended to support it.
insertNewBranch Branch insertNewBranch(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(SparseLeaf1!Value* curr): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(DenseLeaf1!Value* curr): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(SparseBranch* curr): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(DenseBranch* curr): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(OneLeafMax7 curr): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(TwoLeaf3 curr): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(TriLeaf2 curr): Undocumented in source. Be warned that the author may not have intended to support it.
release void release(HeptLeaf1 curr): Undocumented in source. Be warned that the author may not have intended to support it.
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.

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.

See Also

Meta

Source

See Implementation