include/hamt/hamt_check.h

filter: Statementstmt 98.0% 49 / 50 Branchbran 64.0% 41 / 64 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 78.9% 90 / 114 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/hamt/hamt_map.h ↑ Summary HAMT.xs »
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (!n) return HAMT_CHK_NULL_SLOT; 0 38733192 38733192
38 38733192 ▶ if (n->refcnt == 0) return HAMT_CHK_REFCNT;
Branch: 1 branch
BranchTrueFalseTotal
if (n->refcnt == 0) return HAMT_CHK_REFCNT; 0 38733192 38733192
39  
40 38733192 ▶ if (n->ncoll) {
Branch: 1 branch
BranchTrueFalseTotal
if (n->ncoll) { 3146760 35586432 38733192
41 3146760 ▶ if (depth < HAMT_MAX_DEPTH) return HAMT_CHK_COLL_SHALLOW;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (n->ncoll < 2) return HAMT_CHK_COLL_SMALL; 0 3146760 3146760
44 16299179 ▶ for (i = 0; i < n->ncoll; i++) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (!e) return HAMT_CHK_NULL_SLOT; 0 13152419 13152419
48 13152419 ▶ if (e->refcnt == 0) return HAMT_CHK_REFCNT;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if ((e->hash & pmask) != prefix) return HAMT_CHK_ENTRY_PATH; 0 13152419 13152419
50 93876278 ▶ for (j = 0; j < i; j++) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (!e) return HAMT_CHK_NULL_SLOT; 0 14692619 14692619
76 14692619 ▶ if (e->refcnt == 0) return HAMT_CHK_REFCNT;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (rc) return rc; 0 39741 39741
104 39741 ▶ return seen == count ? HAMT_CHK_OK : HAMT_CHK_COUNT;
Branch: 1 branch
BranchTrueFalseTotal
return seen == count ? HAMT_CHK_OK : HAMT_CHK_COUNT; 39741 0 39741
105 }
106  
107 #endif
« include/hamt/hamt_map.h ↑ Summary HAMT.xs »