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