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 DECLARE_MTYPE(HASH)
  32 DECLARE_MTYPE(HASH_BACKET)
  33
  34 /* Default hash table size.  */
  35 #define HASH_INITIAL_SIZE 256
  36 /* Expansion threshold */
  37 #define HASH_THRESHOLD(used, size) ((used) > (size))
  38
  39 #define HASHWALK_CONTINUE 0
  40 #define HASHWALK_ABORT -1
  41
  42 #if CONFDATE > 20200225
  43 CPP_NOTICE("hash.h: time to remove hash_backet #define")
  44 #endif
  45 #define hash_backet hash_bucket
  46
  47 struct hash_bucket {
  48         /*
  49          * if this bucket is the head of the linked listed, len denotes the
  50          * number of elements in the list
  51          */
  52         int len;
  53
  54         /* Linked list.  */
  55         struct hash_bucket *next;
  56
  57         /* Hash key. */
  58         unsigned int key;
  59
  60         /* Data.  */
  61         void *data;
  62 };
  63
  64 struct hashstats {
  65         /* number of empty hash buckets */
  66         atomic_uint_fast32_t empty;
  67         /* sum of squares of bucket length */
  68         atomic_uint_fast32_t ssq;
  69 };
  70
  71 struct hash {
  72         /* Hash bucket. */
  73         struct hash_bucket **index;
  74
  75         /* Hash table size. Must be power of 2 */
  76         unsigned int size;
  77
  78         /* If max_size is 0 there is no limit */
  79         unsigned int max_size;
  80
  81         /* Key make function. */
  82         unsigned int (*hash_key)(const void *);
  83
  84         /* Data compare function. */
  85         bool (*hash_cmp)(const void *, const void *);
  86
  87         /* Backet alloc. */
  88         unsigned long count;
  89
  90         struct hashstats stats;
  91
  92         /* hash name */
  93         char *name;
  94 };
  95
  96 #define hashcount(X) ((X)->count)
  97
  98 /*
  99  * Create a hash table.
 100  *
 101  * The created hash table uses chaining and a user-provided comparator function
 102  * to resolve collisions. For best performance use a perfect hash function.
 103  * Worst case lookup time is O(N) when using a constant hash function. Best
 104  * case lookup time is O(1) when using a perfect hash function.
 105  *
 106  * The initial size of the created hash table is HASH_INITIAL_SIZE.
 107  *
 108  * hash_key
 109  *    hash function to use; should return a unique unsigned integer when called
 110  *    with a data item. Collisions are acceptable.
 111  *
 112  * hash_cmp
 113  *    comparison function used for resolving collisions; when called with two
 114  *    data items, should return nonzero if the two items are equal and 0
 115  *    otherwise
 116  *
 117  * name
 118  *    optional name for the hashtable; this is used when displaying global
 119  *    hashtable statistics. If this parameter is NULL the hash's name will be
 120  *    set to NULL and the default name will be displayed when showing
 121  *    statistics.
 122  *
 123  * Returns:
 124  *    a new hash table
 125  */
 126 extern struct hash *hash_create(unsigned int (*hash_key)(const void *),
 127                                 bool (*hash_cmp)(const void *, const void *),
 128                                 const char *name);
 129
 130 /*
 131  * Create a hash table.
 132  *
 133  * The created hash table uses chaining and a user-provided comparator function
 134  * to resolve collisions. For best performance use a perfect hash function.
 135  * Worst case lookup time is O(N) when using a constant hash function. Best
 136  * case lookup time is O(1) when using a perfect hash function.
 137  *
 138  * size
 139  *    initial number of hash buckets to allocate; must be a power of 2 or the
 140  *    program will assert
 141  *
 142  * hash_key
 143  *    hash function to use; should return a unique unsigned integer when called
 144  *    with a data item. Collisions are acceptable.
 145  *
 146  * hash_cmp
 147  *    comparison function used for resolving collisions; when called with two
 148  *    data items, should return nonzero if the two items are equal and 0
 149  *    otherwise
 150  *
 151  * name
 152  *    optional name for the hashtable; this is used when displaying global
 153  *    hashtable statistics. If this parameter is NULL the hash's name will be
 154  *    set to NULL and the default name will be displayed when showing
 155  *    statistics.
 156  *
 157  * Returns:
 158  *    a new hash table
 159  */
 160 extern struct hash *
 161 hash_create_size(unsigned int size, unsigned int (*hash_key)(const void *),
 162                  bool (*hash_cmp)(const void *, const void *),
 163                  const char *name);
 164
 165 /*
 166  * Retrieve or insert data from / into a hash table.
 167  *
 168  * This function is somewhat counterintuitive in its usage. In order to look up
 169  * an element from its key, you must provide the data item itself, with the
 170  * portions used in the hash function set to the same values as the data item
 171  * to retrieve. To insert a data element, either provide the key as just
 172  * described and provide alloc_func as descrbied below to allocate the full
 173  * data element, or provide the full data element and pass 'hash_alloc_intern'
 174  * to alloc_func.
 175  *
 176  * hash
 177  *    hash table to operate on
 178  *
 179  * data
 180  *    data to insert or retrieve - A hash bucket will not be created if
 181  *    the alloc_func returns a NULL pointer and nothing will be added to
 182  *    the hash.  As such bucket->data will always be non-NULL.
 183  *
 184  * alloc_func
 185  *    function to call if the item is not found in the hash table. This
 186  *    function is called with the value of 'data' and should create the data
 187  *    item to insert and return a pointer to it. If the data has already been
 188  *    completely created and provided in the 'data' parameter, passing
 189  *    'hash_alloc_intern' to this parameter will cause 'data' to be inserted.
 190  *    If this parameter is NULL, then this call to hash_get is equivalent to
 191  *    hash_lookup.
 192  *
 193  * Returns:
 194  *    the data item found or inserted, or NULL if alloc_func is NULL and the
 195  *    data is not found
 196  */
 197 extern void *hash_get(struct hash *hash, void *data,
 198                       void *(*alloc_func)(void *));
 199
 200 /*
 201  * Dummy element allocation function.
 202  *
 203  * See hash_get for details.
 204  *
 205  * data
 206  *    data to insert into the hash table
 207  *
 208  * Returns:
 209  *    data
 210  */
 211 extern void *hash_alloc_intern(void *data);
 212
 213 /*
 214  * Retrieve an item from a hash table.
 215  *
 216  * This function is equivalent to calling hash_get with alloc_func set to NULL.
 217  *
 218  * hash
 219  *    hash table to operate on
 220  *
 221  * data
 222  *    data element with values used for key computation set
 223  *
 224  * Returns:
 225  *    the data element if found, or NULL if not found
 226  */
 227 extern void *hash_lookup(struct hash *hash, void *data);
 228
 229 /*
 230  * Remove an element from a hash table.
 231  *
 232  * hash
 233  *    hash table to operate on
 234  *
 235  * data
 236  *    data element to remove with values used for key computation set
 237  *
 238  * Returns:
 239  *    the removed element if found, or NULL if not found
 240  */
 241 extern void *hash_release(struct hash *hash, void *data);
 242
 243 /*
 244  * Iterate over the elements in a hash table.
 245  *
 246  * It is safe to delete items passed to the iteration function from the hash
 247  * table during iteration.  Please note that adding entries to the hash
 248  * during the walk will cause undefined behavior in that some new entries
 249  * will be walked and some will not.  So do not do this.
 250  *
 251  * The bucket passed to func will have a non-NULL data pointer.
 252  *
 253  * hash
 254  *    hash table to operate on
 255  *
 256  * func
 257  *    function to call with each data item
 258  *
 259  * arg
 260  *    arbitrary argument passed as the second parameter in each call to 'func'
 261  */
 262 extern void hash_iterate(struct hash *hash,
 263                          void (*func)(struct hash_bucket *, void *), void *arg);
 264
 265 /*
 266  * Iterate over the elements in a hash table, stopping on condition.
 267  *
 268  * It is safe to delete items passed to the iteration function from the hash
 269  * table during iteration.  Please note that adding entries to the hash
 270  * during the walk will cause undefined behavior in that some new entries
 271  * will be walked and some will not.  So do not do this.
 272  *
 273  * The bucket passed to func will have a non-NULL data pointer.
 274  *
 275  * hash
 276  *    hash table to operate on
 277  *
 278  * func
 279  *    function to call with each data item. If this function returns
 280  *    HASHWALK_ABORT then the iteration stops.
 281  *
 282  * arg
 283  *    arbitrary argument passed as the second parameter in each call to 'func'
 284  */
 285 extern void hash_walk(struct hash *hash,
 286                       int (*func)(struct hash_bucket *, void *), void *arg);
 287
 288 /*
 289  * Remove all elements from a hash table.
 290  *
 291  * hash
 292  *    hash table to operate on
 293  *
 294  * free_func
 295  *    function to call with each removed item; intended to free the data
 296  */
 297 extern void hash_clean(struct hash *hash, void (*free_func)(void *));
 298
 299 /*
 300  * Delete a hash table.
 301  *
 302  * This function assumes the table is empty. Call hash_clean to delete the
 303  * hashtable contents if necessary.
 304  *
 305  * hash
 306  *    hash table to delete
 307  */
 308 extern void hash_free(struct hash *hash);
 309
 310 /*
 311  * Converts a hash table to an unsorted linked list.
 312  * Does not modify the hash table in any way.
 313  *
 314  * hash
 315  *    hash table to convert
 316  */
 317 extern struct list *hash_to_list(struct hash *hash);
 318
 319 /*
 320  * Hash a string using the modified Bernstein hash.
 321  *
 322  * This is not a perfect hash function.
 323  *
 324  * str
 325  *    string to hash
 326  *
 327  * Returns:
 328  *    modified Bernstein hash of the string
 329  */
 330 extern unsigned int string_hash_make(const char *);
 331
 332 /*
 333  * Install CLI commands for viewing global hash table statistics.
 334  */
 335 extern void hash_cmd_init(void);
 336
 337 #ifdef __cplusplus
 338 }
 339 #endif
 340
 341 #endif /* _ZEBRA_HASH_H */