1 /**
2 * @file hash_table.c
3 * @author Radek Krejci <rkrejci@cesnet.cz>
4 * @brief libyang dictionary for storing strings and generic hash table
5 *
6 * Copyright (c) 2015 - 2018 CESNET, z.s.p.o.
7 *
8 * This source code is licensed under BSD 3-Clause License (the "License").
9 * You may not use this file except in compliance with the License.
10 * You may obtain a copy of the License at
11 *
12 * https://opensource.org/licenses/BSD-3-Clause
13 */
14
15 #include <string.h>
16 #include <stdint.h>
17 #include <stdlib.h>
18 #include <pthread.h>
19 #include <assert.h>
20
21 #include "common.h"
22 #include "context.h"
23 #include "hash_table.h"
24
25 static int
lydict_val_eq(void * val1_p,void * val2_p,int UNUSED (mod),void * cb_data)26 lydict_val_eq(void *val1_p, void *val2_p, int UNUSED(mod), void *cb_data)
27 {
28 if (!val1_p || !val2_p) {
29 LOGARG;
30 return 0;
31 }
32
33 const char *str1 = ((struct dict_rec *)val1_p)->value;
34 const char *str2 = ((struct dict_rec *)val2_p)->value;
35
36 if (!str1 || !str2 || !cb_data) {
37 LOGARG;
38 return 0;
39 }
40
41 if (strncmp(str1, str2, *(size_t *)cb_data) == 0) {
42 return 1;
43 }
44
45 return 0;
46 }
47
48 void
lydict_init(struct dict_table * dict)49 lydict_init(struct dict_table *dict)
50 {
51 if (!dict) {
52 LOGARG;
53 return;
54 }
55
56 dict->hash_tab = lyht_new(1024, sizeof(struct dict_rec), lydict_val_eq, NULL, 1);
57 LY_CHECK_ERR_RETURN(!dict->hash_tab, LOGINT(NULL), );
58 pthread_mutex_init(&dict->lock, NULL);
59 }
60
61 void
lydict_clean(struct dict_table * dict)62 lydict_clean(struct dict_table *dict)
63 {
64 unsigned int i;
65 struct dict_rec *dict_rec = NULL;
66 struct ht_rec *rec = NULL;
67
68 if (!dict) {
69 LOGARG;
70 return;
71 }
72
73 for (i = 0; i < dict->hash_tab->size; i++) {
74 /* get ith record */
75 rec = (struct ht_rec *)&dict->hash_tab->recs[i * dict->hash_tab->rec_size];
76 if (rec->hits == 1) {
77 /*
78 * this should not happen, all records inserted into
79 * dictionary are supposed to be removed using lydict_remove()
80 * before calling lydict_clean()
81 */
82 dict_rec = (struct dict_rec *)rec->val;
83 LOGWRN(NULL, "String \"%s\" not freed from the dictionary, refcount %d", dict_rec->value, dict_rec->refcount);
84 /* if record wasn't removed before free string allocated for that record */
85 #ifdef NDEBUG
86 free(dict_rec->value);
87 #endif
88 }
89 }
90
91 /* free table and destroy mutex */
92 lyht_free(dict->hash_tab);
93 pthread_mutex_destroy(&dict->lock);
94 }
95
96 /*
97 * Bob Jenkin's one-at-a-time hash
98 * http://www.burtleburtle.net/bob/hash/doobs.html
99 *
100 * Spooky hash is faster, but it works only for little endian architectures.
101 */
102 static uint32_t
dict_hash(const char * key,size_t len)103 dict_hash(const char *key, size_t len)
104 {
105 uint32_t hash, i;
106
107 for (hash = i = 0; i < len; ++i) {
108 hash += key[i];
109 hash += (hash << 10);
110 hash ^= (hash >> 6);
111 }
112 hash += (hash << 3);
113 hash ^= (hash >> 11);
114 hash += (hash << 15);
115 return hash;
116 }
117
118 /*
119 * Usage:
120 * - init hash to 0
121 * - repeatedly call dict_hash_multi(), provide hash from the last call
122 * - call dict_hash_multi() with key_part = NULL to finish the hash
123 */
124 uint32_t
dict_hash_multi(uint32_t hash,const char * key_part,size_t len)125 dict_hash_multi(uint32_t hash, const char *key_part, size_t len)
126 {
127 uint32_t i;
128
129 if (key_part) {
130 for (i = 0; i < len; ++i) {
131 hash += key_part[i];
132 hash += (hash << 10);
133 hash ^= (hash >> 6);
134 }
135 } else {
136 hash += (hash << 3);
137 hash ^= (hash >> 11);
138 hash += (hash << 15);
139 }
140
141 return hash;
142 }
143
144 static int
lydict_resize_val_eq(void * val1_p,void * val2_p,int mod,void * cb_data)145 lydict_resize_val_eq(void *val1_p, void *val2_p, int mod, void *cb_data)
146 {
147 if (!val1_p || !val2_p) {
148 LOGARG;
149 return 0;
150 }
151
152 const char *str1 = ((struct dict_rec *)val1_p)->value;
153 const char *str2 = ((struct dict_rec *)val2_p)->value;
154
155 if (!str1 || !str2) {
156 LOGARG;
157 return 0;
158 }
159
160 if (mod) {
161 /* used when inserting new values */
162 if (strcmp(str1, str2) == 0) {
163 return 1;
164 }
165 } else {
166 /* used when finding the original value again in the resized table */
167 return lydict_val_eq(val1_p, val2_p, mod, cb_data);
168 }
169
170 return 0;
171 }
172
173 API void
lydict_remove(struct ly_ctx * ctx,const char * value)174 lydict_remove(struct ly_ctx *ctx, const char *value)
175 {
176 FUN_IN;
177
178 size_t len;
179 int ret;
180 uint32_t hash;
181 struct dict_rec rec, *match = NULL;
182 char *val_p;
183
184 if (!value || !ctx) {
185 return;
186 }
187
188 len = strlen(value);
189 hash = dict_hash(value, len);
190
191 /* create record for lyht_find call */
192 rec.value = (char *)value;
193 rec.refcount = 0;
194
195 pthread_mutex_lock(&ctx->dict.lock);
196 /* set len as data for compare callback */
197 lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
198 /* check if value is already inserted */
199 ret = lyht_find(ctx->dict.hash_tab, &rec, hash, (void **)&match);
200
201 if (ret == 0) {
202 LY_CHECK_ERR_GOTO(!match, LOGINT(ctx), finish);
203
204 /* if value is already in dictionary, decrement reference counter */
205 match->refcount--;
206 if (match->refcount == 0) {
207 /*
208 * remove record
209 * save pointer to stored string before lyht_remove to
210 * free it after it is removed from hash table
211 */
212 val_p = match->value;
213 ret = lyht_remove_with_resize_cb(ctx->dict.hash_tab, &rec, hash, lydict_resize_val_eq);
214 free(val_p);
215 LY_CHECK_ERR_GOTO(ret, LOGINT(ctx), finish);
216 }
217 }
218
219 finish:
220 pthread_mutex_unlock(&ctx->dict.lock);
221 }
222
223 static char *
dict_insert(struct ly_ctx * ctx,char * value,size_t len,int zerocopy)224 dict_insert(struct ly_ctx *ctx, char *value, size_t len, int zerocopy)
225 {
226 struct dict_rec *match = NULL, rec;
227 int ret = 0;
228 uint32_t hash;
229
230 hash = dict_hash(value, len);
231 /* set len as data for compare callback */
232 lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
233 /* create record for lyht_insert */
234 rec.value = value;
235 rec.refcount = 1;
236
237 LOGDBG(LY_LDGDICT, "inserting \"%s\"", rec.value);
238 ret = lyht_insert_with_resize_cb(ctx->dict.hash_tab, (void *)&rec, hash, lydict_resize_val_eq, (void **)&match);
239 if (ret == 1) {
240 match->refcount++;
241 if (zerocopy) {
242 free(value);
243 }
244 } else if (ret == 0) {
245 if (!zerocopy) {
246 /*
247 * allocate string for new record
248 * record is already inserted in hash table
249 */
250 match->value = malloc(sizeof *match->value * (len + 1));
251 LY_CHECK_ERR_RETURN(!match->value, LOGMEM(ctx), NULL);
252 memcpy(match->value, value, len);
253 match->value[len] = '\0';
254 }
255 } else {
256 /* lyht_insert returned error */
257 LOGINT(ctx);
258 return NULL;
259 }
260
261 return match->value;
262 }
263
264 API const char *
lydict_insert(struct ly_ctx * ctx,const char * value,size_t len)265 lydict_insert(struct ly_ctx *ctx, const char *value, size_t len)
266 {
267 FUN_IN;
268
269 const char *result;
270
271 if (!value) {
272 return NULL;
273 }
274
275 if (!len) {
276 len = strlen(value);
277 }
278
279 pthread_mutex_lock(&ctx->dict.lock);
280 result = dict_insert(ctx, (char *)value, len, 0);
281 pthread_mutex_unlock(&ctx->dict.lock);
282
283 return result;
284 }
285
286 API const char *
lydict_insert_zc(struct ly_ctx * ctx,char * value)287 lydict_insert_zc(struct ly_ctx *ctx, char *value)
288 {
289 FUN_IN;
290
291 const char *result;
292
293 if (!value) {
294 return NULL;
295 }
296
297 pthread_mutex_lock(&ctx->dict.lock);
298 result = dict_insert(ctx, value, strlen(value), 1);
299 pthread_mutex_unlock(&ctx->dict.lock);
300
301 return result;
302 }
303
304 struct ht_rec *
lyht_get_rec(unsigned char * recs,uint16_t rec_size,uint32_t idx)305 lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx)
306 {
307 return (struct ht_rec *)&recs[idx * rec_size];
308 }
309
310 struct hash_table *
lyht_new(uint32_t size,uint16_t val_size,values_equal_cb val_equal,void * cb_data,int resize)311 lyht_new(uint32_t size, uint16_t val_size, values_equal_cb val_equal, void *cb_data, int resize)
312 {
313 struct hash_table *ht;
314
315 /* check that 2^x == size (power of 2) */
316 assert(size && !(size & (size - 1)));
317 assert(val_equal && val_size);
318 assert(resize == 0 || resize == 1);
319
320 if (size < LYHT_MIN_SIZE) {
321 size = LYHT_MIN_SIZE;
322 }
323
324 ht = malloc(sizeof *ht);
325 LY_CHECK_ERR_RETURN(!ht, LOGMEM(NULL), NULL);
326
327 ht->used = 0;
328 ht->size = size;
329 ht->invalid = 0;
330 ht->val_equal = val_equal;
331 ht->cb_data = cb_data;
332 ht->resize = (uint16_t)resize;
333
334 ht->rec_size = (sizeof(struct ht_rec) - 1) + val_size;
335 /* allocate the records correctly */
336 ht->recs = calloc(size, ht->rec_size);
337 LY_CHECK_ERR_RETURN(!ht->recs, free(ht); LOGMEM(NULL), NULL);
338
339 return ht;
340 }
341
342 values_equal_cb
lyht_set_cb(struct hash_table * ht,values_equal_cb new_val_equal)343 lyht_set_cb(struct hash_table *ht, values_equal_cb new_val_equal)
344 {
345 values_equal_cb prev;
346
347 prev = ht->val_equal;
348 ht->val_equal = new_val_equal;
349 return prev;
350 }
351
352 void *
lyht_set_cb_data(struct hash_table * ht,void * new_cb_data)353 lyht_set_cb_data(struct hash_table *ht, void *new_cb_data)
354 {
355 void *prev;
356
357 prev = ht->cb_data;
358 ht->cb_data = new_cb_data;
359 return prev;
360 }
361
362 struct hash_table *
lyht_dup(const struct hash_table * orig)363 lyht_dup(const struct hash_table *orig)
364 {
365 struct hash_table *ht;
366
367 if (!orig) {
368 return NULL;
369 }
370
371 ht = lyht_new(orig->size, orig->rec_size - (sizeof(struct ht_rec) - 1), orig->val_equal, orig->cb_data, orig->resize ? 1 : 0);
372 if (!ht) {
373 return NULL;
374 }
375
376 memcpy(ht->recs, orig->recs, (size_t)orig->used * (size_t)orig->rec_size);
377 ht->used = orig->used;
378 ht->invalid = orig->invalid;
379 return ht;
380 }
381
382 void
lyht_free(struct hash_table * ht)383 lyht_free(struct hash_table *ht)
384 {
385 if (ht) {
386 free(ht->recs);
387 free(ht);
388 }
389 }
390
391 static int
lyht_resize(struct hash_table * ht,int enlarge)392 lyht_resize(struct hash_table *ht, int enlarge)
393 {
394 struct ht_rec *rec;
395 unsigned char *old_recs;
396 uint32_t i, old_size;
397 int ret;
398
399 old_recs = ht->recs;
400 old_size = ht->size;
401
402 if (enlarge > 0) {
403 /* double the size */
404 ht->size <<= 1;
405 } else if (enlarge < 0) {
406 /* half the size */
407 ht->size >>= 1;
408 }
409
410 ht->recs = calloc(ht->size, ht->rec_size);
411 LY_CHECK_ERR_RETURN(!ht->recs, LOGMEM(NULL); ht->recs = old_recs; ht->size = old_size, -1);
412
413 /* reset used, it will increase again */
414 ht->used = 0;
415 /* reset invalid, it will increase agein */
416 ht->invalid = 0;
417
418 /* add all the old records into the new records array */
419 for (i = 0; i < old_size; ++i) {
420 rec = lyht_get_rec(old_recs, ht->rec_size, i);
421 if (rec->hits > 0) {
422 ret = lyht_insert(ht, rec->val, rec->hash, NULL);
423 assert(!ret);
424 (void)ret;
425 }
426 }
427
428 /* final touches */
429 free(old_recs);
430 return 0;
431 }
432
433 /* return: 0 - hash found, returned its record,
434 * 1 - hash not found, returned the record where it would be inserted */
435 static int
lyht_find_first(struct hash_table * ht,uint32_t hash,struct ht_rec ** rec_p)436 lyht_find_first(struct hash_table *ht, uint32_t hash, struct ht_rec **rec_p)
437 {
438 struct ht_rec *rec, *inval_rec = NULL;
439 uint32_t i, idx;
440
441 if (rec_p) {
442 *rec_p = NULL;
443 }
444
445 idx = i = hash & (ht->size - 1);
446 rec = lyht_get_rec(ht->recs, ht->rec_size, idx);
447
448 /* skip through overflow and deleted records */
449 while ((rec->hits != 0) && ((rec->hits == -1) || ((rec->hash & (ht->size - 1)) != idx))) {
450 if ((rec->hits == -1) && !inval_rec) {
451 /* remember the first invalid record we found while searching for this hash */
452 inval_rec = rec;
453 }
454 i = (i + 1) % ht->size;
455 if (i == idx) {
456 /* we went through all the records (very unlikely, but possible when many records are invalid),
457 * just return not found */
458 assert(inval_rec);
459 if (rec_p) {
460 *rec_p = inval_rec;
461 }
462 return 1;
463 }
464 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
465 }
466
467 if (rec->hits == 0) {
468 /* we could not find the value */
469 if (rec_p) {
470 /* return the first empty (or invalid) record found */
471 *rec_p = inval_rec ? inval_rec : rec;
472 }
473 return 1;
474 }
475
476 /* we have found a record with equal (shortened) hash,
477 * move it to the first invalid record so that the next search is faster */
478 if (inval_rec) {
479 memcpy(inval_rec, rec, ht->rec_size);
480 rec->hits = -1;
481 rec = inval_rec;
482 }
483 if (rec_p) {
484 *rec_p = rec;
485 }
486 return 0;
487 }
488
489 /**
490 * @brief Search for the next collision.
491 *
492 * @param[in] ht Hash table to search in.
493 * @param[in,out] last Last returned collision record.
494 * @param[in] first First collision record (hits > 1).
495 * @return 0 when hash collision found, \p last points to this next collision,
496 * 1 when hash collision not found, \p last points to the record where it would be inserted.
497 */
498 static int
lyht_find_collision(struct hash_table * ht,struct ht_rec ** last,struct ht_rec * first)499 lyht_find_collision(struct hash_table *ht, struct ht_rec **last, struct ht_rec *first)
500 {
501 struct ht_rec *inval_rec = NULL;
502 uint32_t i, idx;
503
504 assert(last && *last);
505
506 idx = (*last)->hash & (ht->size - 1);
507 i = (((unsigned char *)*last) - ht->recs) / ht->rec_size;
508
509 do {
510 i = (i + 1) % ht->size;
511 *last = lyht_get_rec(ht->recs, ht->rec_size, i);
512 if (*last == first) {
513 /* we went through all the records (very unlikely, but possible when many records are invalid),
514 * just return an invalid record */
515 assert(inval_rec);
516 *last = inval_rec;
517 return 1;
518 }
519
520 if (((*last)->hits == -1) && !inval_rec) {
521 inval_rec = *last;
522 }
523 } while (((*last)->hits != 0) && (((*last)->hits == -1) || (((*last)->hash & (ht->size - 1)) != idx)));
524
525 if ((*last)->hits > 0) {
526 /* we found a collision, so move it to the first invalid record so the next search is faster */
527 assert((*last)->hits == 1);
528 if (inval_rec) {
529 memcpy(inval_rec, *last, ht->rec_size);
530 (*last)->hits = -1;
531 *last = inval_rec;
532 }
533 return 0;
534 }
535
536 /* no next collision found, return the record where it would be inserted */
537 if (inval_rec) {
538 *last = inval_rec;
539 } /* else (*last)->hits == 0, it is already correct */
540 return 1;
541 }
542
543 int
lyht_find(struct hash_table * ht,void * val_p,uint32_t hash,void ** match_p)544 lyht_find(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
545 {
546 struct ht_rec *rec, *crec;
547 uint32_t i, c;
548 int r;
549
550 if (lyht_find_first(ht, hash, &rec)) {
551 /* not found */
552 return 1;
553 }
554 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 0, ht->cb_data)) {
555 /* even the value matches */
556 if (match_p) {
557 *match_p = rec->val;
558 }
559 return 0;
560 }
561
562 /* some collisions, we need to go through them, too */
563 crec = rec;
564 c = rec->hits;
565 for (i = 1; i < c; ++i) {
566 r = lyht_find_collision(ht, &rec, crec);
567 assert(!r);
568 (void)r;
569
570 /* compare values */
571 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 0, ht->cb_data)) {
572 if (match_p) {
573 *match_p = rec->val;
574 }
575 return 0;
576 }
577 }
578
579 /* not found even in collisions */
580 return 1;
581 }
582
583 int
lyht_find_next(struct hash_table * ht,void * val_p,uint32_t hash,void ** match_p)584 lyht_find_next(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
585 {
586 struct ht_rec *rec, *crec;
587 uint32_t i, c;
588 int r, found = 0;
589
590 if (lyht_find_first(ht, hash, &rec)) {
591 /* not found, cannot happen */
592 assert(0);
593 }
594
595 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
596 /* previously returned value */
597 found = 1;
598 }
599
600 if (rec->hits == 1) {
601 /* there are no more similar values */
602 assert(rec->hash == hash);
603 assert(found);
604 return 1;
605 }
606
607 /* go through collisions and find next one after the previous one */
608 crec = rec;
609 c = rec->hits;
610 for (i = 1; i < c; ++i) {
611 r = lyht_find_collision(ht, &rec, crec);
612 assert(!r);
613 (void)r;
614
615 if (rec->hash != hash) {
616 /* a normal collision, we are not interested in those */
617 continue;
618 }
619
620 if (found) {
621 /* next value with equal hash, found our value */
622 if (match_p) {
623 *match_p = rec->val;
624 }
625 return 0;
626 }
627
628 if (!ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
629 /* already returned value, skip */
630 continue;
631 }
632
633 /* this one was returned previously, continue looking */
634 found = 1;
635 }
636
637 /* the last equal value was already returned */
638 assert(found);
639 return 1;
640 }
641
642 #ifndef NDEBUG
643
644 /* prints little-endian numbers, will also work on big-endian just the values will look weird */
645 static char *
lyht_dbgprint_val2str(void * val_p,int32_t hits,uint16_t rec_size)646 lyht_dbgprint_val2str(void *val_p, int32_t hits, uint16_t rec_size)
647 {
648 char *val;
649 int32_t i, j, val_size;
650
651 val_size = rec_size - (sizeof(struct ht_rec) - 1);
652
653 val = malloc(val_size * 2 + 1);
654 for (i = 0, j = val_size - 1; i < val_size; ++i, --j) {
655 if (hits > 0) {
656 sprintf(val + i * 2, "%02x", *(((uint8_t *)val_p) + j));
657 } else {
658 sprintf(val + i * 2, " ");
659 }
660 }
661
662 return val;
663 }
664
665 #endif
666
667 static void
lyht_dbgprint_ht(struct hash_table * ht,const char * info)668 lyht_dbgprint_ht(struct hash_table *ht, const char *info)
669 {
670 #ifndef NDEBUG
671 struct ht_rec *rec;
672 uint32_t i, i_len;
673 char *val;
674
675 if ((LY_LLDBG > ly_log_level) || !(ly_log_dbg_groups & LY_LDGHASH)) {
676 return;
677 }
678
679 LOGDBG(LY_LDGHASH, "");
680 LOGDBG(LY_LDGHASH, "hash table %s (used %u, size %u):", info, ht->used, ht->size);
681
682 val = malloc(11);
683 sprintf(val, "%u", ht->size);
684 i_len = strlen(val);
685 free(val);
686
687 for (i = 0; i < ht->size; ++i) {
688 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
689 val = lyht_dbgprint_val2str(&rec->val, rec->hits, ht->rec_size);
690 if (rec->hits > 0) {
691 LOGDBG(LY_LDGHASH, "[%*u] val %s hash %10u %% %*u hits %2d",
692 (int)i_len, i, val, rec->hash, (int)i_len, rec->hash & (ht->size - 1), rec->hits);
693 } else {
694 LOGDBG(LY_LDGHASH, "[%*u] val %s hash %10s %% %*s hits %2d",
695 (int)i_len, i, val, "", (int)i_len, "", rec->hits);
696 }
697 free(val);
698 }
699 LOGDBG(LY_LDGHASH, "");
700 #else
701 (void)ht;
702 (void)info;
703 #endif
704 }
705
706 static void
lyht_dbgprint_value(void * val_p,uint32_t hash,uint16_t rec_size,const char * operation)707 lyht_dbgprint_value(void *val_p, uint32_t hash, uint16_t rec_size, const char *operation)
708 {
709 #ifndef NDEBUG
710 if ((LY_LLDBG > ly_log_level) || !(ly_log_dbg_groups & LY_LDGHASH)) {
711 return;
712 }
713
714 char *val = lyht_dbgprint_val2str(val_p, 1, rec_size);
715 LOGDBG(LY_LDGHASH, "%s value %s with hash %u", operation, val, hash);
716 free(val);
717 #else
718 (void)val_p;
719 (void)hash;
720 (void)rec_size;
721 (void)operation;
722 #endif
723 }
724
725 int
lyht_insert_with_resize_cb(struct hash_table * ht,void * val_p,uint32_t hash,values_equal_cb resize_val_equal,void ** match_p)726 lyht_insert_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash,
727 values_equal_cb resize_val_equal, void **match_p)
728 {
729 struct ht_rec *rec, *crec = NULL;
730 int32_t i;
731 int r, ret;
732 values_equal_cb old_val_equal;
733
734 lyht_dbgprint_ht(ht, "before");
735 lyht_dbgprint_value(val_p, hash, ht->rec_size, "inserting");
736
737 if (!lyht_find_first(ht, hash, &rec)) {
738 /* we found matching shortened hash */
739 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
740 /* even the value matches */
741 if (match_p) {
742 *match_p = (void *)&rec->val;
743 }
744 return 1;
745 }
746
747 /* some collisions, we need to go through them, too */
748 crec = rec;
749 for (i = 1; i < crec->hits; ++i) {
750 r = lyht_find_collision(ht, &rec, crec);
751 assert(!r);
752
753 /* compare values */
754 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
755 if (match_p) {
756 *match_p = (void *)&rec->val;
757 }
758 return 1;
759 }
760 }
761
762 /* value not found, get the record where it will be inserted */
763 r = lyht_find_collision(ht, &rec, crec);
764 assert(r);
765 }
766
767 /* insert it into the returned record */
768 assert(rec->hits < 1);
769 if (rec->hits < 0) {
770 --ht->invalid;
771 }
772 rec->hash = hash;
773 rec->hits = 1;
774 memcpy(&rec->val, val_p, ht->rec_size - (sizeof(struct ht_rec) - 1));
775 if (match_p) {
776 *match_p = (void *)&rec->val;
777 }
778
779 if (crec) {
780 /* there was a collision, increase hits */
781 if (crec->hits == INT32_MAX) {
782 LOGINT(NULL);
783 }
784 ++crec->hits;
785 }
786
787 /* check size & enlarge if needed */
788 ret = 0;
789 ++ht->used;
790 if (ht->resize) {
791 r = (ht->used * 100) / ht->size;
792 if ((ht->resize == 1) && (r >= LYHT_FIRST_SHRINK_PERCENTAGE)) {
793 /* enable shrinking */
794 ht->resize = 2;
795 }
796 if ((ht->resize == 2) && (r >= LYHT_ENLARGE_PERCENTAGE)) {
797 if (resize_val_equal) {
798 old_val_equal = lyht_set_cb(ht, resize_val_equal);
799 }
800
801 /* enlarge */
802 ret = lyht_resize(ht, 1);
803 /* if hash_table was resized, we need to find new matching value */
804 if (ret == 0 && match_p) {
805 lyht_find(ht, val_p, hash, match_p);
806 }
807
808 if (resize_val_equal) {
809 lyht_set_cb(ht, old_val_equal);
810 }
811 }
812 }
813
814 lyht_dbgprint_ht(ht, "after");
815 return ret;
816 }
817
818 int
lyht_insert(struct hash_table * ht,void * val_p,uint32_t hash,void ** match_p)819 lyht_insert(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
820 {
821 return lyht_insert_with_resize_cb(ht, val_p, hash, NULL, match_p);
822 }
823
824 int
lyht_remove_with_resize_cb(struct hash_table * ht,void * val_p,uint32_t hash,values_equal_cb resize_val_equal)825 lyht_remove_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash, values_equal_cb resize_val_equal)
826 {
827 struct ht_rec *rec, *crec;
828 int32_t i;
829 int first_matched = 0, r, ret;
830 values_equal_cb old_val_equal;
831
832 lyht_dbgprint_ht(ht, "before");
833 lyht_dbgprint_value(val_p, hash, ht->rec_size, "removing");
834
835 if (lyht_find_first(ht, hash, &rec)) {
836 /* hash not found */
837 LOGDBG(LY_LDGHASH, "remove failed");
838 return 1;
839 }
840 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
841 /* even the value matches */
842 first_matched = 1;
843 }
844
845 /* we always need to go through collisions */
846 crec = rec;
847 for (i = 1; i < crec->hits; ++i) {
848 r = lyht_find_collision(ht, &rec, crec);
849 assert(!r);
850
851 /* compare values */
852 if (!first_matched && (rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
853 break;
854 }
855 }
856
857 if (i < crec->hits) {
858 /* one of collisions matched, reduce collision count, remove the record */
859 assert(!first_matched);
860 --crec->hits;
861 rec->hits = -1;
862 } else if (first_matched) {
863 /* the first record matches */
864 if (crec != rec) {
865 /* ... and there are some collisions so put the last collision in its place keeping the correct collision count */
866 rec->hits = crec->hits - 1;
867 memcpy(crec, rec, ht->rec_size);
868 }
869
870 /* this matching record was removed and is not valid anymore */
871 rec->hits = -1;
872 } else {
873 /* value not found even in collisions */
874 assert(!first_matched);
875 LOGDBG(LY_LDGHASH, "remove failed");
876 return 1;
877 }
878
879 /* check size & shrink if needed */
880 ret = 0;
881 --ht->used;
882 ++ht->invalid;
883 if (ht->resize == 2) {
884 r = (ht->used * 100) / ht->size;
885 if ((r < LYHT_SHRINK_PERCENTAGE) && (ht->size > LYHT_MIN_SIZE)) {
886 if (resize_val_equal) {
887 old_val_equal = lyht_set_cb(ht, resize_val_equal);
888 }
889
890 /* shrink */
891 ret = lyht_resize(ht, -1);
892
893 if (resize_val_equal) {
894 lyht_set_cb(ht, old_val_equal);
895 }
896 }
897 }
898
899 r = ((ht->size - ht->used - ht->invalid) * 100) / ht->size;
900 if (r < LYHT_REHASH_PERCENTAGE) {
901 if (resize_val_equal) {
902 old_val_equal = lyht_set_cb(ht, resize_val_equal);
903 }
904
905 /* rehash */
906 ret = lyht_resize(ht, 0);
907
908 if (resize_val_equal) {
909 lyht_set_cb(ht, old_val_equal);
910 }
911 }
912
913 lyht_dbgprint_ht(ht, "after");
914 return ret;
915 }
916
917 int
lyht_remove(struct hash_table * ht,void * val_p,uint32_t hash)918 lyht_remove(struct hash_table *ht, void *val_p, uint32_t hash)
919 {
920 return lyht_remove_with_resize_cb(ht, val_p, hash, NULL);
921 }
922