/* * Copyright (c) 2002-2005 Lev Walkin . All rights reserved. * Copyright (c) 2001-2004 Netli, Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * $Id: genhash.h 447 2005-06-07 06:51:10Z vlm $ */ #ifndef __GENHASH_H__ #define __GENHASH_H__ /* * General purpose hashing framework. * Refer to the corresponding .c source file for the detailed description. * * WARNING: Generally, functions don't allow NULL's to be passed * as the genhash_t pointers, if not explicitly stated otherwise. */ typedef struct genhash_s genhash_t; /* * Create a new hash table * keycmpf : function which returns 0 if keys are equal, else !0 * keyhashf : function which computes the hash value of a key * keydestroyf : function for destroying keys, can be NULL for no destructor * valuedestroyf: function for destroying values, can be NULL for no destructor */ genhash_t *genhash_new( int (*keycmpf) (const void *key1, const void *key2), unsigned int (*keyhashf) (const void *key), void (*keydestroyf) (void *key), void (*valuedestroyf) (void *value)); /* * Re-initialize genhash structure with new callback functions. * (Rarely ever used). */ int genhash_reinit( genhash_t *hash, int (*keycmpf) (const void *key1, const void *key2), unsigned int (*keyhashf) (const void *key), void (*keydestroyf) (void *key), void (*valuedestroyf) (void *value)); /* * Initialize the LRU-driven elements count limiting * and/or set a new Least Recently Used list size limit. * If a new entry is being added to the hash, the least recently used entry * (one at the bottom of the LRU list) will be automatically deleted. * The deletion may be skipped if the hash is very small * (currently, "small" means no longer than 4 entries). * This function is immune to NULL argument. * * RETURN VALUES: * The previous LRU limit, or -1/EINVAL when h is NULL. * EXAMPLE: * genhash_set_lru_limit(h, 1500); // Maximum 1500 entries in the hash */ int genhash_set_lru_limit(genhash_t *h, int new_lru_limit); /* * Set the system-wide (!!!) limit on maximum number of buckets. * If the value is 0, the hash is allowed to store only 4 elements inline * (buckets allocation is suppressed). * If the value is 1, the hash turns out into a linked list. * The default limit is about 1M buckets. * RETURN VALUES: * The previous buckets number limit. */ int genhash_set_buckets_limit(int new_max_number_of_buckets); /* * destroys a hash, freeing each key and/or value. * Keys are always destroyed before values using the destructors * specified upon hash creation. * This function is immune to NULL argument. */ void genhash_destroy(genhash_t *h); /* * Delete all elements from the hash, retaining the hash structure itself. * Optionally, it may be told to invoke, or not invoke the corresponding * key/value destructors. * This function is immune to NULL argument. * * EXAMPLE: * genhash_empty(h, 1, 1); // Remove all entries, invoking destructors */ void genhash_empty(genhash_t *h, int freekeys, int freevalues); /* * Add, returns 0 on success, -1 on failure (ENOMEM). Note, you CAN add * records with duplicate keys. No guarantees about order preservations. * * EXAMPLE: * char *key_str = strdup("key"); * char *val_str = strdup("arbitrary value"); * if(genhash_add(h, key_str, val_str) != 0) { * free(key_str); * free(val_str); * perror("genhash_add failed"); * exit(EX_SOFTWARE); * } */ int genhash_add(genhash_t *h, void *key, void *value); /* * Add, but only if a mapping is not there already. * RETURN VALUES: * 0: Element added successfully. * -1/EINVAL: Invalid arguments (key == NULL). * -1/EEXIST: Duplicate entry is found. * -1/ENOMEM: Memory allocation failed */ int genhash_addunique(genhash_t *h, void *key, void *value); /* * Fetch - returns pointer to a value, NULL/ESRCH if not found */ void *genhash_get(genhash_t *h, const void *key); /* * Delete - returns 0 on success, -1/ESRCH if not found. * Keys are always destroyed before values using the destructors * specified upon hash creation. */ int genhash_del(genhash_t *h, void *key); /* * Return the number of elements in a hash. * This function is immune to NULL argument. */ int genhash_count(genhash_t *h); /* * External iterator structure for using with iterator-based walking functions. * This declaration is NOT INTENDED TO BE USED BY AN APPLICATION DIRECTLY * The pointer to the already allocated structure must be passed to * genhash_iter*() functions. */ typedef struct genhash_iter_s { genhash_t *hash_ptr; union { int item_number; void *location; } un; int order_lru_first; struct genhash_iter_s *iter_prev; struct genhash_iter_s *iter_next; } genhash_iter_t; /* * Initialize the iterator for walking through the hash. * The memory block to be used as iterator is provided by the (*iter) pointer. * This memory must be allocated (possibly, on the stack) by the caller. * OWNERSHIP: * The initialized iterator must be disposed of by calling * genhash_iter_done(). * ORDER: * By default, the elements are iterated in the "most recent first" order, * use reverse_order to change that. For very small number of entries * (currently, 4) the order may be IGNORED. * RETURN VALUES: * number of entries the hash had at the moment. */ int genhash_iter_init(genhash_iter_t *iter, genhash_t *hash_to_use, int reverse_order); /* * Returns the key and value of each element in optional (key) and (value), * which must be passed as the pointers to pointers (hence these ***'s). * OWNERSHIP: * The key and value are pointers to the internally manageed locations. * RETURN VALUES: * 0 if no more elements will be returned, otherwise 1. * EXAMPLE: * key_type_t *key; // Pointer to key * value_type_t *val; // Pointer to value * genhash_iter_t iter; // Iterator structure * genhash_iter_init(&iter, hash_ptr, 0); // Prepare iterator * while(genhash_iter(&iter, &key, &val)) // Iterate over hash elements * print_keyval(key, val); // Use key and value * genhash_iter_done(&iter); // Done iterations. */ int genhash_iter(genhash_iter_t *iter, void */***/key, void */***/val); /* * Dispose of the iterator. * After this operations, the iterator contents unusable * and shall not be accesed. (genhash_iter_init() is OK). */ void genhash_iter_done(genhash_iter_t *iter); /****************************************************************************/ /* * The following hashing and comparison functions are provided for * you, or you may supply your own. */ unsigned int hashf_int (const void *key); /* Key is an int * */ int cmpf_int (const void *key1, const void *key2); unsigned int hashf_void (const void *key); int cmpf_void (const void *key1, const void *key2); unsigned int hashf_string (const void *key); int cmpf_string (const void *key1, const void *key2); #endif /* __GENHASH_H__ */