nxt.trie

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

Members

Aliases

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

Fixed-Length leaf Key-only Node.

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

Immutable RawTree Key.

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

Immutable RawTree Key.

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

Mutable RawTree Key.

Key
alias Key(size_t span) = ubyte[]

Mutable RawTree Key.

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

Fixed-Length RawTree Key.

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

Fixed-Length RawTree Key.

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

Mutable leaf node of 1-Ix leaves.

Enums

ModStatus
enum ModStatus

Results of attempt at modification sub.

isScalarTrieableKeyType
eponymoustemplate isScalarTrieableKeyType(T)

Functions

checkNumeric
auto checkNumeric()

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

constructFixedSizeNode
auto constructFixedSizeNode(Args args)

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

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

Print tree.

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

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

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

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

showStatistics
void showStatistics(RT tree)

Calculate and print statistics of tree.

testString
auto testString(size_t count, uint maxLength)

Check string types in Keys.

toFixedRawKey
UKey toFixedRawKey(TypedKey typedKey, UKey preallocatedFixedUKey)

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

toRawKey
UKey toRawKey(TypedKey typedKey, Array!Ix rawUKey)

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

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

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

tryNextIx
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.

Structs

HeptLeaf1
struct HeptLeaf1

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

OneLeafMax7
struct OneLeafMax7

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

RadixTree
struct RadixTree(K, V)

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

TriLeaf2
struct TriLeaf2

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

TwoLeaf3
struct TwoLeaf3

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

Templates

MutableKey
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.

RawRadixTree
template RawRadixTree(Value = void)

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

iota
template iota(size_t from, size_t to)

Static Iota.

isTrieableKeyType
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

TODO

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

Meta