include/hamt/hamt_node.h

filter: Statementstmt 100% 146 / 146 Branchbran 73.6% 53 / 72 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 91.2% 199 / 218 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/hamt/hamt_xs.h ↑ Summary include/hamt/hamt_pool.h »
1 #ifndef HAMT_NODE_H
2 #define HAMT_NODE_H
3  
4 /* One node of the map's trie, and the handful of ways a node is copied with
5 * one thing different.
6 *
7 * A node is 32 positions wide, and each position is empty, or holds an
8 * entry, or holds a child. Two bitmaps say which: `datamap` has a bit for
9 * each position holding an entry and `nodemap` a bit for each holding a
10 * child, and no bit is in both. Only what is there is stored:
11 *
12 * slot[]: [ entries, lowest position first | children, HIGHEST first ]
13 *
14 * So with nd entries and N slots in all, the entry at position p is at
15 *
16 * slot[ popcount(datamap & (bit(p) - 1)) ]
17 *
18 * and the child at position p is at
19 *
20 * slot[ N - 1 - popcount(nodemap & (bit(p) - 1)) ]
21 *
22 * Children fill from the end so that turning an entry into a child, or a
23 * child back into an entry, moves the fewest slots.
24 *
25 * The position at each level is five bits of the key's hash: bits 0-4 at the
26 * root, 5-9 below it, and so on for twelve levels and sixty bits. A node
27 * thirteen deep has no hash left to index by, and is a COLLISION node: both
28 * maps zero, `ncoll` entries in a plain array, searched one by one.
29 *
30 * A node is never changed once more than one thing points at it. Every
31 * function here that "changes" a node allocates a new one; the functions
32 * that change one where it stands are in hamt_mut.h, and they first make
33 * sure nobody else is looking. */
34  
35 #define HAMT_BITS 5
36 #define HAMT_MAX_DEPTH 12 /* depths 0..11 index by hash; depth 12 collides */
37  
38 #define HAMT_IDX(hash, depth) \
39 ((unsigned)(((uint64_t)(hash) >> (HAMT_BITS * (depth))) & 31))
40 #define HAMT_BIT(hash, depth) ((uint32_t)1 << HAMT_IDX((hash), (depth)))
41  
42 typedef struct hamt_node {
43 uint32_t refcnt;
44 uint32_t datamap;
45 uint32_t nodemap;
46 uint32_t ncoll; /* > 0: a collision node, both maps zero */
47 void *slot[1];
48 } hamt_node;
49  
50 /* How many slots a node holding n things has room for: n rounded up to the
51 * next multiple of four. A node that is being built up in place gains a
52 * slot at a time, and with no room to spare every one of those would be a
53 * new allocation, a copy and a free; with this, three in four are a few
54 * pointers moved along. The room is a function of n and is stored nowhere,
55 * which is what keeps one rule true everywhere: A NODE HOLDING n THINGS IS
56 * ALLOCATED AT HAMT_NODE_BYTES(n). So whoever changes n in place has to
57 * check first that the new n has the same room, and reallocate if not. */
58 #define HAMT_NODE_ROOM(n) (((uint32_t)(n) + 3u) & ~3u)
59 #define HAMT_NODE_BYTES(n) \
60 (offsetof(hamt_node, slot) + (size_t)((n) ? HAMT_NODE_ROOM(n) : 4) * sizeof(void *))
61  
62 #define HAMT_NO_SKIP 0xffffffffU
63  
64 /* Entries in the node: the first this-many slots. */
65 8750124 static uint32_t hamt_node_ndata(const hamt_node *n) {
66 8750124 ▶ return n->ncoll ? n->ncoll : hamt_popcnt32(n->datamap);
Branch: 1 branch
BranchTrueFalseTotal
return n->ncoll ? n->ncoll : hamt_popcnt32(n->datamap); 1357046 7393078 8750124
67 }
68  
69 19627355 static uint32_t hamt_node_nslots(const hamt_node *n) {
70 19627355 return n->ncoll ? n->ncoll
71 19627355 ▶ : hamt_popcnt32(n->datamap) + hamt_popcnt32(n->nodemap);
Branch: 1 branch
BranchTrueFalseTotal
: hamt_popcnt32(n->datamap) + hamt_popcnt32(n->nodemap); 689680 18937675 19627355
72 }
73  
74 /* One entry and nothing else. Legal as a root. Anywhere else it is a node
75 * on its way to being folded into its parent, and never left standing. */
76 35718712 static int hamt_node_is_single(const hamt_node *n) {
77 35718712 ▶ if (n->ncoll) return n->ncoll == 1;
Branch: 1 branch
BranchTrueFalseTotal
if (n->ncoll) return n->ncoll == 1; 12591 35706121 35718712
78 2871661 ▶ return n->nodemap == 0 && n->datamap != 0
Branch: 1 branch
BranchTrueFalseTotal
return n->nodemap == 0 && n->datamap != 0 2871661 0 2871661
79 38577782 ▶ && (n->datamap & (n->datamap - 1)) == 0;
Branch: 2 branches
BranchTrueFalseTotal
&& (n->datamap & (n->datamap - 1)) == 0; 2871661 32834460 35706121
&& (n->datamap & (n->datamap - 1)) == 0; 33588 2838073 2871661
80 }
81  
82 1664275 static hamt_node *hamt_node_new(void *cx, uint32_t nslots) {
83 1664275 ▶ hamt_node *n = (hamt_node *)HAMT_ALLOC(cx, HAMT_NODE_BYTES(nslots));
Branch: 1 branch
BranchTrueFalseTotal
hamt_node *n = (hamt_node *)HAMT_ALLOC(cx, HAMT_NODE_BYTES(nslots)); 1664275 0 1664275
84 1664275 ▶ if (!n) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return NULL; 0 1664275 1664275
85 1664275 n->refcnt = 1;
86 1664275 n->datamap = 0;
87 1664275 n->nodemap = 0;
88 1664275 n->ncoll = 0;
89 (void)cx;
90 1664275 return n;
91 }
92  
93 2974448 static hamt_node *hamt_node_retain(hamt_node *n) {
94 2974448 ▶ if (n->refcnt == 0xffffffffU) HAMT_FATAL("a node's reference count would wrap");
Branch: 1 branch
BranchTrueFalseTotal
if (n->refcnt == 0xffffffffU) HAMT_FATAL("a node's reference count would wrap"); 0 2974448 2974448
95 2974448 n->refcnt++;
96 2974448 return n;
97 }
98  
99 /* A node that has just been filled with borrowed pointers takes its own
100 * reference to each. `skip` is the one slot whose reference the caller is
101 * handing over rather than sharing, or HAMT_NO_SKIP. */
102 835172 static void hamt_node_adopt(hamt_node *n, uint32_t skip) {
103 835172 uint32_t nd = hamt_node_ndata(n), N = hamt_node_nslots(n), i;
104 4019723 ▶ for (i = 0; i < nd; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nd; i++) 3184551 835172 4019723
105 3184551 ▶ if (i != skip) hamt_entry_retain((hamt_entry *)n->slot[i]);
Branch: 1 branch
BranchTrueFalseTotal
if (i != skip) hamt_entry_retain((hamt_entry *)n->slot[i]); 3184551 0 3184551
106 3426556 ▶ for (; i < N; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (; i < N; i++) 2591384 835172 3426556
107 2591384 ▶ if (i != skip) hamt_node_retain((hamt_node *)n->slot[i]);
Branch: 1 branch
BranchTrueFalseTotal
if (i != skip) hamt_node_retain((hamt_node *)n->slot[i]); 2268769 322615 2591384
108 835172 }
109  
110 /* At zero the node is freed BEFORE anything it held is released, the same
111 * rule as an entry and for the same reason: a value's release can run code
112 * that comes back in here. The slots are copied out to make that possible.
113 *
114 * A collision node can be wider than any buffer worth putting on the stack,
115 * so a wide one releases in place and is freed after. That is safe too - a
116 * node whose count has reached zero is reachable from nowhere, so nothing
117 * that runs can find it - it is only not the same order. */
118 4564561 static void hamt_node_release(void *cx, hamt_node *n) {
119 uint32_t nd, N, i;
120  
121 4564561 ▶ if (--n->refcnt) return;
Branch: 1 branch
BranchTrueFalseTotal
if (--n->refcnt) return; 2974448 1590113 4564561
122 1590113 nd = hamt_node_ndata(n);
123 1590113 N = hamt_node_nslots(n);
124  
125 1590113 ▶ if (N <= 32) {
Branch: 1 branch
BranchTrueFalseTotal
if (N <= 32) { 1579593 10520 1590113
126 void *s[32];
127 1579593 memcpy(s, n->slot, (size_t)N * sizeof(void *));
128 1579593 ▶ HAMT_FREE(cx, n, HAMT_NODE_BYTES(N));
Branch: 1 branch
BranchTrueFalseTotal
HAMT_FREE(cx, n, HAMT_NODE_BYTES(N)); 1579593 0 1579593
129 4515233 ▶ for (i = 0; i < nd; i++) hamt_entry_release(cx, (hamt_entry *)s[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nd; i++) hamt_entry_release(cx, (hamt_entry *)s[i]); 2935640 1579593 4515233
130 5116192 ▶ for (; i < N; i++) hamt_node_release(cx, (hamt_node *)s[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (; i < N; i++) hamt_node_release(cx, (hamt_node *)s[i]); 3536599 1579593 5116192
131 }
132 else {
133 747636 ▶ for (i = 0; i < N; i++) hamt_entry_release(cx, (hamt_entry *)n->slot[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < N; i++) hamt_entry_release(cx, (hamt_entry *)n->slot[i]); 737116 10520 747636
134 10520 ▶ HAMT_FREE(cx, n, HAMT_NODE_BYTES(N));
Branch: 1 branch
BranchTrueFalseTotal
HAMT_FREE(cx, n, HAMT_NODE_BYTES(N)); 10520 0 10520
135 }
136 }
137  
138 /* ---- copies with one thing different ----------------------------------
139 *
140 * Each returns a new node holding one reference to everything in it, or
141 * NULL when there is no memory, in which case nothing was retained. The
142 * node copied from is untouched. */
143  
144 /* The same node with slot i pointing somewhere else. `skip` as for adopt:
145 * pass i to hand over the caller's reference to p, HAMT_NO_SKIP to share. */
146 441877 static hamt_node *hamt_node_with_slot(void *cx, const hamt_node *n, uint32_t i,
147 void *p, uint32_t skip) {
148 441877 uint32_t N = hamt_node_nslots(n);
149 441877 hamt_node *r = hamt_node_new(cx, N);
150 441877 ▶ if (!r) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return NULL; 0 441877 441877
151 441877 r->datamap = n->datamap;
152 441877 r->nodemap = n->nodemap;
153 441877 r->ncoll = n->ncoll;
154 441877 memcpy(r->slot, n->slot, (size_t)N * sizeof(void *));
155 441877 r->slot[i] = p;
156 441877 hamt_node_adopt(r, skip);
157 441877 return r;
158 }
159  
160 /* An entry at a position that held nothing. */
161 17989 static hamt_node *hamt_node_add_entry(void *cx, const hamt_node *n,
162 uint32_t bit, hamt_entry *e) {
163 17989 uint32_t N = hamt_node_nslots(n);
164 17989 uint32_t di = hamt_popcnt32(n->datamap & (bit - 1));
165 17989 hamt_node *r = hamt_node_new(cx, N + 1);
166 17989 ▶ if (!r) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return NULL; 0 17989 17989
167 17989 r->datamap = n->datamap | bit;
168 17989 r->nodemap = n->nodemap;
169 17989 memcpy(r->slot, n->slot, (size_t)di * sizeof(void *));
170 17989 r->slot[di] = e;
171 17989 memcpy(r->slot + di + 1, n->slot + di, (size_t)(N - di) * sizeof(void *));
172 17989 hamt_node_adopt(r, HAMT_NO_SKIP);
173 17989 return r;
174 }
175  
176 /* The entry at a position gone, and nothing in its place. */
177 13379 static hamt_node *hamt_node_drop_entry(void *cx, const hamt_node *n, uint32_t bit) {
178 13379 uint32_t N = hamt_node_nslots(n);
179 13379 uint32_t di = hamt_popcnt32(n->datamap & (bit - 1));
180 13379 hamt_node *r = hamt_node_new(cx, N - 1);
181 13379 ▶ if (!r) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return NULL; 0 13379 13379
182 13379 r->datamap = n->datamap & ~bit;
183 13379 r->nodemap = n->nodemap;
184 13379 memcpy(r->slot, n->slot, (size_t)di * sizeof(void *));
185 13379 memcpy(r->slot + di, n->slot + di + 1, (size_t)(N - 1 - di) * sizeof(void *));
186 13379 hamt_node_adopt(r, HAMT_NO_SKIP);
187 13379 return r;
188 }
189  
190 /* The entry at a position replaced by a child: a second key arrived there.
191 * The caller's reference to the child is handed over.
192 *
193 * The entry leaves the front and the child joins the back, so every slot
194 * between the two moves down by one and nothing outside them moves:
195 *
196 * old: e0 .. [E] .. e(nd-1) | c(high) .. .. c(low)
197 * new: e0 .. .. e(nd-1) | c(high) .. [C] .. c(low)
198 */
199 6247 static hamt_node *hamt_node_entry_to_child(void *cx, const hamt_node *n,
200 uint32_t bit, hamt_node *child) {
201 6247 uint32_t N = hamt_node_nslots(n);
202 6247 uint32_t di = hamt_popcnt32(n->datamap & (bit - 1));
203 6247 uint32_t r = hamt_popcnt32(n->nodemap & (bit - 1));
204 6247 uint32_t ci = N - 1 - r;
205 6247 hamt_node *x = hamt_node_new(cx, N);
206 6247 ▶ if (!x) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!x) return NULL; 0 6247 6247
207 6247 x->datamap = n->datamap & ~bit;
208 6247 x->nodemap = n->nodemap | bit;
209 6247 memcpy(x->slot, n->slot, (size_t)di * sizeof(void *));
210 6247 memcpy(x->slot + di, n->slot + di + 1, (size_t)(ci - di) * sizeof(void *));
211 6247 x->slot[ci] = child;
212 6247 memcpy(x->slot + ci + 1, n->slot + ci + 1, (size_t)r * sizeof(void *));
213 6247 hamt_node_adopt(x, ci);
214 6247 return x;
215 }
216  
217 /* The reverse: a child that is down to one entry is folded away and the
218 * entry takes its position. The entry is shared, not handed over.
219 *
220 * old: e0 .. .. e(nd-1) | c(high) .. [C] .. c(low)
221 * new: e0 .. [E] .. e(nd-1) | c(high) .. .. c(low)
222 */
223 31290 static hamt_node *hamt_node_child_to_entry(void *cx, const hamt_node *n,
224 uint32_t bit, hamt_entry *e) {
225 31290 uint32_t N = hamt_node_nslots(n);
226 31290 uint32_t di = hamt_popcnt32(n->datamap & (bit - 1));
227 31290 uint32_t r = hamt_popcnt32(n->nodemap & (bit - 1));
228 31290 uint32_t ci = N - 1 - r;
229 31290 hamt_node *x = hamt_node_new(cx, N);
230 31290 ▶ if (!x) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!x) return NULL; 0 31290 31290
231 31290 x->datamap = n->datamap | bit;
232 31290 x->nodemap = n->nodemap & ~bit;
233 31290 memcpy(x->slot, n->slot, (size_t)di * sizeof(void *));
234 31290 x->slot[di] = e;
235 31290 memcpy(x->slot + di + 1, n->slot + di, (size_t)(ci - di) * sizeof(void *));
236 31290 memcpy(x->slot + ci + 1, n->slot + ci + 1, (size_t)r * sizeof(void *));
237 31290 hamt_node_adopt(x, HAMT_NO_SKIP);
238 31290 return x;
239 }
240  
241 /* A collision node with one more entry at its end. */
242 151369 static hamt_node *hamt_node_coll_add(void *cx, const hamt_node *n, hamt_entry *e) {
243 hamt_node *r;
244 151369 ▶ if (n->ncoll == 0xffffffffU) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (n->ncoll == 0xffffffffU) return NULL; 0 151369 151369
245 151369 r = hamt_node_new(cx, n->ncoll + 1);
246 151369 ▶ if (!r) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return NULL; 0 151369 151369
247 151369 r->ncoll = n->ncoll + 1;
248 151369 memcpy(r->slot, n->slot, (size_t)n->ncoll * sizeof(void *));
249 151369 r->slot[n->ncoll] = e;
250 151369 hamt_node_adopt(r, HAMT_NO_SKIP);
251 151369 return r;
252 }
253  
254 /* A collision node without its i-th entry. Down to one, it is a node its
255 * parent will fold away at once. */
256 12591 static hamt_node *hamt_node_coll_drop(void *cx, const hamt_node *n, uint32_t i) {
257 12591 hamt_node *r = hamt_node_new(cx, n->ncoll - 1);
258 12591 ▶ if (!r) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!r) return NULL; 0 12591 12591
259 12591 r->ncoll = n->ncoll - 1;
260 12591 memcpy(r->slot, n->slot, (size_t)i * sizeof(void *));
261 12591 memcpy(r->slot + i, n->slot + i + 1, (size_t)(n->ncoll - 1 - i) * sizeof(void *));
262 12591 hamt_node_adopt(r, HAMT_NO_SKIP);
263 12591 return r;
264 }
265  
266 /* The smallest subtree that holds two entries with different keys, built to
267 * hang at `depth`. Where their hashes still agree it is a chain of nodes
268 * with one child each; where they part, a node with the two entries; and if
269 * they never part, a collision node. Both entries are shared. */
270 724481 static hamt_node *hamt_node_pair(void *cx, hamt_entry *a, hamt_entry *b,
271 unsigned depth) {
272 hamt_node *n, *sub;
273 unsigned ia, ib;
274  
275 724481 ▶ if (depth >= HAMT_MAX_DEPTH) {
Branch: 1 branch
BranchTrueFalseTotal
if (depth >= HAMT_MAX_DEPTH) { 54127 670354 724481
276 54127 n = hamt_node_new(cx, 2);
277 54127 ▶ if (!n) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return NULL; 0 54127 54127
278 54127 n->ncoll = 2;
279 54127 n->slot[0] = a;
280 54127 n->slot[1] = b;
281 54127 hamt_node_adopt(n, HAMT_NO_SKIP);
282 54127 return n;
283 }
284  
285 670354 ia = HAMT_IDX(a->hash, depth);
286 670354 ib = HAMT_IDX(b->hash, depth);
287 670354 ▶ if (ia != ib) {
Branch: 1 branch
BranchTrueFalseTotal
if (ia != ib) { 101359 568995 670354
288 101359 n = hamt_node_new(cx, 2);
289 101359 ▶ if (!n) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return NULL; 0 101359 101359
290 101359 n->datamap = ((uint32_t)1 << ia) | ((uint32_t)1 << ib);
291 101359 ▶ n->slot[0] = ia < ib ? a : b;
Branch: 1 branch
BranchTrueFalseTotal
n->slot[0] = ia < ib ? a : b; 50903 50456 101359
292 101359 ▶ n->slot[1] = ia < ib ? b : a;
Branch: 1 branch
BranchTrueFalseTotal
n->slot[1] = ia < ib ? b : a; 50903 50456 101359
293 101359 hamt_node_adopt(n, HAMT_NO_SKIP);
294 101359 return n;
295 }
296  
297 568995 sub = hamt_node_pair(cx, a, b, depth + 1);
298 568995 ▶ if (!sub) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!sub) return NULL; 0 568995 568995
299 568995 n = hamt_node_new(cx, 1);
300 568995 ▶ if (!n) { hamt_node_release(cx, sub); return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!n) { hamt_node_release(cx, sub); return NULL; } 0 568995 568995
301 568995 n->nodemap = (uint32_t)1 << ia;
302 568995 n->slot[0] = sub;
303 568995 return n;
304 }
305  
306 #endif
« include/hamt/hamt_xs.h ↑ Summary include/hamt/hamt_pool.h »