blob: fecdd5ccbf8da5919b65fd96967ff2b4413b7912 [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
40 const char *str1 = ((struct dict_rec *)val1_p)->value;
41 const char *str2 = ((struct dict_rec *)val2_p)->value;
42
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
54lydict_init(struct dict_table *dict)
55{
Michal Vaskod989ba02020-08-24 10:59:24 +020056 LY_CHECK_ARG_RET(NULL, dict, );
Radek Krejci5aeea3a2018-09-05 13:29:36 +020057
Radek Krejcif13b87b2020-12-01 22:02:17 +010058 dict->hash_tab = lyht_new(LYDICT_MIN_SIZE, sizeof(struct 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
64lydict_clean(struct dict_table *dict)
65{
Michal Vasko44f3d2c2020-08-24 09:49:38 +020066 struct dict_rec *dict_rec = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +020067 struct ht_rec *rec = NULL;
68
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 */
73 rec = (struct ht_rec *)&dict->hash_tab->recs[i * dict->hash_tab->rec_size];
74 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 Vasko44f3d2c2020-08-24 09:49:38 +020080 dict_rec = (struct 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 */
90 lyht_free(dict->hash_tab);
91 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
140 const char *str1 = ((struct dict_rec *)val1_p)->value;
141 const char *str2 = ((struct dict_rec *)val2_p)->value;
142
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
Michal Vaskoe180ed02021-02-05 16:31:20 +0100159API 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;
165 struct dict_rec rec, *match = NULL;
166 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;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200218 struct 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);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200245 memcpy(match->value, value, len);
246 match->value[len] = '\0';
247 }
248 } else {
249 /* lyht_insert returned error */
David Sedlák234a91f2019-08-15 13:16:43 +0200250 if (zerocopy) {
251 free(value);
252 }
Radek Krejci011e4aa2020-09-04 15:22:31 +0200253 return ret;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200254 }
255
Radek Krejci011e4aa2020-09-04 15:22:31 +0200256 if (str_p) {
257 *str_p = match->value;
258 }
259
260 return ret;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200261}
262
Radek Krejci011e4aa2020-09-04 15:22:31 +0200263API LY_ERR
264lydict_insert(const struct ly_ctx *ctx, const char *value, size_t len, const char **str_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200265{
Radek Krejci011e4aa2020-09-04 15:22:31 +0200266 LY_ERR result;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200267
Michal Vaskobe27c912021-02-24 17:07:37 +0100268 LY_CHECK_ARG_RET(ctx, ctx, str_p, LY_EINVAL);
269
270 if (!value) {
271 *str_p = NULL;
272 return LY_SUCCESS;
273 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200274
Radek Krejci0ae092d2018-09-20 16:43:19 +0200275 if (!len) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200276 len = strlen(value);
277 }
278
Michal Vasko52927e22020-03-16 17:26:14 +0100279 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci011e4aa2020-09-04 15:22:31 +0200280 result = dict_insert(ctx, (char *)value, len, 0, str_p);
Michal Vasko52927e22020-03-16 17:26:14 +0100281 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200282
283 return result;
284}
285
Radek Krejci011e4aa2020-09-04 15:22:31 +0200286API LY_ERR
287lydict_insert_zc(const struct ly_ctx *ctx, char *value, const char **str_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200288{
Radek Krejci011e4aa2020-09-04 15:22:31 +0200289 LY_ERR result;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200290
Michal Vaskobe27c912021-02-24 17:07:37 +0100291 LY_CHECK_ARG_RET(ctx, ctx, str_p, LY_EINVAL);
292
293 if (!value) {
294 *str_p = NULL;
295 return LY_SUCCESS;
296 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200297
Michal Vasko52927e22020-03-16 17:26:14 +0100298 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci011e4aa2020-09-04 15:22:31 +0200299 result = dict_insert(ctx, value, strlen(value), 1, str_p);
Michal Vasko52927e22020-03-16 17:26:14 +0100300 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200301
302 return result;
303}
304
Radek Krejci2d7a47b2019-05-16 13:34:10 +0200305struct ht_rec *
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200306lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx)
307{
308 return (struct ht_rec *)&recs[idx * rec_size];
309}
310
311struct hash_table *
Michal Vasko62524a92021-02-26 10:08:50 +0100312lyht_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 +0200313{
314 struct hash_table *ht;
315
316 /* check that 2^x == size (power of 2) */
317 assert(size && !(size & (size - 1)));
318 assert(val_equal && val_size);
319 assert(resize == 0 || resize == 1);
320
321 if (size < LYHT_MIN_SIZE) {
322 size = LYHT_MIN_SIZE;
323 }
324
325 ht = malloc(sizeof *ht);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200326 LY_CHECK_ERR_RET(!ht, LOGMEM(NULL), NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200327
328 ht->used = 0;
329 ht->size = size;
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200330 ht->invalid = 0;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200331 ht->val_equal = val_equal;
332 ht->cb_data = cb_data;
Radek Krejci1deb5be2020-08-26 16:43:36 +0200333 ht->resize = resize;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200334
335 ht->rec_size = (sizeof(struct ht_rec) - 1) + val_size;
336 /* allocate the records correctly */
337 ht->recs = calloc(size, ht->rec_size);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200338 LY_CHECK_ERR_RET(!ht->recs, free(ht); LOGMEM(NULL), NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200339
340 return ht;
341}
342
Michal Vasko62524a92021-02-26 10:08:50 +0100343lyht_value_equal_cb
344lyht_set_cb(struct hash_table *ht, lyht_value_equal_cb new_val_equal)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200345{
Michal Vasko62524a92021-02-26 10:08:50 +0100346 lyht_value_equal_cb prev;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200347
348 prev = ht->val_equal;
349 ht->val_equal = new_val_equal;
350 return prev;
351}
352
353void *
354lyht_set_cb_data(struct hash_table *ht, void *new_cb_data)
355{
356 void *prev;
357
358 prev = ht->cb_data;
359 ht->cb_data = new_cb_data;
360 return prev;
361}
362
363struct hash_table *
364lyht_dup(const struct hash_table *orig)
365{
366 struct hash_table *ht;
367
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200368 LY_CHECK_ARG_RET(NULL, orig, NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200369
370 ht = lyht_new(orig->size, orig->rec_size - (sizeof(struct ht_rec) - 1), orig->val_equal, orig->cb_data, orig->resize ? 1 : 0);
371 if (!ht) {
372 return NULL;
373 }
374
Radek Krejcid78fd462021-06-02 21:29:20 +0200375 memcpy(ht->recs, orig->recs, (size_t)orig->used * (size_t)orig->rec_size);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200376 ht->used = orig->used;
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200377 ht->invalid = orig->invalid;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200378 return ht;
379}
380
381void
382lyht_free(struct hash_table *ht)
383{
384 if (ht) {
385 free(ht->recs);
386 free(ht);
387 }
388}
389
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200390/**
391 * @brief Resize a hash table.
392 *
393 * @param[in] ht Hash table to resize.
394 * @param[in] operation Operation to perform. 1 to enlarge, -1 to shrink, 0 to only rehash all records.
395 * @return LY_ERR value.
396 */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200397static LY_ERR
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200398lyht_resize(struct hash_table *ht, int operation)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200399{
400 struct ht_rec *rec;
401 unsigned char *old_recs;
402 uint32_t i, old_size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200403
404 old_recs = ht->recs;
405 old_size = ht->size;
406
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200407 if (operation > 0) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200408 /* double the size */
409 ht->size <<= 1;
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200410 } else if (operation < 0) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200411 /* half the size */
412 ht->size >>= 1;
413 }
414
415 ht->recs = calloc(ht->size, ht->rec_size);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200416 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 +0200417
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200418 /* reset used and invalid, it will increase again */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200419 ht->used = 0;
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200420 ht->invalid = 0;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200421
422 /* add all the old records into the new records array */
423 for (i = 0; i < old_size; ++i) {
424 rec = lyht_get_rec(old_recs, ht->rec_size, i);
425 if (rec->hits > 0) {
Radek Krejci1deb5be2020-08-26 16:43:36 +0200426 LY_ERR ret = lyht_insert(ht, rec->val, rec->hash, NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200427 assert(!ret);
428 (void)ret;
429 }
430 }
431
432 /* final touches */
433 free(old_recs);
434 return LY_SUCCESS;
435}
436
Michal Vaskoda859032020-07-14 12:20:14 +0200437/**
438 * @brief Search for the first match.
439 *
440 * @param[in] ht Hash table to search in.
441 * @param[in] hash Hash to find.
442 * @param[out] rec_p Optional found record.
443 * @return LY_SUCCESS hash found, returned its record,
444 * @return LY_ENOTFOUND hash not found, returned the record where it would be inserted.
445 */
446static LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200447lyht_find_first(struct hash_table *ht, uint32_t hash, struct ht_rec **rec_p)
448{
449 struct ht_rec *rec;
450 uint32_t i, idx;
451
452 if (rec_p) {
453 *rec_p = NULL;
454 }
455
456 idx = i = hash & (ht->size - 1);
457 rec = lyht_get_rec(ht->recs, ht->rec_size, idx);
458
459 /* skip through overflow and deleted records */
460 while ((rec->hits != 0) && ((rec->hits == -1) || ((rec->hash & (ht->size - 1)) != idx))) {
461 if ((rec->hits == -1) && rec_p && !(*rec_p)) {
462 /* remember this record for return */
463 *rec_p = rec;
464 }
465 i = (i + 1) % ht->size;
466 if (i == idx) {
467 /* we went through all the records (very unlikely, but possible when many records are invalid),
468 * just return not found */
469 assert(!rec_p || *rec_p);
Michal Vaskoda859032020-07-14 12:20:14 +0200470 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200471 }
472 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
473 }
474 if (rec->hits == 0) {
475 /* we could not find the value */
476 if (rec_p && !*rec_p) {
477 *rec_p = rec;
478 }
Michal Vaskoda859032020-07-14 12:20:14 +0200479 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200480 }
481
482 /* we have found a record with equal (shortened) hash */
483 if (rec_p) {
484 *rec_p = rec;
485 }
Michal Vaskoda859032020-07-14 12:20:14 +0200486 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200487}
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).
Michal Vaskoda859032020-07-14 12:20:14 +0200495 * @return LY_SUCCESS when hash collision found, \p last points to this next collision,
496 * @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 +0200497 */
Michal Vaskoda859032020-07-14 12:20:14 +0200498static LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200499lyht_find_collision(struct hash_table *ht, struct ht_rec **last, struct ht_rec *first)
500{
501 struct ht_rec *empty = 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(empty);
516 *last = empty;
Michal Vaskoda859032020-07-14 12:20:14 +0200517 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200518 }
519
520 if (((*last)->hits == -1) && !empty) {
521 empty = *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 */
527 assert((*last)->hits == 1);
Michal Vaskoda859032020-07-14 12:20:14 +0200528 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200529 }
530
531 /* no next collision found, return the record where it would be inserted */
532 if (empty) {
533 *last = empty;
534 } /* else (*last)->hits == 0, it is already correct */
Michal Vaskoda859032020-07-14 12:20:14 +0200535 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200536}
537
Michal Vaskoda859032020-07-14 12:20:14 +0200538/**
539 * @brief Search for a record with specific value and hash.
540 *
541 * @param[in] ht Hash table to search in.
542 * @param[in] val_p Pointer to the value to find.
543 * @param[in] hash Hash to find.
Radek Krejci857189e2020-09-01 13:26:36 +0200544 * @param[in] mod Whether the operation modifies the hash table (insert or remove) or not (find).
Michal Vaskoda859032020-07-14 12:20:14 +0200545 * @param[out] crec_p Optional found first record.
546 * @param[out] col Optional collision number of @p rec_p, 0 for no collision.
547 * @param[out] rec_p Found exact matching record, may be a collision of @p crec_p.
548 * @return LY_ENOTFOUND if no record found,
549 * @return LY_SUCCESS if record was found.
550 */
551static LY_ERR
Radek Krejci857189e2020-09-01 13:26:36 +0200552lyht_find_rec(struct hash_table *ht, void *val_p, uint32_t hash, ly_bool mod, struct ht_rec **crec_p, uint32_t *col,
Radek Krejci0f969882020-08-21 16:56:47 +0200553 struct ht_rec **rec_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200554{
555 struct ht_rec *rec, *crec;
556 uint32_t i, c;
Michal Vaskoda859032020-07-14 12:20:14 +0200557 LY_ERR r;
558
559 if (crec_p) {
560 *crec_p = NULL;
561 }
562 if (col) {
563 *col = 0;
564 }
565 *rec_p = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200566
567 if (lyht_find_first(ht, hash, &rec)) {
568 /* not found */
Michal Vaskoda859032020-07-14 12:20:14 +0200569 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200570 }
Michal Vaskoda859032020-07-14 12:20:14 +0200571 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200572 /* even the value matches */
Michal Vaskoda859032020-07-14 12:20:14 +0200573 if (crec_p) {
574 *crec_p = rec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200575 }
Michal Vaskoda859032020-07-14 12:20:14 +0200576 if (col) {
577 *col = 0;
578 }
579 *rec_p = rec;
580 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200581 }
582
583 /* some collisions, we need to go through them, too */
584 crec = rec;
Michal Vaskoda859032020-07-14 12:20:14 +0200585 c = crec->hits;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200586 for (i = 1; i < c; ++i) {
587 r = lyht_find_collision(ht, &rec, crec);
588 assert(!r);
589 (void)r;
590
591 /* compare values */
Michal Vaskoda859032020-07-14 12:20:14 +0200592 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
593 if (crec_p) {
594 *crec_p = crec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200595 }
Michal Vaskoda859032020-07-14 12:20:14 +0200596 if (col) {
597 *col = i;
598 }
599 *rec_p = rec;
600 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200601 }
602 }
603
604 /* not found even in collisions */
Michal Vaskoda859032020-07-14 12:20:14 +0200605 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200606}
607
Michal Vaskoda859032020-07-14 12:20:14 +0200608LY_ERR
609lyht_find(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
610{
611 struct ht_rec *rec;
612
613 lyht_find_rec(ht, val_p, hash, 0, NULL, NULL, &rec);
614
615 if (rec && match_p) {
616 *match_p = rec->val;
617 }
618 return rec ? LY_SUCCESS : LY_ENOTFOUND;
619}
620
621LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200622lyht_find_next(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
623{
624 struct ht_rec *rec, *crec;
625 uint32_t i, c;
Michal Vaskoda859032020-07-14 12:20:14 +0200626 LY_ERR r;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200627
Michal Vaskoda859032020-07-14 12:20:14 +0200628 /* found the record of the previously found value */
629 if (lyht_find_rec(ht, val_p, hash, 1, &crec, &i, &rec)) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200630 /* not found, cannot happen */
Michal Vaskoda859032020-07-14 12:20:14 +0200631 LOGINT_RET(NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200632 }
633
634 /* go through collisions and find next one after the previous one */
Michal Vaskoda859032020-07-14 12:20:14 +0200635 c = crec->hits;
636 for (++i; i < c; ++i) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200637 r = lyht_find_collision(ht, &rec, crec);
638 assert(!r);
639 (void)r;
640
Michal Vaskoda859032020-07-14 12:20:14 +0200641 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 0, ht->cb_data)) {
642 /* even the value matches */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200643 if (match_p) {
644 *match_p = rec->val;
645 }
Michal Vaskoda859032020-07-14 12:20:14 +0200646 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200647 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200648 }
649
650 /* the last equal value was already returned */
Michal Vaskoda859032020-07-14 12:20:14 +0200651 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200652}
653
654LY_ERR
Michal Vasko62524a92021-02-26 10:08:50 +0100655lyht_insert_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal,
656 void **match_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200657{
Radek Krejci1deb5be2020-08-26 16:43:36 +0200658 LY_ERR r, ret = LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200659 struct ht_rec *rec, *crec = NULL;
660 int32_t i;
Michal Vasko62524a92021-02-26 10:08:50 +0100661 lyht_value_equal_cb old_val_equal = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200662
663 if (!lyht_find_first(ht, hash, &rec)) {
664 /* we found matching shortened hash */
665 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
666 /* even the value matches */
667 if (match_p) {
668 *match_p = (void *)&rec->val;
669 }
670 return LY_EEXIST;
671 }
672
673 /* some collisions, we need to go through them, too */
674 crec = rec;
675 for (i = 1; i < crec->hits; ++i) {
676 r = lyht_find_collision(ht, &rec, crec);
677 assert(!r);
678
679 /* compare values */
680 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
681 if (match_p) {
682 *match_p = (void *)&rec->val;
683 }
684 return LY_EEXIST;
685 }
686 }
687
688 /* value not found, get the record where it will be inserted */
689 r = lyht_find_collision(ht, &rec, crec);
690 assert(r);
691 }
692
693 /* insert it into the returned record */
694 assert(rec->hits < 1);
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200695 if (rec->hits < 0) {
696 --ht->invalid;
697 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200698 rec->hash = hash;
699 rec->hits = 1;
700 memcpy(&rec->val, val_p, ht->rec_size - (sizeof(struct ht_rec) - 1));
701 if (match_p) {
702 *match_p = (void *)&rec->val;
703 }
704
705 if (crec) {
706 /* there was a collision, increase hits */
707 if (crec->hits == INT32_MAX) {
708 LOGINT(NULL);
709 }
710 ++crec->hits;
711 }
712
713 /* check size & enlarge if needed */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200714 ++ht->used;
715 if (ht->resize) {
Radek Krejcif13b87b2020-12-01 22:02:17 +0100716 r = (ht->used * LYHT_HUNDRED_PERCENTAGE) / ht->size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200717 if ((ht->resize == 1) && (r >= LYHT_FIRST_SHRINK_PERCENTAGE)) {
718 /* enable shrinking */
719 ht->resize = 2;
720 }
721 if ((ht->resize == 2) && (r >= LYHT_ENLARGE_PERCENTAGE)) {
722 if (resize_val_equal) {
723 old_val_equal = lyht_set_cb(ht, resize_val_equal);
724 }
725
726 /* enlarge */
727 ret = lyht_resize(ht, 1);
728 /* if hash_table was resized, we need to find new matching value */
Michal Vasko69730152020-10-09 16:30:07 +0200729 if ((ret == LY_SUCCESS) && match_p) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200730 lyht_find(ht, val_p, hash, match_p);
731 }
732
733 if (resize_val_equal) {
734 lyht_set_cb(ht, old_val_equal);
735 }
736 }
737 }
738 return ret;
739}
740
Radek Krejci0ae092d2018-09-20 16:43:19 +0200741LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200742lyht_insert(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
743{
744 return lyht_insert_with_resize_cb(ht, val_p, hash, NULL, match_p);
745}
746
747LY_ERR
Michal Vasko62524a92021-02-26 10:08:50 +0100748lyht_remove_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200749{
750 struct ht_rec *rec, *crec;
751 int32_t i;
Radek Krejci857189e2020-09-01 13:26:36 +0200752 ly_bool first_matched = 0;
Radek Krejci1deb5be2020-08-26 16:43:36 +0200753 LY_ERR r, ret = LY_SUCCESS;
Michal Vasko62524a92021-02-26 10:08:50 +0100754 lyht_value_equal_cb old_val_equal;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200755
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200756 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 +0200757
758 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
759 /* even the value matches */
760 first_matched = 1;
761 }
762
763 /* we always need to go through collisions */
764 crec = rec;
765 for (i = 1; i < crec->hits; ++i) {
766 r = lyht_find_collision(ht, &rec, crec);
767 assert(!r);
768
769 /* compare values */
770 if (!first_matched && (rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
771 break;
772 }
773 }
774
775 if (i < crec->hits) {
776 /* one of collisions matched, reduce collision count, remove the record */
777 assert(!first_matched);
778 --crec->hits;
779 rec->hits = -1;
780 } else if (first_matched) {
781 /* the first record matches */
782 if (crec != rec) {
783 /* ... so put the last collision in its place */
784 rec->hits = crec->hits - 1;
785 memcpy(crec, rec, ht->rec_size);
786 }
787 rec->hits = -1;
788 } else {
789 /* value not found even in collisions */
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200790 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200791 }
792
793 /* check size & shrink if needed */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200794 --ht->used;
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200795 ++ht->invalid;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200796 if (ht->resize == 2) {
Radek Krejcif13b87b2020-12-01 22:02:17 +0100797 r = (ht->used * LYHT_HUNDRED_PERCENTAGE) / ht->size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200798 if ((r < LYHT_SHRINK_PERCENTAGE) && (ht->size > LYHT_MIN_SIZE)) {
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200799 if (resize_val_equal) {
800 old_val_equal = lyht_set_cb(ht, resize_val_equal);
801 }
802
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200803 /* shrink */
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200804 ret = lyht_resize(ht, -1);
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200805
806 if (resize_val_equal) {
807 lyht_set_cb(ht, old_val_equal);
808 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200809 }
810 }
811
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200812 /* rehash all records if needed */
813 r = ((ht->size - ht->used - ht->invalid) * 100) / ht->size;
814 if (r < LYHT_REHASH_PERCENTAGE) {
815 if (resize_val_equal) {
816 old_val_equal = lyht_set_cb(ht, resize_val_equal);
817 }
818
819 /* rehash */
820 ret = lyht_resize(ht, 0);
821
822 if (resize_val_equal) {
823 lyht_set_cb(ht, old_val_equal);
824 }
825 }
826
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200827 return ret;
828}
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200829
830LY_ERR
831lyht_remove(struct hash_table *ht, void *val_p, uint32_t hash)
832{
833 return lyht_remove_with_resize_cb(ht, val_p, hash, NULL);
834}