| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (va == vb) return 1; |
5229 |
205371 |
210600 |
|
| 52 |
205371 |
▶ | if (!va || !vb) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (a == b) return 1; |
2495 |
189914 |
192409 |
|
| 63 |
189914 |
▶ | if (!a || !b) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (rc <= 0) return rc; |
33 |
83299 |
83332 |
|
| 96 |
|
| } |
| 97 |
366379 |
▶ | for (; i < N; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!e) goto fail; |
0 |
13032 |
13032 |
|
| 197 |
13032 |
▶ | if (e != ea) same_a = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (e != ea) same_a = 0; |
1362 |
11670 |
13032 |
|
| 198 |
13032 |
▶ | if (e != eb) same_b = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!e) goto fail; |
18 |
28693 |
28711 |
|
| 287 |
28693 |
▶ | if (e != ea) same_a = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (e != ea) same_a = 0; |
1857 |
26836 |
28693 |
|
| 288 |
28693 |
▶ | if (e != eb) same_b = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!sub) goto fail; |
0 |
6713 |
6713 |
|
| 305 |
6713 |
| same_a = 0; |
| 306 |
6713 |
▶ | if (sub != cb) same_b = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (sub != cb) same_b = 0; |
3393 |
3320 |
6713 |
|
| 307 |
6713 |
▶ | c->added += hamt_node_count(cb) - (found ? 1 : 0); |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!sub) goto fail; |
3 |
7167 |
7170 |
|
| 315 |
7167 |
▶ | if (sub != ca) same_a = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (sub != ca) same_a = 0; |
3885 |
3282 |
7167 |
|
| 316 |
7167 |
| same_b = 0; |
| 317 |
7167 |
▶ | if (!found) c->added++; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!sub) goto fail; |
4 |
130828 |
130832 |
|
| 324 |
130828 |
▶ | if (sub != ca) same_a = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (sub != ca) same_a = 0; |
112757 |
18071 |
130828 |
|
| 325 |
130828 |
▶ | if (sub != cb) same_b = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| : hamt_diff_report(c, kind, e, NULL); |
534 |
178 |
712 |
|
| 414 |
712 |
▶ | if (rc) return rc; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| : 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
| Branch | True | False | Total |
| : hamt_diff_report(c, kind, x, NULL); |
889 |
265 |
1154 |
|
| 437 |
|
| } |
| 438 |
1855 |
▶ | if (rc) return rc; |
Branch: 1 branch
| Branch | True | False | Total |
| if (rc) return rc; |
0 |
1855 |
1855 |
|
| 439 |
|
| } |
| 440 |
733 |
▶ | if (found) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| : 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
| Branch | True | False | Total |
| if (a == b) return 0; |
698 |
6901 |
7599 |
|
| 450 |
6901 |
| c->visits++; |
| 451 |
|
| |
| 452 |
6901 |
▶ | if (a->ncoll) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (a->ncoll) { |
310 |
6591 |
6901 |
|
| 453 |
2962 |
▶ | for (i = 0; i < a->ncoll; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| : hamt_diff_same_key(c, ea, eb); |
779 |
1873 |
2652 |
|
| 461 |
2652 |
▶ | if (rc) return rc; |
Branch: 1 branch
| Branch | True | False | Total |
| if (rc) return rc; |
0 |
2652 |
2652 |
|
| 462 |
|
| } |
| 463 |
2962 |
▶ | for (j = 0; j < b->ncoll; j++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| : hamt_diff_all(c, ca, HAMT_DIFF_REMOVE); |
575 |
85 |
660 |
|
| 498 |
23361 |
▶ | else if (!ea && !ca) |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| : hamt_diff_all(c, cb, HAMT_DIFF_ADD); |
1617 |
209 |
1826 |
|
| 501 |
21535 |
▶ | else if (ea && eb) { |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (a == b) return 0; |
10 |
43 |
53 |
|
| 526 |
43 |
▶ | if (!a) return hamt_diff_all(c, b, HAMT_DIFF_ADD); |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!list) { c->err = HAMT_ERR_OOM; return out; } |
0 |
15742 |
15742 |
|
| 634 |
104286 |
▶ | for (i = 0; i < a->ncoll; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| : 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| : 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| *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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| *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
| Branch | True | False | Total |
| if (a == b) return 1; |
5492 |
6204 |
11696 |
|
| 858 |
6204 |
| (*visits)++; |
| 859 |
|
| |
| 860 |
6204 |
▶ | if (a->ncoll) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (a->ncoll) { |
270 |
5934 |
6204 |
|
| 861 |
1186 |
▶ | for (i = 0; i < a->ncoll; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!a) return 1; |
2 |
1671 |
1673 |
|
| 909 |
1671 |
▶ | if (!b || ca > cb) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (a->ncoll) { |
3757 |
51459 |
55216 |
|
| 922 |
23759 |
▶ | for (i = 0; i < a->ncoll; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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 |