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 */