1 /***********************************************************
2 * Artsoft Retro-Game Library *
3 *----------------------------------------------------------*
4 * (c) 1994-2006 Artsoft Entertainment *
6 * Detmolder Strasse 189 *
9 * e-mail: info@artsoft.org *
10 *----------------------------------------------------------*
12 ***********************************************************/
15 * Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk>
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:
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
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.
43 * struct hashtable *h;
45 * struct some_value *v;
47 * static unsigned int hash_from_key_fn( void *k );
48 * static int keys_equal_fn ( void *key1, void *key2 );
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));
54 * (initialise k and v to suitable values)
56 * if (! hashtable_insert(h,k,v) )
59 * if (NULL == (found = hashtable_search(h,k) ))
60 * { printf("not found!"); }
62 * if (NULL == (found = hashtable_remove(h,k) ))
63 * { printf("Not found\n"); }
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.
72 * Insert this at the start of your file:
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);
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).
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.
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
98 /*****************************************************************************/
107 unsigned int tablelength;
108 struct entry **table;
109 unsigned int entrycount;
110 unsigned int loadlimit;
111 unsigned int (*hashfn) (void *k);
112 int (*eqfn) (void *k1, void *k2);
115 /*****************************************************************************/
124 /*****************************************************************************
127 * @name create_hashtable
128 * @param minsize minimum initial size of hashtable
129 * @param maxloadfactor maximum ratio entries / tablesize
130 * @param hashfunction function for hashing keys
131 * @param key_eq_fn function for determining key equality
132 * @return newly created hashtable or NULL on failure
136 create_hashtable(unsigned int minsize, float maxloadfactor,
137 unsigned int (*hashfunction) (void*),
138 int (*key_eq_fn) (void*,void*));
140 /*****************************************************************************
143 * @name hashtable_insert
144 * @param h the hashtable to insert into
145 * @param k the key - hashtable claims ownership and will free on removal
146 * @param v the value - does not claim ownership
147 * @return non-zero for successful insertion
149 * This function will cause the table to expand if the insertion would take
150 * the ratio of entries to table size over the maximum load factor.
152 * This function does not check for repeated insertions with a duplicate key.
153 * The value returned when using a duplicate key is undefined -- when
154 * the hashtable changes size, the order of retrieval of duplicate key
155 * entries is reversed.
156 * If in doubt, remove before insert.
160 hashtable_insert(struct hashtable *h, void *k, void *v);
162 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
163 int fnname (struct hashtable *h, keytype *k, valuetype *v) \
165 return hashtable_insert(h,k,v); \
168 /*****************************************************************************
171 * @name hashtable_change
172 * @param h the hashtable to search
173 * @param k the key of the entry to change
174 * @param v the new value
175 * @return non-zero for successful change
179 hashtable_change(struct hashtable *h, void *k, void *v);
181 #define DEFINE_HASHTABLE_CHANGE(fnname, keytype, valuetype) \
182 int fnname (struct hashtable *h, keytype *k, valuetype *v) \
184 return hashtable_change(h,k,v); \
187 /*****************************************************************************
190 * @name hashtable_search
191 * @param h the hashtable to search
192 * @param k the key to search for - does not claim ownership
193 * @return the value associated with the key, or NULL if none found
197 hashtable_search(struct hashtable *h, void *k);
199 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
200 valuetype * fnname (struct hashtable *h, keytype *k) \
202 return (valuetype *) (hashtable_search(h,k)); \
205 /*****************************************************************************
208 * @name hashtable_remove
209 * @param h the hashtable to remove the item from
210 * @param k the key to search for - does not claim ownership
211 * @return the value associated with the key, or NULL if none found
214 void * /* returns value */
215 hashtable_remove(struct hashtable *h, void *k);
217 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \
218 valuetype * fnname (struct hashtable *h, keytype *k) \
220 return (valuetype *) (hashtable_remove(h,k)); \
224 /*****************************************************************************
227 * @name hashtable_count
228 * @return the number of items stored in the hashtable
231 hashtable_count(struct hashtable *h);
234 /*****************************************************************************
237 * @name hashtable_destroy
238 * @param free_values whether to call 'free' on the remaining values
242 hashtable_destroy(struct hashtable *h, int free_values);
245 /*****************************************************************************/
246 /* hashtable_iterator
249 struct hashtable_itr *
250 hashtable_iterator(struct hashtable *h);
252 /*****************************************************************************/
253 /* hashtable_iterator_key
254 * - return the value of the (key,value) pair at the current position */
257 hashtable_iterator_key(struct hashtable_itr *i)
262 /*****************************************************************************/
263 /* value - return the value of the (key,value) pair at the current position */
266 hashtable_iterator_value(struct hashtable_itr *i)
271 /*****************************************************************************/
272 /* advance - advance the iterator to the next element
273 * returns zero if advanced to end of table */
276 hashtable_iterator_advance(struct hashtable_itr *itr);