include/hamt/hamt_map.h

filter: Statementstmt 75.2% 85 / 113 Branchbran 71.9% 59 / 82 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 73.8% 144 / 195 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/abi.xs ↑ Summary include/hamt/hamt_check.h »
1 #ifndef HAMT_MAP_H
2 #define HAMT_MAP_H
3  
4 /* Lookup, insert and delete on a trie of hamt_node.
5 *
6 * Everything here works on a ROOT, and an empty map is a NULL root. An
7 * update copies the nodes on one path from the root to where the key lives
8 * and shares every other node with the trie it started from, which it never
9 * touches: the caller still holds the old root, and it is exactly as it was.
10 *
11 * THE CANONICAL SHAPE. Below the root, a node exists only where two or more
12 * entries share the path to it. Insert cannot break that. Delete can - it
13 * can leave a node holding one entry and nothing else - so on the way back
14 * up, a child that has come down to a single entry is folded into its
15 * parent as that entry. The fold can repeat all the way to the root.
16 *
17 * It follows that two maps holding the same keys have the same shape,
18 * whatever order they were built in and whatever was deleted on the way. */
19  
20 #ifndef HAMT_MAP_FWD
21 #define HAMT_MAP_FWD
22 typedef struct hamt_map hamt_map;
23 #endif
24 struct hamt_map {
25 hamt_node *root;
26 size_t count;
27 };
28  
29 #define HAMT_DEL_OOM (-1)
30 #define HAMT_DEL_ABSENT 0
31 #define HAMT_DEL_DONE 1
32  
33 /* The entry for a key in the subtree under `n`, which hangs at `depth`:
34 * borrowed, or NULL. Allocates nothing and changes no reference count. */
35 1335222 static hamt_entry *hamt_node_find(const hamt_node *n, unsigned depth,
36 const char *key, size_t klen, int utf8,
37 uint64_t hash) {
38  
39 9337936 ▶ while (n) {
Branch: 1 branch
BranchTrueFalseTotal
while (n) { 9337792 144 9337936
40 uint32_t bit, i;
41  
42 9337792 ▶ if (n->ncoll) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->ncoll) { 576048 8761744 9337792
43 2852744 ▶ for (i = 0; i < n->ncoll; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n->ncoll; i++) { 2838777 13967 2852744
44 2838777 hamt_entry *e = (hamt_entry *)n->slot[i];
45 2838777 ▶ if (hamt_entry_key_eq(e, key, klen, utf8, hash)) return e;
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_entry_key_eq(e, key, klen, utf8, hash)) return e; 562081 2276696 2838777
46 }
47 13967 return NULL;
48 }
49  
50 8761744 bit = HAMT_BIT(hash, depth);
51 8761744 ▶ if (n->datamap & bit) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->datamap & bit) { 738166 8023578 8761744
52 738166 hamt_entry *e = (hamt_entry *)
53 738166 n->slot[hamt_popcnt32(n->datamap & (bit - 1))];
54 738166 ▶ return hamt_entry_key_eq(e, key, klen, utf8, hash) ? e : NULL;
Branch: 1 branch
BranchTrueFalseTotal
return hamt_entry_key_eq(e, key, klen, utf8, hash) ? e : NULL; 732553 5613 738166
55 }
56 8023578 ▶ if (!(n->nodemap & bit)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!(n->nodemap & bit)) return NULL; 20864 8002714 8023578
57  
58 8002714 n = (const hamt_node *)n->slot[hamt_node_nslots(n) - 1
59 8002714 - hamt_popcnt32(n->nodemap & (bit - 1))];
60 8002714 depth++;
61 }
62 144 return NULL;
63 }
64  
65 /* The entry for a key, borrowed, or NULL. Retain what you keep. */
66 1291420 static hamt_entry *hamt_map_find(const hamt_node *root, const char *key,
67 size_t klen, int utf8, uint64_t hash) {
68 1291420 return hamt_node_find(root, 0, key, klen, utf8, hash);
69 }
70  
71 56063 static hamt_node *hamt_node_put(void *cx, hamt_node *n, unsigned depth,
72 hamt_entry *e, int *added) {
73 uint32_t bit, i;
74  
75 56063 ▶ if (n->ncoll) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->ncoll) { 4019 52044 56063
76 13341 ▶ for (i = 0; i < n->ncoll; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n->ncoll; i++) { 11487 1854 13341
77 11487 hamt_entry *old = (hamt_entry *)n->slot[i];
78 11487 ▶ if (!hamt_entry_key_eq(old, e->key, e->klen, e->utf8, e->hash)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!hamt_entry_key_eq(old, e->key, e->klen, e->utf8, e->hash)) continue; 9322 2165 11487
79 2165 ▶ if (old == e || old->val == e->val) return hamt_node_retain(n);
Branch: 2 branches
BranchTrueFalseTotal
if (old == e || old->val == e->val) return hamt_node_retain(n); 1094 1071 2165
if (old == e || old->val == e->val) return hamt_node_retain(n); 910 184 1094
80 184 return hamt_node_with_slot(cx, n, i, e, HAMT_NO_SKIP);
81 }
82 1854 *added = 1;
83 1854 return hamt_node_coll_add(cx, n, e);
84 }
85  
86 52044 bit = HAMT_BIT(e->hash, depth);
87  
88 52044 ▶ if (n->datamap & bit) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->datamap & bit) { 5449 46595 52044
89 5449 uint32_t di = hamt_popcnt32(n->datamap & (bit - 1));
90 5449 hamt_entry *old = (hamt_entry *)n->slot[di];
91 hamt_node *sub, *r;
92  
93 5449 ▶ if (hamt_entry_key_eq(old, e->key, e->klen, e->utf8, e->hash)) {
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_entry_key_eq(old, e->key, e->klen, e->utf8, e->hash)) { 4886 563 5449
94 /* The same value under the same key is no change, and the same
95 * root comes back: nothing is allocated. */
96 4886 ▶ if (old == e || old->val == e->val) return hamt_node_retain(n);
Branch: 2 branches
BranchTrueFalseTotal
if (old == e || old->val == e->val) return hamt_node_retain(n); 2382 2504 4886
if (old == e || old->val == e->val) return hamt_node_retain(n); 2117 265 2382
97 265 return hamt_node_with_slot(cx, n, di, e, HAMT_NO_SKIP);
98 }
99  
100 563 sub = hamt_node_pair(cx, old, e, depth + 1);
101 563 ▶ if (!sub) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!sub) return NULL; 0 563 563
102 563 r = hamt_node_entry_to_child(cx, n, bit, sub);
103 563 ▶ if (!r) { hamt_node_release(cx, sub); return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!r) { hamt_node_release(cx, sub); return NULL; } 0 563 563
104 563 *added = 1;
105 563 return r;
106 }
107  
108 46595 ▶ if (n->nodemap & bit) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->nodemap & bit) { 42183 4412 46595
109 42183 uint32_t ci = hamt_node_nslots(n) - 1 - hamt_popcnt32(n->nodemap & (bit - 1));
110 42183 hamt_node *child = (hamt_node *)n->slot[ci];
111 42183 hamt_node *sub = hamt_node_put(cx, child, depth + 1, e, added);
112 hamt_node *r;
113  
114 42183 ▶ if (!sub) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!sub) return NULL; 0 42183 42183
115 42183 ▶ if (sub == child) {
Branch: 1 branch
BranchTrueFalseTotal
if (sub == child) { 20484 21699 42183
116 20484 hamt_node_release(cx, sub);
117 20484 return hamt_node_retain(n);
118 }
119 21699 r = hamt_node_with_slot(cx, n, ci, sub, ci);
120 21699 ▶ if (!r) { hamt_node_release(cx, sub); *added = 0; return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!r) { hamt_node_release(cx, sub); *added = 0; return NULL; } 0 21699 21699
121 21699 return r;
122 }
123  
124 {
125 4412 hamt_node *r = hamt_node_add_entry(cx, n, bit, e);
126 4412 ▶ if (r) *added = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (r) *added = 1; 4412 0 4412
127 4412 return r;
128 }
129 }
130  
131 /* The root of a trie that holds everything `root` holds and `e` as well, or
132 * in place of the entry with e's key. One reference, owned by the caller.
133 * The entry is shared: the caller keeps its own reference to it.
134 *
135 * `*added` is 1 when the key was not there before and 0 when it was. When
136 * the key was there with the very same value, the root that comes back IS
137 * `root`, retained.
138 *
139 * NULL means no memory, and only that: `root` is untouched, and nothing was
140 * retained. */
141 0 static hamt_node *hamt_map_put(void *cx, hamt_node *root, hamt_entry *e,
142 int *added) {
143 hamt_node *r;
144  
145 0 *added = 0;
146 0 ▶ if (!root) {
Branch: 1 branch
BranchTrueFalseTotal
if (!root) { 0 0 0
147 0 r = hamt_node_new(cx, 1);
148 0 ▶ if (!r) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return NULL; 0 0 0
149 0 r->datamap = HAMT_BIT(e->hash, 0);
150 0 r->slot[0] = e;
151 0 hamt_node_adopt(r, HAMT_NO_SKIP);
152 0 *added = 1;
153 0 return r;
154 }
155 0 r = hamt_node_put(cx, root, 0, e, added);
156 0 ▶ if (!r) *added = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) *added = 0; 0 0 0
157 0 return r;
158 }
159  
160 12781 static hamt_node *hamt_node_del(void *cx, hamt_node *n, unsigned depth,
161 const char *key, size_t klen, int utf8,
162 uint64_t hash, int *status) {
163 uint32_t bit, i;
164  
165 12781 ▶ if (n->ncoll) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->ncoll) { 956 11825 12781
166 1763 ▶ for (i = 0; i < n->ncoll; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n->ncoll; i++) { 1763 0 1763
167 hamt_node *r;
168 1763 ▶ if (!hamt_entry_key_eq((hamt_entry *)n->slot[i], key, klen, utf8, hash))
Branch: 1 branch
BranchTrueFalseTotal
if (!hamt_entry_key_eq((hamt_entry *)n->slot[i], key, klen, utf8, hash)) 807 956 1763
169 807 continue;
170 956 r = hamt_node_coll_drop(cx, n, i);
171 956 ▶ *status = r ? HAMT_DEL_DONE : HAMT_DEL_OOM;
Branch: 1 branch
BranchTrueFalseTotal
*status = r ? HAMT_DEL_DONE : HAMT_DEL_OOM; 956 0 956
172 956 return r;
173 }
174 0 *status = HAMT_DEL_ABSENT;
175 0 return hamt_node_retain(n);
176 }
177  
178 11825 bit = HAMT_BIT(hash, depth);
179  
180 11825 ▶ if (n->datamap & bit) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->datamap & bit) { 1950 9875 11825
181 1950 hamt_entry *old = (hamt_entry *)
182 1950 n->slot[hamt_popcnt32(n->datamap & (bit - 1))];
183 hamt_node *r;
184  
185 1950 ▶ if (!hamt_entry_key_eq(old, key, klen, utf8, hash)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!hamt_entry_key_eq(old, key, klen, utf8, hash)) { 0 1950 1950
186 0 *status = HAMT_DEL_ABSENT;
187 0 return hamt_node_retain(n);
188 }
189 /* The last entry of the last node: the map is empty. Only a root
190 * gets here, since nothing below a root is ever down to one. */
191 1950 ▶ if (hamt_node_nslots(n) == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_node_nslots(n) == 1) { 0 1950 1950
192 0 *status = HAMT_DEL_DONE;
193 0 return NULL;
194 }
195 1950 r = hamt_node_drop_entry(cx, n, bit);
196 1950 ▶ *status = r ? HAMT_DEL_DONE : HAMT_DEL_OOM;
Branch: 1 branch
BranchTrueFalseTotal
*status = r ? HAMT_DEL_DONE : HAMT_DEL_OOM; 1950 0 1950
197 1950 return r;
198 }
199  
200 9875 ▶ if (n->nodemap & bit) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->nodemap & bit) { 9875 0 9875
201 9875 uint32_t ci = hamt_node_nslots(n) - 1 - hamt_popcnt32(n->nodemap & (bit - 1));
202 9875 hamt_node *child = (hamt_node *)n->slot[ci];
203 9875 hamt_node *sub = hamt_node_del(cx, child, depth + 1, key, klen, utf8,
204 hash, status);
205 hamt_node *r;
206  
207 9875 ▶ if (*status == HAMT_DEL_OOM) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (*status == HAMT_DEL_OOM) return NULL; 0 9875 9875
208 9875 ▶ if (*status == HAMT_DEL_ABSENT) {
Branch: 1 branch
BranchTrueFalseTotal
if (*status == HAMT_DEL_ABSENT) { 0 9875 9875
209 0 hamt_node_release(cx, sub);
210 0 return hamt_node_retain(n);
211 }
212 9875 ▶ if (!sub) HAMT_FATAL("a node below the root came back empty");
Branch: 1 branch
BranchTrueFalseTotal
if (!sub) HAMT_FATAL("a node below the root came back empty"); 0 9875 9875
213  
214 /* The fold. The child is down to one entry, so it stops existing and
215 * the entry moves up into the position the child had. If that leaves
216 * THIS node with one entry and nothing else, the caller folds it in
217 * turn. */
218 9875 ▶ if (hamt_node_is_single(sub))
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_node_is_single(sub)) 7839 2036 9875
219 7839 r = hamt_node_child_to_entry(cx, n, bit, (hamt_entry *)sub->slot[0]);
220 else
221 2036 r = hamt_node_with_slot(cx, n, ci, sub, HAMT_NO_SKIP);
222  
223 9875 hamt_node_release(cx, sub);
224 9875 ▶ if (!r) *status = HAMT_DEL_OOM;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) *status = HAMT_DEL_OOM; 0 9875 9875
225 9875 return r;
226 }
227  
228 0 *status = HAMT_DEL_ABSENT;
229 0 return hamt_node_retain(n);
230 }
231  
232 /* The root of a trie that holds everything `root` holds but the entry for
233 * this key. One reference, owned by the caller, when it is not NULL.
234 *
235 * HAMT_DEL_DONE the key was there. The root may be NULL: an empty map.
236 * HAMT_DEL_ABSENT it was not. The root that comes back IS `root`, retained
237 * (or NULL for NULL).
238 * HAMT_DEL_OOM no memory. NULL comes back and `root` is untouched. */
239 0 static hamt_node *hamt_map_del(void *cx, hamt_node *root, const char *key,
240 size_t klen, int utf8, uint64_t hash,
241 int *status) {
242 0 ▶ if (!root) {
Branch: 1 branch
BranchTrueFalseTotal
if (!root) { 0 0 0
243 0 *status = HAMT_DEL_ABSENT;
244 0 return NULL;
245 }
246 0 return hamt_node_del(cx, root, 0, key, klen, utf8, hash, status);
247 }
248  
249 #endif
« xs/abi.xs ↑ Summary include/hamt/hamt_check.h »