include/hamt/hamt_entry.h

filter: Statementstmt 100% 27 / 27 Branchbran 83.3% 20 / 24 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 92.1% 47 / 51 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/hamt/hamt_pool.h ↑ Summary include/hamt/hamt_ops.h »
1 #ifndef HAMT_ENTRY_H
2 #define HAMT_ENTRY_H
3  
4 /* One key and its value, in one allocation, shared by every node of every
5 * version that holds it.
6 *
7 * An entry never changes after it is made. Giving a key a new value makes a
8 * new entry and copies the key's bytes: a key is short, and in exchange a
9 * node carries one pointer for each entry and retains one thing when it is
10 * copied. */
11  
12 typedef struct hamt_entry {
13 uint32_t refcnt;
14 uint8_t utf8; /* the key is UTF-8 that could not be downgraded */
15 uint64_t hash;
16 void *val; /* NULL in a set */
17 size_t klen;
18 char key[1]; /* klen bytes, then a NUL */
19 } hamt_entry;
20  
21 #define HAMT_ENTRY_BYTES(klen) (offsetof(hamt_entry, key) + (size_t)(klen) + 1)
22  
23 /* One reference, owned by the caller. The value is retained; the caller
24 * keeps whatever reference it came in with. NULL when there is no memory, in
25 * which case the value was not retained. */
26 695464 static hamt_entry *hamt_entry_new(void *cx, const char *key, size_t klen,
27 int utf8, uint64_t hash, void *val) {
28 hamt_entry *e;
29  
30 695464 ▶ if (klen > (size_t)-1 - offsetof(hamt_entry, key) - 1) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (klen > (size_t)-1 - offsetof(hamt_entry, key) - 1) return NULL; 0 695464 695464
31 695464 e = (hamt_entry *)HAMT_ALLOC(cx, HAMT_ENTRY_BYTES(klen));
32 695464 ▶ if (!e) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!e) return NULL; 0 695464 695464
33  
34 695464 e->refcnt = 1;
35 695464 e->utf8 = utf8 ? 1 : 0;
36 695464 e->hash = hash;
37 695464 e->val = val;
38 695464 e->klen = klen;
39 695464 ▶ if (klen) memcpy(e->key, key, klen);
Branch: 1 branch
BranchTrueFalseTotal
if (klen) memcpy(e->key, key, klen); 695451 13 695464
40 695464 e->key[klen] = '\0';
41  
42 695464 ▶ if (val) HAMT_VAL_RETAIN(cx, val);
Branch: 1 branch
BranchTrueFalseTotal
if (val) HAMT_VAL_RETAIN(cx, val); 292229 403235 695464
43 (void)cx;
44 695464 return e;
45 }
46  
47 /* Reaching the limit takes four billion live nodes pointing at one entry.
48 * It stops rather than wrapping to a count that frees the entry under them. */
49 3944347 static hamt_entry *hamt_entry_retain(hamt_entry *e) {
50 3944347 ▶ if (e->refcnt == 0xffffffffU) HAMT_FATAL("an entry's reference count would wrap");
Branch: 1 branch
BranchTrueFalseTotal
if (e->refcnt == 0xffffffffU) HAMT_FATAL("an entry's reference count would wrap"); 0 3944347 3944347
51 3944347 e->refcnt++;
52 3944347 return e;
53 }
54  
55 /* The order matters. Releasing the value can run code that comes back into
56 * this library, and by then the entry must be gone: so the value's pointer
57 * is taken out, the entry is freed, and the value is released last. */
58 4639811 static void hamt_entry_release(void *cx, hamt_entry *e) {
59 void *val;
60  
61 4639811 ▶ if (--e->refcnt) return;
Branch: 1 branch
BranchTrueFalseTotal
if (--e->refcnt) return; 3944347 695464 4639811
62 695464 val = e->val;
63 695464 HAMT_FREE(cx, e, HAMT_ENTRY_BYTES(e->klen));
64 695464 ▶ if (val) HAMT_VAL_RELEASE(cx, val);
Branch: 1 branch
BranchTrueFalseTotal
if (val) HAMT_VAL_RELEASE(cx, val); 292229 403235 695464
65 (void)cx;
66 }
67  
68 /* Cheapest test first: almost every miss is settled by the hash. */
69 89158963 static int hamt_entry_key_eq(const hamt_entry *e, const char *key, size_t klen,
70 int utf8, uint64_t hash) {
71 89158963 return e->hash == hash
72 89037399 ▶ && e->klen == klen
Branch: 1 branch
BranchTrueFalseTotal
&& e->klen == klen 47696026 41341373 89037399
73 47696026 ▶ && e->utf8 == (utf8 ? 1 : 0)
Branch: 1 branch
BranchTrueFalseTotal
&& e->utf8 == (utf8 ? 1 : 0) 47696026 0 47696026
74 178196362 ▶ && (klen == 0 || memcmp(e->key, key, klen) == 0);
Branch: 3 branches
BranchTrueFalseTotal
&& (klen == 0 || memcmp(e->key, key, klen) == 0); 89037399 121564 89158963
&& (klen == 0 || memcmp(e->key, key, klen) == 0); 47696012 14 47696026
&& (klen == 0 || memcmp(e->key, key, klen) == 0); 1694103 46001909 47696012
75 }
76  
77 #endif
« include/hamt/hamt_pool.h ↑ Summary include/hamt/hamt_ops.h »