/* SPDX-License-Identifier: LGPL-2.1-only */ /* * Copyright (c) 2012 Cumulus Networks, Inc */ #include "nl-default.h" #include "hashtable-api.h" #include #include #include #include "nl-aux-core/nl-core.h" /** * @ingroup core_types * @defgroup hashtable Hashtable * @{ */ /* Generic helper to handle regular and resizeable hash tables */ static nl_hash_table_t *_nl_hash_table_init(nl_hash_table_t *ht, int size) { ht->nodes = calloc(size, sizeof(*ht->nodes)); if (!ht->nodes) { return NULL; } ht->size = size; return ht; } /** * Allocate hashtable * @arg size Size of hashtable in number of elements * * @return Allocated hashtable or NULL. */ nl_hash_table_t *nl_hash_table_alloc(int size) { nl_hash_table_t *ht; ht = calloc(1, sizeof(*ht)); if (!ht) return NULL; return _nl_hash_table_init(ht, size); } /* Generic helper to handle regular and resizeable hash tables */ static void _nl_hash_table_free(nl_hash_table_t *ht) { int i; for (i = 0; i < ht->size; i++) { nl_hash_node_t *node = ht->nodes[i]; nl_hash_node_t *saved_node; while (node) { saved_node = node; node = node->next; nl_object_put(saved_node->obj); free(saved_node); } } free(ht->nodes); } /** * Free hashtable including all nodes * @arg ht Hashtable * * @note Reference counter of all objects in the hashtable will be decremented. */ void nl_hash_table_free(nl_hash_table_t *ht) { _nl_hash_table_free(ht); free(ht); } /** * Lookup identical object in hashtable * @arg ht Hashtable * @arg obj Object to lookup * * Generates hashkey for `obj` and traverses the corresponding chain calling * `nl_object_identical()` on each trying to find a match. * * @return Pointer to object if match was found or NULL. */ struct nl_object *nl_hash_table_lookup(nl_hash_table_t *ht, struct nl_object *obj) { nl_hash_node_t *node; uint32_t key_hash; nl_object_keygen(obj, &key_hash, ht->size); node = ht->nodes[key_hash]; while (node) { if (nl_object_identical(node->obj, obj)) return node->obj; node = node->next; } return NULL; } /** * Add object to hashtable * @arg ht Hashtable * @arg obj Object to add * * Adds `obj` to the hashtable. Object type must support hashing, otherwise all * objects will be added to the chain `0`. * * @note The reference counter of the object is incremented. * * @return 0 on success or a negative error code * @retval -NLE_EXIST Identical object already present in hashtable */ int nl_hash_table_add(nl_hash_table_t *ht, struct nl_object *obj) { nl_hash_node_t *node; uint32_t key_hash; nl_object_keygen(obj, &key_hash, ht->size); node = ht->nodes[key_hash]; while (node) { if (nl_object_identical(node->obj, obj)) { NL_DBG(2, "Warning: Add to hashtable found duplicate...\n"); return -NLE_EXIST; } node = node->next; } NL_DBG(5, "adding cache entry of obj %p in table %p, with hash 0x%x\n", obj, ht, key_hash); node = malloc(sizeof(nl_hash_node_t)); if (!node) return -NLE_NOMEM; nl_object_get(obj); node->obj = obj; node->key = key_hash; node->key_size = sizeof(uint32_t); node->next = ht->nodes[key_hash]; ht->nodes[key_hash] = node; return 0; } /** * Remove object from hashtable * @arg ht Hashtable * @arg obj Object to remove * * Remove `obj` from hashtable if it exists. * * @note Reference counter of object will be decremented. * * @return 0 on success or a negative error code. * @retval -NLE_OBJ_NOTFOUND Object not present in hashtable. */ int nl_hash_table_del(nl_hash_table_t *ht, struct nl_object *obj) { nl_hash_node_t *node, *prev; uint32_t key_hash; nl_object_keygen(obj, &key_hash, ht->size); prev = node = ht->nodes[key_hash]; while (node) { if (nl_object_identical(node->obj, obj)) { nl_object_put(obj); NL_DBG(5, "deleting cache entry of obj %p in table %p, with" " hash 0x%x\n", obj, ht, key_hash); if (node == ht->nodes[key_hash]) ht->nodes[key_hash] = node->next; else prev->next = node->next; free(node); return 0; } prev = node; node = node->next; } return -NLE_OBJ_NOTFOUND; } uint32_t nl_hash(void *k, size_t length, uint32_t initval) { return (__nl_hash((char *)k, length, initval)); } typedef struct nl_rhash_table { struct nl_hash_table hash_table; int orig_size; /* Original size of hashtable at creation time */ /* Number of elements currently stored in the table. Needed to * determine when the table needs to be resized. */ int nelements; } nl_rhash_table_t; /* Internal load factor threshold at which the table will be resized. The * value is represented as a fraction where NL_HT_LOAD_NUM / NL_HT_LOAD_DEN * is the maximal allowed load factor. * * A value of 3/4 (0.75) provides a good trade-off between memory usage and * lookup performance for a chaining hash table. */ #define NL_HT_LOAD_NUM 3 #define NL_HT_LOAD_DEN 4 /** * Private helper which performs a rehash of the table to a new size. On * success the table fields (size/nodes) are updated and 0 is returned. * On allocation failure the table is left untouched and -NLE_NOMEM is * returned so that the caller can gracefully continue operating with the * original (but possibly crowded) table. */ static int nl_rhash_table_resize(nl_rhash_table_t *ht, int new_size) { nl_hash_node_t **new_nodes; int i; if (new_size <= 0) return 0; new_nodes = calloc(new_size, sizeof(*new_nodes)); if (!new_nodes) return -NLE_NOMEM; /* Re-hash all existing nodes into the new bucket array. */ for (i = 0; i < ht->hash_table.size; i++) { nl_hash_node_t *node = ht->hash_table.nodes[i]; while (node) { nl_hash_node_t *next = node->next; uint32_t new_hash; nl_object_keygen(node->obj, &new_hash, new_size); node->key = new_hash; /* Insert at head of the new bucket. */ node->next = new_nodes[new_hash]; new_nodes[new_hash] = node; node = next; } } free(ht->hash_table.nodes); ht->hash_table.nodes = new_nodes; ht->hash_table.size = new_size; return 0; } #define NL_INIT_RHASH_ENTRIES 8 /** * Allocate resizeable hashtable * * @return Allocated hashtable or NULL. */ nl_rhash_table_t *nl_rhash_table_alloc() { nl_rhash_table_t *ht; ht = calloc(1, sizeof(*ht)); if (!ht) goto errout; if (!_nl_hash_table_init(&ht->hash_table, NL_INIT_RHASH_ENTRIES)) { goto errout; } ht->orig_size = NL_INIT_RHASH_ENTRIES; ht->nelements = 0; return ht; errout: free(ht); return NULL; } /** * Free resizeable hashtable including all nodes * @arg ht Resizeable Hashtable * * @note Reference counter of all objects in the hashtable will be decremented. */ void nl_rhash_table_free(nl_rhash_table_t *ht) { _nl_hash_table_free(&ht->hash_table); free(ht); } /** * Lookup identical object in resizeable hashtable * @arg ht Resizeable Hashtable * @arg obj Object to lookup * * Generates hashkey for `obj` and traverses the corresponding chain calling * `nl_object_identical()` on each trying to find a match. * * @return Pointer to object if match was found or NULL. */ struct nl_object *nl_rhash_table_lookup(nl_rhash_table_t *ht, struct nl_object *obj) { return nl_hash_table_lookup(&ht->hash_table, obj); } /** * Add object to resizeable hashtable * @arg ht Resizeable Hashtable * @arg obj Object to add * * Adds `obj` to the resizeable hashtable. Object type must support hashing, * otherwise all objects will be added to the chain `0`. * * @note The reference counter of the object is incremented. * * @return 0 on success or a negative error code * @retval -NLE_EXIST Identical object already present in hashtable */ int nl_rhash_table_add(nl_rhash_table_t *ht, struct nl_object *obj) { int size; int rc; rc = nl_hash_table_add(&ht->hash_table, obj); if (rc < 0) return rc; if (obj->ce_ops->oo_keygen == NULL) return 0; /* Update element count and resize if load factor exceeded */ ht->nelements++; size = ht->hash_table.size; if (ht->nelements * NL_HT_LOAD_DEN > size * NL_HT_LOAD_NUM) { /* Ignore allocation failure – operating with the old table * keeps us functional albeit slower. */ nl_rhash_table_resize(ht, size * 2); } return 0; } /** * Remove object from resizeable hashtable * @arg ht Resizeable Hashtable * @arg obj Object to remove * * Remove `obj` from resizeable hashtable if it exists. * * @note Reference counter of object will be decremented. * * @return 0 on success or a negative error code. * @retval -NLE_OBJ_NOTFOUND Object not present in hashtable. */ int nl_rhash_table_del(nl_rhash_table_t *ht, struct nl_object *obj) { int size; int rc; rc = nl_hash_table_del(&ht->hash_table, obj); if (rc < 0) return rc; if (obj->ce_ops->oo_keygen == NULL) return 0; /* Decrement element count; shrink table if it became sparse. * We keep this simple and only shrink when the table is more than * 4 times sparser than our desired load factor. */ if (ht->nelements > 0) { ht->nelements--; } size = ht->hash_table.size; if (size > ht->orig_size && ht->nelements * NL_HT_LOAD_DEN < (size / 4) * NL_HT_LOAD_NUM) { int new_size = size / 2; if (new_size < ht->orig_size) new_size = ht->orig_size; nl_rhash_table_resize(ht, new_size); } return 0; } /** @} */