blob: d0c039a2fa9e78c1859fd00f99a66e7b9b2eda76 [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átc6e39de2021-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átc6e39de2021-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átc6e39de2021-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);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200429 assert(!ret);
430 (void)ret;
431 }
432 }
433
434 /* final touches */
435 free(old_recs);
436 return LY_SUCCESS;
437}
438
Michal Vaskoda859032020-07-14 12:20:14 +0200439/**
440 * @brief Search for the first match.
441 *
442 * @param[in] ht Hash table to search in.
443 * @param[in] hash Hash to find.
444 * @param[out] rec_p Optional found record.
445 * @return LY_SUCCESS hash found, returned its record,
446 * @return LY_ENOTFOUND hash not found, returned the record where it would be inserted.
447 */
448static LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200449lyht_find_first(struct hash_table *ht, uint32_t hash, struct ht_rec **rec_p)
450{
451 struct ht_rec *rec;
452 uint32_t i, idx;
453
454 if (rec_p) {
455 *rec_p = NULL;
456 }
457
458 idx = i = hash & (ht->size - 1);
459 rec = lyht_get_rec(ht->recs, ht->rec_size, idx);
460
461 /* skip through overflow and deleted records */
462 while ((rec->hits != 0) && ((rec->hits == -1) || ((rec->hash & (ht->size - 1)) != idx))) {
463 if ((rec->hits == -1) && rec_p && !(*rec_p)) {
464 /* remember this record for return */
465 *rec_p = rec;
466 }
467 i = (i + 1) % ht->size;
468 if (i == idx) {
469 /* we went through all the records (very unlikely, but possible when many records are invalid),
470 * just return not found */
471 assert(!rec_p || *rec_p);
Michal Vaskoda859032020-07-14 12:20:14 +0200472 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200473 }
474 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
475 }
476 if (rec->hits == 0) {
477 /* we could not find the value */
478 if (rec_p && !*rec_p) {
479 *rec_p = rec;
480 }
Michal Vaskoda859032020-07-14 12:20:14 +0200481 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200482 }
483
484 /* we have found a record with equal (shortened) hash */
485 if (rec_p) {
486 *rec_p = rec;
487 }
Michal Vaskoda859032020-07-14 12:20:14 +0200488 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200489}
490
491/**
492 * @brief Search for the next collision.
493 *
494 * @param[in] ht Hash table to search in.
495 * @param[in,out] last Last returned collision record.
496 * @param[in] first First collision record (hits > 1).
Michal Vaskoda859032020-07-14 12:20:14 +0200497 * @return LY_SUCCESS when hash collision found, \p last points to this next collision,
498 * @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 +0200499 */
Michal Vaskoda859032020-07-14 12:20:14 +0200500static LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200501lyht_find_collision(struct hash_table *ht, struct ht_rec **last, struct ht_rec *first)
502{
503 struct ht_rec *empty = NULL;
504 uint32_t i, idx;
505
506 assert(last && *last);
507
508 idx = (*last)->hash & (ht->size - 1);
509 i = (((unsigned char *)*last) - ht->recs) / ht->rec_size;
510
511 do {
512 i = (i + 1) % ht->size;
513 *last = lyht_get_rec(ht->recs, ht->rec_size, i);
514 if (*last == first) {
515 /* we went through all the records (very unlikely, but possible when many records are invalid),
516 * just return an invalid record */
517 assert(empty);
518 *last = empty;
Michal Vaskoda859032020-07-14 12:20:14 +0200519 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200520 }
521
522 if (((*last)->hits == -1) && !empty) {
523 empty = *last;
524 }
525 } while (((*last)->hits != 0) && (((*last)->hits == -1) || (((*last)->hash & (ht->size - 1)) != idx)));
526
527 if ((*last)->hits > 0) {
528 /* we found a collision */
529 assert((*last)->hits == 1);
Michal Vaskoda859032020-07-14 12:20:14 +0200530 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200531 }
532
533 /* no next collision found, return the record where it would be inserted */
534 if (empty) {
535 *last = empty;
536 } /* else (*last)->hits == 0, it is already correct */
Michal Vaskoda859032020-07-14 12:20:14 +0200537 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200538}
539
Michal Vaskoda859032020-07-14 12:20:14 +0200540/**
541 * @brief Search for a record with specific value and hash.
542 *
543 * @param[in] ht Hash table to search in.
544 * @param[in] val_p Pointer to the value to find.
545 * @param[in] hash Hash to find.
Radek Krejci857189e2020-09-01 13:26:36 +0200546 * @param[in] mod Whether the operation modifies the hash table (insert or remove) or not (find).
Michal Vaskoda859032020-07-14 12:20:14 +0200547 * @param[out] crec_p Optional found first record.
548 * @param[out] col Optional collision number of @p rec_p, 0 for no collision.
549 * @param[out] rec_p Found exact matching record, may be a collision of @p crec_p.
550 * @return LY_ENOTFOUND if no record found,
551 * @return LY_SUCCESS if record was found.
552 */
553static LY_ERR
Radek Krejci857189e2020-09-01 13:26:36 +0200554lyht_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 +0200555 struct ht_rec **rec_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200556{
557 struct ht_rec *rec, *crec;
558 uint32_t i, c;
Michal Vaskoda859032020-07-14 12:20:14 +0200559 LY_ERR r;
560
561 if (crec_p) {
562 *crec_p = NULL;
563 }
564 if (col) {
565 *col = 0;
566 }
567 *rec_p = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200568
569 if (lyht_find_first(ht, hash, &rec)) {
570 /* not found */
Michal Vaskoda859032020-07-14 12:20:14 +0200571 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200572 }
Michal Vaskoda859032020-07-14 12:20:14 +0200573 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200574 /* even the value matches */
Michal Vaskoda859032020-07-14 12:20:14 +0200575 if (crec_p) {
576 *crec_p = rec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200577 }
Michal Vaskoda859032020-07-14 12:20:14 +0200578 if (col) {
579 *col = 0;
580 }
581 *rec_p = rec;
582 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200583 }
584
585 /* some collisions, we need to go through them, too */
586 crec = rec;
Michal Vaskoda859032020-07-14 12:20:14 +0200587 c = crec->hits;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200588 for (i = 1; i < c; ++i) {
589 r = lyht_find_collision(ht, &rec, crec);
590 assert(!r);
591 (void)r;
592
593 /* compare values */
Michal Vaskoda859032020-07-14 12:20:14 +0200594 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
595 if (crec_p) {
596 *crec_p = crec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200597 }
Michal Vaskoda859032020-07-14 12:20:14 +0200598 if (col) {
599 *col = i;
600 }
601 *rec_p = rec;
602 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200603 }
604 }
605
606 /* not found even in collisions */
Michal Vaskoda859032020-07-14 12:20:14 +0200607 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200608}
609
Michal Vaskoda859032020-07-14 12:20:14 +0200610LY_ERR
611lyht_find(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
612{
613 struct ht_rec *rec;
614
615 lyht_find_rec(ht, val_p, hash, 0, NULL, NULL, &rec);
616
617 if (rec && match_p) {
618 *match_p = rec->val;
619 }
620 return rec ? LY_SUCCESS : LY_ENOTFOUND;
621}
622
623LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200624lyht_find_next(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
625{
626 struct ht_rec *rec, *crec;
627 uint32_t i, c;
Michal Vaskoda859032020-07-14 12:20:14 +0200628 LY_ERR r;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200629
Michal Vaskoda859032020-07-14 12:20:14 +0200630 /* found the record of the previously found value */
631 if (lyht_find_rec(ht, val_p, hash, 1, &crec, &i, &rec)) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200632 /* not found, cannot happen */
Michal Vaskoda859032020-07-14 12:20:14 +0200633 LOGINT_RET(NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200634 }
635
636 /* go through collisions and find next one after the previous one */
Michal Vaskoda859032020-07-14 12:20:14 +0200637 c = crec->hits;
638 for (++i; i < c; ++i) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200639 r = lyht_find_collision(ht, &rec, crec);
640 assert(!r);
641 (void)r;
642
Michal Vaskoda859032020-07-14 12:20:14 +0200643 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 0, ht->cb_data)) {
644 /* even the value matches */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200645 if (match_p) {
646 *match_p = rec->val;
647 }
Michal Vaskoda859032020-07-14 12:20:14 +0200648 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200649 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200650 }
651
652 /* the last equal value was already returned */
Michal Vaskoda859032020-07-14 12:20:14 +0200653 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200654}
655
656LY_ERR
Michal Vasko62524a92021-02-26 10:08:50 +0100657lyht_insert_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal,
658 void **match_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200659{
Radek Krejci1deb5be2020-08-26 16:43:36 +0200660 LY_ERR r, ret = LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200661 struct ht_rec *rec, *crec = NULL;
662 int32_t i;
Michal Vasko62524a92021-02-26 10:08:50 +0100663 lyht_value_equal_cb old_val_equal = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200664
665 if (!lyht_find_first(ht, hash, &rec)) {
666 /* we found matching shortened hash */
667 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
668 /* even the value matches */
669 if (match_p) {
670 *match_p = (void *)&rec->val;
671 }
672 return LY_EEXIST;
673 }
674
675 /* some collisions, we need to go through them, too */
676 crec = rec;
677 for (i = 1; i < crec->hits; ++i) {
678 r = lyht_find_collision(ht, &rec, crec);
679 assert(!r);
680
681 /* compare values */
682 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
683 if (match_p) {
684 *match_p = (void *)&rec->val;
685 }
686 return LY_EEXIST;
687 }
688 }
689
690 /* value not found, get the record where it will be inserted */
691 r = lyht_find_collision(ht, &rec, crec);
692 assert(r);
693 }
694
695 /* insert it into the returned record */
696 assert(rec->hits < 1);
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200697 if (rec->hits < 0) {
698 --ht->invalid;
699 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200700 rec->hash = hash;
701 rec->hits = 1;
702 memcpy(&rec->val, val_p, ht->rec_size - (sizeof(struct ht_rec) - 1));
703 if (match_p) {
704 *match_p = (void *)&rec->val;
705 }
706
707 if (crec) {
708 /* there was a collision, increase hits */
709 if (crec->hits == INT32_MAX) {
710 LOGINT(NULL);
711 }
712 ++crec->hits;
713 }
714
715 /* check size & enlarge if needed */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200716 ++ht->used;
717 if (ht->resize) {
Radek Krejcif13b87b2020-12-01 22:02:17 +0100718 r = (ht->used * LYHT_HUNDRED_PERCENTAGE) / ht->size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200719 if ((ht->resize == 1) && (r >= LYHT_FIRST_SHRINK_PERCENTAGE)) {
720 /* enable shrinking */
721 ht->resize = 2;
722 }
723 if ((ht->resize == 2) && (r >= LYHT_ENLARGE_PERCENTAGE)) {
724 if (resize_val_equal) {
725 old_val_equal = lyht_set_cb(ht, resize_val_equal);
726 }
727
728 /* enlarge */
729 ret = lyht_resize(ht, 1);
730 /* if hash_table was resized, we need to find new matching value */
Michal Vasko69730152020-10-09 16:30:07 +0200731 if ((ret == LY_SUCCESS) && match_p) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200732 lyht_find(ht, val_p, hash, match_p);
733 }
734
735 if (resize_val_equal) {
736 lyht_set_cb(ht, old_val_equal);
737 }
738 }
739 }
740 return ret;
741}
742
Radek Krejci0ae092d2018-09-20 16:43:19 +0200743LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200744lyht_insert(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
745{
746 return lyht_insert_with_resize_cb(ht, val_p, hash, NULL, match_p);
747}
748
749LY_ERR
Michal Vasko62524a92021-02-26 10:08:50 +0100750lyht_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 +0200751{
752 struct ht_rec *rec, *crec;
753 int32_t i;
Radek Krejci857189e2020-09-01 13:26:36 +0200754 ly_bool first_matched = 0;
Radek Krejci1deb5be2020-08-26 16:43:36 +0200755 LY_ERR r, ret = LY_SUCCESS;
Michal Vasko62524a92021-02-26 10:08:50 +0100756 lyht_value_equal_cb old_val_equal;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200757
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200758 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 +0200759
760 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
761 /* even the value matches */
762 first_matched = 1;
763 }
764
765 /* we always need to go through collisions */
766 crec = rec;
767 for (i = 1; i < crec->hits; ++i) {
768 r = lyht_find_collision(ht, &rec, crec);
769 assert(!r);
770
771 /* compare values */
772 if (!first_matched && (rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
773 break;
774 }
775 }
776
777 if (i < crec->hits) {
778 /* one of collisions matched, reduce collision count, remove the record */
779 assert(!first_matched);
780 --crec->hits;
781 rec->hits = -1;
782 } else if (first_matched) {
783 /* the first record matches */
784 if (crec != rec) {
785 /* ... so put the last collision in its place */
786 rec->hits = crec->hits - 1;
787 memcpy(crec, rec, ht->rec_size);
788 }
789 rec->hits = -1;
790 } else {
791 /* value not found even in collisions */
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200792 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200793 }
794
795 /* check size & shrink if needed */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200796 --ht->used;
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200797 ++ht->invalid;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200798 if (ht->resize == 2) {
Radek Krejcif13b87b2020-12-01 22:02:17 +0100799 r = (ht->used * LYHT_HUNDRED_PERCENTAGE) / ht->size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200800 if ((r < LYHT_SHRINK_PERCENTAGE) && (ht->size > LYHT_MIN_SIZE)) {
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200801 if (resize_val_equal) {
802 old_val_equal = lyht_set_cb(ht, resize_val_equal);
803 }
804
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200805 /* shrink */
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200806 ret = lyht_resize(ht, -1);
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200807
808 if (resize_val_equal) {
809 lyht_set_cb(ht, old_val_equal);
810 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200811 }
812 }
813
Michal Vaskodc95d9c2021-04-12 15:11:48 +0200814 /* rehash all records if needed */
815 r = ((ht->size - ht->used - ht->invalid) * 100) / ht->size;
816 if (r < LYHT_REHASH_PERCENTAGE) {
817 if (resize_val_equal) {
818 old_val_equal = lyht_set_cb(ht, resize_val_equal);
819 }
820
821 /* rehash */
822 ret = lyht_resize(ht, 0);
823
824 if (resize_val_equal) {
825 lyht_set_cb(ht, old_val_equal);
826 }
827 }
828
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200829 return ret;
830}
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200831
832LY_ERR
833lyht_remove(struct hash_table *ht, void *val_p, uint32_t hash)
834{
835 return lyht_remove_with_resize_cb(ht, val_p, hash, NULL);
836}