Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 1 | /* |
| 2 | * Generic implementation of hash-based key value mappings. |
| 3 | */ |
| 4 | #include "cache.h" |
| 5 | #include "hashmap.h" |
| 6 | |
| 7 | #define FNV32_BASE ((unsigned int) 0x811c9dc5) |
| 8 | #define FNV32_PRIME ((unsigned int) 0x01000193) |
| 9 | |
| 10 | unsigned int strhash(const char *str) |
| 11 | { |
| 12 | unsigned int c, hash = FNV32_BASE; |
| 13 | while ((c = (unsigned char) *str++)) |
| 14 | hash = (hash * FNV32_PRIME) ^ c; |
| 15 | return hash; |
| 16 | } |
| 17 | |
| 18 | unsigned int strihash(const char *str) |
| 19 | { |
| 20 | unsigned int c, hash = FNV32_BASE; |
| 21 | while ((c = (unsigned char) *str++)) { |
| 22 | if (c >= 'a' && c <= 'z') |
| 23 | c -= 'a' - 'A'; |
| 24 | hash = (hash * FNV32_PRIME) ^ c; |
| 25 | } |
| 26 | return hash; |
| 27 | } |
| 28 | |
| 29 | unsigned int memhash(const void *buf, size_t len) |
| 30 | { |
| 31 | unsigned int hash = FNV32_BASE; |
| 32 | unsigned char *ucbuf = (unsigned char *) buf; |
| 33 | while (len--) { |
| 34 | unsigned int c = *ucbuf++; |
| 35 | hash = (hash * FNV32_PRIME) ^ c; |
| 36 | } |
| 37 | return hash; |
| 38 | } |
| 39 | |
| 40 | unsigned int memihash(const void *buf, size_t len) |
| 41 | { |
| 42 | unsigned int hash = FNV32_BASE; |
| 43 | unsigned char *ucbuf = (unsigned char *) buf; |
| 44 | while (len--) { |
| 45 | unsigned int c = *ucbuf++; |
| 46 | if (c >= 'a' && c <= 'z') |
| 47 | c -= 'a' - 'A'; |
| 48 | hash = (hash * FNV32_PRIME) ^ c; |
| 49 | } |
| 50 | return hash; |
| 51 | } |
| 52 | |
Jeff Hostetler | f75619b | 2017-03-22 17:14:21 +0000 | [diff] [blame] | 53 | /* |
Elijah Newren | 15beaaa | 2019-11-05 17:07:23 +0000 | [diff] [blame] | 54 | * Incorporate another chunk of data into a memihash |
Jeff Hostetler | f75619b | 2017-03-22 17:14:21 +0000 | [diff] [blame] | 55 | * computation. |
| 56 | */ |
| 57 | unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len) |
| 58 | { |
| 59 | unsigned int hash = hash_seed; |
| 60 | unsigned char *ucbuf = (unsigned char *) buf; |
| 61 | while (len--) { |
| 62 | unsigned int c = *ucbuf++; |
| 63 | if (c >= 'a' && c <= 'z') |
| 64 | c -= 'a' - 'A'; |
| 65 | hash = (hash * FNV32_PRIME) ^ c; |
| 66 | } |
| 67 | return hash; |
| 68 | } |
| 69 | |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 70 | #define HASHMAP_INITIAL_SIZE 64 |
| 71 | /* grow / shrink by 2^2 */ |
| 72 | #define HASHMAP_RESIZE_BITS 2 |
| 73 | /* load factor in percent */ |
| 74 | #define HASHMAP_LOAD_FACTOR 80 |
| 75 | |
| 76 | static void alloc_table(struct hashmap *map, unsigned int size) |
| 77 | { |
| 78 | map->tablesize = size; |
René Scharfe | ca56dad | 2021-03-13 17:17:22 +0100 | [diff] [blame] | 79 | CALLOC_ARRAY(map->table, size); |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 80 | |
| 81 | /* calculate resize thresholds for new size */ |
| 82 | map->grow_at = (unsigned int) ((uint64_t) size * HASHMAP_LOAD_FACTOR / 100); |
| 83 | if (size <= HASHMAP_INITIAL_SIZE) |
| 84 | map->shrink_at = 0; |
| 85 | else |
| 86 | /* |
| 87 | * The shrink-threshold must be slightly smaller than |
| 88 | * (grow-threshold / resize-factor) to prevent erratic resizing, |
| 89 | * thus we divide by (resize-factor + 1). |
| 90 | */ |
| 91 | map->shrink_at = map->grow_at / ((1 << HASHMAP_RESIZE_BITS) + 1); |
| 92 | } |
| 93 | |
| 94 | static inline int entry_equals(const struct hashmap *map, |
Elijah Newren | 97a39a4 | 2020-11-02 18:55:02 +0000 | [diff] [blame] | 95 | const struct hashmap_entry *e1, |
| 96 | const struct hashmap_entry *e2, |
| 97 | const void *keydata) |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 98 | { |
Stefan Beller | 7663cdc | 2017-06-30 12:14:05 -0700 | [diff] [blame] | 99 | return (e1 == e2) || |
| 100 | (e1->hash == e2->hash && |
| 101 | !map->cmpfn(map->cmpfn_data, e1, e2, keydata)); |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 102 | } |
| 103 | |
| 104 | static inline unsigned int bucket(const struct hashmap *map, |
Elijah Newren | 97a39a4 | 2020-11-02 18:55:02 +0000 | [diff] [blame] | 105 | const struct hashmap_entry *key) |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 106 | { |
| 107 | return key->hash & (map->tablesize - 1); |
| 108 | } |
| 109 | |
Jeff Hostetler | 0607e10 | 2017-03-22 17:14:22 +0000 | [diff] [blame] | 110 | int hashmap_bucket(const struct hashmap *map, unsigned int hash) |
| 111 | { |
| 112 | return hash & (map->tablesize - 1); |
| 113 | } |
| 114 | |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 115 | static void rehash(struct hashmap *map, unsigned int newsize) |
| 116 | { |
Elijah Newren | b7879b0 | 2020-11-02 18:55:03 +0000 | [diff] [blame] | 117 | /* map->table MUST NOT be NULL when this function is called */ |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 118 | unsigned int i, oldsize = map->tablesize; |
| 119 | struct hashmap_entry **oldtable = map->table; |
| 120 | |
| 121 | alloc_table(map, newsize); |
| 122 | for (i = 0; i < oldsize; i++) { |
| 123 | struct hashmap_entry *e = oldtable[i]; |
| 124 | while (e) { |
| 125 | struct hashmap_entry *next = e->next; |
| 126 | unsigned int b = bucket(map, e); |
| 127 | e->next = map->table[b]; |
| 128 | map->table[b] = e; |
| 129 | e = next; |
| 130 | } |
| 131 | } |
| 132 | free(oldtable); |
| 133 | } |
| 134 | |
| 135 | static inline struct hashmap_entry **find_entry_ptr(const struct hashmap *map, |
| 136 | const struct hashmap_entry *key, const void *keydata) |
| 137 | { |
Elijah Newren | b7879b0 | 2020-11-02 18:55:03 +0000 | [diff] [blame] | 138 | /* map->table MUST NOT be NULL when this function is called */ |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 139 | struct hashmap_entry **e = &map->table[bucket(map, key)]; |
| 140 | while (*e && !entry_equals(map, *e, key, keydata)) |
| 141 | e = &(*e)->next; |
| 142 | return e; |
| 143 | } |
| 144 | |
Stefan Beller | 7663cdc | 2017-06-30 12:14:05 -0700 | [diff] [blame] | 145 | static int always_equal(const void *unused_cmp_data, |
Eric Wong | 939af16 | 2019-10-06 23:30:37 +0000 | [diff] [blame] | 146 | const struct hashmap_entry *unused1, |
| 147 | const struct hashmap_entry *unused2, |
Stefan Beller | 7663cdc | 2017-06-30 12:14:05 -0700 | [diff] [blame] | 148 | const void *unused_keydata) |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 149 | { |
| 150 | return 0; |
| 151 | } |
| 152 | |
| 153 | void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, |
Elijah Newren | 97a39a4 | 2020-11-02 18:55:02 +0000 | [diff] [blame] | 154 | const void *cmpfn_data, size_t initial_size) |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 155 | { |
| 156 | unsigned int size = HASHMAP_INITIAL_SIZE; |
Jeff Hostetler | 0607e10 | 2017-03-22 17:14:22 +0000 | [diff] [blame] | 157 | |
| 158 | memset(map, 0, sizeof(*map)); |
| 159 | |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 160 | map->cmpfn = equals_function ? equals_function : always_equal; |
Stefan Beller | 7663cdc | 2017-06-30 12:14:05 -0700 | [diff] [blame] | 161 | map->cmpfn_data = cmpfn_data; |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 162 | |
| 163 | /* calculate initial table size and allocate the table */ |
| 164 | initial_size = (unsigned int) ((uint64_t) initial_size * 100 |
| 165 | / HASHMAP_LOAD_FACTOR); |
| 166 | while (initial_size > size) |
| 167 | size <<= HASHMAP_RESIZE_BITS; |
| 168 | alloc_table(map, size); |
Jeff Hostetler | 8b604d1 | 2017-09-06 15:43:48 +0000 | [diff] [blame] | 169 | |
| 170 | /* |
| 171 | * Keep track of the number of items in the map and |
| 172 | * allow the map to automatically grow as necessary. |
| 173 | */ |
| 174 | map->do_count_items = 1; |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 175 | } |
| 176 | |
Elijah Newren | 33f20d8 | 2020-11-02 18:55:04 +0000 | [diff] [blame] | 177 | static void free_individual_entries(struct hashmap *map, ssize_t entry_offset) |
| 178 | { |
| 179 | struct hashmap_iter iter; |
| 180 | struct hashmap_entry *e; |
| 181 | |
| 182 | hashmap_iter_init(map, &iter); |
| 183 | while ((e = hashmap_iter_next(&iter))) |
| 184 | /* |
| 185 | * like container_of, but using caller-calculated |
Elijah Newren | 6da1a25 | 2020-11-02 18:55:05 +0000 | [diff] [blame] | 186 | * offset (caller being hashmap_clear_and_free) |
Elijah Newren | 33f20d8 | 2020-11-02 18:55:04 +0000 | [diff] [blame] | 187 | */ |
| 188 | free((char *)e - entry_offset); |
| 189 | } |
| 190 | |
| 191 | void hashmap_partial_clear_(struct hashmap *map, ssize_t entry_offset) |
| 192 | { |
| 193 | if (!map || !map->table) |
| 194 | return; |
| 195 | if (entry_offset >= 0) /* called by hashmap_clear_entries */ |
| 196 | free_individual_entries(map, entry_offset); |
| 197 | memset(map->table, 0, map->tablesize * sizeof(struct hashmap_entry *)); |
| 198 | map->shrink_at = 0; |
| 199 | map->private_size = 0; |
| 200 | } |
| 201 | |
Elijah Newren | 6da1a25 | 2020-11-02 18:55:05 +0000 | [diff] [blame] | 202 | void hashmap_clear_(struct hashmap *map, ssize_t entry_offset) |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 203 | { |
| 204 | if (!map || !map->table) |
| 205 | return; |
Elijah Newren | 6da1a25 | 2020-11-02 18:55:05 +0000 | [diff] [blame] | 206 | if (entry_offset >= 0) /* called by hashmap_clear_and_free */ |
Elijah Newren | 33f20d8 | 2020-11-02 18:55:04 +0000 | [diff] [blame] | 207 | free_individual_entries(map, entry_offset); |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 208 | free(map->table); |
| 209 | memset(map, 0, sizeof(*map)); |
| 210 | } |
| 211 | |
Eric Wong | f23a465 | 2019-10-06 23:30:36 +0000 | [diff] [blame] | 212 | struct hashmap_entry *hashmap_get(const struct hashmap *map, |
| 213 | const struct hashmap_entry *key, |
| 214 | const void *keydata) |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 215 | { |
Elijah Newren | b7879b0 | 2020-11-02 18:55:03 +0000 | [diff] [blame] | 216 | if (!map->table) |
| 217 | return NULL; |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 218 | return *find_entry_ptr(map, key, keydata); |
| 219 | } |
| 220 | |
Eric Wong | 6bcbdfb | 2019-10-06 23:30:34 +0000 | [diff] [blame] | 221 | struct hashmap_entry *hashmap_get_next(const struct hashmap *map, |
Elijah Newren | 97a39a4 | 2020-11-02 18:55:02 +0000 | [diff] [blame] | 222 | const struct hashmap_entry *entry) |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 223 | { |
Eric Wong | f6eb6bd | 2019-10-06 23:30:28 +0000 | [diff] [blame] | 224 | struct hashmap_entry *e = entry->next; |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 225 | for (; e; e = e->next) |
| 226 | if (entry_equals(map, entry, e, NULL)) |
| 227 | return e; |
| 228 | return NULL; |
| 229 | } |
| 230 | |
Eric Wong | b94e5c1 | 2019-10-06 23:30:29 +0000 | [diff] [blame] | 231 | void hashmap_add(struct hashmap *map, struct hashmap_entry *entry) |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 232 | { |
Elijah Newren | b7879b0 | 2020-11-02 18:55:03 +0000 | [diff] [blame] | 233 | unsigned int b; |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 234 | |
Elijah Newren | b7879b0 | 2020-11-02 18:55:03 +0000 | [diff] [blame] | 235 | if (!map->table) |
| 236 | alloc_table(map, HASHMAP_INITIAL_SIZE); |
| 237 | |
| 238 | b = bucket(map, entry); |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 239 | /* add entry */ |
Eric Wong | b94e5c1 | 2019-10-06 23:30:29 +0000 | [diff] [blame] | 240 | entry->next = map->table[b]; |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 241 | map->table[b] = entry; |
| 242 | |
| 243 | /* fix size and rehash if appropriate */ |
Jeff Hostetler | 8b604d1 | 2017-09-06 15:43:48 +0000 | [diff] [blame] | 244 | if (map->do_count_items) { |
| 245 | map->private_size++; |
| 246 | if (map->private_size > map->grow_at) |
| 247 | rehash(map, map->tablesize << HASHMAP_RESIZE_BITS); |
| 248 | } |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 249 | } |
| 250 | |
Eric Wong | 8a973d0 | 2019-10-06 23:30:39 +0000 | [diff] [blame] | 251 | struct hashmap_entry *hashmap_remove(struct hashmap *map, |
Elijah Newren | 97a39a4 | 2020-11-02 18:55:02 +0000 | [diff] [blame] | 252 | const struct hashmap_entry *key, |
| 253 | const void *keydata) |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 254 | { |
| 255 | struct hashmap_entry *old; |
Elijah Newren | b7879b0 | 2020-11-02 18:55:03 +0000 | [diff] [blame] | 256 | struct hashmap_entry **e; |
| 257 | |
| 258 | if (!map->table) |
| 259 | return NULL; |
| 260 | e = find_entry_ptr(map, key, keydata); |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 261 | if (!*e) |
| 262 | return NULL; |
| 263 | |
| 264 | /* remove existing entry */ |
| 265 | old = *e; |
| 266 | *e = old->next; |
| 267 | old->next = NULL; |
| 268 | |
| 269 | /* fix size and rehash if appropriate */ |
Jeff Hostetler | 8b604d1 | 2017-09-06 15:43:48 +0000 | [diff] [blame] | 270 | if (map->do_count_items) { |
| 271 | map->private_size--; |
| 272 | if (map->private_size < map->shrink_at) |
| 273 | rehash(map, map->tablesize >> HASHMAP_RESIZE_BITS); |
| 274 | } |
| 275 | |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 276 | return old; |
| 277 | } |
| 278 | |
Eric Wong | 8a973d0 | 2019-10-06 23:30:39 +0000 | [diff] [blame] | 279 | struct hashmap_entry *hashmap_put(struct hashmap *map, |
Elijah Newren | 97a39a4 | 2020-11-02 18:55:02 +0000 | [diff] [blame] | 280 | struct hashmap_entry *entry) |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 281 | { |
| 282 | struct hashmap_entry *old = hashmap_remove(map, entry, NULL); |
| 283 | hashmap_add(map, entry); |
| 284 | return old; |
| 285 | } |
| 286 | |
| 287 | void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter) |
| 288 | { |
| 289 | iter->map = map; |
| 290 | iter->tablepos = 0; |
| 291 | iter->next = NULL; |
| 292 | } |
| 293 | |
Eric Wong | 87571c3 | 2019-10-06 23:30:38 +0000 | [diff] [blame] | 294 | struct hashmap_entry *hashmap_iter_next(struct hashmap_iter *iter) |
Karsten Blees | 6a364ce | 2013-11-14 20:17:54 +0100 | [diff] [blame] | 295 | { |
| 296 | struct hashmap_entry *current = iter->next; |
| 297 | for (;;) { |
| 298 | if (current) { |
| 299 | iter->next = current->next; |
| 300 | return current; |
| 301 | } |
| 302 | |
| 303 | if (iter->tablepos >= iter->map->tablesize) |
| 304 | return NULL; |
| 305 | |
| 306 | current = iter->map->table[iter->tablepos++]; |
| 307 | } |
| 308 | } |
Karsten Blees | 7b64d42 | 2014-07-03 00:22:54 +0200 | [diff] [blame] | 309 | |
| 310 | struct pool_entry { |
| 311 | struct hashmap_entry ent; |
| 312 | size_t len; |
| 313 | unsigned char data[FLEX_ARRAY]; |
| 314 | }; |
| 315 | |
Stefan Beller | 7663cdc | 2017-06-30 12:14:05 -0700 | [diff] [blame] | 316 | static int pool_entry_cmp(const void *unused_cmp_data, |
Eric Wong | 939af16 | 2019-10-06 23:30:37 +0000 | [diff] [blame] | 317 | const struct hashmap_entry *eptr, |
| 318 | const struct hashmap_entry *entry_or_key, |
| 319 | const void *keydata) |
Karsten Blees | 7b64d42 | 2014-07-03 00:22:54 +0200 | [diff] [blame] | 320 | { |
Eric Wong | 939af16 | 2019-10-06 23:30:37 +0000 | [diff] [blame] | 321 | const struct pool_entry *e1, *e2; |
| 322 | |
| 323 | e1 = container_of(eptr, const struct pool_entry, ent); |
| 324 | e2 = container_of(entry_or_key, const struct pool_entry, ent); |
| 325 | |
Karsten Blees | 7b64d42 | 2014-07-03 00:22:54 +0200 | [diff] [blame] | 326 | return e1->data != keydata && |
| 327 | (e1->len != e2->len || memcmp(e1->data, keydata, e1->len)); |
| 328 | } |
| 329 | |
| 330 | const void *memintern(const void *data, size_t len) |
| 331 | { |
| 332 | static struct hashmap map; |
| 333 | struct pool_entry key, *e; |
| 334 | |
| 335 | /* initialize string pool hashmap */ |
| 336 | if (!map.tablesize) |
Eric Wong | 939af16 | 2019-10-06 23:30:37 +0000 | [diff] [blame] | 337 | hashmap_init(&map, pool_entry_cmp, NULL, 0); |
Karsten Blees | 7b64d42 | 2014-07-03 00:22:54 +0200 | [diff] [blame] | 338 | |
| 339 | /* lookup interned string in pool */ |
Eric Wong | d22245a | 2019-10-06 23:30:27 +0000 | [diff] [blame] | 340 | hashmap_entry_init(&key.ent, memhash(data, len)); |
Karsten Blees | 7b64d42 | 2014-07-03 00:22:54 +0200 | [diff] [blame] | 341 | key.len = len; |
Eric Wong | 404ab78 | 2019-10-06 23:30:42 +0000 | [diff] [blame] | 342 | e = hashmap_get_entry(&map, &key, ent, data); |
Karsten Blees | 7b64d42 | 2014-07-03 00:22:54 +0200 | [diff] [blame] | 343 | if (!e) { |
| 344 | /* not found: create it */ |
Jeff King | 96ffc06 | 2016-02-22 17:44:32 -0500 | [diff] [blame] | 345 | FLEX_ALLOC_MEM(e, data, data, len); |
Eric Wong | d22245a | 2019-10-06 23:30:27 +0000 | [diff] [blame] | 346 | hashmap_entry_init(&e->ent, key.ent.hash); |
Karsten Blees | 7b64d42 | 2014-07-03 00:22:54 +0200 | [diff] [blame] | 347 | e->len = len; |
Eric Wong | b94e5c1 | 2019-10-06 23:30:29 +0000 | [diff] [blame] | 348 | hashmap_add(&map, &e->ent); |
Karsten Blees | 7b64d42 | 2014-07-03 00:22:54 +0200 | [diff] [blame] | 349 | } |
| 350 | return e->data; |
| 351 | } |