| /* Copyright (C) 2002, 2007 Christopher Clark, Princeton University */ |
| /* Parallelization by Christian Bienia */ |
| |
| /* |
| * Copyright (c) 2002, 2007 Christopher Clark and Princeton University |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * * Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * |
| * * 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. |
| * |
| * * Neither the name of the original author; nor the names of any contributors |
| * may be used to endorse or promote products derived from this software |
| * without specific prior written permission. |
| * |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT OWNER |
| * 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. |
| */ |
| |
| #ifndef _HASHTABLE_H_ |
| #define _HASHTABLE_H_ |
| |
| #include <pthread.h> |
| #include "config.h" |
| |
| //WARNING: Dynamic expansion is not thread-safe |
| //#define ENABLE_DYNAMIC_EXPANSION |
| |
| //Make sure dynamic expansion and parallelization not enabled at the same time |
| #ifdef ENABLE_DYNAMIC_EXPANSION |
| #ifdef ENABLE_PTHREADS |
| #error Dynamic hashtable expansion not thread-safe |
| #endif |
| #endif |
| |
| struct hashtable; |
| |
| /* Example of use: |
| * |
| * struct hashtable *h; |
| * struct some_key *k; |
| * struct some_value *v; |
| * |
| * static unsigned int hash_from_key_fn( void *k ); |
| * static int keys_equal_fn ( void *key1, void *key2 ); |
| * |
| * h = hashtable_create(16, hash_from_key_fn, keys_equal_fn); |
| * k = (struct some_key *) malloc(sizeof(struct some_key)); |
| * v = (struct some_value *) malloc(sizeof(struct some_value)); |
| * |
| * (initialise k and v to suitable values) |
| * |
| * if (! hashtable_insert(h,k,v) ) |
| * { exit(-1); } |
| * |
| * if (NULL == (found = hashtable_search(h,k) )) |
| * { printf("not found!"); } |
| * |
| * if (NULL == (found = hashtable_remove(h,k) )) |
| * { printf("Not found\n"); } |
| * |
| */ |
| |
| /* Macros may be used to define type-safe(r) hashtable access functions, with |
| * methods specialized to take known key and value types as parameters. |
| * |
| * Example: |
| * |
| * Insert this at the start of your file: |
| * |
| * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value); |
| * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value); |
| * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value); |
| * |
| * This defines the functions 'insert_some', 'search_some' and 'remove_some'. |
| * These operate just like hashtable_insert etc., with the same parameters, |
| * but their function signatures have 'struct some_key *' rather than |
| * 'void *', and hence can generate compile time errors if your program is |
| * supplying incorrect data as a key (and similarly for value). |
| * |
| * Note that the hash and key equality functions passed to hashtable_create |
| * still take 'void *' parameters instead of 'some key *'. This shouldn't be |
| * a difficult issue as they're only defined and passed once, and the other |
| * functions will ensure that only valid keys are supplied to them. |
| * |
| * The cost for this checking is increased code size and runtime overhead |
| * - if performance is important, it may be worth switching back to the |
| * unsafe methods once your program has been debugged with the safe methods. |
| * This just requires switching to some simple alternative defines - eg: |
| * #define insert_some hashtable_insert |
| * |
| */ |
| |
| /***************************************************************************** |
| * hashtable_create |
| |
| * @name hashtable_create |
| * @param minsize minimum initial size of hashtable |
| * @param hashfunction function for hashing keys |
| * @param key_eq_fn function for determining key equality |
| * @param free_keys whether keys shall be freed or not |
| * @return newly created hashtable or NULL on failure |
| */ |
| |
| struct hashtable * hashtable_create( |
| unsigned int minsize, |
| unsigned int (*hashfunction) (void*), |
| int (*key_eq_fn) (void*,void*), |
| int free_keys |
| ); |
| |
| /* |
| * hashtable_getlock |
| |
| * @name hashtable_getlock |
| * @param h the hashtable for which to get the lock |
| * @param k the key identifying the lock |
| * @return the lock corresponding to the key |
| * |
| * This function provides management of fine-granular locks. It takes a key |
| * as argument and returns the lock corresponding to that key. The lock has |
| * to be acquired before any of the other functions that access the table can |
| * be used safely by multiple threads. After the lock has been acquired, all |
| * accesses to the hash table with this key are thread-safe. |
| */ |
| #ifdef ENABLE_PTHREADS |
| pthread_mutex_t * hashtable_getlock(struct hashtable *h, void *k); |
| #endif |
| |
| /***************************************************************************** |
| * hashtable_insert |
| |
| * @name hashtable_insert |
| * @param h the hashtable to insert into |
| * @param k the key - hashtable claims ownership and will free on removal |
| * @param v the value - does not claim ownership |
| * @return non-zero for successful insertion |
| * |
| * This function will cause the table to expand if the insertion would take |
| * the ratio of entries to table size over the maximum load factor. |
| * |
| * This function does not check for repeated insertions with a duplicate key. |
| * The value returned when using a duplicate key is undefined -- when |
| * the hashtable changes size, the order of retrieval of duplicate key |
| * entries is reversed. |
| * If in doubt, remove before insert. |
| */ |
| |
| int hashtable_insert(struct hashtable *h, void *k, void *v); |
| |
| #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \ |
| int fnname (struct hashtable *h, keytype *k, valuetype *v) \ |
| { \ |
| return hashtable_insert(h,k,v); \ |
| } |
| |
| /***************************************************************************** |
| * hashtable_search |
| |
| * @name hashtable_search |
| * @param h the hashtable to search |
| * @param k the key to search for - does not claim ownership |
| * @return the value associated with the key, or NULL if none found |
| */ |
| |
| void * hashtable_search(struct hashtable *h, void *k); |
| |
| #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \ |
| valuetype * fnname (struct hashtable *h, keytype *k) \ |
| { \ |
| return (valuetype *) (hashtable_search(h,k)); \ |
| } |
| |
| /***************************************************************************** |
| * hashtable_remove |
| |
| * @name hashtable_remove |
| * @param h the hashtable to remove the item from |
| * @param k the key to search for - does not claim ownership |
| * @return the value associated with the key, or NULL if none found |
| */ |
| |
| void * hashtable_remove(struct hashtable *h, void *k); |
| |
| #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \ |
| valuetype * fnname (struct hashtable *h, keytype *k) \ |
| { \ |
| return (valuetype *) (hashtable_remove(h,k)); \ |
| } |
| |
| |
| /***************************************************************************** |
| * hashtable_count |
| |
| * @name hashtable_count |
| * @param h the hashtable |
| * @return the number of items stored in the hashtable |
| */ |
| #ifdef ENABLE_DYNAMIC_EXPANSION |
| unsigned int hashtable_count(struct hashtable *h); |
| #endif //ENABLE_DYNAMIC_EXPANSION |
| |
| /***************************************************************************** |
| * hashtable_destroy |
| |
| * @name hashtable_destroy |
| * @param h the hashtable |
| * @param free_values whether to call 'free' on the remaining values |
| */ |
| |
| void hashtable_destroy(struct hashtable *h, int free_values); |
| |
| #endif /* _HASHTABLE_H_ */ |
| |
