added checking for invalid/malicious filenames in network protocol
[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 //                  http://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(unsigned int minsize, float maxloadfactor,
45                  unsigned int (*hashf) (void*),
46                  int (*eqf) (void*,void*))
47 {
48   struct hashtable *h;
49   unsigned int i, size = 1u;
50
51   /* Check requested hashtable isn't too large */
52   if (minsize > (1u << 31))
53     return NULL;
54
55   /* Enforce size as power of 2 */
56   while (size < minsize)
57     size <<= 1;
58
59   h = (struct hashtable *)malloc(sizeof(struct hashtable));
60
61   if (h == NULL)
62     return NULL;
63
64   h->table = (struct entry **)malloc(sizeof(struct entry*) * size);
65
66   if (h->table == NULL)
67   {
68     free(h);
69
70     return NULL;
71   }
72
73   for (i=0; i < size; i++)
74     h->table[i] = NULL;
75
76   h->tablelength  = size;
77   h->entrycount   = 0;
78   h->hashfn       = hashf;
79   h->eqfn         = eqf;
80   h->loadlimit    = (unsigned int) ((float)size * maxloadfactor);
81
82   return h;
83 }
84
85 /*****************************************************************************/
86 static unsigned int
87 hash(struct hashtable *h, void *k)
88 {
89   /* Aim to protect against poor hash functions by adding logic here
90    * - logic taken from java 1.4 hashtable source */
91
92   unsigned int i = h->hashfn(k);
93
94   i += ~(i << 9);
95   i ^=  ((i >> 14) | (i << 18)); /* >>> */
96   i +=  (i << 4);
97   i ^=  ((i >> 10) | (i << 22)); /* >>> */
98
99   return i;
100 }
101
102 /*****************************************************************************/
103 static unsigned int
104 indexFor(unsigned int tablelength, unsigned int hashvalue)
105 {
106   /* Only works if tablelength == 2^N */
107   return (hashvalue & (tablelength - 1u));
108 }
109
110 /*****************************************************************************/
111 static int
112 hashtable_expand(struct hashtable *h)
113 {
114   /* Double the size of the table to accomodate more entries */
115   struct entry **newtable;
116   struct entry *e;
117   struct entry **pE;
118   unsigned int newsize, i, index;
119
120   /* Check we're not hitting max capacity */
121   if (0 == (newsize = (h->tablelength << 1)))
122     return 0;
123
124   newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize);
125
126   if (newtable != NULL)
127   {
128     memset(newtable, 0, newsize * sizeof(struct entry *));
129
130     /* This algorithm is not 'stable'. ie. it reverses the list
131      * when it transfers entries between the tables */
132     for (i = 0; i < h->tablelength; i++)
133     {
134       while ((e = h->table[i]) != NULL)
135       {
136         h->table[i] = e->next;
137         index = indexFor(newsize,e->h);
138         e->next = newtable[index];
139         newtable[index] = e;
140       }
141     }
142
143     free(h->table);
144     h->table = newtable;
145   }
146   else          /* Plan B: realloc instead */
147   {
148     newtable = (struct entry **)
149       realloc(h->table, newsize * sizeof(struct entry *));
150
151     if (newtable == NULL)
152       return 0;
153
154     h->table = newtable;
155
156     for (i = h->tablelength; i < newsize; i++)
157       newtable[i] = NULL;
158
159     for (i = 0; i < h->tablelength; i++)
160     {
161       for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE)
162       {
163         index = indexFor(newsize,e->h);
164
165         if (index == i)
166         {
167           pE = &(e->next);
168         }
169         else
170         {
171           *pE = e->next;
172           e->next = newtable[index];
173           newtable[index] = e;
174         }
175       }
176     }
177   }
178
179   h->tablelength = newsize;
180   h->loadlimit <<= 1;
181
182   return -1;
183 }
184
185 /*****************************************************************************/
186 unsigned int
187 hashtable_count(struct hashtable *h)
188 {
189   return h->entrycount;
190 }
191
192 /*****************************************************************************/
193 int
194 hashtable_insert(struct hashtable *h, void *k, void *v)
195 {
196   /* This method allows duplicate keys - but they shouldn't be used */
197   unsigned int index;
198   struct entry *e;
199
200   if (++(h->entrycount) > h->loadlimit)
201   {
202     /* Ignore the return value. If expand fails, we should
203      * still try cramming just this value into the existing table
204      * -- we may not have memory for a larger table, but one more
205      * element may be ok. Next time we insert, we'll try expanding again.*/
206
207     hashtable_expand(h);
208   }
209
210   e = (struct entry *)malloc(sizeof(struct entry));
211
212   if (e == NULL)
213   {
214     --(h->entrycount);
215
216     return 0;
217   }
218
219   e->h = hash(h,k);
220   index = indexFor(h->tablelength,e->h);
221   e->k = k;
222   e->v = v;
223   e->next = h->table[index];
224   h->table[index] = e;
225
226   return -1;
227 }
228
229 /*****************************************************************************/
230 int
231 hashtable_change(struct hashtable *h, void *k, void *v)
232 {
233   struct entry *e;
234   unsigned int hashvalue, index;
235
236   hashvalue = hash(h,k);
237   index = indexFor(h->tablelength,hashvalue);
238   e = h->table[index];
239
240   while (e != NULL)
241   {
242     /* Check hash value to short circuit heavier comparison */
243     if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
244     {
245       free(e->v);
246       e->v = v;
247
248       return -1;
249     }
250
251     e = e->next;
252   }
253
254   return 0;
255 }
256
257 /*****************************************************************************/
258 void * /* returns value associated with key */
259 hashtable_search(struct hashtable *h, void *k)
260 {
261   struct entry *e;
262   unsigned int hashvalue, index;
263
264   hashvalue = hash(h,k);
265   index = indexFor(h->tablelength,hashvalue);
266   e = h->table[index];
267
268   while (e != NULL)
269   {
270     /* Check hash value to short circuit heavier comparison */
271     if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
272       return e->v;
273
274     e = e->next;
275   }
276
277   return NULL;
278 }
279
280 /*****************************************************************************/
281 void * /* returns value associated with key */
282 hashtable_remove(struct hashtable *h, void *k)
283 {
284   /* TODO: consider compacting the table when the load factor drops enough,
285    *       or provide a 'compact' method. */
286
287   struct entry *e;
288   struct entry **pE;
289   void *v;
290   unsigned int index = indexFor(h->tablelength,hash(h,k));
291
292   pE = &(h->table[index]);
293   e = *pE;
294
295   while (e != NULL)
296   {
297     if (h->eqfn(k, e->k))
298     {
299       *pE = e->next;
300       h->entrycount--;
301       v = e->v;
302       free(e->k);
303       free(e);
304
305       return v;
306     }
307
308     pE = &(e->next);
309     e = e->next;
310   }
311
312   return NULL;
313 }
314
315 /*****************************************************************************/
316 /* destroy */
317 void
318 hashtable_destroy(struct hashtable *h, int free_values)
319 {
320   unsigned int i;
321   struct entry *e, *f;
322   struct entry **table = h->table;
323
324   for (i = 0; i < h->tablelength; i++)
325   {
326     e = table[i];
327
328     while (e != NULL)
329     {
330       f = e;
331       e = e->next;
332       free(f->k);
333
334       if (free_values)
335         free(f->v);
336
337       free(f);
338     }
339   }
340
341   free(h->table);
342   free(h);
343 }
344
345
346 /*****************************************************************************/
347 /* hashtable_iterator    - iterator constructor */
348
349 struct hashtable_itr *
350 hashtable_iterator(struct hashtable *h)
351 {
352   unsigned int i, tablelength;
353   struct hashtable_itr *itr = (struct hashtable_itr *)
354     malloc(sizeof(struct hashtable_itr));
355
356   if (itr == NULL)
357     return NULL;
358
359   itr->h = h;
360   itr->e = NULL;
361   tablelength = h->tablelength;
362   itr->index = tablelength;
363
364   if (0 == h->entrycount)
365     return itr;
366
367   for (i = 0; i < tablelength; i++)
368   {
369     if (h->table[i] != NULL)
370     {
371       itr->e = h->table[i];
372       itr->index = i;
373
374       break;
375     }
376   }
377
378   return itr;
379 }
380
381 /*****************************************************************************/
382 /* key - return the key of the (key,value) pair at the current position */
383
384 void *
385 hashtable_iterator_key(struct hashtable_itr *i)
386 {
387   return i->e->k;
388 }
389
390 /*****************************************************************************/
391 /* value - return the value of the (key,value) pair at the current position */
392
393 void *
394 hashtable_iterator_value(struct hashtable_itr *i)
395 {
396   return i->e->v;
397 }
398
399 /*****************************************************************************/
400 /* advance - advance the iterator to the next element
401  *           returns zero if advanced to end of table */
402
403 int
404 hashtable_iterator_advance(struct hashtable_itr *itr)
405 {
406   unsigned int j,tablelength;
407   struct entry **table;
408   struct entry *next;
409
410   if (itr->e == NULL)
411     return 0; /* stupidity check */
412
413   next = itr->e->next;
414   if (next != NULL)
415   {
416     itr->e = next;
417
418     return -1;
419   }
420
421   tablelength = itr->h->tablelength;
422   if (tablelength <= (j = ++(itr->index)))
423   {
424     itr->e = NULL;
425
426     return 0;
427   }
428
429   table = itr->h->table;
430   while ((next = table[j]) == NULL)
431   {
432     if (++j >= tablelength)
433     {
434       itr->index = tablelength;
435
436       return 0;
437     }
438   }
439
440   itr->index = j;
441   itr->e = next;
442
443   return -1;
444 }