blob: e771006c14719ede9dd16d1f7c12844d98e1550d [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 *
33 * Implementation of ::values_equal_cb.
34 */
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
105 if (key_part) {
106 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 Vasko0f6b3e22018-09-07 12:18:12 +0200168 if (!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
Michal Vaskoe180ed02021-02-05 16:31:20 +0100221 LOGDBG(LY_LDGDICT, "inserting \"%.*s\"", len, value);
222
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 *
Radek Krejci1deb5be2020-08-26 16:43:36 +0200312lyht_new(uint32_t size, uint16_t val_size, values_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;
330 ht->val_equal = val_equal;
331 ht->cb_data = cb_data;
Radek Krejci1deb5be2020-08-26 16:43:36 +0200332 ht->resize = resize;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200333
334 ht->rec_size = (sizeof(struct ht_rec) - 1) + val_size;
335 /* allocate the records correctly */
336 ht->recs = calloc(size, ht->rec_size);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200337 LY_CHECK_ERR_RET(!ht->recs, free(ht); LOGMEM(NULL), NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200338
339 return ht;
340}
341
342values_equal_cb
343lyht_set_cb(struct hash_table *ht, values_equal_cb new_val_equal)
344{
345 values_equal_cb prev;
346
347 prev = ht->val_equal;
348 ht->val_equal = new_val_equal;
349 return prev;
350}
351
352void *
353lyht_set_cb_data(struct hash_table *ht, void *new_cb_data)
354{
355 void *prev;
356
357 prev = ht->cb_data;
358 ht->cb_data = new_cb_data;
359 return prev;
360}
361
362struct hash_table *
363lyht_dup(const struct hash_table *orig)
364{
365 struct hash_table *ht;
366
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200367 LY_CHECK_ARG_RET(NULL, orig, NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200368
369 ht = lyht_new(orig->size, orig->rec_size - (sizeof(struct ht_rec) - 1), orig->val_equal, orig->cb_data, orig->resize ? 1 : 0);
370 if (!ht) {
371 return NULL;
372 }
373
374 memcpy(ht->recs, orig->recs, orig->used * orig->rec_size);
375 ht->used = orig->used;
376 return ht;
377}
378
379void
380lyht_free(struct hash_table *ht)
381{
382 if (ht) {
383 free(ht->recs);
384 free(ht);
385 }
386}
387
388static LY_ERR
Radek Krejci857189e2020-09-01 13:26:36 +0200389lyht_resize(struct hash_table *ht, ly_bool enlarge)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200390{
391 struct ht_rec *rec;
392 unsigned char *old_recs;
393 uint32_t i, old_size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200394
395 old_recs = ht->recs;
396 old_size = ht->size;
397
398 if (enlarge) {
399 /* double the size */
400 ht->size <<= 1;
401 } else {
402 /* half the size */
403 ht->size >>= 1;
404 }
405
406 ht->recs = calloc(ht->size, ht->rec_size);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200407 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 +0200408
409 /* reset used, it will increase again */
410 ht->used = 0;
411
412 /* add all the old records into the new records array */
413 for (i = 0; i < old_size; ++i) {
414 rec = lyht_get_rec(old_recs, ht->rec_size, i);
415 if (rec->hits > 0) {
Radek Krejci1deb5be2020-08-26 16:43:36 +0200416 LY_ERR ret = lyht_insert(ht, rec->val, rec->hash, NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200417 assert(!ret);
418 (void)ret;
419 }
420 }
421
422 /* final touches */
423 free(old_recs);
424 return LY_SUCCESS;
425}
426
Michal Vaskoda859032020-07-14 12:20:14 +0200427/**
428 * @brief Search for the first match.
429 *
430 * @param[in] ht Hash table to search in.
431 * @param[in] hash Hash to find.
432 * @param[out] rec_p Optional found record.
433 * @return LY_SUCCESS hash found, returned its record,
434 * @return LY_ENOTFOUND hash not found, returned the record where it would be inserted.
435 */
436static LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200437lyht_find_first(struct hash_table *ht, uint32_t hash, struct ht_rec **rec_p)
438{
439 struct ht_rec *rec;
440 uint32_t i, idx;
441
442 if (rec_p) {
443 *rec_p = NULL;
444 }
445
446 idx = i = hash & (ht->size - 1);
447 rec = lyht_get_rec(ht->recs, ht->rec_size, idx);
448
449 /* skip through overflow and deleted records */
450 while ((rec->hits != 0) && ((rec->hits == -1) || ((rec->hash & (ht->size - 1)) != idx))) {
451 if ((rec->hits == -1) && rec_p && !(*rec_p)) {
452 /* remember this record for return */
453 *rec_p = rec;
454 }
455 i = (i + 1) % ht->size;
456 if (i == idx) {
457 /* we went through all the records (very unlikely, but possible when many records are invalid),
458 * just return not found */
459 assert(!rec_p || *rec_p);
Michal Vaskoda859032020-07-14 12:20:14 +0200460 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200461 }
462 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
463 }
464 if (rec->hits == 0) {
465 /* we could not find the value */
466 if (rec_p && !*rec_p) {
467 *rec_p = rec;
468 }
Michal Vaskoda859032020-07-14 12:20:14 +0200469 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200470 }
471
472 /* we have found a record with equal (shortened) hash */
473 if (rec_p) {
474 *rec_p = rec;
475 }
Michal Vaskoda859032020-07-14 12:20:14 +0200476 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200477}
478
479/**
480 * @brief Search for the next collision.
481 *
482 * @param[in] ht Hash table to search in.
483 * @param[in,out] last Last returned collision record.
484 * @param[in] first First collision record (hits > 1).
Michal Vaskoda859032020-07-14 12:20:14 +0200485 * @return LY_SUCCESS when hash collision found, \p last points to this next collision,
486 * @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 +0200487 */
Michal Vaskoda859032020-07-14 12:20:14 +0200488static LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200489lyht_find_collision(struct hash_table *ht, struct ht_rec **last, struct ht_rec *first)
490{
491 struct ht_rec *empty = NULL;
492 uint32_t i, idx;
493
494 assert(last && *last);
495
496 idx = (*last)->hash & (ht->size - 1);
497 i = (((unsigned char *)*last) - ht->recs) / ht->rec_size;
498
499 do {
500 i = (i + 1) % ht->size;
501 *last = lyht_get_rec(ht->recs, ht->rec_size, i);
502 if (*last == first) {
503 /* we went through all the records (very unlikely, but possible when many records are invalid),
504 * just return an invalid record */
505 assert(empty);
506 *last = empty;
Michal Vaskoda859032020-07-14 12:20:14 +0200507 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200508 }
509
510 if (((*last)->hits == -1) && !empty) {
511 empty = *last;
512 }
513 } while (((*last)->hits != 0) && (((*last)->hits == -1) || (((*last)->hash & (ht->size - 1)) != idx)));
514
515 if ((*last)->hits > 0) {
516 /* we found a collision */
517 assert((*last)->hits == 1);
Michal Vaskoda859032020-07-14 12:20:14 +0200518 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200519 }
520
521 /* no next collision found, return the record where it would be inserted */
522 if (empty) {
523 *last = empty;
524 } /* else (*last)->hits == 0, it is already correct */
Michal Vaskoda859032020-07-14 12:20:14 +0200525 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200526}
527
Michal Vaskoda859032020-07-14 12:20:14 +0200528/**
529 * @brief Search for a record with specific value and hash.
530 *
531 * @param[in] ht Hash table to search in.
532 * @param[in] val_p Pointer to the value to find.
533 * @param[in] hash Hash to find.
Radek Krejci857189e2020-09-01 13:26:36 +0200534 * @param[in] mod Whether the operation modifies the hash table (insert or remove) or not (find).
Michal Vaskoda859032020-07-14 12:20:14 +0200535 * @param[out] crec_p Optional found first record.
536 * @param[out] col Optional collision number of @p rec_p, 0 for no collision.
537 * @param[out] rec_p Found exact matching record, may be a collision of @p crec_p.
538 * @return LY_ENOTFOUND if no record found,
539 * @return LY_SUCCESS if record was found.
540 */
541static LY_ERR
Radek Krejci857189e2020-09-01 13:26:36 +0200542lyht_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 +0200543 struct ht_rec **rec_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200544{
545 struct ht_rec *rec, *crec;
546 uint32_t i, c;
Michal Vaskoda859032020-07-14 12:20:14 +0200547 LY_ERR r;
548
549 if (crec_p) {
550 *crec_p = NULL;
551 }
552 if (col) {
553 *col = 0;
554 }
555 *rec_p = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200556
557 if (lyht_find_first(ht, hash, &rec)) {
558 /* not found */
Michal Vaskoda859032020-07-14 12:20:14 +0200559 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200560 }
Michal Vaskoda859032020-07-14 12:20:14 +0200561 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200562 /* even the value matches */
Michal Vaskoda859032020-07-14 12:20:14 +0200563 if (crec_p) {
564 *crec_p = rec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200565 }
Michal Vaskoda859032020-07-14 12:20:14 +0200566 if (col) {
567 *col = 0;
568 }
569 *rec_p = rec;
570 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200571 }
572
573 /* some collisions, we need to go through them, too */
574 crec = rec;
Michal Vaskoda859032020-07-14 12:20:14 +0200575 c = crec->hits;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200576 for (i = 1; i < c; ++i) {
577 r = lyht_find_collision(ht, &rec, crec);
578 assert(!r);
579 (void)r;
580
581 /* compare values */
Michal Vaskoda859032020-07-14 12:20:14 +0200582 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
583 if (crec_p) {
584 *crec_p = crec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200585 }
Michal Vaskoda859032020-07-14 12:20:14 +0200586 if (col) {
587 *col = i;
588 }
589 *rec_p = rec;
590 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200591 }
592 }
593
594 /* not found even in collisions */
Michal Vaskoda859032020-07-14 12:20:14 +0200595 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200596}
597
Michal Vaskoda859032020-07-14 12:20:14 +0200598LY_ERR
599lyht_find(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
600{
601 struct ht_rec *rec;
602
603 lyht_find_rec(ht, val_p, hash, 0, NULL, NULL, &rec);
604
605 if (rec && match_p) {
606 *match_p = rec->val;
607 }
608 return rec ? LY_SUCCESS : LY_ENOTFOUND;
609}
610
611LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200612lyht_find_next(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
613{
614 struct ht_rec *rec, *crec;
615 uint32_t i, c;
Michal Vaskoda859032020-07-14 12:20:14 +0200616 LY_ERR r;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200617
Michal Vaskoda859032020-07-14 12:20:14 +0200618 /* found the record of the previously found value */
619 if (lyht_find_rec(ht, val_p, hash, 1, &crec, &i, &rec)) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200620 /* not found, cannot happen */
Michal Vaskoda859032020-07-14 12:20:14 +0200621 LOGINT_RET(NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200622 }
623
624 /* go through collisions and find next one after the previous one */
Michal Vaskoda859032020-07-14 12:20:14 +0200625 c = crec->hits;
626 for (++i; i < c; ++i) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200627 r = lyht_find_collision(ht, &rec, crec);
628 assert(!r);
629 (void)r;
630
Michal Vaskoda859032020-07-14 12:20:14 +0200631 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 0, ht->cb_data)) {
632 /* even the value matches */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200633 if (match_p) {
634 *match_p = rec->val;
635 }
Michal Vaskoda859032020-07-14 12:20:14 +0200636 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200637 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200638 }
639
640 /* the last equal value was already returned */
Michal Vaskoda859032020-07-14 12:20:14 +0200641 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200642}
643
644LY_ERR
645lyht_insert_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash,
Radek Krejci0f969882020-08-21 16:56:47 +0200646 values_equal_cb resize_val_equal, void **match_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200647{
Radek Krejci1deb5be2020-08-26 16:43:36 +0200648 LY_ERR r, ret = LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200649 struct ht_rec *rec, *crec = NULL;
650 int32_t i;
Radek Krejci540ce982020-11-26 12:01:30 +0100651 values_equal_cb old_val_equal = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200652
653 if (!lyht_find_first(ht, hash, &rec)) {
654 /* we found matching shortened hash */
655 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
656 /* even the value matches */
657 if (match_p) {
658 *match_p = (void *)&rec->val;
659 }
660 return LY_EEXIST;
661 }
662
663 /* some collisions, we need to go through them, too */
664 crec = rec;
665 for (i = 1; i < crec->hits; ++i) {
666 r = lyht_find_collision(ht, &rec, crec);
667 assert(!r);
668
669 /* compare values */
670 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
671 if (match_p) {
672 *match_p = (void *)&rec->val;
673 }
674 return LY_EEXIST;
675 }
676 }
677
678 /* value not found, get the record where it will be inserted */
679 r = lyht_find_collision(ht, &rec, crec);
680 assert(r);
681 }
682
683 /* insert it into the returned record */
684 assert(rec->hits < 1);
685 rec->hash = hash;
686 rec->hits = 1;
687 memcpy(&rec->val, val_p, ht->rec_size - (sizeof(struct ht_rec) - 1));
688 if (match_p) {
689 *match_p = (void *)&rec->val;
690 }
691
692 if (crec) {
693 /* there was a collision, increase hits */
694 if (crec->hits == INT32_MAX) {
695 LOGINT(NULL);
696 }
697 ++crec->hits;
698 }
699
700 /* check size & enlarge if needed */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200701 ++ht->used;
702 if (ht->resize) {
Radek Krejcif13b87b2020-12-01 22:02:17 +0100703 r = (ht->used * LYHT_HUNDRED_PERCENTAGE) / ht->size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200704 if ((ht->resize == 1) && (r >= LYHT_FIRST_SHRINK_PERCENTAGE)) {
705 /* enable shrinking */
706 ht->resize = 2;
707 }
708 if ((ht->resize == 2) && (r >= LYHT_ENLARGE_PERCENTAGE)) {
709 if (resize_val_equal) {
710 old_val_equal = lyht_set_cb(ht, resize_val_equal);
711 }
712
713 /* enlarge */
714 ret = lyht_resize(ht, 1);
715 /* if hash_table was resized, we need to find new matching value */
Michal Vasko69730152020-10-09 16:30:07 +0200716 if ((ret == LY_SUCCESS) && match_p) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200717 lyht_find(ht, val_p, hash, match_p);
718 }
719
720 if (resize_val_equal) {
721 lyht_set_cb(ht, old_val_equal);
722 }
723 }
724 }
725 return ret;
726}
727
Radek Krejci0ae092d2018-09-20 16:43:19 +0200728LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200729lyht_insert(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
730{
731 return lyht_insert_with_resize_cb(ht, val_p, hash, NULL, match_p);
732}
733
734LY_ERR
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200735lyht_remove_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash, values_equal_cb resize_val_equal)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200736{
737 struct ht_rec *rec, *crec;
738 int32_t i;
Radek Krejci857189e2020-09-01 13:26:36 +0200739 ly_bool first_matched = 0;
Radek Krejci1deb5be2020-08-26 16:43:36 +0200740 LY_ERR r, ret = LY_SUCCESS;
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200741 values_equal_cb old_val_equal;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200742
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200743 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 +0200744
745 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
746 /* even the value matches */
747 first_matched = 1;
748 }
749
750 /* we always need to go through collisions */
751 crec = rec;
752 for (i = 1; i < crec->hits; ++i) {
753 r = lyht_find_collision(ht, &rec, crec);
754 assert(!r);
755
756 /* compare values */
757 if (!first_matched && (rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
758 break;
759 }
760 }
761
762 if (i < crec->hits) {
763 /* one of collisions matched, reduce collision count, remove the record */
764 assert(!first_matched);
765 --crec->hits;
766 rec->hits = -1;
767 } else if (first_matched) {
768 /* the first record matches */
769 if (crec != rec) {
770 /* ... so put the last collision in its place */
771 rec->hits = crec->hits - 1;
772 memcpy(crec, rec, ht->rec_size);
773 }
774 rec->hits = -1;
775 } else {
776 /* value not found even in collisions */
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200777 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200778 }
779
780 /* check size & shrink if needed */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200781 --ht->used;
782 if (ht->resize == 2) {
Radek Krejcif13b87b2020-12-01 22:02:17 +0100783 r = (ht->used * LYHT_HUNDRED_PERCENTAGE) / ht->size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200784 if ((r < LYHT_SHRINK_PERCENTAGE) && (ht->size > LYHT_MIN_SIZE)) {
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200785 if (resize_val_equal) {
786 old_val_equal = lyht_set_cb(ht, resize_val_equal);
787 }
788
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200789 /* shrink */
790 ret = lyht_resize(ht, 0);
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200791
792 if (resize_val_equal) {
793 lyht_set_cb(ht, old_val_equal);
794 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200795 }
796 }
797
798 return ret;
799}
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200800
801LY_ERR
802lyht_remove(struct hash_table *ht, void *val_p, uint32_t hash)
803{
804 return lyht_remove_with_resize_cb(ht, val_p, hash, NULL);
805}