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