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         bool (*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                                 bool (*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                  bool (*hash_cmp)(const void *, const void *),
 154                  const char *name);
 155
 156 /*
 157  * Retrieve or insert data from / into a hash table.
 158  *
 159  * This function is somewhat counterintuitive in its usage. In order to look up
 160  * an element from its key, you must provide the data item itself, with the
 161  * portions used in the hash function set to the same values as the data item
 162  * to retrieve. To insert a data element, either provide the key as just
 163  * described and provide alloc_func as descrbied below to allocate the full
 164  * data element, or provide the full data element and pass 'hash_alloc_intern'
 165  * to alloc_func.
 166  *
 167  * hash
 168  *    hash table to operate on
 169  *
 170  * data
 171  *    data to insert or retrieve - A hash backet will not be created if
 172  *    the alloc_func returns a NULL pointer and nothing will be added to
 173  *    the hash.  As such backet->data will always be non-NULL.
 174  *
 175  * alloc_func
 176  *    function to call if the item is not found in the hash table. This
 177  *    function is called with the value of 'data' and should create the data
 178  *    item to insert and return a pointer to it. If the data has already been
 179  *    completely created and provided in the 'data' parameter, passing
 180  *    'hash_alloc_intern' to this parameter will cause 'data' to be inserted.
 181  *    If this parameter is NULL, then this call to hash_get is equivalent to
 182  *    hash_lookup.
 183  *
 184  * Returns:
 185  *    the data item found or inserted, or NULL if alloc_func is NULL and the
 186  *    data is not found
 187  */
 188 extern void *hash_get(struct hash *hash, void *data,
 189                       void *(*alloc_func)(void *));
 190
 191 /*
 192  * Dummy element allocation function.
 193  *
 194  * See hash_get for details.
 195  *
 196  * data
 197  *    data to insert into the hash table
 198  *
 199  * Returns:
 200  *    data
 201  */
 202 extern void *hash_alloc_intern(void *data);
 203
 204 /*
 205  * Retrieve an item from a hash table.
 206  *
 207  * This function is equivalent to calling hash_get with alloc_func set to NULL.
 208  *
 209  * hash
 210  *    hash table to operate on
 211  *
 212  * data
 213  *    data element with values used for key computation set
 214  *
 215  * Returns:
 216  *    the data element if found, or NULL if not found
 217  */
 218 extern void *hash_lookup(struct hash *hash, void *data);
 219
 220 /*
 221  * Remove an element from a hash table.
 222  *
 223  * hash
 224  *    hash table to operate on
 225  *
 226  * data
 227  *    data element to remove with values used for key computation set
 228  *
 229  * Returns:
 230  *    the removed element if found, or NULL if not found
 231  */
 232 extern void *hash_release(struct hash *hash, void *data);
 233
 234 /*
 235  * Iterate over the elements in a hash table.
 236  *
 237  * It is safe to delete items passed to the iteration function from the hash
 238  * table during iteration.  Please note that adding entries to the hash
 239  * during the walk will cause undefined behavior in that some new entries
 240  * will be walked and some will not.  So do not do this.
 241  *
 242  * The backet passed to func will have a non-NULL data pointer.
 243  *
 244  * hash
 245  *    hash table to operate on
 246  *
 247  * func
 248  *    function to call with each data item
 249  *
 250  * arg
 251  *    arbitrary argument passed as the second parameter in each call to 'func'
 252  */
 253 extern void hash_iterate(struct hash *hash,
 254                          void (*func)(struct hash_backet *, void *), void *arg);
 255
 256 /*
 257  * Iterate over the elements in a hash table, stopping on condition.
 258  *
 259  * It is safe to delete items passed to the iteration function from the hash
 260  * table during iteration.  Please note that adding entries to the hash
 261  * during the walk will cause undefined behavior in that some new entries
 262  * will be walked and some will not.  So do not do this.
 263  *
 264  * The backet passed to func will have a non-NULL data pointer.
 265  *
 266  * hash
 267  *    hash table to operate on
 268  *
 269  * func
 270  *    function to call with each data item. If this function returns
 271  *    HASHWALK_ABORT then the iteration stops.
 272  *
 273  * arg
 274  *    arbitrary argument passed as the second parameter in each call to 'func'
 275  */
 276 extern void hash_walk(struct hash *hash,
 277                       int (*func)(struct hash_backet *, void *), void *arg);
 278
 279 /*
 280  * Remove all elements from a hash table.
 281  *
 282  * hash
 283  *    hash table to operate on
 284  *
 285  * free_func
 286  *    function to call with each removed item; intended to free the data
 287  */
 288 extern void hash_clean(struct hash *hash, void (*free_func)(void *));
 289
 290 /*
 291  * Delete a hash table.
 292  *
 293  * This function assumes the table is empty. Call hash_clean to delete the
 294  * hashtable contents if necessary.
 295  *
 296  * hash
 297  *    hash table to delete
 298  */
 299 extern void hash_free(struct hash *hash);
 300
 301 /*
 302  * Converts a hash table to an unsorted linked list.
 303  * Does not modify the hash table in any way.
 304  *
 305  * hash
 306  *    hash table to convert
 307  */
 308 extern struct list *hash_to_list(struct hash *hash);
 309
 310 /*
 311  * Hash a string using the modified Bernstein hash.
 312  *
 313  * This is not a perfect hash function.
 314  *
 315  * str
 316  *    string to hash
 317  *
 318  * Returns:
 319  *    modified Bernstein hash of the string
 320  */
 321 extern unsigned int string_hash_make(const char *);
 322
 323 /*
 324  * Install CLI commands for viewing global hash table statistics.
 325  */
 326 extern void hash_cmd_init(void);
 327
 328 #endif /* _ZEBRA_HASH_H */