Line data Source code
1 : #define _POSIX_C_SOURCE 200809L
2 : #include <stdlib.h>
3 : #include <string.h>
4 : #include <inttypes.h>
5 : #include <math.h>
6 :
7 : #include <crater/hash.h>
8 :
9 : //these are the prime infimums of powers of two in the uint64_t range so which one to use can be calculated by a bit scan (__builtin_clzll() aka bsfq)
10 : uint64_t exp_primes[64] = {0UL, 3UL, 7UL, 13UL, 31UL, 61UL, 127UL, 251UL, 509UL, 1021UL, 2039UL, 4093UL, 8191UL, 16381UL, 32749UL, 65537UL, 131071UL, 262139UL, 524287UL, 1048573UL,
11 : 2097143UL, 4194301UL, 8388593UL, 16777213UL, 33554393UL, 67108859UL, 134217689UL, 268435399UL, 536870909UL, 1073741789UL, 2147483647UL, 4294967291UL, 8589934583UL, 17179869143UL,
12 : 34359738337UL, 68719476731UL, 137438953447UL, 274877906899UL, 549755813881UL, 1099511627689UL, 2199023255531UL, 4398046511093UL, 8796093022151UL, 17592186044399UL,
13 : 35184372088777UL, 70368744177643UL, 140737488355213UL, 281474976710597UL, 562949953421231UL, 1125899906842597UL, 2251799813685119UL, 4503599627370449UL, 9007199254740881UL,
14 : 18014398509481951UL, 36028797018963913UL, 72057594037927931UL, 144115188075855859UL, 288230376151711717UL, 576460752303423433UL, 1152921504606846883UL, 2305843009213693951UL,
15 : 4611686018427387847UL, 9223372036854775783UL, 18446744073709551557UL};
16 :
17 :
18 : const uint64_t cr8r_hash_u64_prime = 536870909;
19 :
20 : CR8R_ATTR_NO_SAN("unsigned-integer-overflow")
21 1358044 : uint64_t cr8r_default_hash_u64(const cr8r_base_ft *ft, const void *_a){
22 1358044 : uint64_t a = *(const uint64_t*)_a;
23 1358044 : unsigned __int128 prod = a*((unsigned __int128)cr8r_hash_u64_prime);
24 1358044 : return (uint64_t)(prod >> 64) ^ (uint64_t)prod;
25 : }
26 :
27 : CR8R_ATTR_NO_SAN("unsigned-integer-overflow")
28 2398 : uint64_t cr8r_default_hash(const cr8r_base_ft *ft, const void *_a){
29 2398 : const char *a = _a;
30 2398 : uint64_t h = 5381;
31 21582 : for(uint64_t i = 0; i < ft->size; ++i){
32 19184 : h = 31*h + a[i];
33 : }
34 2398 : return h;
35 : }
36 :
37 : CR8R_ATTR_NO_SAN("unsigned-integer-overflow")
38 93911 : uint64_t cr8r_default_hash_cstr(const cr8r_base_ft *ft, const void *_a){
39 93911 : const char *a = *(const char**)_a;
40 93911 : uint64_t h = 5381;
41 549289 : for(char c = *a; c; c = *++a){
42 455378 : h = 31*h + c;
43 : }
44 93911 : return h;
45 : }
46 :
47 1029731407 : int cr8r_default_cmp_u64(const cr8r_base_ft *ft, const void *_a, const void *_b){
48 1029731407 : uint64_t a = *(const uint64_t*)_a, b = *(const uint64_t*)_b;
49 1029731407 : if(a < b){
50 : return -1;
51 553537207 : }else if(a == b){
52 188575859 : return 0;
53 : }
54 : return 1;
55 : }
56 :
57 147 : int cr8r_default_cmp_i64(const cr8r_base_ft *ft, const void *_a, const void *_b){
58 147 : int64_t a = *(const int64_t*)_a, b = *(const int64_t*)_b;
59 147 : if(a < b){
60 : return -1;
61 50 : }else if(a == b){
62 7 : return 0;
63 : }
64 : return 1;
65 : }
66 :
67 6143 : int cr8r_default_cmp_u8(const cr8r_base_ft *ft, const void *_a, const void *_b){
68 6143 : uint8_t a = *(const uint8_t*)_a, b = *(const uint8_t*)_b;
69 6143 : if(a < b){
70 : return -1;
71 3145 : }else if(a == b){
72 480 : return 0;
73 : }
74 : return 1;
75 : }
76 :
77 838239 : int cr8r_default_cmp_cstr(const cr8r_base_ft *ft, const void *_a, const void *_b){
78 838239 : return strcmp(*(const char**)_a, *(const char**)_b);
79 : }
80 :
81 42232 : int cr8r_default_replace(cr8r_base_ft *ft, void *_a, void *_b){
82 42232 : memcpy(_a, _b, ft->size);
83 42232 : return 1;
84 : }
85 :
86 7051 : void cr8r_default_free(cr8r_base_ft *ft, void *_p){
87 7051 : free(*(void**)_p);
88 7051 : }
89 :
90 0 : void cr8r_default_copy_cstr(cr8r_base_ft *ft, void *dest, const void *src){
91 0 : *(char**)dest = strdup(*(const char**)src);
92 0 : }
93 :
94 : cr8r_hashtbl_ft cr8r_htft_u64_void = {
95 : .base = {
96 : .data = NULL,
97 : .size = sizeof(uint64_t)
98 : },
99 : .hash = cr8r_default_hash_u64,
100 : .cmp = cr8r_default_cmp_u64,
101 : .load_factor = .7
102 : };
103 :
104 : cr8r_hashtbl_ft cr8r_htft_cstr_u64 = {
105 : .base.data = NULL,
106 : .base.size = sizeof(cr8r_htent_cstr_u64),
107 : .hash = cr8r_default_hash_cstr,
108 : .cmp = cr8r_default_cmp_cstr,
109 : .load_factor = .5
110 : };
111 :
112 : cr8r_hashtbl_ft cr8r_htft_u64_u64 = {
113 : .base.data = NULL,
114 : .base.size = 2*sizeof(uint64_t),
115 : .hash = cr8r_default_hash_u64,
116 : .cmp = cr8r_default_cmp_u64,
117 : .load_factor = .7
118 : };
119 :
120 1 : bool cr8r_hash_ft_init(cr8r_hashtbl_ft *ft,
121 : void *data, uint64_t size,
122 : uint64_t (*hash)(const cr8r_base_ft*, const void*),
123 : int (*cmp)(const cr8r_base_ft*, const void*, const void*),
124 : int (*add)(cr8r_base_ft*, void*, void*),
125 : void (*del)(cr8r_base_ft*, void*)
126 : ){
127 1 : if(!hash || !cmp){
128 : return 0;
129 : }
130 1 : ft->base.data = data;
131 1 : ft->base.size = size;
132 1 : ft->hash = hash;
133 1 : ft->cmp = cmp;
134 1 : ft->add = add;
135 1 : ft->del = del;
136 1 : return 1;
137 : }
138 :
139 :
140 37 : int cr8r_hash_init(cr8r_hashtbl_t *self, const cr8r_hashtbl_ft *ft, uint64_t reserve){
141 37 : *self = (cr8r_hashtbl_t){};
142 37 : if(!reserve){
143 : return 1;
144 : }
145 37 : uint64_t i = 64 - __builtin_clzll(reserve - 1);
146 37 : self->len_a = exp_primes[i];
147 37 : self->table_a = calloc(ft->base.size, self->len_a);
148 37 : if(!self->table_a){
149 : return 0;
150 : }
151 37 : self->flags_a = calloc(sizeof(uint64_t), ((self->len_a - 1) >> 5) + 1);
152 37 : if(!self->flags_a){
153 0 : free(self->table_a);
154 0 : self->table_a = NULL;
155 0 : return 0;
156 : }
157 37 : self->cap = self->len_a*(long double)ft->load_factor;
158 37 : return 1;
159 : }
160 :
161 31909 : inline static uint64_t cr8r_hash_find_slot_re(cr8r_hashtbl_t *self, const cr8r_hashtbl_ft *ft, uint64_t a){
162 45493 : for(uint64_t j = 0, i; j < self->len_a; ++j){
163 45493 : i = (a + (j&1 ? j*j : self->len_a - j*j%self->len_a))%self->len_a;
164 45493 : uint64_t f = (self->flags_a[i >> 5] >> (i&0x1F))&0x100000001ULL;
165 45493 : if(!(f&0x100000000ULL)){
166 : return i;
167 : }
168 : }
169 : return ~0ULL;
170 : }
171 :
172 1368306 : inline static uint64_t cr8r_hash_find_slot_ap(cr8r_hashtbl_t *self, const cr8r_hashtbl_ft *ft, const void *key){
173 1368306 : uint64_t a = ft->hash(&ft->base,key) % self->len_a;
174 1471732 : for(uint64_t j = 0, i; j < self->len_a; ++j){
175 1471732 : i = (a + (j&1 ? j*j : self->len_a - j*j%self->len_a))%self->len_a;
176 1471732 : uint64_t f = (self->flags_a[i >> 5] >> (i&0x1F))&0x100000001ULL;
177 1471732 : if(!(f&0x100000000ULL && ft->cmp(&ft->base, key, self->table_a + i*ft->base.size))){
178 1368306 : return i;
179 : }
180 : }
181 : return ~0ULL;
182 : }
183 :
184 13 : inline static int cr8r_hash_ix_start(cr8r_hashtbl_t *self, const cr8r_hashtbl_ft *ft){
185 13 : uint64_t i = self->len_a ? 64 - __builtin_clzll(self->len_a - 1) : 1;
186 13 : uint64_t new_len = exp_primes[i];
187 13 : void *new_table = calloc(ft->base.size, new_len);
188 13 : if(!new_table){
189 : return 0;
190 : }
191 13 : uint64_t *new_flags = calloc(sizeof(uint64_t), ((new_len - 1) >> 5) + 1);
192 13 : if(!new_flags){
193 0 : free(new_table);
194 0 : return 0;
195 : }
196 13 : uint64_t new_cap = new_len*(double)ft->load_factor;
197 : //we currently have full entries and can fit new_cap before resizing. This means we must move full/(new_cap - full)
198 : //entries on average per insertion. Because full == cap + 1, new_cap == new_len*load_factor, cap == len_a*load_factor,
199 : //and new_len == len_a*growth_factor, full/(new_cap - full) ~~ cap/(new_cap - cap) ~~ len_a/(new_len - len_a)
200 : //~~ len_a/(len_a*growth_factor - len_a) ~~ 1/(growth_factor - 1). I picked the largest prime number before each power
201 : //of 2 so full/(new_cap - full) is very close to 1. It is always less than 2 so I might just use 2 instead of r
202 : #ifdef DEBUG
203 13 : if(self->table_b){
204 0 : abort();
205 : }
206 : #endif
207 13 : self->table_b = self->table_a;
208 13 : self->table_a = new_table;
209 13 : self->flags_b = self->flags_a;
210 13 : self->flags_a = new_flags;
211 13 : self->len_b = self->len_a;
212 13 : self->len_a = new_len;
213 13 : self->cap = new_cap;
214 13 : self->r = ceill((self->full + 1.)/(new_cap - self->full - 1.));
215 13 : self->i = 0;
216 13 : return 1;
217 : }
218 :
219 21012 : inline static void cr8r_hash_ix_move(cr8r_hashtbl_t *self, const cr8r_hashtbl_ft *ft, uint64_t n){
220 21012 : uint64_t b = self->i;
221 71178 : for(uint64_t a; b < self->len_b; ++b){
222 71167 : uint64_t f = (self->flags_b[b >> 5] >> (b&0x1F))&0x100000001ULL;
223 71167 : if(!(f&0x100000000ULL)){
224 39258 : continue;
225 : }
226 31909 : void *ent = self->table_b + b*ft->base.size;
227 31909 : a = ft->hash(&ft->base,ent) % self->len_a;
228 31909 : a = cr8r_hash_find_slot_re(self, ft, a);
229 31909 : memcpy(self->table_a + a*ft->base.size, ent, ft->base.size);
230 31909 : self->flags_b[b >> 5] |= 0x1ULL << (b&0x1F);
231 31909 : self->flags_b[b >> 5] &= ~(0x100000000ULL << (b&0x1F));
232 31909 : self->flags_a[a >> 5] |= 0x100000000ULL << (a&0x1F);
233 31909 : self->flags_a[a >> 5] &= ~(0x1ULL << (a&0x1F));
234 31909 : if(!--n){
235 : break;
236 : }
237 : }
238 21012 : self->i = b;
239 21012 : if(b == self->len_b){
240 11 : free(self->table_b);
241 11 : free(self->flags_b);
242 11 : self->table_b = NULL;
243 11 : self->flags_b = NULL;
244 11 : self->len_b = 0;
245 11 : self->i = 0;
246 : }
247 21012 : }
248 :
249 220326 : inline static uint64_t cr8r_hash_get_index(void *table, uint64_t *flags, uint64_t len, uint64_t a, const cr8r_hashtbl_ft *ft, const void *key){
250 220326 : a %= len;
251 323950 : for(uint64_t j = 0, i; j < len; ++j){
252 323950 : i = (a + (j&1 ? j*j : len - j*j%len))%len;
253 323950 : uint64_t f = (flags[i >> 5] >> (i&0x1F))&0x100000001ULL;
254 323950 : if(!f){
255 : return ~0ULL;
256 : }
257 282738 : if(f&0x100000000ULL && !ft->cmp(&ft->base, key, table + i*ft->base.size)){
258 : return i;
259 : }
260 : }
261 : return ~0ULL;
262 : }
263 :
264 175967 : inline static void *cr8r_hash_get_single_a(cr8r_hashtbl_t *self, uint64_t i, const cr8r_hashtbl_ft *ft, const void *key){
265 175967 : uint64_t a = cr8r_hash_get_index(self->table_a, self->flags_a, self->len_a, i, ft, key);
266 175967 : return (~a) ? self->table_a + a*ft->base.size : NULL;
267 : }
268 :
269 43564 : inline static void *cr8r_hash_get_single_b(cr8r_hashtbl_t *self, uint64_t i, const cr8r_hashtbl_ft *ft, const void *key){
270 43564 : uint64_t b = cr8r_hash_get_index(self->table_b, self->flags_b, self->len_b, i, ft, key);
271 43564 : return (~b) ? self->table_b + b*ft->base.size : NULL;
272 : }
273 :
274 29114 : inline static void *cr8r_hash_get_split(cr8r_hashtbl_t *self, const cr8r_hashtbl_ft *ft, const void *key){
275 29114 : uint64_t i = ft->hash(&ft->base,key);
276 29114 : if(self->i << 1 < self->len_b){
277 27508 : return cr8r_hash_get_single_a(self, i, ft, key) ?: cr8r_hash_get_single_b(self, i, ft, key);
278 : }
279 1606 : return cr8r_hash_get_single_b(self, i, ft, key) ?: cr8r_hash_get_single_a(self, i, ft, key);
280 : }
281 :
282 175967 : void *cr8r_hash_get(cr8r_hashtbl_t *self, const cr8r_hashtbl_ft *ft, const void *key){
283 175967 : if(!self->table_a){
284 : return NULL;
285 : }
286 175967 : return self->table_b ? cr8r_hash_get_split(self, ft, key) : cr8r_hash_get_single_a(self, ft->hash(&ft->base,key), ft, key);
287 : }
288 :
289 155928 : void *cr8r_hash_insert(cr8r_hashtbl_t *self, const cr8r_hashtbl_ft *ft, const void *key, int *_status){
290 155928 : void *ret = NULL;
291 155928 : int status = 0;
292 155928 : if(self->full == self->cap){
293 7 : if(!cr8r_hash_ix_start(self, ft)){
294 0 : if(_status){
295 0 : *_status = 0;
296 : }
297 0 : return NULL;
298 : }
299 : }
300 155928 : if(self->table_b){
301 15260 : cr8r_hash_ix_move(self, ft, self->r);
302 15260 : if(self->table_b){
303 15255 : if(cr8r_hash_get_single_b(self, ft->hash(&ft->base,key), ft, key)){
304 0 : if(_status){
305 0 : *_status = 2;
306 : }
307 0 : return NULL;
308 : }
309 : }
310 : }
311 155928 : uint64_t i = cr8r_hash_find_slot_ap(self, ft, key);
312 155928 : if(!~i){
313 0 : if(_status){
314 0 : *_status = 0;
315 : }
316 0 : return NULL;
317 : }
318 155928 : if((self->flags_a[i >> 5] >> (i&0x1F))&0x100000000ULL){
319 : status = 2;
320 : }else{
321 121409 : ret = self->table_a + i*ft->base.size;
322 121409 : memcpy(ret, key, ft->base.size);
323 121409 : self->flags_a[i >> 5] |= 0x100000000ULL << (i&0x1F);
324 121409 : self->flags_a[i >> 5] &= ~(0x1ULL << (i&0x1F));
325 121409 : ++self->full;
326 121409 : status = 1;
327 : }
328 155928 : if(_status){
329 51013 : *_status = status;
330 : }
331 : return ret;
332 : }
333 :
334 1214903 : void *cr8r_hash_append(cr8r_hashtbl_t *self, cr8r_hashtbl_ft *ft, void *key, int *_status){
335 1214903 : void *ret = NULL;
336 1214903 : int status = 0;
337 1214903 : if(self->full == self->cap){
338 6 : if(!cr8r_hash_ix_start(self, ft)){
339 0 : if(_status){
340 0 : *_status = 0;
341 : }
342 0 : return NULL;
343 : }
344 : }
345 1214903 : if(self->table_b){
346 5752 : cr8r_hash_ix_move(self, ft, self->r);
347 5752 : if(self->table_b){
348 5746 : if((ret = cr8r_hash_get_single_b(self, ft->hash(&ft->base,key), ft, key))){
349 2525 : status = ft->add(&ft->base,ret, key) ? 2 : 0;
350 2525 : if(_status){
351 2525 : *_status = status;
352 : }
353 2525 : return ret;
354 : }
355 : }
356 : }
357 1212378 : uint64_t i = cr8r_hash_find_slot_ap(self, ft, key);
358 1212378 : if(!~i){
359 0 : if(_status){
360 0 : *_status = 0;
361 : }
362 0 : return NULL;
363 : }
364 1212378 : ret = self->table_a + i*ft->base.size;
365 1212378 : if((self->flags_a[i >> 5] >> (i&0x1F))&0x100000000ULL){
366 108058 : status = ft->add(&ft->base,ret, key) ? 2 : 0;
367 : }else{
368 1104320 : memcpy(ret, key, ft->base.size);
369 1104320 : self->flags_a[i >> 5] |= 0x100000000ULL << (i&0x1F);
370 1104320 : self->flags_a[i >> 5] &= ~(0x1ULL << (i&0x1F));
371 1104320 : ++self->full;
372 1104320 : status = 1;
373 : }
374 1212378 : if(_status){
375 72803 : *_status = status;
376 : }
377 : return ret;
378 : }
379 :
380 788 : inline static int cr8r_hash_remove_single_a(cr8r_hashtbl_t *self, uint64_t i, cr8r_hashtbl_ft *ft, const void *key){
381 788 : uint64_t a = cr8r_hash_get_index(self->table_a, self->flags_a, self->len_a, i, ft, key);
382 788 : if(!~a){
383 : return 0;
384 : }
385 711 : self->flags_a[a >> 5] ^= 0x100000001ULL << (a&0x1F);
386 711 : --self->full;
387 711 : if(ft->del){
388 0 : ft->del(&ft->base, self->table_a + a*ft->base.size);
389 : }
390 : return 1;
391 : }
392 :
393 7 : inline static int cr8r_hash_remove_single_b(cr8r_hashtbl_t *self, uint64_t i, cr8r_hashtbl_ft *ft, const void *key){
394 7 : uint64_t b = cr8r_hash_get_index(self->table_b, self->flags_b, self->len_b, i, ft, key);
395 7 : if(!~b){
396 : return 0;
397 : }
398 7 : self->flags_b[b >> 5] ^= 0x100000001ULL << (b&0x1F);
399 7 : --self->full;
400 7 : if(ft->del){
401 0 : ft->del(&ft->base, self->table_b + b*ft->base.size);
402 : }
403 : return 1;
404 : }
405 :
406 7 : inline static int cr8r_hash_remove_split(cr8r_hashtbl_t *self, cr8r_hashtbl_ft *ft, const void *key){
407 7 : uint64_t i = ft->hash(&ft->base,key);
408 7 : if(self->i << 1 < self->len_b){
409 5 : return cr8r_hash_remove_single_a(self, i, ft, key) ?: cr8r_hash_remove_single_b(self, i, ft, key);
410 : }
411 2 : return cr8r_hash_remove_single_b(self, i, ft, key) ?: cr8r_hash_remove_single_a(self, i, ft, key);
412 : }
413 :
414 790 : int cr8r_hash_remove(cr8r_hashtbl_t *self, cr8r_hashtbl_ft *ft, const void *key){
415 790 : if(!self->table_a){
416 : return 0;
417 : }
418 790 : return self->table_b ? cr8r_hash_remove_split(self, ft, key) : cr8r_hash_remove_single_a(self, ft->hash(&ft->base,key), ft, key);
419 : }
420 :
421 1976 : void cr8r_hash_delete(cr8r_hashtbl_t *self, cr8r_hashtbl_ft *ft, void *ent){
422 1976 : if(self->table_a <= ent && ent < self->table_a + self->len_a*ft->base.size){
423 1975 : uint64_t i = (ent - self->table_a)/ft->base.size;
424 1975 : self->flags_a[i >> 5] ^= 0x100000001ULL << (i&0x1F);
425 : }else{
426 1 : uint64_t i = (ent - self->table_b)/ft->base.size;
427 1 : self->flags_b[i >> 5] ^= 0x100000001ULL << (i&0x1F);
428 : }
429 1976 : --self->full;
430 1976 : if(ft->del){
431 0 : ft->del(&ft->base,ent);
432 : }
433 1976 : }
434 :
435 33 : void cr8r_hash_clear(cr8r_hashtbl_t *self, cr8r_hashtbl_ft *ft){
436 33 : if(ft->del){
437 81920 : for(uint64_t a = 0; a < self->len_a; ++a){
438 81918 : uint64_t f = (self->flags_a[a >> 5] >> (a&0x1F))&0x100000001ULL;
439 81918 : if(f&0x100000000ULL){
440 14777 : ft->del(&ft->base, self->table_a + a*ft->base.size);
441 : }
442 : }
443 2 : for(uint64_t b = 0; b < self->len_b; ++b){
444 0 : uint64_t f = (self->flags_b[b >> 5] >> (b&0x1F))&0x100000001ULL;
445 0 : if(f&0x100000000ULL){
446 0 : ft->del(&ft->base, self->table_b + b*ft->base.size);
447 : }
448 : }
449 : }
450 33 : free(self->table_b);
451 33 : self->table_b = NULL;
452 33 : free(self->flags_b);
453 33 : self->flags_b = NULL;
454 33 : self->len_b = 0;
455 33 : memset(self->flags_a, 0, (((self->len_a - 1) >> 5) + 1)*sizeof(uint64_t));
456 33 : self->full = 0;
457 33 : }
458 :
459 33 : void cr8r_hash_destroy(cr8r_hashtbl_t *self, cr8r_hashtbl_ft *ft){
460 33 : cr8r_hash_clear(self, ft);
461 33 : free(self->table_a);
462 33 : self->table_a = NULL;
463 33 : free(self->flags_a);
464 33 : self->flags_a = NULL;
465 33 : self->len_a = 0;
466 33 : self->cap = 0;
467 33 : }
468 :
|
