1 // ============================================================================
2 // Artsoft Retro-Game Library
3 // ----------------------------------------------------------------------------
4 // (c) 1995-2014 by Artsoft Entertainment
7 // https://www.artsoft.org/
8 // ----------------------------------------------------------------------------
10 // ============================================================================
13 * Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk>
15 * Permission is hereby granted, free of charge, to any person obtaining a copy
16 * of this software and associated documentation files (the "Software"), to
17 * deal in the Software without restriction, including without limitation the
18 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
19 * sell copies of the Software, and to permit persons to whom the Software is
20 * furnished to do so, subject to the following conditions:
22 * The above copyright notice and this permission notice shall be included in
23 * all copies of the Software and its documentation and acknowledgment shall be
24 * given in the documentation and software packages that this Software was
27 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
28 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
29 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
30 * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
31 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
32 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41 * struct hashtable *h;
43 * struct some_value *v;
45 * static unsigned int hash_from_key_fn( void *k );
46 * static int keys_equal_fn ( void *key1, void *key2 );
48 * h = create_hashtable(16, 0.75, hash_from_key_fn, keys_equal_fn, free, free);
49 * k = (struct some_key *) malloc(sizeof(struct some_key));
50 * v = (struct some_value *) malloc(sizeof(struct some_value));
52 * (initialise k and v to suitable values)
54 * if (! hashtable_insert(h,k,v) )
57 * if (NULL == (found = hashtable_search(h,k) ))
58 * { printf("not found!"); }
60 * if (NULL == (found = hashtable_remove(h,k) ))
61 * { printf("Not found\n"); }
65 /* Macros may be used to define type-safe(r) hashtable access functions, with
66 * methods specialized to take known key and value types as parameters.
70 * Insert this at the start of your file:
72 * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
73 * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
74 * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
76 * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
77 * These operate just like hashtable_insert etc., with the same parameters,
78 * but their function signatures have 'struct some_key *' rather than
79 * 'void *', and hence can generate compile time errors if your program is
80 * supplying incorrect data as a key (and similarly for value).
82 * Note that the hash and key equality functions passed to create_hashtable
83 * still take 'void *' parameters instead of 'some key *'. This shouldn't be
84 * a difficult issue as they're only defined and passed once, and the other
85 * functions will ensure that only valid keys are supplied to them.
87 * The cost for this checking is increased code size and runtime overhead
88 * - if performance is important, it may be worth switching back to the
89 * unsafe methods once your program has been debugged with the safe methods.
90 * This just requires switching to some simple alternative defines - eg:
91 * #define insert_some hashtable_insert
96 /*****************************************************************************/
106 unsigned int tablelength;
107 struct entry **table;
108 unsigned int entrycount;
109 unsigned int loadlimit;
110 unsigned int (*hashfn) (void *k);
111 int (*eqfn) (void *k1, void *k2);
112 void (*freekfn) (void *k);
113 void (*freevfn) (void *v);
116 /*****************************************************************************/
125 /*****************************************************************************
126 * create_hashtable_ext
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 * @param key_free_fn function for freeing keys
134 * @param value_free_fn function for freeing values
135 * @return newly created hashtable or NULL on failure
139 create_hashtable_ext(unsigned int minsize, float maxloadfactor,
140 unsigned int (*hashfunction) (void*),
141 int (*key_eq_fn) (void*, void*),
142 void (*key_free_fn) (void*),
143 void (*value_free_fn) (void*));
145 /* wrapper function using reasonable default values for some parameters */
147 create_hashtable(unsigned int (*hashfunction) (void*),
148 int (*key_eq_fn) (void*, void*),
149 void (*key_free_fn) (void*),
150 void (*value_free_fn) (void*));
152 /*****************************************************************************
155 * @name hashtable_insert
156 * @param h the hashtable to insert into
157 * @param k the key - will be freed on removal if free function defined
158 * @param v the value - will be freed on removal if free function defined
159 * @return non-zero for successful insertion
161 * This function will cause the table to expand if the insertion would take
162 * the ratio of entries to table size over the maximum load factor.
164 * This function does not check for repeated insertions with a duplicate key.
165 * The value returned when using a duplicate key is undefined -- when
166 * the hashtable changes size, the order of retrieval of duplicate key
167 * entries is reversed.
168 * If in doubt, remove before insert.
172 hashtable_insert(struct hashtable *h, void *k, void *v);
174 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
175 static int fnname (struct hashtable *h, keytype *k, valuetype *v) \
177 return hashtable_insert(h, k, v); \
180 /*****************************************************************************
183 * @name hashtable_change
184 * @param h the hashtable to search
185 * @param k the key of the entry to change
186 * @param v the new value
187 * @return non-zero for successful change
191 hashtable_change(struct hashtable *h, void *k, void *v);
193 #define DEFINE_HASHTABLE_CHANGE(fnname, keytype, valuetype) \
194 static int fnname (struct hashtable *h, keytype *k, valuetype *v) \
196 return hashtable_change(h, k, v); \
199 /*****************************************************************************
202 * @name hashtable_search
203 * @param h the hashtable to search
204 * @param k the key to search for
205 * @return the value associated with the key, or NULL if none found
209 hashtable_search(struct hashtable *h, void *k);
211 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
212 static valuetype * fnname (struct hashtable *h, keytype *k) \
214 return (valuetype *) (hashtable_search(h, k)); \
217 /*****************************************************************************
220 * @name hashtable_remove
221 * @param h the hashtable to remove the item from
222 * @param k the key to search for
223 * @return the value associated with the key, or NULL if none found
226 void * /* returns value */
227 hashtable_remove(struct hashtable *h, void *k);
229 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \
230 static valuetype * fnname (struct hashtable *h, keytype *k) \
232 return (valuetype *) (hashtable_remove(h, k)); \
236 /*****************************************************************************
239 * @name hashtable_count
240 * @return the number of items stored in the hashtable
243 hashtable_count(struct hashtable *h);
246 /*****************************************************************************
249 * @name hashtable_destroy
253 hashtable_destroy(struct hashtable *h);
256 /*****************************************************************************/
257 /* hashtable_iterator
260 struct hashtable_itr *
261 hashtable_iterator(struct hashtable *h);
263 /*****************************************************************************/
264 /* key - return the key of the (key, value) pair at the current position */
267 hashtable_iterator_key(struct hashtable_itr *i);
269 /*****************************************************************************/
270 /* value - return the value of the (key, value) pair at the current position */
273 hashtable_iterator_value(struct hashtable_itr *i);
275 /*****************************************************************************/
276 /* advance - advance the iterator to the next element
277 * returns zero if advanced to end of table */
280 hashtable_iterator_advance(struct hashtable_itr *itr);