blob: 90915f0cd3623d57b4016de93e71fbb1a5ecf761 [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
Radek Krejci535ea9f2020-05-29 16:01:05 +020015#include "hash_table.h"
Radek Krejcie7b95092019-05-15 11:03:07 +020016
Michal Vasko69730152020-10-09 16:30:07 +020017#include <assert.h>
18#include <pthread.h>
Radek Krejci5aeea3a2018-09-05 13:29:36 +020019#include <stdint.h>
20#include <stdlib.h>
Michal Vasko69730152020-10-09 16:30:07 +020021#include <string.h>
Radek Krejci5aeea3a2018-09-05 13:29:36 +020022
Radek Krejci535ea9f2020-05-29 16:01:05 +020023#include "common.h"
Michal Vasko69730152020-10-09 16:30:07 +020024#include "compat.h"
Radek Krejci535ea9f2020-05-29 16:01:05 +020025#include "dict.h"
Radek Krejci857189e2020-09-01 13:26:36 +020026#include "log.h"
Radek Krejci5aeea3a2018-09-05 13:29:36 +020027
Radek Krejcif13b87b2020-12-01 22:02:17 +010028#define LYDICT_MIN_SIZE 1024
29
Radek Krejci857189e2020-09-01 13:26:36 +020030/**
31 * @brief Comparison callback for dictionary's hash table
32 *
Michal Vasko62524a92021-02-26 10:08:50 +010033 * Implementation of ::lyht_value_equal_cb.
Radek Krejci857189e2020-09-01 13:26:36 +020034 */
35static ly_bool
36lydict_val_eq(void *val1_p, void *val2_p, ly_bool UNUSED(mod), void *cb_data)
Radek Krejci5aeea3a2018-09-05 13:29:36 +020037{
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020038 LY_CHECK_ARG_RET(NULL, val1_p, val2_p, cb_data, 0);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020039
Michal Vasko8efac242023-03-30 08:24:56 +020040 const char *str1 = ((struct ly_dict_rec *)val1_p)->value;
41 const char *str2 = ((struct ly_dict_rec *)val2_p)->value;
Radek Krejci5aeea3a2018-09-05 13:29:36 +020042
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020043 LY_CHECK_ERR_RET(!str1, LOGARG(NULL, val1_p), 0);
44 LY_CHECK_ERR_RET(!str2, LOGARG(NULL, val2_p), 0);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020045
46 if (strncmp(str1, str2, *(size_t *)cb_data) == 0) {
47 return 1;
48 }
49
50 return 0;
51}
52
53void
Michal Vasko8efac242023-03-30 08:24:56 +020054lydict_init(struct ly_dict *dict)
Radek Krejci5aeea3a2018-09-05 13:29:36 +020055{
Michal Vaskod989ba02020-08-24 10:59:24 +020056 LY_CHECK_ARG_RET(NULL, dict, );
Radek Krejci5aeea3a2018-09-05 13:29:36 +020057
Michal Vasko8efac242023-03-30 08:24:56 +020058 dict->hash_tab = lyht_new(LYDICT_MIN_SIZE, sizeof(struct ly_dict_rec), lydict_val_eq, NULL, 1);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020059 LY_CHECK_ERR_RET(!dict->hash_tab, LOGINT(NULL), );
Radek Krejci5aeea3a2018-09-05 13:29:36 +020060 pthread_mutex_init(&dict->lock, NULL);
61}
62
63void
Michal Vasko8efac242023-03-30 08:24:56 +020064lydict_clean(struct ly_dict *dict)
Radek Krejci5aeea3a2018-09-05 13:29:36 +020065{
Michal Vasko8efac242023-03-30 08:24:56 +020066 struct ly_dict_rec *dict_rec = NULL;
67 struct ly_ht_rec *rec = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +020068
Michal Vaskod989ba02020-08-24 10:59:24 +020069 LY_CHECK_ARG_RET(NULL, dict, );
Radek Krejci5aeea3a2018-09-05 13:29:36 +020070
Radek Krejci1deb5be2020-08-26 16:43:36 +020071 for (uint32_t i = 0; i < dict->hash_tab->size; i++) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +020072 /* get ith record */
Michal Vasko8efac242023-03-30 08:24:56 +020073 rec = (struct ly_ht_rec *)&dict->hash_tab->recs[i * dict->hash_tab->rec_size];
Radek Krejci5aeea3a2018-09-05 13:29:36 +020074 if (rec->hits == 1) {
75 /*
76 * this should not happen, all records inserted into
77 * dictionary are supposed to be removed using lydict_remove()
78 * before calling lydict_clean()
79 */
Michal Vasko8efac242023-03-30 08:24:56 +020080 dict_rec = (struct ly_dict_rec *)rec->val;
Radek Krejci5aeea3a2018-09-05 13:29:36 +020081 LOGWRN(NULL, "String \"%s\" not freed from the dictionary, refcount %d", dict_rec->value, dict_rec->refcount);
82 /* if record wasn't removed before free string allocated for that record */
83#ifdef NDEBUG
84 free(dict_rec->value);
85#endif
86 }
87 }
88
89 /* free table and destroy mutex */
Michal Vasko77b7f90a2023-01-31 15:42:41 +010090 lyht_free(dict->hash_tab, NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020091 pthread_mutex_destroy(&dict->lock);
92}
93
94/*
Radek Krejci5aeea3a2018-09-05 13:29:36 +020095 * Usage:
96 * - init hash to 0
97 * - repeatedly call dict_hash_multi(), provide hash from the last call
98 * - call dict_hash_multi() with key_part = NULL to finish the hash
99 */
100uint32_t
101dict_hash_multi(uint32_t hash, const char *key_part, size_t len)
102{
103 uint32_t i;
104
aPiecek4f07c3e2021-06-11 10:53:07 +0200105 if (key_part && len) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200106 for (i = 0; i < len; ++i) {
107 hash += key_part[i];
108 hash += (hash << 10);
109 hash ^= (hash >> 6);
110 }
111 } else {
112 hash += (hash << 3);
113 hash ^= (hash >> 11);
114 hash += (hash << 15);
115 }
116
117 return hash;
118}
119
Radek Krejcif2dc4c52018-11-08 09:04:13 +0100120/*
121 * Bob Jenkin's one-at-a-time hash
122 * http://www.burtleburtle.net/bob/hash/doobs.html
123 *
124 * Spooky hash is faster, but it works only for little endian architectures.
125 */
126uint32_t
127dict_hash(const char *key, size_t len)
128{
129 uint32_t hash;
130
131 hash = dict_hash_multi(0, key, len);
132 return dict_hash_multi(hash, NULL, len);
133}
134
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200135static ly_bool
136lydict_resize_val_eq(void *val1_p, void *val2_p, ly_bool mod, void *cb_data)
137{
138 LY_CHECK_ARG_RET(NULL, val1_p, val2_p, 0);
139
Michal Vasko8efac242023-03-30 08:24:56 +0200140 const char *str1 = ((struct ly_dict_rec *)val1_p)->value;
141 const char *str2 = ((struct ly_dict_rec *)val2_p)->value;
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200142
143 LY_CHECK_ERR_RET(!str1, LOGARG(NULL, val1_p), 0);
144 LY_CHECK_ERR_RET(!str2, LOGARG(NULL, val2_p), 0);
145
146 if (mod) {
147 /* used when inserting new values */
148 if (strcmp(str1, str2) == 0) {
149 return 1;
150 }
151 } else {
152 /* used when finding the original value again in the resized table */
153 return lydict_val_eq(val1_p, val2_p, mod, cb_data);
154 }
155
156 return 0;
157}
158
Jan Kundrátc53a7ec2021-12-09 16:01:19 +0100159LIBYANG_API_DEF LY_ERR
Michal Vasko52927e22020-03-16 17:26:14 +0100160lydict_remove(const struct ly_ctx *ctx, const char *value)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200161{
Michal Vaskoe180ed02021-02-05 16:31:20 +0100162 LY_ERR ret = LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200163 size_t len;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200164 uint32_t hash;
Michal Vasko8efac242023-03-30 08:24:56 +0200165 struct ly_dict_rec rec, *match = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200166 char *val_p;
167
Michal Vasko016569c2021-03-04 15:50:02 +0100168 if (!ctx || !value) {
Michal Vaskoe180ed02021-02-05 16:31:20 +0100169 return LY_SUCCESS;
Michal Vasko0f6b3e22018-09-07 12:18:12 +0200170 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200171
Michal Vaskoe180ed02021-02-05 16:31:20 +0100172 LOGDBG(LY_LDGDICT, "removing \"%s\"", value);
173
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200174 len = strlen(value);
175 hash = dict_hash(value, len);
176
177 /* create record for lyht_find call */
178 rec.value = (char *)value;
179 rec.refcount = 0;
180
Michal Vasko52927e22020-03-16 17:26:14 +0100181 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200182 /* set len as data for compare callback */
183 lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
184 /* check if value is already inserted */
185 ret = lyht_find(ctx->dict.hash_tab, &rec, hash, (void **)&match);
186
Radek Krejci1deb5be2020-08-26 16:43:36 +0200187 if (ret == LY_SUCCESS) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200188 LY_CHECK_ERR_GOTO(!match, LOGINT(ctx), finish);
189
190 /* if value is already in dictionary, decrement reference counter */
191 match->refcount--;
192 if (match->refcount == 0) {
193 /*
194 * remove record
195 * save pointer to stored string before lyht_remove to
196 * free it after it is removed from hash table
197 */
198 val_p = match->value;
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200199 ret = lyht_remove_with_resize_cb(ctx->dict.hash_tab, &rec, hash, lydict_resize_val_eq);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200200 free(val_p);
201 LY_CHECK_ERR_GOTO(ret, LOGINT(ctx), finish);
202 }
Michal Vaskoe180ed02021-02-05 16:31:20 +0100203 } else if (ret == LY_ENOTFOUND) {
204 LOGERR(ctx, LY_ENOTFOUND, "Value \"%s\" was not found in the dictionary.", value);
205 } else {
206 LOGINT(ctx);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200207 }
208
209finish:
Michal Vasko52927e22020-03-16 17:26:14 +0100210 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
Michal Vaskoe180ed02021-02-05 16:31:20 +0100211 return ret;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200212}
213
Radek Krejci011e4aa2020-09-04 15:22:31 +0200214LY_ERR
215dict_insert(const struct ly_ctx *ctx, char *value, size_t len, ly_bool zerocopy, const char **str_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200216{
Radek Krejci011e4aa2020-09-04 15:22:31 +0200217 LY_ERR ret = LY_SUCCESS;
Michal Vasko8efac242023-03-30 08:24:56 +0200218 struct ly_dict_rec *match = NULL, rec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200219 uint32_t hash;
220
Radek Krejci422afb12021-03-04 16:38:16 +0100221 LOGDBG(LY_LDGDICT, "inserting \"%.*s\"", (int)len, value);
Michal Vaskoe180ed02021-02-05 16:31:20 +0100222
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200223 hash = dict_hash(value, len);
224 /* set len as data for compare callback */
225 lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
226 /* create record for lyht_insert */
227 rec.value = value;
228 rec.refcount = 1;
229
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200230 ret = lyht_insert_with_resize_cb(ctx->dict.hash_tab, (void *)&rec, hash, lydict_resize_val_eq, (void **)&match);
Michal Vaskofcc96b92018-09-12 11:12:01 +0200231 if (ret == LY_EEXIST) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200232 match->refcount++;
233 if (zerocopy) {
234 free(value);
235 }
Radek Krejci011e4aa2020-09-04 15:22:31 +0200236 ret = LY_SUCCESS;
Michal Vaskofcc96b92018-09-12 11:12:01 +0200237 } else if (ret == LY_SUCCESS) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200238 if (!zerocopy) {
239 /*
240 * allocate string for new record
241 * record is already inserted in hash table
242 */
243 match->value = malloc(sizeof *match->value * (len + 1));
Radek Krejci011e4aa2020-09-04 15:22:31 +0200244 LY_CHECK_ERR_RET(!match->value, LOGMEM(ctx), LY_EMEM);
Michal Vasko08e9b112021-06-11 15:41:17 +0200245 if (len) {
246 memcpy(match->value, value, len);
247 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200248 match->value[len] = '\0';
249 }
250 } else {
251 /* lyht_insert returned error */
David Sedlák234a91f2019-08-15 13:16:43 +0200252 if (zerocopy) {
253 free(value);
254 }
Radek Krejci011e4aa2020-09-04 15:22:31 +0200255 return ret;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200256 }
257
Radek Krejci011e4aa2020-09-04 15:22:31 +0200258 if (str_p) {
259 *str_p = match->value;
260 }
261
262 return ret;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200263}
264
Jan Kundrátc53a7ec2021-12-09 16:01:19 +0100265LIBYANG_API_DEF LY_ERR
Radek Krejci011e4aa2020-09-04 15:22:31 +0200266lydict_insert(const struct ly_ctx *ctx, const char *value, size_t len, const char **str_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200267{
Radek Krejci011e4aa2020-09-04 15:22:31 +0200268 LY_ERR result;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200269
Michal Vaskobe27c912021-02-24 17:07:37 +0100270 LY_CHECK_ARG_RET(ctx, ctx, str_p, LY_EINVAL);
271
272 if (!value) {
273 *str_p = NULL;
274 return LY_SUCCESS;
275 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200276
Radek Krejci0ae092d2018-09-20 16:43:19 +0200277 if (!len) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200278 len = strlen(value);
279 }
280
Michal Vasko52927e22020-03-16 17:26:14 +0100281 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci011e4aa2020-09-04 15:22:31 +0200282 result = dict_insert(ctx, (char *)value, len, 0, str_p);
Michal Vasko52927e22020-03-16 17:26:14 +0100283 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200284
285 return result;
286}
287
Jan Kundrátc53a7ec2021-12-09 16:01:19 +0100288LIBYANG_API_DEF LY_ERR
Radek Krejci011e4aa2020-09-04 15:22:31 +0200289lydict_insert_zc(const struct ly_ctx *ctx, char *value, const char **str_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200290{
Radek Krejci011e4aa2020-09-04 15:22:31 +0200291 LY_ERR result;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200292
Michal Vaskobe27c912021-02-24 17:07:37 +0100293 LY_CHECK_ARG_RET(ctx, ctx, str_p, LY_EINVAL);
294
295 if (!value) {
296 *str_p = NULL;
297 return LY_SUCCESS;
298 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200299
Michal Vasko52927e22020-03-16 17:26:14 +0100300 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci011e4aa2020-09-04 15:22:31 +0200301 result = dict_insert(ctx, value, strlen(value), 1, str_p);
Michal Vasko52927e22020-03-16 17:26:14 +0100302 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200303
304 return result;
305}
306
Michal Vasko8efac242023-03-30 08:24:56 +0200307struct ly_ht_rec *
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200308lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx)
309{
Michal Vasko8efac242023-03-30 08:24:56 +0200310 return (struct ly_ht_rec *)&recs[idx * rec_size];
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200311}
312
Michal Vasko8efac242023-03-30 08:24:56 +0200313struct ly_ht *
Michal Vasko62524a92021-02-26 10:08:50 +0100314lyht_new(uint32_t size, uint16_t val_size, lyht_value_equal_cb val_equal, void *cb_data, uint16_t resize)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200315{
Michal Vasko8efac242023-03-30 08:24:56 +0200316 struct ly_ht *ht;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200317
318 /* check that 2^x == size (power of 2) */
319 assert(size && !(size & (size - 1)));
320 assert(val_equal && val_size);
321 assert(resize == 0 || resize == 1);
322
323 if (size < LYHT_MIN_SIZE) {
324 size = LYHT_MIN_SIZE;
325 }
326
327 ht = malloc(sizeof *ht);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200328 LY_CHECK_ERR_RET(!ht, LOGMEM(NULL), NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200329
330 ht->used = 0;
331 ht->size = size;
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200332 ht->invalid = 0;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200333 ht->val_equal = val_equal;
334 ht->cb_data = cb_data;
Radek Krejci1deb5be2020-08-26 16:43:36 +0200335 ht->resize = resize;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200336
Michal Vasko8efac242023-03-30 08:24:56 +0200337 ht->rec_size = (sizeof(struct ly_ht_rec) - 1) + val_size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200338 /* allocate the records correctly */
339 ht->recs = calloc(size, ht->rec_size);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200340 LY_CHECK_ERR_RET(!ht->recs, free(ht); LOGMEM(NULL), NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200341
342 return ht;
343}
344
Michal Vasko62524a92021-02-26 10:08:50 +0100345lyht_value_equal_cb
Michal Vasko8efac242023-03-30 08:24:56 +0200346lyht_set_cb(struct ly_ht *ht, lyht_value_equal_cb new_val_equal)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200347{
Michal Vasko62524a92021-02-26 10:08:50 +0100348 lyht_value_equal_cb prev;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200349
350 prev = ht->val_equal;
351 ht->val_equal = new_val_equal;
352 return prev;
353}
354
355void *
Michal Vasko8efac242023-03-30 08:24:56 +0200356lyht_set_cb_data(struct ly_ht *ht, void *new_cb_data)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200357{
358 void *prev;
359
360 prev = ht->cb_data;
361 ht->cb_data = new_cb_data;
362 return prev;
363}
364
Michal Vasko8efac242023-03-30 08:24:56 +0200365struct ly_ht *
366lyht_dup(const struct ly_ht *orig)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200367{
Michal Vasko8efac242023-03-30 08:24:56 +0200368 struct ly_ht *ht;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200369
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200370 LY_CHECK_ARG_RET(NULL, orig, NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200371
Michal Vasko8efac242023-03-30 08:24:56 +0200372 ht = lyht_new(orig->size, orig->rec_size - (sizeof(struct ly_ht_rec) - 1), orig->val_equal, orig->cb_data, orig->resize ? 1 : 0);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200373 if (!ht) {
374 return NULL;
375 }
376
Radek Krejcid78fd462021-06-02 21:29:20 +0200377 memcpy(ht->recs, orig->recs, (size_t)orig->used * (size_t)orig->rec_size);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200378 ht->used = orig->used;
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200379 ht->invalid = orig->invalid;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200380 return ht;
381}
382
383void
Michal Vasko8efac242023-03-30 08:24:56 +0200384lyht_free(struct ly_ht *ht, void (*val_free)(void *val_p))
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200385{
Michal Vasko8efac242023-03-30 08:24:56 +0200386 struct ly_ht_rec *rec;
Michal Vasko77b7f90a2023-01-31 15:42:41 +0100387 uint32_t i;
388
389 if (!ht) {
390 return;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200391 }
Michal Vasko77b7f90a2023-01-31 15:42:41 +0100392
393 if (val_free) {
394 for (i = 0; i < ht->size; ++i) {
395 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
396 if (rec->hits > 0) {
397 val_free(&rec->val);
398 }
399 }
400 }
401 free(ht->recs);
402 free(ht);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200403}
404
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200405/**
406 * @brief Resize a hash table.
407 *
408 * @param[in] ht Hash table to resize.
409 * @param[in] operation Operation to perform. 1 to enlarge, -1 to shrink, 0 to only rehash all records.
410 * @return LY_ERR value.
411 */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200412static LY_ERR
Michal Vasko8efac242023-03-30 08:24:56 +0200413lyht_resize(struct ly_ht *ht, int operation)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200414{
Michal Vasko8efac242023-03-30 08:24:56 +0200415 struct ly_ht_rec *rec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200416 unsigned char *old_recs;
417 uint32_t i, old_size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200418
419 old_recs = ht->recs;
420 old_size = ht->size;
421
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200422 if (operation > 0) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200423 /* double the size */
424 ht->size <<= 1;
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200425 } else if (operation < 0) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200426 /* half the size */
427 ht->size >>= 1;
428 }
429
430 ht->recs = calloc(ht->size, ht->rec_size);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200431 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 +0200432
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200433 /* reset used and invalid, it will increase again */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200434 ht->used = 0;
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200435 ht->invalid = 0;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200436
437 /* add all the old records into the new records array */
438 for (i = 0; i < old_size; ++i) {
439 rec = lyht_get_rec(old_recs, ht->rec_size, i);
440 if (rec->hits > 0) {
Radek Krejci1deb5be2020-08-26 16:43:36 +0200441 LY_ERR ret = lyht_insert(ht, rec->val, rec->hash, NULL);
Michal Vasko26bbb272022-08-02 14:54:33 +0200442
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200443 assert(!ret);
444 (void)ret;
445 }
446 }
447
448 /* final touches */
449 free(old_recs);
450 return LY_SUCCESS;
451}
452
Michal Vaskoda859032020-07-14 12:20:14 +0200453/**
454 * @brief Search for the first match.
455 *
456 * @param[in] ht Hash table to search in.
457 * @param[in] hash Hash to find.
458 * @param[out] rec_p Optional found record.
459 * @return LY_SUCCESS hash found, returned its record,
460 * @return LY_ENOTFOUND hash not found, returned the record where it would be inserted.
461 */
462static LY_ERR
Michal Vasko8efac242023-03-30 08:24:56 +0200463lyht_find_first(struct ly_ht *ht, uint32_t hash, struct ly_ht_rec **rec_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200464{
Michal Vasko8efac242023-03-30 08:24:56 +0200465 struct ly_ht_rec *rec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200466 uint32_t i, idx;
467
468 if (rec_p) {
469 *rec_p = NULL;
470 }
471
472 idx = i = hash & (ht->size - 1);
473 rec = lyht_get_rec(ht->recs, ht->rec_size, idx);
474
475 /* skip through overflow and deleted records */
476 while ((rec->hits != 0) && ((rec->hits == -1) || ((rec->hash & (ht->size - 1)) != idx))) {
477 if ((rec->hits == -1) && rec_p && !(*rec_p)) {
478 /* remember this record for return */
479 *rec_p = rec;
480 }
481 i = (i + 1) % ht->size;
482 if (i == idx) {
483 /* we went through all the records (very unlikely, but possible when many records are invalid),
484 * just return not found */
485 assert(!rec_p || *rec_p);
Michal Vaskoda859032020-07-14 12:20:14 +0200486 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200487 }
488 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
489 }
490 if (rec->hits == 0) {
491 /* we could not find the value */
492 if (rec_p && !*rec_p) {
493 *rec_p = rec;
494 }
Michal Vaskoda859032020-07-14 12:20:14 +0200495 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200496 }
497
498 /* we have found a record with equal (shortened) hash */
499 if (rec_p) {
500 *rec_p = rec;
501 }
Michal Vaskoda859032020-07-14 12:20:14 +0200502 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200503}
504
505/**
506 * @brief Search for the next collision.
507 *
508 * @param[in] ht Hash table to search in.
509 * @param[in,out] last Last returned collision record.
510 * @param[in] first First collision record (hits > 1).
Michal Vaskoda859032020-07-14 12:20:14 +0200511 * @return LY_SUCCESS when hash collision found, \p last points to this next collision,
512 * @return LY_ENOTFOUND when hash collision not found, \p last points to the record where it would be inserted.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200513 */
Michal Vaskoda859032020-07-14 12:20:14 +0200514static LY_ERR
Michal Vasko8efac242023-03-30 08:24:56 +0200515lyht_find_collision(struct ly_ht *ht, struct ly_ht_rec **last, struct ly_ht_rec *first)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200516{
Michal Vasko8efac242023-03-30 08:24:56 +0200517 struct ly_ht_rec *empty = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200518 uint32_t i, idx;
519
520 assert(last && *last);
521
522 idx = (*last)->hash & (ht->size - 1);
523 i = (((unsigned char *)*last) - ht->recs) / ht->rec_size;
524
525 do {
526 i = (i + 1) % ht->size;
527 *last = lyht_get_rec(ht->recs, ht->rec_size, i);
528 if (*last == first) {
529 /* we went through all the records (very unlikely, but possible when many records are invalid),
530 * just return an invalid record */
531 assert(empty);
532 *last = empty;
Michal Vaskoda859032020-07-14 12:20:14 +0200533 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200534 }
535
536 if (((*last)->hits == -1) && !empty) {
537 empty = *last;
538 }
539 } while (((*last)->hits != 0) && (((*last)->hits == -1) || (((*last)->hash & (ht->size - 1)) != idx)));
540
541 if ((*last)->hits > 0) {
542 /* we found a collision */
543 assert((*last)->hits == 1);
Michal Vaskoda859032020-07-14 12:20:14 +0200544 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200545 }
546
547 /* no next collision found, return the record where it would be inserted */
548 if (empty) {
549 *last = empty;
550 } /* else (*last)->hits == 0, it is already correct */
Michal Vaskoda859032020-07-14 12:20:14 +0200551 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200552}
553
Michal Vaskoda859032020-07-14 12:20:14 +0200554/**
555 * @brief Search for a record with specific value and hash.
556 *
557 * @param[in] ht Hash table to search in.
558 * @param[in] val_p Pointer to the value to find.
559 * @param[in] hash Hash to find.
Radek Krejci857189e2020-09-01 13:26:36 +0200560 * @param[in] mod Whether the operation modifies the hash table (insert or remove) or not (find).
Michal Vaskoda859032020-07-14 12:20:14 +0200561 * @param[out] crec_p Optional found first record.
562 * @param[out] col Optional collision number of @p rec_p, 0 for no collision.
563 * @param[out] rec_p Found exact matching record, may be a collision of @p crec_p.
564 * @return LY_ENOTFOUND if no record found,
565 * @return LY_SUCCESS if record was found.
566 */
567static LY_ERR
Michal Vasko8efac242023-03-30 08:24:56 +0200568lyht_find_rec(struct ly_ht *ht, void *val_p, uint32_t hash, ly_bool mod, struct ly_ht_rec **crec_p, uint32_t *col,
569 struct ly_ht_rec **rec_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200570{
Michal Vasko8efac242023-03-30 08:24:56 +0200571 struct ly_ht_rec *rec, *crec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200572 uint32_t i, c;
Michal Vaskoda859032020-07-14 12:20:14 +0200573 LY_ERR r;
574
575 if (crec_p) {
576 *crec_p = NULL;
577 }
578 if (col) {
579 *col = 0;
580 }
581 *rec_p = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200582
583 if (lyht_find_first(ht, hash, &rec)) {
584 /* not found */
Michal Vaskoda859032020-07-14 12:20:14 +0200585 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200586 }
Michal Vaskoda859032020-07-14 12:20:14 +0200587 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200588 /* even the value matches */
Michal Vaskoda859032020-07-14 12:20:14 +0200589 if (crec_p) {
590 *crec_p = rec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200591 }
Michal Vaskoda859032020-07-14 12:20:14 +0200592 if (col) {
593 *col = 0;
594 }
595 *rec_p = rec;
596 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200597 }
598
599 /* some collisions, we need to go through them, too */
600 crec = rec;
Michal Vaskoda859032020-07-14 12:20:14 +0200601 c = crec->hits;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200602 for (i = 1; i < c; ++i) {
603 r = lyht_find_collision(ht, &rec, crec);
604 assert(!r);
605 (void)r;
606
607 /* compare values */
Michal Vaskoda859032020-07-14 12:20:14 +0200608 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
609 if (crec_p) {
610 *crec_p = crec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200611 }
Michal Vaskoda859032020-07-14 12:20:14 +0200612 if (col) {
613 *col = i;
614 }
615 *rec_p = rec;
616 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200617 }
618 }
619
620 /* not found even in collisions */
Michal Vaskoda859032020-07-14 12:20:14 +0200621 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200622}
623
Michal Vaskoda859032020-07-14 12:20:14 +0200624LY_ERR
Michal Vasko8efac242023-03-30 08:24:56 +0200625lyht_find(struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p)
Michal Vaskoda859032020-07-14 12:20:14 +0200626{
Michal Vasko8efac242023-03-30 08:24:56 +0200627 struct ly_ht_rec *rec;
Michal Vaskoda859032020-07-14 12:20:14 +0200628
629 lyht_find_rec(ht, val_p, hash, 0, NULL, NULL, &rec);
630
631 if (rec && match_p) {
632 *match_p = rec->val;
633 }
634 return rec ? LY_SUCCESS : LY_ENOTFOUND;
635}
636
637LY_ERR
Michal Vasko8efac242023-03-30 08:24:56 +0200638lyht_find_next_with_collision_cb(struct ly_ht *ht, void *val_p, uint32_t hash,
Michal Vasko6374de22022-09-05 15:48:48 +0200639 lyht_value_equal_cb collision_val_equal, void **match_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200640{
Michal Vasko8efac242023-03-30 08:24:56 +0200641 struct ly_ht_rec *rec, *crec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200642 uint32_t i, c;
Michal Vaskoda859032020-07-14 12:20:14 +0200643 LY_ERR r;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200644
Michal Vasko6374de22022-09-05 15:48:48 +0200645 /* find the record of the previously found value */
Michal Vaskoda859032020-07-14 12:20:14 +0200646 if (lyht_find_rec(ht, val_p, hash, 1, &crec, &i, &rec)) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200647 /* not found, cannot happen */
Michal Vaskoda859032020-07-14 12:20:14 +0200648 LOGINT_RET(NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200649 }
650
Michal Vasko6374de22022-09-05 15:48:48 +0200651 /* go through collisions and find the next one after the previous one */
Michal Vaskoda859032020-07-14 12:20:14 +0200652 c = crec->hits;
653 for (++i; i < c; ++i) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200654 r = lyht_find_collision(ht, &rec, crec);
655 assert(!r);
656 (void)r;
657
Michal Vasko6374de22022-09-05 15:48:48 +0200658 if (rec->hash != hash) {
659 continue;
660 }
661
662 if (collision_val_equal) {
663 if (collision_val_equal(val_p, &rec->val, 0, ht->cb_data)) {
664 /* even the value matches */
665 if (match_p) {
666 *match_p = rec->val;
667 }
668 return LY_SUCCESS;
669 }
670 } else if (ht->val_equal(val_p, &rec->val, 0, ht->cb_data)) {
Michal Vaskoda859032020-07-14 12:20:14 +0200671 /* even the value matches */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200672 if (match_p) {
673 *match_p = rec->val;
674 }
Michal Vaskoda859032020-07-14 12:20:14 +0200675 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200676 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200677 }
678
679 /* the last equal value was already returned */
Michal Vaskoda859032020-07-14 12:20:14 +0200680 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200681}
682
683LY_ERR
Michal Vasko8efac242023-03-30 08:24:56 +0200684lyht_find_next(struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p)
Michal Vasko6374de22022-09-05 15:48:48 +0200685{
686 return lyht_find_next_with_collision_cb(ht, val_p, hash, NULL, match_p);
687}
688
689LY_ERR
Michal Vasko8efac242023-03-30 08:24:56 +0200690lyht_insert_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal,
Michal Vasko62524a92021-02-26 10:08:50 +0100691 void **match_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200692{
Radek Krejci1deb5be2020-08-26 16:43:36 +0200693 LY_ERR r, ret = LY_SUCCESS;
Michal Vasko8efac242023-03-30 08:24:56 +0200694 struct ly_ht_rec *rec, *crec = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200695 int32_t i;
Michal Vasko62524a92021-02-26 10:08:50 +0100696 lyht_value_equal_cb old_val_equal = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200697
698 if (!lyht_find_first(ht, hash, &rec)) {
699 /* we found matching shortened hash */
700 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
701 /* even the value matches */
702 if (match_p) {
703 *match_p = (void *)&rec->val;
704 }
705 return LY_EEXIST;
706 }
707
708 /* some collisions, we need to go through them, too */
709 crec = rec;
710 for (i = 1; i < crec->hits; ++i) {
711 r = lyht_find_collision(ht, &rec, crec);
712 assert(!r);
713
714 /* compare values */
715 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
716 if (match_p) {
717 *match_p = (void *)&rec->val;
718 }
719 return LY_EEXIST;
720 }
721 }
722
723 /* value not found, get the record where it will be inserted */
724 r = lyht_find_collision(ht, &rec, crec);
725 assert(r);
726 }
727
728 /* insert it into the returned record */
729 assert(rec->hits < 1);
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200730 if (rec->hits < 0) {
731 --ht->invalid;
732 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200733 rec->hash = hash;
734 rec->hits = 1;
Michal Vasko8efac242023-03-30 08:24:56 +0200735 memcpy(&rec->val, val_p, ht->rec_size - (sizeof(struct ly_ht_rec) - 1));
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200736 if (match_p) {
737 *match_p = (void *)&rec->val;
738 }
739
740 if (crec) {
741 /* there was a collision, increase hits */
742 if (crec->hits == INT32_MAX) {
743 LOGINT(NULL);
744 }
745 ++crec->hits;
746 }
747
748 /* check size & enlarge if needed */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200749 ++ht->used;
750 if (ht->resize) {
Radek Krejcif13b87b2020-12-01 22:02:17 +0100751 r = (ht->used * LYHT_HUNDRED_PERCENTAGE) / ht->size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200752 if ((ht->resize == 1) && (r >= LYHT_FIRST_SHRINK_PERCENTAGE)) {
753 /* enable shrinking */
754 ht->resize = 2;
755 }
756 if ((ht->resize == 2) && (r >= LYHT_ENLARGE_PERCENTAGE)) {
757 if (resize_val_equal) {
758 old_val_equal = lyht_set_cb(ht, resize_val_equal);
759 }
760
761 /* enlarge */
762 ret = lyht_resize(ht, 1);
763 /* if hash_table was resized, we need to find new matching value */
Michal Vasko69730152020-10-09 16:30:07 +0200764 if ((ret == LY_SUCCESS) && match_p) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200765 lyht_find(ht, val_p, hash, match_p);
766 }
767
768 if (resize_val_equal) {
769 lyht_set_cb(ht, old_val_equal);
770 }
771 }
772 }
773 return ret;
774}
775
Radek Krejci0ae092d2018-09-20 16:43:19 +0200776LY_ERR
Michal Vasko8efac242023-03-30 08:24:56 +0200777lyht_insert(struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200778{
779 return lyht_insert_with_resize_cb(ht, val_p, hash, NULL, match_p);
780}
781
782LY_ERR
Michal Vasko8efac242023-03-30 08:24:56 +0200783lyht_remove_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200784{
Michal Vasko8efac242023-03-30 08:24:56 +0200785 struct ly_ht_rec *rec, *crec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200786 int32_t i;
Radek Krejci857189e2020-09-01 13:26:36 +0200787 ly_bool first_matched = 0;
Radek Krejci1deb5be2020-08-26 16:43:36 +0200788 LY_ERR r, ret = LY_SUCCESS;
Michal Vasko62524a92021-02-26 10:08:50 +0100789 lyht_value_equal_cb old_val_equal;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200790
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200791 LY_CHECK_ERR_RET(lyht_find_first(ht, hash, &rec), LOGARG(NULL, hash), LY_ENOTFOUND); /* hash not found */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200792
793 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
794 /* even the value matches */
795 first_matched = 1;
796 }
797
798 /* we always need to go through collisions */
799 crec = rec;
800 for (i = 1; i < crec->hits; ++i) {
801 r = lyht_find_collision(ht, &rec, crec);
802 assert(!r);
803
804 /* compare values */
805 if (!first_matched && (rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
806 break;
807 }
808 }
809
810 if (i < crec->hits) {
811 /* one of collisions matched, reduce collision count, remove the record */
812 assert(!first_matched);
813 --crec->hits;
814 rec->hits = -1;
815 } else if (first_matched) {
816 /* the first record matches */
817 if (crec != rec) {
818 /* ... so put the last collision in its place */
819 rec->hits = crec->hits - 1;
820 memcpy(crec, rec, ht->rec_size);
821 }
822 rec->hits = -1;
823 } else {
824 /* value not found even in collisions */
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200825 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200826 }
827
828 /* check size & shrink if needed */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200829 --ht->used;
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200830 ++ht->invalid;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200831 if (ht->resize == 2) {
Radek Krejcif13b87b2020-12-01 22:02:17 +0100832 r = (ht->used * LYHT_HUNDRED_PERCENTAGE) / ht->size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200833 if ((r < LYHT_SHRINK_PERCENTAGE) && (ht->size > LYHT_MIN_SIZE)) {
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200834 if (resize_val_equal) {
835 old_val_equal = lyht_set_cb(ht, resize_val_equal);
836 }
837
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200838 /* shrink */
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200839 ret = lyht_resize(ht, -1);
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200840
841 if (resize_val_equal) {
842 lyht_set_cb(ht, old_val_equal);
843 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200844 }
845 }
846
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200847 /* rehash all records if needed */
848 r = ((ht->size - ht->used - ht->invalid) * 100) / ht->size;
849 if (r < LYHT_REHASH_PERCENTAGE) {
850 if (resize_val_equal) {
851 old_val_equal = lyht_set_cb(ht, resize_val_equal);
852 }
853
854 /* rehash */
855 ret = lyht_resize(ht, 0);
856
857 if (resize_val_equal) {
858 lyht_set_cb(ht, old_val_equal);
859 }
860 }
861
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200862 return ret;
863}
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200864
865LY_ERR
Michal Vasko8efac242023-03-30 08:24:56 +0200866lyht_remove(struct ly_ht *ht, void *val_p, uint32_t hash)
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200867{
868 return lyht_remove_with_resize_cb(ht, val_p, hash, NULL);
869}
Michal Vasko626196f2022-08-05 12:49:52 +0200870
871uint32_t
872lyht_get_fixed_size(uint32_t item_count)
873{
874 uint32_t i, size = 0;
875
876 /* detect number of upper zero bits in the items' counter value ... */
877 for (i = (sizeof item_count * CHAR_BIT) - 1; i > 0; i--) {
878 size = item_count << i;
879 size = size >> i;
880 if (size == item_count) {
881 break;
882 }
883 }
884 assert(i);
885
886 /* ... and then we convert it to the position of the highest non-zero bit ... */
887 i = (sizeof item_count * CHAR_BIT) - i;
888
889 /* ... and by using it to shift 1 to the left we get the closest sufficient hash table size */
890 size = 1 << i;
891
892 return size;
893}