| 1 |
|
| #ifndef HAMT_ITER_H |
| 2 |
|
| #define HAMT_ITER_H |
| 3 |
|
| |
| 4 |
|
| /* Every entry of a trie, once each. A node's own entries come first, in |
| 5 |
|
| * slot order, and then each child in slot order, so the order is the same |
| 6 |
|
| * every time for the same trie and two tries of the same shape are walked |
| 7 |
|
| * in step. |
| 8 |
|
| * |
| 9 |
|
| * The iterator borrows the root. Whoever walks holds a reference to it for |
| 10 |
|
| * as long as the walk lasts; since nothing reachable from a root ever |
| 11 |
|
| * changes, nothing else can go wrong underneath it. */ |
| 12 |
|
| |
| 13 |
|
| typedef struct hamt_iter { |
| 14 |
|
| const hamt_node *node[HAMT_MAX_DEPTH + 1]; |
| 15 |
|
| uint32_t pos[HAMT_MAX_DEPTH + 1]; |
| 16 |
|
| int depth; /* -1 when there is nothing left */ |
| 17 |
|
| } hamt_iter; |
| 18 |
|
| |
| 19 |
10261 |
| static void hamt_iter_init(hamt_iter *it, const hamt_node *root) { |
| 20 |
10261 |
▶ | it->depth = root ? 0 : -1; |
Branch: 1 branch
| Branch | True | False | Total |
| it->depth = root ? 0 : -1; |
9328 |
933 |
10261 |
|
| 21 |
10261 |
| it->node[0] = root; |
| 22 |
10261 |
| it->pos[0] = 0; |
| 23 |
10261 |
| } |
| 24 |
|
| |
| 25 |
1698474 |
| static hamt_entry *hamt_iter_next(hamt_iter *it) { |
| 26 |
5999085 |
▶ | while (it->depth >= 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (it->depth >= 0) { |
5988868 |
10217 |
5999085 |
|
| 27 |
5988868 |
| const hamt_node *n = it->node[it->depth]; |
| 28 |
5988868 |
| uint32_t p = it->pos[it->depth]; |
| 29 |
|
| |
| 30 |
5988868 |
▶ | if (p < hamt_node_ndata(n)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (p < hamt_node_ndata(n)) { |
1688257 |
4300611 |
5988868 |
|
| 31 |
1688257 |
| it->pos[it->depth] = p + 1; |
| 32 |
1688257 |
| return (hamt_entry *)n->slot[p]; |
| 33 |
|
| } |
| 34 |
4300611 |
▶ | if (p < hamt_node_nslots(n)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (p < hamt_node_nslots(n)) { |
2145665 |
2154946 |
4300611 |
|
| 35 |
2145665 |
| it->pos[it->depth] = p + 1; |
| 36 |
2145665 |
| it->depth++; |
| 37 |
2145665 |
| it->node[it->depth] = (const hamt_node *)n->slot[p]; |
| 38 |
2145665 |
| it->pos[it->depth] = 0; |
| 39 |
2145665 |
| continue; |
| 40 |
|
| } |
| 41 |
2154946 |
| it->depth--; |
| 42 |
|
| } |
| 43 |
10217 |
| return NULL; |
| 44 |
|
| } |
| 45 |
|
| |
| 46 |
|
| #endif |