diff options
Diffstat (limited to 'src/hash_table.h')
| -rw-r--r-- | src/hash_table.h | 174 |
1 files changed, 77 insertions, 97 deletions
diff --git a/src/hash_table.h b/src/hash_table.h index 91ae63d..5780f1e 100644 --- a/src/hash_table.h +++ b/src/hash_table.h @@ -4,7 +4,7 @@ * @author Michal Vasko <mvasko@cesnet.cz> * @brief libyang hash table * - * Copyright (c) 2015 - 2022 CESNET, z.s.p.o. + * 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. @@ -16,27 +16,49 @@ #ifndef LY_HASH_TABLE_H_ #define LY_HASH_TABLE_H_ -#include <pthread.h> #include <stddef.h> #include <stdint.h> -#include "compat.h" +#ifdef __cplusplus +extern "C" { +#endif + #include "log.h" /** + * @struct ly_ht + * @brief libyang hash table. + */ +struct ly_ht; + +/** * @brief Compute hash from (several) string(s). * * Usage: * - init hash to 0 - * - repeatedly call ::dict_hash_multi(), provide hash from the last call - * - call ::dict_hash_multi() with key_part = NULL to finish the hash + * - repeatedly call ::lyht_hash_multi(), provide hash from the last call + * - call ::lyht_hash_multi() with key_part = NULL to finish the hash + * + * @param[in] hash Previous hash. + * @param[in] key_part Next key to hash, + * @param[in] len Length of @p key_part. + * @return Hash with the next key. */ -uint32_t dict_hash_multi(uint32_t hash, const char *key_part, size_t len); +LIBYANG_API_DECL uint32_t lyht_hash_multi(uint32_t hash, const char *key_part, size_t len); /** * @brief Compute hash from a string. + * + * Bob Jenkin's one-at-a-time hash + * http://www.burtleburtle.net/bob/hash/doobs.html + * + * Spooky hash is faster, but it works only for little endian architectures. + * + * @param[in] key Key to hash. + * @param[in] len Length of @p key. + * @return Hash of the key. */ -uint32_t dict_hash(const char *key, size_t len); +LIBYANG_API_DECL uint32_t lyht_hash(const char *key, size_t len); /** * @brief Callback for checking hash table values equivalence. @@ -49,82 +71,6 @@ uint32_t dict_hash(const char *key, size_t len); */ typedef ly_bool (*lyht_value_equal_cb)(void *val1_p, void *val2_p, ly_bool mod, void *cb_data); -/** reference value for 100% */ -#define LYHT_HUNDRED_PERCENTAGE 100 - -/** when the table is at least this much percent full, it is enlarged (double the size) */ -#define LYHT_ENLARGE_PERCENTAGE 75 - -/** only once the table is this much percent full, enable shrinking */ -#define LYHT_FIRST_SHRINK_PERCENTAGE 50 - -/** when the table is less than this much percent full, it is shrunk (half the size) */ -#define LYHT_SHRINK_PERCENTAGE 25 - -/** when the table has less than this much percent empty records, it is rehashed to get rid of all the invalid records */ -#define LYHT_REHASH_PERCENTAGE 2 - -/** never shrink beyond this size */ -#define LYHT_MIN_SIZE 8 - -/** - * @brief Generic hash table record. - */ -struct ht_rec { - uint32_t hash; /* hash of the value */ - int32_t hits; /* collision/overflow value count - 1 (a filled entry has 1 hit, - * special value -1 means a deleted record) */ - unsigned char val[1]; /* arbitrary-size value */ -} _PACKED; - -/** - * @brief (Very) generic hash table. - * - * Hash table with open addressing collision resolution and - * linear probing of interval 1 (next free record is used). - * Removal is lazy (removed records are only marked), but - * if possible, they are fully emptied. - */ -struct hash_table { - uint32_t used; /* number of values stored in the hash table (filled records) */ - uint32_t size; /* always holds 2^x == size (is power of 2), actually number of records allocated */ - uint32_t invalid; /* number of invalid records (deleted) */ - lyht_value_equal_cb val_equal; /* callback for testing value equivalence */ - void *cb_data; /* user data callback arbitrary value */ - uint16_t resize; /* 0 - resizing is disabled, * - * 1 - enlarging is enabled, * - * 2 - both shrinking and enlarging is enabled */ - uint16_t rec_size; /* real size (in bytes) of one record for accessing recs array */ - unsigned char *recs; /* pointer to the hash table itself (array of struct ht_rec) */ -}; - -struct dict_rec { - char *value; - uint32_t refcount; -}; - -/** - * dictionary to store repeating strings - */ -struct dict_table { - struct hash_table *hash_tab; - pthread_mutex_t lock; -}; - -/** - * @brief Initiate content (non-zero values) of the dictionary - * - * @param[in] dict Dictionary table to initiate - */ -void lydict_init(struct dict_table *dict); - -/** - * @brief Cleanup the dictionary content - * - * @param[in] dict Dictionary table to cleanup - */ -void lydict_clean(struct dict_table *dict); - /** * @brief Create new hash table. * @@ -135,7 +81,8 @@ void lydict_clean(struct dict_table *dict); * @param[in] resize Whether to resize the table on too few/too many records taken. * @return Empty hash table, NULL on error. */ -struct hash_table *lyht_new(uint32_t size, uint16_t val_size, lyht_value_equal_cb val_equal, void *cb_data, uint16_t resize); +LIBYANG_API_DECL struct ly_ht *lyht_new(uint32_t size, uint16_t val_size, lyht_value_equal_cb val_equal, void *cb_data, + uint16_t resize); /** * @brief Set hash table value equal callback. @@ -144,7 +91,7 @@ struct hash_table *lyht_new(uint32_t size, uint16_t val_size, lyht_value_equal_c * @param[in] new_val_equal New callback for checking value equivalence. * @return Previous callback for checking value equivalence. */ -lyht_value_equal_cb lyht_set_cb(struct hash_table *ht, lyht_value_equal_cb new_val_equal); +LIBYANG_API_DECL lyht_value_equal_cb lyht_set_cb(struct ly_ht *ht, lyht_value_equal_cb new_val_equal); /** * @brief Set hash table value equal callback user data. @@ -153,7 +100,7 @@ lyht_value_equal_cb lyht_set_cb(struct hash_table *ht, lyht_value_equal_cb new_v * @param[in] new_cb_data New data for values callback. * @return Previous data for values callback. */ -void *lyht_set_cb_data(struct hash_table *ht, void *new_cb_data); +LIBYANG_API_DECL void *lyht_set_cb_data(struct ly_ht *ht, void *new_cb_data); /** * @brief Make a duplicate of an existing hash table. @@ -161,14 +108,15 @@ void *lyht_set_cb_data(struct hash_table *ht, void *new_cb_data); * @param[in] orig Original hash table to duplicate. * @return Duplicated hash table @p orig, NULL on error. */ -struct hash_table *lyht_dup(const struct hash_table *orig); +LIBYANG_API_DECL struct ly_ht *lyht_dup(const struct ly_ht *orig); /** * @brief Free a hash table. * * @param[in] ht Hash table to be freed. + * @param[in] val_free Optional callback for freeing all the stored values, @p val_p is a pointer to a stored value. */ -void lyht_free(struct hash_table *ht); +LIBYANG_API_DECL void lyht_free(struct ly_ht *ht, void (*val_free)(void *val_p)); /** * @brief Find a value in a hash table. @@ -180,7 +128,21 @@ void lyht_free(struct hash_table *ht); * @return LY_SUCCESS if value was found, * @return LY_ENOTFOUND if not found. */ -LY_ERR lyht_find(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p); +LIBYANG_API_DECL LY_ERR lyht_find(const struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p); + +/** + * @brief Find a value in a hash table but use a custom val_equal callback. + * + * @param[in] ht Hash table to search in. + * @param[in] val_p Pointer to the value to find. + * @param[in] hash Hash of the stored value. + * @param[in] val_equal Callback for checking value equivalence. + * @param[out] match_p Pointer to the matching value, optional. + * @return LY_SUCCESS if value was found, + * @return LY_ENOTFOUND if not found. + */ +LIBYANG_API_DECL 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); /** * @brief Find another equal value in the hash table. @@ -192,7 +154,7 @@ LY_ERR lyht_find(struct hash_table *ht, void *val_p, uint32_t hash, void **match * @return LY_SUCCESS if value was found, * @return LY_ENOTFOUND if not found. */ -LY_ERR lyht_find_next(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p); +LIBYANG_API_DECL LY_ERR lyht_find_next(const struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p); /** * @brief Find another equal value in the hash table. Same functionality as ::lyht_find_next() @@ -206,7 +168,7 @@ LY_ERR lyht_find_next(struct hash_table *ht, void *val_p, uint32_t hash, void ** * @return LY_SUCCESS if value was found, * @return LY_ENOTFOUND if not found. */ -LY_ERR lyht_find_next_with_collision_cb(struct hash_table *ht, void *val_p, uint32_t hash, +LIBYANG_API_DECL 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); /** @@ -221,7 +183,20 @@ LY_ERR lyht_find_next_with_collision_cb(struct hash_table *ht, void *val_p, uint * @return LY_EEXIST in case the value is already present. * @return LY_EMEM in case of memory allocation failure. */ -LY_ERR lyht_insert(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p); +LIBYANG_API_DECL LY_ERR lyht_insert(struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p); + +/** + * @brief Insert a value into a hash table, without checking whether the value has already been inserted. + * + * @param[in] ht Hash table to insert into. + * @param[in] val_p Pointer to the value to insert. Be careful, if the values stored in the hash table + * are pointers, @p val_p must be a pointer to a pointer. + * @param[in] hash Hash of the stored value. + * @param[out] match_p Pointer to the stored value, optional + * @return LY_SUCCESS on success, + * @return LY_EMEM in case of memory allocation failure. + */ +LIBYANG_API_DECL LY_ERR lyht_insert_no_check(struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p); /** * @brief Insert a value into hash table. Same functionality as ::lyht_insert() @@ -238,8 +213,8 @@ LY_ERR lyht_insert(struct hash_table *ht, void *val_p, uint32_t hash, void **mat * @return LY_EEXIST in case the value is already present. * @return LY_EMEM in case of memory allocation failure. */ -LY_ERR lyht_insert_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal, - void **match_p); +LIBYANG_API_DECL 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); /** * @brief Remove a value from a hash table. @@ -251,7 +226,7 @@ LY_ERR lyht_insert_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t h * @return LY_SUCCESS on success, * @return LY_ENOTFOUND if value was not found. */ -LY_ERR lyht_remove(struct hash_table *ht, void *val_p, uint32_t hash); +LIBYANG_API_DECL LY_ERR lyht_remove(struct ly_ht *ht, void *val_p, uint32_t hash); /** * @brief Remove a value from a hash table. Same functionality as ::lyht_remove() @@ -266,7 +241,8 @@ LY_ERR lyht_remove(struct hash_table *ht, void *val_p, uint32_t hash); * @return LY_SUCCESS on success, * @return LY_ENOTFOUND if value was not found. */ -LY_ERR lyht_remove_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal); +LIBYANG_API_DECL LY_ERR lyht_remove_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash, + lyht_value_equal_cb resize_val_equal); /** * @brief Get suitable size of a hash table for a fixed number of items. @@ -274,6 +250,10 @@ LY_ERR lyht_remove_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t h * @param[in] item_count Number of stored items. * @return Hash table size. */ -uint32_t lyht_get_fixed_size(uint32_t item_count); +LIBYANG_API_DECL uint32_t lyht_get_fixed_size(uint32_t item_count); + +#ifdef __cplusplus +} +#endif #endif /* LY_HASH_TABLE_H_ */ |