include/hamt/hamt_algebra.h

filter: Statementstmt 99.2% 524 / 528 Branchbran 92.7% 499 / 538 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 95.9% 1023 / 1066 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/vector_transient.xs ↑ Summary xs/vector.xs »
1 #ifndef HAMT_ALGEBRA_H
2 #define HAMT_ALGEBRA_H
3  
4 /* Operations over TWO tries at once: are they equal, what is their union,
5 * where do they differ.
6 *
7 * All three walk the two together, position by position, and all three get
8 * their speed from one fact: if the two nodes at the same place are the same
9 * pointer, everything under them is the same, and there is nothing to do.
10 * Two versions of one map differ along a handful of paths, so comparing or
11 * merging them costs what changed between them and not what they hold.
12 *
13 * They can be walked in step at all because of the canonical shape: the
14 * same keys always make the same trie, so a position that holds a child in
15 * one and an entry in the other is a real difference in content, never an
16 * accident of history.
17 *
18 * Callbacks return 0 to carry on. Anything else stops the operation, which
19 * unwinds what it had built and reports HAMT_ERR_ABORT; a callback that ran
20 * out of memory returns HAMT_ERR_OOM and that is reported instead. */
21  
22 #define HAMT_OK 0
23 #define HAMT_ERR_ABORT 1
24 #define HAMT_ERR_OOM 2
25  
26 /* How many entries a subtree holds. Visits every node of it. */
27 146110 static size_t hamt_node_count(const hamt_node *n) {
28 uint32_t nd, N, i;
29 size_t total;
30 146110 ▶ if (!n) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return 0; 0 146110 146110
31 146110 nd = hamt_node_ndata(n);
32 146110 N = hamt_node_nslots(n);
33 146110 total = nd;
34 262393 ▶ for (i = nd; i < N; i++) total += hamt_node_count((const hamt_node *)n->slot[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = nd; i < N; i++) total += hamt_node_count((const hamt_node *)n->slot[i]); 116283 146110 262393
35 146110 return total;
36 }
37  
38 /* ---- equality ---------------------------------------------------------- */
39  
40 /* 1 equal, 0 not, negative to stop. */
41 typedef int (*hamt_eq_fn)(void *ud, void *cx, void *va, void *vb);
42  
43 typedef struct hamt_eq_ctx {
44 void *cx;
45 hamt_eq_fn eq; /* NULL: HAMT_VAL_EQ */
46 void *ud;
47 size_t visits; /* node pairs looked at */
48 } hamt_eq_ctx;
49  
50 210600 static int hamt_val_same(hamt_eq_ctx *c, void *va, void *vb) {
51 210600 ▶ if (va == vb) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (va == vb) return 1; 5229 205371 210600
52 205371 ▶ if (!va || !vb) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!va || !vb) return 0; 205371 0 205371
if (!va || !vb) return 0; 0 205371 205371
53 205371 ▶ if (c->eq) return c->eq(c->ud, c->cx, va, vb);
Branch: 1 branch
BranchTrueFalseTotal
if (c->eq) return c->eq(c->ud, c->cx, va, vb); 8071 197300 205371
54 197300 return HAMT_VAL_EQ(c->cx, va, vb) ? 1 : 0;
55 }
56  
57 /* 1 when the two subtrees hold the same keys with equal values, 0 when they
58 * do not, negative when the comparison callback stopped it. */
59 192409 static int hamt_node_equal(hamt_eq_ctx *c, const hamt_node *a, const hamt_node *b) {
60 uint32_t nd, N, i, j;
61  
62 192409 ▶ if (a == b) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (a == b) return 1; 2495 189914 192409
63 189914 ▶ if (!a || !b) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!a || !b) return 0; 189914 0 189914
if (!a || !b) return 0; 0 189914 189914
64 189914 c->visits++;
65  
66 189914 ▶ if (a->datamap != b->datamap || a->nodemap != b->nodemap || a->ncoll != b->ncoll)
Branch: 3 branches
BranchTrueFalseTotal
if (a->datamap != b->datamap || a->nodemap != b->nodemap || a->ncoll != b->ncoll) 189875 39 189914
if (a->datamap != b->datamap || a->nodemap != b->nodemap || a->ncoll != b->ncoll) 189875 0 189875
if (a->datamap != b->datamap || a->nodemap != b->nodemap || a->ncoll != b->ncoll) 14 189861 189875
67 53 return 0;
68 189861 nd = hamt_node_ndata(a);
69 189861 N = hamt_node_nslots(a);
70  
71 189861 ▶ if (a->ncoll) {
Branch: 1 branch
BranchTrueFalseTotal
if (a->ncoll) { 14906 174955 189861
72 /* The same keys, in whatever order each node happens to hold them. */
73 100046 ▶ for (i = 0; i < nd; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nd; i++) { 85154 14892 100046
74 85154 const hamt_entry *ea = (const hamt_entry *)a->slot[i];
75 85154 const hamt_entry *eb = NULL;
76 int rc;
77 932945 ▶ for (j = 0; j < nd; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < nd; j++) { 932937 8 932945
78 932937 eb = (const hamt_entry *)b->slot[j];
79 932937 ▶ if (hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) break; 85146 847791 932937
80 }
81 85154 ▶ if (j == nd) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (j == nd) return 0; 8 85146 85154
82 85146 rc = hamt_val_same(c, ea->val, eb->val);
83 85146 ▶ if (rc <= 0) return rc;
Branch: 1 branch
BranchTrueFalseTotal
if (rc <= 0) return rc; 6 85140 85146
84 }
85 14892 return 1;
86 }
87  
88 272307 ▶ for (i = 0; i < nd; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nd; i++) { 97388 174919 272307
89 97388 const hamt_entry *ea = (const hamt_entry *)a->slot[i];
90 97388 const hamt_entry *eb = (const hamt_entry *)b->slot[i];
91 int rc;
92 97388 ▶ if (ea == eb) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (ea == eb) continue; 14053 83335 97388
93 83335 ▶ if (!hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) return 0; 0 83335 83335
94 83335 rc = hamt_val_same(c, ea->val, eb->val);
95 83332 ▶ if (rc <= 0) return rc;
Branch: 1 branch
BranchTrueFalseTotal
if (rc <= 0) return rc; 33 83299 83332
96 }
97 366379 ▶ for (; i < N; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (; i < N; i++) { 191828 174551 366379
98 191828 int rc = hamt_node_equal(c, (const hamt_node *)a->slot[i],
99 191828 (const hamt_node *)b->slot[i]);
100 191828 ▶ if (rc <= 0) return rc;
Branch: 1 branch
BranchTrueFalseTotal
if (rc <= 0) return rc; 368 191460 191828
101 }
102 174551 return 1;
103 }
104  
105 /* ---- union ------------------------------------------------------------- */
106  
107 /* Called for a key in both maps whose two values are not the same pointer.
108 * Sets *out to the entry the result should hold, with one reference for the
109 * caller: `ea` or `eb` retained, or a new entry under the same key.
110 * Returns HAMT_OK, HAMT_ERR_ABORT or HAMT_ERR_OOM. */
111 typedef int (*hamt_resolve_fn)(void *ud, void *cx, hamt_entry *ea,
112 hamt_entry *eb, hamt_entry **out);
113  
114 typedef struct hamt_merge_ctx {
115 void *cx;
116 hamt_resolve_fn resolve; /* NULL: the second map's entry wins */
117 void *ud;
118 size_t added; /* keys of the second map that the first lacked */
119 size_t visits; /* node pairs looked at */
120 int err;
121 } hamt_merge_ctx;
122  
123 /* The entry for a key both maps hold. One reference, or NULL with err set. */
124 48797 static hamt_entry *hamt_merge_resolve(hamt_merge_ctx *c, hamt_entry *ea,
125 hamt_entry *eb) {
126 48797 hamt_entry *out = NULL;
127 int rc;
128  
129 /* The first map's entry when there is nothing to choose between, so the
130 * result shares with the first map wherever it can. */
131 48797 ▶ if (ea == eb || ea->val == eb->val) return hamt_entry_retain(ea);
Branch: 2 branches
BranchTrueFalseTotal
if (ea == eb || ea->val == eb->val) return hamt_entry_retain(ea); 44333 4464 48797
if (ea == eb || ea->val == eb->val) return hamt_entry_retain(ea); 40353 3980 44333
132 3980 ▶ if (!c->resolve) return hamt_entry_retain(eb);
Branch: 1 branch
BranchTrueFalseTotal
if (!c->resolve) return hamt_entry_retain(eb); 2045 1935 3980
133  
134 1935 rc = c->resolve(c->ud, c->cx, ea, eb, &out);
135 1935 ▶ if (rc != HAMT_OK) { c->err = rc; return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (rc != HAMT_OK) { c->err = rc; return NULL; } 21 1914 1935
136 1914 return out;
137 }
138  
139 /* One entry from one map into a subtree of the other. `e_is_first` says
140 * which map the entry came from, which is the order the resolver is told.
141 * `*found` is whether the subtree already had the key. Returns `n` itself,
142 * retained, when the subtree is unchanged. */
143 13883 static hamt_node *hamt_merge_put(hamt_merge_ctx *c, hamt_node *n, unsigned depth,
144 hamt_entry *e, int e_is_first, int *found) {
145 13883 hamt_entry *old = hamt_node_find(n, depth, e->key, e->klen, e->utf8, e->hash);
146 hamt_entry *r;
147 hamt_node *out;
148 13883 int added = 0;
149  
150 13883 *found = old != NULL;
151 13883 ▶ if (!old) {
Branch: 1 branch
BranchTrueFalseTotal
if (!old) { 6829 7054 13883
152 6829 out = hamt_node_put(c->cx, n, depth, e, &added);
153 6829 ▶ if (!out) c->err = HAMT_ERR_OOM;
Branch: 1 branch
BranchTrueFalseTotal
if (!out) c->err = HAMT_ERR_OOM; 0 6829 6829
154 6829 return out;
155 }
156  
157 7054 ▶ r = e_is_first ? hamt_merge_resolve(c, e, old) : hamt_merge_resolve(c, old, e);
Branch: 1 branch
BranchTrueFalseTotal
r = e_is_first ? hamt_merge_resolve(c, e, old) : hamt_merge_resolve(c, old, e); 3470 3584 7054
158 7054 ▶ if (!r) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return NULL; 3 7051 7054
159 /* When the choice is the entry already there, the put gives `n` back. */
160 7051 out = hamt_node_put(c->cx, n, depth, r, &added);
161 7051 hamt_entry_release(c->cx, r);
162 7051 ▶ if (!out) c->err = HAMT_ERR_OOM;
Branch: 1 branch
BranchTrueFalseTotal
if (!out) c->err = HAMT_ERR_OOM; 0 7051 7051
163 7051 return out;
164 }
165  
166 static hamt_node *hamt_node_merge(hamt_merge_ctx *c, hamt_node *a, hamt_node *b,
167 unsigned depth);
168  
169 /* Two collision nodes: the first's entries, each resolved against the
170 * second's where the key is in both, then the second's that the first has
171 * not got. */
172 8111 static hamt_node *hamt_coll_merge(hamt_merge_ctx *c, hamt_node *a, hamt_node *b) {
173 8111 size_t cap = (size_t)a->ncoll + (size_t)b->ncoll;
174 8111 size_t bytes = cap * sizeof(void *);
175 hamt_entry **list;
176 8111 uint32_t n = 0, i, j;
177 8111 int same_a = 1, same_b = 1;
178 8111 hamt_node *r = NULL;
179  
180 8111 ▶ if (cap > 0xffffffffU) { c->err = HAMT_ERR_OOM; return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (cap > 0xffffffffU) { c->err = HAMT_ERR_OOM; return NULL; } 0 8111 8111
181 8111 list = (hamt_entry **)HAMT_ALLOC(c->cx, bytes);
182 8111 ▶ if (!list) { c->err = HAMT_ERR_OOM; return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!list) { c->err = HAMT_ERR_OOM; return NULL; } 0 8111 8111
183  
184 54885 ▶ for (i = 0; i < a->ncoll; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < a->ncoll; i++) { 46774 8111 54885
185 46774 hamt_entry *ea = (hamt_entry *)a->slot[i], *eb = NULL, *e;
186 343358 ▶ for (j = 0; j < b->ncoll; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < b->ncoll; j++) { 309616 33742 343358
187 309616 eb = (hamt_entry *)b->slot[j];
188 309616 ▶ if (hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) break; 13032 296584 309616
189 }
190 46774 ▶ if (j == b->ncoll) {
Branch: 1 branch
BranchTrueFalseTotal
if (j == b->ncoll) { 33742 13032 46774
191 33742 e = hamt_entry_retain(ea);
192 33742 same_b = 0;
193 }
194 else {
195 13032 e = hamt_merge_resolve(c, ea, eb);
196 13032 ▶ if (!e) goto fail;
Branch: 1 branch
BranchTrueFalseTotal
if (!e) goto fail; 0 13032 13032
197 13032 ▶ if (e != ea) same_a = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (e != ea) same_a = 0; 1362 11670 13032
198 13032 ▶ if (e != eb) same_b = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (e != eb) same_b = 0; 10518 2514 13032
199 }
200 46774 list[n++] = e;
201 }
202 53887 ▶ for (j = 0; j < b->ncoll; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < b->ncoll; j++) { 45776 8111 53887
203 45776 hamt_entry *eb = (hamt_entry *)b->slot[j];
204 343063 ▶ for (i = 0; i < a->ncoll; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < a->ncoll; i++) { 310319 32744 343063
205 310319 hamt_entry *ea = (hamt_entry *)a->slot[i];
206 310319 ▶ if (hamt_entry_key_eq(ea, eb->key, eb->klen, eb->utf8, eb->hash)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_entry_key_eq(ea, eb->key, eb->klen, eb->utf8, eb->hash)) break; 13032 297287 310319
207 }
208 45776 ▶ if (i < a->ncoll) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (i < a->ncoll) continue; 13032 32744 45776
209 32744 list[n++] = hamt_entry_retain(eb);
210 32744 c->added++;
211 32744 same_a = 0;
212 }
213  
214 8111 ▶ if (same_a) r = hamt_node_retain(a);
Branch: 1 branch
BranchTrueFalseTotal
if (same_a) r = hamt_node_retain(a); 628 7483 8111
215 7483 ▶ else if (same_b) r = hamt_node_retain(b);
Branch: 1 branch
BranchTrueFalseTotal
else if (same_b) r = hamt_node_retain(b); 185 7298 7483
216 else {
217 7298 r = hamt_node_new(c->cx, n);
218 7298 ▶ if (!r) { c->err = HAMT_ERR_OOM; goto fail; }
Branch: 1 branch
BranchTrueFalseTotal
if (!r) { c->err = HAMT_ERR_OOM; goto fail; } 0 7298 7298
219 7298 r->ncoll = n;
220 7298 memcpy(r->slot, list, (size_t)n * sizeof(void *));
221 7298 HAMT_FREE(c->cx, list, bytes);
222 7298 return r; /* the list's references are the node's now */
223 }
224  
225 813 fail:
226 4784 ▶ for (i = 0; i < n; i++) hamt_entry_release(c->cx, list[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) hamt_entry_release(c->cx, list[i]); 3971 813 4784
227 813 HAMT_FREE(c->cx, list, bytes);
228 813 return r;
229 }
230  
231 /* The union of two subtrees that hang at the same place. One reference, or
232 * NULL with err set. Returns `a` itself when the result is exactly `a`, and
233 * `b` itself when it is exactly `b`, so a caller can tell that nothing
234 * changed on that side by comparing pointers. */
235 132575 static hamt_node *hamt_node_merge(hamt_merge_ctx *c, hamt_node *a, hamt_node *b,
236 unsigned depth) {
237 void *rd[32], *rc[32]; /* what goes in the result: entries, children */
238 132575 uint32_t datamap = 0, nodemap = 0, nd = 0, nc = 0, pos, i, N;
239 uint32_t na_slots, nb_slots;
240 132575 int same_a = 1, same_b = 1;
241 hamt_node *r;
242  
243 132575 ▶ if (a == b) return hamt_node_retain(a);
Branch: 1 branch
BranchTrueFalseTotal
if (a == b) return hamt_node_retain(a); 9328 123247 132575
244 123247 c->visits++;
245 123247 ▶ if (a->ncoll) return hamt_coll_merge(c, a, b);
Branch: 1 branch
BranchTrueFalseTotal
if (a->ncoll) return hamt_coll_merge(c, a, b); 8111 115136 123247
246  
247 115136 na_slots = hamt_node_nslots(a);
248 115136 nb_slots = hamt_node_nslots(b);
249  
250 /* Every pointer put in rd[] and rc[] is one this function owns a
251 * reference to, shared or newly made alike, so the two ways out - build
252 * the node, or give everything back - need not tell them apart. */
253 3799037 ▶ for (pos = 0; pos < 32; pos++) {
Branch: 1 branch
BranchTrueFalseTotal
for (pos = 0; pos < 32; pos++) { 3683926 115111 3799037
254 3683926 uint32_t bit = (uint32_t)1 << pos;
255 3683926 hamt_entry *ea = NULL, *eb = NULL;
256 3683926 hamt_node *ca = NULL, *cb = NULL;
257  
258 3683926 ▶ if (a->datamap & bit)
Branch: 1 branch
BranchTrueFalseTotal
if (a->datamap & bit) 110728 3573198 3683926
259 110728 ea = (hamt_entry *)a->slot[hamt_popcnt32(a->datamap & (bit - 1))];
260 3573198 ▶ else if (a->nodemap & bit)
Branch: 1 branch
BranchTrueFalseTotal
else if (a->nodemap & bit) 145507 3427691 3573198
261 145507 ca = (hamt_node *)a->slot[na_slots - 1 - hamt_popcnt32(a->nodemap & (bit - 1))];
262 3683926 ▶ if (b->datamap & bit)
Branch: 1 branch
BranchTrueFalseTotal
if (b->datamap & bit) 109247 3574679 3683926
263 109247 eb = (hamt_entry *)b->slot[hamt_popcnt32(b->datamap & (bit - 1))];
264 3574679 ▶ else if (b->nodemap & bit)
Branch: 1 branch
BranchTrueFalseTotal
else if (b->nodemap & bit) 144923 3429756 3574679
265 144923 cb = (hamt_node *)b->slot[nb_slots - 1 - hamt_popcnt32(b->nodemap & (bit - 1))];
266  
267 3683926 ▶ if (!ea && !ca && !eb && !cb) continue;
Branch: 4 branches
BranchTrueFalseTotal
if (!ea && !ca && !eb && !cb) continue; 3573198 110728 3683926
if (!ea && !ca && !eb && !cb) continue; 3427691 145507 3573198
if (!ea && !ca && !eb && !cb) continue; 3363875 63816 3427691
if (!ea && !ca && !eb && !cb) continue; 3356497 7378 3363875
268  
269 327429 ▶ if (!eb && !cb) { /* the first map's alone */
Branch: 2 branches
BranchTrueFalseTotal
if (!eb && !cb) { /* the first map's alone */ 218182 109247 327429
if (!eb && !cb) { /* the first map's alone */ 73259 144923 218182
270 73259 same_b = 0;
271 73259 ▶ if (ea) { rd[nd++] = hamt_entry_retain(ea); datamap |= bit; }
Branch: 1 branch
BranchTrueFalseTotal
if (ea) { rd[nd++] = hamt_entry_retain(ea); datamap |= bit; } 65754 7505 73259
272 7505 else { rc[nc++] = hamt_node_retain(ca); nodemap |= bit; }
273 }
274 254170 ▶ else if (!ea && !ca) { /* the second's alone */
Branch: 2 branches
BranchTrueFalseTotal
else if (!ea && !ca) { /* the second's alone */ 209196 44974 254170
else if (!ea && !ca) { /* the second's alone */ 71194 138002 209196
275 71194 same_a = 0;
276 71194 ▶ if (eb) { rd[nd++] = hamt_entry_retain(eb); datamap |= bit; c->added++; }
Branch: 1 branch
BranchTrueFalseTotal
if (eb) { rd[nd++] = hamt_entry_retain(eb); datamap |= bit; c->added++; } 63816 7378 71194
277 else {
278 7378 rc[nc++] = hamt_node_retain(cb);
279 7378 nodemap |= bit;
280 7378 c->added += hamt_node_count(cb);
281 }
282 }
283 182976 ▶ else if (ea && eb) {
Branch: 2 branches
BranchTrueFalseTotal
else if (ea && eb) { 44974 138002 182976
else if (ea && eb) { 38261 6713 44974
284 76504 ▶ if (hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) {
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) { 28711 9550 38261
285 28711 hamt_entry *e = hamt_merge_resolve(c, ea, eb);
286 28711 ▶ if (!e) goto fail;
Branch: 1 branch
BranchTrueFalseTotal
if (!e) goto fail; 18 28693 28711
287 28693 ▶ if (e != ea) same_a = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (e != ea) same_a = 0; 1857 26836 28693
288 28693 ▶ if (e != eb) same_b = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (e != eb) same_b = 0; 24784 3909 28693
289 28693 rd[nd++] = e;
290 28693 datamap |= bit;
291 }
292 else { /* two keys, one position */
293 9550 hamt_node *sub = hamt_node_pair(c->cx, ea, eb, depth + 1);
294 9550 ▶ if (!sub) { c->err = HAMT_ERR_OOM; goto fail; }
Branch: 1 branch
BranchTrueFalseTotal
if (!sub) { c->err = HAMT_ERR_OOM; goto fail; } 0 9550 9550
295 9550 same_a = same_b = 0;
296 9550 c->added++;
297 9550 rc[nc++] = sub;
298 9550 nodemap |= bit;
299 }
300 }
301 144715 ▶ else if (ea) { /* an entry meets a subtree */
Branch: 1 branch
BranchTrueFalseTotal
else if (ea) { /* an entry meets a subtree */ 6713 138002 144715
302 int found;
303 6713 hamt_node *sub = hamt_merge_put(c, cb, depth + 1, ea, 1, &found);
304 6713 ▶ if (!sub) goto fail;
Branch: 1 branch
BranchTrueFalseTotal
if (!sub) goto fail; 0 6713 6713
305 6713 same_a = 0;
306 6713 ▶ if (sub != cb) same_b = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (sub != cb) same_b = 0; 3393 3320 6713
307 6713 ▶ c->added += hamt_node_count(cb) - (found ? 1 : 0);
Branch: 1 branch
BranchTrueFalseTotal
c->added += hamt_node_count(cb) - (found ? 1 : 0); 3470 3243 6713
308 6713 rc[nc++] = sub;
309 6713 nodemap |= bit;
310 }
311 138002 ▶ else if (eb) { /* a subtree meets an entry */
Branch: 1 branch
BranchTrueFalseTotal
else if (eb) { /* a subtree meets an entry */ 7170 130832 138002
312 int found;
313 7170 hamt_node *sub = hamt_merge_put(c, ca, depth + 1, eb, 0, &found);
314 7170 ▶ if (!sub) goto fail;
Branch: 1 branch
BranchTrueFalseTotal
if (!sub) goto fail; 3 7167 7170
315 7167 ▶ if (sub != ca) same_a = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (sub != ca) same_a = 0; 3885 3282 7167
316 7167 same_b = 0;
317 7167 ▶ if (!found) c->added++;
Branch: 1 branch
BranchTrueFalseTotal
if (!found) c->added++; 3586 3581 7167
318 7167 rc[nc++] = sub;
319 7167 nodemap |= bit;
320 }
321 else { /* two subtrees */
322 130832 hamt_node *sub = hamt_node_merge(c, ca, cb, depth + 1);
323 130832 ▶ if (!sub) goto fail;
Branch: 1 branch
BranchTrueFalseTotal
if (!sub) goto fail; 4 130828 130832
324 130828 ▶ if (sub != ca) same_a = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (sub != ca) same_a = 0; 112757 18071 130828
325 130828 ▶ if (sub != cb) same_b = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (sub != cb) same_b = 0; 119114 11714 130828
326 130828 rc[nc++] = sub;
327 130828 nodemap |= bit;
328 }
329 }
330  
331 115111 ▶ if (same_a || same_b) {
Branch: 2 branches
BranchTrueFalseTotal
if (same_a || same_b) { 106730 8381 115111
if (same_a || same_b) { 2573 104157 106730
332 20496 ▶ for (i = 0; i < nd; i++) hamt_entry_release(c->cx, (hamt_entry *)rd[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nd; i++) hamt_entry_release(c->cx, (hamt_entry *)rd[i]); 9542 10954 20496
333 27507 ▶ for (i = 0; i < nc; i++) hamt_node_release(c->cx, (hamt_node *)rc[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nc; i++) hamt_node_release(c->cx, (hamt_node *)rc[i]); 16553 10954 27507
334 10954 ▶ return hamt_node_retain(same_a ? a : b);
Branch: 1 branch
BranchTrueFalseTotal
return hamt_node_retain(same_a ? a : b); 8381 2573 10954
335 }
336  
337 104157 N = nd + nc;
338 104157 r = hamt_node_new(c->cx, N);
339 104157 ▶ if (!r) { c->err = HAMT_ERR_OOM; goto fail; }
Branch: 1 branch
BranchTrueFalseTotal
if (!r) { c->err = HAMT_ERR_OOM; goto fail; } 0 104157 104157
340 104157 r->datamap = datamap;
341 104157 r->nodemap = nodemap;
342 252823 ▶ for (i = 0; i < nd; i++) r->slot[i] = rd[i];
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nd; i++) r->slot[i] = rd[i]; 148666 104157 252823
343 256680 ▶ for (i = 0; i < nc; i++) r->slot[N - 1 - i] = rc[i]; /* lowest position last */
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nc; i++) r->slot[N - 1 - i] = rc[i]; /* lowest position last */ 152523 104157 256680
344 104157 return r;
345  
346 25 fail:
347 80 ▶ for (i = 0; i < nd; i++) hamt_entry_release(c->cx, (hamt_entry *)rd[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nd; i++) hamt_entry_release(c->cx, (hamt_entry *)rd[i]); 55 25 80
348 90 ▶ for (i = 0; i < nc; i++) hamt_node_release(c->cx, (hamt_node *)rc[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nc; i++) hamt_node_release(c->cx, (hamt_node *)rc[i]); 65 25 90
349 25 return NULL;
350 }
351  
352 /* The root of a trie holding every key of both. Where a key is in both, the
353 * resolver chooses, or the second map's entry wins when there is none.
354 *
355 * One reference, owned by the caller. c->added is how many keys the second
356 * map brought that the first did not have, so the result's count is the
357 * first map's plus that. The result IS `a` when `b` added and changed
358 * nothing, and IS `b` when the result is exactly `b`.
359 *
360 * NULL with c->err set means it stopped: nothing is leaked and neither
361 * input is touched. NULL with c->err clear means both were empty. */
362 1751 static hamt_node *hamt_map_merge(hamt_merge_ctx *c, hamt_node *a, hamt_node *b) {
363 1751 c->added = 0;
364 1751 c->visits = 0;
365 1751 c->err = HAMT_OK;
366 1751 ▶ if (!b) return a ? hamt_node_retain(a) : NULL;
Branch: 2 branches
BranchTrueFalseTotal
if (!b) return a ? hamt_node_retain(a) : NULL; 3 1748 1751
if (!b) return a ? hamt_node_retain(a) : NULL; 2 1 3
367 1748 ▶ if (!a) { c->added = hamt_node_count(b); return hamt_node_retain(b); }
Branch: 1 branch
BranchTrueFalseTotal
if (!a) { c->added = hamt_node_count(b); return hamt_node_retain(b); } 5 1743 1748
368 1743 return hamt_node_merge(c, a, b, 0);
369 }
370  
371 /* ---- difference -------------------------------------------------------- */
372  
373 #define HAMT_DIFF_ADD 1 /* in the second map only: ea is NULL */
374 #define HAMT_DIFF_REMOVE 2 /* in the first map only: eb is NULL */
375 #define HAMT_DIFF_CHANGE 3 /* in both, with values that are not equal */
376  
377 /* 0 to carry on, anything else to stop. */
378 typedef int (*hamt_diff_fn)(void *ud, void *cx, int kind, hamt_entry *ea,
379 hamt_entry *eb);
380  
381 typedef struct hamt_diff_ctx {
382 void *cx;
383 hamt_diff_fn fn;
384 void *ud;
385 hamt_eq_ctx eq; /* how two values under one key are compared */
386 size_t visits; /* node pairs looked at */
387 size_t reported;
388 } hamt_diff_ctx;
389  
390 16630 static int hamt_diff_report(hamt_diff_ctx *c, int kind, hamt_entry *ea,
391 hamt_entry *eb) {
392 16630 c->reported++;
393 16630 ▶ return c->fn ? c->fn(c->ud, c->cx, kind, ea, eb) : 0;
Branch: 1 branch
BranchTrueFalseTotal
return c->fn ? c->fn(c->ud, c->cx, kind, ea, eb) : 0; 16595 35 16630
394 }
395  
396 /* The same key on both sides: a change, or nothing. */
397 15693 static int hamt_diff_same_key(hamt_diff_ctx *c, hamt_entry *ea, hamt_entry *eb) {
398 int rc;
399 15693 ▶ if (ea == eb) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (ea == eb) return 0; 1757 13936 15693
400 13936 rc = hamt_val_same(&c->eq, ea->val, eb->val);
401 13936 ▶ if (rc < 0) return HAMT_ERR_ABORT;
Branch: 1 branch
BranchTrueFalseTotal
if (rc < 0) return HAMT_ERR_ABORT; 0 13936 13936
402 13936 ▶ return rc ? 0 : hamt_diff_report(c, HAMT_DIFF_CHANGE, ea, eb);
Branch: 1 branch
BranchTrueFalseTotal
return rc ? 0 : hamt_diff_report(c, HAMT_DIFF_CHANGE, ea, eb); 10734 3202 13936
403 }
404  
405 /* Everything under a subtree is on one side only. */
406 297 static int hamt_diff_all(hamt_diff_ctx *c, const hamt_node *n, int kind) {
407 hamt_iter it;
408 hamt_entry *e;
409 int rc;
410 297 hamt_iter_init(&it, n);
411 1008 ▶ while ((e = hamt_iter_next(&it))) {
Branch: 1 branch
BranchTrueFalseTotal
while ((e = hamt_iter_next(&it))) { 712 296 1008
412 534 rc = kind == HAMT_DIFF_ADD ? hamt_diff_report(c, kind, NULL, e)
413 712 ▶ : hamt_diff_report(c, kind, e, NULL);
Branch: 1 branch
BranchTrueFalseTotal
: hamt_diff_report(c, kind, e, NULL); 534 178 712
414 712 ▶ if (rc) return rc;
Branch: 1 branch
BranchTrueFalseTotal
if (rc) return rc; 1 711 712
415 }
416 296 return 0;
417 }
418  
419 /* One entry against a subtree of the other map. `kind` is what the
420 * subtree's other entries are: ADD when the subtree is the second map's. */
421 733 static int hamt_diff_entry_vs_node(hamt_diff_ctx *c, hamt_entry *e,
422 const hamt_node *n, int kind) {
423 hamt_iter it;
424 hamt_entry *x;
425 733 int rc, found = 0;
426  
427 733 hamt_iter_init(&it, n);
428 2588 ▶ while ((x = hamt_iter_next(&it))) {
Branch: 1 branch
BranchTrueFalseTotal
while ((x = hamt_iter_next(&it))) { 1855 733 2588
429 1855 ▶ if (hamt_entry_key_eq(x, e->key, e->klen, e->utf8, e->hash)) {
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_entry_key_eq(x, e->key, e->klen, e->utf8, e->hash)) { 701 1154 1855
430 701 found = 1;
431 701 rc = kind == HAMT_DIFF_ADD ? hamt_diff_same_key(c, e, x)
432 701 ▶ : hamt_diff_same_key(c, x, e);
Branch: 1 branch
BranchTrueFalseTotal
: hamt_diff_same_key(c, x, e); 518 183 701
433 }
434 else {
435 1154 rc = kind == HAMT_DIFF_ADD ? hamt_diff_report(c, kind, NULL, x)
436 1154 ▶ : hamt_diff_report(c, kind, x, NULL);
Branch: 1 branch
BranchTrueFalseTotal
: hamt_diff_report(c, kind, x, NULL); 889 265 1154
437 }
438 1855 ▶ if (rc) return rc;
Branch: 1 branch
BranchTrueFalseTotal
if (rc) return rc; 0 1855 1855
439 }
440 733 ▶ if (found) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (found) return 0; 701 32 733
441 16 return kind == HAMT_DIFF_ADD ? hamt_diff_report(c, HAMT_DIFF_REMOVE, e, NULL)
442 48 ▶ : hamt_diff_report(c, HAMT_DIFF_ADD, NULL, e);
Branch: 1 branch
BranchTrueFalseTotal
: hamt_diff_report(c, HAMT_DIFF_ADD, NULL, e); 16 16 32
443 }
444  
445 7599 static int hamt_node_diff(hamt_diff_ctx *c, const hamt_node *a, const hamt_node *b) {
446 uint32_t pos, i, j, na_slots, nb_slots;
447 int rc;
448  
449 7599 ▶ if (a == b) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (a == b) return 0; 698 6901 7599
450 6901 c->visits++;
451  
452 6901 ▶ if (a->ncoll) {
Branch: 1 branch
BranchTrueFalseTotal
if (a->ncoll) { 310 6591 6901
453 2962 ▶ for (i = 0; i < a->ncoll; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < a->ncoll; i++) { 2652 310 2962
454 2652 hamt_entry *ea = (hamt_entry *)a->slot[i], *eb = NULL;
455 54520 ▶ for (j = 0; j < b->ncoll; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < b->ncoll; j++) { 53741 779 54520
456 53741 eb = (hamt_entry *)b->slot[j];
457 53741 ▶ if (hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) break; 1873 51868 53741
458 }
459 779 rc = j == b->ncoll ? hamt_diff_report(c, HAMT_DIFF_REMOVE, ea, NULL)
460 2652 ▶ : hamt_diff_same_key(c, ea, eb);
Branch: 1 branch
BranchTrueFalseTotal
: hamt_diff_same_key(c, ea, eb); 779 1873 2652
461 2652 ▶ if (rc) return rc;
Branch: 1 branch
BranchTrueFalseTotal
if (rc) return rc; 0 2652 2652
462 }
463 2962 ▶ for (j = 0; j < b->ncoll; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < b->ncoll; j++) { 2652 310 2962
464 2652 hamt_entry *eb = (hamt_entry *)b->slot[j];
465 54520 ▶ for (i = 0; i < a->ncoll; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < a->ncoll; i++) { 53741 779 54520
466 53741 hamt_entry *ea = (hamt_entry *)a->slot[i];
467 53741 ▶ if (hamt_entry_key_eq(ea, eb->key, eb->klen, eb->utf8, eb->hash)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_entry_key_eq(ea, eb->key, eb->klen, eb->utf8, eb->hash)) break; 1873 51868 53741
468 }
469 2652 ▶ if (i < a->ncoll) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (i < a->ncoll) continue; 1873 779 2652
470 779 rc = hamt_diff_report(c, HAMT_DIFF_ADD, NULL, eb);
471 779 ▶ if (rc) return rc;
Branch: 1 branch
BranchTrueFalseTotal
if (rc) return rc; 0 779 779
472 }
473 310 return 0;
474 }
475  
476 6591 na_slots = hamt_node_nslots(a);
477 6591 nb_slots = hamt_node_nslots(b);
478  
479 217294 ▶ for (pos = 0; pos < 32; pos++) {
Branch: 1 branch
BranchTrueFalseTotal
for (pos = 0; pos < 32; pos++) { 210712 6582 217294
480 210712 uint32_t bit = (uint32_t)1 << pos;
481 210712 hamt_entry *ea = NULL, *eb = NULL;
482 210712 const hamt_node *ca = NULL, *cb = NULL;
483  
484 210712 ▶ if (a->datamap & bit)
Branch: 1 branch
BranchTrueFalseTotal
if (a->datamap & bit) 14352 196360 210712
485 14352 ea = (hamt_entry *)a->slot[hamt_popcnt32(a->datamap & (bit - 1))];
486 196360 ▶ else if (a->nodemap & bit)
Branch: 1 branch
BranchTrueFalseTotal
else if (a->nodemap & bit) 7843 188517 196360
487 7843 ca = (const hamt_node *)a->slot[na_slots - 1 - hamt_popcnt32(a->nodemap & (bit - 1))];
488 210712 ▶ if (b->datamap & bit)
Branch: 1 branch
BranchTrueFalseTotal
if (b->datamap & bit) 15059 195653 210712
489 15059 eb = (hamt_entry *)b->slot[hamt_popcnt32(b->datamap & (bit - 1))];
490 195653 ▶ else if (b->nodemap & bit)
Branch: 1 branch
BranchTrueFalseTotal
else if (b->nodemap & bit) 8302 187351 195653
491 8302 cb = (const hamt_node *)b->slot[nb_slots - 1 - hamt_popcnt32(b->nodemap & (bit - 1))];
492  
493 210712 ▶ if (!ea && !ca && !eb && !cb) continue;
Branch: 4 branches
BranchTrueFalseTotal
if (!ea && !ca && !eb && !cb) continue; 196360 14352 210712
if (!ea && !ca && !eb && !cb) continue; 188517 7843 196360
if (!ea && !ca && !eb && !cb) continue; 186900 1617 188517
if (!ea && !ca && !eb && !cb) continue; 186691 209 186900
494  
495 24021 ▶ if (!eb && !cb)
Branch: 2 branches
BranchTrueFalseTotal
if (!eb && !cb) 8962 15059 24021
if (!eb && !cb) 660 8302 8962
496 660 rc = ea ? hamt_diff_report(c, HAMT_DIFF_REMOVE, ea, NULL)
497 660 ▶ : hamt_diff_all(c, ca, HAMT_DIFF_REMOVE);
Branch: 1 branch
BranchTrueFalseTotal
: hamt_diff_all(c, ca, HAMT_DIFF_REMOVE); 575 85 660
498 23361 ▶ else if (!ea && !ca)
Branch: 2 branches
BranchTrueFalseTotal
else if (!ea && !ca) 9584 13777 23361
else if (!ea && !ca) 1826 7758 9584
499 1826 rc = eb ? hamt_diff_report(c, HAMT_DIFF_ADD, NULL, eb)
500 1826 ▶ : hamt_diff_all(c, cb, HAMT_DIFF_ADD);
Branch: 1 branch
BranchTrueFalseTotal
: hamt_diff_all(c, cb, HAMT_DIFF_ADD); 1617 209 1826
501 21535 ▶ else if (ea && eb) {
Branch: 2 branches
BranchTrueFalseTotal
else if (ea && eb) { 13777 7758 21535
else if (ea && eb) { 13243 534 13777
502 26486 ▶ if (hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash))
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) 13119 124 13243
503 13119 rc = hamt_diff_same_key(c, ea, eb);
504 else {
505 124 rc = hamt_diff_report(c, HAMT_DIFF_REMOVE, ea, NULL);
506 124 ▶ if (!rc) rc = hamt_diff_report(c, HAMT_DIFF_ADD, NULL, eb);
Branch: 1 branch
BranchTrueFalseTotal
if (!rc) rc = hamt_diff_report(c, HAMT_DIFF_ADD, NULL, eb); 124 0 124
507 }
508 }
509 8292 ▶ else if (ea) rc = hamt_diff_entry_vs_node(c, ea, cb, HAMT_DIFF_ADD);
Branch: 1 branch
BranchTrueFalseTotal
else if (ea) rc = hamt_diff_entry_vs_node(c, ea, cb, HAMT_DIFF_ADD); 534 7758 8292
510 7758 ▶ else if (eb) rc = hamt_diff_entry_vs_node(c, eb, ca, HAMT_DIFF_REMOVE);
Branch: 1 branch
BranchTrueFalseTotal
else if (eb) rc = hamt_diff_entry_vs_node(c, eb, ca, HAMT_DIFF_REMOVE); 199 7559 7758
511 7559 else rc = hamt_node_diff(c, ca, cb);
512  
513 24021 ▶ if (rc) return rc;
Branch: 1 branch
BranchTrueFalseTotal
if (rc) return rc; 9 24012 24021
514 }
515 6582 return 0;
516 }
517  
518 /* Reports every key that is in one map and not the other, or in both with
519 * values that are not equal, once each and in no promised order. Allocates
520 * nothing. 0, or whatever stopped it. */
521 53 static int hamt_map_diff(hamt_diff_ctx *c, const hamt_node *a, const hamt_node *b) {
522 53 c->visits = 0;
523 53 c->reported = 0;
524 53 c->eq.visits = 0;
525 53 ▶ if (a == b) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (a == b) return 0; 10 43 53
526 43 ▶ if (!a) return hamt_diff_all(c, b, HAMT_DIFF_ADD);
Branch: 1 branch
BranchTrueFalseTotal
if (!a) return hamt_diff_all(c, b, HAMT_DIFF_ADD); 1 42 43
527 42 ▶ if (!b) return hamt_diff_all(c, a, HAMT_DIFF_REMOVE);
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return hamt_diff_all(c, a, HAMT_DIFF_REMOVE); 2 40 42
528 40 return hamt_node_diff(c, a, b);
529 }
530  
531 /* ---- intersection and difference --------------------------------------
532 *
533 * Both keep some of the FIRST trie's entries and none of the second's: the
534 * intersection keeps those whose key the second trie has, the difference
535 * those whose key it has not. Values play no part, so these serve a set,
536 * whose entries have none, and would serve a map's keys as well.
537 *
538 * Unlike a union, these REMOVE, so a subtree can come back smaller than a
539 * subtree is allowed to be. The canonical shape is restored on the way up,
540 * exactly as delete does it: what comes back from a position is a part -
541 * nothing, or a lone entry for the parent to hold in place of the child, or
542 * a node.
543 *
544 * COUNTING. The result's size has to be known without walking the result,
545 * or the speed of skipping shared subtrees is spent counting them. Two
546 * tallies are kept - entries kept and entries removed - and either gives
547 * the size, as `kept` or as the first trie's count less `removed`. Each is
548 * exact only if one kind of skipped subtree is walked after all: `kept`
549 * needs the subtrees that are kept whole, `removed` the ones removed whole.
550 * `count_shared` picks: when the second trie is small next to the first,
551 * the subtrees the two have in common are small, and those are the ones
552 * walked; otherwise the ones only the first has. The caller sets it from
553 * the two counts, and reads back whichever tally that makes exact. */
554  
555 #define HAMT_PART_NONE 0
556 #define HAMT_PART_ENTRY 1
557 #define HAMT_PART_NODE 2
558  
559 typedef struct hamt_part {
560 int kind;
561 void *p; /* one reference, the receiver's */
562 } hamt_part;
563  
564 typedef struct hamt_set_ctx {
565 void *cx;
566 int count_shared; /* walk the subtrees common to both, not the first's own */
567 size_t kept;
568 size_t removed;
569 size_t visits; /* node pairs looked at */
570 size_t walked; /* entries counted by walking a subtree */
571 int err;
572 } hamt_set_ctx;
573  
574 /* The size of a subtree that is being kept or removed whole, found by
575 * walking it. The tally of what this costs is what the tests hold to
576 * account: it must stay small whenever one of the two results is. */
577 15731 static size_t hamt_set_walk(hamt_set_ctx *c, const hamt_node *n) {
578 15731 size_t k = hamt_node_count(n);
579 15731 c->walked += k;
580 15731 return k;
581 }
582  
583 247116 static hamt_part hamt_part_make(int kind, void *p) {
584 hamt_part r;
585 247116 r.kind = kind;
586 247116 r.p = p;
587 247116 return r;
588 }
589  
590 /* What a position's gathered entries and children amount to. Every pointer
591 * in rd[] and rc[] is one the caller owns a reference to; all of them are
592 * used or released here. `same` means they are exactly what `a` holds, in
593 * which case `a` itself is the answer. */
594 220188 static hamt_part hamt_part_build(hamt_set_ctx *c, hamt_node *a, unsigned depth,
595 int same, uint32_t datamap, uint32_t nodemap,
596 void **rd, uint32_t nd, void **rc, uint32_t nc) {
597 220188 uint32_t i, N = nd + nc;
598 hamt_node *r;
599  
600 220188 ▶ if (same || N == 0 || c->err) {
Branch: 3 branches
BranchTrueFalseTotal
if (same || N == 0 || c->err) { 158920 61268 220188
if (same || N == 0 || c->err) { 96939 61981 158920
if (same || N == 0 || c->err) { 0 96939 96939
601 169507 ▶ for (i = 0; i < nd; i++) hamt_entry_release(c->cx, (hamt_entry *)rd[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nd; i++) hamt_entry_release(c->cx, (hamt_entry *)rd[i]); 46258 123249 169507
602 194719 ▶ for (i = 0; i < nc; i++) hamt_node_release(c->cx, (hamt_node *)rc[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nc; i++) hamt_node_release(c->cx, (hamt_node *)rc[i]); 71470 123249 194719
603 123249 ▶ if (c->err || N == 0) return hamt_part_make(HAMT_PART_NONE, NULL);
Branch: 2 branches
BranchTrueFalseTotal
if (c->err || N == 0) return hamt_part_make(HAMT_PART_NONE, NULL); 123249 0 123249
if (c->err || N == 0) return hamt_part_make(HAMT_PART_NONE, NULL); 61981 61268 123249
604 61268 return hamt_part_make(HAMT_PART_NODE, hamt_node_retain(a));
605 }
606 /* One entry and nothing else, below the root: the parent holds it. */
607 96939 ▶ if (nc == 0 && nd == 1 && depth > 0)
Branch: 3 branches
BranchTrueFalseTotal
if (nc == 0 && nd == 1 && depth > 0) 38786 58153 96939
if (nc == 0 && nd == 1 && depth > 0) 26090 12696 38786
if (nc == 0 && nd == 1 && depth > 0) 25937 153 26090
608 25937 return hamt_part_make(HAMT_PART_ENTRY, rd[0]);
609  
610 71002 r = hamt_node_new(c->cx, N);
611 71002 ▶ if (!r) {
Branch: 1 branch
BranchTrueFalseTotal
if (!r) { 0 71002 71002
612 0 c->err = HAMT_ERR_OOM;
613 0 ▶ for (i = 0; i < nd; i++) hamt_entry_release(c->cx, (hamt_entry *)rd[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nd; i++) hamt_entry_release(c->cx, (hamt_entry *)rd[i]); 0 0 0
614 0 ▶ for (i = 0; i < nc; i++) hamt_node_release(c->cx, (hamt_node *)rc[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nc; i++) hamt_node_release(c->cx, (hamt_node *)rc[i]); 0 0 0
615 0 return hamt_part_make(HAMT_PART_NONE, NULL);
616 }
617 71002 r->datamap = datamap;
618 71002 r->nodemap = nodemap;
619 129421 ▶ for (i = 0; i < nd; i++) r->slot[i] = rd[i];
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nd; i++) r->slot[i] = rd[i]; 58419 71002 129421
620 158125 ▶ for (i = 0; i < nc; i++) r->slot[N - 1 - i] = rc[i];
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nc; i++) r->slot[N - 1 - i] = rc[i]; 87123 71002 158125
621 71002 return hamt_part_make(HAMT_PART_NODE, r);
622 }
623  
624 /* Two collision nodes: the first's entries that the second has (`keep_common`)
625 * or has not. */
626 15742 static hamt_part hamt_coll_filter(hamt_set_ctx *c, hamt_node *a, hamt_node *b,
627 int keep_common) {
628 15742 size_t bytes = (size_t)a->ncoll * sizeof(void *);
629 15742 hamt_entry **list = (hamt_entry **)HAMT_ALLOC(c->cx, bytes);
630 15742 uint32_t n = 0, i, j;
631 15742 hamt_part out = hamt_part_make(HAMT_PART_NONE, NULL);
632  
633 15742 ▶ if (!list) { c->err = HAMT_ERR_OOM; return out; }
Branch: 1 branch
BranchTrueFalseTotal
if (!list) { c->err = HAMT_ERR_OOM; return out; } 0 15742 15742
634 104286 ▶ for (i = 0; i < a->ncoll; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < a->ncoll; i++) { 88544 15742 104286
635 88544 hamt_entry *ea = (hamt_entry *)a->slot[i];
636 565614 ▶ for (j = 0; j < b->ncoll; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < b->ncoll; j++) { 500410 65204 565614
637 500410 hamt_entry *eb = (hamt_entry *)b->slot[j];
638 500410 ▶ if (hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) break; 23340 477070 500410
639 }
640 88544 ▶ if ((j < b->ncoll) == (keep_common != 0)) { list[n++] = ea; c->kept++; }
Branch: 1 branch
BranchTrueFalseTotal
if ((j < b->ncoll) == (keep_common != 0)) { list[n++] = ea; c->kept++; } 44272 44272 88544
641 44272 else c->removed++;
642 }
643  
644 15742 ▶ if (n == a->ncoll) out = hamt_part_make(HAMT_PART_NODE, hamt_node_retain(a));
Branch: 1 branch
BranchTrueFalseTotal
if (n == a->ncoll) out = hamt_part_make(HAMT_PART_NODE, hamt_node_retain(a)); 4556 11186 15742
645 11186 ▶ else if (n == 1) out = hamt_part_make(HAMT_PART_ENTRY, hamt_entry_retain(list[0]));
Branch: 1 branch
BranchTrueFalseTotal
else if (n == 1) out = hamt_part_make(HAMT_PART_ENTRY, hamt_entry_retain(list[0])); 1686 9500 11186
646 9500 ▶ else if (n > 1) {
Branch: 1 branch
BranchTrueFalseTotal
else if (n > 1) { 4944 4556 9500
647 4944 hamt_node *r = hamt_node_new(c->cx, n);
648 4944 ▶ if (!r) c->err = HAMT_ERR_OOM;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) c->err = HAMT_ERR_OOM; 0 4944 4944
649 else {
650 4944 r->ncoll = n;
651 4944 memcpy(r->slot, list, (size_t)n * sizeof(void *));
652 4944 hamt_node_adopt(r, HAMT_NO_SKIP);
653 4944 out = hamt_part_make(HAMT_PART_NODE, r);
654 }
655 }
656 15742 HAMT_FREE(c->cx, list, bytes);
657 15742 return out;
658 }
659  
660 /* Where the gathering loop puts a part that came back from below. */
661 #define HAMT_PART_PLACE(part, child, bit) \
662 do { \
663 if ((part).kind == HAMT_PART_NODE) { \
664 if ((part).p != (void *)(child)) same = 0; \
665 rc[nc++] = (part).p; nodemap |= (bit); \
666 } \
667 else { \
668 same = 0; \
669 if ((part).kind == HAMT_PART_ENTRY) { \
670 rd[nd++] = (part).p; datamap |= (bit); \
671 } \
672 } \
673 } while (0)
674  
675 120320 static hamt_part hamt_node_intersect(hamt_set_ctx *c, hamt_node *a, hamt_node *b,
676 unsigned depth) {
677 void *rd[32], *rc[32];
678 120320 uint32_t datamap = 0, nodemap = 0, nd = 0, nc = 0, pos, na_slots, nb_slots;
679 120320 int same = 1;
680  
681 120320 c->visits++;
682 120320 ▶ if (a->ncoll) return hamt_coll_filter(c, a, b, 1);
Branch: 1 branch
BranchTrueFalseTotal
if (a->ncoll) return hamt_coll_filter(c, a, b, 1); 7871 112449 120320
683  
684 112449 na_slots = hamt_node_nslots(a);
685 112449 nb_slots = hamt_node_nslots(b);
686  
687 3710817 ▶ for (pos = 0; pos < 32 && !c->err; pos++) {
Branch: 2 branches
BranchTrueFalseTotal
for (pos = 0; pos < 32 && !c->err; pos++) { 3598368 112449 3710817
for (pos = 0; pos < 32 && !c->err; pos++) { 3598368 0 3598368
688 3598368 uint32_t bit = (uint32_t)1 << pos;
689 3598368 hamt_entry *ea = NULL, *eb = NULL;
690 3598368 hamt_node *ca = NULL, *cb = NULL;
691  
692 3598368 ▶ if (a->datamap & bit)
Branch: 1 branch
BranchTrueFalseTotal
if (a->datamap & bit) 107643 3490725 3598368
693 107643 ea = (hamt_entry *)a->slot[hamt_popcnt32(a->datamap & (bit - 1))];
694 3490725 ▶ else if (a->nodemap & bit)
Branch: 1 branch
BranchTrueFalseTotal
else if (a->nodemap & bit) 141220 3349505 3490725
695 141220 ca = (hamt_node *)a->slot[na_slots - 1 - hamt_popcnt32(a->nodemap & (bit - 1))];
696 3349505 else continue; /* nothing here to keep */
697  
698 248863 ▶ if (b->datamap & bit)
Branch: 1 branch
BranchTrueFalseTotal
if (b->datamap & bit) 43905 204958 248863
699 43905 eb = (hamt_entry *)b->slot[hamt_popcnt32(b->datamap & (bit - 1))];
700 204958 ▶ else if (b->nodemap & bit)
Branch: 1 branch
BranchTrueFalseTotal
else if (b->nodemap & bit) 134175 70783 204958
701 134175 cb = (hamt_node *)b->slot[nb_slots - 1 - hamt_popcnt32(b->nodemap & (bit - 1))];
702  
703 248863 ▶ if (ea) {
Branch: 1 branch
BranchTrueFalseTotal
if (ea) { 107643 141220 248863
704 37260 int has = eb ? hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)
705 184480 ▶ : cb ? hamt_node_find(cb, depth + 1, ea->key, ea->klen, ea->utf8, ea->hash) != NULL
Branch: 1 branch
BranchTrueFalseTotal
: cb ? hamt_node_find(cb, depth + 1, ea->key, ea->klen, ea->utf8, ea->hash) != NULL 37260 70383 107643
706 76837 : 0;
707 107643 ▶ if (has) { rd[nd++] = hamt_entry_retain(ea); datamap |= bit; c->kept++; }
Branch: 1 branch
BranchTrueFalseTotal
if (has) { rd[nd++] = hamt_entry_retain(ea); datamap |= bit; c->kept++; } 31408 76235 107643
708 76235 else { same = 0; c->removed++; }
709 }
710 141220 ▶ else if (!eb && !cb) { /* a subtree with no partner */
Branch: 2 branches
BranchTrueFalseTotal
else if (!eb && !cb) { /* a subtree with no partner */ 134575 6645 141220
else if (!eb && !cb) { /* a subtree with no partner */ 6854 127721 134575
711 6854 same = 0;
712 6854 ▶ if (!c->count_shared) c->removed += hamt_set_walk(c, ca);
Branch: 1 branch
BranchTrueFalseTotal
if (!c->count_shared) c->removed += hamt_set_walk(c, ca); 4128 2726 6854
713 }
714 134366 ▶ else if (eb) { /* at most one of a subtree */
Branch: 1 branch
BranchTrueFalseTotal
else if (eb) { /* at most one of a subtree */ 6645 127721 134366
715 6645 hamt_entry *e = hamt_node_find(ca, depth + 1, eb->key, eb->klen, eb->utf8, eb->hash);
716 6645 same = 0;
717 6645 ▶ if (!c->count_shared) c->removed += hamt_set_walk(c, ca) - (e ? 1 : 0);
Branch: 2 branches
BranchTrueFalseTotal
if (!c->count_shared) c->removed += hamt_set_walk(c, ca) - (e ? 1 : 0); 4379 2266 6645
if (!c->count_shared) c->removed += hamt_set_walk(c, ca) - (e ? 1 : 0); 2462 1917 4379
718 6645 ▶ if (e) { rd[nd++] = hamt_entry_retain(e); datamap |= bit; c->kept++; }
Branch: 1 branch
BranchTrueFalseTotal
if (e) { rd[nd++] = hamt_entry_retain(e); datamap |= bit; c->kept++; } 3356 3289 6645
719 }
720 127721 ▶ else if (ca == cb) { /* the same subtree: all of it */
Branch: 1 branch
BranchTrueFalseTotal
else if (ca == cb) { /* the same subtree: all of it */ 8902 118819 127721
721 8902 rc[nc++] = hamt_node_retain(ca);
722 8902 nodemap |= bit;
723 8902 ▶ if (c->count_shared) c->kept += hamt_set_walk(c, ca);
Branch: 1 branch
BranchTrueFalseTotal
if (c->count_shared) c->kept += hamt_set_walk(c, ca); 0 8902 8902
724 }
725 else {
726 118819 hamt_part part = hamt_node_intersect(c, ca, cb, depth + 1);
727 118819 ▶ HAMT_PART_PLACE(part, ca, bit);
Branch: 3 branches
BranchTrueFalseTotal
HAMT_PART_PLACE(part, ca, bit); 45243 73576 118819
HAMT_PART_PLACE(part, ca, bit); 36249 8994 45243
HAMT_PART_PLACE(part, ca, bit); 16495 57081 73576
728 }
729 }
730 112449 return hamt_part_build(c, a, depth, same, datamap, nodemap, rd, nd, rc, nc);
731 }
732  
733 115610 static hamt_part hamt_node_subtract(hamt_set_ctx *c, hamt_node *a, hamt_node *b,
734 unsigned depth) {
735 void *rd[32], *rc[32];
736 115610 uint32_t datamap = 0, nodemap = 0, nd = 0, nc = 0, pos, na_slots, nb_slots;
737 115610 int same = 1;
738  
739 115610 c->visits++;
740 115610 ▶ if (a->ncoll) return hamt_coll_filter(c, a, b, 0);
Branch: 1 branch
BranchTrueFalseTotal
if (a->ncoll) return hamt_coll_filter(c, a, b, 0); 7871 107739 115610
741  
742 107739 na_slots = hamt_node_nslots(a);
743 107739 nb_slots = hamt_node_nslots(b);
744  
745 3555387 ▶ for (pos = 0; pos < 32 && !c->err; pos++) {
Branch: 2 branches
BranchTrueFalseTotal
for (pos = 0; pos < 32 && !c->err; pos++) { 3447648 107739 3555387
for (pos = 0; pos < 32 && !c->err; pos++) { 3447648 0 3447648
746 3447648 uint32_t bit = (uint32_t)1 << pos;
747 3447648 hamt_entry *ea = NULL, *eb = NULL;
748 3447648 hamt_node *ca = NULL, *cb = NULL;
749  
750 3447648 ▶ if (a->datamap & bit)
Branch: 1 branch
BranchTrueFalseTotal
if (a->datamap & bit) 92007 3355641 3447648
751 92007 ea = (hamt_entry *)a->slot[hamt_popcnt32(a->datamap & (bit - 1))];
752 3355641 ▶ else if (a->nodemap & bit)
Branch: 1 branch
BranchTrueFalseTotal
else if (a->nodemap & bit) 135310 3220331 3355641
753 135310 ca = (hamt_node *)a->slot[na_slots - 1 - hamt_popcnt32(a->nodemap & (bit - 1))];
754 3220331 else continue;
755  
756 227317 ▶ if (b->datamap & bit)
Branch: 1 branch
BranchTrueFalseTotal
if (b->datamap & bit) 37227 190090 227317
757 37227 eb = (hamt_entry *)b->slot[hamt_popcnt32(b->datamap & (bit - 1))];
758 190090 ▶ else if (b->nodemap & bit)
Branch: 1 branch
BranchTrueFalseTotal
else if (b->nodemap & bit) 128418 61672 190090
759 128418 cb = (hamt_node *)b->slot[nb_slots - 1 - hamt_popcnt32(b->nodemap & (bit - 1))];
760  
761 227317 ▶ if (ea) {
Branch: 1 branch
BranchTrueFalseTotal
if (ea) { 92007 135310 227317
762 31408 int has = eb ? hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)
763 157930 ▶ : cb ? hamt_node_find(cb, depth + 1, ea->key, ea->klen, ea->utf8, ea->hash) != NULL
Branch: 1 branch
BranchTrueFalseTotal
: cb ? hamt_node_find(cb, depth + 1, ea->key, ea->klen, ea->utf8, ea->hash) != NULL 31408 60599 92007
764 65923 : 0;
765 92007 ▶ if (has) { same = 0; c->removed++; }
Branch: 1 branch
BranchTrueFalseTotal
if (has) { same = 0; c->removed++; } 25834 66173 92007
766 66173 else { rd[nd++] = hamt_entry_retain(ea); datamap |= bit; c->kept++; }
767 }
768 135310 ▶ else if (!eb && !cb) { /* a subtree with no partner: kept whole */
Branch: 2 branches
BranchTrueFalseTotal
else if (!eb && !cb) { /* a subtree with no partner: kept whole */ 129491 5819 135310
else if (!eb && !cb) { /* a subtree with no partner: kept whole */ 6397 123094 129491
769 6397 rc[nc++] = hamt_node_retain(ca);
770 6397 nodemap |= bit;
771 6397 ▶ if (!c->count_shared) c->kept += hamt_set_walk(c, ca);
Branch: 1 branch
BranchTrueFalseTotal
if (!c->count_shared) c->kept += hamt_set_walk(c, ca); 3671 2726 6397
772 }
773 128913 ▶ else if (eb) { /* a subtree less at most one key */
Branch: 1 branch
BranchTrueFalseTotal
else if (eb) { /* a subtree less at most one key */ 5819 123094 128913
774 5819 hamt_entry *e = hamt_node_find(ca, depth + 1, eb->key, eb->klen, eb->utf8, eb->hash);
775 5819 ▶ if (!c->count_shared) c->kept += hamt_set_walk(c, ca) - (e ? 1 : 0);
Branch: 2 branches
BranchTrueFalseTotal
if (!c->count_shared) c->kept += hamt_set_walk(c, ca) - (e ? 1 : 0); 3553 2266 5819
if (!c->count_shared) c->kept += hamt_set_walk(c, ca) - (e ? 1 : 0); 2012 1541 3553
776 5819 ▶ if (!e) { rc[nc++] = hamt_node_retain(ca); nodemap |= bit; }
Branch: 1 branch
BranchTrueFalseTotal
if (!e) { rc[nc++] = hamt_node_retain(ca); nodemap |= bit; } 2913 2906 5819
777 else {
778 int status;
779 2906 hamt_node *sub = hamt_node_del(c->cx, ca, depth + 1, eb->key, eb->klen,
780 2906 eb->utf8, eb->hash, &status);
781 2906 same = 0;
782 2906 c->removed++;
783 2906 ▶ if (status == HAMT_DEL_OOM || !sub) { c->err = HAMT_ERR_OOM; break; }
Branch: 2 branches
BranchTrueFalseTotal
if (status == HAMT_DEL_OOM || !sub) { c->err = HAMT_ERR_OOM; break; } 2906 0 2906
if (status == HAMT_DEL_OOM || !sub) { c->err = HAMT_ERR_OOM; break; } 0 2906 2906
784 2906 ▶ if (hamt_node_is_single(sub)) { /* down to one: it moves up */
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_node_is_single(sub)) { /* down to one: it moves up */ 2054 852 2906
785 2054 rd[nd++] = hamt_entry_retain((hamt_entry *)sub->slot[0]);
786 2054 datamap |= bit;
787 2054 hamt_node_release(c->cx, sub);
788 }
789 852 else { rc[nc++] = sub; nodemap |= bit; }
790 }
791 }
792 123094 ▶ else if (ca == cb) { /* the same subtree: none of it */
Branch: 1 branch
BranchTrueFalseTotal
else if (ca == cb) { /* the same subtree: none of it */ 8980 114114 123094
793 8980 same = 0;
794 8980 ▶ if (c->count_shared) c->removed += hamt_set_walk(c, ca);
Branch: 1 branch
BranchTrueFalseTotal
if (c->count_shared) c->removed += hamt_set_walk(c, ca); 0 8980 8980
795 }
796 else {
797 114114 hamt_part part = hamt_node_subtract(c, ca, cb, depth + 1);
798 114114 ▶ HAMT_PART_PLACE(part, ca, bit);
Branch: 3 branches
BranchTrueFalseTotal
HAMT_PART_PLACE(part, ca, bit); 94286 19828 114114
HAMT_PART_PLACE(part, ca, bit); 38212 56074 94286
HAMT_PART_PLACE(part, ca, bit); 11128 8700 19828
799 }
800 }
801 107739 return hamt_part_build(c, a, depth, same, datamap, nodemap, rd, nd, rc, nc);
802 }
803  
804 3359 static void hamt_set_ctx_start(hamt_set_ctx *c, size_t ca, size_t cb) {
805 3359 c->count_shared = cb <= ca / 2;
806 3359 c->kept = 0;
807 3359 c->removed = 0;
808 3359 c->visits = 0;
809 3359 c->walked = 0;
810 3359 c->err = HAMT_OK;
811 3359 }
812  
813 /* The root of a trie holding the first trie's entries whose key the second
814 * also has. `ca` and `cb` are the two counts; `*count` is the result's.
815 * The result IS `a` when the second has every key of the first. NULL is an
816 * empty result, or a failure when c->err is set. */
817 1679 static hamt_node *hamt_set_intersect(hamt_set_ctx *c, hamt_node *a, hamt_node *b,
818 size_t ca, size_t cb, size_t *count) {
819 hamt_part part;
820  
821 1679 hamt_set_ctx_start(c, ca, cb);
822 1679 *count = 0;
823 1679 ▶ if (!a || !b) return NULL;
Branch: 2 branches
BranchTrueFalseTotal
if (!a || !b) return NULL; 1678 1 1679
if (!a || !b) return NULL; 1 1677 1678
824 1677 ▶ if (a == b) { *count = ca; return hamt_node_retain(a); }
Branch: 1 branch
BranchTrueFalseTotal
if (a == b) { *count = ca; return hamt_node_retain(a); } 176 1501 1677
825  
826 1501 part = hamt_node_intersect(c, a, b, 0);
827 1501 ▶ if (c->err || part.kind == HAMT_PART_NONE) return NULL;
Branch: 2 branches
BranchTrueFalseTotal
if (c->err || part.kind == HAMT_PART_NONE) return NULL; 1501 0 1501
if (c->err || part.kind == HAMT_PART_NONE) return NULL; 563 938 1501
828 938 ▶ *count = c->count_shared ? c->kept : ca - c->removed;
Branch: 1 branch
BranchTrueFalseTotal
*count = c->count_shared ? c->kept : ca - c->removed; 114 824 938
829 938 return (hamt_node *)part.p;
830 }
831  
832 /* The root of a trie holding the first trie's entries whose key the second
833 * has NOT. The result IS `a` when the two share no key. */
834 1680 static hamt_node *hamt_set_subtract(hamt_set_ctx *c, hamt_node *a, hamt_node *b,
835 size_t ca, size_t cb, size_t *count) {
836 hamt_part part;
837  
838 1680 hamt_set_ctx_start(c, ca, cb);
839 1680 *count = 0;
840 1680 ▶ if (!a || a == b) return NULL;
Branch: 2 branches
BranchTrueFalseTotal
if (!a || a == b) return NULL; 1680 0 1680
if (!a || a == b) return NULL; 183 1497 1680
841 1497 ▶ if (!b) { *count = ca; return hamt_node_retain(a); }
Branch: 1 branch
BranchTrueFalseTotal
if (!b) { *count = ca; return hamt_node_retain(a); } 1 1496 1497
842  
843 1496 part = hamt_node_subtract(c, a, b, 0);
844 1496 ▶ if (c->err || part.kind == HAMT_PART_NONE) return NULL;
Branch: 2 branches
BranchTrueFalseTotal
if (c->err || part.kind == HAMT_PART_NONE) return NULL; 1496 0 1496
if (c->err || part.kind == HAMT_PART_NONE) return NULL; 193 1303 1496
845 1303 ▶ *count = c->count_shared ? ca - c->removed : c->kept;
Branch: 1 branch
BranchTrueFalseTotal
*count = c->count_shared ? ca - c->removed : c->kept; 244 1059 1303
846 1303 return (hamt_node *)part.p;
847 }
848  
849 /* ---- two questions that need no result --------------------------------- */
850  
851 /* 1 when every key of `a` is a key of `b`. Stops at the first that is not,
852 * and allocates nothing. */
853 11696 static int hamt_node_subset(const hamt_node *a, const hamt_node *b, unsigned depth,
854 size_t *visits) {
855 uint32_t pos, i, j, na_slots, nb_slots;
856  
857 11696 ▶ if (a == b) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (a == b) return 1; 5492 6204 11696
858 6204 (*visits)++;
859  
860 6204 ▶ if (a->ncoll) {
Branch: 1 branch
BranchTrueFalseTotal
if (a->ncoll) { 270 5934 6204
861 1186 ▶ for (i = 0; i < a->ncoll; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < a->ncoll; i++) { 1071 115 1186
862 1071 const hamt_entry *ea = (const hamt_entry *)a->slot[i];
863 8907 ▶ for (j = 0; j < b->ncoll; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < b->ncoll; j++) 8752 155 8907
864 8752 ▶ if (hamt_entry_key_eq((const hamt_entry *)b->slot[j],
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_entry_key_eq((const hamt_entry *)b->slot[j], 916 7836 8752
865 9668 ea->key, ea->klen, ea->utf8, ea->hash)) break;
866 1071 ▶ if (j == b->ncoll) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (j == b->ncoll) return 0; 155 916 1071
867 }
868 115 return 1;
869 }
870  
871 /* Anything of `a` at a position where `b` has nothing settles it. */
872 5934 ▶ if ((a->datamap | a->nodemap) & ~(b->datamap | b->nodemap)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if ((a->datamap | a->nodemap) & ~(b->datamap | b->nodemap)) return 0; 296 5638 5934
873 /* A subtree holds two keys at least, and cannot fit in one entry. */
874 5638 ▶ if (a->nodemap & b->datamap) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (a->nodemap & b->datamap) return 0; 103 5535 5638
875  
876 5535 na_slots = hamt_node_nslots(a);
877 5535 nb_slots = hamt_node_nslots(b);
878 115027 ▶ for (pos = 0; pos < 32; pos++) {
Branch: 1 branch
BranchTrueFalseTotal
for (pos = 0; pos < 32; pos++) { 111648 3379 115027
879 111648 uint32_t bit = (uint32_t)1 << pos;
880 111648 ▶ if (a->datamap & bit) {
Branch: 1 branch
BranchTrueFalseTotal
if (a->datamap & bit) { 7170 104478 111648
881 7170 const hamt_entry *ea = (const hamt_entry *)
882 7170 a->slot[hamt_popcnt32(a->datamap & (bit - 1))];
883 7170 ▶ if (b->datamap & bit) {
Branch: 1 branch
BranchTrueFalseTotal
if (b->datamap & bit) { 5987 1183 7170
884 5987 const hamt_entry *eb = (const hamt_entry *)
885 5987 b->slot[hamt_popcnt32(b->datamap & (bit - 1))];
886 5987 ▶ if (!hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) return 0; 9 5978 5987
887 }
888 else {
889 1183 const hamt_node *cb = (const hamt_node *)
890 1183 b->slot[nb_slots - 1 - hamt_popcnt32(b->nodemap & (bit - 1))];
891 1183 ▶ if (!hamt_node_find(cb, depth + 1, ea->key, ea->klen, ea->utf8, ea->hash)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!hamt_node_find(cb, depth + 1, ea->key, ea->klen, ea->utf8, ea->hash)) return 0; 56 1127 1183
892 }
893 }
894 104478 ▶ else if (a->nodemap & bit) {
Branch: 1 branch
BranchTrueFalseTotal
else if (a->nodemap & bit) { 10699 93779 104478
895 10699 const hamt_node *ca = (const hamt_node *)
896 10699 a->slot[na_slots - 1 - hamt_popcnt32(a->nodemap & (bit - 1))];
897 10699 const hamt_node *cb = (const hamt_node *)
898 10699 b->slot[nb_slots - 1 - hamt_popcnt32(b->nodemap & (bit - 1))];
899 10699 ▶ if (!hamt_node_subset(ca, cb, depth + 1, visits)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!hamt_node_subset(ca, cb, depth + 1, visits)) return 0; 2091 8608 10699
900 }
901 }
902 3379 return 1;
903 }
904  
905 1673 static int hamt_set_subset(const hamt_node *a, const hamt_node *b, size_t ca,
906 size_t cb, size_t *visits) {
907 1673 *visits = 0;
908 1673 ▶ if (!a) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (!a) return 1; 2 1671 1673
909 1671 ▶ if (!b || ca > cb) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!b || ca > cb) return 0; 1670 1 1671
if (!b || ca > cb) return 0; 673 997 1670
910 997 return hamt_node_subset(a, b, 0, visits);
911 }
912  
913 /* 1 when the two have no key in common. Stops at the first they share. */
914 55681 static int hamt_node_disjoint(const hamt_node *a, const hamt_node *b, unsigned depth,
915 size_t *visits) {
916 uint32_t common, pos, i, j, na_slots, nb_slots;
917  
918 55681 ▶ if (a == b) return 0; /* a node is never empty */
Branch: 1 branch
BranchTrueFalseTotal
if (a == b) return 0; /* a node is never empty */ 465 55216 55681
919 55216 (*visits)++;
920  
921 55216 ▶ if (a->ncoll) {
Branch: 1 branch
BranchTrueFalseTotal
if (a->ncoll) { 3757 51459 55216
922 23759 ▶ for (i = 0; i < a->ncoll; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < a->ncoll; i++) { 20224 3535 23759
923 20224 const hamt_entry *ea = (const hamt_entry *)a->slot[i];
924 144749 ▶ for (j = 0; j < b->ncoll; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < b->ncoll; j++) 124747 20002 144749
925 124747 ▶ if (hamt_entry_key_eq((const hamt_entry *)b->slot[j],
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_entry_key_eq((const hamt_entry *)b->slot[j], 222 124525 124747
926 124969 ea->key, ea->klen, ea->utf8, ea->hash)) return 0;
927 }
928 3535 return 1;
929 }
930  
931 /* Only positions both use can hold a shared key. */
932 51459 common = (a->datamap | a->nodemap) & (b->datamap | b->nodemap);
933 51459 na_slots = hamt_node_nslots(a);
934 51459 nb_slots = hamt_node_nslots(b);
935 1584953 ▶ for (pos = 0; pos < 32; pos++) {
Branch: 1 branch
BranchTrueFalseTotal
for (pos = 0; pos < 32; pos++) { 1537134 47819 1584953
936 1537134 uint32_t bit = (uint32_t)1 << pos;
937 1537134 const hamt_entry *ea = NULL, *eb = NULL;
938 1537134 const hamt_node *ca = NULL, *cb = NULL;
939  
940 1537134 ▶ if (!(common & bit)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!(common & bit)) continue; 1472162 64972 1537134
941 64972 ▶ if (a->datamap & bit) ea = (const hamt_entry *)a->slot[hamt_popcnt32(a->datamap & (bit - 1))];
Branch: 1 branch
BranchTrueFalseTotal
if (a->datamap & bit) ea = (const hamt_entry *)a->slot[hamt_popcnt32(a->datamap & (bit - 1))]; 8720 56252 64972
942 56252 else ca = (const hamt_node *)a->slot[na_slots - 1 - hamt_popcnt32(a->nodemap & (bit - 1))];
943 64972 ▶ if (b->datamap & bit) eb = (const hamt_entry *)b->slot[hamt_popcnt32(b->datamap & (bit - 1))];
Branch: 1 branch
BranchTrueFalseTotal
if (b->datamap & bit) eb = (const hamt_entry *)b->slot[hamt_popcnt32(b->datamap & (bit - 1))]; 8708 56264 64972
944 56264 else cb = (const hamt_node *)b->slot[nb_slots - 1 - hamt_popcnt32(b->nodemap & (bit - 1))];
945  
946 64972 ▶ if (ea && eb) {
Branch: 2 branches
BranchTrueFalseTotal
if (ea && eb) { 8720 56252 64972
if (ea && eb) { 6467 2253 8720
947 6467 ▶ if (hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_entry_key_eq(eb, ea->key, ea->klen, ea->utf8, ea->hash)) return 0; 283 6184 6467
948 }
949 58505 ▶ else if (ea) {
Branch: 1 branch
BranchTrueFalseTotal
else if (ea) { 2253 56252 58505
950 2253 ▶ if (hamt_node_find(cb, depth + 1, ea->key, ea->klen, ea->utf8, ea->hash)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_node_find(cb, depth + 1, ea->key, ea->klen, ea->utf8, ea->hash)) return 0; 61 2192 2253
951 }
952 56252 ▶ else if (eb) {
Branch: 1 branch
BranchTrueFalseTotal
else if (eb) { 2241 54011 56252
953 2241 ▶ if (hamt_node_find(ca, depth + 1, eb->key, eb->klen, eb->utf8, eb->hash)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_node_find(ca, depth + 1, eb->key, eb->klen, eb->utf8, eb->hash)) return 0; 66 2175 2241
954 }
955 54011 ▶ else if (!hamt_node_disjoint(ca, cb, depth + 1, visits)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
else if (!hamt_node_disjoint(ca, cb, depth + 1, visits)) return 0; 3230 50781 54011
956 }
957 47819 return 1;
958 }
959  
960 1673 static int hamt_set_disjoint(const hamt_node *a, const hamt_node *b, size_t *visits) {
961 1673 *visits = 0;
962 1673 ▶ if (!a || !b) return 1;
Branch: 2 branches
BranchTrueFalseTotal
if (!a || !b) return 1; 1671 2 1673
if (!a || !b) return 1; 1 1670 1671
963 1670 return hamt_node_disjoint(a, b, 0, visits);
964 }
965  
966 #endif
« xs/vector_transient.xs ↑ Summary xs/vector.xs »