type NodeStore

bend-collections@1.0.0.0 · src/containers/balanced_search_tree.bend:13

import Base

13# Node storage: one array per node field instead of one array of Node
14# records. Reading a record out of an array hands back a shared copy that the
15# runtime reference-counts and takes apart field by field; a field read out of
16# its own array is a plain word. The store has the shape of a dynamic array
17# of nodes: slots [0, used) are live, the capacity is 2^depth <= 2^limit, and
18# it grows by doubling. A slot holds the encoding of its node by ntag (0 free,
19# 1 black, 2 red), nleft (the free-list link of a free slot), nright, nparent
20# and nkey (None when free); every other slot holds the encoding of Free{0},
21# so each array is exactly its field of the node list, padded.
22type NodeStore<-K: Data> is Type:
23  NS{limit: Nat, depth: Nat, cap: Nat, used: Nat, tags: Array<Nat>, lefts: Array<Nat>, rights: Array<Nat>, parents: Array<Nat>, keys: Array<Maybe<&2, K>>}