Thumbnail

rani/cscroll.git

Clone URL: https://git.buni.party/rani/cscroll.git

Info Tree Commits Branches Tags Show Grep

Viewing file on branch master

/ src hashmap.c
1#include <stdlib.h>
2#include <stdint.h>
3#include <string.h>
4
5#include "hashmap.h"
6
7#define HASHMAP_RESIZE_LEN 128
8#define HASHMAP_RESIZE_FACT 75 // percent full
9
10// FNV-1a
11static unsigned long hashs(const char * s) {
12 unsigned long hash = 2166136261UL;
13 int c;
14 while ((c = *s++)) {
15 hash *= 2166136261UL;
16 hash ^= c;
17 }
18 return hash;
19}
20
21
22static struct hashmap_bucket * new_bucket(void) {
23 struct hashmap_bucket * b = malloc(sizeof(struct hashmap_bucket));
24 b->entries = NULL;
25 b->last = NULL;
26 return b;
27}
28
29
30static struct hashmap_col_list * new_col_list(void) {
31 struct hashmap_col_list * cl = malloc(sizeof(struct hashmap_col_list));
32 cl->next = NULL;
33 cl->prev = NULL;
34 cl->hash = 0;
35 cl->key = NULL;
36 cl->val = NULL;
37 return cl;
38}
39
40
41static void destroy_col(struct hashmap_col_list * cl) {
42 free(cl->key);
43 free(cl);
44}
45
46
47static struct hashmap_col_list * append_col(struct hashmap_bucket * b) {
48 if (!b->entries) {
49 b->entries = new_col_list();
50 b->last = b->entries;
51 return b->entries;
52 }
53
54 b->last->next = new_col_list();
55 b->last->next->prev = b->last;
56 b->last = b->last->next;
57 return b->last;
58}
59
60
61static struct hashmap_bucket * hashmap_get_bucket(const hashmap * hm, const char * key) {
62 unsigned long hash = hashs(key);
63 size_t index = hash % hm->max;
64 return hm->buckets[index];
65}
66
67
68static struct hashmap_col_list * search_col_list(struct hashmap_bucket * b, const char * key) {
69 for (struct hashmap_col_list * cl = b->entries; cl; cl = cl->next) {
70 if (!strcmp(key, cl->key)) return cl;
71 }
72 return NULL;
73}
74
75
76hashmap * hashmap_new(void (*destroyer)(void*)) {
77 hashmap * hm = malloc(sizeof(hashmap));
78 hm->destroyer = destroyer;
79 hm->buckets = malloc(sizeof(struct hashmap_bucket*) * HASHMAP_RESIZE_LEN);
80 hm->len = 0;
81 hm->max = HASHMAP_RESIZE_LEN;
82
83 for (size_t i = 0; i < hm->max; i++) {
84 hm->buckets[i] = NULL;
85 }
86
87 return hm;
88}
89
90
91static void hashmap_resize(hashmap * hm) {
92 size_t nmax = hm->max * 2;
93 struct hashmap_bucket ** nb = malloc(sizeof(struct hashmap_bucket*) * nmax);
94
95 for (size_t i = 0; i < nmax; i++) {
96 nb[i] = NULL;
97 }
98
99 for (size_t i = 0; i < hm->max; i++) {
100 struct hashmap_bucket * ob = hm->buckets[i];
101 if (!ob || !ob->entries) continue;
102
103 for (struct hashmap_col_list * cl = ob->entries; cl;) {
104 struct hashmap_col_list * next = cl->next;
105
106 size_t nindex = cl->hash % nmax;
107 if (!nb[nindex]) {
108 nb[nindex] = new_bucket();
109 nb[nindex]->entries = cl;
110 nb[nindex]->last = cl;
111 cl->prev = NULL;
112 cl->next = NULL;
113 } else {
114 struct hashmap_col_list * last = nb[nindex]->last;
115 last->next = cl;
116 cl->next = NULL;
117 cl->prev = last;
118 nb[nindex]->last = cl;
119 }
120
121 cl = next;
122 }
123
124 free(ob);
125 }
126
127 free(hm->buckets);
128 hm->buckets = nb;
129 hm->max = nmax;
130}
131
132
133void hashmap_insert(hashmap * hm, char * key, void * val) {
134 if ((hm->len * 100) / hm->max >= HASHMAP_RESIZE_FACT) {
135 hashmap_resize(hm);
136 }
137
138 struct hashmap_col_list * cl = NULL;
139
140 unsigned long hash = hashs(key);
141 size_t index = hash % hm->max;
142 if (!hm->buckets[index]) {
143 hm->buckets[index] = new_bucket();
144 } else {
145 for (struct hashmap_col_list * l = hm->buckets[index]->entries; l; l = l->next) {
146 // overrite the old collision entry
147 if (!strcmp(l->key, key)) {
148 cl = l;
149 if (hm->destroyer) hm->destroyer(cl->val);
150 cl->val = val;
151 }
152 }
153 }
154
155 if (!cl) {
156 cl = append_col(hm->buckets[index]);
157 cl->hash = hash;
158 cl->key = strdup(key);
159 cl->val = val;
160
161 hm->len++;
162 }
163}
164
165
166void * hashmap_get(const hashmap * hm, const char * key) {
167 struct hashmap_bucket * b = hashmap_get_bucket(hm, key);
168 if (!b) return NULL;
169 struct hashmap_col_list * cl = search_col_list(b, key);
170 if (!cl) return NULL;
171 return cl->val;
172}
173
174
175void hashmap_remove(hashmap * hm, char * key) {
176 struct hashmap_bucket * b = hashmap_get_bucket(hm, key);
177 if (!b) return;
178
179 struct hashmap_col_list * cl = search_col_list(b, key);
180 if (!cl) return;
181
182 struct hashmap_col_list * prev = cl->prev;
183 struct hashmap_col_list * next = cl->next;
184
185 if (!prev) b->entries = next;
186 else prev->next = next;
187 if (next) next->prev = prev;
188
189 if (hm->destroyer) hm->destroyer(cl->val);
190 destroy_col(cl);
191}
192
193
194int hashmap_walk(hashmap * hm, hashmap_walk_state * state) {
195 for (size_t i = state->curbuck; i < hm->max; i++) {
196 struct hashmap_bucket * b = hm->buckets[i];
197 if (!b || !b->entries) continue;
198
199 if (!state->col) state->col = b->entries;
200 for (struct hashmap_col_list * cl = state->col; cl; cl = cl->next) {
201 state->col = cl->next;
202 state->curbuck = i;
203 if (!state->col) state->curbuck++;
204
205 state->key = cl->key;
206 state->val = cl->val;
207 return 1;
208 }
209 state->col = NULL;
210 }
211
212 return 0;
213}
214
215
216void hashmap_destroy(hashmap * hm) {
217 for (size_t i = 0; i < hm->max; i++) {
218 struct hashmap_bucket * b = hm->buckets[i];
219 if (!b) continue;
220
221 // free each collision in the bucket
222 for (struct hashmap_col_list * cl = b->entries; cl;) {
223 struct hashmap_col_list * next = cl->next;
224 if (hm->destroyer) hm->destroyer(cl->val);
225 destroy_col(cl);
226 cl = next;
227 }
228
229 free(b);
230 }
231
232 free(hm->buckets);
233 free(hm);
234}
235