]>
git.proxmox.com Git - mirror_frr.git/blob - lib/hash.h
2 * Copyright (C) 1998 Kunihiro Ishiguro
4 * This file is part of GNU Zebra.
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.
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.
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
25 #include "frratomic.h"
28 DECLARE_MTYPE(HASH_BACKET
)
30 /* Default hash table size. */
31 #define HASH_INITIAL_SIZE 256
32 /* Expansion threshold */
33 #define HASH_THRESHOLD(used, size) ((used) > (size))
35 #define HASHWALK_CONTINUE 0
36 #define HASHWALK_ABORT -1
40 * if this backet is the head of the linked listed, len denotes the
41 * number of elements in the list
46 struct hash_backet
*next
;
56 /* number of empty hash buckets */
57 _Atomic
uint_fast32_t empty
;
58 /* sum of squares of bucket length */
59 _Atomic
uint_fast32_t ssq
;
64 struct hash_backet
**index
;
66 /* Hash table size. Must be power of 2 */
69 /* If max_size is 0 there is no limit */
70 unsigned int max_size
;
72 /* Key make function. */
73 unsigned int (*hash_key
)(void *);
75 /* Data compare function. */
76 bool (*hash_cmp
)(const void *, const void *);
81 struct hashstats stats
;
87 #define hashcount(X) ((X)->count)
90 * Create a hash table.
92 * The created hash table uses chaining and a user-provided comparator function
93 * to resolve collisions. For best performance use a perfect hash function.
94 * Worst case lookup time is O(N) when using a constant hash function. Best
95 * case lookup time is O(1) when using a perfect hash function.
97 * The initial size of the created hash table is HASH_INITIAL_SIZE.
100 * hash function to use; should return a unique unsigned integer when called
101 * with a data item. Collisions are acceptable.
104 * comparison function used for resolving collisions; when called with two
105 * data items, should return nonzero if the two items are equal and 0
109 * optional name for the hashtable; this is used when displaying global
110 * hashtable statistics. If this parameter is NULL the hash's name will be
111 * set to NULL and the default name will be displayed when showing
117 extern struct hash
*hash_create(unsigned int (*hash_key
)(void *),
118 bool (*hash_cmp
)(const void *, const void *),
122 * Create a hash table.
124 * The created hash table uses chaining and a user-provided comparator function
125 * to resolve collisions. For best performance use a perfect hash function.
126 * Worst case lookup time is O(N) when using a constant hash function. Best
127 * case lookup time is O(1) when using a perfect hash function.
130 * initial number of hash buckets to allocate; must be a power of 2 or the
131 * program will assert
134 * hash function to use; should return a unique unsigned integer when called
135 * with a data item. Collisions are acceptable.
138 * comparison function used for resolving collisions; when called with two
139 * data items, should return nonzero if the two items are equal and 0
143 * optional name for the hashtable; this is used when displaying global
144 * hashtable statistics. If this parameter is NULL the hash's name will be
145 * set to NULL and the default name will be displayed when showing
152 hash_create_size(unsigned int size
, unsigned int (*hash_key
)(void *),
153 bool (*hash_cmp
)(const void *, const void *),
157 * Retrieve or insert data from / into a hash table.
159 * This function is somewhat counterintuitive in its usage. In order to look up
160 * an element from its key, you must provide the data item itself, with the
161 * portions used in the hash function set to the same values as the data item
162 * to retrieve. To insert a data element, either provide the key as just
163 * described and provide alloc_func as descrbied below to allocate the full
164 * data element, or provide the full data element and pass 'hash_alloc_intern'
168 * hash table to operate on
171 * data to insert or retrieve - A hash backet will not be created if
172 * the alloc_func returns a NULL pointer and nothing will be added to
173 * the hash. As such backet->data will always be non-NULL.
176 * function to call if the item is not found in the hash table. This
177 * function is called with the value of 'data' and should create the data
178 * item to insert and return a pointer to it. If the data has already been
179 * completely created and provided in the 'data' parameter, passing
180 * 'hash_alloc_intern' to this parameter will cause 'data' to be inserted.
181 * If this parameter is NULL, then this call to hash_get is equivalent to
185 * the data item found or inserted, or NULL if alloc_func is NULL and the
188 extern void *hash_get(struct hash
*hash
, void *data
,
189 void *(*alloc_func
)(void *));
192 * Dummy element allocation function.
194 * See hash_get for details.
197 * data to insert into the hash table
202 extern void *hash_alloc_intern(void *data
);
205 * Retrieve an item from a hash table.
207 * This function is equivalent to calling hash_get with alloc_func set to NULL.
210 * hash table to operate on
213 * data element with values used for key computation set
216 * the data element if found, or NULL if not found
218 extern void *hash_lookup(struct hash
*hash
, void *data
);
221 * Remove an element from a hash table.
224 * hash table to operate on
227 * data element to remove with values used for key computation set
230 * the removed element if found, or NULL if not found
232 extern void *hash_release(struct hash
*hash
, void *data
);
235 * Iterate over the elements in a hash table.
237 * It is safe to delete items passed to the iteration function from the hash
238 * table during iteration. Please note that adding entries to the hash
239 * during the walk will cause undefined behavior in that some new entries
240 * will be walked and some will not. So do not do this.
242 * The backet passed to func will have a non-NULL data pointer.
245 * hash table to operate on
248 * function to call with each data item
251 * arbitrary argument passed as the second parameter in each call to 'func'
253 extern void hash_iterate(struct hash
*hash
,
254 void (*func
)(struct hash_backet
*, void *), void *arg
);
257 * Iterate over the elements in a hash table, stopping on condition.
259 * It is safe to delete items passed to the iteration function from the hash
260 * table during iteration. Please note that adding entries to the hash
261 * during the walk will cause undefined behavior in that some new entries
262 * will be walked and some will not. So do not do this.
264 * The backet passed to func will have a non-NULL data pointer.
267 * hash table to operate on
270 * function to call with each data item. If this function returns
271 * HASHWALK_ABORT then the iteration stops.
274 * arbitrary argument passed as the second parameter in each call to 'func'
276 extern void hash_walk(struct hash
*hash
,
277 int (*func
)(struct hash_backet
*, void *), void *arg
);
280 * Remove all elements from a hash table.
283 * hash table to operate on
286 * function to call with each removed item; intended to free the data
288 extern void hash_clean(struct hash
*hash
, void (*free_func
)(void *));
291 * Delete a hash table.
293 * This function assumes the table is empty. Call hash_clean to delete the
294 * hashtable contents if necessary.
297 * hash table to delete
299 extern void hash_free(struct hash
*hash
);
302 * Converts a hash table to an unsorted linked list.
303 * Does not modify the hash table in any way.
306 * hash table to convert
308 extern struct list
*hash_to_list(struct hash
*hash
);
311 * Hash a string using the modified Bernstein hash.
313 * This is not a perfect hash function.
319 * modified Bernstein hash of the string
321 extern unsigned int string_hash_make(const char *);
324 * Install CLI commands for viewing global hash table statistics.
326 extern void hash_cmd_init(void);
328 #endif /* _ZEBRA_HASH_H */