blob: 7b7ac142e652cc4bfa7dc596983b75b78708279b [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
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;
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);
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
Radek Krejci2d7a47b2019-05-16 13:34:10 +0200307struct ht_rec *
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200308lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx)
309{
310 return (struct ht_rec *)&recs[idx * rec_size];
311}
312
313struct hash_table *
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{
316 struct hash_table *ht;
317
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
337 ht->rec_size = (sizeof(struct ht_rec) - 1) + val_size;
338 /* 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
346lyht_set_cb(struct hash_table *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 *
356lyht_set_cb_data(struct hash_table *ht, void *new_cb_data)
357{
358 void *prev;
359
360 prev = ht->cb_data;
361 ht->cb_data = new_cb_data;
362 return prev;
363}
364
365struct hash_table *
366lyht_dup(const struct hash_table *orig)
367{
368 struct hash_table *ht;
369
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200370 LY_CHECK_ARG_RET(NULL, orig, NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200371
372 ht = lyht_new(orig->size, orig->rec_size - (sizeof(struct ht_rec) - 1), orig->val_equal, orig->cb_data, orig->resize ? 1 : 0);
373 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
384lyht_free(struct hash_table *ht)
385{
386 if (ht) {
387 free(ht->recs);
388 free(ht);
389 }
390}
391
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200392/**
393 * @brief Resize a hash table.
394 *
395 * @param[in] ht Hash table to resize.
396 * @param[in] operation Operation to perform. 1 to enlarge, -1 to shrink, 0 to only rehash all records.
397 * @return LY_ERR value.
398 */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200399static LY_ERR
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200400lyht_resize(struct hash_table *ht, int operation)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200401{
402 struct ht_rec *rec;
403 unsigned char *old_recs;
404 uint32_t i, old_size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200405
406 old_recs = ht->recs;
407 old_size = ht->size;
408
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200409 if (operation > 0) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200410 /* double the size */
411 ht->size <<= 1;
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200412 } else if (operation < 0) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200413 /* half the size */
414 ht->size >>= 1;
415 }
416
417 ht->recs = calloc(ht->size, ht->rec_size);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200418 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 +0200419
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200420 /* reset used and invalid, it will increase again */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200421 ht->used = 0;
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200422 ht->invalid = 0;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200423
424 /* add all the old records into the new records array */
425 for (i = 0; i < old_size; ++i) {
426 rec = lyht_get_rec(old_recs, ht->rec_size, i);
427 if (rec->hits > 0) {
Radek Krejci1deb5be2020-08-26 16:43:36 +0200428 LY_ERR ret = lyht_insert(ht, rec->val, rec->hash, NULL);
Michal Vasko26bbb272022-08-02 14:54:33 +0200429
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200430 assert(!ret);
431 (void)ret;
432 }
433 }
434
435 /* final touches */
436 free(old_recs);
437 return LY_SUCCESS;
438}
439
Michal Vaskoda859032020-07-14 12:20:14 +0200440/**
441 * @brief Search for the first match.
442 *
443 * @param[in] ht Hash table to search in.
444 * @param[in] hash Hash to find.
445 * @param[out] rec_p Optional found record.
446 * @return LY_SUCCESS hash found, returned its record,
447 * @return LY_ENOTFOUND hash not found, returned the record where it would be inserted.
448 */
449static LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200450lyht_find_first(struct hash_table *ht, uint32_t hash, struct ht_rec **rec_p)
451{
452 struct ht_rec *rec;
453 uint32_t i, idx;
454
455 if (rec_p) {
456 *rec_p = NULL;
457 }
458
459 idx = i = hash & (ht->size - 1);
460 rec = lyht_get_rec(ht->recs, ht->rec_size, idx);
461
462 /* skip through overflow and deleted records */
463 while ((rec->hits != 0) && ((rec->hits == -1) || ((rec->hash & (ht->size - 1)) != idx))) {
464 if ((rec->hits == -1) && rec_p && !(*rec_p)) {
465 /* remember this record for return */
466 *rec_p = rec;
467 }
468 i = (i + 1) % ht->size;
469 if (i == idx) {
470 /* we went through all the records (very unlikely, but possible when many records are invalid),
471 * just return not found */
472 assert(!rec_p || *rec_p);
Michal Vaskoda859032020-07-14 12:20:14 +0200473 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200474 }
475 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
476 }
477 if (rec->hits == 0) {
478 /* we could not find the value */
479 if (rec_p && !*rec_p) {
480 *rec_p = rec;
481 }
Michal Vaskoda859032020-07-14 12:20:14 +0200482 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200483 }
484
485 /* we have found a record with equal (shortened) hash */
486 if (rec_p) {
487 *rec_p = rec;
488 }
Michal Vaskoda859032020-07-14 12:20:14 +0200489 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200490}
491
492/**
493 * @brief Search for the next collision.
494 *
495 * @param[in] ht Hash table to search in.
496 * @param[in,out] last Last returned collision record.
497 * @param[in] first First collision record (hits > 1).
Michal Vaskoda859032020-07-14 12:20:14 +0200498 * @return LY_SUCCESS when hash collision found, \p last points to this next collision,
499 * @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 +0200500 */
Michal Vaskoda859032020-07-14 12:20:14 +0200501static LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200502lyht_find_collision(struct hash_table *ht, struct ht_rec **last, struct ht_rec *first)
503{
504 struct ht_rec *empty = NULL;
505 uint32_t i, idx;
506
507 assert(last && *last);
508
509 idx = (*last)->hash & (ht->size - 1);
510 i = (((unsigned char *)*last) - ht->recs) / ht->rec_size;
511
512 do {
513 i = (i + 1) % ht->size;
514 *last = lyht_get_rec(ht->recs, ht->rec_size, i);
515 if (*last == first) {
516 /* we went through all the records (very unlikely, but possible when many records are invalid),
517 * just return an invalid record */
518 assert(empty);
519 *last = empty;
Michal Vaskoda859032020-07-14 12:20:14 +0200520 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200521 }
522
523 if (((*last)->hits == -1) && !empty) {
524 empty = *last;
525 }
526 } while (((*last)->hits != 0) && (((*last)->hits == -1) || (((*last)->hash & (ht->size - 1)) != idx)));
527
528 if ((*last)->hits > 0) {
529 /* we found a collision */
530 assert((*last)->hits == 1);
Michal Vaskoda859032020-07-14 12:20:14 +0200531 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200532 }
533
534 /* no next collision found, return the record where it would be inserted */
535 if (empty) {
536 *last = empty;
537 } /* else (*last)->hits == 0, it is already correct */
Michal Vaskoda859032020-07-14 12:20:14 +0200538 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200539}
540
Michal Vaskoda859032020-07-14 12:20:14 +0200541/**
542 * @brief Search for a record with specific value and hash.
543 *
544 * @param[in] ht Hash table to search in.
545 * @param[in] val_p Pointer to the value to find.
546 * @param[in] hash Hash to find.
Radek Krejci857189e2020-09-01 13:26:36 +0200547 * @param[in] mod Whether the operation modifies the hash table (insert or remove) or not (find).
Michal Vaskoda859032020-07-14 12:20:14 +0200548 * @param[out] crec_p Optional found first record.
549 * @param[out] col Optional collision number of @p rec_p, 0 for no collision.
550 * @param[out] rec_p Found exact matching record, may be a collision of @p crec_p.
551 * @return LY_ENOTFOUND if no record found,
552 * @return LY_SUCCESS if record was found.
553 */
554static LY_ERR
Radek Krejci857189e2020-09-01 13:26:36 +0200555lyht_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 +0200556 struct ht_rec **rec_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200557{
558 struct ht_rec *rec, *crec;
559 uint32_t i, c;
Michal Vaskoda859032020-07-14 12:20:14 +0200560 LY_ERR r;
561
562 if (crec_p) {
563 *crec_p = NULL;
564 }
565 if (col) {
566 *col = 0;
567 }
568 *rec_p = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200569
570 if (lyht_find_first(ht, hash, &rec)) {
571 /* not found */
Michal Vaskoda859032020-07-14 12:20:14 +0200572 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200573 }
Michal Vaskoda859032020-07-14 12:20:14 +0200574 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200575 /* even the value matches */
Michal Vaskoda859032020-07-14 12:20:14 +0200576 if (crec_p) {
577 *crec_p = rec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200578 }
Michal Vaskoda859032020-07-14 12:20:14 +0200579 if (col) {
580 *col = 0;
581 }
582 *rec_p = rec;
583 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200584 }
585
586 /* some collisions, we need to go through them, too */
587 crec = rec;
Michal Vaskoda859032020-07-14 12:20:14 +0200588 c = crec->hits;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200589 for (i = 1; i < c; ++i) {
590 r = lyht_find_collision(ht, &rec, crec);
591 assert(!r);
592 (void)r;
593
594 /* compare values */
Michal Vaskoda859032020-07-14 12:20:14 +0200595 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
596 if (crec_p) {
597 *crec_p = crec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200598 }
Michal Vaskoda859032020-07-14 12:20:14 +0200599 if (col) {
600 *col = i;
601 }
602 *rec_p = rec;
603 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200604 }
605 }
606
607 /* not found even in collisions */
Michal Vaskoda859032020-07-14 12:20:14 +0200608 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200609}
610
Michal Vaskoda859032020-07-14 12:20:14 +0200611LY_ERR
612lyht_find(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
613{
614 struct ht_rec *rec;
615
616 lyht_find_rec(ht, val_p, hash, 0, NULL, NULL, &rec);
617
618 if (rec && match_p) {
619 *match_p = rec->val;
620 }
621 return rec ? LY_SUCCESS : LY_ENOTFOUND;
622}
623
624LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200625lyht_find_next(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
626{
627 struct ht_rec *rec, *crec;
628 uint32_t i, c;
Michal Vaskoda859032020-07-14 12:20:14 +0200629 LY_ERR r;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200630
Michal Vaskoda859032020-07-14 12:20:14 +0200631 /* found the record of the previously found value */
632 if (lyht_find_rec(ht, val_p, hash, 1, &crec, &i, &rec)) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200633 /* not found, cannot happen */
Michal Vaskoda859032020-07-14 12:20:14 +0200634 LOGINT_RET(NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200635 }
636
637 /* go through collisions and find next one after the previous one */
Michal Vaskoda859032020-07-14 12:20:14 +0200638 c = crec->hits;
639 for (++i; i < c; ++i) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200640 r = lyht_find_collision(ht, &rec, crec);
641 assert(!r);
642 (void)r;
643
Michal Vaskoda859032020-07-14 12:20:14 +0200644 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 0, ht->cb_data)) {
645 /* even the value matches */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200646 if (match_p) {
647 *match_p = rec->val;
648 }
Michal Vaskoda859032020-07-14 12:20:14 +0200649 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200650 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200651 }
652
653 /* the last equal value was already returned */
Michal Vaskoda859032020-07-14 12:20:14 +0200654 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200655}
656
657LY_ERR
Michal Vasko62524a92021-02-26 10:08:50 +0100658lyht_insert_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal,
659 void **match_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200660{
Radek Krejci1deb5be2020-08-26 16:43:36 +0200661 LY_ERR r, ret = LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200662 struct ht_rec *rec, *crec = NULL;
663 int32_t i;
Michal Vasko62524a92021-02-26 10:08:50 +0100664 lyht_value_equal_cb old_val_equal = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200665
666 if (!lyht_find_first(ht, hash, &rec)) {
667 /* we found matching shortened hash */
668 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
669 /* even the value matches */
670 if (match_p) {
671 *match_p = (void *)&rec->val;
672 }
673 return LY_EEXIST;
674 }
675
676 /* some collisions, we need to go through them, too */
677 crec = rec;
678 for (i = 1; i < crec->hits; ++i) {
679 r = lyht_find_collision(ht, &rec, crec);
680 assert(!r);
681
682 /* compare values */
683 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
684 if (match_p) {
685 *match_p = (void *)&rec->val;
686 }
687 return LY_EEXIST;
688 }
689 }
690
691 /* value not found, get the record where it will be inserted */
692 r = lyht_find_collision(ht, &rec, crec);
693 assert(r);
694 }
695
696 /* insert it into the returned record */
697 assert(rec->hits < 1);
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200698 if (rec->hits < 0) {
699 --ht->invalid;
700 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200701 rec->hash = hash;
702 rec->hits = 1;
703 memcpy(&rec->val, val_p, ht->rec_size - (sizeof(struct ht_rec) - 1));
704 if (match_p) {
705 *match_p = (void *)&rec->val;
706 }
707
708 if (crec) {
709 /* there was a collision, increase hits */
710 if (crec->hits == INT32_MAX) {
711 LOGINT(NULL);
712 }
713 ++crec->hits;
714 }
715
716 /* check size & enlarge if needed */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200717 ++ht->used;
718 if (ht->resize) {
Radek Krejcif13b87b2020-12-01 22:02:17 +0100719 r = (ht->used * LYHT_HUNDRED_PERCENTAGE) / ht->size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200720 if ((ht->resize == 1) && (r >= LYHT_FIRST_SHRINK_PERCENTAGE)) {
721 /* enable shrinking */
722 ht->resize = 2;
723 }
724 if ((ht->resize == 2) && (r >= LYHT_ENLARGE_PERCENTAGE)) {
725 if (resize_val_equal) {
726 old_val_equal = lyht_set_cb(ht, resize_val_equal);
727 }
728
729 /* enlarge */
730 ret = lyht_resize(ht, 1);
731 /* if hash_table was resized, we need to find new matching value */
Michal Vasko69730152020-10-09 16:30:07 +0200732 if ((ret == LY_SUCCESS) && match_p) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200733 lyht_find(ht, val_p, hash, match_p);
734 }
735
736 if (resize_val_equal) {
737 lyht_set_cb(ht, old_val_equal);
738 }
739 }
740 }
741 return ret;
742}
743
Radek Krejci0ae092d2018-09-20 16:43:19 +0200744LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200745lyht_insert(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
746{
747 return lyht_insert_with_resize_cb(ht, val_p, hash, NULL, match_p);
748}
749
750LY_ERR
Michal Vasko62524a92021-02-26 10:08:50 +0100751lyht_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 +0200752{
753 struct ht_rec *rec, *crec;
754 int32_t i;
Radek Krejci857189e2020-09-01 13:26:36 +0200755 ly_bool first_matched = 0;
Radek Krejci1deb5be2020-08-26 16:43:36 +0200756 LY_ERR r, ret = LY_SUCCESS;
Michal Vasko62524a92021-02-26 10:08:50 +0100757 lyht_value_equal_cb old_val_equal;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200758
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200759 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 +0200760
761 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
762 /* even the value matches */
763 first_matched = 1;
764 }
765
766 /* we always need to go through collisions */
767 crec = rec;
768 for (i = 1; i < crec->hits; ++i) {
769 r = lyht_find_collision(ht, &rec, crec);
770 assert(!r);
771
772 /* compare values */
773 if (!first_matched && (rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
774 break;
775 }
776 }
777
778 if (i < crec->hits) {
779 /* one of collisions matched, reduce collision count, remove the record */
780 assert(!first_matched);
781 --crec->hits;
782 rec->hits = -1;
783 } else if (first_matched) {
784 /* the first record matches */
785 if (crec != rec) {
786 /* ... so put the last collision in its place */
787 rec->hits = crec->hits - 1;
788 memcpy(crec, rec, ht->rec_size);
789 }
790 rec->hits = -1;
791 } else {
792 /* value not found even in collisions */
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200793 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200794 }
795
796 /* check size & shrink if needed */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200797 --ht->used;
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200798 ++ht->invalid;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200799 if (ht->resize == 2) {
Radek Krejcif13b87b2020-12-01 22:02:17 +0100800 r = (ht->used * LYHT_HUNDRED_PERCENTAGE) / ht->size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200801 if ((r < LYHT_SHRINK_PERCENTAGE) && (ht->size > LYHT_MIN_SIZE)) {
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200802 if (resize_val_equal) {
803 old_val_equal = lyht_set_cb(ht, resize_val_equal);
804 }
805
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200806 /* shrink */
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200807 ret = lyht_resize(ht, -1);
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200808
809 if (resize_val_equal) {
810 lyht_set_cb(ht, old_val_equal);
811 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200812 }
813 }
814
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200815 /* rehash all records if needed */
816 r = ((ht->size - ht->used - ht->invalid) * 100) / ht->size;
817 if (r < LYHT_REHASH_PERCENTAGE) {
818 if (resize_val_equal) {
819 old_val_equal = lyht_set_cb(ht, resize_val_equal);
820 }
821
822 /* rehash */
823 ret = lyht_resize(ht, 0);
824
825 if (resize_val_equal) {
826 lyht_set_cb(ht, old_val_equal);
827 }
828 }
829
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200830 return ret;
831}
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200832
833LY_ERR
834lyht_remove(struct hash_table *ht, void *val_p, uint32_t hash)
835{
836 return lyht_remove_with_resize_cb(ht, val_p, hash, NULL);
837}
Michal Vasko626196f2022-08-05 12:49:52 +0200838
839uint32_t
840lyht_get_fixed_size(uint32_t item_count)
841{
842 uint32_t i, size = 0;
843
844 /* detect number of upper zero bits in the items' counter value ... */
845 for (i = (sizeof item_count * CHAR_BIT) - 1; i > 0; i--) {
846 size = item_count << i;
847 size = size >> i;
848 if (size == item_count) {
849 break;
850 }
851 }
852 assert(i);
853
854 /* ... and then we convert it to the position of the highest non-zero bit ... */
855 i = (sizeof item_count * CHAR_BIT) - i;
856
857 /* ... and by using it to shift 1 to the left we get the closest sufficient hash table size */
858 size = 1 << i;
859
860 return size;
861}