phobos-next ~master (2022-05-18T09:58:38.2169964)

nxt.trie

nxt

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.

Ix
alias Ix = Mod!(radix, ubyte)

Radix Modulo Index Restricted index type avoids range checking in array indexing below.

Ix
alias Ix = ubyte
Undocumented in source.
IxsN
alias IxsN(uint capacity, uint elementLength) = StaticModArray!(capacity, elementLength, 8, useModuloFlag)
Undocumented in source.
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.

RadixTreeMap
alias RadixTreeMap = RadixTree
Undocumented in source.
UIx
alias UIx = Mod!(radix, size_t)

Radix Modulo Index Restricted index type avoids range checking in array indexing below.

UIx
alias UIx = size_t
Undocumented in source.
UKey
alias UKey = Key!span
Undocumented in source.
isFixedTrieableKeyType
alias isFixedTrieableKeyType = isIntegralBijectableType
Undocumented in source.

Enums

ModStatus
enum ModStatus

Results of attempt at modification sub.

isScalarTrieableKeyType
eponymoustemplate isScalarTrieableKeyType(T)

Functions

empty
bool empty(UKey ukey)
Undocumented in source. Be warned that the author may not have intended to support it.
firstIx
UIx firstIx(Leaf1!Value curr)
freeNode
void freeNode(A alloc, NodeType nt)
Undocumented in source. Be warned that the author may not have intended to support it.
makeFixedSizeNodePointer
auto makeFixedSizeNodePointer(A alloc, Args args)

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

makeFixedSizeNodeValue
auto makeFixedSizeNodeValue(Args args)

Construct a Node-type of value type NodeType using constructor arguments args of Args.

print
void print(RadixTree!(Key, Value, A) tree)

Print tree.

showStatistics
void showStatistics(RT tree)

Calculate and print statistics of tree.

testEqual
bool testEqual(T x, U y)
Undocumented in source. Be warned that the author may not have intended to support it.
testScalar
auto testScalar()
Undocumented in source. Be warned that the author may not have intended to support it.
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.

Manifest constants

keySeparator
enum keySeparator;
Undocumented in source.
useModuloFlag
enum useModuloFlag;
Undocumented in source.
useModuloFlag
enum useModuloFlag;
Undocumented in source.

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, A = Mallocator)

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

RadixTreeSet
template RadixTreeSet(K, A = Mallocator)
Undocumented in source.
RawRadixTree
template RawRadixTree(Value = void, A_)

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: Get rid of explicit @nogc qualifiers for all templates starting with those taking A alloc as parameter

TODO: Try to get rid of alias this

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: split up file into raw_trie.d, trie.d

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 makeVariableSizeNodePointer according C11-recommendations. For reference set commit d2f1971dd570439da4198fa76603b53b072060f8 at https://github.com/emacs-mirror/emacs.git

Meta

Source

See Source File

nxt modules

Page generated by adrdox