c3b3a3e348c4748c24b0a732a40a870d9ef2705f
[blender.git] / source / blender / blenlib / intern / BLI_ghash.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  * A general (pointer -> pointer) hash table ADT
27  */
28
29 /** \file blender/blenlib/intern/BLI_ghash.c
30  *  \ingroup bli
31  */
32
33 #include <string.h>
34 #include <stdlib.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "BLI_utildefines.h"
39 #include "BLI_mempool.h"
40 #include "BLI_ghash.h"
41
42 #include "MEM_sys_types.h"  /* for intptr_t support */
43 /***/
44
45 unsigned int hashsizes[] = {
46         5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 
47         16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 
48         4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 
49         268435459
50 };
51
52 /***/
53
54 GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
55 {
56         GHash *gh = MEM_mallocN(sizeof(*gh), info);
57         gh->hashfp = hashfp;
58         gh->cmpfp = cmpfp;
59         gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, 0);
60
61         gh->cursize = 0;
62         gh->nentries = 0;
63         gh->nbuckets = hashsizes[gh->cursize];
64
65         gh->buckets = MEM_mallocN(gh->nbuckets * sizeof(*gh->buckets), "buckets");
66         memset(gh->buckets, 0, gh->nbuckets * sizeof(*gh->buckets));
67
68         return gh;
69 }
70
71 int BLI_ghash_size(GHash *gh)
72 {
73         return gh->nentries;
74 }
75
76 void BLI_ghash_insert(GHash *gh, void *key, void *val)
77 {
78         unsigned int hash = gh->hashfp(key) % gh->nbuckets;
79         Entry *e = (Entry *)BLI_mempool_alloc(gh->entrypool);
80
81         e->next = gh->buckets[hash];
82         e->key = key;
83         e->val = val;
84         gh->buckets[hash] = e;
85
86         if (++gh->nentries > (float)gh->nbuckets / 2) {
87                 Entry **old = gh->buckets;
88                 int i, nold = gh->nbuckets;
89
90                 gh->nbuckets = hashsizes[++gh->cursize];
91                 gh->buckets = (Entry **)MEM_mallocN(gh->nbuckets * sizeof(*gh->buckets), "buckets");
92                 memset(gh->buckets, 0, gh->nbuckets * sizeof(*gh->buckets));
93
94                 for (i = 0; i < nold; i++) {
95                         for (e = old[i]; e; ) {
96                                 Entry *n = e->next;
97
98                                 hash = gh->hashfp(e->key) % gh->nbuckets;
99                                 e->next = gh->buckets[hash];
100                                 gh->buckets[hash] = e;
101
102                                 e = n;
103                         }
104                 }
105
106                 MEM_freeN(old);
107         }
108 }
109
110 void *BLI_ghash_lookup(GHash *gh, const void *key)
111 {
112         const unsigned int hash = gh->hashfp(key) % gh->nbuckets;
113         Entry *e;
114
115         for (e = gh->buckets[hash]; e; e = e->next) {
116                 if (gh->cmpfp(key, e->key) == 0) {
117                         return e->val;
118                 }
119         }
120         return NULL;
121 }
122
123 bool BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
124 {
125         unsigned int hash = gh->hashfp(key) % gh->nbuckets;
126         Entry *e;
127         Entry *p = NULL;
128
129         for (e = gh->buckets[hash]; e; e = e->next) {
130                 if (gh->cmpfp(key, e->key) == 0) {
131                         Entry *n = e->next;
132
133                         if (keyfreefp) keyfreefp(e->key);
134                         if (valfreefp) valfreefp(e->val);
135                         BLI_mempool_free(gh->entrypool, e);
136
137                         /* correct but 'e' isn't used before return */
138                         /* e = n; *//*UNUSED*/
139                         if (p) p->next = n;
140                         else   gh->buckets[hash] = n;
141
142                         gh->nentries--;
143                         return true;
144                 }
145                 p = e;
146         }
147
148         return false;
149 }
150
151 /* same as above but return the value,
152  * no free value argument since it will be returned */
153 void *BLI_ghash_pop(GHash *gh, void *key, GHashKeyFreeFP keyfreefp)
154 {
155         unsigned int hash = gh->hashfp(key) % gh->nbuckets;
156         Entry *e;
157         Entry *p = NULL;
158
159         for (e = gh->buckets[hash]; e; e = e->next) {
160                 if (gh->cmpfp(key, e->key) == 0) {
161                         Entry *n = e->next;
162                         void *value = e->val;
163
164                         if (keyfreefp) keyfreefp(e->key);
165                         BLI_mempool_free(gh->entrypool, e);
166
167                         /* correct but 'e' isn't used before return */
168                         /* e = n; *//*UNUSED*/
169                         if (p) p->next = n;
170                         else   gh->buckets[hash] = n;
171
172                         gh->nentries--;
173                         return value;
174                 }
175                 p = e;
176         }
177
178         return NULL;
179 }
180
181 bool BLI_ghash_haskey(GHash *gh, const void *key)
182 {
183         unsigned int hash = gh->hashfp(key) % gh->nbuckets;
184         Entry *e;
185
186         for (e = gh->buckets[hash]; e; e = e->next)
187                 if (gh->cmpfp(key, e->key) == 0)
188                         return true;
189
190         return false;
191 }
192
193 void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
194 {
195         int i;
196
197         if (keyfreefp || valfreefp) {
198                 for (i = 0; i < gh->nbuckets; i++) {
199                         Entry *e;
200
201                         for (e = gh->buckets[i]; e; ) {
202                                 Entry *n = e->next;
203
204                                 if (keyfreefp) keyfreefp(e->key);
205                                 if (valfreefp) valfreefp(e->val);
206
207                                 e = n;
208                         }
209                 }
210         }
211
212         MEM_freeN(gh->buckets);
213         BLI_mempool_destroy(gh->entrypool);
214         gh->buckets = NULL;
215         gh->nentries = 0;
216         gh->nbuckets = 0;
217         MEM_freeN(gh);
218 }
219
220 /***/
221
222 GHashIterator *BLI_ghashIterator_new(GHash *gh)
223 {
224         GHashIterator *ghi = MEM_mallocN(sizeof(*ghi), "ghash iterator");
225         ghi->gh = gh;
226         ghi->curEntry = NULL;
227         ghi->curBucket = -1;
228         while (!ghi->curEntry) {
229                 ghi->curBucket++;
230                 if (ghi->curBucket == ghi->gh->nbuckets)
231                         break;
232                 ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
233         }
234         return ghi;
235 }
236 void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh)
237 {
238         ghi->gh = gh;
239         ghi->curEntry = NULL;
240         ghi->curBucket = -1;
241         while (!ghi->curEntry) {
242                 ghi->curBucket++;
243                 if (ghi->curBucket == ghi->gh->nbuckets)
244                         break;
245                 ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
246         }
247 }
248 void BLI_ghashIterator_free(GHashIterator *ghi)
249 {
250         MEM_freeN(ghi);
251 }
252
253 void *BLI_ghashIterator_getKey(GHashIterator *ghi)
254 {
255         return ghi->curEntry ? ghi->curEntry->key : NULL;
256 }
257 void *BLI_ghashIterator_getValue(GHashIterator *ghi)
258 {
259         return ghi->curEntry ? ghi->curEntry->val : NULL;
260 }
261
262 void BLI_ghashIterator_step(GHashIterator *ghi)
263 {
264         if (ghi->curEntry) {
265                 ghi->curEntry = ghi->curEntry->next;
266                 while (!ghi->curEntry) {
267                         ghi->curBucket++;
268                         if (ghi->curBucket == ghi->gh->nbuckets)
269                                 break;
270                         ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
271                 }
272         }
273 }
274 int BLI_ghashIterator_notDone(GHashIterator *ghi)
275 {
276         return ghi->curEntry != NULL;
277 }
278
279 /***/
280
281 unsigned int BLI_ghashutil_ptrhash(const void *key)
282 {
283         return (unsigned int)(intptr_t)key;
284 }
285 int BLI_ghashutil_ptrcmp(const void *a, const void *b)
286 {
287         if (a == b)
288                 return 0;
289         else
290                 return (a < b) ? -1 : 1;
291 }
292
293 unsigned int BLI_ghashutil_inthash(const void *ptr)
294 {
295         uintptr_t key = (uintptr_t)ptr;
296
297         key += ~(key << 16);
298         key ^=  (key >>  5);
299         key +=  (key <<  3);
300         key ^=  (key >> 13);
301         key += ~(key <<  9);
302         key ^=  (key >> 17);
303
304         return (unsigned int)(key & 0xffffffff);
305 }
306
307 int BLI_ghashutil_intcmp(const void *a, const void *b)
308 {
309         if (a == b)
310                 return 0;
311         else
312                 return (a < b) ? -1 : 1;
313 }
314
315 /**
316  * This function implements the widely used "djb" hash apparently posted
317  * by Daniel Bernstein to comp.lang.c some time ago.  The 32 bit
318  * unsigned hash value starts at 5381 and for each byte 'c' in the
319  * string, is updated: <literal>hash = hash * 33 + c</literal>.  This
320  * function uses the signed value of each byte.
321  *
322  * note: this is the same hash method that glib 2.34.0 uses.
323  */
324 unsigned int BLI_ghashutil_strhash(const void *ptr)
325 {
326         const signed char *p;
327         unsigned int h = 5381;
328
329         for (p = ptr; *p != '\0'; p++) {
330                 h = (h << 5) + h + *p;
331         }
332
333         return h;
334 }
335 int BLI_ghashutil_strcmp(const void *a, const void *b)
336 {
337         return strcmp(a, b);
338 }
339
340 GHash *BLI_ghash_ptr_new(const char *info)
341 {
342         return BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info);
343 }
344 GHash *BLI_ghash_str_new(const char *info)
345 {
346         return BLI_ghash_new(BLI_ghashutil_strhash, BLI_ghashutil_strcmp, info);
347 }
348 GHash *BLI_ghash_int_new(const char *info)
349 {
350         return BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp, info);
351 }
352 GHash *BLI_ghash_pair_new(const char *info)
353 {
354         return BLI_ghash_new(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info);
355 }
356
357 GHashPair *BLI_ghashutil_pairalloc(const void *first, const void *second)
358 {
359         GHashPair *pair = MEM_mallocN(sizeof(GHashPair), "GHashPair");
360         pair->first = first;
361         pair->second = second;
362         return pair;
363 }
364
365 unsigned int BLI_ghashutil_pairhash(const void *ptr)
366 {
367         const GHashPair *pair = ptr;
368         unsigned int hash = BLI_ghashutil_ptrhash(pair->first);
369         return hash ^ BLI_ghashutil_ptrhash(pair->second);
370 }
371
372 int BLI_ghashutil_paircmp(const void *a, const void *b)
373 {
374         const GHashPair *A = a;
375         const GHashPair *B = b;
376
377         int cmp = BLI_ghashutil_ptrcmp(A->first, B->first);
378         if (cmp == 0)
379                 return BLI_ghashutil_ptrcmp(A->second, B->second);
380         return cmp;
381 }
382
383 void BLI_ghashutil_pairfree(void *ptr)
384 {
385         MEM_freeN((void *)ptr);
386 }