1import core/mem
2import core/vec
3
4identifier: type = distinct usize
5--- Opaque target-sized ordinal identifying a node in a particular tree. It
6--- does not retain or identify the tree itself.
7public node_id: type = identifier
8
9--- Wrap an ordinal as a node identifier without validating membership in a
10--- tree.
11public id: (ordinal: usize) -> (value: identifier) =
12 value = identifier(ordinal)
13end id
14
15--- Return the ordinal carried by a node identifier.
16public ordinal: (value: identifier) -> (number: usize) =
17 number = usize(value)
18end ordinal
19--- The node identifier is outside the tree's stored node range.
20public no_such_node: atom
21--- The requested child interval is not wholly within already published nodes.
22public invalid_children: atom
23--- Another node identifier cannot be represented in target `usize`.
24public too_many_nodes: atom
25--- The branch's leaf total cannot be represented in target `usize`.
26public too_many_leaves: atom
27
28node_value: type = struct
29 name: utf8
30 leaves: usize
31 -- Sum of every node's leaf total through this node. Each node has a
32 -- target-sized identifier; two words hold every possible cumulative sum.
33 through_low: usize
34 through_high: usize
35 kind: variant
36 leaf |
37 branch: (first: node_id, count: usize)
38 end kind
39end node_value
40--- Opaque named leaf or branch with a precomputed leaf total. The name is
41--- borrowed UTF-8.
42public node: type = node_value
43
44tree_value: type = struct
45 nodes: vec.list(node_value)
46end tree_value
47--- Append-only store of named nodes. Branches reference contiguous ranges of
48--- already published nodes; allocation is supplied explicitly.
49public tree: type = tree_value
50
51--- Create an empty tree without allocating.
52public new: () -> (result: tree_value) =
53 result = (nodes: vec.new(item: node_value))
54end new
55
56--- Return the number of published nodes.
57public length: (value: tree_value) -> (count: usize) =
58 count = vec.length(value.nodes)
59end length
60
61next_id: (count: usize) -> (id: node_id) ! too_many_nodes =
62 maximum: usize = 0 -% 1
63 fail too_many_nodes when count == maximum
64 id = identifier(count)
65end next_id
66
67--- Append a named leaf and return its identifier. Retains the name's backing;
68--- allocation or identifier exhaustion leaves existing nodes unchanged.
69public add_leaf: (provider: type is mem.allocator, inout value: tree_value,
70 inout state: provider, escaping name: utf8)
71 -> (id: node_id) ! mem.out_of_memory | too_many_nodes =
72 id = try next_id(length(value))
73 mut previous_low: usize = 0
74 mut previous_high: usize = 0
75 if length(value) > 0 then
76 last: node_value = (vec.get(value.nodes, length(value) - 1) else (problem)
77 _ = problem
78 -- A nonempty list always has its last node.
79 fail too_many_nodes
80 end)
81 previous_low = last.through_low
82 previous_high = last.through_high
83 end if
84 next_low: usize = previous_low +% 1
85 if next_low == 0 then inc previous_high end if
86 added: node_value = (name: name, leaves: 1, through_low: next_low,
87 through_high: previous_high,
88 kind: leaf)
89 try vec.push(value.nodes, state, added)
90end add_leaf
91
92--- Append a branch over a contiguous interval of existing nodes. Retains the
93--- name, validates children and leaf totals before publication, and permits
94--- an empty interval.
95---
96--- Edges name only previously published nodes. Their leaf totals are fixed,
97--- so their cumulative totals give bounded-stack queries at any depth.
98--- Shared children count once for each incoming path, as recursive counting
99--- would. An empty child interval has total zero.
100public add_branch: (provider: type is mem.allocator, inout value: tree_value,
101 inout state: provider, escaping name: utf8,
102 first: node_id, count: usize)
103 -> (id: node_id)
104 ! mem.out_of_memory | too_many_nodes
105 | invalid_children | too_many_leaves =
106 id = try next_id(length(value))
107 begins: usize = usize(first)
108 amount: usize = usize(count)
109 available: usize = length(value)
110 fail invalid_children when begins > available
111 fail invalid_children when amount > available - begins
112 mut before_low: usize = 0
113 mut before_high: usize = 0
114 if begins > 0 then
115 predecessor: node_value = (vec.get(value.nodes, begins - 1) else (problem)
116 _ = problem
117 fail invalid_children
118 end)
119 before_low = predecessor.through_low
120 before_high = predecessor.through_high
121 end if
122 mut through_low: usize = 0
123 mut through_high: usize = 0
124 if available > 0 then
125 last: node_value = (vec.get(value.nodes, available - 1) else (problem)
126 _ = problem
127 fail invalid_children
128 end)
129 through_low = last.through_low
130 through_high = last.through_high
131 end if
132 mut total: usize = 0
133 if amount > 0 then
134 end_node: node_value = (vec.get(value.nodes, begins + amount - 1)
135 else (problem)
136 _ = problem
137 fail invalid_children
138 end)
139 total = end_node.through_low -% before_low
140 mut high: usize = end_node.through_high - before_high
141 if end_node.through_low < before_low then dec high end if
142 fail too_many_leaves when high <> 0
143 end if
144 next_low: usize = through_low +% total
145 if next_low < through_low then inc through_high end if
146 added: node_value =
147 (name: name, leaves: total, through_low: next_low,
148 through_high: through_high,
149 kind: branch(first: first, count: count))
150 try vec.push(value.nodes, state, added)
151end add_branch
152
153--- Copy the node selected by an identifier. Reports `no_such_node` if absent;
154--- the name remains borrowed from its original backing.
155public get: (value: tree_value, id: node_id)
156 -> (result: node_value from value) ! no_such_node =
157 result = vec.get(value.nodes, usize(id)) else (problem)
158 _ = problem
159 fail no_such_node
160 end
161end get
162
163--- Lend the UTF-8 name retained in a node.
164public name: (value: node_value) -> (text: utf8 from value) =
165 text = value.name
166end name
167
168--- Return the node's precomputed leaf total in constant time. Shared children
169--- count once per incoming path; an empty branch counts zero.
170public count_leaves: (value: tree_value, id: node_id)
171 -> (count: usize) ! no_such_node =
172 selected: node_value = get(value, id) else (problem)
173 _ = problem
174 fail no_such_node
175 end
176 count = selected.leaves
177end count_leaves
178
179--- Release node storage through the original allocator and reset the tree.
180--- Name backing remains owned by its caller.
181public release: (provider: type is mem.allocator, inout value: tree_value,
182 inout state: provider) -> none =
183 vec.release(value.nodes, state)
184end release