blob: 20391ec2ef8447b72fb5b2b548444c528ccc08a2 [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 Krejci857189e2020-09-01 13:26:36 +020028/**
29 * @brief Comparison callback for dictionary's hash table
30 *
31 * Implementation of ::values_equal_cb.
32 */
33static ly_bool
34lydict_val_eq(void *val1_p, void *val2_p, ly_bool UNUSED(mod), void *cb_data)
Radek Krejci5aeea3a2018-09-05 13:29:36 +020035{
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020036 LY_CHECK_ARG_RET(NULL, val1_p, val2_p, cb_data, 0);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020037
38 const char *str1 = ((struct dict_rec *)val1_p)->value;
39 const char *str2 = ((struct dict_rec *)val2_p)->value;
40
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020041 LY_CHECK_ERR_RET(!str1, LOGARG(NULL, val1_p), 0);
42 LY_CHECK_ERR_RET(!str2, LOGARG(NULL, val2_p), 0);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020043
44 if (strncmp(str1, str2, *(size_t *)cb_data) == 0) {
45 return 1;
46 }
47
48 return 0;
49}
50
51void
52lydict_init(struct dict_table *dict)
53{
Michal Vaskod989ba02020-08-24 10:59:24 +020054 LY_CHECK_ARG_RET(NULL, dict, );
Radek Krejci5aeea3a2018-09-05 13:29:36 +020055
56 dict->hash_tab = lyht_new(1024, sizeof(struct dict_rec), lydict_val_eq, NULL, 1);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020057 LY_CHECK_ERR_RET(!dict->hash_tab, LOGINT(NULL), );
Radek Krejci5aeea3a2018-09-05 13:29:36 +020058 pthread_mutex_init(&dict->lock, NULL);
59}
60
61void
62lydict_clean(struct dict_table *dict)
63{
Michal Vasko44f3d2c2020-08-24 09:49:38 +020064 struct dict_rec *dict_rec = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +020065 struct ht_rec *rec = NULL;
66
Michal Vaskod989ba02020-08-24 10:59:24 +020067 LY_CHECK_ARG_RET(NULL, dict, );
Radek Krejci5aeea3a2018-09-05 13:29:36 +020068
Radek Krejci1deb5be2020-08-26 16:43:36 +020069 for (uint32_t i = 0; i < dict->hash_tab->size; i++) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +020070 /* get ith record */
71 rec = (struct ht_rec *)&dict->hash_tab->recs[i * dict->hash_tab->rec_size];
72 if (rec->hits == 1) {
73 /*
74 * this should not happen, all records inserted into
75 * dictionary are supposed to be removed using lydict_remove()
76 * before calling lydict_clean()
77 */
Michal Vasko44f3d2c2020-08-24 09:49:38 +020078 dict_rec = (struct dict_rec *)rec->val;
Radek Krejci5aeea3a2018-09-05 13:29:36 +020079 LOGWRN(NULL, "String \"%s\" not freed from the dictionary, refcount %d", dict_rec->value, dict_rec->refcount);
80 /* if record wasn't removed before free string allocated for that record */
81#ifdef NDEBUG
82 free(dict_rec->value);
83#endif
84 }
85 }
86
87 /* free table and destroy mutex */
88 lyht_free(dict->hash_tab);
89 pthread_mutex_destroy(&dict->lock);
90}
91
92/*
Radek Krejci5aeea3a2018-09-05 13:29:36 +020093 * Usage:
94 * - init hash to 0
95 * - repeatedly call dict_hash_multi(), provide hash from the last call
96 * - call dict_hash_multi() with key_part = NULL to finish the hash
97 */
98uint32_t
99dict_hash_multi(uint32_t hash, const char *key_part, size_t len)
100{
101 uint32_t i;
102
103 if (key_part) {
104 for (i = 0; i < len; ++i) {
105 hash += key_part[i];
106 hash += (hash << 10);
107 hash ^= (hash >> 6);
108 }
109 } else {
110 hash += (hash << 3);
111 hash ^= (hash >> 11);
112 hash += (hash << 15);
113 }
114
115 return hash;
116}
117
Radek Krejcif2dc4c52018-11-08 09:04:13 +0100118/*
119 * Bob Jenkin's one-at-a-time hash
120 * http://www.burtleburtle.net/bob/hash/doobs.html
121 *
122 * Spooky hash is faster, but it works only for little endian architectures.
123 */
124uint32_t
125dict_hash(const char *key, size_t len)
126{
127 uint32_t hash;
128
129 hash = dict_hash_multi(0, key, len);
130 return dict_hash_multi(hash, NULL, len);
131}
132
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200133static ly_bool
134lydict_resize_val_eq(void *val1_p, void *val2_p, ly_bool mod, void *cb_data)
135{
136 LY_CHECK_ARG_RET(NULL, val1_p, val2_p, 0);
137
138 const char *str1 = ((struct dict_rec *)val1_p)->value;
139 const char *str2 = ((struct dict_rec *)val2_p)->value;
140
141 LY_CHECK_ERR_RET(!str1, LOGARG(NULL, val1_p), 0);
142 LY_CHECK_ERR_RET(!str2, LOGARG(NULL, val2_p), 0);
143
144 if (mod) {
145 /* used when inserting new values */
146 if (strcmp(str1, str2) == 0) {
147 return 1;
148 }
149 } else {
150 /* used when finding the original value again in the resized table */
151 return lydict_val_eq(val1_p, val2_p, mod, cb_data);
152 }
153
154 return 0;
155}
156
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200157API void
Michal Vasko52927e22020-03-16 17:26:14 +0100158lydict_remove(const struct ly_ctx *ctx, const char *value)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200159{
Radek Krejci1deb5be2020-08-26 16:43:36 +0200160 LY_ERR ret;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200161 size_t len;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200162 uint32_t hash;
163 struct dict_rec rec, *match = NULL;
164 char *val_p;
165
Michal Vasko0f6b3e22018-09-07 12:18:12 +0200166 if (!value) {
Michal Vasko0b3a4172018-09-07 12:20:18 +0200167 return;
Michal Vasko0f6b3e22018-09-07 12:18:12 +0200168 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200169
170 len = strlen(value);
171 hash = dict_hash(value, len);
172
173 /* create record for lyht_find call */
174 rec.value = (char *)value;
175 rec.refcount = 0;
176
Michal Vasko52927e22020-03-16 17:26:14 +0100177 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200178 /* set len as data for compare callback */
179 lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
180 /* check if value is already inserted */
181 ret = lyht_find(ctx->dict.hash_tab, &rec, hash, (void **)&match);
182
Radek Krejci1deb5be2020-08-26 16:43:36 +0200183 if (ret == LY_SUCCESS) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200184 LY_CHECK_ERR_GOTO(!match, LOGINT(ctx), finish);
185
186 /* if value is already in dictionary, decrement reference counter */
187 match->refcount--;
188 if (match->refcount == 0) {
189 /*
190 * remove record
191 * save pointer to stored string before lyht_remove to
192 * free it after it is removed from hash table
193 */
194 val_p = match->value;
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200195 ret = lyht_remove_with_resize_cb(ctx->dict.hash_tab, &rec, hash, lydict_resize_val_eq);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200196 free(val_p);
197 LY_CHECK_ERR_GOTO(ret, LOGINT(ctx), finish);
198 }
199 }
200
201finish:
Michal Vasko52927e22020-03-16 17:26:14 +0100202 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200203}
204
Radek Krejci011e4aa2020-09-04 15:22:31 +0200205LY_ERR
206dict_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 +0200207{
Radek Krejci011e4aa2020-09-04 15:22:31 +0200208 LY_ERR ret = LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200209 struct dict_rec *match = NULL, rec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200210 uint32_t hash;
211
212 hash = dict_hash(value, len);
213 /* set len as data for compare callback */
214 lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
215 /* create record for lyht_insert */
216 rec.value = value;
217 rec.refcount = 1;
218
219 LOGDBG(LY_LDGDICT, "inserting \"%s\"", rec.value);
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200220 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 +0200221 if (ret == LY_EEXIST) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200222 match->refcount++;
223 if (zerocopy) {
224 free(value);
225 }
Radek Krejci011e4aa2020-09-04 15:22:31 +0200226 ret = LY_SUCCESS;
Michal Vaskofcc96b92018-09-12 11:12:01 +0200227 } else if (ret == LY_SUCCESS) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200228 if (!zerocopy) {
229 /*
230 * allocate string for new record
231 * record is already inserted in hash table
232 */
233 match->value = malloc(sizeof *match->value * (len + 1));
Radek Krejci011e4aa2020-09-04 15:22:31 +0200234 LY_CHECK_ERR_RET(!match->value, LOGMEM(ctx), LY_EMEM);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200235 memcpy(match->value, value, len);
236 match->value[len] = '\0';
237 }
238 } else {
239 /* lyht_insert returned error */
David Sedlák234a91f2019-08-15 13:16:43 +0200240 if (zerocopy) {
241 free(value);
242 }
Radek Krejci011e4aa2020-09-04 15:22:31 +0200243 return ret;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200244 }
245
Radek Krejci011e4aa2020-09-04 15:22:31 +0200246 if (str_p) {
247 *str_p = match->value;
248 }
249
250 return ret;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200251}
252
Radek Krejci011e4aa2020-09-04 15:22:31 +0200253API LY_ERR
254lydict_insert(const struct ly_ctx *ctx, const char *value, size_t len, const char **str_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200255{
Radek Krejci011e4aa2020-09-04 15:22:31 +0200256 LY_ERR result;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200257
Radek Krejci011e4aa2020-09-04 15:22:31 +0200258 LY_CHECK_ARG_RET(ctx, ctx, value, LY_EINVAL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200259
Radek Krejci0ae092d2018-09-20 16:43:19 +0200260 if (!len) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200261 len = strlen(value);
262 }
263
Michal Vasko52927e22020-03-16 17:26:14 +0100264 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci011e4aa2020-09-04 15:22:31 +0200265 result = dict_insert(ctx, (char *)value, len, 0, str_p);
Michal Vasko52927e22020-03-16 17:26:14 +0100266 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200267
268 return result;
269}
270
Radek Krejci011e4aa2020-09-04 15:22:31 +0200271API LY_ERR
272lydict_insert_zc(const struct ly_ctx *ctx, char *value, const char **str_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200273{
Radek Krejci011e4aa2020-09-04 15:22:31 +0200274 LY_ERR result;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200275
Radek Krejci011e4aa2020-09-04 15:22:31 +0200276 LY_CHECK_ARG_RET(ctx, ctx, value, LY_EINVAL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200277
Michal Vasko52927e22020-03-16 17:26:14 +0100278 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci011e4aa2020-09-04 15:22:31 +0200279 result = dict_insert(ctx, value, strlen(value), 1, str_p);
Michal Vasko52927e22020-03-16 17:26:14 +0100280 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200281
282 return result;
283}
284
Radek Krejci2d7a47b2019-05-16 13:34:10 +0200285struct ht_rec *
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200286lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx)
287{
288 return (struct ht_rec *)&recs[idx * rec_size];
289}
290
291struct hash_table *
Radek Krejci1deb5be2020-08-26 16:43:36 +0200292lyht_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 +0200293{
294 struct hash_table *ht;
295
296 /* check that 2^x == size (power of 2) */
297 assert(size && !(size & (size - 1)));
298 assert(val_equal && val_size);
299 assert(resize == 0 || resize == 1);
300
301 if (size < LYHT_MIN_SIZE) {
302 size = LYHT_MIN_SIZE;
303 }
304
305 ht = malloc(sizeof *ht);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200306 LY_CHECK_ERR_RET(!ht, LOGMEM(NULL), NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200307
308 ht->used = 0;
309 ht->size = size;
310 ht->val_equal = val_equal;
311 ht->cb_data = cb_data;
Radek Krejci1deb5be2020-08-26 16:43:36 +0200312 ht->resize = resize;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200313
314 ht->rec_size = (sizeof(struct ht_rec) - 1) + val_size;
315 /* allocate the records correctly */
316 ht->recs = calloc(size, ht->rec_size);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200317 LY_CHECK_ERR_RET(!ht->recs, free(ht); LOGMEM(NULL), NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200318
319 return ht;
320}
321
322values_equal_cb
323lyht_set_cb(struct hash_table *ht, values_equal_cb new_val_equal)
324{
325 values_equal_cb prev;
326
327 prev = ht->val_equal;
328 ht->val_equal = new_val_equal;
329 return prev;
330}
331
332void *
333lyht_set_cb_data(struct hash_table *ht, void *new_cb_data)
334{
335 void *prev;
336
337 prev = ht->cb_data;
338 ht->cb_data = new_cb_data;
339 return prev;
340}
341
342struct hash_table *
343lyht_dup(const struct hash_table *orig)
344{
345 struct hash_table *ht;
346
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200347 LY_CHECK_ARG_RET(NULL, orig, NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200348
349 ht = lyht_new(orig->size, orig->rec_size - (sizeof(struct ht_rec) - 1), orig->val_equal, orig->cb_data, orig->resize ? 1 : 0);
350 if (!ht) {
351 return NULL;
352 }
353
354 memcpy(ht->recs, orig->recs, orig->used * orig->rec_size);
355 ht->used = orig->used;
356 return ht;
357}
358
359void
360lyht_free(struct hash_table *ht)
361{
362 if (ht) {
363 free(ht->recs);
364 free(ht);
365 }
366}
367
368static LY_ERR
Radek Krejci857189e2020-09-01 13:26:36 +0200369lyht_resize(struct hash_table *ht, ly_bool enlarge)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200370{
371 struct ht_rec *rec;
372 unsigned char *old_recs;
373 uint32_t i, old_size;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200374
375 old_recs = ht->recs;
376 old_size = ht->size;
377
378 if (enlarge) {
379 /* double the size */
380 ht->size <<= 1;
381 } else {
382 /* half the size */
383 ht->size >>= 1;
384 }
385
386 ht->recs = calloc(ht->size, ht->rec_size);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200387 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 +0200388
389 /* reset used, it will increase again */
390 ht->used = 0;
391
392 /* add all the old records into the new records array */
393 for (i = 0; i < old_size; ++i) {
394 rec = lyht_get_rec(old_recs, ht->rec_size, i);
395 if (rec->hits > 0) {
Radek Krejci1deb5be2020-08-26 16:43:36 +0200396 LY_ERR ret = lyht_insert(ht, rec->val, rec->hash, NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200397 assert(!ret);
398 (void)ret;
399 }
400 }
401
402 /* final touches */
403 free(old_recs);
404 return LY_SUCCESS;
405}
406
Michal Vaskoda859032020-07-14 12:20:14 +0200407/**
408 * @brief Search for the first match.
409 *
410 * @param[in] ht Hash table to search in.
411 * @param[in] hash Hash to find.
412 * @param[out] rec_p Optional found record.
413 * @return LY_SUCCESS hash found, returned its record,
414 * @return LY_ENOTFOUND hash not found, returned the record where it would be inserted.
415 */
416static LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200417lyht_find_first(struct hash_table *ht, uint32_t hash, struct ht_rec **rec_p)
418{
419 struct ht_rec *rec;
420 uint32_t i, idx;
421
422 if (rec_p) {
423 *rec_p = NULL;
424 }
425
426 idx = i = hash & (ht->size - 1);
427 rec = lyht_get_rec(ht->recs, ht->rec_size, idx);
428
429 /* skip through overflow and deleted records */
430 while ((rec->hits != 0) && ((rec->hits == -1) || ((rec->hash & (ht->size - 1)) != idx))) {
431 if ((rec->hits == -1) && rec_p && !(*rec_p)) {
432 /* remember this record for return */
433 *rec_p = rec;
434 }
435 i = (i + 1) % ht->size;
436 if (i == idx) {
437 /* we went through all the records (very unlikely, but possible when many records are invalid),
438 * just return not found */
439 assert(!rec_p || *rec_p);
Michal Vaskoda859032020-07-14 12:20:14 +0200440 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200441 }
442 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
443 }
444 if (rec->hits == 0) {
445 /* we could not find the value */
446 if (rec_p && !*rec_p) {
447 *rec_p = rec;
448 }
Michal Vaskoda859032020-07-14 12:20:14 +0200449 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200450 }
451
452 /* we have found a record with equal (shortened) hash */
453 if (rec_p) {
454 *rec_p = rec;
455 }
Michal Vaskoda859032020-07-14 12:20:14 +0200456 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200457}
458
459/**
460 * @brief Search for the next collision.
461 *
462 * @param[in] ht Hash table to search in.
463 * @param[in,out] last Last returned collision record.
464 * @param[in] first First collision record (hits > 1).
Michal Vaskoda859032020-07-14 12:20:14 +0200465 * @return LY_SUCCESS when hash collision found, \p last points to this next collision,
466 * @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 +0200467 */
Michal Vaskoda859032020-07-14 12:20:14 +0200468static LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200469lyht_find_collision(struct hash_table *ht, struct ht_rec **last, struct ht_rec *first)
470{
471 struct ht_rec *empty = NULL;
472 uint32_t i, idx;
473
474 assert(last && *last);
475
476 idx = (*last)->hash & (ht->size - 1);
477 i = (((unsigned char *)*last) - ht->recs) / ht->rec_size;
478
479 do {
480 i = (i + 1) % ht->size;
481 *last = lyht_get_rec(ht->recs, ht->rec_size, i);
482 if (*last == first) {
483 /* we went through all the records (very unlikely, but possible when many records are invalid),
484 * just return an invalid record */
485 assert(empty);
486 *last = empty;
Michal Vaskoda859032020-07-14 12:20:14 +0200487 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200488 }
489
490 if (((*last)->hits == -1) && !empty) {
491 empty = *last;
492 }
493 } while (((*last)->hits != 0) && (((*last)->hits == -1) || (((*last)->hash & (ht->size - 1)) != idx)));
494
495 if ((*last)->hits > 0) {
496 /* we found a collision */
497 assert((*last)->hits == 1);
Michal Vaskoda859032020-07-14 12:20:14 +0200498 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200499 }
500
501 /* no next collision found, return the record where it would be inserted */
502 if (empty) {
503 *last = empty;
504 } /* else (*last)->hits == 0, it is already correct */
Michal Vaskoda859032020-07-14 12:20:14 +0200505 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200506}
507
Michal Vaskoda859032020-07-14 12:20:14 +0200508/**
509 * @brief Search for a record with specific value and hash.
510 *
511 * @param[in] ht Hash table to search in.
512 * @param[in] val_p Pointer to the value to find.
513 * @param[in] hash Hash to find.
Radek Krejci857189e2020-09-01 13:26:36 +0200514 * @param[in] mod Whether the operation modifies the hash table (insert or remove) or not (find).
Michal Vaskoda859032020-07-14 12:20:14 +0200515 * @param[out] crec_p Optional found first record.
516 * @param[out] col Optional collision number of @p rec_p, 0 for no collision.
517 * @param[out] rec_p Found exact matching record, may be a collision of @p crec_p.
518 * @return LY_ENOTFOUND if no record found,
519 * @return LY_SUCCESS if record was found.
520 */
521static LY_ERR
Radek Krejci857189e2020-09-01 13:26:36 +0200522lyht_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 +0200523 struct ht_rec **rec_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200524{
525 struct ht_rec *rec, *crec;
526 uint32_t i, c;
Michal Vaskoda859032020-07-14 12:20:14 +0200527 LY_ERR r;
528
529 if (crec_p) {
530 *crec_p = NULL;
531 }
532 if (col) {
533 *col = 0;
534 }
535 *rec_p = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200536
537 if (lyht_find_first(ht, hash, &rec)) {
538 /* not found */
Michal Vaskoda859032020-07-14 12:20:14 +0200539 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200540 }
Michal Vaskoda859032020-07-14 12:20:14 +0200541 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200542 /* even the value matches */
Michal Vaskoda859032020-07-14 12:20:14 +0200543 if (crec_p) {
544 *crec_p = rec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200545 }
Michal Vaskoda859032020-07-14 12:20:14 +0200546 if (col) {
547 *col = 0;
548 }
549 *rec_p = rec;
550 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200551 }
552
553 /* some collisions, we need to go through them, too */
554 crec = rec;
Michal Vaskoda859032020-07-14 12:20:14 +0200555 c = crec->hits;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200556 for (i = 1; i < c; ++i) {
557 r = lyht_find_collision(ht, &rec, crec);
558 assert(!r);
559 (void)r;
560
561 /* compare values */
Michal Vaskoda859032020-07-14 12:20:14 +0200562 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
563 if (crec_p) {
564 *crec_p = crec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200565 }
Michal Vaskoda859032020-07-14 12:20:14 +0200566 if (col) {
567 *col = i;
568 }
569 *rec_p = rec;
570 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200571 }
572 }
573
574 /* not found even in collisions */
Michal Vaskoda859032020-07-14 12:20:14 +0200575 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200576}
577
Michal Vaskoda859032020-07-14 12:20:14 +0200578LY_ERR
579lyht_find(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
580{
581 struct ht_rec *rec;
582
583 lyht_find_rec(ht, val_p, hash, 0, NULL, NULL, &rec);
584
585 if (rec && match_p) {
586 *match_p = rec->val;
587 }
588 return rec ? LY_SUCCESS : LY_ENOTFOUND;
589}
590
591LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200592lyht_find_next(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
593{
594 struct ht_rec *rec, *crec;
595 uint32_t i, c;
Michal Vaskoda859032020-07-14 12:20:14 +0200596 LY_ERR r;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200597
Michal Vaskoda859032020-07-14 12:20:14 +0200598 /* found the record of the previously found value */
599 if (lyht_find_rec(ht, val_p, hash, 1, &crec, &i, &rec)) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200600 /* not found, cannot happen */
Michal Vaskoda859032020-07-14 12:20:14 +0200601 LOGINT_RET(NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200602 }
603
604 /* go through collisions and find next one after the previous one */
Michal Vaskoda859032020-07-14 12:20:14 +0200605 c = crec->hits;
606 for (++i; i < c; ++i) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200607 r = lyht_find_collision(ht, &rec, crec);
608 assert(!r);
609 (void)r;
610
Michal Vaskoda859032020-07-14 12:20:14 +0200611 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 0, ht->cb_data)) {
612 /* even the value matches */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200613 if (match_p) {
614 *match_p = rec->val;
615 }
Michal Vaskoda859032020-07-14 12:20:14 +0200616 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200617 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200618 }
619
620 /* the last equal value was already returned */
Michal Vaskoda859032020-07-14 12:20:14 +0200621 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200622}
623
624LY_ERR
625lyht_insert_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash,
Radek Krejci0f969882020-08-21 16:56:47 +0200626 values_equal_cb resize_val_equal, void **match_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200627{
Radek Krejci1deb5be2020-08-26 16:43:36 +0200628 LY_ERR r, ret = LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200629 struct ht_rec *rec, *crec = NULL;
630 int32_t i;
Radek Krejci540ce982020-11-26 12:01:30 +0100631 values_equal_cb old_val_equal = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200632
633 if (!lyht_find_first(ht, hash, &rec)) {
634 /* we found matching shortened hash */
635 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
636 /* even the value matches */
637 if (match_p) {
638 *match_p = (void *)&rec->val;
639 }
640 return LY_EEXIST;
641 }
642
643 /* some collisions, we need to go through them, too */
644 crec = rec;
645 for (i = 1; i < crec->hits; ++i) {
646 r = lyht_find_collision(ht, &rec, crec);
647 assert(!r);
648
649 /* compare values */
650 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
651 if (match_p) {
652 *match_p = (void *)&rec->val;
653 }
654 return LY_EEXIST;
655 }
656 }
657
658 /* value not found, get the record where it will be inserted */
659 r = lyht_find_collision(ht, &rec, crec);
660 assert(r);
661 }
662
663 /* insert it into the returned record */
664 assert(rec->hits < 1);
665 rec->hash = hash;
666 rec->hits = 1;
667 memcpy(&rec->val, val_p, ht->rec_size - (sizeof(struct ht_rec) - 1));
668 if (match_p) {
669 *match_p = (void *)&rec->val;
670 }
671
672 if (crec) {
673 /* there was a collision, increase hits */
674 if (crec->hits == INT32_MAX) {
675 LOGINT(NULL);
676 }
677 ++crec->hits;
678 }
679
680 /* check size & enlarge if needed */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200681 ++ht->used;
682 if (ht->resize) {
683 r = (ht->used * 100) / ht->size;
684 if ((ht->resize == 1) && (r >= LYHT_FIRST_SHRINK_PERCENTAGE)) {
685 /* enable shrinking */
686 ht->resize = 2;
687 }
688 if ((ht->resize == 2) && (r >= LYHT_ENLARGE_PERCENTAGE)) {
689 if (resize_val_equal) {
690 old_val_equal = lyht_set_cb(ht, resize_val_equal);
691 }
692
693 /* enlarge */
694 ret = lyht_resize(ht, 1);
695 /* if hash_table was resized, we need to find new matching value */
Michal Vasko69730152020-10-09 16:30:07 +0200696 if ((ret == LY_SUCCESS) && match_p) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200697 lyht_find(ht, val_p, hash, match_p);
698 }
699
700 if (resize_val_equal) {
701 lyht_set_cb(ht, old_val_equal);
702 }
703 }
704 }
705 return ret;
706}
707
Radek Krejci0ae092d2018-09-20 16:43:19 +0200708LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200709lyht_insert(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
710{
711 return lyht_insert_with_resize_cb(ht, val_p, hash, NULL, match_p);
712}
713
714LY_ERR
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200715lyht_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 +0200716{
717 struct ht_rec *rec, *crec;
718 int32_t i;
Radek Krejci857189e2020-09-01 13:26:36 +0200719 ly_bool first_matched = 0;
Radek Krejci1deb5be2020-08-26 16:43:36 +0200720 LY_ERR r, ret = LY_SUCCESS;
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200721 values_equal_cb old_val_equal;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200722
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200723 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 +0200724
725 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
726 /* even the value matches */
727 first_matched = 1;
728 }
729
730 /* we always need to go through collisions */
731 crec = rec;
732 for (i = 1; i < crec->hits; ++i) {
733 r = lyht_find_collision(ht, &rec, crec);
734 assert(!r);
735
736 /* compare values */
737 if (!first_matched && (rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
738 break;
739 }
740 }
741
742 if (i < crec->hits) {
743 /* one of collisions matched, reduce collision count, remove the record */
744 assert(!first_matched);
745 --crec->hits;
746 rec->hits = -1;
747 } else if (first_matched) {
748 /* the first record matches */
749 if (crec != rec) {
750 /* ... so put the last collision in its place */
751 rec->hits = crec->hits - 1;
752 memcpy(crec, rec, ht->rec_size);
753 }
754 rec->hits = -1;
755 } else {
756 /* value not found even in collisions */
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200757 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200758 }
759
760 /* check size & shrink if needed */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200761 --ht->used;
762 if (ht->resize == 2) {
763 r = (ht->used * 100) / ht->size;
764 if ((r < LYHT_SHRINK_PERCENTAGE) && (ht->size > LYHT_MIN_SIZE)) {
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200765 if (resize_val_equal) {
766 old_val_equal = lyht_set_cb(ht, resize_val_equal);
767 }
768
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200769 /* shrink */
770 ret = lyht_resize(ht, 0);
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200771
772 if (resize_val_equal) {
773 lyht_set_cb(ht, old_val_equal);
774 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200775 }
776 }
777
778 return ret;
779}
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200780
781LY_ERR
782lyht_remove(struct hash_table *ht, void *val_p, uint32_t hash)
783{
784 return lyht_remove_with_resize_cb(ht, val_p, hash, NULL);
785}