]>
Commit | Line | Data |
---|---|---|
acddc0ed | 1 | // SPDX-License-Identifier: GPL-2.0-or-later |
718e3744 | 2 | /* Hash routine. |
896014f4 | 3 | * Copyright (C) 1998 Kunihiro Ishiguro |
896014f4 | 4 | */ |
718e3744 | 5 | |
6 | #ifndef _ZEBRA_HASH_H | |
7 | #define _ZEBRA_HASH_H | |
8 | ||
4a1ab8e4 | 9 | #include "memory.h" |
6f6f0010 | 10 | #include "frratomic.h" |
4a1ab8e4 | 11 | |
5e244469 RW |
12 | #ifdef __cplusplus |
13 | extern "C" { | |
14 | #endif | |
15 | ||
d62a17ae | 16 | /* Default hash table size. */ |
bed7ad83 QY |
17 | #define HASH_INITIAL_SIZE 256 |
18 | /* Expansion threshold */ | |
19 | #define HASH_THRESHOLD(used, size) ((used) > (size)) | |
718e3744 | 20 | |
3f9c7369 DS |
21 | #define HASHWALK_CONTINUE 0 |
22 | #define HASHWALK_ABORT -1 | |
23 | ||
e3b78da8 | 24 | struct hash_bucket { |
6fd8c487 | 25 | /* |
e3b78da8 | 26 | * if this bucket is the head of the linked listed, len denotes the |
6fd8c487 QY |
27 | * number of elements in the list |
28 | */ | |
d62a17ae | 29 | int len; |
6f6f0010 | 30 | |
d62a17ae | 31 | /* Linked list. */ |
e3b78da8 | 32 | struct hash_bucket *next; |
718e3744 | 33 | |
d62a17ae | 34 | /* Hash key. */ |
35 | unsigned int key; | |
718e3744 | 36 | |
d62a17ae | 37 | /* Data. */ |
38 | void *data; | |
718e3744 | 39 | }; |
40 | ||
d62a17ae | 41 | struct hashstats { |
42 | /* number of empty hash buckets */ | |
c8a65463 | 43 | atomic_uint_fast32_t empty; |
d62a17ae | 44 | /* sum of squares of bucket length */ |
c8a65463 | 45 | atomic_uint_fast32_t ssq; |
6f6f0010 QY |
46 | }; |
47 | ||
d62a17ae | 48 | struct hash { |
e3b78da8 TB |
49 | /* Hash bucket. */ |
50 | struct hash_bucket **index; | |
718e3744 | 51 | |
d62a17ae | 52 | /* Hash table size. Must be power of 2 */ |
53 | unsigned int size; | |
718e3744 | 54 | |
40520c36 DW |
55 | /* If max_size is 0 there is no limit */ |
56 | unsigned int max_size; | |
57 | ||
d62a17ae | 58 | /* Key make function. */ |
d8b87afe | 59 | unsigned int (*hash_key)(const void *); |
718e3744 | 60 | |
d62a17ae | 61 | /* Data compare function. */ |
74df8d6d | 62 | bool (*hash_cmp)(const void *, const void *); |
718e3744 | 63 | |
1ac88792 | 64 | /* Bucket alloc. */ |
d62a17ae | 65 | unsigned long count; |
4db0cff1 | 66 | |
d62a17ae | 67 | struct hashstats stats; |
6f6f0010 | 68 | |
d62a17ae | 69 | /* hash name */ |
70 | char *name; | |
718e3744 | 71 | }; |
72 | ||
8234a987 | 73 | #define hashcount(X) ((X)->count) |
74 | ||
6fd8c487 QY |
75 | /* |
76 | * Create a hash table. | |
77 | * | |
78 | * The created hash table uses chaining and a user-provided comparator function | |
79 | * to resolve collisions. For best performance use a perfect hash function. | |
80 | * Worst case lookup time is O(N) when using a constant hash function. Best | |
81 | * case lookup time is O(1) when using a perfect hash function. | |
82 | * | |
83 | * The initial size of the created hash table is HASH_INITIAL_SIZE. | |
84 | * | |
85 | * hash_key | |
86 | * hash function to use; should return a unique unsigned integer when called | |
87 | * with a data item. Collisions are acceptable. | |
88 | * | |
89 | * hash_cmp | |
90 | * comparison function used for resolving collisions; when called with two | |
c8aad9c3 | 91 | * data items, should return true if the two items are equal and false |
6fd8c487 QY |
92 | * otherwise |
93 | * | |
94 | * name | |
95 | * optional name for the hashtable; this is used when displaying global | |
96 | * hashtable statistics. If this parameter is NULL the hash's name will be | |
97 | * set to NULL and the default name will be displayed when showing | |
98 | * statistics. | |
99 | * | |
100 | * Returns: | |
101 | * a new hash table | |
102 | */ | |
d8b87afe | 103 | extern struct hash *hash_create(unsigned int (*hash_key)(const void *), |
74df8d6d | 104 | bool (*hash_cmp)(const void *, const void *), |
6fd8c487 QY |
105 | const char *name); |
106 | ||
107 | /* | |
108 | * Create a hash table. | |
109 | * | |
110 | * The created hash table uses chaining and a user-provided comparator function | |
111 | * to resolve collisions. For best performance use a perfect hash function. | |
112 | * Worst case lookup time is O(N) when using a constant hash function. Best | |
113 | * case lookup time is O(1) when using a perfect hash function. | |
114 | * | |
115 | * size | |
116 | * initial number of hash buckets to allocate; must be a power of 2 or the | |
117 | * program will assert | |
118 | * | |
119 | * hash_key | |
120 | * hash function to use; should return a unique unsigned integer when called | |
121 | * with a data item. Collisions are acceptable. | |
122 | * | |
123 | * hash_cmp | |
124 | * comparison function used for resolving collisions; when called with two | |
be268ed6 | 125 | * data items, should return true if the two items are equal and false |
6fd8c487 QY |
126 | * otherwise |
127 | * | |
128 | * name | |
129 | * optional name for the hashtable; this is used when displaying global | |
130 | * hashtable statistics. If this parameter is NULL the hash's name will be | |
131 | * set to NULL and the default name will be displayed when showing | |
132 | * statistics. | |
133 | * | |
134 | * Returns: | |
135 | * a new hash table | |
136 | */ | |
137 | extern struct hash * | |
d8b87afe | 138 | hash_create_size(unsigned int size, unsigned int (*hash_key)(const void *), |
74df8d6d DS |
139 | bool (*hash_cmp)(const void *, const void *), |
140 | const char *name); | |
6fd8c487 QY |
141 | |
142 | /* | |
143 | * Retrieve or insert data from / into a hash table. | |
144 | * | |
145 | * This function is somewhat counterintuitive in its usage. In order to look up | |
146 | * an element from its key, you must provide the data item itself, with the | |
147 | * portions used in the hash function set to the same values as the data item | |
148 | * to retrieve. To insert a data element, either provide the key as just | |
214d8a60 | 149 | * described and provide alloc_func as described below to allocate the full |
6fd8c487 QY |
150 | * data element, or provide the full data element and pass 'hash_alloc_intern' |
151 | * to alloc_func. | |
152 | * | |
153 | * hash | |
154 | * hash table to operate on | |
155 | * | |
156 | * data | |
e3b78da8 | 157 | * data to insert or retrieve - A hash bucket will not be created if |
d3ce24ef | 158 | * the alloc_func returns a NULL pointer and nothing will be added to |
e3b78da8 | 159 | * the hash. As such bucket->data will always be non-NULL. |
6fd8c487 QY |
160 | * |
161 | * alloc_func | |
162 | * function to call if the item is not found in the hash table. This | |
163 | * function is called with the value of 'data' and should create the data | |
164 | * item to insert and return a pointer to it. If the data has already been | |
165 | * completely created and provided in the 'data' parameter, passing | |
166 | * 'hash_alloc_intern' to this parameter will cause 'data' to be inserted. | |
167 | * If this parameter is NULL, then this call to hash_get is equivalent to | |
168 | * hash_lookup. | |
169 | * | |
170 | * Returns: | |
171 | * the data item found or inserted, or NULL if alloc_func is NULL and the | |
172 | * data is not found | |
173 | */ | |
174 | extern void *hash_get(struct hash *hash, void *data, | |
175 | void *(*alloc_func)(void *)); | |
176 | ||
177 | /* | |
178 | * Dummy element allocation function. | |
179 | * | |
180 | * See hash_get for details. | |
181 | * | |
182 | * data | |
183 | * data to insert into the hash table | |
184 | * | |
185 | * Returns: | |
186 | * data | |
187 | */ | |
188 | extern void *hash_alloc_intern(void *data); | |
189 | ||
190 | /* | |
191 | * Retrieve an item from a hash table. | |
192 | * | |
193 | * This function is equivalent to calling hash_get with alloc_func set to NULL. | |
194 | * | |
195 | * hash | |
196 | * hash table to operate on | |
197 | * | |
198 | * data | |
199 | * data element with values used for key computation set | |
200 | * | |
201 | * Returns: | |
202 | * the data element if found, or NULL if not found | |
203 | */ | |
204 | extern void *hash_lookup(struct hash *hash, void *data); | |
718e3744 | 205 | |
6fd8c487 QY |
206 | /* |
207 | * Remove an element from a hash table. | |
208 | * | |
209 | * hash | |
210 | * hash table to operate on | |
211 | * | |
212 | * data | |
213 | * data element to remove with values used for key computation set | |
214 | * | |
215 | * Returns: | |
216 | * the removed element if found, or NULL if not found | |
217 | */ | |
218 | extern void *hash_release(struct hash *hash, void *data); | |
718e3744 | 219 | |
6fd8c487 QY |
220 | /* |
221 | * Iterate over the elements in a hash table. | |
222 | * | |
341743ac DS |
223 | * The passed in arg to the handler function is the only safe |
224 | * item to delete from the hash. | |
225 | * | |
226 | * Please note that adding entries to the hash | |
8b52179d DS |
227 | * during the walk will cause undefined behavior in that some new entries |
228 | * will be walked and some will not. So do not do this. | |
6fd8c487 | 229 | * |
e3b78da8 | 230 | * The bucket passed to func will have a non-NULL data pointer. |
d3ce24ef | 231 | * |
6fd8c487 QY |
232 | * hash |
233 | * hash table to operate on | |
234 | * | |
235 | * func | |
236 | * function to call with each data item | |
237 | * | |
238 | * arg | |
239 | * arbitrary argument passed as the second parameter in each call to 'func' | |
240 | */ | |
241 | extern void hash_iterate(struct hash *hash, | |
e3b78da8 | 242 | void (*func)(struct hash_bucket *, void *), void *arg); |
718e3744 | 243 | |
6fd8c487 QY |
244 | /* |
245 | * Iterate over the elements in a hash table, stopping on condition. | |
246 | * | |
341743ac DS |
247 | * The passed in arg to the handler function is the only safe item |
248 | * to delete from the hash. | |
249 | * | |
250 | * Please note that adding entries to the hash | |
8b52179d DS |
251 | * during the walk will cause undefined behavior in that some new entries |
252 | * will be walked and some will not. So do not do this. | |
6fd8c487 | 253 | * |
e3b78da8 | 254 | * The bucket passed to func will have a non-NULL data pointer. |
d3ce24ef | 255 | * |
6fd8c487 QY |
256 | * hash |
257 | * hash table to operate on | |
258 | * | |
259 | * func | |
260 | * function to call with each data item. If this function returns | |
261 | * HASHWALK_ABORT then the iteration stops. | |
262 | * | |
263 | * arg | |
264 | * arbitrary argument passed as the second parameter in each call to 'func' | |
265 | */ | |
266 | extern void hash_walk(struct hash *hash, | |
e3b78da8 | 267 | int (*func)(struct hash_bucket *, void *), void *arg); |
3f9c7369 | 268 | |
6fd8c487 QY |
269 | /* |
270 | * Remove all elements from a hash table. | |
271 | * | |
272 | * hash | |
273 | * hash table to operate on | |
274 | * | |
275 | * free_func | |
276 | * function to call with each removed item; intended to free the data | |
277 | */ | |
278 | extern void hash_clean(struct hash *hash, void (*free_func)(void *)); | |
279 | ||
d8bc11a5 DS |
280 | /* |
281 | * Remove all elements from a hash table and free the table, | |
282 | * setting the pointer to NULL. | |
283 | * | |
284 | * hash | |
285 | * hash table to operate on | |
286 | * free_func | |
287 | * function to call with each removed item, intended to free the data | |
288 | */ | |
289 | extern void hash_clean_and_free(struct hash **hash, void (*free_func)(void *)); | |
290 | ||
6fd8c487 QY |
291 | /* |
292 | * Delete a hash table. | |
293 | * | |
294 | * This function assumes the table is empty. Call hash_clean to delete the | |
295 | * hashtable contents if necessary. | |
296 | * | |
297 | * hash | |
298 | * hash table to delete | |
299 | */ | |
300 | extern void hash_free(struct hash *hash); | |
718e3744 | 301 | |
91f10370 QY |
302 | /* |
303 | * Converts a hash table to an unsorted linked list. | |
304 | * Does not modify the hash table in any way. | |
305 | * | |
306 | * hash | |
6fd8c487 | 307 | * hash table to convert |
91f10370 QY |
308 | */ |
309 | extern struct list *hash_to_list(struct hash *hash); | |
310 | ||
6fd8c487 QY |
311 | /* |
312 | * Hash a string using the modified Bernstein hash. | |
313 | * | |
314 | * This is not a perfect hash function. | |
315 | * | |
316 | * str | |
317 | * string to hash | |
318 | * | |
319 | * Returns: | |
320 | * modified Bernstein hash of the string | |
321 | */ | |
d62a17ae | 322 | extern unsigned int string_hash_make(const char *); |
6392aa83 | 323 | |
6fd8c487 QY |
324 | /* |
325 | * Install CLI commands for viewing global hash table statistics. | |
326 | */ | |
d62a17ae | 327 | extern void hash_cmd_init(void); |
4db0cff1 | 328 | |
5e244469 RW |
329 | #ifdef __cplusplus |
330 | } | |
331 | #endif | |
332 | ||
718e3744 | 333 | #endif /* _ZEBRA_HASH_H */ |