include/hamt/hamt_vec.h

filter: Statementstmt 93.2% 486 / 521 Branchbran 78.5% 325 / 414 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 86.7% 811 / 935 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/hamt/hamt_abi_impl.h ↑ Summary include/hamt/hamt_mut.h »
1 #ifndef HAMT_VEC_H
2 #define HAMT_VEC_H
3  
4 /* The vector: a sequence indexed from zero, with cheap append, cheap removal
5 * from the end, cheap replacement anywhere - and, from the second half of
6 * this file, concatenation, slicing and so insertion and removal in the
7 * middle, all without copying what does not change.
8 *
9 * It is a tree 32 wide whose leaves hold the values. The last few values -
10 * up to 32 of them - are kept out of the tree in a leaf of their own, the
11 * TAIL, so that nearly every append and every removal from the end touches
12 * one node and no path.
13 *
14 * count how many values in all
15 * tail the last 1..32 of them; NULL only when count is 0
16 * root a tree of everything before the tail; NULL when there is none
17 * shift five times the number of levels of nodes above the leaves
18 *
19 * REGULAR AND RELAXED. In a vector that has only been pushed to, every leaf
20 * in the tree is full and every node is full but the last on its level, so
21 * the child that holds an index is five bits of the index and nothing has
22 * to be looked up. Joining two such trees, or cutting one, leaves nodes
23 * along the join or the cut that are part full. Those nodes are RELAXED:
24 * each carries a table, `sizes`, of how many values lie under its first
25 * child, its first two, and so on. Finding a child in one is a guess from
26 * the index bits and then a step or two forward along the table.
27 *
28 * A node with no table is regular, and that is a promise: every child but
29 * its last holds exactly as many values as a child at that level can. A
30 * node is given a table exactly when that would not be true (hamt_vnode_make
31 * decides), so a tree that happens to come out regular is treated as one.
32 *
33 * How far a relaxed tree strays is put right where two trees are joined and
34 * where one is cut: the run of nodes along the join, or under each node
35 * along the cut, is repacked until no more than HAMT_VEC_EXTRAS of them are
36 * spare. That is what keeps the tree's height, and the steps a lookup takes
37 * along a table, close to a regular tree's. It is a repair made at each
38 * seam and not a promise about every node; see hamt_vec_check_spare.
39 *
40 * WHO MAY CHANGE WHAT. push, pop and set change a vector where it stands.
41 * The caller owns the hamt_vec struct, and the struct owns one reference to
42 * its root and one to its tail. A node whose reference count is one is the
43 * vector's alone and is changed in place; any other is shared, and is copied
44 * first, the copy taking the vector's place as holder of that reference. The
45 * walk makes each node on its way its own before it steps into it
46 * (hamt_vnode_own). A vector that never changes is made by giving every
47 * update a struct of its own that starts out sharing the root and the tail.
48 *
49 * concat and slice are the other kind: they build a new vector from old
50 * ones, which they only read.
51 *
52 * NO MEMORY. Every function either does what it was asked or leaves each
53 * vector holding exactly the values it held. A failed push, pop or set may
54 * leave some nodes as private copies of what they were, which nothing can
55 * observe.
56 *
57 * THE DISPLACED VALUE. A set or a pop takes one value out. It is handed
58 * back, with the reference the vector held, for the caller to release once
59 * it is done with the struct: releasing it can run code that uses this very
60 * vector. */
61  
62 #define HAMT_VEC_BITS 5
63 #define HAMT_VEC_WIDTH 32
64 #define HAMT_VEC_MASK 31
65 #define HAMT_VEC_EXTRAS 2
66  
67 /* For a test that wants to know how far a lookup had to step along a table. */
68 #ifndef HAMT_VEC_STEPPED
69 # define HAMT_VEC_STEPPED() ((void)0)
70 #endif
71  
72 typedef struct hamt_vnode {
73 uint32_t refcnt;
74 uint16_t len; /* slots in use, 1..32 */
75 uint16_t leaf; /* 1: the slots are values. 0: they are nodes */
76 size_t *sizes; /* NULL: regular. Else sizes[k] is the number of
77 * values under children 0..k, for k < len */
78 void *slot[HAMT_VEC_WIDTH];
79 } hamt_vnode;
80  
81 #define HAMT_VEC_SIZES_BYTES (HAMT_VEC_WIDTH * sizeof(size_t))
82  
83 #ifndef HAMT_VEC_FWD
84 #define HAMT_VEC_FWD
85 typedef struct hamt_vec hamt_vec;
86 #endif
87 struct hamt_vec {
88 size_t count;
89 uint32_t shift;
90 hamt_vnode *root;
91 hamt_vnode *tail;
92 };
93  
94 459099 static hamt_vnode *hamt_vnode_new(void *cx, int leaf) {
95 459099 hamt_vnode *n = (hamt_vnode *)HAMT_ALLOC(cx, sizeof(hamt_vnode));
96 459099 ▶ if (!n) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return NULL; 0 459099 459099
97 459099 n->refcnt = 1;
98 459099 n->len = 0;
99 459099 n->leaf = leaf ? 1 : 0;
100 459099 n->sizes = NULL;
101 (void)cx;
102 459099 return n;
103 }
104  
105 1476701 static hamt_vnode *hamt_vnode_retain(hamt_vnode *n) {
106 1476701 ▶ if (n->refcnt == 0xffffffffU) HAMT_FATAL("a vector node's reference count would wrap");
Branch: 1 branch
BranchTrueFalseTotal
if (n->refcnt == 0xffffffffU) HAMT_FATAL("a vector node's reference count would wrap"); 0 1476701 1476701
107 1476701 n->refcnt++;
108 1476701 return n;
109 }
110  
111 /* The node's memory and its table: what it pointed at is the caller's
112 * business. */
113 459099 static void hamt_vnode_free_raw(void *cx, hamt_vnode *n) {
114 459099 ▶ if (n->sizes) HAMT_FREE(cx, n->sizes, HAMT_VEC_SIZES_BYTES);
Branch: 1 branch
BranchTrueFalseTotal
if (n->sizes) HAMT_FREE(cx, n->sizes, HAMT_VEC_SIZES_BYTES); 21859 437240 459099
115 459099 HAMT_FREE(cx, n, sizeof(hamt_vnode));
116 (void)cx;
117 459099 }
118  
119 /* At zero the node is freed before anything it held is released: a value's
120 * release can run code that comes back in here. */
121 1687709 static void hamt_vnode_release(void *cx, hamt_vnode *n) {
122 void *s[HAMT_VEC_WIDTH];
123 uint32_t i, len;
124 int leaf;
125  
126 1687709 ▶ if (--n->refcnt) return;
Branch: 1 branch
BranchTrueFalseTotal
if (--n->refcnt) return; 1255606 432103 1687709
127 432103 len = n->len;
128 432103 leaf = n->leaf;
129 432103 memcpy(s, n->slot, (size_t)len * sizeof(void *));
130 432103 hamt_vnode_free_raw(cx, n);
131 5801753 ▶ if (leaf) { for (i = 0; i < len; i++) HAMT_VAL_RELEASE(cx, s[i]); }
Branch: 2 branches
BranchTrueFalseTotal
if (leaf) { for (i = 0; i < len; i++) HAMT_VAL_RELEASE(cx, s[i]); } 316336 115767 432103
if (leaf) { for (i = 0; i < len; i++) HAMT_VAL_RELEASE(cx, s[i]); } 5369650 316336 5685986
132 1113218 ▶ else { for (i = 0; i < len; i++) hamt_vnode_release(cx, (hamt_vnode *)s[i]); }
Branch: 1 branch
BranchTrueFalseTotal
else { for (i = 0; i < len; i++) hamt_vnode_release(cx, (hamt_vnode *)s[i]); } 997451 115767 1113218
133 (void)cx;
134 }
135  
136 /* Makes the node in *slot the holder's alone and returns it. If it already
137 * is, nothing happens. Otherwise *slot gets a copy that takes its own
138 * reference to everything the original held, and the original loses the
139 * reference *slot had. NULL when there is no memory, with *slot untouched. */
140 762688 static hamt_vnode *hamt_vnode_own(void *cx, hamt_vnode **slot) {
141 762688 hamt_vnode *n = *slot, *c;
142 uint32_t i;
143  
144 762688 ▶ if (n->refcnt == 1) return n;
Branch: 1 branch
BranchTrueFalseTotal
if (n->refcnt == 1) return n; 543087 219601 762688
145 219601 c = hamt_vnode_new(cx, n->leaf);
146 219601 ▶ if (!c) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!c) return NULL; 0 219601 219601
147 219601 ▶ if (n->sizes) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->sizes) { 4521 215080 219601
148 4521 c->sizes = (size_t *)HAMT_ALLOC(cx, HAMT_VEC_SIZES_BYTES);
149 4521 ▶ if (!c->sizes) { hamt_vnode_free_raw(cx, c); return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!c->sizes) { hamt_vnode_free_raw(cx, c); return NULL; } 0 4521 4521
150 4521 memcpy(c->sizes, n->sizes, (size_t)n->len * sizeof(size_t));
151 }
152 219601 c->len = n->len;
153 219601 memcpy(c->slot, n->slot, (size_t)n->len * sizeof(void *));
154 3400545 ▶ if (n->leaf) { for (i = 0; i < n->len; i++) HAMT_VAL_RETAIN(cx, c->slot[i]); }
Branch: 2 branches
BranchTrueFalseTotal
if (n->leaf) { for (i = 0; i < n->len; i++) HAMT_VAL_RETAIN(cx, c->slot[i]); } 173779 45822 219601
if (n->leaf) { for (i = 0; i < n->len; i++) HAMT_VAL_RETAIN(cx, c->slot[i]); } 3180944 173779 3354723
155 847639 ▶ else { for (i = 0; i < n->len; i++) hamt_vnode_retain((hamt_vnode *)c->slot[i]); }
Branch: 1 branch
BranchTrueFalseTotal
else { for (i = 0; i < n->len; i++) hamt_vnode_retain((hamt_vnode *)c->slot[i]); } 801817 45822 847639
156 219601 n->refcnt--; /* it was above one: this frees nothing */
157 219601 *slot = c;
158 219601 return c;
159 }
160  
161 /* How many values a subtree holds. `level` is the node's own: 0 for a leaf.
162 * A relaxed node knows; a regular one is full children and whatever its
163 * last child holds, so this is one walk down the right-hand edge at most. */
164 247533 static size_t hamt_vnode_count(const hamt_vnode *n, uint32_t level) {
165 247533 size_t total = 0;
166 for (;;) {
167 300809 ▶ if (n->leaf) return total + n->len;
Branch: 1 branch
BranchTrueFalseTotal
if (n->leaf) return total + n->len; 239842 60967 300809
168 60967 ▶ if (n->sizes) return total + n->sizes[n->len - 1];
Branch: 1 branch
BranchTrueFalseTotal
if (n->sizes) return total + n->sizes[n->len - 1]; 7691 53276 60967
169 53276 total += (size_t)(n->len - 1) << level;
170 53276 n = (const hamt_vnode *)n->slot[n->len - 1];
171 53276 level -= HAMT_VEC_BITS;
172 }
173 }
174  
175 /* Which child of a node holds the value at *i, counted from the node's
176 * first value; *i is left counted from that child's first. */
177 954528 static uint32_t hamt_vnode_child(const hamt_vnode *n, uint32_t level, size_t *i) {
178 954528 uint32_t k = (uint32_t)(*i >> level);
179  
180 954528 ▶ if (!n->sizes) {
Branch: 1 branch
BranchTrueFalseTotal
if (!n->sizes) { 896953 57575 954528
181 896953 *i &= ((size_t)1 << level) - 1;
182 896953 return k;
183 }
184 /* The guess cannot be past the child: no child holds more than a full
185 * one, so there cannot be fewer values before it than that many. */
186 88661 ▶ while (n->sizes[k] <= *i) { k++; HAMT_VEC_STEPPED(); }
Branch: 1 branch
BranchTrueFalseTotal
while (n->sizes[k] <= *i) { k++; HAMT_VEC_STEPPED(); } 31086 57575 88661
187 57575 ▶ if (k) *i -= n->sizes[k - 1];
Branch: 1 branch
BranchTrueFalseTotal
if (k) *i -= n->sizes[k - 1]; 31582 25993 57575
188 57575 return k;
189 }
190  
191 /* A node at `level` over the children in kids[], which are nodes one level
192 * down. Takes over the caller's references to them. It is given a table
193 * exactly when it needs one. NULL when there is no memory, with the
194 * children still the caller's. */
195 91491 static hamt_vnode *hamt_vnode_make(void *cx, hamt_vnode **kids, uint32_t n, uint32_t level) {
196 91491 hamt_vnode *node = hamt_vnode_new(cx, 0);
197 91491 size_t full = (size_t)1 << level, total = 0;
198 uint32_t k;
199 91491 int regular = 1;
200  
201 91491 ▶ if (!node) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!node) return NULL; 0 91491 91491
202 163726 ▶ for (k = 0; k + 1 < n && regular; k++)
Branch: 2 branches
BranchTrueFalseTotal
for (k = 0; k + 1 < n && regular; k++) 80323 83403 163726
for (k = 0; k + 1 < n && regular; k++) 72235 8088 80323
203 72235 ▶ if (hamt_vnode_count(kids[k], level - HAMT_VEC_BITS) != full) regular = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_vnode_count(kids[k], level - HAMT_VEC_BITS) != full) regular = 0; 17318 54917 72235
204  
205 91491 ▶ if (!regular) {
Branch: 1 branch
BranchTrueFalseTotal
if (!regular) { 17318 74173 91491
206 17318 node->sizes = (size_t *)HAMT_ALLOC(cx, HAMT_VEC_SIZES_BYTES);
207 17318 ▶ if (!node->sizes) { hamt_vnode_free_raw(cx, node); return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!node->sizes) { hamt_vnode_free_raw(cx, node); return NULL; } 0 17318 17318
208 112592 ▶ for (k = 0; k < n; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < n; k++) { 95274 17318 112592
209 95274 total += hamt_vnode_count(kids[k], level - HAMT_VEC_BITS);
210 95274 node->sizes[k] = total;
211 }
212 }
213 91491 node->len = (uint16_t)n;
214 91491 memcpy(node->slot, kids, (size_t)n * sizeof(void *));
215 91491 return node;
216 }
217  
218 /* A leaf holding the n values at vals[], each of which it retains. */
219 122769 static hamt_vnode *hamt_vnode_leaf(void *cx, void *const *vals, uint32_t n) {
220 122769 hamt_vnode *leaf = hamt_vnode_new(cx, 1);
221 uint32_t i;
222 122769 ▶ if (!leaf) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!leaf) return NULL; 0 122769 122769
223 122769 leaf->len = (uint16_t)n;
224 122769 memcpy(leaf->slot, vals, (size_t)n * sizeof(void *));
225 1895965 ▶ for (i = 0; i < n; i++) HAMT_VAL_RETAIN(cx, leaf->slot[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) HAMT_VAL_RETAIN(cx, leaf->slot[i]); 1773196 122769 1895965
226 (void)cx;
227 122769 return leaf;
228 }
229  
230 452935 static void hamt_vec_init(hamt_vec *v) {
231 452935 v->count = 0;
232 452935 v->shift = HAMT_VEC_BITS;
233 452935 v->root = NULL;
234 452935 v->tail = NULL;
235 452935 }
236  
237 /* A second struct onto the same vector: both now hold the root and the
238 * tail, so the first update through either copies what it touches. */
239 176089 static void hamt_vec_share(hamt_vec *dst, const hamt_vec *src) {
240 176089 *dst = *src;
241 176089 ▶ if (dst->root) hamt_vnode_retain(dst->root);
Branch: 1 branch
BranchTrueFalseTotal
if (dst->root) hamt_vnode_retain(dst->root); 145233 30856 176089
242 176089 ▶ if (dst->tail) hamt_vnode_retain(dst->tail);
Branch: 1 branch
BranchTrueFalseTotal
if (dst->tail) hamt_vnode_retain(dst->tail); 175176 913 176089
243 176089 }
244  
245 /* Lets go of everything the struct holds and leaves it empty. The struct is
246 * emptied first, so a value's release that looks at it sees an empty vector
247 * and not a half-released one. */
248 267219 static void hamt_vec_clear(void *cx, hamt_vec *v) {
249 267219 hamt_vnode *root = v->root, *tail = v->tail;
250 267219 hamt_vec_init(v);
251 267219 ▶ if (root) hamt_vnode_release(cx, root);
Branch: 1 branch
BranchTrueFalseTotal
if (root) hamt_vnode_release(cx, root); 183457 83762 267219
252 267219 ▶ if (tail) hamt_vnode_release(cx, tail);
Branch: 1 branch
BranchTrueFalseTotal
if (tail) hamt_vnode_release(cx, tail); 256882 10337 267219
253 267219 }
254  
255 /* Where the tail starts: the number of values in the tree. */
256 651704 static size_t hamt_vec_tailoff(const hamt_vec *v) {
257 651704 ▶ return v->tail ? v->count - v->tail->len : v->count;
Branch: 1 branch
BranchTrueFalseTotal
return v->tail ? v->count - v->tail->len : v->count; 651704 0 651704
258 }
259  
260 /* The leaf holding index i, which must be below the count, and where in the
261 * vector that leaf starts. Borrowed. */
262 537423 static const hamt_vnode *hamt_vec_leaf(const hamt_vec *v, size_t i, size_t *start) {
263 const hamt_vnode *n;
264 uint32_t level;
265 537423 size_t tailoff = hamt_vec_tailoff(v), rel = i;
266  
267 537423 ▶ if (i >= tailoff) { *start = tailoff; return v->tail; }
Branch: 1 branch
BranchTrueFalseTotal
if (i >= tailoff) { *start = tailoff; return v->tail; } 101056 436367 537423
268 436367 n = v->root;
269 1242659 ▶ for (level = v->shift; level > 0; level -= HAMT_VEC_BITS)
Branch: 1 branch
BranchTrueFalseTotal
for (level = v->shift; level > 0; level -= HAMT_VEC_BITS) 806292 436367 1242659
270 806292 n = (const hamt_vnode *)n->slot[hamt_vnode_child(n, level, &rel)];
271 436367 *start = i - rel;
272 436367 return n;
273 }
274  
275 /* The value at index i, which must be below the count. Borrowed. */
276 172694 static void *hamt_vec_get(const hamt_vec *v, size_t i) {
277 size_t start;
278 172694 const hamt_vnode *leaf = hamt_vec_leaf(v, i, &start);
279 172694 return leaf->slot[i - start];
280 }
281  
282 /* A chain of nodes `level` deep with `leaf` at the bottom of it, taking over
283 * the caller's reference to the leaf. A node with one child is regular
284 * whatever the child holds. NULL when there is no memory, with the leaf
285 * still the caller's. */
286 14684 static hamt_vnode *hamt_vec_new_path(void *cx, uint32_t level, hamt_vnode *leaf) {
287 14684 hamt_vnode *top = leaf;
288 uint32_t l;
289  
290 15101 ▶ for (l = 0; l < level; l += HAMT_VEC_BITS) {
Branch: 1 branch
BranchTrueFalseTotal
for (l = 0; l < level; l += HAMT_VEC_BITS) { 417 14684 15101
291 417 hamt_vnode *n = hamt_vnode_new(cx, 0);
292 417 ▶ if (!n) {
Branch: 1 branch
BranchTrueFalseTotal
if (!n) { 0 417 417
293 0 ▶ while (top != leaf) {
Branch: 1 branch
BranchTrueFalseTotal
while (top != leaf) { 0 0 0
294 0 hamt_vnode *down = (hamt_vnode *)top->slot[0];
295 0 hamt_vnode_free_raw(cx, top);
296 0 top = down;
297 }
298 0 return NULL;
299 }
300 417 n->slot[0] = top;
301 417 n->len = 1;
302 417 top = n;
303 }
304 14684 return top;
305 }
306  
307 /* Hangs a leaf at the right-hand end of the tree, taking over the caller's
308 * reference to it. The leaf may be short. 0, or -1 for no memory with the
309 * leaf still the caller's and the vector holding what it held.
310 *
311 * The leaf goes under the lowest node on the right-hand edge that has a
312 * slot free; if none has, a new root goes over the old one. A regular node
313 * that gets a new last child stays regular only if the child that was last
314 * is full, and is given a table if it is not. */
315 17722 static int hamt_vec_push_leaf(void *cx, hamt_vec *v, hamt_vnode *leaf) {
316 17722 hamt_vnode *path, *n, *host = NULL;
317 hamt_vnode **at;
318 17722 size_t *table = NULL;
319 17722 uint32_t level, host_level = 0;
320 const hamt_vnode *scan;
321  
322 17722 ▶ if (!v->root) {
Branch: 1 branch
BranchTrueFalseTotal
if (!v->root) { 3038 14684 17722
323 3038 n = hamt_vnode_new(cx, 0);
324 3038 ▶ if (!n) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return -1; 0 3038 3038
325 3038 n->slot[0] = leaf;
326 3038 n->len = 1;
327 3038 v->root = n;
328 3038 v->shift = HAMT_VEC_BITS;
329 3038 return 0;
330 }
331  
332 /* First, only looking: the lowest node on the edge with room. */
333 14684 scan = v->root;
334 39721 ▶ for (level = v->shift; level > 0; level -= HAMT_VEC_BITS) {
Branch: 1 branch
BranchTrueFalseTotal
for (level = v->shift; level > 0; level -= HAMT_VEC_BITS) { 25037 14684 39721
335 25037 ▶ if (scan->len < HAMT_VEC_WIDTH) host_level = level;
Branch: 1 branch
BranchTrueFalseTotal
if (scan->len < HAMT_VEC_WIDTH) host_level = level; 24416 621 25037
336 25037 scan = (const hamt_vnode *)scan->slot[scan->len - 1];
337 }
338  
339 14684 ▶ if (!host_level) {
Branch: 1 branch
BranchTrueFalseTotal
if (!host_level) { 98 14586 14684
340 /* No room anywhere: a new root over the old one and a new path. */
341 hamt_vnode *kids[2];
342 98 path = hamt_vec_new_path(cx, v->shift, leaf);
343 98 ▶ if (!path) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!path) return -1; 0 98 98
344 98 kids[0] = v->root;
345 98 kids[1] = path;
346 98 n = hamt_vnode_make(cx, kids, 2, v->shift + HAMT_VEC_BITS);
347 98 ▶ if (!n) {
Branch: 1 branch
BranchTrueFalseTotal
if (!n) { 0 98 98
348 /* Take the chain down again without touching the leaf. */
349 0 ▶ while (path != leaf) {
Branch: 1 branch
BranchTrueFalseTotal
while (path != leaf) { 0 0 0
350 0 hamt_vnode *down = (hamt_vnode *)path->slot[0];
351 0 hamt_vnode_free_raw(cx, path);
352 0 path = down;
353 }
354 0 return -1;
355 }
356 98 v->root = n;
357 98 v->shift += HAMT_VEC_BITS;
358 98 return 0;
359 }
360  
361 /* Make the edge this vector's own down to the host. Then everything the
362 * change needs is allocated, and only then is anything changed. */
363 14586 at = &v->root;
364 14586 for (level = v->shift; ; level -= HAMT_VEC_BITS) {
365 24620 n = hamt_vnode_own(cx, at);
366 24620 ▶ if (!n) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return -1; 0 24620 24620
367 24620 ▶ if (level == host_level) { host = n; break; }
Branch: 1 branch
BranchTrueFalseTotal
if (level == host_level) { host = n; break; } 14586 10034 24620
368 10034 at = (hamt_vnode **)&n->slot[n->len - 1];
369 }
370  
371 14586 ▶ if (!host->sizes) {
Branch: 1 branch
BranchTrueFalseTotal
if (!host->sizes) { 12780 1806 14586
372 12780 const hamt_vnode *was_last = (const hamt_vnode *)host->slot[host->len - 1];
373 12780 size_t under = hamt_vnode_count(was_last, host_level - HAMT_VEC_BITS);
374 12780 ▶ if (under != ((size_t)1 << host_level)) {
Branch: 1 branch
BranchTrueFalseTotal
if (under != ((size_t)1 << host_level)) { 20 12760 12780
375 uint32_t k;
376 20 table = (size_t *)HAMT_ALLOC(cx, HAMT_VEC_SIZES_BYTES);
377 20 ▶ if (!table) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!table) return -1; 0 20 20
378 20 ▶ for (k = 0; k + 1 < host->len; k++) table[k] = (size_t)(k + 1) << host_level;
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k + 1 < host->len; k++) table[k] = (size_t)(k + 1) << host_level; 0 20 20
379 20 table[host->len - 1] = ((size_t)(host->len - 1) << host_level) + under;
380 }
381 }
382 14586 path = hamt_vec_new_path(cx, host_level - HAMT_VEC_BITS, leaf);
383 14586 ▶ if (!path) {
Branch: 1 branch
BranchTrueFalseTotal
if (!path) { 0 14586 14586
384 0 ▶ if (table) HAMT_FREE(cx, table, HAMT_VEC_SIZES_BYTES);
Branch: 1 branch
BranchTrueFalseTotal
if (table) HAMT_FREE(cx, table, HAMT_VEC_SIZES_BYTES); 0 0 0
385 0 return -1;
386 }
387  
388 /* Nothing below can fail. Every relaxed node above the host has that
389 * many more values under its last child. */
390 14586 n = v->root;
391 24620 ▶ for (level = v->shift; level > host_level; level -= HAMT_VEC_BITS) {
Branch: 1 branch
BranchTrueFalseTotal
for (level = v->shift; level > host_level; level -= HAMT_VEC_BITS) { 10034 14586 24620
392 10034 ▶ if (n->sizes) n->sizes[n->len - 1] += leaf->len;
Branch: 1 branch
BranchTrueFalseTotal
if (n->sizes) n->sizes[n->len - 1] += leaf->len; 203 9831 10034
393 10034 n = (hamt_vnode *)n->slot[n->len - 1];
394 }
395 14586 ▶ if (table) host->sizes = table;
Branch: 1 branch
BranchTrueFalseTotal
if (table) host->sizes = table; 20 14566 14586
396 14586 ▶ if (host->sizes) host->sizes[host->len] = host->sizes[host->len - 1] + leaf->len;
Branch: 1 branch
BranchTrueFalseTotal
if (host->sizes) host->sizes[host->len] = host->sizes[host->len - 1] + leaf->len; 1826 12760 14586
397 14586 host->slot[host->len++] = path;
398 14586 return 0;
399 }
400  
401 /* Takes the tree's last leaf out to be the tail. The vector must have a
402 * tree and no tail. 0, or -1 for no memory with the vector as it was. */
403 36651 static int hamt_vec_pull_tail(void *cx, hamt_vec *v) {
404 hamt_vnode *path[14], *n, *leaf;
405 hamt_vnode **at;
406 uint32_t level;
407 36651 int depth = 0, d;
408  
409 36651 at = &v->root;
410 76161 ▶ for (level = v->shift; level > 0; level -= HAMT_VEC_BITS) {
Branch: 1 branch
BranchTrueFalseTotal
for (level = v->shift; level > 0; level -= HAMT_VEC_BITS) { 39510 36651 76161
411 39510 n = hamt_vnode_own(cx, at);
412 39510 ▶ if (!n) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return -1; 0 39510 39510
413 39510 path[depth++] = n;
414 39510 at = (hamt_vnode **)&n->slot[n->len - 1];
415 }
416 36651 leaf = *at;
417  
418 /* The leaf's reference moves from its parent to the tail. Going back up,
419 * a node left with nothing is freed and its parent loses the slot; the
420 * first node that still has something, and every relaxed node above it,
421 * has that many fewer values under its last child. */
422 36651 d = depth;
423 61634 ▶ while (d > 0) {
Branch: 1 branch
BranchTrueFalseTotal
while (d > 0) { 36767 24867 61634
424 36767 n = path[--d];
425 36767 ▶ if (--n->len > 0) break;
Branch: 1 branch
BranchTrueFalseTotal
if (--n->len > 0) break; 11784 24983 36767
426 24983 hamt_vnode_free_raw(cx, n);
427 24983 ▶ if (d == 0) v->root = NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (d == 0) v->root = NULL; 24867 116 24983
428 }
429 39394 ▶ while (d > 0) {
Branch: 1 branch
BranchTrueFalseTotal
while (d > 0) { 2743 36651 39394
430 2743 n = path[--d];
431 2743 ▶ if (n->sizes) n->sizes[n->len - 1] -= leaf->len;
Branch: 1 branch
BranchTrueFalseTotal
if (n->sizes) n->sizes[n->len - 1] -= leaf->len; 514 2229 2743
432 }
433 /* A root with one child is a level the tree no longer needs. */
434 36669 ▶ while (v->root && v->shift > HAMT_VEC_BITS && v->root->len == 1) {
Branch: 3 branches
BranchTrueFalseTotal
while (v->root && v->shift > HAMT_VEC_BITS && v->root->len == 1) { 11802 24867 36669
while (v->root && v->shift > HAMT_VEC_BITS && v->root->len == 1) { 2849 8953 11802
while (v->root && v->shift > HAMT_VEC_BITS && v->root->len == 1) { 18 2831 2849
435 18 hamt_vnode *top = v->root;
436 18 v->root = (hamt_vnode *)top->slot[0];
437 18 hamt_vnode_free_raw(cx, top);
438 18 v->shift -= HAMT_VEC_BITS;
439 }
440 36651 ▶ if (!v->root) v->shift = HAMT_VEC_BITS;
Branch: 1 branch
BranchTrueFalseTotal
if (!v->root) v->shift = HAMT_VEC_BITS; 24867 11784 36651
441 36651 v->tail = leaf;
442 36651 return 0;
443 }
444  
445 /* Appends a value. The vector takes its own reference. 0, or -1 for no
446 * memory with the vector holding what it held. */
447 517251 static int hamt_vec_push(void *cx, hamt_vec *v, void *val) {
448 hamt_vnode *fresh, *n;
449  
450 /* Room in the tail: the common case, one node and no path. */
451 517251 ▶ if (v->tail && v->tail->len < HAMT_VEC_WIDTH) {
Branch: 2 branches
BranchTrueFalseTotal
if (v->tail && v->tail->len < HAMT_VEC_WIDTH) { 509039 8212 517251
if (v->tail && v->tail->len < HAMT_VEC_WIDTH) { 495468 13571 509039
452 495468 n = hamt_vnode_own(cx, &v->tail);
453 495468 ▶ if (!n) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return -1; 0 495468 495468
454 495468 HAMT_VAL_RETAIN(cx, val);
455 495468 n->slot[n->len++] = val;
456 495468 v->count++;
457 495468 return 0;
458 }
459  
460 21783 fresh = hamt_vnode_new(cx, 1);
461 21783 ▶ if (!fresh) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!fresh) return -1; 0 21783 21783
462 21783 ▶ if (v->tail && hamt_vec_push_leaf(cx, v, v->tail)) {
Branch: 2 branches
BranchTrueFalseTotal
if (v->tail && hamt_vec_push_leaf(cx, v, v->tail)) { 13571 8212 21783
if (v->tail && hamt_vec_push_leaf(cx, v, v->tail)) { 0 13571 13571
463 0 hamt_vnode_free_raw(cx, fresh);
464 0 return -1;
465 }
466 21783 HAMT_VAL_RETAIN(cx, val);
467 21783 fresh->slot[0] = val;
468 21783 fresh->len = 1;
469 21783 v->tail = fresh;
470 21783 v->count++;
471 21783 return 0;
472 }
473  
474 /* Replaces the value at index i, which must be below the count. The vector
475 * takes its own reference to the new value; the old one comes back through
476 * `dead` with the reference the vector held, or NULL when the new value is
477 * the one already there and nothing was done. 0, or -1 for no memory. */
478 40349 static int hamt_vec_set(void *cx, hamt_vec *v, size_t i, void *val, void **dead) {
479 hamt_vnode **at, *n;
480 uint32_t level;
481 40349 size_t tailoff = hamt_vec_tailoff(v);
482  
483 40349 *dead = NULL;
484 40349 ▶ if (hamt_vec_get(v, i) == val) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_vec_get(v, i) == val) return 0; 0 40349 40349
485  
486 40349 ▶ if (i >= tailoff) {
Branch: 1 branch
BranchTrueFalseTotal
if (i >= tailoff) { 5014 35335 40349
487 5014 n = hamt_vnode_own(cx, &v->tail);
488 5014 ▶ if (!n) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return -1; 0 5014 5014
489 5014 i -= tailoff;
490 }
491 else {
492 35335 at = &v->root;
493 98330 ▶ for (level = v->shift; level > 0; level -= HAMT_VEC_BITS) {
Branch: 1 branch
BranchTrueFalseTotal
for (level = v->shift; level > 0; level -= HAMT_VEC_BITS) { 62995 35335 98330
494 62995 n = hamt_vnode_own(cx, at);
495 62995 ▶ if (!n) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return -1; 0 62995 62995
496 62995 at = (hamt_vnode **)&n->slot[hamt_vnode_child(n, level, &i)];
497 }
498 35335 n = hamt_vnode_own(cx, at);
499 35335 ▶ if (!n) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return -1; 0 35335 35335
500 }
501 40349 HAMT_VAL_RETAIN(cx, val);
502 40349 *dead = n->slot[i];
503 40349 n->slot[i] = val;
504 40349 return 0;
505 }
506  
507 /* Lets go of a leaf that holds exactly one value, handing the value back
508 * with a reference rather than releasing it. */
509 3489 static void *hamt_vec_take_last(void *cx, hamt_vnode *leaf) {
510 3489 void *val = leaf->slot[0];
511 3489 ▶ if (leaf->refcnt == 1) hamt_vnode_free_raw(cx, leaf); /* its reference is the caller's now */
Branch: 1 branch
BranchTrueFalseTotal
if (leaf->refcnt == 1) hamt_vnode_free_raw(cx, leaf); /* its reference is the caller's now */ 1995 1494 3489
512 else {
513 1494 HAMT_VAL_RETAIN(cx, val);
514 1494 leaf->refcnt--;
515 }
516 (void)cx;
517 3489 return val;
518 }
519  
520 /* Removes the last value, which comes back through `dead` with the
521 * reference the vector held; NULL for an empty vector, which stays empty.
522 * 0, or -1 for no memory with the vector holding what it held. */
523 103244 static int hamt_vec_pop(void *cx, hamt_vec *v, void **dead) {
524 hamt_vnode *n, *tail;
525  
526 103244 *dead = NULL;
527 103244 ▶ if (v->count == 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (v->count == 0) return 0; 9 103235 103244
528  
529 103235 ▶ if (v->tail->len > 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (v->tail->len > 1) { 99746 3489 103235
530 99746 n = hamt_vnode_own(cx, &v->tail);
531 99746 ▶ if (!n) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return -1; 0 99746 99746
532 99746 *dead = n->slot[--n->len];
533 99746 v->count--;
534 99746 return 0;
535 }
536  
537 /* The tail is down to its last value. If there is a tree, its last leaf
538 * comes out to be the new tail - which is all that can fail, so it is
539 * done first, with the old tail set aside. */
540 3489 tail = v->tail;
541 3489 v->tail = NULL;
542 3489 ▶ if (v->root && hamt_vec_pull_tail(cx, v)) {
Branch: 2 branches
BranchTrueFalseTotal
if (v->root && hamt_vec_pull_tail(cx, v)) { 3051 438 3489
if (v->root && hamt_vec_pull_tail(cx, v)) { 0 3051 3051
543 0 v->tail = tail;
544 0 return -1;
545 }
546 3489 v->count--;
547 3489 *dead = hamt_vec_take_last(cx, tail);
548 3489 return 0;
549 }
550  
551 /* ---- walking ----------------------------------------------------------- */
552  
553 /* Hands out the vector a leaf at a time: a run of up to 32 values and the
554 * index of the first. One descent for each run, not for each value. The
555 * vector is borrowed; whoever walks keeps it alive and unchanged. */
556 typedef struct hamt_vec_iter {
557 const hamt_vec *v;
558 size_t pos;
559 } hamt_vec_iter;
560  
561 64678 static void hamt_vec_iter_init(hamt_vec_iter *it, const hamt_vec *v) {
562 64678 it->v = v;
563 64678 it->pos = 0;
564 64678 }
565  
566 /* The next run, or NULL at the end. */
567 429273 static void *const *hamt_vec_iter_next(hamt_vec_iter *it, size_t *start, uint32_t *n) {
568 const hamt_vnode *leaf;
569 size_t leaf_start;
570  
571 429273 ▶ if (it->pos >= it->v->count) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (it->pos >= it->v->count) return NULL; 64544 364729 429273
572 /* A run is a whole leaf, so the position is always where one starts. */
573 364729 leaf = hamt_vec_leaf(it->v, it->pos, &leaf_start);
574 364729 *start = leaf_start;
575 364729 *n = leaf->len;
576 364729 it->pos = leaf_start + leaf->len;
577 364729 return (void *const *)leaf->slot;
578 }
579  
580 /* 1 when the two hold equal values in the same order, 0 when not, negative
581 * when the comparison stopped it. Two runs that are the same memory are the
582 * same values and are not looked into, so two versions of one vector are
583 * compared for what differs between them. The leaves of two vectors need
584 * not line up: each stretch compared is as long as both current runs allow. */
585 67 static int hamt_vec_equal(hamt_eq_ctx *c, const hamt_vec *a, const hamt_vec *b) {
586 hamt_vec_iter ia, ib;
587 67 void *const *ra = NULL, *const *rb = NULL;
588 67 size_t sa = 0, sb = 0, pos = 0;
589 67 uint32_t na = 0, nb = 0;
590  
591 67 ▶ if (a->count != b->count) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (a->count != b->count) return 0; 0 67 67
592 67 ▶ if (a->root == b->root && a->tail == b->tail) return 1;
Branch: 2 branches
BranchTrueFalseTotal
if (a->root == b->root && a->tail == b->tail) return 1; 19 48 67
if (a->root == b->root && a->tail == b->tail) return 1; 10 9 19
593  
594 57 hamt_vec_iter_init(&ia, a);
595 57 hamt_vec_iter_init(&ib, b);
596 1803 ▶ while (pos < a->count) {
Branch: 1 branch
BranchTrueFalseTotal
while (pos < a->count) { 1776 27 1803
597 uint32_t i, k;
598 1776 ▶ if (pos >= sa + na) ra = hamt_vec_iter_next(&ia, &sa, &na);
Branch: 1 branch
BranchTrueFalseTotal
if (pos >= sa + na) ra = hamt_vec_iter_next(&ia, &sa, &na); 1680 96 1776
599 1776 ▶ if (pos >= sb + nb) rb = hamt_vec_iter_next(&ib, &sb, &nb);
Branch: 1 branch
BranchTrueFalseTotal
if (pos >= sb + nb) rb = hamt_vec_iter_next(&ib, &sb, &nb); 1679 97 1776
600 1776 ▶ k = (uint32_t)((sa + na < sb + nb ? sa + na : sb + nb) - pos);
Branch: 1 branch
BranchTrueFalseTotal
k = (uint32_t)((sa + na < sb + nb ? sa + na : sb + nb) - pos); 97 1679 1776
601 1776 ▶ if (ra + (pos - sa) != rb + (pos - sb)) {
Branch: 1 branch
BranchTrueFalseTotal
if (ra + (pos - sa) != rb + (pos - sb)) { 1014 762 1776
602 1014 c->visits++;
603 29167 ▶ for (i = 0; i < k; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < k; i++) { 28183 984 29167
604 28183 int rc = hamt_val_same(c, ra[pos - sa + i], rb[pos - sb + i]);
605 28175 ▶ if (rc <= 0) return rc;
Branch: 1 branch
BranchTrueFalseTotal
if (rc <= 0) return rc; 22 28153 28175
606 }
607 }
608 1746 pos += k;
609 }
610 27 return 1;
611 }
612  
613 /* ---- joining ------------------------------------------------------------
614 *
615 * Two trees are joined along the right-hand edge of the first and the
616 * left-hand edge of the second. From the bottom up, at each level, there is
617 * a run of nodes: what the left node holds but for its last child, what
618 * came up from the level below, and what the right node holds but for its
619 * first child. The run is repacked - nodes that are nearly full are left
620 * exactly as they are and shared, a short one is poured into those after
621 * it - until it is no more than HAMT_VEC_EXTRAS nodes longer than the
622 * shortest it could be. Then it is gathered under one parent, or two, and
623 * those go up to the level above.
624 *
625 * Nothing that is read is changed: every node the result uses unchanged is
626 * shared, and only the nodes along the join are new. */
627  
628 /* A handful of nodes, each of which the list owns a reference to. */
629 typedef struct hamt_vlist {
630 hamt_vnode *n[2 * HAMT_VEC_WIDTH + 2];
631 uint32_t len;
632 } hamt_vlist;
633  
634 90618 static void hamt_vlist_release(void *cx, hamt_vlist *l) {
635 uint32_t i;
636 305734 ▶ for (i = 0; i < l->len; i++) hamt_vnode_release(cx, l->n[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < l->len; i++) hamt_vnode_release(cx, l->n[i]); 215116 90618 305734
637 90618 l->len = 0;
638 90618 }
639  
640 /* The run `all`, whose nodes are at `level` (0: leaves), repacked into
641 * `out`. 0, or -1 for no memory with `out` empty. `all` is only read. */
642 90524 static int hamt_rrb_repack(void *cx, const hamt_vlist *all, uint32_t level,
643 hamt_vlist *out) {
644 uint32_t c[2 * HAMT_VEC_WIDTH + 2];
645 90524 uint32_t n = all->len, i, j, src = 0, off = 0;
646 90524 size_t total = 0, shortest;
647  
648 90524 out->len = 0;
649 305452 ▶ for (i = 0; i < n; i++) { c[i] = all->n[i]->len; total += c[i]; }
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { c[i] = all->n[i]->len; total += c[i]; } 214928 90524 305452
650 90524 shortest = (total + HAMT_VEC_MASK) / HAMT_VEC_WIDTH;
651  
652 /* The plan: how many slots each node of the result will hold. While the
653 * run is too long, the first node with a slot or more to spare is
654 * emptied into the nodes after it, each filled in turn, and the run is
655 * one node shorter. */
656 90524 i = 0;
657 92820 ▶ while (n > shortest + HAMT_VEC_EXTRAS) {
Branch: 1 branch
BranchTrueFalseTotal
while (n > shortest + HAMT_VEC_EXTRAS) { 2296 90524 92820
658 uint32_t carry;
659 6128 ▶ while (c[i] >= HAMT_VEC_WIDTH - 1) i++;
Branch: 1 branch
BranchTrueFalseTotal
while (c[i] >= HAMT_VEC_WIDTH - 1) i++; 3832 2296 6128
660 2296 carry = c[i];
661 do {
662 6600 uint32_t take = carry + c[i + 1] < HAMT_VEC_WIDTH ? carry + c[i + 1] : HAMT_VEC_WIDTH;
663 6600 carry = carry + c[i + 1] - take;
664 6600 c[i] = take;
665 6600 i++;
666 6600 ▶ } while (carry > 0);
Branch: 1 branch
BranchTrueFalseTotal
} while (carry > 0); 4304 2296 6600
667 17872 ▶ for (j = i; j + 1 < n; j++) c[j] = c[j + 1];
Branch: 1 branch
BranchTrueFalseTotal
for (j = i; j + 1 < n; j++) c[j] = c[j + 1]; 15576 2296 17872
668 2296 n--;
669 2296 i--;
670 }
671  
672 /* Carrying it out. A node the plan leaves whole is shared; anything
673 * else is a new node filled from the old ones in order. */
674 303156 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 212632 90524 303156
675 hamt_vnode *made;
676  
677 212632 ▶ if (off == 0 && all->n[src]->len == c[i]) {
Branch: 2 branches
BranchTrueFalseTotal
if (off == 0 && all->n[src]->len == c[i]) { 208328 4304 212632
if (off == 0 && all->n[src]->len == c[i]) { 206083 2245 208328
678 206083 made = hamt_vnode_retain(all->n[src++]);
679 }
680 else {
681 void *slots[HAMT_VEC_WIDTH];
682 6549 uint32_t got = 0, k;
683  
684 19698 ▶ while (got < c[i]) {
Branch: 1 branch
BranchTrueFalseTotal
while (got < c[i]) { 13149 6549 19698
685 13149 const hamt_vnode *from = all->n[src];
686 13149 uint32_t take = from->len - off;
687 13149 ▶ if (take > c[i] - got) take = c[i] - got;
Branch: 1 branch
BranchTrueFalseTotal
if (take > c[i] - got) take = c[i] - got; 4304 8845 13149
688 13149 memcpy(slots + got, from->slot + off, (size_t)take * sizeof(void *));
689 13149 got += take;
690 13149 off += take;
691 13149 ▶ if (off == from->len) { src++; off = 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (off == from->len) { src++; off = 0; } 8845 4304 13149
692 }
693 6549 ▶ if (level == 0) made = hamt_vnode_leaf(cx, slots, got);
Branch: 1 branch
BranchTrueFalseTotal
if (level == 0) made = hamt_vnode_leaf(cx, slots, got); 6451 98 6549
694 else {
695 1420 ▶ for (k = 0; k < got; k++) hamt_vnode_retain((hamt_vnode *)slots[k]);
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < got; k++) hamt_vnode_retain((hamt_vnode *)slots[k]); 1322 98 1420
696 98 made = hamt_vnode_make(cx, (hamt_vnode **)slots, got, level);
697 98 ▶ if (!made) for (k = 0; k < got; k++) hamt_vnode_release(cx, (hamt_vnode *)slots[k]);
Branch: 2 branches
BranchTrueFalseTotal
if (!made) for (k = 0; k < got; k++) hamt_vnode_release(cx, (hamt_vnode *)slots[k]); 0 98 98
if (!made) for (k = 0; k < got; k++) hamt_vnode_release(cx, (hamt_vnode *)slots[k]); 0 0 0
698 }
699 6549 ▶ if (!made) { hamt_vlist_release(cx, out); return -1; }
Branch: 1 branch
BranchTrueFalseTotal
if (!made) { hamt_vlist_release(cx, out); return -1; } 0 6549 6549
700 }
701 212632 out->n[out->len++] = made;
702 }
703 90524 return 0;
704 }
705  
706 /* The nodes of `kids`, at the level below `level`, gathered under one node
707 * at `level` or two. Takes over the list's references, which the caller must
708 * then not release. 0, or -1 for no memory with `kids` still the caller's. */
709 5283 static int hamt_rrb_gather(void *cx, hamt_vlist *kids, uint32_t level, hamt_vlist *out) {
710 5283 uint32_t first = kids->len < HAMT_VEC_WIDTH ? kids->len : HAMT_VEC_WIDTH;
711 5283 hamt_vnode *a, *b = NULL;
712  
713 5283 out->len = 0;
714 5283 a = hamt_vnode_make(cx, kids->n, first, level);
715 5283 ▶ if (!a) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!a) return -1; 0 5283 5283
716 5283 ▶ if (kids->len > first) {
Branch: 1 branch
BranchTrueFalseTotal
if (kids->len > first) { 657 4626 5283
717 657 b = hamt_vnode_make(cx, kids->n + first, kids->len - first, level);
718 657 ▶ if (!b) {
Branch: 1 branch
BranchTrueFalseTotal
if (!b) { 0 657 657
719 /* Undo the first without letting go of its children. */
720 0 a->len = 0;
721 0 hamt_vnode_free_raw(cx, a);
722 0 return -1;
723 }
724 }
725 5283 out->n[out->len++] = a;
726 5283 ▶ if (b) out->n[out->len++] = b;
Branch: 1 branch
BranchTrueFalseTotal
if (b) out->n[out->len++] = b; 657 4626 5283
727 5283 return 0;
728 }
729  
730 /* Joins the subtree L, at level ll, to the subtree R, at level rl. `out`
731 * gets one node or two at the higher of the two levels, holding everything
732 * under L followed by everything under R. L and R are only read. */
733 9778 static int hamt_rrb_join(void *cx, const hamt_vnode *L, uint32_t ll,
734 const hamt_vnode *R, uint32_t rl, hamt_vlist *out) {
735 hamt_vlist mid, all, packed;
736 9778 uint32_t level = ll > rl ? ll : rl, i;
737 int rc;
738  
739 9778 out->len = 0;
740 9778 ▶ if (level == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (level == 0) { 4495 5283 9778
741 4495 out->n[0] = hamt_vnode_retain((hamt_vnode *)L);
742 4495 out->n[1] = hamt_vnode_retain((hamt_vnode *)R);
743 4495 out->len = 2;
744 4495 return 0;
745 }
746  
747 /* Down whichever edge is higher, or both, until the levels meet. */
748 5283 ▶ if (ll > rl) rc = hamt_rrb_join(cx, (const hamt_vnode *)L->slot[L->len - 1], ll - HAMT_VEC_BITS, R, rl, &mid);
Branch: 1 branch
BranchTrueFalseTotal
if (ll > rl) rc = hamt_rrb_join(cx, (const hamt_vnode *)L->slot[L->len - 1], ll - HAMT_VEC_BITS, R, rl, &mid); 155 5128 5283
749 5128 ▶ else if (ll < rl) rc = hamt_rrb_join(cx, L, ll, (const hamt_vnode *)R->slot[0], rl - HAMT_VEC_BITS, &mid);
Branch: 1 branch
BranchTrueFalseTotal
else if (ll < rl) rc = hamt_rrb_join(cx, L, ll, (const hamt_vnode *)R->slot[0], rl - HAMT_VEC_BITS, &mid); 390 4738 5128
750 4738 else rc = hamt_rrb_join(cx, (const hamt_vnode *)L->slot[L->len - 1], ll - HAMT_VEC_BITS,
751 4738 (const hamt_vnode *)R->slot[0], rl - HAMT_VEC_BITS, &mid);
752 5283 ▶ if (rc) return rc;
Branch: 1 branch
BranchTrueFalseTotal
if (rc) return rc; 0 5283 5283
753  
754 5283 all.len = 0;
755 5283 ▶ if (ll >= rl)
Branch: 1 branch
BranchTrueFalseTotal
if (ll >= rl) 4893 390 5283
756 26509 ▶ for (i = 0; i + 1 < L->len; i++) all.n[all.len++] = hamt_vnode_retain((hamt_vnode *)L->slot[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i + 1 < L->len; i++) all.n[all.len++] = hamt_vnode_retain((hamt_vnode *)L->slot[i]); 21616 4893 26509
757 15510 ▶ for (i = 0; i < mid.len; i++) all.n[all.len++] = mid.n[i]; /* the references move */
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < mid.len; i++) all.n[all.len++] = mid.n[i]; /* the references move */ 10227 5283 15510
758 5283 ▶ if (rl >= ll)
Branch: 1 branch
BranchTrueFalseTotal
if (rl >= ll) 5128 155 5283
759 36997 ▶ for (i = 1; i < R->len; i++) all.n[all.len++] = hamt_vnode_retain((hamt_vnode *)R->slot[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 1; i < R->len; i++) all.n[all.len++] = hamt_vnode_retain((hamt_vnode *)R->slot[i]); 31869 5128 36997
760  
761 5283 rc = hamt_rrb_repack(cx, &all, level - HAMT_VEC_BITS, &packed);
762 5283 hamt_vlist_release(cx, &all);
763 5283 ▶ if (rc) return rc;
Branch: 1 branch
BranchTrueFalseTotal
if (rc) return rc; 0 5283 5283
764  
765 5283 rc = hamt_rrb_gather(cx, &packed, level, out);
766 5283 ▶ if (rc) hamt_vlist_release(cx, &packed);
Branch: 1 branch
BranchTrueFalseTotal
if (rc) hamt_vlist_release(cx, &packed); 0 5283 5283
767 5283 return rc;
768 }
769  
770 /* `out` becomes a vector of everything in `a` followed by everything in
771 * `b`. Neither is changed, and the result shares with both everything that
772 * is not along the join. `out` is uninitialised on the way in. 0, or -1 for
773 * no memory with `out` empty. */
774 15170 static int hamt_vec_concat(void *cx, hamt_vec *out, const hamt_vec *a, const hamt_vec *b) {
775 hamt_vec left;
776 hamt_vlist top;
777 hamt_vnode *root;
778 uint32_t shift;
779  
780 15170 ▶ if (a->count == 0) { hamt_vec_share(out, b); return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (a->count == 0) { hamt_vec_share(out, b); return 0; } 1003 14167 15170
781 14167 ▶ if (b->count == 0) { hamt_vec_share(out, a); return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (b->count == 0) { hamt_vec_share(out, a); return 0; } 1107 13060 14167
782  
783 13060 ▶ if (!b->root) {
Branch: 1 branch
BranchTrueFalseTotal
if (!b->root) { 8909 4151 13060
784 /* The second is a tail and nothing more: its values are pushed. */
785 uint32_t i;
786 8909 hamt_vec_share(out, a);
787 60815 ▶ for (i = 0; i < b->tail->len; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < b->tail->len; i++) 51906 8909 60815
788 51906 ▶ if (hamt_vec_push(cx, out, b->tail->slot[i])) { hamt_vec_clear(cx, out); return -1; }
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_vec_push(cx, out, b->tail->slot[i])) { hamt_vec_clear(cx, out); return -1; } 0 51906 51906
789 8909 return 0;
790 }
791  
792 /* The first with its tail put into its tree, short as it may be, in a
793 * struct of its own so that `a` is not touched. */
794 4151 hamt_vec_share(&left, a);
795 4151 ▶ if (hamt_vec_push_leaf(cx, &left, left.tail)) { hamt_vec_clear(cx, &left); hamt_vec_init(out); return -1; }
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_vec_push_leaf(cx, &left, left.tail)) { hamt_vec_clear(cx, &left); hamt_vec_init(out); return -1; } 0 4151 4151
796 4151 left.tail = NULL;
797  
798 4151 ▶ if (hamt_rrb_join(cx, left.root, left.shift, b->root, b->shift, &top)) {
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_rrb_join(cx, left.root, left.shift, b->root, b->shift, &top)) { 0 4151 4151
799 0 hamt_vec_clear(cx, &left);
800 0 hamt_vec_init(out);
801 0 return -1;
802 }
803 4151 shift = left.shift > b->shift ? left.shift : b->shift;
804 4151 ▶ if (top.len == 1) root = top.n[0];
Branch: 1 branch
BranchTrueFalseTotal
if (top.len == 1) root = top.n[0]; 4037 114 4151
805 else {
806 114 root = hamt_vnode_make(cx, top.n, 2, shift + HAMT_VEC_BITS);
807 114 ▶ if (!root) {
Branch: 1 branch
BranchTrueFalseTotal
if (!root) { 0 114 114
808 0 hamt_vlist_release(cx, &top);
809 0 hamt_vec_clear(cx, &left);
810 0 hamt_vec_init(out);
811 0 return -1;
812 }
813 114 shift += HAMT_VEC_BITS;
814 }
815 4151 hamt_vec_clear(cx, &left);
816  
817 /* The root has two children at least: each tree's own root had, above
818 * the lowest level, and what the join put between them is one more. */
819 4151 out->count = a->count + b->count;
820 4151 out->shift = shift;
821 4151 out->root = root;
822 4151 out->tail = hamt_vnode_retain(b->tail);
823 4151 return 0;
824 }
825  
826 /* ---- cutting ------------------------------------------------------------ */
827  
828 /* A node at `level` over the n children in kids[], one of which has just
829 * been cut short. Cutting takes slots away without taking a child away, so
830 * the children are repacked exactly as a join repacks its run, and the node
831 * is no looser for having been cut. Takes over the caller's references to
832 * the children whether or not it succeeds. */
833 85241 static hamt_vnode *hamt_rrb_cut_node(void *cx, hamt_vnode **kids, uint32_t n, uint32_t level) {
834 hamt_vlist all, packed;
835 hamt_vnode *made;
836  
837 85241 memcpy(all.n, kids, (size_t)n * sizeof(void *));
838 85241 all.len = n;
839 85241 ▶ if (hamt_rrb_repack(cx, &all, level - HAMT_VEC_BITS, &packed)) {
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_rrb_repack(cx, &all, level - HAMT_VEC_BITS, &packed)) { 0 85241 85241
840 0 hamt_vlist_release(cx, &all);
841 0 return NULL;
842 }
843 85241 hamt_vlist_release(cx, &all);
844 85241 made = hamt_vnode_make(cx, packed.n, packed.len, level);
845 85241 ▶ if (!made) hamt_vlist_release(cx, &packed);
Branch: 1 branch
BranchTrueFalseTotal
if (!made) hamt_vlist_release(cx, &packed); 0 85241 85241
846 85241 return made;
847 }
848  
849 /* The first `keep` values under a node, as a node at the same level. `keep`
850 * is at least one and at most what the node holds. One reference, or NULL
851 * for no memory. Everything left of the cut is shared; the nodes along it
852 * are new. */
853 67244 static hamt_vnode *hamt_rrb_cut_right(void *cx, const hamt_vnode *n, uint32_t level, size_t keep) {
854 hamt_vnode *kids[HAMT_VEC_WIDTH], *sub;
855 67244 size_t i = keep - 1;
856 uint32_t k, j;
857  
858 67244 ▶ if (keep == hamt_vnode_count(n, level)) return hamt_vnode_retain((hamt_vnode *)n);
Branch: 1 branch
BranchTrueFalseTotal
if (keep == hamt_vnode_count(n, level)) return hamt_vnode_retain((hamt_vnode *)n); 1933 65311 67244
859 65311 ▶ if (level == 0) return hamt_vnode_leaf(cx, (void *const *)n->slot, (uint32_t)keep);
Branch: 1 branch
BranchTrueFalseTotal
if (level == 0) return hamt_vnode_leaf(cx, (void *const *)n->slot, (uint32_t)keep); 31667 33644 65311
860  
861 33644 k = hamt_vnode_child(n, level, &i);
862 33644 sub = hamt_rrb_cut_right(cx, (const hamt_vnode *)n->slot[k], level - HAMT_VEC_BITS, i + 1);
863 33644 ▶ if (!sub) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!sub) return NULL; 0 33644 33644
864 70633 ▶ for (j = 0; j < k; j++) kids[j] = hamt_vnode_retain((hamt_vnode *)n->slot[j]);
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < k; j++) kids[j] = hamt_vnode_retain((hamt_vnode *)n->slot[j]); 36989 33644 70633
865 33644 kids[k] = sub;
866 33644 return hamt_rrb_cut_node(cx, kids, k + 1, level);
867 }
868  
869 /* Everything under a node but its first `drop` values. `drop` is less than
870 * what the node holds. */
871 107499 static hamt_vnode *hamt_rrb_cut_left(void *cx, const hamt_vnode *n, uint32_t level, size_t drop) {
872 hamt_vnode *kids[HAMT_VEC_WIDTH], *sub;
873 107499 size_t i = drop;
874 107499 uint32_t k, j, m = 0;
875  
876 107499 ▶ if (drop == 0) return hamt_vnode_retain((hamt_vnode *)n);
Branch: 1 branch
BranchTrueFalseTotal
if (drop == 0) return hamt_vnode_retain((hamt_vnode *)n); 6429 101070 107499
877 101070 ▶ if (level == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (level == 0) 49473 51597 101070
878 49473 return hamt_vnode_leaf(cx, (void *const *)n->slot + drop, (uint32_t)(n->len - drop));
879  
880 51597 k = hamt_vnode_child(n, level, &i);
881 51597 sub = hamt_rrb_cut_left(cx, (const hamt_vnode *)n->slot[k], level - HAMT_VEC_BITS, i);
882 51597 ▶ if (!sub) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!sub) return NULL; 0 51597 51597
883 51597 kids[m++] = sub;
884 80583 ▶ for (j = k + 1; j < n->len; j++) kids[m++] = hamt_vnode_retain((hamt_vnode *)n->slot[j]);
Branch: 1 branch
BranchTrueFalseTotal
for (j = k + 1; j < n->len; j++) kids[m++] = hamt_vnode_retain((hamt_vnode *)n->slot[j]); 28986 51597 80583
885 51597 return hamt_rrb_cut_node(cx, kids, m, level);
886 }
887  
888 /* `out` becomes a vector of the `len` values of `v` starting at `from`,
889 * which must lie within it; `len` is at least one. `v` is not changed.
890 * `out` is uninitialised on the way in. 0, or -1 for no memory with `out`
891 * empty. */
892 73932 static int hamt_vec_slice(void *cx, hamt_vec *out, const hamt_vec *v, size_t from, size_t len) {
893 73932 size_t to = from + len, tailoff = hamt_vec_tailoff(v);
894 73932 hamt_vnode *root = NULL, *tail = NULL;
895 73932 uint32_t shift = v->shift;
896  
897 73932 hamt_vec_init(out);
898  
899 73932 ▶ if (to > tailoff) {
Branch: 1 branch
BranchTrueFalseTotal
if (to > tailoff) { 40332 33600 73932
900 /* Some of the tail is kept: that is the new tail. */
901 40332 ▶ size_t t0 = from > tailoff ? from - tailoff : 0, t1 = to - tailoff;
Branch: 1 branch
BranchTrueFalseTotal
size_t t0 = from > tailoff ? from - tailoff : 0, t1 = to - tailoff; 14160 26172 40332
902 40332 ▶ if (t0 == 0 && t1 == v->tail->len) tail = hamt_vnode_retain(v->tail);
Branch: 2 branches
BranchTrueFalseTotal
if (t0 == 0 && t1 == v->tail->len) tail = hamt_vnode_retain(v->tail); 26172 14160 40332
if (t0 == 0 && t1 == v->tail->len) tail = hamt_vnode_retain(v->tail); 5154 21018 26172
903 35178 else tail = hamt_vnode_leaf(cx, (void *const *)v->tail->slot + t0, (uint32_t)(t1 - t0));
904 40332 ▶ if (!tail) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!tail) return -1; 0 40332 40332
905 40332 ▶ if (from < tailoff) {
Branch: 1 branch
BranchTrueFalseTotal
if (from < tailoff) { 22302 18030 40332
906 22302 root = hamt_rrb_cut_left(cx, v->root, shift, from);
907 22302 ▶ if (!root) { hamt_vnode_release(cx, tail); return -1; }
Branch: 1 branch
BranchTrueFalseTotal
if (!root) { hamt_vnode_release(cx, tail); return -1; } 0 22302 22302
908 }
909 }
910 else {
911 /* It ends inside the tree: cut the right, then the left. The last
912 * leaf of what is left will be taken out as the tail. */
913 33600 hamt_vnode *right = hamt_rrb_cut_right(cx, v->root, shift, to);
914 33600 ▶ if (!right) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!right) return -1; 0 33600 33600
915 33600 root = hamt_rrb_cut_left(cx, right, shift, from);
916 33600 hamt_vnode_release(cx, right);
917 33600 ▶ if (!root) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!root) return -1; 0 33600 33600
918 }
919  
920 /* What is left may be far smaller than the tree it was cut from, and
921 * still as tall: a root with one child is a level too many, and a root
922 * with two is the two cut edges and nothing between them, which is
923 * exactly what a join takes. So the two are joined, level by level,
924 * until the root is one that holds something. */
925 75135 ▶ while (root && shift > HAMT_VEC_BITS) {
Branch: 2 branches
BranchTrueFalseTotal
while (root && shift > HAMT_VEC_BITS) { 57105 18030 75135
while (root && shift > HAMT_VEC_BITS) { 1957 55148 57105
926 hamt_vnode *down;
927 1957 ▶ if (root->len == 1) down = hamt_vnode_retain((hamt_vnode *)root->slot[0]);
Branch: 1 branch
BranchTrueFalseTotal
if (root->len == 1) down = hamt_vnode_retain((hamt_vnode *)root->slot[0]); 953 1004 1957
928 1004 ▶ else if (root->len == 2) {
Branch: 1 branch
BranchTrueFalseTotal
else if (root->len == 2) { 344 660 1004
929 hamt_vlist top;
930 344 ▶ if (hamt_rrb_join(cx, (const hamt_vnode *)root->slot[0], shift - HAMT_VEC_BITS,
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_rrb_join(cx, (const hamt_vnode *)root->slot[0], shift - HAMT_VEC_BITS, 0 344 344
931 344 (const hamt_vnode *)root->slot[1], shift - HAMT_VEC_BITS, &top)) {
932 0 hamt_vnode_release(cx, root);
933 0 ▶ if (tail) hamt_vnode_release(cx, tail);
Branch: 1 branch
BranchTrueFalseTotal
if (tail) hamt_vnode_release(cx, tail); 0 0 0
934 0 return -1;
935 }
936 344 ▶ if (top.len == 2) { hamt_vlist_release(cx, &top); break; } /* it does need both */
Branch: 1 branch
BranchTrueFalseTotal
if (top.len == 2) { hamt_vlist_release(cx, &top); break; } /* it does need both */ 94 250 344
937 250 down = top.n[0];
938 }
939 660 else break;
940 1203 hamt_vnode_release(cx, root);
941 1203 root = down;
942 1203 shift -= HAMT_VEC_BITS;
943 }
944 73932 out->count = len;
945 73932 ▶ out->shift = root ? shift : HAMT_VEC_BITS;
Branch: 1 branch
BranchTrueFalseTotal
out->shift = root ? shift : HAMT_VEC_BITS; 55902 18030 73932
946 73932 out->root = root;
947 73932 out->tail = tail;
948 73932 ▶ if (!tail && hamt_vec_pull_tail(cx, out)) { hamt_vec_clear(cx, out); return -1; }
Branch: 2 branches
BranchTrueFalseTotal
if (!tail && hamt_vec_pull_tail(cx, out)) { hamt_vec_clear(cx, out); return -1; } 33600 40332 73932
if (!tail && hamt_vec_pull_tail(cx, out)) { hamt_vec_clear(cx, out); return -1; } 0 33600 33600
949 73932 return 0;
950 }
951  
952 /* ---- the checker ------------------------------------------------------- */
953  
954 #define HAMT_VCHK_OK 0
955 #define HAMT_VCHK_EMPTY 1 /* count 0 with a root or a tail, or the reverse */
956 #define HAMT_VCHK_TAIL 2 /* a tail that is not a leaf of 1..32 */
957 #define HAMT_VCHK_ROOT 3 /* a root where there should be none, or none where one */
958 #define HAMT_VCHK_SHIFT 4 /* a shift that is not a positive multiple of 5 */
959 #define HAMT_VCHK_REFCNT 5 /* a node with a count of zero */
960 #define HAMT_VCHK_LEN 6 /* a node holding nothing, or more than 32 */
961 #define HAMT_VCHK_KIND 7 /* a leaf where a node belongs, or the reverse */
962 #define HAMT_VCHK_NOT_FULL 8 /* a regular node with a child that is not last and not full */
963 #define HAMT_VCHK_TALL 9 /* a root with one child above the lowest level */
964 #define HAMT_VCHK_TOTAL 10 /* the tree does not hold what the count says */
965 #define HAMT_VCHK_NULL 11 /* a slot holding nothing */
966 #define HAMT_VCHK_SIZES 12 /* a table that does not say what is under the node */
967 #define HAMT_VCHK_SPARE 13 /* a relaxed node with more children to spare than allowed */
968 #define HAMT_VCHK_LEAF_TABLE 14 /* a leaf with a table */
969  
970 /* How many values the subtree holds, recounted from its leaves; *rc gets
971 * the first rule broken. */
972 642919 static size_t hamt_vnode_check(const hamt_vnode *n, uint32_t level, uint32_t spare, int *rc) {
973 642919 size_t total = 0, full = (size_t)1 << level, slots = 0;
974 uint32_t i;
975  
976 642919 ▶ if (*rc) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (*rc) return 0; 0 642919 642919
977 642919 ▶ if (!n) { *rc = HAMT_VCHK_NULL; return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (!n) { *rc = HAMT_VCHK_NULL; return 0; } 0 642919 642919
978 642919 ▶ if (n->refcnt == 0) { *rc = HAMT_VCHK_REFCNT; return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (n->refcnt == 0) { *rc = HAMT_VCHK_REFCNT; return 0; } 0 642919 642919
979 642919 ▶ if (n->len == 0 || n->len > HAMT_VEC_WIDTH) { *rc = HAMT_VCHK_LEN; return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (n->len == 0 || n->len > HAMT_VEC_WIDTH) { *rc = HAMT_VCHK_LEN; return 0; } 642919 0 642919
if (n->len == 0 || n->len > HAMT_VEC_WIDTH) { *rc = HAMT_VCHK_LEN; return 0; } 0 642919 642919
980 642919 ▶ if ((n->leaf != 0) != (level == 0)) { *rc = HAMT_VCHK_KIND; return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if ((n->leaf != 0) != (level == 0)) { *rc = HAMT_VCHK_KIND; return 0; } 0 642919 642919
981  
982 642919 ▶ if (level == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (level == 0) { 589671 53248 642919
983 589671 ▶ if (n->sizes) { *rc = HAMT_VCHK_LEAF_TABLE; return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (n->sizes) { *rc = HAMT_VCHK_LEAF_TABLE; return 0; } 0 589671 589671
984 18587150 ▶ for (i = 0; i < n->len; i++) if (!n->slot[i]) { *rc = HAMT_VCHK_NULL; return 0; }
Branch: 2 branches
BranchTrueFalseTotal
for (i = 0; i < n->len; i++) if (!n->slot[i]) { *rc = HAMT_VCHK_NULL; return 0; } 0 17997479 17997479
for (i = 0; i < n->len; i++) if (!n->slot[i]) { *rc = HAMT_VCHK_NULL; return 0; } 17997479 589671 18587150
985 589671 return n->len;
986 }
987 660865 ▶ for (i = 0; i < n->len; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n->len; i++) { 607617 53248 660865
988 607617 const hamt_vnode *kid = (const hamt_vnode *)n->slot[i];
989 607617 size_t got = hamt_vnode_check(kid, level - HAMT_VEC_BITS, spare, rc);
990 607617 ▶ if (*rc) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (*rc) return 0; 0 607617 607617
991 607617 total += got;
992 607617 slots += kid->len;
993 607617 ▶ if (n->sizes) { if (n->sizes[i] != total) { *rc = HAMT_VCHK_SIZES; return 0; } }
Branch: 2 branches
BranchTrueFalseTotal
if (n->sizes) { if (n->sizes[i] != total) { *rc = HAMT_VCHK_SIZES; return 0; } } 50662 556955 607617
if (n->sizes) { if (n->sizes[i] != total) { *rc = HAMT_VCHK_SIZES; return 0; } } 0 50662 50662
994 556955 ▶ else if (i + 1 < n->len && got != full) { *rc = HAMT_VCHK_NOT_FULL; return 0; }
Branch: 2 branches
BranchTrueFalseTotal
else if (i + 1 < n->len && got != full) { *rc = HAMT_VCHK_NOT_FULL; return 0; } 518954 38001 556955
else if (i + 1 < n->len && got != full) { *rc = HAMT_VCHK_NOT_FULL; return 0; } 0 518954 518954
995 }
996 /* No more children than the slots under them need, plus the spare. */
997 53248 ▶ if (n->len > (slots + HAMT_VEC_MASK) / HAMT_VEC_WIDTH + spare) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->len > (slots + HAMT_VEC_MASK) / HAMT_VEC_WIDTH + spare) { 0 53248 53248
998 0 *rc = HAMT_VCHK_SPARE;
999 0 return 0;
1000 }
1001 53248 return total;
1002 }
1003  
1004 /* 0 when the vector is one this library could have built, otherwise the
1005 * number of the first rule it breaks. Visits every node.
1006 *
1007 * `spare` is how many more children a node may have than the slots under
1008 * them need, for a caller that wants to hold a vector to that as well.
1009 *
1010 * It is NOT something every vector satisfies, and hamt_vec_check does not
1011 * ask it. A join repacks the run of nodes along its seam until the RUN is
1012 * within HAMT_VEC_EXTRAS of the shortest it could be, and a cut does the
1013 * same for each node along the cut. That bounds the run, not each node
1014 * made from it: one level up, the same repacking moves whole children from
1015 * one parent to the next, and a parent can end up holding the loose end of
1016 * one neighbour and the loose start of another. So looseness is put right
1017 * where two trees meet and can gather, a little, elsewhere. What holds for
1018 * a vector made by joining and cutting vectors that were only ever pushed
1019 * to is the bound itself, and the tests hold those to it. What is held for
1020 * every vector is measured instead: its height, and how far a lookup steps
1021 * along a table. */
1022 80738 static int hamt_vec_check_spare(const hamt_vec *v, uint32_t spare) {
1023 size_t tailoff, total;
1024 uint32_t i;
1025 80738 int rc = 0;
1026  
1027 80738 ▶ if (v->count == 0) return (v->root || v->tail) ? HAMT_VCHK_EMPTY : HAMT_VCHK_OK;
Branch: 3 branches
BranchTrueFalseTotal
if (v->count == 0) return (v->root || v->tail) ? HAMT_VCHK_EMPTY : HAMT_VCHK_OK; 2849 77889 80738
if (v->count == 0) return (v->root || v->tail) ? HAMT_VCHK_EMPTY : HAMT_VCHK_OK; 2849 0 2849
if (v->count == 0) return (v->root || v->tail) ? HAMT_VCHK_EMPTY : HAMT_VCHK_OK; 0 2849 2849
1028 77889 ▶ if (!v->tail) return HAMT_VCHK_EMPTY;
Branch: 1 branch
BranchTrueFalseTotal
if (!v->tail) return HAMT_VCHK_EMPTY; 0 77889 77889
1029 77889 ▶ if (!v->tail->leaf || v->tail->len == 0 || v->tail->len > HAMT_VEC_WIDTH
Branch: 3 branches
BranchTrueFalseTotal
if (!v->tail->leaf || v->tail->len == 0 || v->tail->len > HAMT_VEC_WIDTH 77889 0 77889
if (!v->tail->leaf || v->tail->len == 0 || v->tail->len > HAMT_VEC_WIDTH 77889 0 77889
if (!v->tail->leaf || v->tail->len == 0 || v->tail->len > HAMT_VEC_WIDTH 77889 0 77889
1030 77889 ▶ || v->tail->len > v->count) return HAMT_VCHK_TAIL;
Branch: 1 branch
BranchTrueFalseTotal
|| v->tail->len > v->count) return HAMT_VCHK_TAIL; 0 77889 77889
1031 77889 ▶ if (v->tail->sizes) return HAMT_VCHK_LEAF_TABLE;
Branch: 1 branch
BranchTrueFalseTotal
if (v->tail->sizes) return HAMT_VCHK_LEAF_TABLE; 0 77889 77889
1032 77889 ▶ if (v->tail->refcnt == 0) return HAMT_VCHK_REFCNT;
Branch: 1 branch
BranchTrueFalseTotal
if (v->tail->refcnt == 0) return HAMT_VCHK_REFCNT; 0 77889 77889
1033 956902 ▶ for (i = 0; i < v->tail->len; i++) if (!v->tail->slot[i]) return HAMT_VCHK_NULL;
Branch: 2 branches
BranchTrueFalseTotal
for (i = 0; i < v->tail->len; i++) if (!v->tail->slot[i]) return HAMT_VCHK_NULL; 0 879013 879013
for (i = 0; i < v->tail->len; i++) if (!v->tail->slot[i]) return HAMT_VCHK_NULL; 879013 77889 956902
1034  
1035 77889 tailoff = v->count - v->tail->len;
1036 77889 ▶ if ((tailoff == 0) != (v->root == NULL)) return HAMT_VCHK_ROOT;
Branch: 1 branch
BranchTrueFalseTotal
if ((tailoff == 0) != (v->root == NULL)) return HAMT_VCHK_ROOT; 0 77889 77889
1037 77889 ▶ if (!v->root) return HAMT_VCHK_OK;
Branch: 1 branch
BranchTrueFalseTotal
if (!v->root) return HAMT_VCHK_OK; 42587 35302 77889
1038  
1039 35302 ▶ if (v->shift == 0 || v->shift % HAMT_VEC_BITS || v->shift > 60) return HAMT_VCHK_SHIFT;
Branch: 3 branches
BranchTrueFalseTotal
if (v->shift == 0 || v->shift % HAMT_VEC_BITS || v->shift > 60) return HAMT_VCHK_SHIFT; 35302 0 35302
if (v->shift == 0 || v->shift % HAMT_VEC_BITS || v->shift > 60) return HAMT_VCHK_SHIFT; 35302 0 35302
if (v->shift == 0 || v->shift % HAMT_VEC_BITS || v->shift > 60) return HAMT_VCHK_SHIFT; 0 35302 35302
1040 35302 ▶ if (v->shift > HAMT_VEC_BITS && v->root->len == 1) return HAMT_VCHK_TALL;
Branch: 2 branches
BranchTrueFalseTotal
if (v->shift > HAMT_VEC_BITS && v->root->len == 1) return HAMT_VCHK_TALL; 1643 33659 35302
if (v->shift > HAMT_VEC_BITS && v->root->len == 1) return HAMT_VCHK_TALL; 0 1643 1643
1041 35302 total = hamt_vnode_check(v->root, v->shift, spare, &rc);
1042 35302 ▶ if (rc) return rc;
Branch: 1 branch
BranchTrueFalseTotal
if (rc) return rc; 0 35302 35302
1043 35302 ▶ return total == tailoff ? HAMT_VCHK_OK : HAMT_VCHK_TOTAL;
Branch: 1 branch
BranchTrueFalseTotal
return total == tailoff ? HAMT_VCHK_OK : HAMT_VCHK_TOTAL; 35302 0 35302
1044 }
1045  
1046 80738 static int hamt_vec_check(const hamt_vec *v) {
1047 80738 return hamt_vec_check_spare(v, HAMT_VEC_WIDTH); /* no node has more children than that */
1048 }
1049  
1050 /* How many levels of nodes are over the leaves. */
1051 0 static uint32_t hamt_vec_height(const hamt_vec *v) {
1052 0 ▶ return v->root ? v->shift / HAMT_VEC_BITS : 0;
Branch: 1 branch
BranchTrueFalseTotal
return v->root ? v->shift / HAMT_VEC_BITS : 0; 0 0 0
1053 }
1054  
1055 #endif
« include/hamt/hamt_abi_impl.h ↑ Summary include/hamt/hamt_mut.h »