lib/hash.h

   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         /* Bucket 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 true if the two items are equal and false
 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 true if the two items are equal and false
 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 described 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  * 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
 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.
 244  *
 245  * The bucket passed to func will have a non-NULL data pointer.
 246  *
 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  */
 256 extern void hash_iterate(struct hash *hash,
 257                          void (*func)(struct hash_bucket *, void *), void *arg);
 258
 259 /*
 260  * Iterate over the elements in a hash table, stopping on condition.
 261  *
 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
 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.
 268  *
 269  * The bucket passed to func will have a non-NULL data pointer.
 270  *
 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  */
 281 extern void hash_walk(struct hash *hash,
 282                       int (*func)(struct hash_bucket *, void *), void *arg);
 283
 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  */
 293 extern 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  */
 304 extern void hash_free(struct hash *hash);
 305
 306 /*
 307  * Converts a hash table to an unsorted linked list.
 308  * Does not modify the hash table in any way.
 309  *
 310  * hash
 311  *    hash table to convert
 312  */
 313 extern struct list *hash_to_list(struct hash *hash);
 314
 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  */
 326 extern unsigned int string_hash_make(const char *);
 327
 328 /*
 329  * Install CLI commands for viewing global hash table statistics.
 330  */
 331 extern void hash_cmd_init(void);
 332
 333 #ifdef __cplusplus
 334 }
 335 #endif
 336
 337 #endif /* _ZEBRA_HASH_H */