summaryrefslogtreecommitdiffstats
path: root/src/hash_table.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/hash_table.c')
-rw-r--r--src/hash_table.c534
1 files changed, 534 insertions, 0 deletions
diff --git a/src/hash_table.c b/src/hash_table.c
new file mode 100644
index 0000000..f951e6a
--- /dev/null
+++ b/src/hash_table.c
@@ -0,0 +1,534 @@
+/**
+ * @file hash_table.c
+ * @author Radek Krejci <rkrejci@cesnet.cz>
+ * @author Michal Vasko <mvasko@cesnet.cz>
+ * @brief libyang generic hash table implementation
+ *
+ * Copyright (c) 2015 - 2023 CESNET, z.s.p.o.
+ *
+ * This source code is licensed under BSD 3-Clause License (the "License").
+ * You may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * https://opensource.org/licenses/BSD-3-Clause
+ */
+
+#include "hash_table.h"
+
+#include <assert.h>
+#include <pthread.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "compat.h"
+#include "dict.h"
+#include "log.h"
+#include "ly_common.h"
+
+LIBYANG_API_DEF uint32_t
+lyht_hash_multi(uint32_t hash, const char *key_part, size_t len)
+{
+ uint32_t i;
+
+ if (key_part && len) {
+ for (i = 0; i < len; ++i) {
+ hash += key_part[i];
+ hash += (hash << 10);
+ hash ^= (hash >> 6);
+ }
+ } else {
+ hash += (hash << 3);
+ hash ^= (hash >> 11);
+ hash += (hash << 15);
+ }
+
+ return hash;
+}
+
+LIBYANG_API_DEF uint32_t
+lyht_hash(const char *key, size_t len)
+{
+ uint32_t hash;
+
+ hash = lyht_hash_multi(0, key, len);
+ return lyht_hash_multi(hash, NULL, len);
+}
+
+static LY_ERR
+lyht_init_hlists_and_records(struct ly_ht *ht)
+{
+ struct ly_ht_rec *rec;
+ uint32_t i;
+
+ ht->recs = calloc(ht->size, ht->rec_size);
+ LY_CHECK_ERR_RET(!ht->recs, LOGMEM(NULL), LY_EMEM);
+ for (i = 0; i < ht->size; i++) {
+ rec = lyht_get_rec(ht->recs, ht->rec_size, i);
+ if (i != ht->size) {
+ rec->next = i + 1;
+ } else {
+ rec->next = LYHT_NO_RECORD;
+ }
+ }
+
+ ht->hlists = malloc(sizeof(ht->hlists[0]) * ht->size);
+ LY_CHECK_ERR_RET(!ht->hlists, free(ht->recs); LOGMEM(NULL), LY_EMEM);
+ for (i = 0; i < ht->size; i++) {
+ ht->hlists[i].first = LYHT_NO_RECORD;
+ ht->hlists[i].last = LYHT_NO_RECORD;
+ }
+ ht->first_free_rec = 0;
+
+ return LY_SUCCESS;
+}
+
+LIBYANG_API_DEF struct ly_ht *
+lyht_new(uint32_t size, uint16_t val_size, lyht_value_equal_cb val_equal, void *cb_data, uint16_t resize)
+{
+ struct ly_ht *ht;
+
+ /* check that 2^x == size (power of 2) */
+ assert(size && !(size & (size - 1)));
+ assert(val_equal && val_size);
+ assert(resize == 0 || resize == 1);
+
+ if (size < LYHT_MIN_SIZE) {
+ size = LYHT_MIN_SIZE;
+ }
+
+ ht = malloc(sizeof *ht);
+ LY_CHECK_ERR_RET(!ht, LOGMEM(NULL), NULL);
+
+ ht->used = 0;
+ ht->size = size;
+ ht->val_equal = val_equal;
+ ht->cb_data = cb_data;
+ ht->resize = resize;
+
+ ht->rec_size = SIZEOF_LY_HT_REC + val_size;
+ if (lyht_init_hlists_and_records(ht) != LY_SUCCESS) {
+ free(ht);
+ return NULL;
+ }
+
+ return ht;
+}
+
+LIBYANG_API_DEF lyht_value_equal_cb
+lyht_set_cb(struct ly_ht *ht, lyht_value_equal_cb new_val_equal)
+{
+ lyht_value_equal_cb prev;
+
+ prev = ht->val_equal;
+ ht->val_equal = new_val_equal;
+ return prev;
+}
+
+LIBYANG_API_DEF void *
+lyht_set_cb_data(struct ly_ht *ht, void *new_cb_data)
+{
+ void *prev;
+
+ prev = ht->cb_data;
+ ht->cb_data = new_cb_data;
+ return prev;
+}
+
+LIBYANG_API_DEF struct ly_ht *
+lyht_dup(const struct ly_ht *orig)
+{
+ struct ly_ht *ht;
+
+ LY_CHECK_ARG_RET(NULL, orig, NULL);
+
+ ht = lyht_new(orig->size, orig->rec_size - SIZEOF_LY_HT_REC, orig->val_equal, orig->cb_data, orig->resize ? 1 : 0);
+ if (!ht) {
+ return NULL;
+ }
+
+ memcpy(ht->hlists, orig->hlists, sizeof(ht->hlists[0]) * orig->size);
+ memcpy(ht->recs, orig->recs, (size_t)orig->size * orig->rec_size);
+ ht->used = orig->used;
+ return ht;
+}
+
+LIBYANG_API_DEF void
+lyht_free(struct ly_ht *ht, void (*val_free)(void *val_p))
+{
+ struct ly_ht_rec *rec;
+ uint32_t hlist_idx;
+ uint32_t rec_idx;
+
+ if (!ht) {
+ return;
+ }
+
+ if (val_free) {
+ LYHT_ITER_ALL_RECS(ht, hlist_idx, rec_idx, rec) {
+ val_free(&rec->val);
+ }
+ }
+ free(ht->hlists);
+ free(ht->recs);
+ free(ht);
+}
+
+/**
+ * @brief Resize a hash table.
+ *
+ * @param[in] ht Hash table to resize.
+ * @param[in] operation Operation to perform. 1 to enlarge, -1 to shrink, 0 to only rehash all records.
+ * @return LY_ERR value.
+ */
+static LY_ERR
+lyht_resize(struct ly_ht *ht, int operation, int check)
+{
+ struct ly_ht_rec *rec;
+ struct ly_ht_hlist *old_hlists;
+ unsigned char *old_recs;
+ uint32_t old_first_free_rec;
+ uint32_t i, old_size;
+ uint32_t rec_idx;
+
+ old_hlists = ht->hlists;
+ old_recs = ht->recs;
+ old_size = ht->size;
+ old_first_free_rec = ht->first_free_rec;
+
+ if (operation > 0) {
+ /* double the size */
+ ht->size <<= 1;
+ } else if (operation < 0) {
+ /* half the size */
+ ht->size >>= 1;
+ }
+
+ if (lyht_init_hlists_and_records(ht) != LY_SUCCESS) {
+ ht->hlists = old_hlists;
+ ht->recs = old_recs;
+ ht->size = old_size;
+ ht->first_free_rec = old_first_free_rec;
+ return LY_EMEM;
+ }
+
+ /* reset used, it will increase again */
+ ht->used = 0;
+
+ /* add all the old records into the new records array */
+ for (i = 0; i < old_size; i++) {
+ for (rec_idx = old_hlists[i].first, rec = lyht_get_rec(old_recs, ht->rec_size, rec_idx);
+ rec_idx != LYHT_NO_RECORD;
+ rec_idx = rec->next, rec = lyht_get_rec(old_recs, ht->rec_size, rec_idx)) {
+ LY_ERR ret;
+
+ if (check) {
+ ret = lyht_insert(ht, rec->val, rec->hash, NULL);
+ } else {
+ ret = lyht_insert_no_check(ht, rec->val, rec->hash, NULL);
+ }
+
+ assert(!ret);
+ (void)ret;
+ }
+ }
+
+ /* final touches */
+ free(old_recs);
+ free(old_hlists);
+ return LY_SUCCESS;
+}
+
+/**
+ * @brief Search for a record with specific value and hash.
+ *
+ * @param[in] ht Hash table to search in.
+ * @param[in] val_p Pointer to the value to find.
+ * @param[in] hash Hash to find.
+ * @param[in] mod Whether the operation modifies the hash table (insert or remove) or not (find).
+ * @param[in] val_equal Callback for checking value equivalence.
+ * @param[out] crec_p Optional found first record.
+ * @param[out] col Optional collision number of @p rec_p, 0 for no collision.
+ * @param[out] rec_p Found exact matching record, may be a collision of @p crec_p.
+ * @return LY_ENOTFOUND if no record found,
+ * @return LY_SUCCESS if record was found.
+ */
+static LY_ERR
+lyht_find_rec(const struct ly_ht *ht, void *val_p, uint32_t hash, ly_bool mod, lyht_value_equal_cb val_equal,
+ struct ly_ht_rec **crec_p, uint32_t *col, struct ly_ht_rec **rec_p)
+{
+ uint32_t hlist_idx = hash & (ht->size - 1);
+ struct ly_ht_rec *rec;
+ uint32_t rec_idx;
+
+ if (crec_p) {
+ *crec_p = NULL;
+ }
+ if (col) {
+ *col = 0;
+ }
+ *rec_p = NULL;
+
+ LYHT_ITER_HLIST_RECS(ht, hlist_idx, rec_idx, rec) {
+ if ((rec->hash == hash) && val_equal(val_p, &rec->val, mod, ht->cb_data)) {
+ if (crec_p) {
+ *crec_p = rec;
+ }
+ *rec_p = rec;
+ return LY_SUCCESS;
+ }
+
+ if (col) {
+ *col = *col + 1;
+ }
+ }
+
+ /* not found even in collisions */
+ return LY_ENOTFOUND;
+}
+
+LIBYANG_API_DEF LY_ERR
+lyht_find(const struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p)
+{
+ struct ly_ht_rec *rec;
+
+ lyht_find_rec(ht, val_p, hash, 0, ht->val_equal, NULL, NULL, &rec);
+
+ if (rec && match_p) {
+ *match_p = rec->val;
+ }
+ return rec ? LY_SUCCESS : LY_ENOTFOUND;
+}
+
+LIBYANG_API_DEF LY_ERR
+lyht_find_with_val_cb(const struct ly_ht *ht, void *val_p, uint32_t hash, lyht_value_equal_cb val_equal, void **match_p)
+{
+ struct ly_ht_rec *rec;
+
+ lyht_find_rec(ht, val_p, hash, 0, val_equal ? val_equal : ht->val_equal, NULL, NULL, &rec);
+
+ if (rec && match_p) {
+ *match_p = rec->val;
+ }
+ return rec ? LY_SUCCESS : LY_ENOTFOUND;
+}
+
+LIBYANG_API_DEF LY_ERR
+lyht_find_next_with_collision_cb(const struct ly_ht *ht, void *val_p, uint32_t hash,
+ lyht_value_equal_cb collision_val_equal, void **match_p)
+{
+ struct ly_ht_rec *rec, *crec;
+ uint32_t rec_idx;
+ uint32_t i;
+
+ /* find the record of the previously found value */
+ if (lyht_find_rec(ht, val_p, hash, 1, ht->val_equal, &crec, &i, &rec)) {
+ /* not found, cannot happen */
+ LOGINT_RET(NULL);
+ }
+
+ for (rec_idx = rec->next, rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
+ rec_idx != LYHT_NO_RECORD;
+ rec_idx = rec->next, rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx)) {
+
+ if (rec->hash != hash) {
+ continue;
+ }
+
+ if (collision_val_equal) {
+ if (collision_val_equal(val_p, &rec->val, 0, ht->cb_data)) {
+ /* even the value matches */
+ if (match_p) {
+ *match_p = rec->val;
+ }
+ return LY_SUCCESS;
+ }
+ } else if (ht->val_equal(val_p, &rec->val, 0, ht->cb_data)) {
+ /* even the value matches */
+ if (match_p) {
+ *match_p = rec->val;
+ }
+ return LY_SUCCESS;
+ }
+ }
+
+ /* the last equal value was already returned */
+ return LY_ENOTFOUND;
+}
+
+LIBYANG_API_DEF LY_ERR
+lyht_find_next(const struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p)
+{
+ return lyht_find_next_with_collision_cb(ht, val_p, hash, NULL, match_p);
+}
+
+static LY_ERR
+_lyht_insert_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal,
+ void **match_p, int check)
+{
+ uint32_t hlist_idx = hash & (ht->size - 1);
+ LY_ERR r, ret = LY_SUCCESS;
+ struct ly_ht_rec *rec, *prev_rec;
+ lyht_value_equal_cb old_val_equal = NULL;
+ uint32_t rec_idx;
+
+ if (check) {
+ if (lyht_find_rec(ht, val_p, hash, 1, ht->val_equal, NULL, NULL, &rec) == LY_SUCCESS) {
+ if (rec && match_p) {
+ *match_p = rec->val;
+ }
+ return LY_EEXIST;
+ }
+ }
+
+ rec_idx = ht->first_free_rec;
+ assert(rec_idx < ht->size);
+ rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
+ ht->first_free_rec = rec->next;
+
+ if (ht->hlists[hlist_idx].first == LYHT_NO_RECORD) {
+ ht->hlists[hlist_idx].first = rec_idx;
+ } else {
+ prev_rec = lyht_get_rec(ht->recs, ht->rec_size, ht->hlists[hlist_idx].last);
+ prev_rec->next = rec_idx;
+ }
+ rec->next = LYHT_NO_RECORD;
+ ht->hlists[hlist_idx].last = rec_idx;
+
+ rec->hash = hash;
+ memcpy(&rec->val, val_p, ht->rec_size - SIZEOF_LY_HT_REC);
+ if (match_p) {
+ *match_p = (void *)&rec->val;
+ }
+
+ /* check size & enlarge if needed */
+ ++ht->used;
+ if (ht->resize) {
+ r = (ht->used * LYHT_HUNDRED_PERCENTAGE) / ht->size;
+ if ((ht->resize == 1) && (r >= LYHT_FIRST_SHRINK_PERCENTAGE)) {
+ /* enable shrinking */
+ ht->resize = 2;
+ }
+ if ((ht->resize == 2) && (r >= LYHT_ENLARGE_PERCENTAGE)) {
+ if (resize_val_equal) {
+ old_val_equal = lyht_set_cb(ht, resize_val_equal);
+ }
+
+ /* enlarge */
+ ret = lyht_resize(ht, 1, check);
+ /* if hash_table was resized, we need to find new matching value */
+ if ((ret == LY_SUCCESS) && match_p) {
+ ret = lyht_find(ht, val_p, hash, match_p);
+ assert(!ret);
+ }
+
+ if (resize_val_equal) {
+ lyht_set_cb(ht, old_val_equal);
+ }
+ }
+ }
+ return ret;
+}
+
+LIBYANG_API_DEF LY_ERR
+lyht_insert_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal,
+ void **match_p)
+{
+ return _lyht_insert_with_resize_cb(ht, val_p, hash, resize_val_equal, match_p, 1);
+}
+
+LIBYANG_API_DEF LY_ERR
+lyht_insert(struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p)
+{
+ return _lyht_insert_with_resize_cb(ht, val_p, hash, NULL, match_p, 1);
+}
+
+LIBYANG_API_DEF LY_ERR
+lyht_insert_no_check(struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p)
+{
+ return _lyht_insert_with_resize_cb(ht, val_p, hash, NULL, match_p, 0);
+}
+
+LIBYANG_API_DEF LY_ERR
+lyht_remove_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal)
+{
+ struct ly_ht_rec *found_rec, *prev_rec, *rec;
+ uint32_t hlist_idx = hash & (ht->size - 1);
+ LY_ERR r, ret = LY_SUCCESS;
+ lyht_value_equal_cb old_val_equal = NULL;
+ uint32_t prev_rec_idx;
+ uint32_t rec_idx;
+
+ if (lyht_find_rec(ht, val_p, hash, 1, ht->val_equal, NULL, NULL, &found_rec)) {
+ LOGARG(NULL, hash);
+ return LY_ENOTFOUND;
+ }
+
+ prev_rec_idx = LYHT_NO_RECORD;
+ LYHT_ITER_HLIST_RECS(ht, hlist_idx, rec_idx, rec) {
+ if (rec == found_rec) {
+ break;
+ }
+ prev_rec_idx = rec_idx;
+ }
+
+ if (prev_rec_idx == LYHT_NO_RECORD) {
+ ht->hlists[hlist_idx].first = rec->next;
+ if (rec->next == LYHT_NO_RECORD) {
+ ht->hlists[hlist_idx].last = LYHT_NO_RECORD;
+ }
+ } else {
+ prev_rec = lyht_get_rec(ht->recs, ht->rec_size, prev_rec_idx);
+ prev_rec->next = rec->next;
+ if (rec->next == LYHT_NO_RECORD) {
+ ht->hlists[hlist_idx].last = prev_rec_idx;
+ }
+ }
+
+ rec->next = ht->first_free_rec;
+ ht->first_free_rec = rec_idx;
+
+ /* check size & shrink if needed */
+ --ht->used;
+ if (ht->resize == 2) {
+ r = (ht->used * LYHT_HUNDRED_PERCENTAGE) / ht->size;
+ if ((r < LYHT_SHRINK_PERCENTAGE) && (ht->size > LYHT_MIN_SIZE)) {
+ if (resize_val_equal) {
+ old_val_equal = lyht_set_cb(ht, resize_val_equal);
+ }
+
+ /* shrink */
+ ret = lyht_resize(ht, -1, 1);
+
+ if (resize_val_equal) {
+ lyht_set_cb(ht, old_val_equal);
+ }
+ }
+ }
+
+ return ret;
+}
+
+LIBYANG_API_DEF LY_ERR
+lyht_remove(struct ly_ht *ht, void *val_p, uint32_t hash)
+{
+ return lyht_remove_with_resize_cb(ht, val_p, hash, NULL);
+}
+
+LIBYANG_API_DEF uint32_t
+lyht_get_fixed_size(uint32_t item_count)
+{
+ if (item_count == 0) {
+ return 1;
+ }
+
+ /* return next power of 2 (greater or equal) */
+ item_count--;
+ item_count |= item_count >> 1;
+ item_count |= item_count >> 2;
+ item_count |= item_count >> 4;
+ item_count |= item_count >> 8;
+ item_count |= item_count >> 16;
+
+ return item_count + 1;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-25 07:10:18 +0000