| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #ifndef UTIL_HASHSET_H | ||
| 2 | #define UTIL_HASHSET_H | ||
| 3 | |||
| 4 | #include <stdbool.h> | ||
| 5 | #include <stddef.h> | ||
| 6 | #include "macros.h" | ||
| 7 | |||
| 8 | // A container type for holding a set of strings, using hashing for | ||
| 9 | // primary lookups and separate chaining for collision resolution. | ||
| 10 | typedef struct { | ||
| 11 | struct HashSetEntry **table; | ||
| 12 | size_t table_size; | ||
| 13 | size_t nr_entries; | ||
| 14 | size_t grow_at; | ||
| 15 | size_t (*hash)(const unsigned char *str, size_t len); | ||
| 16 | bool (*equal)(const void *s1, const void *s2, size_t n); | ||
| 17 | } HashSet; | ||
| 18 | |||
| 19 | typedef struct HashSetEntry { | ||
| 20 | struct HashSetEntry *next; | ||
| 21 | size_t str_len; | ||
| 22 | char str[]; | ||
| 23 | } HashSetEntry; | ||
| 24 | |||
| 25 | typedef struct { | ||
| 26 | const HashSet *set; | ||
| 27 | const HashSetEntry *entry; | ||
| 28 | size_t idx; | ||
| 29 | } HashSetIter; | ||
| 30 | |||
| 31 | 3 | static inline HashSetIter hashset_iter(const HashSet *set) | |
| 32 | { | ||
| 33 | 3 | return (HashSetIter){.set = set}; | |
| 34 | } | ||
| 35 | |||
| 36 | // Set `iter->entry` to the next active HashSetEntry in iter->set and | ||
| 37 | // return true, or return false when there are no remaining entries to | ||
| 38 | // visit. Note that `iter->entry` is only NULL prior to the first call. | ||
| 39 | 18 | static inline bool hashset_next(HashSetIter *iter) | |
| 40 | { | ||
| 41 |
4/4✓ Branch 0 (2→3) taken 14 times.
✓ Branch 1 (2→5) taken 4 times.
✓ Branch 2 (3→4) taken 3 times.
✓ Branch 3 (3→5) taken 11 times.
|
18 | if (likely(iter->entry) && iter->entry->next) { |
| 42 | // Traverse linked entries | ||
| 43 | 3 | iter->entry = iter->entry->next; | |
| 44 | 3 | return true; | |
| 45 | } | ||
| 46 | |||
| 47 | // Traverse table entries | ||
| 48 | 15 | const HashSet *set = iter->set; | |
| 49 |
2/2✓ Branch 0 (9→6) taken 98 times.
✓ Branch 1 (9→10) taken 5 times.
|
103 | for (size_t i = iter->idx, n = set->table_size; i < n; i++) { |
| 50 | 98 | const HashSetEntry *e = set->table[i]; | |
| 51 |
2/2✓ Branch 0 (6→7) taken 10 times.
✓ Branch 1 (6→8) taken 88 times.
|
98 | if (e) { |
| 52 | 10 | iter->entry = e; | |
| 53 | 10 | iter->idx = i + 1; | |
| 54 | 10 | return true; | |
| 55 | } | ||
| 56 | } | ||
| 57 | |||
| 58 | return false; | ||
| 59 | } | ||
| 60 | |||
| 61 | void hashset_init(HashSet *set, size_t initial_size, bool icase); | ||
| 62 | void hashset_free(HashSet *set); | ||
| 63 | HashSetEntry *hashset_get(const HashSet *set, const char *str, size_t str_len); | ||
| 64 | HashSetEntry *hashset_insert(HashSet *set, const char *str, size_t str_len); | ||
| 65 | |||
| 66 | #endif | ||
| 67 |