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.
44 /*****************************************************************************/
46 create_hashtable(unsigned int minsize, float maxloadfactor,
47 unsigned int (*hashf) (void*),
48 int (*eqf) (void*,void*))
51 unsigned int i, size = 1u;
53 /* Check requested hashtable isn't too large */
54 if (minsize > (1u << 31))
57 /* Enforce size as power of 2 */
58 while (size < minsize)
61 h = (struct hashtable *)malloc(sizeof(struct hashtable));
66 h->table = (struct entry **)malloc(sizeof(struct entry*) * size);
75 for (i=0; i < size; i++)
78 h->tablelength = size;
82 h->loadlimit = (unsigned int) ((float)size * maxloadfactor);
87 /*****************************************************************************/
89 hash(struct hashtable *h, void *k)
91 /* Aim to protect against poor hash functions by adding logic here
92 * - logic taken from java 1.4 hashtable source */
94 unsigned int i = h->hashfn(k);
97 i ^= ((i >> 14) | (i << 18)); /* >>> */
99 i ^= ((i >> 10) | (i << 22)); /* >>> */
104 /*****************************************************************************/
106 indexFor(unsigned int tablelength, unsigned int hashvalue)
108 /* Only works if tablelength == 2^N */
109 return (hashvalue & (tablelength - 1u));
112 /*****************************************************************************/
114 hashtable_expand(struct hashtable *h)
116 /* Double the size of the table to accomodate more entries */
117 struct entry **newtable;
120 unsigned int newsize, i, index;
122 /* Check we're not hitting max capacity */
123 if (0 == (newsize = (h->tablelength << 1)))
126 newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize);
128 if (newtable != NULL)
130 memset(newtable, 0, newsize * sizeof(struct entry *));
132 /* This algorithm is not 'stable'. ie. it reverses the list
133 * when it transfers entries between the tables */
134 for (i = 0; i < h->tablelength; i++)
136 while ((e = h->table[i]) != NULL)
138 h->table[i] = e->next;
139 index = indexFor(newsize,e->h);
140 e->next = newtable[index];
148 else /* Plan B: realloc instead */
150 newtable = (struct entry **)
151 realloc(h->table, newsize * sizeof(struct entry *));
153 if (newtable == NULL)
158 for (i = h->tablelength; i < newsize; i++)
161 for (i = 0; i < h->tablelength; i++)
163 for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE)
165 index = indexFor(newsize,e->h);
174 e->next = newtable[index];
181 h->tablelength = newsize;
187 /*****************************************************************************/
189 hashtable_count(struct hashtable *h)
191 return h->entrycount;
194 /*****************************************************************************/
196 hashtable_insert(struct hashtable *h, void *k, void *v)
198 /* This method allows duplicate keys - but they shouldn't be used */
202 if (++(h->entrycount) > h->loadlimit)
204 /* Ignore the return value. If expand fails, we should
205 * still try cramming just this value into the existing table
206 * -- we may not have memory for a larger table, but one more
207 * element may be ok. Next time we insert, we'll try expanding again.*/
212 e = (struct entry *)malloc(sizeof(struct entry));
222 index = indexFor(h->tablelength,e->h);
225 e->next = h->table[index];
231 /*****************************************************************************/
233 hashtable_change(struct hashtable *h, void *k, void *v)
236 unsigned int hashvalue, index;
238 hashvalue = hash(h,k);
239 index = indexFor(h->tablelength,hashvalue);
244 /* Check hash value to short circuit heavier comparison */
245 if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
259 /*****************************************************************************/
260 void * /* returns value associated with key */
261 hashtable_search(struct hashtable *h, void *k)
264 unsigned int hashvalue, index;
266 hashvalue = hash(h,k);
267 index = indexFor(h->tablelength,hashvalue);
272 /* Check hash value to short circuit heavier comparison */
273 if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
282 /*****************************************************************************/
283 void * /* returns value associated with key */
284 hashtable_remove(struct hashtable *h, void *k)
286 /* TODO: consider compacting the table when the load factor drops enough,
287 * or provide a 'compact' method. */
292 unsigned int index = indexFor(h->tablelength,hash(h,k));
294 pE = &(h->table[index]);
299 if (h->eqfn(k, e->k))
317 /*****************************************************************************/
320 hashtable_destroy(struct hashtable *h, int free_values)
324 struct entry **table = h->table;
326 for (i = 0; i < h->tablelength; i++)
348 /*****************************************************************************/
349 /* hashtable_iterator - iterator constructor */
351 struct hashtable_itr *
352 hashtable_iterator(struct hashtable *h)
354 unsigned int i, tablelength;
355 struct hashtable_itr *itr = (struct hashtable_itr *)
356 malloc(sizeof(struct hashtable_itr));
363 tablelength = h->tablelength;
364 itr->index = tablelength;
366 if (0 == h->entrycount)
369 for (i = 0; i < tablelength; i++)
371 if (h->table[i] != NULL)
373 itr->e = h->table[i];
383 /*****************************************************************************/
384 /* key - return the key of the (key,value) pair at the current position */
387 hashtable_iterator_key(struct hashtable_itr *i)
392 /*****************************************************************************/
393 /* value - return the value of the (key,value) pair at the current position */
396 hashtable_iterator_value(struct hashtable_itr *i)
401 /*****************************************************************************/
402 /* advance - advance the iterator to the next element
403 * returns zero if advanced to end of table */
406 hashtable_iterator_advance(struct hashtable_itr *itr)
408 unsigned int j,tablelength;
409 struct entry **table;
413 return 0; /* stupidity check */
423 tablelength = itr->h->tablelength;
424 if (tablelength <= (j = ++(itr->index)))
431 table = itr->h->table;
432 while ((next = table[j]) == NULL)
434 if (++j >= tablelength)
436 itr->index = tablelength;