1 /* Hash routine. 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 */ 20 21 #ifndef _ZEBRA_HASH_H 22 #define _ZEBRA_HASH_H 23 24 #include "memory.h" 25 #include "frratomic.h" 26 27 #ifdef __cplusplus 28 extern "C" { 29 #endif 30 31 /* Default hash table size. */ 32 #define HASH_INITIAL_SIZE 256 33 /* Expansion threshold */ 34 #define HASH_THRESHOLD(used, size) ((used) > (size)) 35 36 #define HASHWALK_CONTINUE 0 37 #define HASHWALK_ABORT -1 38 39 struct hash_bucket { 40 /* 41 * if this bucket is the head of the linked listed, len denotes the 42 * number of elements in the list 43 */ 44 int len; 45 46 /* Linked list. */ 47 struct hash_bucket *next; 48 49 /* Hash key. */ 50 unsigned int key; 51 52 /* Data. */ 53 void *data; 54 }; 55 56 struct hashstats { 57 /* number of empty hash buckets */ 58 atomic_uint_fast32_t empty; 59 /* sum of squares of bucket length */ 60 atomic_uint_fast32_t ssq; 61 }; 62 63 struct hash { 64 /* Hash bucket. */ 65 struct hash_bucket **index; 66 67 /* Hash table size. Must be power of 2 */ 68 unsigned int size; 69 70 /* If max_size is 0 there is no limit */ 71 unsigned int max_size; 72 73 /* Key make function. */ 74 unsigned int (*hash_key)(const void *); 75 76 /* Data compare function. */ 77 bool (*hash_cmp)(const void *, const void *); 78 79 /* Backet alloc. */ 80 unsigned long count; 81 82 struct hashstats stats; 83 84 /* hash name */ 85 char *name; 86 }; 87 88 #define hashcount(X) ((X)->count) 89 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 106 * data items, should return nonzero if the two items are equal and 0 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 */ 118 extern struct hash *hash_create(unsigned int (*hash_key)(const void *), 119 bool (*hash_cmp)(const void *, const void *), 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 140 * data items, should return nonzero if the two items are equal and 0 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 */ 152 extern struct hash * 153 hash_create_size(unsigned int size, unsigned int (*hash_key)(const void *), 154 bool (*hash_cmp)(const void *, const void *), 155 const char *name); 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 164 * described and provide alloc_func as descrbied below to allocate the full 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 172 * data to insert or retrieve - A hash bucket will not be created if 173 * the alloc_func returns a NULL pointer and nothing will be added to 174 * the hash. As such bucket->data will always be non-NULL. 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 */ 189 extern 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 */ 203 extern 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 */ 219 extern void *hash_lookup(struct hash *hash, void *data); 220 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 */ 233 extern void *hash_release(struct hash *hash, void *data); 234 235 /* 236 * Iterate over the elements in a hash table. 237 * 238 * It is safe to delete items passed to the iteration function from the hash 239 * table during iteration. Please note that adding entries to the hash 240 * during the walk will cause undefined behavior in that some new entries 241 * will be walked and some will not. So do not do this. 242 * 243 * The bucket passed to func will have a non-NULL data pointer. 244 * 245 * hash 246 * hash table to operate on 247 * 248 * func 249 * function to call with each data item 250 * 251 * arg 252 * arbitrary argument passed as the second parameter in each call to 'func' 253 */ 254 extern void hash_iterate(struct hash *hash, 255 void (*func)(struct hash_bucket *, void *), void *arg); 256 257 /* 258 * Iterate over the elements in a hash table, stopping on condition. 259 * 260 * It is safe to delete items passed to the iteration function from the hash 261 * table during iteration. Please note that adding entries to the hash 262 * during the walk will cause undefined behavior in that some new entries 263 * will be walked and some will not. So do not do this. 264 * 265 * The bucket passed to func will have a non-NULL data pointer. 266 * 267 * hash 268 * hash table to operate on 269 * 270 * func 271 * function to call with each data item. If this function returns 272 * HASHWALK_ABORT then the iteration stops. 273 * 274 * arg 275 * arbitrary argument passed as the second parameter in each call to 'func' 276 */ 277 extern void hash_walk(struct hash *hash, 278 int (*func)(struct hash_bucket *, void *), void *arg); 279 280 /* 281 * Remove all elements from a hash table. 282 * 283 * hash 284 * hash table to operate on 285 * 286 * free_func 287 * function to call with each removed item; intended to free the data 288 */ 289 extern void hash_clean(struct hash *hash, void (*free_func)(void *)); 290 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); 301 302 /* 303 * Converts a hash table to an unsorted linked list. 304 * Does not modify the hash table in any way. 305 * 306 * hash 307 * hash table to convert 308 */ 309 extern struct list *hash_to_list(struct hash *hash); 310 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 */ 322 extern unsigned int string_hash_make(const char *); 323 324 /* 325 * Install CLI commands for viewing global hash table statistics. 326 */ 327 extern void hash_cmd_init(void); 328 329 #ifdef __cplusplus 330 } 331 #endif 332 333 #endif /* _ZEBRA_HASH_H */ 334