blob: 11ca8f3c058e71744f17a89ff0b4589eec5e70e3 [file] [log] [blame]
Radek Krejci5aeea3a2018-09-05 13:29:36 +02001/**
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
25static int
26lydict_val_eq(void *val1_p, void *val2_p, int UNUSED(mod), void *cb_data)
27{
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020028 LY_CHECK_ARG_RET(NULL, val1_p, val2_p, cb_data, 0);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020029
30 const char *str1 = ((struct dict_rec *)val1_p)->value;
31 const char *str2 = ((struct dict_rec *)val2_p)->value;
32
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020033 LY_CHECK_ERR_RET(!str1, LOGARG(NULL, val1_p), 0);
34 LY_CHECK_ERR_RET(!str2, LOGARG(NULL, val2_p), 0);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020035
36 if (strncmp(str1, str2, *(size_t *)cb_data) == 0) {
37 return 1;
38 }
39
40 return 0;
41}
42
43void
44lydict_init(struct dict_table *dict)
45{
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020046 LY_CHECK_ARG_RET(NULL, dict,);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020047
48 dict->hash_tab = lyht_new(1024, sizeof(struct dict_rec), lydict_val_eq, NULL, 1);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020049 LY_CHECK_ERR_RET(!dict->hash_tab, LOGINT(NULL), );
Radek Krejci5aeea3a2018-09-05 13:29:36 +020050 pthread_mutex_init(&dict->lock, NULL);
51}
52
53void
54lydict_clean(struct dict_table *dict)
55{
56 unsigned int i;
57 struct dict_rec *dict_rec = NULL;
58 struct ht_rec *rec = NULL;
59
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020060 LY_CHECK_ARG_RET(NULL, dict,);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020061
62 for (i = 0; i < dict->hash_tab->size; i++) {
63 /* get ith record */
64 rec = (struct ht_rec *)&dict->hash_tab->recs[i * dict->hash_tab->rec_size];
65 if (rec->hits == 1) {
66 /*
67 * this should not happen, all records inserted into
68 * dictionary are supposed to be removed using lydict_remove()
69 * before calling lydict_clean()
70 */
71 dict_rec = (struct dict_rec *)rec->val;
72 LOGWRN(NULL, "String \"%s\" not freed from the dictionary, refcount %d", dict_rec->value, dict_rec->refcount);
73 /* if record wasn't removed before free string allocated for that record */
74#ifdef NDEBUG
75 free(dict_rec->value);
76#endif
77 }
78 }
79
80 /* free table and destroy mutex */
81 lyht_free(dict->hash_tab);
82 pthread_mutex_destroy(&dict->lock);
83}
84
85/*
Radek Krejci5aeea3a2018-09-05 13:29:36 +020086 * Usage:
87 * - init hash to 0
88 * - repeatedly call dict_hash_multi(), provide hash from the last call
89 * - call dict_hash_multi() with key_part = NULL to finish the hash
90 */
91uint32_t
92dict_hash_multi(uint32_t hash, const char *key_part, size_t len)
93{
94 uint32_t i;
95
96 if (key_part) {
97 for (i = 0; i < len; ++i) {
98 hash += key_part[i];
99 hash += (hash << 10);
100 hash ^= (hash >> 6);
101 }
102 } else {
103 hash += (hash << 3);
104 hash ^= (hash >> 11);
105 hash += (hash << 15);
106 }
107
108 return hash;
109}
110
Radek Krejcif2dc4c52018-11-08 09:04:13 +0100111/*
112 * Bob Jenkin's one-at-a-time hash
113 * http://www.burtleburtle.net/bob/hash/doobs.html
114 *
115 * Spooky hash is faster, but it works only for little endian architectures.
116 */
117uint32_t
118dict_hash(const char *key, size_t len)
119{
120 uint32_t hash;
121
122 hash = dict_hash_multi(0, key, len);
123 return dict_hash_multi(hash, NULL, len);
124}
125
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200126API void
127lydict_remove(struct ly_ctx *ctx, const char *value)
128{
129 size_t len;
130 int ret;
131 uint32_t hash;
132 struct dict_rec rec, *match = NULL;
133 char *val_p;
134
Michal Vasko0f6b3e22018-09-07 12:18:12 +0200135 if (!value) {
Michal Vasko0b3a4172018-09-07 12:20:18 +0200136 return;
Michal Vasko0f6b3e22018-09-07 12:18:12 +0200137 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200138
139 len = strlen(value);
140 hash = dict_hash(value, len);
141
142 /* create record for lyht_find call */
143 rec.value = (char *)value;
144 rec.refcount = 0;
145
146 pthread_mutex_lock(&ctx->dict.lock);
147 /* set len as data for compare callback */
148 lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
149 /* check if value is already inserted */
150 ret = lyht_find(ctx->dict.hash_tab, &rec, hash, (void **)&match);
151
152 if (ret == 0) {
153 LY_CHECK_ERR_GOTO(!match, LOGINT(ctx), finish);
154
155 /* if value is already in dictionary, decrement reference counter */
156 match->refcount--;
157 if (match->refcount == 0) {
158 /*
159 * remove record
160 * save pointer to stored string before lyht_remove to
161 * free it after it is removed from hash table
162 */
163 val_p = match->value;
164 ret = lyht_remove(ctx->dict.hash_tab, &rec, hash);
165 free(val_p);
166 LY_CHECK_ERR_GOTO(ret, LOGINT(ctx), finish);
167 }
168 }
169
170finish:
171 pthread_mutex_unlock(&ctx->dict.lock);
172}
173
174static char *
175dict_insert(struct ly_ctx *ctx, char *value, size_t len, int zerocopy)
176{
177 struct dict_rec *match = NULL, rec;
178 int ret = 0;
179 uint32_t hash;
180
181 hash = dict_hash(value, len);
182 /* set len as data for compare callback */
183 lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
184 /* create record for lyht_insert */
185 rec.value = value;
186 rec.refcount = 1;
187
188 LOGDBG(LY_LDGDICT, "inserting \"%s\"", rec.value);
189 ret = lyht_insert(ctx->dict.hash_tab, (void *)&rec, hash, (void **)&match);
Michal Vaskofcc96b92018-09-12 11:12:01 +0200190 if (ret == LY_EEXIST) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200191 match->refcount++;
192 if (zerocopy) {
193 free(value);
194 }
Michal Vaskofcc96b92018-09-12 11:12:01 +0200195 } else if (ret == LY_SUCCESS) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200196 if (!zerocopy) {
197 /*
198 * allocate string for new record
199 * record is already inserted in hash table
200 */
201 match->value = malloc(sizeof *match->value * (len + 1));
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200202 LY_CHECK_ERR_RET(!match->value, LOGMEM(ctx), NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200203 memcpy(match->value, value, len);
204 match->value[len] = '\0';
205 }
206 } else {
207 /* lyht_insert returned error */
208 LOGINT(ctx);
209 return NULL;
210 }
211
212 return match->value;
213}
214
215API const char *
216lydict_insert(struct ly_ctx *ctx, const char *value, size_t len)
217{
218 const char *result;
219
Radek Krejci0ae092d2018-09-20 16:43:19 +0200220 LY_CHECK_ARG_RET(ctx, ctx, value, NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200221
Radek Krejci0ae092d2018-09-20 16:43:19 +0200222 if (!len) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200223 len = strlen(value);
224 }
225
226 pthread_mutex_lock(&ctx->dict.lock);
227 result = dict_insert(ctx, (char *)value, len, 0);
228 pthread_mutex_unlock(&ctx->dict.lock);
229
230 return result;
231}
232
233API const char *
234lydict_insert_zc(struct ly_ctx *ctx, char *value)
235{
236 const char *result;
237
Radek Krejci0ae092d2018-09-20 16:43:19 +0200238 LY_CHECK_ARG_RET(ctx, ctx, value, NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200239
240 pthread_mutex_lock(&ctx->dict.lock);
241 result = dict_insert(ctx, value, strlen(value), 1);
242 pthread_mutex_unlock(&ctx->dict.lock);
243
244 return result;
245}
246
247static struct ht_rec *
248lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx)
249{
250 return (struct ht_rec *)&recs[idx * rec_size];
251}
252
253struct hash_table *
254lyht_new(uint32_t size, uint16_t val_size, values_equal_cb val_equal, void *cb_data, int resize)
255{
256 struct hash_table *ht;
257
258 /* check that 2^x == size (power of 2) */
259 assert(size && !(size & (size - 1)));
260 assert(val_equal && val_size);
261 assert(resize == 0 || resize == 1);
262
263 if (size < LYHT_MIN_SIZE) {
264 size = LYHT_MIN_SIZE;
265 }
266
267 ht = malloc(sizeof *ht);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200268 LY_CHECK_ERR_RET(!ht, LOGMEM(NULL), NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200269
270 ht->used = 0;
271 ht->size = size;
272 ht->val_equal = val_equal;
273 ht->cb_data = cb_data;
274 ht->resize = (uint16_t)resize;
275
276 ht->rec_size = (sizeof(struct ht_rec) - 1) + val_size;
277 /* allocate the records correctly */
278 ht->recs = calloc(size, ht->rec_size);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200279 LY_CHECK_ERR_RET(!ht->recs, free(ht); LOGMEM(NULL), NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200280
281 return ht;
282}
283
284values_equal_cb
285lyht_set_cb(struct hash_table *ht, values_equal_cb new_val_equal)
286{
287 values_equal_cb prev;
288
289 prev = ht->val_equal;
290 ht->val_equal = new_val_equal;
291 return prev;
292}
293
294void *
295lyht_set_cb_data(struct hash_table *ht, void *new_cb_data)
296{
297 void *prev;
298
299 prev = ht->cb_data;
300 ht->cb_data = new_cb_data;
301 return prev;
302}
303
304struct hash_table *
305lyht_dup(const struct hash_table *orig)
306{
307 struct hash_table *ht;
308
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200309 LY_CHECK_ARG_RET(NULL, orig, NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200310
311 ht = lyht_new(orig->size, orig->rec_size - (sizeof(struct ht_rec) - 1), orig->val_equal, orig->cb_data, orig->resize ? 1 : 0);
312 if (!ht) {
313 return NULL;
314 }
315
316 memcpy(ht->recs, orig->recs, orig->used * orig->rec_size);
317 ht->used = orig->used;
318 return ht;
319}
320
321void
322lyht_free(struct hash_table *ht)
323{
324 if (ht) {
325 free(ht->recs);
326 free(ht);
327 }
328}
329
330static LY_ERR
331lyht_resize(struct hash_table *ht, int enlarge)
332{
333 struct ht_rec *rec;
334 unsigned char *old_recs;
335 uint32_t i, old_size;
336 int ret;
337
338 old_recs = ht->recs;
339 old_size = ht->size;
340
341 if (enlarge) {
342 /* double the size */
343 ht->size <<= 1;
344 } else {
345 /* half the size */
346 ht->size >>= 1;
347 }
348
349 ht->recs = calloc(ht->size, ht->rec_size);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200350 LY_CHECK_ERR_RET(!ht->recs, LOGMEM(NULL); ht->recs = old_recs; ht->size = old_size, LY_EMEM);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200351
352 /* reset used, it will increase again */
353 ht->used = 0;
354
355 /* add all the old records into the new records array */
356 for (i = 0; i < old_size; ++i) {
357 rec = lyht_get_rec(old_recs, ht->rec_size, i);
358 if (rec->hits > 0) {
359 ret = lyht_insert(ht, rec->val, rec->hash, NULL);
360 assert(!ret);
361 (void)ret;
362 }
363 }
364
365 /* final touches */
366 free(old_recs);
367 return LY_SUCCESS;
368}
369
370/* return: 0 - hash found, returned its record,
371 * 1 - hash not found, returned the record where it would be inserted */
372static int
373lyht_find_first(struct hash_table *ht, uint32_t hash, struct ht_rec **rec_p)
374{
375 struct ht_rec *rec;
376 uint32_t i, idx;
377
378 if (rec_p) {
379 *rec_p = NULL;
380 }
381
382 idx = i = hash & (ht->size - 1);
383 rec = lyht_get_rec(ht->recs, ht->rec_size, idx);
384
385 /* skip through overflow and deleted records */
386 while ((rec->hits != 0) && ((rec->hits == -1) || ((rec->hash & (ht->size - 1)) != idx))) {
387 if ((rec->hits == -1) && rec_p && !(*rec_p)) {
388 /* remember this record for return */
389 *rec_p = rec;
390 }
391 i = (i + 1) % ht->size;
392 if (i == idx) {
393 /* we went through all the records (very unlikely, but possible when many records are invalid),
394 * just return not found */
395 assert(!rec_p || *rec_p);
396 return 1;
397 }
398 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
399 }
400 if (rec->hits == 0) {
401 /* we could not find the value */
402 if (rec_p && !*rec_p) {
403 *rec_p = rec;
404 }
405 return 1;
406 }
407
408 /* we have found a record with equal (shortened) hash */
409 if (rec_p) {
410 *rec_p = rec;
411 }
412 return 0;
413}
414
415/**
416 * @brief Search for the next collision.
417 *
418 * @param[in] ht Hash table to search in.
419 * @param[in,out] last Last returned collision record.
420 * @param[in] first First collision record (hits > 1).
421 * @return 0 when hash collision found, \p last points to this next collision,
422 * 1 when hash collision not found, \p last points to the record where it would be inserted.
423 */
424static int
425lyht_find_collision(struct hash_table *ht, struct ht_rec **last, struct ht_rec *first)
426{
427 struct ht_rec *empty = NULL;
428 uint32_t i, idx;
429
430 assert(last && *last);
431
432 idx = (*last)->hash & (ht->size - 1);
433 i = (((unsigned char *)*last) - ht->recs) / ht->rec_size;
434
435 do {
436 i = (i + 1) % ht->size;
437 *last = lyht_get_rec(ht->recs, ht->rec_size, i);
438 if (*last == first) {
439 /* we went through all the records (very unlikely, but possible when many records are invalid),
440 * just return an invalid record */
441 assert(empty);
442 *last = empty;
443 return 1;
444 }
445
446 if (((*last)->hits == -1) && !empty) {
447 empty = *last;
448 }
449 } while (((*last)->hits != 0) && (((*last)->hits == -1) || (((*last)->hash & (ht->size - 1)) != idx)));
450
451 if ((*last)->hits > 0) {
452 /* we found a collision */
453 assert((*last)->hits == 1);
454 return 0;
455 }
456
457 /* no next collision found, return the record where it would be inserted */
458 if (empty) {
459 *last = empty;
460 } /* else (*last)->hits == 0, it is already correct */
461 return 1;
462}
463
464int
465lyht_find(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
466{
467 struct ht_rec *rec, *crec;
468 uint32_t i, c;
469 int r;
470
471 if (lyht_find_first(ht, hash, &rec)) {
472 /* not found */
473 return 1;
474 }
475 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 0, ht->cb_data)) {
476 /* even the value matches */
477 if (match_p) {
478 *match_p = rec->val;
479 }
480 return 0;
481 }
482
483 /* some collisions, we need to go through them, too */
484 crec = rec;
485 c = rec->hits;
486 for (i = 1; i < c; ++i) {
487 r = lyht_find_collision(ht, &rec, crec);
488 assert(!r);
489 (void)r;
490
491 /* compare values */
492 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 0, ht->cb_data)) {
493 if (match_p) {
494 *match_p = rec->val;
495 }
496 return 0;
497 }
498 }
499
500 /* not found even in collisions */
501 return 1;
502}
503
504int
505lyht_find_next(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
506{
507 struct ht_rec *rec, *crec;
508 uint32_t i, c;
509 int r, found = 0;
510
511 if (lyht_find_first(ht, hash, &rec)) {
512 /* not found, cannot happen */
513 assert(0);
514 }
515
516 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
517 /* previously returned value */
518 found = 1;
519 }
520
521 if (rec->hits == 1) {
522 /* there are no more similar values */
523 assert(rec->hash == hash);
524 assert(found);
525 return 1;
526 }
527
528 /* go through collisions and find next one after the previous one */
529 crec = rec;
530 c = rec->hits;
531 for (i = 1; i < c; ++i) {
532 r = lyht_find_collision(ht, &rec, crec);
533 assert(!r);
534 (void)r;
535
536 if (rec->hash != hash) {
537 /* a normal collision, we are not interested in those */
538 continue;
539 }
540
541 if (found) {
542 /* next value with equal hash, found our value */
543 if (match_p) {
544 *match_p = rec->val;
545 }
546 return 0;
547 }
548
549 if (!ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
550 /* already returned value, skip */
551 continue;
552 }
553
554 /* this one was returned previously, continue looking */
555 found = 1;
556 }
557
558 /* the last equal value was already returned */
559 assert(found);
560 return 1;
561}
562
563LY_ERR
564lyht_insert_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash,
565 values_equal_cb resize_val_equal, void **match_p)
566{
567 struct ht_rec *rec, *crec = NULL;
568 int32_t i;
569 int r, ret;
570 values_equal_cb old_val_equal;
571
572 if (!lyht_find_first(ht, hash, &rec)) {
573 /* we found matching shortened hash */
574 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
575 /* even the value matches */
576 if (match_p) {
577 *match_p = (void *)&rec->val;
578 }
579 return LY_EEXIST;
580 }
581
582 /* some collisions, we need to go through them, too */
583 crec = rec;
584 for (i = 1; i < crec->hits; ++i) {
585 r = lyht_find_collision(ht, &rec, crec);
586 assert(!r);
587
588 /* compare values */
589 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
590 if (match_p) {
591 *match_p = (void *)&rec->val;
592 }
593 return LY_EEXIST;
594 }
595 }
596
597 /* value not found, get the record where it will be inserted */
598 r = lyht_find_collision(ht, &rec, crec);
599 assert(r);
600 }
601
602 /* insert it into the returned record */
603 assert(rec->hits < 1);
604 rec->hash = hash;
605 rec->hits = 1;
606 memcpy(&rec->val, val_p, ht->rec_size - (sizeof(struct ht_rec) - 1));
607 if (match_p) {
608 *match_p = (void *)&rec->val;
609 }
610
611 if (crec) {
612 /* there was a collision, increase hits */
613 if (crec->hits == INT32_MAX) {
614 LOGINT(NULL);
615 }
616 ++crec->hits;
617 }
618
619 /* check size & enlarge if needed */
620 ret = LY_SUCCESS;
621 ++ht->used;
622 if (ht->resize) {
623 r = (ht->used * 100) / ht->size;
624 if ((ht->resize == 1) && (r >= LYHT_FIRST_SHRINK_PERCENTAGE)) {
625 /* enable shrinking */
626 ht->resize = 2;
627 }
628 if ((ht->resize == 2) && (r >= LYHT_ENLARGE_PERCENTAGE)) {
629 if (resize_val_equal) {
630 old_val_equal = lyht_set_cb(ht, resize_val_equal);
631 }
632
633 /* enlarge */
634 ret = lyht_resize(ht, 1);
635 /* if hash_table was resized, we need to find new matching value */
636 if (ret == LY_SUCCESS && match_p) {
637 lyht_find(ht, val_p, hash, match_p);
638 }
639
640 if (resize_val_equal) {
641 lyht_set_cb(ht, old_val_equal);
642 }
643 }
644 }
645 return ret;
646}
647
Radek Krejci0ae092d2018-09-20 16:43:19 +0200648LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200649lyht_insert(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
650{
651 return lyht_insert_with_resize_cb(ht, val_p, hash, NULL, match_p);
652}
653
654LY_ERR
655lyht_remove(struct hash_table *ht, void *val_p, uint32_t hash)
656{
657 struct ht_rec *rec, *crec;
658 int32_t i;
659 int first_matched = 0, r, ret;
660
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200661 LY_CHECK_ERR_RET(lyht_find_first(ht, hash, &rec), LOGARG(NULL, hash), LY_EINVAL); /* hash not found */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200662
663 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
664 /* even the value matches */
665 first_matched = 1;
666 }
667
668 /* we always need to go through collisions */
669 crec = rec;
670 for (i = 1; i < crec->hits; ++i) {
671 r = lyht_find_collision(ht, &rec, crec);
672 assert(!r);
673
674 /* compare values */
675 if (!first_matched && (rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
676 break;
677 }
678 }
679
680 if (i < crec->hits) {
681 /* one of collisions matched, reduce collision count, remove the record */
682 assert(!first_matched);
683 --crec->hits;
684 rec->hits = -1;
685 } else if (first_matched) {
686 /* the first record matches */
687 if (crec != rec) {
688 /* ... so put the last collision in its place */
689 rec->hits = crec->hits - 1;
690 memcpy(crec, rec, ht->rec_size);
691 }
692 rec->hits = -1;
693 } else {
694 /* value not found even in collisions */
695 LOGINT(NULL);
696 return LY_EINT;
697 }
698
699 /* check size & shrink if needed */
700 ret = LY_SUCCESS;
701 --ht->used;
702 if (ht->resize == 2) {
703 r = (ht->used * 100) / ht->size;
704 if ((r < LYHT_SHRINK_PERCENTAGE) && (ht->size > LYHT_MIN_SIZE)) {
705 /* shrink */
706 ret = lyht_resize(ht, 0);
707 }
708 }
709
710 return ret;
711}