| 1 |
|
| #ifndef HAMT_CHECK_H |
| 2 |
|
| #define HAMT_CHECK_H |
| 3 |
|
| |
| 4 |
|
| /* Walks a whole trie and says whether it is one this library could have |
| 5 |
|
| * built. For the tests: it visits every node, so it costs what the map |
| 6 |
|
| * holds, and nothing in the library calls it. |
| 7 |
|
| * |
| 8 |
|
| * 0 when every rule holds. Otherwise the number of the first rule that did |
| 9 |
|
| * not, from the list below, so a failure names what broke. */ |
| 10 |
|
| |
| 11 |
|
| #define HAMT_CHK_OK 0 |
| 12 |
|
| #define HAMT_CHK_REFCNT 1 /* a node or entry with a count of zero */ |
| 13 |
|
| #define HAMT_CHK_MAPS_OVERLAP 2 /* a position in both maps */ |
| 14 |
|
| #define HAMT_CHK_EMPTY_NODE 3 /* a node holding nothing */ |
| 15 |
|
| #define HAMT_CHK_SINGLE_BELOW 4 /* one entry, no children, not the root */ |
| 16 |
|
| #define HAMT_CHK_COLL_SHALLOW 5 /* a collision node above depth 12 */ |
| 17 |
|
| #define HAMT_CHK_COLL_MAPS 6 /* a collision node with a map bit set */ |
| 18 |
|
| #define HAMT_CHK_COLL_SMALL 7 /* a collision node with fewer than two */ |
| 19 |
|
| #define HAMT_CHK_COLL_DUP 8 /* two equal keys in a collision node */ |
| 20 |
|
| #define HAMT_CHK_TOO_DEEP 9 /* an indexing node at depth 12 */ |
| 21 |
|
| #define HAMT_CHK_ENTRY_PATH 10 /* an entry not where its hash puts it */ |
| 22 |
|
| #define HAMT_CHK_NULL_SLOT 11 /* a slot holding nothing */ |
| 23 |
|
| #define HAMT_CHK_COUNT 12 /* the entries do not total the count */ |
| 24 |
|
| #define HAMT_CHK_ORDER 13 /* entries or children out of order */ |
| 25 |
|
| |
| 26 |
|
| /* The hash bits that every entry under a node at this depth must share. */ |
| 27 |
38733192 |
| static uint64_t hamt_chk_prefix_mask(unsigned depth) { |
| 28 |
38733192 |
| unsigned bits = HAMT_BITS * depth; |
| 29 |
38733192 |
▶ | return bits >= 64 ? ~(uint64_t)0 : (((uint64_t)1 << bits) - 1); |
Branch: 1 branch
| Branch | True | False | Total |
| return bits >= 64 ? ~(uint64_t)0 : (((uint64_t)1 << bits) - 1); |
38733192 |
0 |
38733192 |
|
| 30 |
|
| } |
| 31 |
|
| |
| 32 |
38733192 |
| static int hamt_node_check(const hamt_node *n, unsigned depth, uint64_t prefix, |
| 33 |
|
| size_t *count) { |
| 34 |
|
| uint32_t nd, N, i, pos; |
| 35 |
38733192 |
| uint64_t pmask = hamt_chk_prefix_mask(depth); |
| 36 |
|
| |
| 37 |
38733192 |
▶ | if (!n) return HAMT_CHK_NULL_SLOT; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!n) return HAMT_CHK_NULL_SLOT; |
0 |
38733192 |
38733192 |
|
| 38 |
38733192 |
▶ | if (n->refcnt == 0) return HAMT_CHK_REFCNT; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n->refcnt == 0) return HAMT_CHK_REFCNT; |
0 |
38733192 |
38733192 |
|
| 39 |
|
| |
| 40 |
38733192 |
▶ | if (n->ncoll) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (n->ncoll) { |
3146760 |
35586432 |
38733192 |
|
| 41 |
3146760 |
▶ | if (depth < HAMT_MAX_DEPTH) return HAMT_CHK_COLL_SHALLOW; |
Branch: 1 branch
| Branch | True | False | Total |
| if (depth < HAMT_MAX_DEPTH) return HAMT_CHK_COLL_SHALLOW; |
0 |
3146760 |
3146760 |
|
| 42 |
3146760 |
▶ | if (n->datamap || n->nodemap) return HAMT_CHK_COLL_MAPS; |
Branch: 2 branches
| Branch | True | False | Total |
| if (n->datamap || n->nodemap) return HAMT_CHK_COLL_MAPS; |
3146760 |
0 |
3146760 |
| if (n->datamap || n->nodemap) return HAMT_CHK_COLL_MAPS; |
0 |
3146760 |
3146760 |
|
| 43 |
3146760 |
▶ | if (n->ncoll < 2) return HAMT_CHK_COLL_SMALL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n->ncoll < 2) return HAMT_CHK_COLL_SMALL; |
0 |
3146760 |
3146760 |
|
| 44 |
16299179 |
▶ | for (i = 0; i < n->ncoll; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < n->ncoll; i++) { |
13152419 |
3146760 |
16299179 |
|
| 45 |
13152419 |
| const hamt_entry *e = (const hamt_entry *)n->slot[i]; |
| 46 |
|
| uint32_t j; |
| 47 |
13152419 |
▶ | if (!e) return HAMT_CHK_NULL_SLOT; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!e) return HAMT_CHK_NULL_SLOT; |
0 |
13152419 |
13152419 |
|
| 48 |
13152419 |
▶ | if (e->refcnt == 0) return HAMT_CHK_REFCNT; |
Branch: 1 branch
| Branch | True | False | Total |
| if (e->refcnt == 0) return HAMT_CHK_REFCNT; |
0 |
13152419 |
13152419 |
|
| 49 |
13152419 |
▶ | if ((e->hash & pmask) != prefix) return HAMT_CHK_ENTRY_PATH; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((e->hash & pmask) != prefix) return HAMT_CHK_ENTRY_PATH; |
0 |
13152419 |
13152419 |
|
| 50 |
93876278 |
▶ | for (j = 0; j < i; j++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (j = 0; j < i; j++) { |
80723859 |
13152419 |
93876278 |
|
| 51 |
80723859 |
| const hamt_entry *f = (const hamt_entry *)n->slot[j]; |
| 52 |
80723859 |
▶ | if (hamt_entry_key_eq(f, e->key, e->klen, e->utf8, e->hash)) |
Branch: 1 branch
| Branch | True | False | Total |
| if (hamt_entry_key_eq(f, e->key, e->klen, e->utf8, e->hash)) |
0 |
80723859 |
80723859 |
|
| 53 |
0 |
| return HAMT_CHK_COLL_DUP; |
| 54 |
|
| } |
| 55 |
|
| } |
| 56 |
3146760 |
| *count += n->ncoll; |
| 57 |
3146760 |
| return HAMT_CHK_OK; |
| 58 |
|
| } |
| 59 |
|
| |
| 60 |
35586432 |
▶ | if (depth >= HAMT_MAX_DEPTH) return HAMT_CHK_TOO_DEEP; |
Branch: 1 branch
| Branch | True | False | Total |
| if (depth >= HAMT_MAX_DEPTH) return HAMT_CHK_TOO_DEEP; |
0 |
35586432 |
35586432 |
|
| 61 |
35586432 |
▶ | if (n->datamap & n->nodemap) return HAMT_CHK_MAPS_OVERLAP; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n->datamap & n->nodemap) return HAMT_CHK_MAPS_OVERLAP; |
0 |
35586432 |
35586432 |
|
| 62 |
|
| |
| 63 |
35586432 |
| nd = hamt_popcnt32(n->datamap); |
| 64 |
35586432 |
| N = nd + hamt_popcnt32(n->nodemap); |
| 65 |
35586432 |
▶ | if (N == 0) return HAMT_CHK_EMPTY_NODE; |
Branch: 1 branch
| Branch | True | False | Total |
| if (N == 0) return HAMT_CHK_EMPTY_NODE; |
0 |
35586432 |
35586432 |
|
| 66 |
35586432 |
▶ | if (depth > 0 && hamt_node_is_single(n)) return HAMT_CHK_SINGLE_BELOW; |
Branch: 2 branches
| Branch | True | False | Total |
| if (depth > 0 && hamt_node_is_single(n)) return HAMT_CHK_SINGLE_BELOW; |
35546691 |
39741 |
35586432 |
| if (depth > 0 && hamt_node_is_single(n)) return HAMT_CHK_SINGLE_BELOW; |
0 |
35546691 |
35546691 |
|
| 67 |
|
| |
| 68 |
|
| /* Entries: the i-th slot must hold the entry for the i-th set bit of |
| 69 |
|
| * the datamap, lowest first. */ |
| 70 |
35586432 |
| i = 0; |
| 71 |
1174352256 |
▶ | for (pos = 0; pos < 32; pos++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (pos = 0; pos < 32; pos++) { |
1138765824 |
35586432 |
1174352256 |
|
| 72 |
|
| const hamt_entry *e; |
| 73 |
1138765824 |
▶ | if (!(n->datamap & ((uint32_t)1 << pos))) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!(n->datamap & ((uint32_t)1 << pos))) continue; |
1124073205 |
14692619 |
1138765824 |
|
| 74 |
14692619 |
| e = (const hamt_entry *)n->slot[i++]; |
| 75 |
14692619 |
▶ | if (!e) return HAMT_CHK_NULL_SLOT; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!e) return HAMT_CHK_NULL_SLOT; |
0 |
14692619 |
14692619 |
|
| 76 |
14692619 |
▶ | if (e->refcnt == 0) return HAMT_CHK_REFCNT; |
Branch: 1 branch
| Branch | True | False | Total |
| if (e->refcnt == 0) return HAMT_CHK_REFCNT; |
0 |
14692619 |
14692619 |
|
| 77 |
14692619 |
▶ | if ((e->hash & pmask) != prefix) return HAMT_CHK_ENTRY_PATH; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((e->hash & pmask) != prefix) return HAMT_CHK_ENTRY_PATH; |
0 |
14692619 |
14692619 |
|
| 78 |
14692619 |
▶ | if (HAMT_IDX(e->hash, depth) != pos) return HAMT_CHK_ORDER; |
Branch: 1 branch
| Branch | True | False | Total |
| if (HAMT_IDX(e->hash, depth) != pos) return HAMT_CHK_ORDER; |
0 |
14692619 |
14692619 |
|
| 79 |
|
| } |
| 80 |
35586432 |
| *count += nd; |
| 81 |
|
| |
| 82 |
|
| /* Children: the last slot holds the child for the lowest set bit of the |
| 83 |
|
| * nodemap, and they run backwards from there. Each child is checked |
| 84 |
|
| * against the prefix its position gives it, so a child in the wrong |
| 85 |
|
| * slot fails on its own entries. */ |
| 86 |
35586432 |
| i = N; |
| 87 |
1174352256 |
▶ | for (pos = 0; pos < 32; pos++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (pos = 0; pos < 32; pos++) { |
1138765824 |
35586432 |
1174352256 |
|
| 88 |
|
| int rc; |
| 89 |
1138765824 |
▶ | if (!(n->nodemap & ((uint32_t)1 << pos))) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!(n->nodemap & ((uint32_t)1 << pos))) continue; |
1100072373 |
38693451 |
1138765824 |
|
| 90 |
38693451 |
| rc = hamt_node_check((const hamt_node *)n->slot[--i], depth + 1, |
| 91 |
38693451 |
| prefix | ((uint64_t)pos << (HAMT_BITS * depth)), |
| 92 |
|
| count); |
| 93 |
38693451 |
▶ | if (rc) return rc; |
Branch: 1 branch
| Branch | True | False | Total |
| if (rc) return rc; |
0 |
38693451 |
38693451 |
|
| 94 |
|
| } |
| 95 |
35586432 |
| return HAMT_CHK_OK; |
| 96 |
|
| } |
| 97 |
|
| |
| 98 |
40679 |
| static int hamt_map_check(const hamt_node *root, size_t count) { |
| 99 |
40679 |
| size_t seen = 0; |
| 100 |
|
| int rc; |
| 101 |
40679 |
▶ | if (!root) return count == 0 ? HAMT_CHK_OK : HAMT_CHK_COUNT; |
Branch: 2 branches
| Branch | True | False | Total |
| if (!root) return count == 0 ? HAMT_CHK_OK : HAMT_CHK_COUNT; |
938 |
39741 |
40679 |
| if (!root) return count == 0 ? HAMT_CHK_OK : HAMT_CHK_COUNT; |
938 |
0 |
938 |
|
| 102 |
39741 |
| rc = hamt_node_check(root, 0, 0, &seen); |
| 103 |
39741 |
▶ | if (rc) return rc; |
Branch: 1 branch
| Branch | True | False | Total |
| if (rc) return rc; |
0 |
39741 |
39741 |
|
| 104 |
39741 |
▶ | return seen == count ? HAMT_CHK_OK : HAMT_CHK_COUNT; |
Branch: 1 branch
| Branch | True | False | Total |
| return seen == count ? HAMT_CHK_OK : HAMT_CHK_COUNT; |
39741 |
0 |
39741 |
|
| 105 |
|
| } |
| 106 |
|
| |
| 107 |
|
| #endif |