add BLI_ghash_pop() which returns the value for a key and removes it at the same...
[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_blenlib.h"
39
40 #include "BLI_utildefines.h"
41 #include "BLI_mempool.h"
42 #include "BLI_ghash.h"
43
44 #include "BLO_sys_types.h" // for intptr_t support
45 /***/
46
47 unsigned int hashsizes[] = {
48         5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 
49         16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 
50         4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 
51         268435459
52 };
53
54 /***/
55
56 GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
57 {
58         GHash *gh = MEM_mallocN(sizeof(*gh), info);
59         gh->hashfp = hashfp;
60         gh->cmpfp = cmpfp;
61         gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, 0);
62
63         gh->cursize = 0;
64         gh->nentries = 0;
65         gh->nbuckets = hashsizes[gh->cursize];
66
67         gh->buckets = MEM_mallocN(gh->nbuckets * sizeof(*gh->buckets), "buckets");
68         memset(gh->buckets, 0, gh->nbuckets * sizeof(*gh->buckets));
69
70         return gh;
71 }
72
73 int BLI_ghash_size(GHash *gh)
74 {
75         return gh->nentries;
76 }
77
78 void BLI_ghash_insert(GHash *gh, void *key, void *val)
79 {
80         unsigned int hash = gh->hashfp(key) % gh->nbuckets;
81         Entry *e = (Entry *)BLI_mempool_alloc(gh->entrypool);
82
83         e->key = key;
84         e->val = val;
85         e->next = gh->buckets[hash];
86         gh->buckets[hash] = e;
87
88         if (++gh->nentries > (float)gh->nbuckets / 2) {
89                 Entry **old = gh->buckets;
90                 int i, nold = gh->nbuckets;
91
92                 gh->nbuckets = hashsizes[++gh->cursize];
93                 gh->buckets = (Entry **)MEM_mallocN(gh->nbuckets * sizeof(*gh->buckets), "buckets");
94                 memset(gh->buckets, 0, gh->nbuckets * sizeof(*gh->buckets));
95
96                 for (i = 0; i < nold; i++) {
97                         for (e = old[i]; e; ) {
98                                 Entry *n = e->next;
99
100                                 hash = gh->hashfp(e->key) % gh->nbuckets;
101                                 e->next = gh->buckets[hash];
102                                 gh->buckets[hash] = e;
103
104                                 e = n;
105                         }
106                 }
107
108                 MEM_freeN(old);
109         }
110 }
111
112 void *BLI_ghash_lookup(GHash *gh, const void *key)
113 {
114         if (gh) {
115                 unsigned int hash = gh->hashfp(key) % gh->nbuckets;
116                 Entry *e;
117
118                 for (e = gh->buckets[hash]; e; e = e->next)
119                         if (gh->cmpfp(key, e->key) == 0)
120                                 return e->val;
121         }
122         return NULL;
123 }
124
125 int BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
126 {
127         unsigned int hash = gh->hashfp(key) % gh->nbuckets;
128         Entry *e;
129         Entry *p = NULL;
130
131         for (e = gh->buckets[hash]; e; e = e->next) {
132                 if (gh->cmpfp(key, e->key) == 0) {
133                         Entry *n = e->next;
134
135                         if (keyfreefp) keyfreefp(e->key);
136                         if (valfreefp) valfreefp(e->val);
137                         BLI_mempool_free(gh->entrypool, e);
138
139                         /* correct but 'e' isn't used before return */
140                         /* e= n; *//*UNUSED*/
141                         if (p) p->next = n;
142                         else   gh->buckets[hash] = n;
143
144                         gh->nentries--;
145                         return 1;
146                 }
147                 p = e;
148         }
149
150         return 0;
151 }
152
153 /* same as above but return the value,
154  * no free value argument since it will be returned */
155 void *BLI_ghash_pop(GHash *gh, void *key, GHashKeyFreeFP keyfreefp)
156 {
157         unsigned int hash = gh->hashfp(key) % gh->nbuckets;
158         Entry *e;
159         Entry *p = NULL;
160
161         for (e = gh->buckets[hash]; e; e = e->next) {
162                 if (gh->cmpfp(key, e->key) == 0) {
163                         Entry *n = e->next;
164                         void *value = e->val;
165
166                         if (keyfreefp) keyfreefp(e->key);
167                         BLI_mempool_free(gh->entrypool, e);
168
169                         /* correct but 'e' isn't used before return */
170                         /* e= n; *//*UNUSED*/
171                         if (p) p->next = n;
172                         else   gh->buckets[hash] = n;
173
174                         gh->nentries--;
175                         return value;
176                 }
177                 p = e;
178         }
179
180         return NULL;
181 }
182
183 int BLI_ghash_haskey(GHash *gh, void *key)
184 {
185         unsigned int hash = gh->hashfp(key) % gh->nbuckets;
186         Entry *e;
187
188         for (e = gh->buckets[hash]; e; e = e->next)
189                 if (gh->cmpfp(key, e->key) == 0)
190                         return 1;
191
192         return 0;
193 }
194
195 void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
196 {
197         int i;
198
199         if (keyfreefp || valfreefp) {
200                 for (i = 0; i < gh->nbuckets; i++) {
201                         Entry *e;
202
203                         for (e = gh->buckets[i]; e; ) {
204                                 Entry *n = e->next;
205
206                                 if (keyfreefp) keyfreefp(e->key);
207                                 if (valfreefp) valfreefp(e->val);
208
209                                 e = n;
210                         }
211                 }
212         }
213
214         MEM_freeN(gh->buckets);
215         BLI_mempool_destroy(gh->entrypool);
216         gh->buckets = NULL;
217         gh->nentries = 0;
218         gh->nbuckets = 0;
219         MEM_freeN(gh);
220 }
221
222 /***/
223
224 GHashIterator *BLI_ghashIterator_new(GHash *gh)
225 {
226         GHashIterator *ghi = MEM_mallocN(sizeof(*ghi), "ghash iterator");
227         ghi->gh = gh;
228         ghi->curEntry = NULL;
229         ghi->curBucket = -1;
230         while (!ghi->curEntry) {
231                 ghi->curBucket++;
232                 if (ghi->curBucket == ghi->gh->nbuckets)
233                         break;
234                 ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
235         }
236         return ghi;
237 }
238 void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh)
239 {
240         ghi->gh = gh;
241         ghi->curEntry = NULL;
242         ghi->curBucket = -1;
243         while (!ghi->curEntry) {
244                 ghi->curBucket++;
245                 if (ghi->curBucket == ghi->gh->nbuckets)
246                         break;
247                 ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
248         }
249 }
250 void BLI_ghashIterator_free(GHashIterator *ghi)
251 {
252         MEM_freeN(ghi);
253 }
254
255 void *BLI_ghashIterator_getKey(GHashIterator *ghi)
256 {
257         return ghi->curEntry ? ghi->curEntry->key : NULL;
258 }
259 void *BLI_ghashIterator_getValue(GHashIterator *ghi)
260 {
261         return ghi->curEntry ? ghi->curEntry->val : NULL;
262 }
263
264 void BLI_ghashIterator_step(GHashIterator *ghi)
265 {
266         if (ghi->curEntry) {
267                 ghi->curEntry = ghi->curEntry->next;
268                 while (!ghi->curEntry) {
269                         ghi->curBucket++;
270                         if (ghi->curBucket == ghi->gh->nbuckets)
271                                 break;
272                         ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
273                 }
274         }
275 }
276 int BLI_ghashIterator_isDone(GHashIterator *ghi)
277 {
278         return !ghi->curEntry;
279 }
280
281 /***/
282
283 unsigned int BLI_ghashutil_ptrhash(const void *key)
284 {
285         return (unsigned int)(intptr_t)key;
286 }
287 int BLI_ghashutil_ptrcmp(const void *a, const void *b)
288 {
289         if (a == b)
290                 return 0;
291         else
292                 return (a < b) ? -1 : 1;
293 }
294
295 unsigned int BLI_ghashutil_inthash(const void *ptr)
296 {
297         uintptr_t key = (uintptr_t)ptr;
298
299         key += ~(key << 16);
300         key ^=  (key >>  5);
301         key +=  (key <<  3);
302         key ^=  (key >> 13);
303         key += ~(key <<  9);
304         key ^=  (key >> 17);
305
306         return (unsigned int)(key & 0xffffffff);
307 }
308
309 int BLI_ghashutil_intcmp(const void *a, const void *b)
310 {
311         if (a == b)
312                 return 0;
313         else
314                 return (a < b) ? -1 : 1;
315 }
316
317 unsigned int BLI_ghashutil_strhash(const void *ptr)
318 {
319         const char *s = ptr;
320         unsigned int i = 0;
321         unsigned char c;
322
323         while ((c = *s++)) {
324                 i = i * 37 + c;
325         }
326
327         return i;
328 }
329 int BLI_ghashutil_strcmp(const void *a, const void *b)
330 {
331         return strcmp(a, b);
332 }
333
334 GHash *BLI_ghash_ptr_new(const char *info)
335 {
336         return BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info);
337 }
338 GHash *BLI_ghash_str_new(const char *info)
339 {
340         return BLI_ghash_new(BLI_ghashutil_strhash, BLI_ghashutil_strcmp, info);
341 }
342 GHash *BLI_ghash_int_new(const char *info)
343 {
344         return BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp, info);
345 }
346 GHash *BLI_ghash_pair_new(const char *info)
347 {
348         return BLI_ghash_new(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info);
349 }
350
351 GHashPair *BLI_ghashutil_pairalloc(const void *first, const void *second)
352 {
353         GHashPair *pair = MEM_mallocN(sizeof(GHashPair), "GHashPair");
354         pair->first = first;
355         pair->second = second;
356         return pair;
357 }
358
359 unsigned int BLI_ghashutil_pairhash(const void *ptr)
360 {
361         const GHashPair *pair = ptr;
362         unsigned int hash = BLI_ghashutil_ptrhash(pair->first);
363         return hash ^ BLI_ghashutil_ptrhash(pair->second);
364 }
365
366 int BLI_ghashutil_paircmp(const void *a, const void *b)
367 {
368         const GHashPair *A = a;
369         const GHashPair *B = b;
370
371         int cmp = BLI_ghashutil_ptrcmp(A->first, B->first);
372         if (cmp == 0)
373                 return BLI_ghashutil_ptrcmp(A->second, B->second);
374         return cmp;
375 }
376
377 void BLI_ghashutil_pairfree(void *ptr)
378 {
379         MEM_freeN((void *)ptr);
380 }
381