include/hamt/hamt_mut.h

filter: Statementstmt 96.7% 211 / 218 Branchbran 75.4% 92 / 122 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 89.1% 303 / 340 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/hamt/hamt_vec.h ↑ Summary include/hamt/hamt_sv.h »
1 #ifndef HAMT_MUT_H
2 #define HAMT_MUT_H
3  
4 /* Insert and delete that change a trie where it stands, wherever that is
5 * safe, and copy only where it is not.
6 *
7 * WHEN IT IS SAFE. A node may be changed in place exactly when its
8 * reference count is one. The caller of these functions owns one reference
9 * to the root and hands it over; if that is the only reference there is,
10 * nobody else can reach the root, so nobody else can see it change. The
11 * same holds one level down: a child with a count of one is pointed at by
12 * that parent alone, and the walk only reaches it through a parent it has
13 * just found to be its own. A node with any other count is shared with
14 * something - an older version, a snapshot, a walk in progress - and is
15 * copied instead; the copy takes its own reference to each child, which
16 * makes every child shared too, so everything under a shared node is copied
17 * in turn without anything having to say so.
18 *
19 * This is why a batch of updates on a fresh handle costs one path of copies
20 * for the first update and almost nothing for the rest: after the first,
21 * the path is the handle's alone.
22 *
23 * It rests on one rule that every caller keeps: NOBODY HOLDS A NODE WITHOUT
24 * COUNTING IT. A pointer kept across a call here without a reference of its
25 * own is a pointer to something that may have been changed or freed.
26 *
27 * THE DISPLACED ENTRY. An update displaces at most one entry: the one whose
28 * value is replaced, or the one deleted. Releasing it can run a value's
29 * destructor, which can call back into the very handle being updated, so it
30 * is not released here. It is handed back through `dead`, with a reference,
31 * for the caller to release once the new root is in place.
32 *
33 * NO MEMORY. Every function either does all of its work or none: on failure
34 * the trie is exactly as it was and the caller still owns the reference it
35 * passed in. Nothing is changed in place until every allocation the change
36 * needs has succeeded. */
37  
38 #define HAMT_EDITABLE(n) ((n)->refcnt == 1)
39  
40 /* The node with an entry added at a position that held nothing. If it has
41 * room, it is changed where it stands and comes back itself. If not, it is
42 * a new allocation that takes over the old node's references rather than
43 * adding to them, and the old node's memory is freed. NULL when there is no
44 * memory, with the node untouched. */
45 341448 static hamt_node *hamt_node_add_entry_move(void *cx, hamt_node *n, uint32_t bit,
46 hamt_entry *e) {
47 341448 uint32_t N = hamt_node_nslots(n);
48 341448 uint32_t di = hamt_popcnt32(n->datamap & (bit - 1));
49 hamt_node *r;
50  
51 /* Room for one more where it stands: nothing is allocated. */
52 341448 ▶ if (HAMT_NODE_ROOM(N + 1) == HAMT_NODE_ROOM(N) && N) {
Branch: 2 branches
BranchTrueFalseTotal
if (HAMT_NODE_ROOM(N + 1) == HAMT_NODE_ROOM(N) && N) { 267819 73629 341448
if (HAMT_NODE_ROOM(N + 1) == HAMT_NODE_ROOM(N) && N) { 267819 0 267819
53 267819 memmove(n->slot + di + 1, n->slot + di, (size_t)(N - di) * sizeof(void *));
54 267819 n->slot[di] = hamt_entry_retain(e);
55 267819 n->datamap |= bit;
56 267819 return n;
57 }
58 73629 r = hamt_node_new(cx, N + 1);
59 73629 ▶ if (!r) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return NULL; 0 73629 73629
60 73629 r->datamap = n->datamap | bit;
61 73629 r->nodemap = n->nodemap;
62 73629 memcpy(r->slot, n->slot, (size_t)di * sizeof(void *));
63 73629 r->slot[di] = hamt_entry_retain(e);
64 73629 memcpy(r->slot + di + 1, n->slot + di, (size_t)(N - di) * sizeof(void *));
65 73629 ▶ HAMT_FREE(cx, n, HAMT_NODE_BYTES(N));
Branch: 1 branch
BranchTrueFalseTotal
HAMT_FREE(cx, n, HAMT_NODE_BYTES(N)); 73629 0 73629
66 73629 return r;
67 }
68  
69 /* The node without the entry at a position, the same way. The entry is
70 * handed back with the reference the node held. */
71 2790 static hamt_node *hamt_node_drop_entry_move(void *cx, hamt_node *n, uint32_t bit,
72 hamt_entry **dropped) {
73 2790 uint32_t N = hamt_node_nslots(n);
74 2790 uint32_t di = hamt_popcnt32(n->datamap & (bit - 1));
75 hamt_node *r;
76  
77 /* One fewer still needs the room it has: it stays where it is. */
78 2790 ▶ if (HAMT_NODE_ROOM(N - 1) == HAMT_NODE_ROOM(N)) {
Branch: 1 branch
BranchTrueFalseTotal
if (HAMT_NODE_ROOM(N - 1) == HAMT_NODE_ROOM(N)) { 2257 533 2790
79 2257 *dropped = (hamt_entry *)n->slot[di];
80 2257 memmove(n->slot + di, n->slot + di + 1, (size_t)(N - 1 - di) * sizeof(void *));
81 2257 n->datamap &= ~bit;
82 2257 return n;
83 }
84 533 r = hamt_node_new(cx, N - 1);
85 533 ▶ if (!r) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return NULL; 0 533 533
86 533 r->datamap = n->datamap & ~bit;
87 533 r->nodemap = n->nodemap;
88 533 *dropped = (hamt_entry *)n->slot[di];
89 533 memcpy(r->slot, n->slot, (size_t)di * sizeof(void *));
90 533 memcpy(r->slot + di, n->slot + di + 1, (size_t)(N - 1 - di) * sizeof(void *));
91 533 ▶ HAMT_FREE(cx, n, HAMT_NODE_BYTES(N));
Branch: 1 branch
BranchTrueFalseTotal
HAMT_FREE(cx, n, HAMT_NODE_BYTES(N)); 533 0 533
92 533 return r;
93 }
94  
95 /* Same size, so no allocation: the entry at a position gives way to a
96 * child, which takes over the caller's reference. The entry is handed back
97 * with the reference the node held. */
98 139689 static hamt_entry *hamt_node_entry_to_child_here(hamt_node *n, uint32_t bit,
99 hamt_node *child) {
100 139689 uint32_t N = hamt_node_nslots(n);
101 139689 uint32_t di = hamt_popcnt32(n->datamap & (bit - 1));
102 139689 uint32_t ci = N - 1 - hamt_popcnt32(n->nodemap & (bit - 1));
103 139689 hamt_entry *old = (hamt_entry *)n->slot[di];
104 139689 memmove(n->slot + di, n->slot + di + 1, (size_t)(ci - di) * sizeof(void *));
105 139689 n->slot[ci] = child;
106 139689 n->datamap &= ~bit;
107 139689 n->nodemap |= bit;
108 139689 return old;
109 }
110  
111 /* And back: the child at a position gives way to an entry, which takes over
112 * the caller's reference. The child is handed back with the reference the
113 * node held. */
114 3115 static hamt_node *hamt_node_child_to_entry_here(hamt_node *n, uint32_t bit,
115 hamt_entry *e) {
116 3115 uint32_t N = hamt_node_nslots(n);
117 3115 uint32_t di = hamt_popcnt32(n->datamap & (bit - 1));
118 3115 uint32_t ci = N - 1 - hamt_popcnt32(n->nodemap & (bit - 1));
119 3115 hamt_node *old = (hamt_node *)n->slot[ci];
120 3115 memmove(n->slot + di + 1, n->slot + di, (size_t)(ci - di) * sizeof(void *));
121 3115 n->slot[di] = e;
122 3115 n->datamap |= bit;
123 3115 n->nodemap &= ~bit;
124 3115 return old;
125 }
126  
127 /* Takes over the caller's reference to `n` and returns a node the caller
128 * owns one reference to, which may be `n` itself. NULL means no memory: `n`
129 * is untouched and still the caller's. */
130 3135208 static hamt_node *hamt_node_put_mut(void *cx, hamt_node *n, unsigned depth,
131 hamt_entry *e, int *added, hamt_entry **dead) {
132 3135208 int edit = HAMT_EDITABLE(n);
133 uint32_t bit, i;
134 hamt_node *r;
135  
136 3135208 ▶ if (n->ncoll) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->ncoll) { 169406 2965802 3135208
137 1962463 ▶ for (i = 0; i < n->ncoll; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n->ncoll; i++) { 1812948 149515 1962463
138 1812948 hamt_entry *old = (hamt_entry *)n->slot[i];
139 1812948 ▶ 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; 1793057 19891 1812948
140 19891 ▶ if (old == e || old->val == e->val) return n;
Branch: 2 branches
BranchTrueFalseTotal
if (old == e || old->val == e->val) return n; 19891 0 19891
if (old == e || old->val == e->val) return n; 113 19778 19891
141 19778 ▶ if (edit) {
Branch: 1 branch
BranchTrueFalseTotal
if (edit) { 5567 14211 19778
142 5567 n->slot[i] = hamt_entry_retain(e);
143 5567 *dead = old;
144 5567 return n;
145 }
146 14211 r = hamt_node_with_slot(cx, n, i, e, HAMT_NO_SKIP);
147 14211 ▶ if (!r) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return NULL; 0 14211 14211
148 14211 *dead = hamt_entry_retain(old);
149 14211 hamt_node_release(cx, n);
150 14211 return r;
151 }
152 /* A collision node is rare enough to grow by copying whether or not
153 * it is ours. The copy holds every entry, so letting the old node
154 * go releases nothing that matters. */
155 149515 r = hamt_node_coll_add(cx, n, e);
156 149515 ▶ if (!r) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return NULL; 0 149515 149515
157 149515 *added = 1;
158 149515 hamt_node_release(cx, n);
159 149515 return r;
160 }
161  
162 2965802 bit = HAMT_BIT(e->hash, depth);
163  
164 2965802 ▶ if (n->datamap & bit) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->datamap & bit) { 166229 2799573 2965802
165 166229 uint32_t di = hamt_popcnt32(n->datamap & (bit - 1));
166 166229 hamt_entry *old = (hamt_entry *)n->slot[di];
167 hamt_node *sub;
168  
169 166229 ▶ 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)) { 20856 145373 166229
170 20856 ▶ if (old == e || old->val == e->val) return n;
Branch: 2 branches
BranchTrueFalseTotal
if (old == e || old->val == e->val) return n; 20856 0 20856
if (old == e || old->val == e->val) return n; 165 20691 20856
171 20691 ▶ if (edit) {
Branch: 1 branch
BranchTrueFalseTotal
if (edit) { 3921 16770 20691
172 3921 n->slot[di] = hamt_entry_retain(e);
173 3921 *dead = old;
174 3921 return n;
175 }
176 16770 r = hamt_node_with_slot(cx, n, di, e, HAMT_NO_SKIP);
177 16770 ▶ if (!r) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return NULL; 0 16770 16770
178 16770 *dead = hamt_entry_retain(old);
179 16770 hamt_node_release(cx, n);
180 16770 return r;
181 }
182  
183 /* Two keys at one position. The subtree that holds both takes its
184 * own reference to each, so the entry leaving this node is not
185 * displaced, only moved down. */
186 145373 sub = hamt_node_pair(cx, old, e, depth + 1);
187 145373 ▶ if (!sub) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!sub) return NULL; 0 145373 145373
188 145373 ▶ if (edit) {
Branch: 1 branch
BranchTrueFalseTotal
if (edit) { 139689 5684 145373
189 139689 hamt_entry_release(cx, hamt_node_entry_to_child_here(n, bit, sub));
190 139689 *added = 1;
191 139689 return n;
192 }
193 5684 r = hamt_node_entry_to_child(cx, n, bit, sub);
194 5684 ▶ if (!r) { hamt_node_release(cx, sub); return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!r) { hamt_node_release(cx, sub); return NULL; } 0 5684 5684
195 5684 *added = 1;
196 5684 hamt_node_release(cx, n);
197 5684 return r;
198 }
199  
200 2799573 ▶ if (n->nodemap & bit) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->nodemap & bit) { 2444548 355025 2799573
201 2444548 uint32_t ci = hamt_node_nslots(n) - 1 - hamt_popcnt32(n->nodemap & (bit - 1));
202 2444548 hamt_node *child = (hamt_node *)n->slot[ci];
203 hamt_node *sub;
204  
205 2444548 ▶ if (edit) {
Branch: 1 branch
BranchTrueFalseTotal
if (edit) { 2148362 296186 2444548
206 /* This node's reference to the child is the one handed down. */
207 2148362 sub = hamt_node_put_mut(cx, child, depth + 1, e, added, dead);
208 2148362 ▶ if (!sub) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!sub) return NULL; 0 2148362 2148362
209 2148362 n->slot[ci] = sub;
210 2148362 return n;
211 }
212  
213 /* A shared node's reference to its child is not ours to hand down,
214 * so the child goes down with one of its own - which makes it
215 * shared, and so copied rather than changed. */
216 296186 hamt_node_retain(child);
217 296186 sub = hamt_node_put_mut(cx, child, depth + 1, e, added, dead);
218 296186 ▶ if (!sub) { hamt_node_release(cx, child); return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!sub) { hamt_node_release(cx, child); return NULL; } 0 296186 296186
219 296186 ▶ if (sub == child) {
Branch: 1 branch
BranchTrueFalseTotal
if (sub == child) { 1517 294669 296186
220 1517 hamt_node_release(cx, sub);
221 1517 return n;
222 }
223 294669 r = hamt_node_with_slot(cx, n, ci, sub, ci);
224 294669 ▶ if (!r) {
Branch: 1 branch
BranchTrueFalseTotal
if (!r) { 0 294669 294669
225 /* Everything below was a copy, so it can all be let go. */
226 0 hamt_node_release(cx, sub);
227 0 ▶ if (*dead) { hamt_entry_release(cx, *dead); *dead = NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (*dead) { hamt_entry_release(cx, *dead); *dead = NULL; } 0 0 0
228 0 *added = 0;
229 0 return NULL;
230 }
231 294669 hamt_node_release(cx, n);
232 294669 return r;
233 }
234  
235 341448 r = edit ? hamt_node_add_entry_move(cx, n, bit, e)
236 355025 ▶ : hamt_node_add_entry(cx, n, bit, e);
Branch: 1 branch
BranchTrueFalseTotal
: hamt_node_add_entry(cx, n, bit, e); 341448 13577 355025
237 355025 ▶ if (!r) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return NULL; 0 355025 355025
238 355025 *added = 1;
239 355025 ▶ if (!edit) hamt_node_release(cx, n);
Branch: 1 branch
BranchTrueFalseTotal
if (!edit) hamt_node_release(cx, n); 13577 341448 355025
240 355025 return r;
241 }
242  
243 /* Puts an entry into the trie at *rootp, which the caller owns one
244 * reference to before and after; the pointer may change. The entry is
245 * shared: the caller keeps its own reference.
246 *
247 * `*added` is 1 for a new key. `*dead` is the entry this one displaced, if
248 * any, for the caller to release AFTER it has put the new root wherever it
249 * keeps its root.
250 *
251 * 0, or -1 for no memory with everything as it was. */
252 694149 static int hamt_map_put_mut(void *cx, hamt_node **rootp, hamt_entry *e,
253 int *added, hamt_entry **dead) {
254 hamt_node *r;
255  
256 694149 *added = 0;
257 694149 *dead = NULL;
258 694149 ▶ if (!*rootp) {
Branch: 1 branch
BranchTrueFalseTotal
if (!*rootp) { 3489 690660 694149
259 3489 r = hamt_node_new(cx, 1);
260 3489 ▶ if (!r) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return -1; 0 3489 3489
261 3489 r->datamap = HAMT_BIT(e->hash, 0);
262 3489 r->slot[0] = hamt_entry_retain(e);
263 3489 *added = 1;
264 3489 *rootp = r;
265 3489 return 0;
266 }
267 690660 r = hamt_node_put_mut(cx, *rootp, 0, e, added, dead);
268 690660 ▶ if (!r) { *added = 0; return -1; }
Branch: 1 branch
BranchTrueFalseTotal
if (!r) { *added = 0; return -1; } 0 690660 690660
269 690660 *rootp = r;
270 690660 return 0;
271 }
272  
273 /* Takes over the caller's reference to `n` when it removes something
274 * (HAMT_DEL_DONE) and returns what replaces it, which may be `n` itself, or
275 * NULL for a root that is now empty. HAMT_DEL_ABSENT returns `n`, untouched
276 * and still the caller's. HAMT_DEL_OOM returns NULL, likewise. */
277 299338 static hamt_node *hamt_node_del_mut(void *cx, hamt_node *n, unsigned depth,
278 const char *key, size_t klen, int utf8,
279 uint64_t hash, int *status, hamt_entry **dead) {
280 299338 int edit = HAMT_EDITABLE(n);
281 uint32_t bit, i;
282 hamt_node *r;
283  
284 299338 ▶ if (n->ncoll) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->ncoll) { 18479 280859 299338
285 334838 ▶ for (i = 0; i < n->ncoll; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n->ncoll; i++) { 327994 6844 334838
286 327994 hamt_entry *old = (hamt_entry *)n->slot[i];
287 327994 ▶ if (!hamt_entry_key_eq(old, key, klen, utf8, hash)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!hamt_entry_key_eq(old, key, klen, utf8, hash)) continue; 316359 11635 327994
288 11635 r = hamt_node_coll_drop(cx, n, i);
289 11635 ▶ if (!r) { *status = HAMT_DEL_OOM; return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!r) { *status = HAMT_DEL_OOM; return NULL; } 0 11635 11635
290 11635 *dead = hamt_entry_retain(old);
291 11635 *status = HAMT_DEL_DONE;
292 11635 hamt_node_release(cx, n);
293 11635 return r;
294 }
295 6844 *status = HAMT_DEL_ABSENT;
296 6844 return n;
297 }
298  
299 280859 bit = HAMT_BIT(hash, depth);
300  
301 280859 ▶ if (n->datamap & bit) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->datamap & bit) { 18252 262607 280859
302 18252 hamt_entry *old = (hamt_entry *)
303 18252 n->slot[hamt_popcnt32(n->datamap & (bit - 1))];
304  
305 18252 ▶ if (!hamt_entry_key_eq(old, key, klen, utf8, hash)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!hamt_entry_key_eq(old, key, klen, utf8, hash)) { 4026 14226 18252
306 4026 *status = HAMT_DEL_ABSENT;
307 4026 return n;
308 }
309 14226 ▶ if (hamt_node_nslots(n) == 1) { /* the last of a root */
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_node_nslots(n) == 1) { /* the last of a root */ 7 14219 14226
310 7 *dead = hamt_entry_retain(old);
311 7 *status = HAMT_DEL_DONE;
312 7 hamt_node_release(cx, n);
313 7 return NULL;
314 }
315 14219 ▶ if (edit) {
Branch: 1 branch
BranchTrueFalseTotal
if (edit) { 2790 11429 14219
316 2790 r = hamt_node_drop_entry_move(cx, n, bit, dead);
317 2790 ▶ if (!r) { *status = HAMT_DEL_OOM; return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!r) { *status = HAMT_DEL_OOM; return NULL; } 0 2790 2790
318 2790 *status = HAMT_DEL_DONE;
319 2790 return r;
320 }
321 11429 r = hamt_node_drop_entry(cx, n, bit);
322 11429 ▶ if (!r) { *status = HAMT_DEL_OOM; return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!r) { *status = HAMT_DEL_OOM; return NULL; } 0 11429 11429
323 11429 *dead = hamt_entry_retain(old);
324 11429 *status = HAMT_DEL_DONE;
325 11429 hamt_node_release(cx, n);
326 11429 return r;
327 }
328  
329 262607 ▶ if (n->nodemap & bit) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->nodemap & bit) { 254350 8257 262607
330 254350 uint32_t ci = hamt_node_nslots(n) - 1 - hamt_popcnt32(n->nodemap & (bit - 1));
331 254350 hamt_node *child = (hamt_node *)n->slot[ci];
332 hamt_node *sub;
333  
334 254350 ▶ if (edit) {
Branch: 1 branch
BranchTrueFalseTotal
if (edit) { 74791 179559 254350
335 74791 sub = hamt_node_del_mut(cx, child, depth + 1, key, klen, utf8, hash,
336 status, dead);
337 74791 ▶ if (*status != HAMT_DEL_DONE) return *status == HAMT_DEL_ABSENT ? n : NULL;
Branch: 2 branches
BranchTrueFalseTotal
if (*status != HAMT_DEL_DONE) return *status == HAMT_DEL_ABSENT ? n : NULL; 31045 43746 74791
if (*status != HAMT_DEL_DONE) return *status == HAMT_DEL_ABSENT ? n : NULL; 31045 0 31045
338 43746 ▶ 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 43746 43746
339  
340 43746 ▶ if (hamt_node_is_single(sub)) {
Branch: 1 branch
BranchTrueFalseTotal
if (hamt_node_is_single(sub)) { 3115 40631 43746
341 /* The fold, where the node stands. The entry is kept alive
342 * by a reference of this node's before the child that held
343 * it is let go. */
344 3115 hamt_entry *up = hamt_entry_retain((hamt_entry *)sub->slot[0]);
345 3115 n->slot[ci] = sub;
346 3115 hamt_node_release(cx, hamt_node_child_to_entry_here(n, bit, up));
347 }
348 40631 else n->slot[ci] = sub;
349 43746 return n;
350 }
351  
352 179559 hamt_node_retain(child);
353 179559 sub = hamt_node_del_mut(cx, child, depth + 1, key, klen, utf8, hash,
354 status, dead);
355 179559 ▶ if (*status == HAMT_DEL_OOM) { hamt_node_release(cx, child); return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (*status == HAMT_DEL_OOM) { hamt_node_release(cx, child); return NULL; } 0 179559 179559
356 179559 ▶ if (*status == HAMT_DEL_ABSENT) { hamt_node_release(cx, child); return n; }
Branch: 1 branch
BranchTrueFalseTotal
if (*status == HAMT_DEL_ABSENT) { hamt_node_release(cx, child); return n; } 64065 115494 179559
357 115494 ▶ 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 115494 115494
358  
359 115494 r = hamt_node_is_single(sub)
360 23451 ? hamt_node_child_to_entry(cx, n, bit, (hamt_entry *)sub->slot[0])
361 115494 ▶ : hamt_node_with_slot(cx, n, ci, sub, HAMT_NO_SKIP);
Branch: 1 branch
BranchTrueFalseTotal
: hamt_node_with_slot(cx, n, ci, sub, HAMT_NO_SKIP); 23451 92043 115494
362 115494 hamt_node_release(cx, sub);
363 115494 ▶ if (!r) {
Branch: 1 branch
BranchTrueFalseTotal
if (!r) { 0 115494 115494
364 0 ▶ if (*dead) { hamt_entry_release(cx, *dead); *dead = NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (*dead) { hamt_entry_release(cx, *dead); *dead = NULL; } 0 0 0
365 0 *status = HAMT_DEL_OOM;
366 0 return NULL;
367 }
368 115494 hamt_node_release(cx, n);
369 115494 return r;
370 }
371  
372 8257 *status = HAMT_DEL_ABSENT;
373 8257 return n;
374 }
375  
376 /* Takes a key out of the trie at *rootp, which the caller owns one
377 * reference to before and after; the pointer may change, and is NULL for a
378 * trie that is now empty. `*dead` is the entry removed, for the caller to
379 * release after it has put the new root wherever it keeps its root.
380 *
381 * HAMT_DEL_DONE, HAMT_DEL_ABSENT, or HAMT_DEL_OOM with everything as it
382 * was. */
383 44996 static int hamt_map_del_mut(void *cx, hamt_node **rootp, const char *key,
384 size_t klen, int utf8, uint64_t hash,
385 hamt_entry **dead) {
386 44996 int status = HAMT_DEL_ABSENT;
387 hamt_node *r;
388  
389 44996 *dead = NULL;
390 44996 ▶ if (!*rootp) return HAMT_DEL_ABSENT;
Branch: 1 branch
BranchTrueFalseTotal
if (!*rootp) return HAMT_DEL_ABSENT; 8 44988 44996
391 44988 r = hamt_node_del_mut(cx, *rootp, 0, key, klen, utf8, hash, &status, dead);
392 44988 ▶ if (status == HAMT_DEL_DONE) *rootp = r;
Branch: 1 branch
BranchTrueFalseTotal
if (status == HAMT_DEL_DONE) *rootp = r; 25861 19127 44988
393 44988 return status;
394 }
395  
396 #endif
« include/hamt/hamt_vec.h ↑ Summary include/hamt/hamt_sv.h »