blob: 5780f1e2be8139bb2e151cfb029720cfbe9beb08 [file] [log] [blame]
Radek Krejci5aeea3a2018-09-05 13:29:36 +02001/**
2 * @file hash_table.h
3 * @author Radek Krejci <rkrejci@cesnet.cz>
4 * @author Michal Vasko <mvasko@cesnet.cz>
5 * @brief libyang hash table
6 *
Michal Vaskoae130f52023-04-20 14:25:16 +02007 * Copyright (c) 2015 - 2023 CESNET, z.s.p.o.
Radek Krejci5aeea3a2018-09-05 13:29:36 +02008 *
9 * This source code is licensed under BSD 3-Clause License (the "License").
10 * You may not use this file except in compliance with the License.
11 * You may obtain a copy of the License at
12 *
13 * https://opensource.org/licenses/BSD-3-Clause
14 */
15
16#ifndef LY_HASH_TABLE_H_
17#define LY_HASH_TABLE_H_
18
Radek Krejcie7b95092019-05-15 11:03:07 +020019#include <stddef.h>
20#include <stdint.h>
21
Michal Vaskoae130f52023-04-20 14:25:16 +020022#ifdef __cplusplus
23extern "C" {
24#endif
25
Radek Krejcie7b95092019-05-15 11:03:07 +020026#include "log.h"
Radek Krejci5aeea3a2018-09-05 13:29:36 +020027
28/**
Michal Vaskob2c26802023-05-24 14:57:03 +020029 * @struct ly_ht
30 * @brief libyang hash table.
31 */
32struct ly_ht;
33
34/**
Radek Krejci5aeea3a2018-09-05 13:29:36 +020035 * @brief Compute hash from (several) string(s).
36 *
37 * Usage:
38 * - init hash to 0
Michal Vaskoae130f52023-04-20 14:25:16 +020039 * - repeatedly call ::lyht_hash_multi(), provide hash from the last call
40 * - call ::lyht_hash_multi() with key_part = NULL to finish the hash
41 *
42 * @param[in] hash Previous hash.
43 * @param[in] key_part Next key to hash,
44 * @param[in] len Length of @p key_part.
45 * @return Hash with the next key.
Radek Krejci5aeea3a2018-09-05 13:29:36 +020046 */
Michal Vaskoae130f52023-04-20 14:25:16 +020047LIBYANG_API_DECL uint32_t lyht_hash_multi(uint32_t hash, const char *key_part, size_t len);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020048
Michal Vaskoa655fca2022-09-05 15:48:31 +020049/**
Radek Krejcif2dc4c52018-11-08 09:04:13 +010050 * @brief Compute hash from a string.
Michal Vaskoae130f52023-04-20 14:25:16 +020051 *
52 * Bob Jenkin's one-at-a-time hash
53 * http://www.burtleburtle.net/bob/hash/doobs.html
54 *
55 * Spooky hash is faster, but it works only for little endian architectures.
56 *
57 * @param[in] key Key to hash.
58 * @param[in] len Length of @p key.
59 * @return Hash of the key.
Radek Krejcif2dc4c52018-11-08 09:04:13 +010060 */
Michal Vaskoae130f52023-04-20 14:25:16 +020061LIBYANG_API_DECL uint32_t lyht_hash(const char *key, size_t len);
Radek Krejcif2dc4c52018-11-08 09:04:13 +010062
Radek Krejci5aeea3a2018-09-05 13:29:36 +020063/**
64 * @brief Callback for checking hash table values equivalence.
65 *
Michal Vasko90932a92020-02-12 14:33:03 +010066 * @param[in] val1_p Pointer to the first value, the one being searched (inserted/removed).
67 * @param[in] val2_p Pointer to the second value, the one stored in the hash table.
Radek Krejci5aeea3a2018-09-05 13:29:36 +020068 * @param[in] mod Whether the operation modifies the hash table (insert or remove) or not (find).
69 * @param[in] cb_data User callback data.
Radek Krejci857189e2020-09-01 13:26:36 +020070 * @return false (non-equal) or true (equal).
Radek Krejci5aeea3a2018-09-05 13:29:36 +020071 */
Michal Vasko62524a92021-02-26 10:08:50 +010072typedef ly_bool (*lyht_value_equal_cb)(void *val1_p, void *val2_p, ly_bool mod, void *cb_data);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020073
Radek Krejci5aeea3a2018-09-05 13:29:36 +020074/**
75 * @brief Create new hash table.
76 *
77 * @param[in] size Starting size of the hash table (capacity of values), must be power of 2.
78 * @param[in] val_size Size in bytes of value (the stored hashed item).
79 * @param[in] val_equal Callback for checking value equivalence.
Michal Vaskoa655fca2022-09-05 15:48:31 +020080 * @param[in] cb_data User data always passed to @p val_equal.
Radek Krejci5aeea3a2018-09-05 13:29:36 +020081 * @param[in] resize Whether to resize the table on too few/too many records taken.
82 * @return Empty hash table, NULL on error.
83 */
Michal Vaskoae130f52023-04-20 14:25:16 +020084LIBYANG_API_DECL struct ly_ht *lyht_new(uint32_t size, uint16_t val_size, lyht_value_equal_cb val_equal, void *cb_data,
85 uint16_t resize);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020086
87/**
88 * @brief Set hash table value equal callback.
89 *
90 * @param[in] ht Hash table to modify.
91 * @param[in] new_val_equal New callback for checking value equivalence.
92 * @return Previous callback for checking value equivalence.
93 */
Michal Vaskoae130f52023-04-20 14:25:16 +020094LIBYANG_API_DECL lyht_value_equal_cb lyht_set_cb(struct ly_ht *ht, lyht_value_equal_cb new_val_equal);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020095
96/**
97 * @brief Set hash table value equal callback user data.
98 *
99 * @param[in] ht Hash table to modify.
100 * @param[in] new_cb_data New data for values callback.
101 * @return Previous data for values callback.
102 */
Michal Vaskoae130f52023-04-20 14:25:16 +0200103LIBYANG_API_DECL void *lyht_set_cb_data(struct ly_ht *ht, void *new_cb_data);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200104
105/**
106 * @brief Make a duplicate of an existing hash table.
107 *
108 * @param[in] orig Original hash table to duplicate.
Michal Vaskoa655fca2022-09-05 15:48:31 +0200109 * @return Duplicated hash table @p orig, NULL on error.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200110 */
Michal Vaskoae130f52023-04-20 14:25:16 +0200111LIBYANG_API_DECL struct ly_ht *lyht_dup(const struct ly_ht *orig);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200112
113/**
114 * @brief Free a hash table.
115 *
116 * @param[in] ht Hash table to be freed.
Michal Vasko88ccd582023-03-30 11:50:57 +0200117 * @param[in] val_free Optional callback for freeing all the stored values, @p val_p is a pointer to a stored value.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200118 */
Michal Vaskoae130f52023-04-20 14:25:16 +0200119LIBYANG_API_DECL void lyht_free(struct ly_ht *ht, void (*val_free)(void *val_p));
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200120
121/**
122 * @brief Find a value in a hash table.
123 *
124 * @param[in] ht Hash table to search in.
125 * @param[in] val_p Pointer to the value to find.
126 * @param[in] hash Hash of the stored value.
127 * @param[out] match_p Pointer to the matching value, optional.
Michal Vaskoda859032020-07-14 12:20:14 +0200128 * @return LY_SUCCESS if value was found,
129 * @return LY_ENOTFOUND if not found.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200130 */
Michal Vaskof1e09412023-10-23 10:03:21 +0200131LIBYANG_API_DECL LY_ERR lyht_find(const struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p);
132
133/**
134 * @brief Find a value in a hash table but use a custom val_equal callback.
135 *
136 * @param[in] ht Hash table to search in.
137 * @param[in] val_p Pointer to the value to find.
138 * @param[in] hash Hash of the stored value.
139 * @param[in] val_equal Callback for checking value equivalence.
140 * @param[out] match_p Pointer to the matching value, optional.
141 * @return LY_SUCCESS if value was found,
142 * @return LY_ENOTFOUND if not found.
143 */
144LIBYANG_API_DECL LY_ERR lyht_find_with_val_cb(const struct ly_ht *ht, void *val_p, uint32_t hash,
145 lyht_value_equal_cb val_equal, void **match_p);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200146
147/**
148 * @brief Find another equal value in the hash table.
149 *
150 * @param[in] ht Hash table to search in.
Michal Vaskoa655fca2022-09-05 15:48:31 +0200151 * @param[in] val_p Pointer to the previously found value in @p ht.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200152 * @param[in] hash Hash of the previously found value.
153 * @param[out] match_p Pointer to the matching value, optional.
Michal Vaskoda859032020-07-14 12:20:14 +0200154 * @return LY_SUCCESS if value was found,
155 * @return LY_ENOTFOUND if not found.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200156 */
Michal Vaskof1e09412023-10-23 10:03:21 +0200157LIBYANG_API_DECL LY_ERR lyht_find_next(const struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200158
159/**
Michal Vasko6374de22022-09-05 15:48:48 +0200160 * @brief Find another equal value in the hash table. Same functionality as ::lyht_find_next()
161 * but allows to specify a collision val equal callback to be used for checking for matching colliding values.
162 *
163 * @param[in] ht Hash table to search in.
164 * @param[in] val_p Pointer to the previously found value in @p ht.
165 * @param[in] hash Hash of the previously found value.
166 * @param[in] collision_val_equal Val equal callback to use for checking collisions.
167 * @param[out] match_p Pointer to the matching value, optional.
168 * @return LY_SUCCESS if value was found,
169 * @return LY_ENOTFOUND if not found.
170 */
Michal Vaskof1e09412023-10-23 10:03:21 +0200171LIBYANG_API_DECL LY_ERR lyht_find_next_with_collision_cb(const struct ly_ht *ht, void *val_p, uint32_t hash,
Michal Vasko6374de22022-09-05 15:48:48 +0200172 lyht_value_equal_cb collision_val_equal, void **match_p);
173
174/**
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200175 * @brief Insert a value into a hash table.
176 *
177 * @param[in] ht Hash table to insert into.
178 * @param[in] val_p Pointer to the value to insert. Be careful, if the values stored in the hash table
Michal Vaskoa655fca2022-09-05 15:48:31 +0200179 * are pointers, @p val_p must be a pointer to a pointer.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200180 * @param[in] hash Hash of the stored value.
181 * @param[out] match_p Pointer to the stored value, optional
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200182 * @return LY_SUCCESS on success,
Radek Krejci011e4aa2020-09-04 15:22:31 +0200183 * @return LY_EEXIST in case the value is already present.
184 * @return LY_EMEM in case of memory allocation failure.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200185 */
Michal Vaskoae130f52023-04-20 14:25:16 +0200186LIBYANG_API_DECL LY_ERR lyht_insert(struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200187
188/**
Olivier Matz6ad93d92023-09-28 12:13:36 +0200189 * @brief Insert a value into a hash table, without checking whether the value has already been inserted.
190 *
191 * @param[in] ht Hash table to insert into.
192 * @param[in] val_p Pointer to the value to insert. Be careful, if the values stored in the hash table
193 * are pointers, @p val_p must be a pointer to a pointer.
194 * @param[in] hash Hash of the stored value.
195 * @param[out] match_p Pointer to the stored value, optional
196 * @return LY_SUCCESS on success,
197 * @return LY_EMEM in case of memory allocation failure.
198 */
199LIBYANG_API_DECL LY_ERR lyht_insert_no_check(struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p);
200
201/**
Radek Krejci8678fa42020-08-18 16:07:28 +0200202 * @brief Insert a value into hash table. Same functionality as ::lyht_insert()
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200203 * but allows to specify a temporary val equal callback to be used in case the hash table
204 * will be resized after successful insertion.
205 *
206 * @param[in] ht Hash table to insert into.
207 * @param[in] val_p Pointer to the value to insert. Be careful, if the values stored in the hash table
Michal Vaskoa655fca2022-09-05 15:48:31 +0200208 * are pointers, @p val_p must be a pointer to a pointer.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200209 * @param[in] hash Hash of the stored value.
210 * @param[in] resize_val_equal Val equal callback to use for resizing.
211 * @param[out] match_p Pointer to the stored value, optional
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200212 * @return LY_SUCCESS on success,
Radek Krejci011e4aa2020-09-04 15:22:31 +0200213 * @return LY_EEXIST in case the value is already present.
214 * @return LY_EMEM in case of memory allocation failure.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200215 */
Michal Vaskoae130f52023-04-20 14:25:16 +0200216LIBYANG_API_DECL LY_ERR lyht_insert_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash,
217 lyht_value_equal_cb resize_val_equal, void **match_p);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200218
219/**
220 * @brief Remove a value from a hash table.
221 *
222 * @param[in] ht Hash table to remove from.
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200223 * @param[in] val_p Pointer to value to be removed. Be careful, if the values stored in the hash table
Michal Vaskoa655fca2022-09-05 15:48:31 +0200224 * are pointers, @p val_p must be a pointer to a pointer.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200225 * @param[in] hash Hash of the stored value.
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200226 * @return LY_SUCCESS on success,
227 * @return LY_ENOTFOUND if value was not found.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200228 */
Michal Vaskoae130f52023-04-20 14:25:16 +0200229LIBYANG_API_DECL LY_ERR lyht_remove(struct ly_ht *ht, void *val_p, uint32_t hash);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200230
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200231/**
Radek Krejci8678fa42020-08-18 16:07:28 +0200232 * @brief Remove a value from a hash table. Same functionality as ::lyht_remove()
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200233 * but allows to specify a temporary val equal callback to be used in case the hash table
234 * will be resized after successful removal.
235 *
236 * @param[in] ht Hash table to remove from.
237 * @param[in] val_p Pointer to value to be removed. Be careful, if the values stored in the hash table
Michal Vaskoa655fca2022-09-05 15:48:31 +0200238 * are pointers, @p val_p must be a pointer to a pointer.
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200239 * @param[in] hash Hash of the stored value.
240 * @param[in] resize_val_equal Val equal callback to use for resizing.
241 * @return LY_SUCCESS on success,
242 * @return LY_ENOTFOUND if value was not found.
243 */
Michal Vaskoae130f52023-04-20 14:25:16 +0200244LIBYANG_API_DECL LY_ERR lyht_remove_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash,
245 lyht_value_equal_cb resize_val_equal);
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200246
Michal Vasko626196f2022-08-05 12:49:52 +0200247/**
248 * @brief Get suitable size of a hash table for a fixed number of items.
249 *
250 * @param[in] item_count Number of stored items.
251 * @return Hash table size.
252 */
Michal Vaskoae130f52023-04-20 14:25:16 +0200253LIBYANG_API_DECL uint32_t lyht_get_fixed_size(uint32_t item_count);
254
255#ifdef __cplusplus
256}
257#endif
Michal Vasko626196f2022-08-05 12:49:52 +0200258
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200259#endif /* LY_HASH_TABLE_H_ */