Line data Source code
1 : #include "passgen/container/hashmap.h"
2 : #include "passgen/config.h"
3 : #include "passgen/util/siphash.h"
4 : #include <stdlib.h>
5 : #define UNUSED(x) (void) x
6 :
7 : static const size_t hashmap_sizes[] = {
8 : 3,
9 : 7,
10 : 17,
11 : 37,
12 : 79,
13 : 163,
14 : 331,
15 : 673,
16 : 1361,
17 : 2729,
18 : 5471,
19 : 10949,
20 : 21911,
21 : 43853,
22 : 87719,
23 : 175447,
24 : 350899,
25 : 701819,
26 : 0};
27 :
28 : struct siphash_keys {
29 : const char *first;
30 : const char *second;
31 : };
32 :
33 : static const struct siphash_keys utf8_keys = {
34 : .first = "someverylongpass",
35 : .second = "myotherverylongk",
36 : };
37 :
38 : static const struct siphash_keys utf32_keys = {
39 : .first = "someverylongpass",
40 : .second = "myotherverylongk",
41 : };
42 :
43 95 : void passgen_hashmap_init(
44 : passgen_hashmap *map,
45 : const passgen_hashmap_context *context) {
46 : // zero-out hashmap
47 95 : memset(map, 0, sizeof(*map));
48 :
49 : // set context or default to UTF-8 context
50 95 : if(context) {
51 89 : map->context = context;
52 : } else {
53 6 : map->context = &passgen_hashmap_context_utf8;
54 : }
55 :
56 : // initialize hashmap context
57 95 : map->context->init(map);
58 95 : }
59 :
60 19 : void passgen_hashmap_free(passgen_hashmap *map) {
61 : // deinitialize context
62 19 : map->context->fini(map);
63 :
64 : // deallocate data
65 19 : free(map->data);
66 :
67 : // set everything to zero
68 19 : PASSGEN_CLEAR(map);
69 19 : }
70 :
71 20 : void passgen_hashmap_realloc(passgen_hashmap *map, size_t capacity) {
72 : // save previous hashmap
73 20 : passgen_hashmap old = *map;
74 :
75 20 : map->data = calloc(capacity, sizeof(passgen_hashmap_entry));
76 20 : map->capacity = capacity;
77 20 : map->len = 0;
78 :
79 : // copy data over
80 87607 : for(size_t i = 0; i < old.capacity; i++) {
81 87587 : if(old.data[i].key) {
82 13997 : passgen_hashmap_insert(map, old.data[i].key, old.data[i].value);
83 : }
84 : }
85 :
86 20 : free(old.data);
87 20 : }
88 :
89 38651 : static inline size_t passgen_hashmap_position(
90 : const passgen_hashmap *map,
91 : const void *key,
92 : bool first) {
93 38651 : return map->context->hash(map, key, first) % map->capacity;
94 : }
95 :
96 1859 : static inline bool passgen_hashmap_move(passgen_hashmap *map, size_t pos) {
97 1859 : const void *key = map->data[pos].key;
98 1859 : bool first = passgen_hashmap_position(map, key, true) == pos;
99 1859 : size_t other_pos = passgen_hashmap_position(map, key, !first);
100 1859 : if(!map->data[other_pos].key) {
101 1568 : map->data[other_pos].key = map->data[pos].key;
102 1568 : map->data[other_pos].value = map->data[pos].value;
103 1568 : return true;
104 : }
105 291 : return false;
106 : }
107 :
108 15 : static inline size_t next_capacity(passgen_hashmap *map) {
109 : size_t i;
110 106 : for(i = 0; hashmap_sizes[i]; i++) {
111 106 : if(hashmap_sizes[i] >= map->capacity) {
112 15 : break;
113 : }
114 : }
115 15 : if(hashmap_sizes[i] && hashmap_sizes[i + 1]) {
116 15 : return hashmap_sizes[i + 1];
117 : } else {
118 0 : return 2 * map->capacity - 1;
119 : }
120 : }
121 :
122 : passgen_hashmap_entry
123 24023 : passgen_hashmap_insert(passgen_hashmap *map, const void *key, void *value) {
124 24023 : if(map->capacity == 0) {
125 5 : passgen_hashmap_realloc(map, hashmap_sizes[0]);
126 : }
127 :
128 : size_t hash;
129 :
130 24023 : hash = passgen_hashmap_position(map, key, true);
131 24023 : if(!map->data[hash].key) {
132 22211 : map->data[hash].key = key;
133 22211 : map->data[hash].value = value;
134 22211 : map->len += 1;
135 22211 : return (passgen_hashmap_entry){NULL, NULL};
136 : } else {
137 1812 : if(map->context->equal(map, map->data[hash].key, key)) {
138 0 : passgen_hashmap_entry entry = map->data[hash];
139 0 : map->data[hash].key = key;
140 0 : map->data[hash].value = value;
141 0 : return entry;
142 1812 : } else if(passgen_hashmap_move(map, hash)) {
143 1536 : map->data[hash].key = key;
144 1536 : map->data[hash].value = value;
145 1536 : map->len += 1;
146 1536 : return (passgen_hashmap_entry){NULL, NULL};
147 : }
148 : }
149 :
150 276 : hash = passgen_hashmap_position(map, key, false);
151 276 : if(!map->data[hash].key) {
152 229 : map->data[hash].key = key;
153 229 : map->data[hash].value = value;
154 229 : map->len += 1;
155 229 : return (passgen_hashmap_entry){NULL, NULL};
156 : } else {
157 47 : if(map->context->equal(map, map->data[hash].key, key)) {
158 0 : passgen_hashmap_entry entry = map->data[hash];
159 0 : map->data[hash].key = key;
160 0 : map->data[hash].value = value;
161 0 : return entry;
162 47 : } else if(passgen_hashmap_move(map, hash)) {
163 32 : map->data[hash].key = key;
164 32 : map->data[hash].value = value;
165 32 : map->len += 1;
166 32 : return (passgen_hashmap_entry){NULL, NULL};
167 : }
168 : }
169 :
170 15 : passgen_hashmap_realloc(map, next_capacity(map));
171 15 : return passgen_hashmap_insert(map, key, value);
172 : }
173 :
174 : passgen_hashmap_entry
175 2 : passgen_hashmap_remove(passgen_hashmap *map, const void *key) {
176 : size_t hash;
177 :
178 : // if this key exists
179 2 : hash = passgen_hashmap_position(map, key, true);
180 2 : if(map->data[hash].key) {
181 : // and it matches
182 2 : if(map->context->equal(map, map->data[hash].key, key)) {
183 1 : passgen_hashmap_entry entry = map->data[hash];
184 1 : map->data[hash].key = NULL;
185 1 : map->data[hash].value = NULL;
186 1 : map->len -= 1;
187 1 : return entry;
188 : }
189 : }
190 :
191 : // if this key exists
192 1 : hash = passgen_hashmap_position(map, key, false);
193 1 : if(map->data[hash].key) {
194 : // and it matches
195 1 : if(map->context->equal(map, map->data[hash].key, key)) {
196 1 : passgen_hashmap_entry entry = map->data[hash];
197 1 : map->data[hash].key = NULL;
198 1 : map->data[hash].value = NULL;
199 1 : map->len -= 1;
200 1 : return entry;
201 : }
202 : }
203 :
204 0 : return (passgen_hashmap_entry){NULL, NULL};
205 : }
206 :
207 : passgen_hashmap_entry *
208 10016 : passgen_hashmap_lookup(const passgen_hashmap *map, const void *key) {
209 : // make sure the hashmap is not empty
210 10016 : if(!map->data) {
211 1 : return NULL;
212 : }
213 :
214 : size_t hash;
215 :
216 : // lookup first possible location
217 10015 : hash = passgen_hashmap_position(map, key, true);
218 20026 : if(map->data[hash].key &&
219 10011 : map->context->equal(map, map->data[hash].key, key)) {
220 9399 : return &map->data[hash];
221 : }
222 :
223 : // lookup second possible location
224 616 : hash = passgen_hashmap_position(map, key, false);
225 1225 : if(map->data[hash].key &&
226 609 : map->context->equal(map, map->data[hash].key, key)) {
227 609 : return &map->data[hash];
228 : }
229 :
230 7 : return NULL;
231 : }
232 :
233 8 : int passgen_hashmap_foreach(
234 : const passgen_hashmap *map,
235 : void *user,
236 : int (*func)(void *user, passgen_hashmap_entry *entry)) {
237 8 : if(map->len) {
238 87730 : for(size_t i = 0; i < map->capacity; i++) {
239 87728 : if(map->data[i].key) {
240 10006 : int ret = func(user, &map->data[i]);
241 10006 : if(ret != 0) {
242 1 : return ret;
243 : }
244 : }
245 : }
246 : }
247 :
248 7 : return 0;
249 : }
250 :
251 93 : static void utf8_init(passgen_hashmap *map) {
252 93 : map->context_data = (void *) &utf8_keys;
253 93 : }
254 :
255 17 : static void utf8_fini(passgen_hashmap *map) {
256 17 : map->context_data = NULL;
257 17 : }
258 :
259 : static uint64_t
260 38650 : utf8_hash(const passgen_hashmap *map, const void *key, bool first) {
261 : UNUSED(map);
262 : uint64_t output;
263 38650 : const struct siphash_keys *keys = map->context_data;
264 38650 : const char *siphash_key = first ? keys->first : keys->second;
265 38650 : passgen_siphash(
266 : key,
267 : strlen(key),
268 : siphash_key,
269 : (uint8_t *) &output,
270 : sizeof(output));
271 38650 : return output;
272 : }
273 :
274 : static bool
275 12482 : utf8_equal(const passgen_hashmap *map, const void *lhs, const void *rhs) {
276 : UNUSED(map);
277 12482 : return strcmp(lhs, rhs) == 0;
278 : }
279 :
280 : const passgen_hashmap_context passgen_hashmap_context_utf8 = {
281 : .hash = utf8_hash,
282 : .equal = utf8_equal,
283 : .init = utf8_init,
284 : .fini = utf8_fini,
285 : };
286 :
287 21 : static size_t utf32_len(const void *data) {
288 : // cast void pointer to array of UTF-32 codepoints
289 21 : const int32_t *utf32 = data;
290 :
291 : // iterate over until we hit zero codepoint
292 21 : size_t len = 0;
293 117 : while(utf32[len]) {
294 96 : len++;
295 : }
296 :
297 21 : return len;
298 : }
299 :
300 : static uint64_t
301 9 : utf32_hash(const passgen_hashmap *map, const void *key, bool first) {
302 : UNUSED(map);
303 : uint64_t output;
304 9 : const struct siphash_keys *keys = map->context_data;
305 9 : const char *siphash_key = first ? keys->first : keys->second;
306 9 : passgen_siphash(
307 : key,
308 : utf32_len(key),
309 : siphash_key,
310 : (uint8_t *) &output,
311 : sizeof(output));
312 9 : return output;
313 : }
314 :
315 : static bool
316 6 : utf32_equal(const passgen_hashmap *map, const void *lhs, const void *rhs) {
317 : UNUSED(map);
318 : // compute lengths of lhs and rhs
319 6 : size_t rhs_len = utf32_len(rhs);
320 6 : size_t lhs_len = utf32_len(lhs);
321 :
322 : // if lengths are not the same, the keys cannot be equal
323 6 : if(rhs_len != lhs_len) {
324 1 : return false;
325 : }
326 :
327 : // compare lhs and rhs
328 5 : int ret = memcmp(lhs, rhs, rhs_len * sizeof(uint32_t));
329 :
330 : // return true if comparison was equal
331 5 : return ret == 0;
332 : }
333 :
334 2 : static void utf32_init(passgen_hashmap *map) {
335 2 : map->context_data = (void *) &utf32_keys;
336 2 : }
337 :
338 2 : static void utf32_fini(passgen_hashmap *map) {
339 2 : map->context_data = NULL;
340 2 : }
341 :
342 : const passgen_hashmap_context passgen_hashmap_context_utf32 = {
343 : .hash = utf32_hash,
344 : .equal = utf32_equal,
345 : .init = utf32_init,
346 : .fini = utf32_fini,
347 : };
348 :
349 10000 : int passgen_hashmap_entry_free(void *user, passgen_hashmap_entry *entry) {
350 : (void) user;
351 10000 : free((void *) entry->key);
352 10000 : free(entry->value);
353 10000 : PASSGEN_CLEAR(entry);
354 10000 : return 0;
355 : }
|
