1 /*********************************************************** 2 * Artsoft Retro-Game Library * 3 *----------------------------------------------------------* 4 * (c) 1994-2006 Artsoft Entertainment * 5 * Holger Schemel * 6 * Detmolder Strasse 189 * 7 * 33604 Bielefeld * 8 * Germany * 9 * e-mail: info@artsoft.org * 10 *----------------------------------------------------------* 11 * hash.h * 12 ***********************************************************/ 13 14 /* 15 * Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk> 16 * 17 * Permission is hereby granted, free of charge, to any person obtaining a copy 18 * of this software and associated documentation files (the "Software"), to 19 * deal in the Software without restriction, including without limitation the 20 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or 21 * sell copies of the Software, and to permit persons to whom the Software is 22 * furnished to do so, subject to the following conditions: 23 * 24 * The above copyright notice and this permission notice shall be included in 25 * all copies of the Software and its documentation and acknowledgment shall be 26 * given in the documentation and software packages that this Software was 27 * used. 28 * 29 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 30 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 31 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 32 * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER 33 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 34 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 35 * */ 36 37 #ifndef HASH_H 38 #define HASH_H 39 40 41 /* Example of use: 42 * 43 * struct hashtable *h; 44 * struct some_key *k; 45 * struct some_value *v; 46 * 47 * static unsigned int hash_from_key_fn( void *k ); 48 * static int keys_equal_fn ( void *key1, void *key2 ); 49 * 50 * h = create_hashtable(16, 0.75, hash_from_key_fn, keys_equal_fn); 51 * k = (struct some_key *) malloc(sizeof(struct some_key)); 52 * v = (struct some_value *) malloc(sizeof(struct some_value)); 53 * 54 * (initialise k and v to suitable values) 55 * 56 * if (! hashtable_insert(h,k,v) ) 57 * { exit(-1); } 58 * 59 * if (NULL == (found = hashtable_search(h,k) )) 60 * { printf("not found!"); } 61 * 62 * if (NULL == (found = hashtable_remove(h,k) )) 63 * { printf("Not found\n"); } 64 * 65 */ 66 67 /* Macros may be used to define type-safe(r) hashtable access functions, with 68 * methods specialized to take known key and value types as parameters. 69 * 70 * Example: 71 * 72 * Insert this at the start of your file: 73 * 74 * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value); 75 * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value); 76 * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value); 77 * 78 * This defines the functions 'insert_some', 'search_some' and 'remove_some'. 79 * These operate just like hashtable_insert etc., with the same parameters, 80 * but their function signatures have 'struct some_key *' rather than 81 * 'void *', and hence can generate compile time errors if your program is 82 * supplying incorrect data as a key (and similarly for value). 83 * 84 * Note that the hash and key equality functions passed to create_hashtable 85 * still take 'void *' parameters instead of 'some key *'. This shouldn't be 86 * a difficult issue as they're only defined and passed once, and the other 87 * functions will ensure that only valid keys are supplied to them. 88 * 89 * The cost for this checking is increased code size and runtime overhead 90 * - if performance is important, it may be worth switching back to the 91 * unsafe methods once your program has been debugged with the safe methods. 92 * This just requires switching to some simple alternative defines - eg: 93 * #define insert_some hashtable_insert 94 * 95 */ 96 97 98 /*****************************************************************************/ 99 struct entry 100 { 101 void *k, *v; 102 unsigned int h; 103 struct entry *next; 104 }; 105 106 struct hashtable 107 { 108 unsigned int tablelength; 109 struct entry **table; 110 unsigned int entrycount; 111 unsigned int loadlimit; 112 unsigned int (*hashfn) (void *k); 113 int (*eqfn) (void *k1, void *k2); 114 }; 115 116 /*****************************************************************************/ 117 struct hashtable_itr 118 { 119 struct hashtable *h; 120 struct entry *e; 121 unsigned int index; 122 }; 123 124 125 /***************************************************************************** 126 * create_hashtable 127 128 * @name create_hashtable 129 * @param minsize minimum initial size of hashtable 130 * @param maxloadfactor maximum ratio entries / tablesize 131 * @param hashfunction function for hashing keys 132 * @param key_eq_fn function for determining key equality 133 * @return newly created hashtable or NULL on failure 134 */ 135 136 struct hashtable * 137 create_hashtable(unsigned int minsize, float maxloadfactor, 138 unsigned int (*hashfunction) (void*), 139 int (*key_eq_fn) (void*,void*)); 140 141 /***************************************************************************** 142 * hashtable_insert 143 144 * @name hashtable_insert 145 * @param h the hashtable to insert into 146 * @param k the key - hashtable claims ownership and will free on removal 147 * @param v the value - does not claim ownership 148 * @return non-zero for successful insertion 149 * 150 * This function will cause the table to expand if the insertion would take 151 * the ratio of entries to table size over the maximum load factor. 152 * 153 * This function does not check for repeated insertions with a duplicate key. 154 * The value returned when using a duplicate key is undefined -- when 155 * the hashtable changes size, the order of retrieval of duplicate key 156 * entries is reversed. 157 * If in doubt, remove before insert. 158 */ 159 160 int 161 hashtable_insert(struct hashtable *h, void *k, void *v); 162 163 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \ 164 int fnname (struct hashtable *h, keytype *k, valuetype *v) \ 165 { \ 166 return hashtable_insert(h,k,v); \ 167 } 168 169 /***************************************************************************** 170 * hashtable_change 171 172 * @name hashtable_change 173 * @param h the hashtable to search 174 * @param k the key of the entry to change 175 * @param v the new value 176 * @return non-zero for successful change 177 */ 178 179 int 180 hashtable_change(struct hashtable *h, void *k, void *v); 181 182 #define DEFINE_HASHTABLE_CHANGE(fnname, keytype, valuetype) \ 183 int fnname (struct hashtable *h, keytype *k, valuetype *v) \ 184 { \ 185 return hashtable_change(h,k,v); \ 186 } 187 188 /***************************************************************************** 189 * hashtable_search 190 191 * @name hashtable_search 192 * @param h the hashtable to search 193 * @param k the key to search for - does not claim ownership 194 * @return the value associated with the key, or NULL if none found 195 */ 196 197 void * 198 hashtable_search(struct hashtable *h, void *k); 199 200 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \ 201 valuetype * fnname (struct hashtable *h, keytype *k) \ 202 { \ 203 return (valuetype *) (hashtable_search(h,k)); \ 204 } 205 206 /***************************************************************************** 207 * hashtable_remove 208 209 * @name hashtable_remove 210 * @param h the hashtable to remove the item from 211 * @param k the key to search for - does not claim ownership 212 * @return the value associated with the key, or NULL if none found 213 */ 214 215 void * /* returns value */ 216 hashtable_remove(struct hashtable *h, void *k); 217 218 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \ 219 valuetype * fnname (struct hashtable *h, keytype *k) \ 220 { \ 221 return (valuetype *) (hashtable_remove(h,k)); \ 222 } 223 224 225 /***************************************************************************** 226 * hashtable_count 227 228 * @name hashtable_count 229 * @return the number of items stored in the hashtable 230 */ 231 unsigned int 232 hashtable_count(struct hashtable *h); 233 234 235 /***************************************************************************** 236 * hashtable_destroy 237 238 * @name hashtable_destroy 239 * @param free_values whether to call 'free' on the remaining values 240 */ 241 242 void 243 hashtable_destroy(struct hashtable *h, int free_values); 244 245 246 /*****************************************************************************/ 247 /* hashtable_iterator 248 */ 249 250 struct hashtable_itr * 251 hashtable_iterator(struct hashtable *h); 252 253 /*****************************************************************************/ 254 /* key - return the key of the (key,value) pair at the current position */ 255 256 void * 257 hashtable_iterator_key(struct hashtable_itr *i); 258 259 /*****************************************************************************/ 260 /* value - return the value of the (key,value) pair at the current position */ 261 262 void * 263 hashtable_iterator_value(struct hashtable_itr *i); 264 265 /*****************************************************************************/ 266 /* advance - advance the iterator to the next element 267 * returns zero if advanced to end of table */ 268 269 int 270 hashtable_iterator_advance(struct hashtable_itr *itr); 271 272 #endif 273