Tries and Prefix Trees.

Implementation is layered:

  • RawRadixTree stores its untyped keys as variable length ubyte-strings (UKey)
  • On top of that RadixTree implements typed-key access via its template parameter Key.

Both layers currently support

  • template parameterization on the Value-type in the map case (when Value is non-void)
  • @nogc and, when possible, @safe pure nothrow
  • insertion with returned modifications status: auto newKeyWasInserted = set.insert(Key key)
  • AA-style in-operator
    • key in set is bool for set-case
    • key in map returns non-null value pointer when key is stored in map
  • AA-style iteration of map keys: map.byKey()
  • AA-style iteration of map values: map.byValue()
  • SortedRange-style iteration over elements sorted by key: assert(set[].isSorted)
  • containment checking: bool contains(in Key key)
  • element indexing and element index assignment for map case via opIndex and opIndexAssign
  • key-prefix Completion (returning a Range over all set/map-elements that match a key prefix): prefix(Key keyPrefix)

Typed layer supports

  • ordered access of aggregate types



alias FixedKeyLeafN = WordVariant!(OneLeafMax7, TwoLeaf3, TriLeaf2)

Fixed-Length leaf Key-only Node.

alias IKey(size_t span) = immutable(Mod!(2^^span))[]

Immutable RawTree Key.

alias IKey(size_t span) = immutable(ubyte)[]

Immutable RawTree Key.

alias Key(size_t span) = Mod!(2^^span)[]

Mutable RawTree Key.

alias Key(size_t span) = ubyte[]

Mutable RawTree Key.

alias KeyN(size_t span, size_t N) = Mod!(2^^span)[N]

Fixed-Length RawTree Key.

alias KeyN(size_t span, size_t N) = ubyte[N]

Fixed-Length RawTree Key.

alias Leaf1(Value) = WordVariant!(HeptLeaf1, SparseLeaf1!Value*, DenseLeaf1!Value*)

Mutable leaf node of 1-Ix leaves.


enum ModStatus

Results of attempt at modification sub.

eponymoustemplate isScalarTrieableKeyType(T)


auto checkNumeric()

Check correctness when span is span and for each Key in Keys.

auto constructFixedSizeNode(Args args)

Allocate (if pointer) and Construct a Node-type of value type NodeType using constructor arguments args of Args.

UIx firstIx(Leaf1!Value curr)
void print(RadixTree!(Key, Value) tree)

Print tree.

RadixTree!(MutableKey!Key, Value) radixTreeMap()

Instantiator for the map-version of RadixTree where value-type is Value.

RadixTree!(MutableKey!Key, void) radixTreeSet()

Instantiator for the set-version of RadixTree where value-type is void (unused).

void showStatistics(RT tree)

Calculate and print statistics of tree.

auto testString(size_t count, uint maxLength)

Check string types in Keys.

UKey toFixedRawKey(TypedKey typedKey, UKey preallocatedFixedUKey)

Remap fixed-length typed key typedKey to raw (untyped) key of type UKey. TODO: DIP-1000 scope

UKey toRawKey(TypedKey typedKey, Array!Ix rawUKey)

Remap typed key typedKey to raw (untyped) key of type UKey.

inout(TypedKey) toTypedKey(inout(Ix)[] ukey)

Remap raw untyped key ukey to typed key of type TypedKey.

bool tryNextIx(Leaf1!Value curr, UIx ix, Ix nextIx)

Try to iterate leaf index ix to index, either sparse or dense and put result in nextIx.


struct HeptLeaf1

Hepa/7-Key Leaf with key-length 1.

struct OneLeafMax7

Single/1-Key Leaf with maximum key-length 7.

struct RadixTree(K, V)

Radix-Tree with key of type K and value of type V (if non-void).

struct TriLeaf2

Ternary/3-Key Leaf with key-length 2.

struct TwoLeaf3

Binary/2-Key Leaf with key-length 3.


template MutableKey(Key)

Keys are stored in a way that they can't be accessed by reference so we allow array (and string) keys to be of mutable type.

template RawRadixTree(Value = void)

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

template iota(size_t from, size_t to)

Static Iota.

template isTrieableKeyType(T)

See Also

for a descriptive usage of prefixed access.

TODO: split up file into raw_trie.d, trie.d

TODO: use fast bit-scanning functions in core.bitop for DenseBranch and DenseLeaf iterators

TODO: shift addresses of class and pointers by its alignment before adding them to make top-branch as dense possible

TODO: Allow slicing from non-mutable tries and add test-case at line 5300

TODO: 2. Make as many members as possible free functionss free-functions to reduce compilation times. Alternative make them templates (template-lazy )

TODO: Use scope on Range, RawRange and members that return key and value reference when DIP-1000 has been implemented

TODO: Encode string with zero-terminating 0 byte when it's not the last member in a key aggregate


Replace case undefined: return typeof(return).init; // terminate recursion with case undefined: return curr;

TODO: TODO: Make Key and Ix[]-array of immutable Ix like string

TODO: Allow Node-constructors to take const and immutable prefixes and then make toRawKey and toTypedKey accept return const-slices

TODO: Remove @trusted from VLA (variable length array)-members of SparseBranch/SparseLeaf and make their callers @trusted instead.

TODO: Assure that ~this() is run for argument nt in freeNode. Can we use postblit() for this?

TODO: Search for "functionize this loop or reuse memmove" and use move()

TODO: Add Branch-hint allocation flag and re-benchmark construction of radixTreeSet with 10000000 uints

TODO: Add sortedness to IxsN and make IxsN.contains() use binarySearch(). Make use of sortn.

TODO: Check for case when expanding to bit-branch instead of SparseBranch in all expand() overloads

TODO: Make array indexing/slicing as @trusted and use .ptr[] instead of [] when things are stable.

TODO: Add various extra packings in MixLeaf1to4: number of - Ix (0,1,2,3,4,5,6): 3-bits - Ix2 (0,1,2,3): 2-bits - Ix3 (0,1,2): 2-bits - Ix4 (0,1): 1-bit Total bits 8-bits Possible packings with 6 bytes - 4_ - 4_2 - 4_2 - 4_2_1 - 4_1 - 4_1_1 - 3_2 - 3_2_1 - 3_1 - 3_1_1 - 3_1_1_1 - 2_2_2 - 2_2 - 2_2_1 - 2_2_1_1 - 2 - 2_1 - 2_1_1 - 2_1_1_1 - 2_1_1_1_1 - 1 - 1_1 - 1_1_1 - 1_1_1_1 - 1_1_1_1_1 - 1_1_1_1_1_1

TODO: Sorted Range Primitives over Keys

- Returns a range of elements which are equivalent (though not necessarily equal) to value. auto equalRange(this This)(inout T value)

- Returns a range of elements which are greater than low and smaller than highValue. auto bound(this This)(inout T lowValue, inout T highValue)

- Returns a range of elements which are less than value. auto lowerBound(this This)(inout T value)

- Returns a range of elements which are greater than value. auto upperBound(this This)(inout T value)

TODO: opBinaryRight shall return _rawTree.ElementRef instead of bool

TODO: Fix vla-allocations in constructVariableSizeNode according C11-recommendations. For reference set commit d2f1971dd570439da4198fa76603b53b072060f8 at https://github.com/emacs-mirror/emacs.git