| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!c) return NULL; |
0 |
219601 |
219601 |
|
| 147 |
219601 |
▶ | if (n->sizes) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| while (n->sizes[k] <= *i) { k++; HAMT_VEC_STEPPED(); } |
31086 |
57575 |
88661 |
|
| 187 |
57575 |
▶ | if (k) *i -= n->sizes[k - 1]; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!node) return NULL; |
0 |
91491 |
91491 |
|
| 202 |
163726 |
▶ | for (k = 0; k + 1 < n && regular; k++) |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (hamt_vnode_count(kids[k], level - HAMT_VEC_BITS) != full) regular = 0; |
17318 |
54917 |
72235 |
|
| 204 |
|
| |
| 205 |
91491 |
▶ | if (!regular) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (dst->root) hamt_vnode_retain(dst->root); |
145233 |
30856 |
176089 |
|
| 242 |
176089 |
▶ | if (dst->tail) hamt_vnode_retain(dst->tail); |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (root) hamt_vnode_release(cx, root); |
183457 |
83762 |
267219 |
|
| 252 |
267219 |
▶ | if (tail) hamt_vnode_release(cx, tail); |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!n) { |
0 |
417 |
417 |
|
| 293 |
0 |
▶ | while (top != leaf) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!v->root) { |
3038 |
14684 |
17722 |
|
| 323 |
3038 |
| n = hamt_vnode_new(cx, 0); |
| 324 |
3038 |
▶ | if (!n) return -1; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!n) { |
0 |
98 |
98 |
|
| 348 |
|
| /* Take the chain down again without touching the leaf. */ |
| 349 |
0 |
▶ | while (path != leaf) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!n) return -1; |
0 |
24620 |
24620 |
|
| 367 |
24620 |
▶ | if (level == host_level) { host = n; break; } |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!path) { |
0 |
14586 |
14586 |
|
| 384 |
0 |
▶ | if (table) HAMT_FREE(cx, table, HAMT_VEC_SIZES_BYTES); |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| while (d > 0) { |
36767 |
24867 |
61634 |
|
| 424 |
36767 |
| n = path[--d]; |
| 425 |
36767 |
▶ | if (--n->len > 0) break; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (d == 0) v->root = NULL; |
24867 |
116 |
24983 |
|
| 428 |
|
| } |
| 429 |
39394 |
▶ | while (d > 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!fresh) return -1; |
0 |
21783 |
21783 |
|
| 462 |
21783 |
▶ | if (v->tail && hamt_vec_push_leaf(cx, v, v->tail)) { |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (hamt_vec_get(v, i) == val) return 0; |
0 |
40349 |
40349 |
|
| 485 |
|
| |
| 486 |
40349 |
▶ | if (i >= tailoff) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (i >= tailoff) { |
5014 |
35335 |
40349 |
|
| 487 |
5014 |
| n = hamt_vnode_own(cx, &v->tail); |
| 488 |
5014 |
▶ | if (!n) return -1; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (v->count == 0) return 0; |
9 |
103235 |
103244 |
|
| 528 |
|
| |
| 529 |
103235 |
▶ | if (v->tail->len > 1) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| } while (carry > 0); |
4304 |
2296 |
6600 |
|
| 667 |
17872 |
▶ | for (j = i; j + 1 < n; j++) c[j] = c[j + 1]; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!a) return -1; |
0 |
5283 |
5283 |
|
| 716 |
5283 |
▶ | if (kids->len > first) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (rc) return rc; |
0 |
5283 |
5283 |
|
| 753 |
|
| |
| 754 |
5283 |
| all.len = 0; |
| 755 |
5283 |
▶ | if (ll >= rl) |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (b->count == 0) { hamt_vec_share(out, a); return 0; } |
1107 |
13060 |
14167 |
|
| 782 |
|
| |
| 783 |
13060 |
▶ | if (!b->root) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (drop == 0) return hamt_vnode_retain((hamt_vnode *)n); |
6429 |
101070 |
107499 |
|
| 877 |
101070 |
▶ | if (level == 0) |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!tail) return -1; |
0 |
40332 |
40332 |
|
| 905 |
40332 |
▶ | if (from < tailoff) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (*rc) return 0; |
0 |
642919 |
642919 |
|
| 977 |
642919 |
▶ | if (!n) { *rc = HAMT_VCHK_NULL; return 0; } |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if ((n->leaf != 0) != (level == 0)) { *rc = HAMT_VCHK_KIND; return 0; } |
0 |
642919 |
642919 |
|
| 981 |
|
| |
| 982 |
642919 |
▶ | if (level == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (level == 0) { |
589671 |
53248 |
642919 |
|
| 983 |
589671 |
▶ | if (n->sizes) { *rc = HAMT_VCHK_LEAF_TABLE; return 0; } |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| || 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (rc) return rc; |
0 |
35302 |
35302 |
|
| 1043 |
35302 |
▶ | return total == tailoff ? HAMT_VCHK_OK : HAMT_VCHK_TOTAL; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| return v->root ? v->shift / HAMT_VEC_BITS : 0; |
0 |
0 |
0 |
|
| 1053 |
|
| } |
| 1054 |
|
| |
| 1055 |
|
| #endif |