| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| && e->klen == klen |
47696026 |
41341373 |
89037399 |
|
| 73 |
47696026 |
▶ | && e->utf8 == (utf8 ? 1 : 0) |
Branch: 1 branch
| Branch | True | False | Total |
| && e->utf8 == (utf8 ? 1 : 0) |
47696026 |
0 |
47696026 |
|
| 74 |
178196362 |
▶ | && (klen == 0 || memcmp(e->key, key, klen) == 0); |
Branch: 3 branches
| Branch | True | False | Total |
| && (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 |