blob: 2e7a511f17ab0fd935873ed6cb719aebdb43c5e0 [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 *
7 * Copyright (c) 2015 - 2018 CESNET, z.s.p.o.
8 *
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 <pthread.h>
20#include <stddef.h>
21#include <stdint.h>
22
Michal Vaskoc5a22832020-08-20 13:21:33 +020023#include "compat.h"
Radek Krejcie7b95092019-05-15 11:03:07 +020024#include "log.h"
Radek Krejci5aeea3a2018-09-05 13:29:36 +020025
26/**
27 * @brief Compute hash from (several) string(s).
28 *
29 * Usage:
30 * - init hash to 0
Radek Krejci8678fa42020-08-18 16:07:28 +020031 * - repeatedly call ::dict_hash_multi(), provide hash from the last call
32 * - call ::dict_hash_multi() with key_part = NULL to finish the hash
Radek Krejci5aeea3a2018-09-05 13:29:36 +020033 */
34uint32_t dict_hash_multi(uint32_t hash, const char *key_part, size_t len);
35
Radek Krejcif2dc4c52018-11-08 09:04:13 +010036/*
37 * @brief Compute hash from a string.
38 */
39uint32_t dict_hash(const char *key, size_t len);
40
Radek Krejci5aeea3a2018-09-05 13:29:36 +020041/**
42 * @brief Callback for checking hash table values equivalence.
43 *
Michal Vasko90932a92020-02-12 14:33:03 +010044 * @param[in] val1_p Pointer to the first value, the one being searched (inserted/removed).
45 * @param[in] val2_p Pointer to the second value, the one stored in the hash table.
Radek Krejci5aeea3a2018-09-05 13:29:36 +020046 * @param[in] mod Whether the operation modifies the hash table (insert or remove) or not (find).
47 * @param[in] cb_data User callback data.
Radek Krejci857189e2020-09-01 13:26:36 +020048 * @return false (non-equal) or true (equal).
Radek Krejci5aeea3a2018-09-05 13:29:36 +020049 */
Radek Krejci857189e2020-09-01 13:26:36 +020050typedef ly_bool (*values_equal_cb)(void *val1_p, void *val2_p, ly_bool mod, void *cb_data);
Radek Krejci5aeea3a2018-09-05 13:29:36 +020051
Radek Krejcif13b87b2020-12-01 22:02:17 +010052/** reference value for 100% */
53#define LYHT_HUNDRED_PERCENTAGE 100
54
Radek Krejci5aeea3a2018-09-05 13:29:36 +020055/** when the table is at least this much percent full, it is enlarged (double the size) */
56#define LYHT_ENLARGE_PERCENTAGE 75
57
58/** only once the table is this much percent full, enable shrinking */
59#define LYHT_FIRST_SHRINK_PERCENTAGE 50
60
61/** when the table is less than this much percent full, it is shrunk (half the size) */
62#define LYHT_SHRINK_PERCENTAGE 25
63
64/** never shrink beyond this size */
65#define LYHT_MIN_SIZE 8
66
67/**
68 * @brief Generic hash table record.
69 */
70struct ht_rec {
71 uint32_t hash; /* hash of the value */
72 int32_t hits; /* collision/overflow value count - 1 (a filled entry has 1 hit,
73 * special value -1 means a deleted record) */
74 unsigned char val[1]; /* arbitrary-size value */
75} _PACKED;
76
77/**
78 * @brief (Very) generic hash table.
79 *
80 * Hash table with open addressing collision resolution and
81 * linear probing of interval 1 (next free record is used).
82 * Removal is lazy (removed records are only marked), but
83 * if possible, they are fully emptied.
84 */
85struct hash_table {
86 uint32_t used; /* number of values stored in the hash table (filled records) */
87 uint32_t size; /* always holds 2^x == size (is power of 2), actually number of records allocated */
88 values_equal_cb val_equal; /* callback for testing value equivalence */
89 void *cb_data; /* user data callback arbitrary value */
90 uint16_t resize; /* 0 - resizing is disabled, *
91 * 1 - enlarging is enabled, *
92 * 2 - both shrinking and enlarging is enabled */
93 uint16_t rec_size; /* real size (in bytes) of one record for accessing recs array */
94 unsigned char *recs; /* pointer to the hash table itself (array of struct ht_rec) */
95};
96
97struct dict_rec {
98 char *value;
99 uint32_t refcount;
100};
101
102/**
103 * dictionary to store repeating strings
104 */
105struct dict_table {
106 struct hash_table *hash_tab;
107 pthread_mutex_t lock;
108};
109
110/**
111 * @brief Initiate content (non-zero values) of the dictionary
112 *
113 * @param[in] dict Dictionary table to initiate
114 */
115void lydict_init(struct dict_table *dict);
116
117/**
118 * @brief Cleanup the dictionary content
119 *
120 * @param[in] dict Dictionary table to cleanup
121 */
122void lydict_clean(struct dict_table *dict);
123
124/**
125 * @brief Create new hash table.
126 *
127 * @param[in] size Starting size of the hash table (capacity of values), must be power of 2.
128 * @param[in] val_size Size in bytes of value (the stored hashed item).
129 * @param[in] val_equal Callback for checking value equivalence.
130 * @param[in] cb_data User data always passed to \p val_equal.
131 * @param[in] resize Whether to resize the table on too few/too many records taken.
132 * @return Empty hash table, NULL on error.
133 */
Radek Krejci1deb5be2020-08-26 16:43:36 +0200134struct hash_table *lyht_new(uint32_t size, uint16_t val_size, values_equal_cb val_equal, void *cb_data, uint16_t resize);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200135
136/**
137 * @brief Set hash table value equal callback.
138 *
139 * @param[in] ht Hash table to modify.
140 * @param[in] new_val_equal New callback for checking value equivalence.
141 * @return Previous callback for checking value equivalence.
142 */
143values_equal_cb lyht_set_cb(struct hash_table *ht, values_equal_cb new_val_equal);
144
145/**
146 * @brief Set hash table value equal callback user data.
147 *
148 * @param[in] ht Hash table to modify.
149 * @param[in] new_cb_data New data for values callback.
150 * @return Previous data for values callback.
151 */
152void *lyht_set_cb_data(struct hash_table *ht, void *new_cb_data);
153
154/**
155 * @brief Make a duplicate of an existing hash table.
156 *
157 * @param[in] orig Original hash table to duplicate.
158 * @return Duplicated hash table \p orig, NULL on error.
159 */
160struct hash_table *lyht_dup(const struct hash_table *orig);
161
162/**
163 * @brief Free a hash table.
164 *
165 * @param[in] ht Hash table to be freed.
166 */
167void lyht_free(struct hash_table *ht);
168
169/**
170 * @brief Find a value in a hash table.
171 *
172 * @param[in] ht Hash table to search in.
173 * @param[in] val_p Pointer to the value to find.
174 * @param[in] hash Hash of the stored value.
175 * @param[out] match_p Pointer to the matching value, optional.
Michal Vaskoda859032020-07-14 12:20:14 +0200176 * @return LY_SUCCESS if value was found,
177 * @return LY_ENOTFOUND if not found.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200178 */
Michal Vaskoda859032020-07-14 12:20:14 +0200179LY_ERR lyht_find(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200180
181/**
182 * @brief Find another equal value in the hash table.
183 *
184 * @param[in] ht Hash table to search in.
185 * @param[in] val_p Pointer to the previously found value in \p ht.
186 * @param[in] hash Hash of the previously found value.
187 * @param[out] match_p Pointer to the matching value, optional.
Michal Vaskoda859032020-07-14 12:20:14 +0200188 * @return LY_SUCCESS if value was found,
189 * @return LY_ENOTFOUND if not found.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200190 */
Michal Vaskoda859032020-07-14 12:20:14 +0200191LY_ERR lyht_find_next(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200192
193/**
194 * @brief Insert a value into a hash table.
195 *
196 * @param[in] ht Hash table to insert into.
197 * @param[in] val_p Pointer to the value to insert. Be careful, if the values stored in the hash table
198 * are pointers, \p val_p must be a pointer to a pointer.
199 * @param[in] hash Hash of the stored value.
200 * @param[out] match_p Pointer to the stored value, optional
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200201 * @return LY_SUCCESS on success,
Radek Krejci011e4aa2020-09-04 15:22:31 +0200202 * @return LY_EEXIST in case the value is already present.
203 * @return LY_EMEM in case of memory allocation failure.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200204 */
Radek Krejci0ae092d2018-09-20 16:43:19 +0200205LY_ERR lyht_insert(struct hash_table *ht, void *val_p, uint32_t hash, void **match_p);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200206
207/**
Radek Krejci8678fa42020-08-18 16:07:28 +0200208 * @brief Insert a value into hash table. Same functionality as ::lyht_insert()
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200209 * but allows to specify a temporary val equal callback to be used in case the hash table
210 * will be resized after successful insertion.
211 *
212 * @param[in] ht Hash table to insert into.
213 * @param[in] val_p Pointer to the value to insert. Be careful, if the values stored in the hash table
214 * are pointers, \p val_p must be a pointer to a pointer.
215 * @param[in] hash Hash of the stored value.
216 * @param[in] resize_val_equal Val equal callback to use for resizing.
217 * @param[out] match_p Pointer to the stored value, optional
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200218 * @return LY_SUCCESS on success,
Radek Krejci011e4aa2020-09-04 15:22:31 +0200219 * @return LY_EEXIST in case the value is already present.
220 * @return LY_EMEM in case of memory allocation failure.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200221 */
222LY_ERR lyht_insert_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash, values_equal_cb resize_val_equal,
Radek Krejci0f969882020-08-21 16:56:47 +0200223 void **match_p);
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200224
225/**
226 * @brief Remove a value from a hash table.
227 *
228 * @param[in] ht Hash table to remove from.
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200229 * @param[in] val_p Pointer to value to be removed. Be careful, if the values stored in the hash table
230 * are pointers, \p val_p must be a pointer to a pointer.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200231 * @param[in] hash Hash of the stored value.
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200232 * @return LY_SUCCESS on success,
233 * @return LY_ENOTFOUND if value was not found.
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200234 */
235LY_ERR lyht_remove(struct hash_table *ht, void *val_p, uint32_t hash);
236
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200237/**
Radek Krejci8678fa42020-08-18 16:07:28 +0200238 * @brief Remove a value from a hash table. Same functionality as ::lyht_remove()
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200239 * but allows to specify a temporary val equal callback to be used in case the hash table
240 * will be resized after successful removal.
241 *
242 * @param[in] ht Hash table to remove from.
243 * @param[in] val_p Pointer to value to be removed. Be careful, if the values stored in the hash table
244 * are pointers, \p val_p must be a pointer to a pointer.
245 * @param[in] hash Hash of the stored value.
246 * @param[in] resize_val_equal Val equal callback to use for resizing.
247 * @return LY_SUCCESS on success,
248 * @return LY_ENOTFOUND if value was not found.
249 */
250LY_ERR lyht_remove_with_resize_cb(struct hash_table *ht, void *val_p, uint32_t hash, values_equal_cb resize_val_equal);
251
Radek Krejci5aeea3a2018-09-05 13:29:36 +0200252#endif /* LY_HASH_TABLE_H_ */