| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| : 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
| Branch | True | False | Total |
| if (n->ncoll) return n->ncoll == 1; |
12591 |
35706121 |
35718712 |
|
| 78 |
2871661 |
▶ | return n->nodemap == 0 && n->datamap != 0 |
Branch: 1 branch
| Branch | True | False | Total |
| return n->nodemap == 0 && n->datamap != 0 |
2871661 |
0 |
2871661 |
|
| 79 |
38577782 |
▶ | && (n->datamap & (n->datamap - 1)) == 0; |
Branch: 2 branches
| Branch | True | False | Total |
| && (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
| Branch | True | False | Total |
| hamt_node *n = (hamt_node *)HAMT_ALLOC(cx, HAMT_NODE_BYTES(nslots)); |
1664275 |
0 |
1664275 |
|
| 84 |
1664275 |
▶ | if (!n) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (i != skip) hamt_entry_retain((hamt_entry *)n->slot[i]); |
3184551 |
0 |
3184551 |
|
| 106 |
3426556 |
▶ | for (; i < N; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (; i < N; i++) |
2591384 |
835172 |
3426556 |
|
| 107 |
2591384 |
▶ | if (i != skip) hamt_node_retain((hamt_node *)n->slot[i]); |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (ia != ib) { |
101359 |
568995 |
670354 |
|
| 288 |
101359 |
| n = hamt_node_new(cx, 2); |
| 289 |
101359 |
▶ | if (!n) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| n->slot[0] = ia < ib ? a : b; |
50903 |
50456 |
101359 |
|
| 292 |
101359 |
▶ | n->slot[1] = ia < ib ? b : a; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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 |