cleanup of BD style game elements in level editor
[rocksndiamonds.git] / src / libgame / hash.c
1 // ============================================================================
2 // Artsoft Retro-Game Library
3 // ----------------------------------------------------------------------------
4 // (c) 1995-2014 by Artsoft Entertainment
5 //                  Holger Schemel
6 //                  info@artsoft.org
7 //                  https://www.artsoft.org/
8 // ----------------------------------------------------------------------------
9 // hash.c
10 // ============================================================================
11
12 /*
13  * Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk>
14  *
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:
21  *
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
25  * used.
26  *
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.
33  * */
34
35 #include <stdlib.h>
36 #include <stdio.h>
37 #include <string.h>
38
39 #include "hash.h"
40
41
42 /*****************************************************************************/
43 struct hashtable *
44 create_hashtable_ext(unsigned int minsize, float maxloadfactor,
45                      unsigned int (*hashf) (void*),
46                      int (*eqf) (void*, void*),
47                      void (*freekfn) (void*),
48                      void (*freevfn) (void*))
49 {
50   struct hashtable *h;
51   unsigned int i, size = 1u;
52
53   /* Check requested hashtable isn't too large */
54   if (minsize > (1u << 31))
55     return NULL;
56
57   /* Enforce size as power of 2 */
58   while (size < minsize)
59     size <<= 1;
60
61   h = (struct hashtable *)malloc(sizeof(struct hashtable));
62
63   if (h == NULL)
64     return NULL;
65
66   h->table = (struct entry **)malloc(sizeof(struct entry*) * size);
67
68   if (h->table == NULL)
69   {
70     free(h);
71
72     return NULL;
73   }
74
75   for (i = 0; i < size; i++)
76     h->table[i] = NULL;
77
78   h->tablelength  = size;
79   h->entrycount   = 0;
80   h->hashfn       = hashf;
81   h->eqfn         = eqf;
82   h->loadlimit    = (unsigned int) ((float)size * maxloadfactor);
83   h->freekfn      = freekfn;
84   h->freevfn      = freevfn;
85
86   return h;
87 }
88
89 struct hashtable *
90 create_hashtable(unsigned int (*hashf) (void*),
91                  int (*eqf) (void*, void*),
92                  void (*freekfn) (void*),
93                  void (*freevfn) (void*))
94 {
95   return create_hashtable_ext(16, 0.75, hashf, eqf, freekfn, freevfn);
96 }
97
98 /*****************************************************************************/
99 static unsigned int
100 hash(struct hashtable *h, void *k)
101 {
102   /* Aim to protect against poor hash functions by adding logic here
103    * - logic taken from java 1.4 hashtable source */
104
105   unsigned int i = h->hashfn(k);
106
107   i += ~(i << 9);
108   i ^=  ((i >> 14) | (i << 18)); /* >>> */
109   i +=  (i << 4);
110   i ^=  ((i >> 10) | (i << 22)); /* >>> */
111
112   return i;
113 }
114
115 /*****************************************************************************/
116 static unsigned int
117 indexFor(unsigned int tablelength, unsigned int hashvalue)
118 {
119   /* Only works if tablelength == 2^N */
120   return (hashvalue & (tablelength - 1u));
121 }
122
123 /*****************************************************************************/
124 static int
125 hashtable_expand(struct hashtable *h)
126 {
127   /* Double the size of the table to accomodate more entries */
128   struct entry **newtable;
129   struct entry *e;
130   struct entry **pE;
131   unsigned int newsize, i, index;
132
133   /* Check we're not hitting max capacity */
134   if (0 == (newsize = (h->tablelength << 1)))
135     return 0;
136
137   newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize);
138
139   if (newtable != NULL)
140   {
141     memset(newtable, 0, newsize * sizeof(struct entry *));
142
143     /* This algorithm is not 'stable'. ie. it reverses the list
144      * when it transfers entries between the tables */
145     for (i = 0; i < h->tablelength; i++)
146     {
147       while ((e = h->table[i]) != NULL)
148       {
149         h->table[i] = e->next;
150         index = indexFor(newsize, e->h);
151         e->next = newtable[index];
152         newtable[index] = e;
153       }
154     }
155
156     free(h->table);
157     h->table = newtable;
158   }
159   else          /* Plan B: realloc instead */
160   {
161     newtable = (struct entry **)
162       realloc(h->table, newsize * sizeof(struct entry *));
163
164     if (newtable == NULL)
165       return 0;
166
167     h->table = newtable;
168
169     for (i = h->tablelength; i < newsize; i++)
170       newtable[i] = NULL;
171
172     for (i = 0; i < h->tablelength; i++)
173     {
174       for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE)
175       {
176         index = indexFor(newsize, e->h);
177
178         if (index == i)
179         {
180           pE = &(e->next);
181         }
182         else
183         {
184           *pE = e->next;
185           e->next = newtable[index];
186           newtable[index] = e;
187         }
188       }
189     }
190   }
191
192   h->tablelength = newsize;
193   h->loadlimit <<= 1;
194
195   return -1;
196 }
197
198 /*****************************************************************************/
199 unsigned int
200 hashtable_count(struct hashtable *h)
201 {
202   return h->entrycount;
203 }
204
205 /*****************************************************************************/
206 int
207 hashtable_insert(struct hashtable *h, void *k, void *v)
208 {
209   /* This method allows duplicate keys - but they shouldn't be used */
210   unsigned int index;
211   struct entry *e;
212
213   if (++(h->entrycount) > h->loadlimit)
214   {
215     /* Ignore the return value. If expand fails, we should
216      * still try cramming just this value into the existing table
217      * -- we may not have memory for a larger table, but one more
218      * element may be ok. Next time we insert, we'll try expanding again.*/
219
220     hashtable_expand(h);
221   }
222
223   e = (struct entry *)malloc(sizeof(struct entry));
224
225   if (e == NULL)
226   {
227     --(h->entrycount);
228
229     return 0;
230   }
231
232   e->h = hash(h, k);
233   index = indexFor(h->tablelength, e->h);
234   e->k = k;
235   e->v = v;
236   e->next = h->table[index];
237   h->table[index] = e;
238
239   return -1;
240 }
241
242 /*****************************************************************************/
243 int
244 hashtable_change(struct hashtable *h, void *k, void *v)
245 {
246   struct entry *e;
247   unsigned int hashvalue, index;
248
249   hashvalue = hash(h, k);
250   index = indexFor(h->tablelength, hashvalue);
251   e = h->table[index];
252
253   while (e != NULL)
254   {
255     /* Check hash value to short circuit heavier comparison */
256     if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
257     {
258       if (h->freevfn != NULL)
259         h->freevfn(e->v);
260       e->v = v;
261
262       return -1;
263     }
264
265     e = e->next;
266   }
267
268   return 0;
269 }
270
271 /*****************************************************************************/
272 int /* checks if key exists */
273 hashtable_exists(struct hashtable *h, void *k)
274 {
275   struct entry *e;
276   unsigned int hashvalue, index;
277
278   hashvalue = hash(h, k);
279   index = indexFor(h->tablelength, hashvalue);
280   e = h->table[index];
281
282   while (e != NULL)
283   {
284     /* Check hash value to short circuit heavier comparison */
285     if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
286       return 1;
287
288     e = e->next;
289   }
290
291   return 0;
292 }
293
294 /*****************************************************************************/
295 void * /* returns value associated with key */
296 hashtable_search(struct hashtable *h, void *k)
297 {
298   struct entry *e;
299   unsigned int hashvalue, index;
300
301   hashvalue = hash(h, k);
302   index = indexFor(h->tablelength, hashvalue);
303   e = h->table[index];
304
305   while (e != NULL)
306   {
307     /* Check hash value to short circuit heavier comparison */
308     if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
309       return e->v;
310
311     e = e->next;
312   }
313
314   return NULL;
315 }
316
317 /*****************************************************************************/
318 void * /* returns value associated with key */
319 hashtable_remove(struct hashtable *h, void *k)
320 {
321   /* TODO: consider compacting the table when the load factor drops enough,
322    *       or provide a 'compact' method. */
323
324   struct entry *e;
325   struct entry **pE;
326   void *v;
327   unsigned int index = indexFor(h->tablelength, hash(h, k));
328
329   pE = &(h->table[index]);
330   e = *pE;
331
332   while (e != NULL)
333   {
334     if (h->eqfn(k, e->k))
335     {
336       *pE = e->next;
337       h->entrycount--;
338       v = NULL;
339       if (h->freekfn != NULL)
340         h->freekfn(e->k);
341       if (h->freevfn != NULL)
342         h->freevfn(e->v);
343       else
344         v = e->v;
345       free(e);
346
347       return v;
348     }
349
350     pE = &(e->next);
351     e = e->next;
352   }
353
354   return NULL;
355 }
356
357 /*****************************************************************************/
358 /* destroy */
359 void
360 hashtable_destroy(struct hashtable *h)
361 {
362   unsigned int i;
363   struct entry *e, *f;
364   struct entry **table = h->table;
365
366   for (i = 0; i < h->tablelength; i++)
367   {
368     e = table[i];
369
370     while (e != NULL)
371     {
372       f = e;
373       e = e->next;
374       if (h->freekfn != NULL)
375         h->freekfn(f->k);
376       if (h->freevfn != NULL)
377         h->freevfn(f->v);
378
379       free(f);
380     }
381   }
382
383   free(h->table);
384   free(h);
385 }
386
387 /*****************************************************************************/
388 /* hashtable_iterator    - iterator constructor */
389
390 struct hashtable_itr *
391 hashtable_iterator(struct hashtable *h)
392 {
393   unsigned int i, tablelength;
394   struct hashtable_itr *itr = (struct hashtable_itr *)
395     malloc(sizeof(struct hashtable_itr));
396
397   if (itr == NULL)
398     return NULL;
399
400   itr->h = h;
401   itr->e = NULL;
402   tablelength = h->tablelength;
403   itr->index = tablelength;
404
405   if (0 == h->entrycount)
406     return itr;
407
408   for (i = 0; i < tablelength; i++)
409   {
410     if (h->table[i] != NULL)
411     {
412       itr->e = h->table[i];
413       itr->index = i;
414
415       break;
416     }
417   }
418
419   return itr;
420 }
421
422 /*****************************************************************************/
423 /* key - return the key of the (key, value) pair at the current position */
424
425 void *
426 hashtable_iterator_key(struct hashtable_itr *itr)
427 {
428   if (itr == NULL || itr->e == NULL)
429     return NULL;
430
431   return itr->e->k;
432 }
433
434 /*****************************************************************************/
435 /* value - return the value of the (key, value) pair at the current position */
436
437 void *
438 hashtable_iterator_value(struct hashtable_itr *itr)
439 {
440   if (itr == NULL || itr->e == NULL)
441     return NULL;
442
443   return itr->e->v;
444 }
445
446 /*****************************************************************************/
447 /* advance - advance the iterator to the next element
448  *           returns zero if advanced to end of table */
449
450 int
451 hashtable_iterator_advance(struct hashtable_itr *itr)
452 {
453   unsigned int j, tablelength;
454   struct entry **table;
455   struct entry *next;
456
457   if (itr->e == NULL)
458     return 0; /* stupidity check */
459
460   next = itr->e->next;
461   if (next != NULL)
462   {
463     itr->e = next;
464
465     return -1;
466   }
467
468   tablelength = itr->h->tablelength;
469   if (tablelength <= (j = ++(itr->index)))
470   {
471     itr->e = NULL;
472
473     return 0;
474   }
475
476   table = itr->h->table;
477   while ((next = table[j]) == NULL)
478   {
479     if (++j >= tablelength)
480     {
481       itr->index = tablelength;
482
483       return 0;
484     }
485   }
486
487   itr->index = j;
488   itr->e = next;
489
490   return -1;
491 }
492
493 /*****************************************************************************/
494 /* call function for all hashtable entries */
495 void
496 hashtable_foreach(struct hashtable *h, hashtable_fn fn, void *userdata)
497 {
498   if (h == NULL)
499     return;
500
501   if (hashtable_count(h) == 0)
502     return;
503
504   struct hashtable_itr *itr = hashtable_iterator(h);
505
506   do
507   {
508     fn(hashtable_iterator_key(itr), hashtable_iterator_value(itr), userdata);
509   }
510   while (hashtable_iterator_advance(itr));
511
512   free(itr);
513 }
514
515 /*****************************************************************************/
516 /* call function for all hashtable entries and remove them, if function returned 1 */
517 unsigned int
518 hashtable_foreach_remove(struct hashtable *h, hashtable_remove_fn fn, void *userdata)
519 {
520   if (h == NULL)
521     return 0;
522
523   if (hashtable_count(h) == 0)
524     return 0;
525
526   struct hashtable *remove = create_hashtable(h->hashfn, h->eqfn, NULL, NULL);
527   struct hashtable_itr *itr = hashtable_iterator(h);
528
529   do
530   {
531     if (fn(hashtable_iterator_key(itr), hashtable_iterator_value(itr), userdata))
532       hashtable_insert(remove, hashtable_iterator_key(itr), "1");
533   }
534   while (hashtable_iterator_advance(itr));
535
536   free(itr);
537
538   unsigned int num_removed = 0;
539
540   if (hashtable_count(remove) > 0)
541   {
542     struct hashtable_itr *itr_remove = hashtable_iterator(remove);
543
544     do
545     {
546       hashtable_remove(h, hashtable_iterator_key(itr_remove));
547       num_removed++;
548     }
549     while (hashtable_iterator_advance(itr_remove));
550
551     free(itr_remove);
552   }
553
554   hashtable_destroy(remove);
555
556   return num_removed;
557 }
558
559 /*****************************************************************************/
560 /* remove_all hashtable entries */
561 unsigned int
562 hashtable_remove_all(struct hashtable *h)
563 {
564   /* TODO: this function should directly remove all hashtable entries */
565
566   if (h == NULL)
567     return 0;
568
569   if (hashtable_count(h) == 0)
570     return 0;
571
572   struct hashtable *remove = create_hashtable(h->hashfn, h->eqfn, NULL, NULL);
573   struct hashtable_itr *itr = hashtable_iterator(h);
574
575   do
576   {
577     hashtable_insert(remove, hashtable_iterator_key(itr), "1");
578   }
579   while (hashtable_iterator_advance(itr));
580
581   free(itr);
582
583   struct hashtable_itr *itr_remove = hashtable_iterator(remove);
584   unsigned int num_removed = 0;
585
586   do
587   {
588     hashtable_remove(h, hashtable_iterator_key(itr_remove));
589     num_removed++;
590   }
591   while (hashtable_iterator_advance(itr_remove));
592
593   free(itr_remove);
594
595   hashtable_destroy(remove);
596
597   return num_removed;
598 }