]> git.proxmox.com Git - mirror_frr.git/blob - lib/hash.h
lib: Remove tests for ipv[4|6]_prefix_table
[mirror_frr.git] / lib / hash.h
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /* Hash routine.
3 * Copyright (C) 1998 Kunihiro Ishiguro
4 */
5
6 #ifndef _ZEBRA_HASH_H
7 #define _ZEBRA_HASH_H
8
9 #include "memory.h"
10 #include "frratomic.h"
11
12 #ifdef __cplusplus
13 extern "C" {
14 #endif
15
16 /* Default hash table size. */
17 #define HASH_INITIAL_SIZE 256
18 /* Expansion threshold */
19 #define HASH_THRESHOLD(used, size) ((used) > (size))
20
21 #define HASHWALK_CONTINUE 0
22 #define HASHWALK_ABORT -1
23
24 struct hash_bucket {
25 /*
26 * if this bucket is the head of the linked listed, len denotes the
27 * number of elements in the list
28 */
29 int len;
30
31 /* Linked list. */
32 struct hash_bucket *next;
33
34 /* Hash key. */
35 unsigned int key;
36
37 /* Data. */
38 void *data;
39 };
40
41 struct hashstats {
42 /* number of empty hash buckets */
43 atomic_uint_fast32_t empty;
44 /* sum of squares of bucket length */
45 atomic_uint_fast32_t ssq;
46 };
47
48 struct hash {
49 /* Hash bucket. */
50 struct hash_bucket **index;
51
52 /* Hash table size. Must be power of 2 */
53 unsigned int size;
54
55 /* If max_size is 0 there is no limit */
56 unsigned int max_size;
57
58 /* Key make function. */
59 unsigned int (*hash_key)(const void *);
60
61 /* Data compare function. */
62 bool (*hash_cmp)(const void *, const void *);
63
64 /* Bucket alloc. */
65 unsigned long count;
66
67 struct hashstats stats;
68
69 /* hash name */
70 char *name;
71 };
72
73 #define hashcount(X) ((X)->count)
74
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
91 * data items, should return true if the two items are equal and false
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 */
103 extern struct hash *hash_create(unsigned int (*hash_key)(const void *),
104 bool (*hash_cmp)(const void *, const void *),
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
125 * data items, should return true if the two items are equal and false
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 *
138 hash_create_size(unsigned int size, unsigned int (*hash_key)(const void *),
139 bool (*hash_cmp)(const void *, const void *),
140 const char *name);
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
149 * described and provide alloc_func as described below to allocate the full
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
157 * data to insert or retrieve - A hash bucket will not be created if
158 * the alloc_func returns a NULL pointer and nothing will be added to
159 * the hash. As such bucket->data will always be non-NULL.
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);
205
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);
219
220 /*
221 * Iterate over the elements in a hash table.
222 *
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
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.
229 *
230 * The bucket passed to func will have a non-NULL data pointer.
231 *
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,
242 void (*func)(struct hash_bucket *, void *), void *arg);
243
244 /*
245 * Iterate over the elements in a hash table, stopping on condition.
246 *
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
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.
253 *
254 * The bucket passed to func will have a non-NULL data pointer.
255 *
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,
267 int (*func)(struct hash_bucket *, void *), void *arg);
268
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
280 /*
281 * Delete a hash table.
282 *
283 * This function assumes the table is empty. Call hash_clean to delete the
284 * hashtable contents if necessary.
285 *
286 * hash
287 * hash table to delete
288 */
289 extern void hash_free(struct hash *hash);
290
291 /*
292 * Converts a hash table to an unsorted linked list.
293 * Does not modify the hash table in any way.
294 *
295 * hash
296 * hash table to convert
297 */
298 extern struct list *hash_to_list(struct hash *hash);
299
300 /*
301 * Hash a string using the modified Bernstein hash.
302 *
303 * This is not a perfect hash function.
304 *
305 * str
306 * string to hash
307 *
308 * Returns:
309 * modified Bernstein hash of the string
310 */
311 extern unsigned int string_hash_make(const char *);
312
313 /*
314 * Install CLI commands for viewing global hash table statistics.
315 */
316 extern void hash_cmd_init(void);
317
318 #ifdef __cplusplus
319 }
320 #endif
321
322 #endif /* _ZEBRA_HASH_H */