1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include "hashmap.h"
#include <stdlib.h>
#include <stdio.h>
#define DEFAULT_CAP 16
void hm_init (
struct hash_map* map,
hm_hash_fn hash_fn,
hm_eq_fn eq_fn,
hm_destroy_fn destroy_fn
) {
map->cap = DEFAULT_CAP;
map->entries = ccc_alloc(map->cap * sizeof(void*));
map->hash_fn = hash_fn;
map->eq_fn = eq_fn;
map->destroy_fn = destroy_fn;
}
void hm_destroy(struct hash_map* map) {
for (integral_t i = 0; i < map->cap; i++) {
if (map->entries[i] == NULL) continue;
if (map->destroy_fn != NULL) map->destroy_fn(map->entries[i]);
free(map->entries[i]);
}
free(map->entries);
}
void** hm_cell_r(const struct hash_map* map, const void* entry) {
integral_t idx0 = map->hash_fn(entry, map->cap), idx = idx0;
do {
if (map->entries[idx] == NULL || map->eq_fn(map->entries[idx], entry))
return &map->entries[idx];
} while ((idx = (idx + 1) % map->cap) != idx0);
return NULL;
}
static void rehash(struct hash_map* map) {
void** old_entries = map->entries;
integral_t old_cap = map->cap;
map->cap = (map->cap + 1) << 1;
map->entries = ccc_alloc(map->cap * sizeof(void*));
for (integral_t i = 0; i < old_cap; i++) {
if (old_entries[i] == NULL) continue;
void** cell = hm_cell_r(map, old_entries[i]);
if (cell == NULL) {
fprintf(stderr, "ccc: rehash failed, likely a bug\n");
exit(1);
}
*cell = old_entries[i];
}
free(old_entries);
}
void** hm_cell_w(struct hash_map* map, const void* entry) {
void** cell = hm_cell_r(map, entry);
while (cell == NULL) {
rehash(map);
cell = hm_cell_r(map, entry);
}
return cell;
}
|
