1 /***********************************************************
2 * Artsoft Retro-Game Library *
3 *----------------------------------------------------------*
4 * (c) 1994-2003 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;
52 /* Check requested hashtable isn't too large */
53 if (minsize > (1u << 31)) return NULL;
54 /* Enforce size as power of 2 */
55 while (size < minsize) size <<= 1;
56 h = (struct hashtable *)malloc(sizeof(struct hashtable));
57 if (NULL == h) return NULL; /*oom*/
58 h->table = (struct entry **)malloc(sizeof(struct entry*) * size);
59 if (NULL == h->table) { free(h); return NULL; } /*oom*/
60 for (i=0;i<size;i++) { h->table[i] = NULL; }
61 h->tablelength = size;
65 h->loadlimit = (unsigned int) ((float)size * maxloadfactor);
69 /*****************************************************************************/
71 hash(struct hashtable *h, void *k)
73 /* Aim to protect against poor hash functions by adding logic here
74 * - logic taken from java 1.4 hashtable source */
75 unsigned int i = h->hashfn(k);
77 i ^= ((i >> 14) | (i << 18)); /* >>> */
79 i ^= ((i >> 10) | (i << 22)); /* >>> */
82 /*****************************************************************************/
84 indexFor(unsigned int tablelength, unsigned int hashvalue)
86 /* Only works if tablelength == 2^N */
87 return (hashvalue & (tablelength - 1u));
90 /*****************************************************************************/
92 hashtable_expand(struct hashtable *h)
94 /* Double the size of the table to accomodate more entries */
95 struct entry **newtable;
98 unsigned int newsize, i, index;
99 /* Check we're not hitting max capacity */
100 if (0 == (newsize = (h->tablelength << 1))) return 0;
102 newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize);
103 if (NULL != newtable)
105 memset(newtable, 0, newsize * sizeof(struct entry *));
106 /* This algorithm is not 'stable'. ie. it reverses the list
107 * when it transfers entries between the tables */
108 for (i = 0; i < h->tablelength; i++) {
109 while (NULL != (e = h->table[i])) {
110 h->table[i] = e->next;
111 index = indexFor(newsize,e->h);
112 e->next = newtable[index];
119 /* Plan B: realloc instead */
122 newtable = (struct entry **)
123 realloc(h->table, newsize * sizeof(struct entry *));
124 if (NULL == newtable) return 0;
126 for (i = h->tablelength; i < newsize; i++) {
129 for (i = 0; i < h->tablelength; i++) {
130 for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
131 index = indexFor(newsize,e->h);
139 e->next = newtable[index];
145 h->tablelength = newsize;
150 /*****************************************************************************/
152 hashtable_count(struct hashtable *h)
154 return h->entrycount;
157 /*****************************************************************************/
159 hashtable_insert(struct hashtable *h, void *k, void *v)
161 /* This method allows duplicate keys - but they shouldn't be used */
164 if (++(h->entrycount) > h->loadlimit)
166 /* Ignore the return value. If expand fails, we should
167 * still try cramming just this value into the existing table
168 * -- we may not have memory for a larger table, but one more
169 * element may be ok. Next time we insert, we'll try expanding again.*/
172 e = (struct entry *)malloc(sizeof(struct entry));
173 if (NULL == e) { --(h->entrycount); return 0; } /*oom*/
175 index = indexFor(h->tablelength,e->h);
178 e->next = h->table[index];
183 /*****************************************************************************/
185 hashtable_change(struct hashtable *h, void *k, void *v)
188 unsigned int hashvalue, index;
189 hashvalue = hash(h,k);
190 index = indexFor(h->tablelength,hashvalue);
194 /* Check hash value to short circuit heavier comparison */
195 if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
206 /*****************************************************************************/
207 void * /* returns value associated with key */
208 hashtable_search(struct hashtable *h, void *k)
211 unsigned int hashvalue, index;
212 hashvalue = hash(h,k);
213 index = indexFor(h->tablelength,hashvalue);
217 /* Check hash value to short circuit heavier comparison */
218 if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v;
224 /*****************************************************************************/
225 void * /* returns value associated with key */
226 hashtable_remove(struct hashtable *h, void *k)
228 /* TODO: consider compacting the table when the load factor drops enough,
229 * or provide a 'compact' method. */
235 unsigned int index = indexFor(h->tablelength,hash(h,k));
236 pE = &(h->table[index]);
240 if (h->eqfn(k, e->k))
255 /*****************************************************************************/
258 hashtable_destroy(struct hashtable *h, int free_values)
262 struct entry **table = h->table;
265 for (i = 0; i < h->tablelength; i++)
269 { f = e; e = e->next; free(f->k); free(f->v); free(f); }
274 for (i = 0; i < h->tablelength; i++)
278 { f = e; e = e->next; free(f->k); free(f); }
284 /*****************************************************************************/
285 /* hashtable_iterator - iterator constructor */
287 struct hashtable_itr *
288 hashtable_iterator(struct hashtable *h)
290 unsigned int i, tablelength;
291 struct hashtable_itr *itr = (struct hashtable_itr *)
292 malloc(sizeof(struct hashtable_itr));
293 if (NULL == itr) return NULL;
296 tablelength = h->tablelength;
297 itr->index = tablelength;
298 if (0 == h->entrycount) return itr;
300 for (i = 0; i < tablelength; i++)
302 if (NULL != h->table[i])
304 itr->e = h->table[i];
312 /*****************************************************************************/
313 /* key - return the key of the (key,value) pair at the current position */
316 hashtable_iterator_key(struct hashtable_itr *i)
321 /*****************************************************************************/
322 /* value - return the value of the (key,value) pair at the current position */
325 hashtable_iterator_value(struct hashtable_itr *i)
330 /*****************************************************************************/
331 /* advance - advance the iterator to the next element
332 * returns zero if advanced to end of table */
335 hashtable_iterator_advance(struct hashtable_itr *itr)
337 unsigned int j,tablelength;
338 struct entry **table;
340 if (NULL == itr->e) return 0; /* stupidity check */
348 tablelength = itr->h->tablelength;
349 if (tablelength <= (j = ++(itr->index)))
354 table = itr->h->table;
355 while (NULL == (next = table[j]))
357 if (++j >= tablelength)
359 itr->index = tablelength;