blob: 0e4d512aa3f537968ab5d2bcc93492d85f936a0b [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
Radek Krejci5aeea3a2018-09-05 13:29:36 +020017#include <string.h>
18#include <stdint.h>
19#include <stdlib.h>
20#include <pthread.h>
21#include <assert.h>
22
Radek Krejci535ea9f2020-05-29 16:01:05 +020023#include "common.h"
24#include "dict.h"
Radek Krejci5aeea3a2018-09-05 13:29:36 +020025
26static int
27lydict_val_eq(void *val1_p, void *val2_p, int UNUSED(mod), void *cb_data)
28{
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020029 LY_CHECK_ARG_RET(NULL, val1_p, val2_p, cb_data, 0);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020030
31 const char *str1 = ((struct dict_rec *)val1_p)->value;
32 const char *str2 = ((struct dict_rec *)val2_p)->value;
33
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020034 LY_CHECK_ERR_RET(!str1, LOGARG(NULL, val1_p), 0);
35 LY_CHECK_ERR_RET(!str2, LOGARG(NULL, val2_p), 0);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020036
37 if (strncmp(str1, str2, *(size_t *)cb_data) == 0) {
38 return 1;
39 }
40
41 return 0;
42}
43
44void
45lydict_init(struct dict_table *dict)
46{
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020047 LY_CHECK_ARG_RET(NULL, dict,);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020048
49 dict->hash_tab = lyht_new(1024, sizeof(struct dict_rec), lydict_val_eq, NULL, 1);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020050 LY_CHECK_ERR_RET(!dict->hash_tab, LOGINT(NULL), );
Radek Krejci5aeea3a2018-09-05 13:29:36 +020051 pthread_mutex_init(&dict->lock, NULL);
52}
53
54void
55lydict_clean(struct dict_table *dict)
56{
57 unsigned int i;
58 struct dict_rec *dict_rec = NULL;
59 struct ht_rec *rec = NULL;
60
Michal Vaskob3d0d6b2018-09-07 10:17:33 +020061 LY_CHECK_ARG_RET(NULL, dict,);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020062
63 for (i = 0; i < dict->hash_tab->size; i++) {
64 /* get ith record */
65 rec = (struct ht_rec *)&dict->hash_tab->recs[i * dict->hash_tab->rec_size];
66 if (rec->hits == 1) {
67 /*
68 * this should not happen, all records inserted into
69 * dictionary are supposed to be removed using lydict_remove()
70 * before calling lydict_clean()
71 */
72 dict_rec = (struct dict_rec *)rec->val;
73 LOGWRN(NULL, "String \"%s\" not freed from the dictionary, refcount %d", dict_rec->value, dict_rec->refcount);
74 /* if record wasn't removed before free string allocated for that record */
75#ifdef NDEBUG
76 free(dict_rec->value);
77#endif
78 }
79 }
80
81 /* free table and destroy mutex */
82 lyht_free(dict->hash_tab);
83 pthread_mutex_destroy(&dict->lock);
84}
85
86/*
Radek Krejci5aeea3a2018-09-05 13:29:36 +020087 * Usage:
88 * - init hash to 0
89 * - repeatedly call dict_hash_multi(), provide hash from the last call
90 * - call dict_hash_multi() with key_part = NULL to finish the hash
91 */
92uint32_t
93dict_hash_multi(uint32_t hash, const char *key_part, size_t len)
94{
95 uint32_t i;
96
97 if (key_part) {
98 for (i = 0; i < len; ++i) {
99 hash += key_part[i];
100 hash += (hash << 10);
101 hash ^= (hash >> 6);
102 }
103 } else {
104 hash += (hash << 3);
105 hash ^= (hash >> 11);
106 hash += (hash << 15);
107 }
108
109 return hash;
110}
111
Radek Krejcif2dc4c52018-11-08 09:04:13 +0100112/*
113 * Bob Jenkin's one-at-a-time hash
114 * http://www.burtleburtle.net/bob/hash/doobs.html
115 *
116 * Spooky hash is faster, but it works only for little endian architectures.
117 */
118uint32_t
119dict_hash(const char *key, size_t len)
120{
121 uint32_t hash;
122
123 hash = dict_hash_multi(0, key, len);
124 return dict_hash_multi(hash, NULL, len);
125}
126
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200127API void
Michal Vasko52927e22020-03-16 17:26:14 +0100128lydict_remove(const struct ly_ctx *ctx, const char *value)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200129{
130 size_t len;
131 int ret;
132 uint32_t hash;
133 struct dict_rec rec, *match = NULL;
134 char *val_p;
135
Michal Vasko0f6b3e22018-09-07 12:18:12 +0200136 if (!value) {
Michal Vasko0b3a4172018-09-07 12:20:18 +0200137 return;
Michal Vasko0f6b3e22018-09-07 12:18:12 +0200138 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200139
140 len = strlen(value);
141 hash = dict_hash(value, len);
142
143 /* create record for lyht_find call */
144 rec.value = (char *)value;
145 rec.refcount = 0;
146
Michal Vasko52927e22020-03-16 17:26:14 +0100147 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200148 /* set len as data for compare callback */
149 lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
150 /* check if value is already inserted */
151 ret = lyht_find(ctx->dict.hash_tab, &rec, hash, (void **)&match);
152
153 if (ret == 0) {
154 LY_CHECK_ERR_GOTO(!match, LOGINT(ctx), finish);
155
156 /* if value is already in dictionary, decrement reference counter */
157 match->refcount--;
158 if (match->refcount == 0) {
159 /*
160 * remove record
161 * save pointer to stored string before lyht_remove to
162 * free it after it is removed from hash table
163 */
164 val_p = match->value;
165 ret = lyht_remove(ctx->dict.hash_tab, &rec, hash);
166 free(val_p);
167 LY_CHECK_ERR_GOTO(ret, LOGINT(ctx), finish);
168 }
169 }
170
171finish:
Michal Vasko52927e22020-03-16 17:26:14 +0100172 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200173}
174
175static char *
Michal Vasko52927e22020-03-16 17:26:14 +0100176dict_insert(const struct ly_ctx *ctx, char *value, size_t len, int zerocopy)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200177{
178 struct dict_rec *match = NULL, rec;
179 int ret = 0;
180 uint32_t hash;
181
182 hash = dict_hash(value, len);
183 /* set len as data for compare callback */
184 lyht_set_cb_data(ctx->dict.hash_tab, (void *)&len);
185 /* create record for lyht_insert */
186 rec.value = value;
187 rec.refcount = 1;
188
189 LOGDBG(LY_LDGDICT, "inserting \"%s\"", rec.value);
190 ret = lyht_insert(ctx->dict.hash_tab, (void *)&rec, hash, (void **)&match);
Michal Vaskofcc96b92018-09-12 11:12:01 +0200191 if (ret == LY_EEXIST) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200192 match->refcount++;
193 if (zerocopy) {
194 free(value);
195 }
Michal Vaskofcc96b92018-09-12 11:12:01 +0200196 } else if (ret == LY_SUCCESS) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200197 if (!zerocopy) {
198 /*
199 * allocate string for new record
200 * record is already inserted in hash table
201 */
202 match->value = malloc(sizeof *match->value * (len + 1));
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200203 LY_CHECK_ERR_RET(!match->value, LOGMEM(ctx), NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200204 memcpy(match->value, value, len);
205 match->value[len] = '\0';
206 }
207 } else {
208 /* lyht_insert returned error */
209 LOGINT(ctx);
David Sedlák234a91f2019-08-15 13:16:43 +0200210 if (zerocopy) {
211 free(value);
212 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200213 return NULL;
214 }
215
216 return match->value;
217}
218
219API const char *
Michal Vasko52927e22020-03-16 17:26:14 +0100220lydict_insert(const struct ly_ctx *ctx, const char *value, size_t len)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200221{
222 const char *result;
223
Radek Krejci0ae092d2018-09-20 16:43:19 +0200224 LY_CHECK_ARG_RET(ctx, ctx, value, NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200225
Radek Krejci0ae092d2018-09-20 16:43:19 +0200226 if (!len) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200227 len = strlen(value);
228 }
229
Michal Vasko52927e22020-03-16 17:26:14 +0100230 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200231 result = dict_insert(ctx, (char *)value, len, 0);
Michal Vasko52927e22020-03-16 17:26:14 +0100232 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200233
234 return result;
235}
236
237API const char *
Michal Vasko52927e22020-03-16 17:26:14 +0100238lydict_insert_zc(const struct ly_ctx *ctx, char *value)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200239{
240 const char *result;
241
Radek Krejci0ae092d2018-09-20 16:43:19 +0200242 LY_CHECK_ARG_RET(ctx, ctx, value, NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200243
Michal Vasko52927e22020-03-16 17:26:14 +0100244 pthread_mutex_lock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200245 result = dict_insert(ctx, value, strlen(value), 1);
Michal Vasko52927e22020-03-16 17:26:14 +0100246 pthread_mutex_unlock((pthread_mutex_t *)&ctx->dict.lock);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200247
248 return result;
249}
250
Radek Krejci2d7a47b2019-05-16 13:34:10 +0200251struct ht_rec *
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200252lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx)
253{
254 return (struct ht_rec *)&recs[idx * rec_size];
255}
256
257struct hash_table *
258lyht_new(uint32_t size, uint16_t val_size, values_equal_cb val_equal, void *cb_data, int resize)
259{
260 struct hash_table *ht;
261
262 /* check that 2^x == size (power of 2) */
263 assert(size && !(size & (size - 1)));
264 assert(val_equal && val_size);
265 assert(resize == 0 || resize == 1);
266
267 if (size < LYHT_MIN_SIZE) {
268 size = LYHT_MIN_SIZE;
269 }
270
271 ht = malloc(sizeof *ht);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200272 LY_CHECK_ERR_RET(!ht, LOGMEM(NULL), NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200273
274 ht->used = 0;
275 ht->size = size;
276 ht->val_equal = val_equal;
277 ht->cb_data = cb_data;
278 ht->resize = (uint16_t)resize;
279
280 ht->rec_size = (sizeof(struct ht_rec) - 1) + val_size;
281 /* allocate the records correctly */
282 ht->recs = calloc(size, ht->rec_size);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200283 LY_CHECK_ERR_RET(!ht->recs, free(ht); LOGMEM(NULL), NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200284
285 return ht;
286}
287
288values_equal_cb
289lyht_set_cb(struct hash_table *ht, values_equal_cb new_val_equal)
290{
291 values_equal_cb prev;
292
293 prev = ht->val_equal;
294 ht->val_equal = new_val_equal;
295 return prev;
296}
297
298void *
299lyht_set_cb_data(struct hash_table *ht, void *new_cb_data)
300{
301 void *prev;
302
303 prev = ht->cb_data;
304 ht->cb_data = new_cb_data;
305 return prev;
306}
307
308struct hash_table *
309lyht_dup(const struct hash_table *orig)
310{
311 struct hash_table *ht;
312
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200313 LY_CHECK_ARG_RET(NULL, orig, NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200314
315 ht = lyht_new(orig->size, orig->rec_size - (sizeof(struct ht_rec) - 1), orig->val_equal, orig->cb_data, orig->resize ? 1 : 0);
316 if (!ht) {
317 return NULL;
318 }
319
320 memcpy(ht->recs, orig->recs, orig->used * orig->rec_size);
321 ht->used = orig->used;
322 return ht;
323}
324
325void
326lyht_free(struct hash_table *ht)
327{
328 if (ht) {
329 free(ht->recs);
330 free(ht);
331 }
332}
333
334static LY_ERR
335lyht_resize(struct hash_table *ht, int enlarge)
336{
337 struct ht_rec *rec;
338 unsigned char *old_recs;
339 uint32_t i, old_size;
340 int ret;
341
342 old_recs = ht->recs;
343 old_size = ht->size;
344
345 if (enlarge) {
346 /* double the size */
347 ht->size <<= 1;
348 } else {
349 /* half the size */
350 ht->size >>= 1;
351 }
352
353 ht->recs = calloc(ht->size, ht->rec_size);
Michal Vaskob3d0d6b2018-09-07 10:17:33 +0200354 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 +0200355
356 /* reset used, it will increase again */
357 ht->used = 0;
358
359 /* add all the old records into the new records array */
360 for (i = 0; i < old_size; ++i) {
361 rec = lyht_get_rec(old_recs, ht->rec_size, i);
362 if (rec->hits > 0) {
363 ret = lyht_insert(ht, rec->val, rec->hash, NULL);
364 assert(!ret);
365 (void)ret;
366 }
367 }
368
369 /* final touches */
370 free(old_recs);
371 return LY_SUCCESS;
372}
373
Michal Vaskoda859032020-07-14 12:20:14 +0200374/**
375 * @brief Search for the first match.
376 *
377 * @param[in] ht Hash table to search in.
378 * @param[in] hash Hash to find.
379 * @param[out] rec_p Optional found record.
380 * @return LY_SUCCESS hash found, returned its record,
381 * @return LY_ENOTFOUND hash not found, returned the record where it would be inserted.
382 */
383static LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200384lyht_find_first(struct hash_table *ht, uint32_t hash, struct ht_rec **rec_p)
385{
386 struct ht_rec *rec;
387 uint32_t i, idx;
388
389 if (rec_p) {
390 *rec_p = NULL;
391 }
392
393 idx = i = hash & (ht->size - 1);
394 rec = lyht_get_rec(ht->recs, ht->rec_size, idx);
395
396 /* skip through overflow and deleted records */
397 while ((rec->hits != 0) && ((rec->hits == -1) || ((rec->hash & (ht->size - 1)) != idx))) {
398 if ((rec->hits == -1) && rec_p && !(*rec_p)) {
399 /* remember this record for return */
400 *rec_p = rec;
401 }
402 i = (i + 1) % ht->size;
403 if (i == idx) {
404 /* we went through all the records (very unlikely, but possible when many records are invalid),
405 * just return not found */
406 assert(!rec_p || *rec_p);
Michal Vaskoda859032020-07-14 12:20:14 +0200407 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200408 }
409 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
410 }
411 if (rec->hits == 0) {
412 /* we could not find the value */
413 if (rec_p && !*rec_p) {
414 *rec_p = rec;
415 }
Michal Vaskoda859032020-07-14 12:20:14 +0200416 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200417 }
418
419 /* we have found a record with equal (shortened) hash */
420 if (rec_p) {
421 *rec_p = rec;
422 }
Michal Vaskoda859032020-07-14 12:20:14 +0200423 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200424}
425
426/**
427 * @brief Search for the next collision.
428 *
429 * @param[in] ht Hash table to search in.
430 * @param[in,out] last Last returned collision record.
431 * @param[in] first First collision record (hits > 1).
Michal Vaskoda859032020-07-14 12:20:14 +0200432 * @return LY_SUCCESS when hash collision found, \p last points to this next collision,
433 * @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 +0200434 */
Michal Vaskoda859032020-07-14 12:20:14 +0200435static LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200436lyht_find_collision(struct hash_table *ht, struct ht_rec **last, struct ht_rec *first)
437{
438 struct ht_rec *empty = NULL;
439 uint32_t i, idx;
440
441 assert(last && *last);
442
443 idx = (*last)->hash & (ht->size - 1);
444 i = (((unsigned char *)*last) - ht->recs) / ht->rec_size;
445
446 do {
447 i = (i + 1) % ht->size;
448 *last = lyht_get_rec(ht->recs, ht->rec_size, i);
449 if (*last == first) {
450 /* we went through all the records (very unlikely, but possible when many records are invalid),
451 * just return an invalid record */
452 assert(empty);
453 *last = empty;
Michal Vaskoda859032020-07-14 12:20:14 +0200454 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200455 }
456
457 if (((*last)->hits == -1) && !empty) {
458 empty = *last;
459 }
460 } while (((*last)->hits != 0) && (((*last)->hits == -1) || (((*last)->hash & (ht->size - 1)) != idx)));
461
462 if ((*last)->hits > 0) {
463 /* we found a collision */
464 assert((*last)->hits == 1);
Michal Vaskoda859032020-07-14 12:20:14 +0200465 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200466 }
467
468 /* no next collision found, return the record where it would be inserted */
469 if (empty) {
470 *last = empty;
471 } /* else (*last)->hits == 0, it is already correct */
Michal Vaskoda859032020-07-14 12:20:14 +0200472 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200473}
474
Michal Vaskoda859032020-07-14 12:20:14 +0200475/**
476 * @brief Search for a record with specific value and hash.
477 *
478 * @param[in] ht Hash table to search in.
479 * @param[in] val_p Pointer to the value to find.
480 * @param[in] hash Hash to find.
481 * @param[in] mod Operation kind for the val_equal callback.
482 * @param[out] crec_p Optional found first record.
483 * @param[out] col Optional collision number of @p rec_p, 0 for no collision.
484 * @param[out] rec_p Found exact matching record, may be a collision of @p crec_p.
485 * @return LY_ENOTFOUND if no record found,
486 * @return LY_SUCCESS if record was found.
487 */
488static LY_ERR
489lyht_find_rec(struct hash_table *ht, void *val_p, uint32_t hash, int mod, struct ht_rec **crec_p, uint32_t *col,
490 struct ht_rec **rec_p)
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200491{
492 struct ht_rec *rec, *crec;
493 uint32_t i, c;
Michal Vaskoda859032020-07-14 12:20:14 +0200494 LY_ERR r;
495
496 if (crec_p) {
497 *crec_p = NULL;
498 }
499 if (col) {
500 *col = 0;
501 }
502 *rec_p = NULL;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200503
504 if (lyht_find_first(ht, hash, &rec)) {
505 /* not found */
Michal Vaskoda859032020-07-14 12:20:14 +0200506 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200507 }
Michal Vaskoda859032020-07-14 12:20:14 +0200508 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200509 /* even the value matches */
Michal Vaskoda859032020-07-14 12:20:14 +0200510 if (crec_p) {
511 *crec_p = rec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200512 }
Michal Vaskoda859032020-07-14 12:20:14 +0200513 if (col) {
514 *col = 0;
515 }
516 *rec_p = rec;
517 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200518 }
519
520 /* some collisions, we need to go through them, too */
521 crec = rec;
Michal Vaskoda859032020-07-14 12:20:14 +0200522 c = crec->hits;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200523 for (i = 1; i < c; ++i) {
524 r = lyht_find_collision(ht, &rec, crec);
525 assert(!r);
526 (void)r;
527
528 /* compare values */
Michal Vaskoda859032020-07-14 12:20:14 +0200529 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
530 if (crec_p) {
531 *crec_p = crec;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200532 }
Michal Vaskoda859032020-07-14 12:20:14 +0200533 if (col) {
534 *col = i;
535 }
536 *rec_p = rec;
537 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200538 }
539 }
540
541 /* not found even in collisions */
Michal Vaskoda859032020-07-14 12:20:14 +0200542 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200543}
544
Michal Vaskoda859032020-07-14 12:20:14 +0200545LY_ERR
546lyht_find(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
547{
548 struct ht_rec *rec;
549
550 lyht_find_rec(ht, val_p, hash, 0, NULL, NULL, &rec);
551
552 if (rec && match_p) {
553 *match_p = rec->val;
554 }
555 return rec ? LY_SUCCESS : LY_ENOTFOUND;
556}
557
558LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200559lyht_find_next(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
560{
561 struct ht_rec *rec, *crec;
562 uint32_t i, c;
Michal Vaskoda859032020-07-14 12:20:14 +0200563 LY_ERR r;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200564
Michal Vaskoda859032020-07-14 12:20:14 +0200565 /* found the record of the previously found value */
566 if (lyht_find_rec(ht, val_p, hash, 1, &crec, &i, &rec)) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200567 /* not found, cannot happen */
Michal Vaskoda859032020-07-14 12:20:14 +0200568 LOGINT_RET(NULL);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200569 }
570
571 /* go through collisions and find next one after the previous one */
Michal Vaskoda859032020-07-14 12:20:14 +0200572 c = crec->hits;
573 for (++i; i < c; ++i) {
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200574 r = lyht_find_collision(ht, &rec, crec);
575 assert(!r);
576 (void)r;
577
Michal Vaskoda859032020-07-14 12:20:14 +0200578 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 0, ht->cb_data)) {
579 /* even the value matches */
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200580 if (match_p) {
581 *match_p = rec->val;
582 }
Michal Vaskoda859032020-07-14 12:20:14 +0200583 return LY_SUCCESS;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200584 }
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200585 }
586
587 /* the last equal value was already returned */
Michal Vaskoda859032020-07-14 12:20:14 +0200588 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200589}
590
591LY_ERR
592lyht_insert_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash,
593 values_equal_cb resize_val_equal, void **match_p)
594{
595 struct ht_rec *rec, *crec = NULL;
596 int32_t i;
597 int r, ret;
598 values_equal_cb old_val_equal;
599
600 if (!lyht_find_first(ht, hash, &rec)) {
601 /* we found matching shortened hash */
602 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
603 /* even the value matches */
604 if (match_p) {
605 *match_p = (void *)&rec->val;
606 }
607 return LY_EEXIST;
608 }
609
610 /* some collisions, we need to go through them, too */
611 crec = rec;
612 for (i = 1; i < crec->hits; ++i) {
613 r = lyht_find_collision(ht, &rec, crec);
614 assert(!r);
615
616 /* compare values */
617 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
618 if (match_p) {
619 *match_p = (void *)&rec->val;
620 }
621 return LY_EEXIST;
622 }
623 }
624
625 /* value not found, get the record where it will be inserted */
626 r = lyht_find_collision(ht, &rec, crec);
627 assert(r);
628 }
629
630 /* insert it into the returned record */
631 assert(rec->hits < 1);
632 rec->hash = hash;
633 rec->hits = 1;
634 memcpy(&rec->val, val_p, ht->rec_size - (sizeof(struct ht_rec) - 1));
635 if (match_p) {
636 *match_p = (void *)&rec->val;
637 }
638
639 if (crec) {
640 /* there was a collision, increase hits */
641 if (crec->hits == INT32_MAX) {
642 LOGINT(NULL);
643 }
644 ++crec->hits;
645 }
646
647 /* check size & enlarge if needed */
648 ret = LY_SUCCESS;
649 ++ht->used;
650 if (ht->resize) {
651 r = (ht->used * 100) / ht->size;
652 if ((ht->resize == 1) && (r >= LYHT_FIRST_SHRINK_PERCENTAGE)) {
653 /* enable shrinking */
654 ht->resize = 2;
655 }
656 if ((ht->resize == 2) && (r >= LYHT_ENLARGE_PERCENTAGE)) {
657 if (resize_val_equal) {
658 old_val_equal = lyht_set_cb(ht, resize_val_equal);
659 }
660
661 /* enlarge */
662 ret = lyht_resize(ht, 1);
663 /* if hash_table was resized, we need to find new matching value */
664 if (ret == LY_SUCCESS && match_p) {
665 lyht_find(ht, val_p, hash, match_p);
666 }
667
668 if (resize_val_equal) {
669 lyht_set_cb(ht, old_val_equal);
670 }
671 }
672 }
673 return ret;
674}
675
Radek Krejci0ae092d2018-09-20 16:43:19 +0200676LY_ERR
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200677lyht_insert(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p)
678{
679 return lyht_insert_with_resize_cb(ht, val_p, hash, NULL, match_p);
680}
681
682LY_ERR
683lyht_remove(struct hash_table *ht, void *val_p, uint32_t hash)
684{
685 struct ht_rec *rec, *crec;
686 int32_t i;
687 int first_matched = 0, r, ret;
688
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200689 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 +0200690
691 if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
692 /* even the value matches */
693 first_matched = 1;
694 }
695
696 /* we always need to go through collisions */
697 crec = rec;
698 for (i = 1; i < crec->hits; ++i) {
699 r = lyht_find_collision(ht, &rec, crec);
700 assert(!r);
701
702 /* compare values */
703 if (!first_matched && (rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
704 break;
705 }
706 }
707
708 if (i < crec->hits) {
709 /* one of collisions matched, reduce collision count, remove the record */
710 assert(!first_matched);
711 --crec->hits;
712 rec->hits = -1;
713 } else if (first_matched) {
714 /* the first record matches */
715 if (crec != rec) {
716 /* ... so put the last collision in its place */
717 rec->hits = crec->hits - 1;
718 memcpy(crec, rec, ht->rec_size);
719 }
720 rec->hits = -1;
721 } else {
722 /* value not found even in collisions */
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200723 return LY_ENOTFOUND;
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200724 }
725
726 /* check size & shrink if needed */
727 ret = LY_SUCCESS;
728 --ht->used;
729 if (ht->resize == 2) {
730 r = (ht->used * 100) / ht->size;
731 if ((r < LYHT_SHRINK_PERCENTAGE) && (ht->size > LYHT_MIN_SIZE)) {
732 /* shrink */
733 ret = lyht_resize(ht, 0);
734 }
735 }
736
737 return ret;
738}