1*1f5207b7SJohn Levon /* Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */ 2*1f5207b7SJohn Levon 3*1f5207b7SJohn Levon #ifndef __HASHTABLE_CWC22_H__ 4*1f5207b7SJohn Levon #define __HASHTABLE_CWC22_H__ 5*1f5207b7SJohn Levon 6*1f5207b7SJohn Levon struct hashtable; 7*1f5207b7SJohn Levon 8*1f5207b7SJohn Levon /* Example of use: 9*1f5207b7SJohn Levon * 10*1f5207b7SJohn Levon * struct hashtable *h; 11*1f5207b7SJohn Levon * struct some_key *k; 12*1f5207b7SJohn Levon * struct some_value *v; 13*1f5207b7SJohn Levon * 14*1f5207b7SJohn Levon * static unsigned int hash_from_key_fn( void *k ); 15*1f5207b7SJohn Levon * static int keys_equal_fn ( void *key1, void *key2 ); 16*1f5207b7SJohn Levon * 17*1f5207b7SJohn Levon * h = create_hashtable(16, hash_from_key_fn, keys_equal_fn); 18*1f5207b7SJohn Levon * k = (struct some_key *) malloc(sizeof(struct some_key)); 19*1f5207b7SJohn Levon * v = (struct some_value *) malloc(sizeof(struct some_value)); 20*1f5207b7SJohn Levon * 21*1f5207b7SJohn Levon * (initialise k and v to suitable values) 22*1f5207b7SJohn Levon * 23*1f5207b7SJohn Levon * if (! hashtable_insert(h,k,v) ) 24*1f5207b7SJohn Levon * { exit(-1); } 25*1f5207b7SJohn Levon * 26*1f5207b7SJohn Levon * if (NULL == (found = hashtable_search(h,k) )) 27*1f5207b7SJohn Levon * { printf("not found!"); } 28*1f5207b7SJohn Levon * 29*1f5207b7SJohn Levon * if (NULL == (found = hashtable_remove(h,k) )) 30*1f5207b7SJohn Levon * { printf("Not found\n"); } 31*1f5207b7SJohn Levon * 32*1f5207b7SJohn Levon */ 33*1f5207b7SJohn Levon 34*1f5207b7SJohn Levon /* Macros may be used to define type-safe(r) hashtable access functions, with 35*1f5207b7SJohn Levon * methods specialized to take known key and value types as parameters. 36*1f5207b7SJohn Levon * 37*1f5207b7SJohn Levon * Example: 38*1f5207b7SJohn Levon * 39*1f5207b7SJohn Levon * Insert this at the start of your file: 40*1f5207b7SJohn Levon * 41*1f5207b7SJohn Levon * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value); 42*1f5207b7SJohn Levon * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value); 43*1f5207b7SJohn Levon * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value); 44*1f5207b7SJohn Levon * 45*1f5207b7SJohn Levon * This defines the functions 'insert_some', 'search_some' and 'remove_some'. 46*1f5207b7SJohn Levon * These operate just like hashtable_insert etc., with the same parameters, 47*1f5207b7SJohn Levon * but their function signatures have 'struct some_key *' rather than 48*1f5207b7SJohn Levon * 'void *', and hence can generate compile time errors if your program is 49*1f5207b7SJohn Levon * supplying incorrect data as a key (and similarly for value). 50*1f5207b7SJohn Levon * 51*1f5207b7SJohn Levon * Note that the hash and key equality functions passed to create_hashtable 52*1f5207b7SJohn Levon * still take 'void *' parameters instead of 'some key *'. This shouldn't be 53*1f5207b7SJohn Levon * a difficult issue as they're only defined and passed once, and the other 54*1f5207b7SJohn Levon * functions will ensure that only valid keys are supplied to them. 55*1f5207b7SJohn Levon * 56*1f5207b7SJohn Levon * The cost for this checking is increased code size and runtime overhead 57*1f5207b7SJohn Levon * - if performance is important, it may be worth switching back to the 58*1f5207b7SJohn Levon * unsafe methods once your program has been debugged with the safe methods. 59*1f5207b7SJohn Levon * This just requires switching to some simple alternative defines - eg: 60*1f5207b7SJohn Levon * #define insert_some hashtable_insert 61*1f5207b7SJohn Levon * 62*1f5207b7SJohn Levon */ 63*1f5207b7SJohn Levon 64*1f5207b7SJohn Levon /***************************************************************************** 65*1f5207b7SJohn Levon * create_hashtable 66*1f5207b7SJohn Levon 67*1f5207b7SJohn Levon * @name create_hashtable 68*1f5207b7SJohn Levon * @param minsize minimum initial size of hashtable 69*1f5207b7SJohn Levon * @param hashfunction function for hashing keys 70*1f5207b7SJohn Levon * @param key_eq_fn function for determining key equality 71*1f5207b7SJohn Levon * @return newly created hashtable or NULL on failure 72*1f5207b7SJohn Levon */ 73*1f5207b7SJohn Levon 74*1f5207b7SJohn Levon struct hashtable * 75*1f5207b7SJohn Levon create_hashtable(unsigned int minsize, 76*1f5207b7SJohn Levon unsigned int (*hashfunction) (void*), 77*1f5207b7SJohn Levon int (*key_eq_fn) (void*,void*)); 78*1f5207b7SJohn Levon 79*1f5207b7SJohn Levon /***************************************************************************** 80*1f5207b7SJohn Levon * hashtable_insert 81*1f5207b7SJohn Levon 82*1f5207b7SJohn Levon * @name hashtable_insert 83*1f5207b7SJohn Levon * @param h the hashtable to insert into 84*1f5207b7SJohn Levon * @param k the key - hashtable claims ownership and will free on removal 85*1f5207b7SJohn Levon * @param v the value - does not claim ownership 86*1f5207b7SJohn Levon * @return non-zero for successful insertion 87*1f5207b7SJohn Levon * 88*1f5207b7SJohn Levon * This function will cause the table to expand if the insertion would take 89*1f5207b7SJohn Levon * the ratio of entries to table size over the maximum load factor. 90*1f5207b7SJohn Levon * 91*1f5207b7SJohn Levon * This function does not check for repeated insertions with a duplicate key. 92*1f5207b7SJohn Levon * The value returned when using a duplicate key is undefined -- when 93*1f5207b7SJohn Levon * the hashtable changes size, the order of retrieval of duplicate key 94*1f5207b7SJohn Levon * entries is reversed. 95*1f5207b7SJohn Levon * If in doubt, remove before insert. 96*1f5207b7SJohn Levon */ 97*1f5207b7SJohn Levon 98*1f5207b7SJohn Levon int 99*1f5207b7SJohn Levon hashtable_insert(struct hashtable *h, void *k, void *v); 100*1f5207b7SJohn Levon 101*1f5207b7SJohn Levon #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \ 102*1f5207b7SJohn Levon int fnname (struct hashtable *h, keytype *k, valuetype *v) \ 103*1f5207b7SJohn Levon { \ 104*1f5207b7SJohn Levon return hashtable_insert(h,k,v); \ 105*1f5207b7SJohn Levon } 106*1f5207b7SJohn Levon 107*1f5207b7SJohn Levon /***************************************************************************** 108*1f5207b7SJohn Levon * hashtable_search 109*1f5207b7SJohn Levon 110*1f5207b7SJohn Levon * @name hashtable_search 111*1f5207b7SJohn Levon * @param h the hashtable to search 112*1f5207b7SJohn Levon * @param k the key to search for - does not claim ownership 113*1f5207b7SJohn Levon * @return the value associated with the key, or NULL if none found 114*1f5207b7SJohn Levon */ 115*1f5207b7SJohn Levon 116*1f5207b7SJohn Levon void * 117*1f5207b7SJohn Levon hashtable_search(struct hashtable *h, void *k); 118*1f5207b7SJohn Levon 119*1f5207b7SJohn Levon #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \ 120*1f5207b7SJohn Levon valuetype * fnname (struct hashtable *h, keytype *k) \ 121*1f5207b7SJohn Levon { \ 122*1f5207b7SJohn Levon return (valuetype *) (hashtable_search(h,k)); \ 123*1f5207b7SJohn Levon } 124*1f5207b7SJohn Levon 125*1f5207b7SJohn Levon /***************************************************************************** 126*1f5207b7SJohn Levon * hashtable_remove 127*1f5207b7SJohn Levon 128*1f5207b7SJohn Levon * @name hashtable_remove 129*1f5207b7SJohn Levon * @param h the hashtable to remove the item from 130*1f5207b7SJohn Levon * @param k the key to search for - does not claim ownership 131*1f5207b7SJohn Levon * @return the value associated with the key, or NULL if none found 132*1f5207b7SJohn Levon */ 133*1f5207b7SJohn Levon 134*1f5207b7SJohn Levon void * /* returns value */ 135*1f5207b7SJohn Levon hashtable_remove(struct hashtable *h, void *k); 136*1f5207b7SJohn Levon 137*1f5207b7SJohn Levon #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \ 138*1f5207b7SJohn Levon valuetype * fnname (struct hashtable *h, keytype *k) \ 139*1f5207b7SJohn Levon { \ 140*1f5207b7SJohn Levon return (valuetype *) (hashtable_remove(h,k)); \ 141*1f5207b7SJohn Levon } 142*1f5207b7SJohn Levon 143*1f5207b7SJohn Levon 144*1f5207b7SJohn Levon /***************************************************************************** 145*1f5207b7SJohn Levon * hashtable_count 146*1f5207b7SJohn Levon 147*1f5207b7SJohn Levon * @name hashtable_count 148*1f5207b7SJohn Levon * @param h the hashtable 149*1f5207b7SJohn Levon * @return the number of items stored in the hashtable 150*1f5207b7SJohn Levon */ 151*1f5207b7SJohn Levon unsigned int 152*1f5207b7SJohn Levon hashtable_count(struct hashtable *h); 153*1f5207b7SJohn Levon 154*1f5207b7SJohn Levon 155*1f5207b7SJohn Levon /***************************************************************************** 156*1f5207b7SJohn Levon * hashtable_destroy 157*1f5207b7SJohn Levon 158*1f5207b7SJohn Levon * @name hashtable_destroy 159*1f5207b7SJohn Levon * @param h the hashtable 160*1f5207b7SJohn Levon * @param free_values whether to call 'free' on the remaining values 161*1f5207b7SJohn Levon */ 162*1f5207b7SJohn Levon 163*1f5207b7SJohn Levon void 164*1f5207b7SJohn Levon hashtable_destroy(struct hashtable *h, int free_values); 165*1f5207b7SJohn Levon 166*1f5207b7SJohn Levon #endif /* __HASHTABLE_CWC22_H__ */ 167*1f5207b7SJohn Levon 168*1f5207b7SJohn Levon /* 169*1f5207b7SJohn Levon * Copyright (c) 2002, Christopher Clark 170*1f5207b7SJohn Levon * All rights reserved. 171*1f5207b7SJohn Levon * 172*1f5207b7SJohn Levon * Redistribution and use in source and binary forms, with or without 173*1f5207b7SJohn Levon * modification, are permitted provided that the following conditions 174*1f5207b7SJohn Levon * are met: 175*1f5207b7SJohn Levon * 176*1f5207b7SJohn Levon * * Redistributions of source code must retain the above copyright 177*1f5207b7SJohn Levon * notice, this list of conditions and the following disclaimer. 178*1f5207b7SJohn Levon * 179*1f5207b7SJohn Levon * * Redistributions in binary form must reproduce the above copyright 180*1f5207b7SJohn Levon * notice, this list of conditions and the following disclaimer in the 181*1f5207b7SJohn Levon * documentation and/or other materials provided with the distribution. 182*1f5207b7SJohn Levon * 183*1f5207b7SJohn Levon * * Neither the name of the original author; nor the names of any contributors 184*1f5207b7SJohn Levon * may be used to endorse or promote products derived from this software 185*1f5207b7SJohn Levon * without specific prior written permission. 186*1f5207b7SJohn Levon * 187*1f5207b7SJohn Levon * 188*1f5207b7SJohn Levon * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 189*1f5207b7SJohn Levon * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 190*1f5207b7SJohn Levon * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 191*1f5207b7SJohn Levon * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 192*1f5207b7SJohn Levon * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 193*1f5207b7SJohn Levon * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 194*1f5207b7SJohn Levon * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 195*1f5207b7SJohn Levon * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 196*1f5207b7SJohn Levon * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 197*1f5207b7SJohn Levon * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 198*1f5207b7SJohn Levon * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 199*1f5207b7SJohn Levon */ 200