diff options
Diffstat (limited to 'lib/hash.h')
| -rw-r--r-- | lib/hash.h | 337 |
1 files changed, 337 insertions, 0 deletions
diff --git a/lib/hash.h b/lib/hash.h new file mode 100644 index 0000000..91770d1 --- /dev/null +++ b/lib/hash.h @@ -0,0 +1,337 @@ +/* Hash routine. + * Copyright (C) 1998 Kunihiro Ishiguro + * + * This file is part of GNU Zebra. + * + * GNU Zebra is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published + * by the Free Software Foundation; either version 2, or (at your + * option) any later version. + * + * GNU Zebra is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef _ZEBRA_HASH_H +#define _ZEBRA_HASH_H + +#include "memory.h" +#include "frratomic.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* Default hash table size. */ +#define HASH_INITIAL_SIZE 256 +/* Expansion threshold */ +#define HASH_THRESHOLD(used, size) ((used) > (size)) + +#define HASHWALK_CONTINUE 0 +#define HASHWALK_ABORT -1 + +struct hash_bucket { + /* + * if this bucket is the head of the linked listed, len denotes the + * number of elements in the list + */ + int len; + + /* Linked list. */ + struct hash_bucket *next; + + /* Hash key. */ + unsigned int key; + + /* Data. */ + void *data; +}; + +struct hashstats { + /* number of empty hash buckets */ + atomic_uint_fast32_t empty; + /* sum of squares of bucket length */ + atomic_uint_fast32_t ssq; +}; + +struct hash { + /* Hash bucket. */ + struct hash_bucket **index; + + /* Hash table size. Must be power of 2 */ + unsigned int size; + + /* If max_size is 0 there is no limit */ + unsigned int max_size; + + /* Key make function. */ + unsigned int (*hash_key)(const void *); + + /* Data compare function. */ + bool (*hash_cmp)(const void *, const void *); + + /* Bucket alloc. */ + unsigned long count; + + struct hashstats stats; + + /* hash name */ + char *name; +}; + +#define hashcount(X) ((X)->count) + +/* + * Create a hash table. + * + * The created hash table uses chaining and a user-provided comparator function + * to resolve collisions. For best performance use a perfect hash function. + * Worst case lookup time is O(N) when using a constant hash function. Best + * case lookup time is O(1) when using a perfect hash function. + * + * The initial size of the created hash table is HASH_INITIAL_SIZE. + * + * hash_key + * hash function to use; should return a unique unsigned integer when called + * with a data item. Collisions are acceptable. + * + * hash_cmp + * comparison function used for resolving collisions; when called with two + * data items, should return true if the two items are equal and false + * otherwise + * + * name + * optional name for the hashtable; this is used when displaying global + * hashtable statistics. If this parameter is NULL the hash's name will be + * set to NULL and the default name will be displayed when showing + * statistics. + * + * Returns: + * a new hash table + */ +extern struct hash *hash_create(unsigned int (*hash_key)(const void *), + bool (*hash_cmp)(const void *, const void *), + const char *name); + +/* + * Create a hash table. + * + * The created hash table uses chaining and a user-provided comparator function + * to resolve collisions. For best performance use a perfect hash function. + * Worst case lookup time is O(N) when using a constant hash function. Best + * case lookup time is O(1) when using a perfect hash function. + * + * size + * initial number of hash buckets to allocate; must be a power of 2 or the + * program will assert + * + * hash_key + * hash function to use; should return a unique unsigned integer when called + * with a data item. Collisions are acceptable. + * + * hash_cmp + * comparison function used for resolving collisions; when called with two + * data items, should return true if the two items are equal and false + * otherwise + * + * name + * optional name for the hashtable; this is used when displaying global + * hashtable statistics. If this parameter is NULL the hash's name will be + * set to NULL and the default name will be displayed when showing + * statistics. + * + * Returns: + * a new hash table + */ +extern struct hash * +hash_create_size(unsigned int size, unsigned int (*hash_key)(const void *), + bool (*hash_cmp)(const void *, const void *), + const char *name); + +/* + * Retrieve or insert data from / into a hash table. + * + * This function is somewhat counterintuitive in its usage. In order to look up + * an element from its key, you must provide the data item itself, with the + * portions used in the hash function set to the same values as the data item + * to retrieve. To insert a data element, either provide the key as just + * described and provide alloc_func as described below to allocate the full + * data element, or provide the full data element and pass 'hash_alloc_intern' + * to alloc_func. + * + * hash + * hash table to operate on + * + * data + * data to insert or retrieve - A hash bucket will not be created if + * the alloc_func returns a NULL pointer and nothing will be added to + * the hash. As such bucket->data will always be non-NULL. + * + * alloc_func + * function to call if the item is not found in the hash table. This + * function is called with the value of 'data' and should create the data + * item to insert and return a pointer to it. If the data has already been + * completely created and provided in the 'data' parameter, passing + * 'hash_alloc_intern' to this parameter will cause 'data' to be inserted. + * If this parameter is NULL, then this call to hash_get is equivalent to + * hash_lookup. + * + * Returns: + * the data item found or inserted, or NULL if alloc_func is NULL and the + * data is not found + */ +extern void *hash_get(struct hash *hash, void *data, + void *(*alloc_func)(void *)); + +/* + * Dummy element allocation function. + * + * See hash_get for details. + * + * data + * data to insert into the hash table + * + * Returns: + * data + */ +extern void *hash_alloc_intern(void *data); + +/* + * Retrieve an item from a hash table. + * + * This function is equivalent to calling hash_get with alloc_func set to NULL. + * + * hash + * hash table to operate on + * + * data + * data element with values used for key computation set + * + * Returns: + * the data element if found, or NULL if not found + */ +extern void *hash_lookup(struct hash *hash, void *data); + +/* + * Remove an element from a hash table. + * + * hash + * hash table to operate on + * + * data + * data element to remove with values used for key computation set + * + * Returns: + * the removed element if found, or NULL if not found + */ +extern void *hash_release(struct hash *hash, void *data); + +/* + * Iterate over the elements in a hash table. + * + * The passed in arg to the handler function is the only safe + * item to delete from the hash. + * + * Please note that adding entries to the hash + * during the walk will cause undefined behavior in that some new entries + * will be walked and some will not. So do not do this. + * + * The bucket passed to func will have a non-NULL data pointer. + * + * hash + * hash table to operate on + * + * func + * function to call with each data item + * + * arg + * arbitrary argument passed as the second parameter in each call to 'func' + */ +extern void hash_iterate(struct hash *hash, + void (*func)(struct hash_bucket *, void *), void *arg); + +/* + * Iterate over the elements in a hash table, stopping on condition. + * + * The passed in arg to the handler function is the only safe item + * to delete from the hash. + * + * Please note that adding entries to the hash + * during the walk will cause undefined behavior in that some new entries + * will be walked and some will not. So do not do this. + * + * The bucket passed to func will have a non-NULL data pointer. + * + * hash + * hash table to operate on + * + * func + * function to call with each data item. If this function returns + * HASHWALK_ABORT then the iteration stops. + * + * arg + * arbitrary argument passed as the second parameter in each call to 'func' + */ +extern void hash_walk(struct hash *hash, + int (*func)(struct hash_bucket *, void *), void *arg); + +/* + * Remove all elements from a hash table. + * + * hash + * hash table to operate on + * + * free_func + * function to call with each removed item; intended to free the data + */ +extern void hash_clean(struct hash *hash, void (*free_func)(void *)); + +/* + * Delete a hash table. + * + * This function assumes the table is empty. Call hash_clean to delete the + * hashtable contents if necessary. + * + * hash + * hash table to delete + */ +extern void hash_free(struct hash *hash); + +/* + * Converts a hash table to an unsorted linked list. + * Does not modify the hash table in any way. + * + * hash + * hash table to convert + */ +extern struct list *hash_to_list(struct hash *hash); + +/* + * Hash a string using the modified Bernstein hash. + * + * This is not a perfect hash function. + * + * str + * string to hash + * + * Returns: + * modified Bernstein hash of the string + */ +extern unsigned int string_hash_make(const char *); + +/* + * Install CLI commands for viewing global hash table statistics. + */ +extern void hash_cmd_init(void); + +#ifdef __cplusplus +} +#endif + +#endif /* _ZEBRA_HASH_H */ |