Merging r44227 through r45619 from trunk into soc-2011-tomato
[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)
136                                 keyfreefp(e->key);
137                         if (valfreefp)
138                                 valfreefp(e->val);
139                         BLI_mempool_free(gh->entrypool, e);
140
141                         /* correct but 'e' isn't used before return */
142                         /* e= n; *//*UNUSED*/
143                         if (p)
144                                 p->next = n;
145                         else
146                                 gh->buckets[hash] = n;
147
148                         --gh->nentries;
149                         return 1;
150                 }
151                 p = e;
152         }
153
154         return 0;
155 }
156
157 int BLI_ghash_haskey(GHash *gh, void *key)
158 {
159         unsigned int hash = gh->hashfp(key) % gh->nbuckets;
160         Entry *e;
161
162         for (e = gh->buckets[hash]; e; e = e->next)
163                 if (gh->cmpfp(key, e->key) == 0)
164                         return 1;
165
166         return 0;
167 }
168
169 void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
170 {
171         int i;
172
173         if (keyfreefp || valfreefp) {
174                 for (i = 0; i < gh->nbuckets; i++) {
175                         Entry *e;
176
177                         for (e = gh->buckets[i]; e;) {
178                                 Entry *n = e->next;
179
180                                 if (keyfreefp) keyfreefp(e->key);
181                                 if (valfreefp) valfreefp(e->val);
182
183                                 e = n;
184                         }
185                 }
186         }
187
188         MEM_freeN(gh->buckets);
189         BLI_mempool_destroy(gh->entrypool);
190         gh->buckets = NULL;
191         gh->nentries = 0;
192         gh->nbuckets = 0;
193         MEM_freeN(gh);
194 }
195
196 /***/
197
198 GHashIterator *BLI_ghashIterator_new(GHash *gh)
199 {
200         GHashIterator *ghi = MEM_mallocN(sizeof(*ghi), "ghash iterator");
201         ghi->gh = gh;
202         ghi->curEntry = NULL;
203         ghi->curBucket = -1;
204         while (!ghi->curEntry) {
205                 ghi->curBucket++;
206                 if (ghi->curBucket == ghi->gh->nbuckets)
207                         break;
208                 ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
209         }
210         return ghi;
211 }
212 void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh)
213 {
214         ghi->gh = gh;
215         ghi->curEntry = NULL;
216         ghi->curBucket = -1;
217         while (!ghi->curEntry) {
218                 ghi->curBucket++;
219                 if (ghi->curBucket == ghi->gh->nbuckets)
220                         break;
221                 ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
222         }
223 }
224 void BLI_ghashIterator_free(GHashIterator *ghi)
225 {
226         MEM_freeN(ghi);
227 }
228
229 void *BLI_ghashIterator_getKey(GHashIterator *ghi)
230 {
231         return ghi->curEntry ? ghi->curEntry->key : NULL;
232 }
233 void *BLI_ghashIterator_getValue(GHashIterator *ghi)
234 {
235         return ghi->curEntry ? ghi->curEntry->val : NULL;
236 }
237
238 void BLI_ghashIterator_step(GHashIterator *ghi)
239 {
240         if (ghi->curEntry) {
241                 ghi->curEntry = ghi->curEntry->next;
242                 while (!ghi->curEntry) {
243                         ghi->curBucket++;
244                         if (ghi->curBucket == ghi->gh->nbuckets)
245                                 break;
246                         ghi->curEntry = ghi->gh->buckets[ghi->curBucket];
247                 }
248         }
249 }
250 int BLI_ghashIterator_isDone(GHashIterator *ghi)
251 {
252         return !ghi->curEntry;
253 }
254
255 /***/
256
257 unsigned int BLI_ghashutil_ptrhash(const void *key)
258 {
259         return (unsigned int)(intptr_t)key;
260 }
261 int BLI_ghashutil_ptrcmp(const void *a, const void *b)
262 {
263         if (a == b)
264                 return 0;
265         else
266                 return (a < b) ? -1 : 1;
267 }
268
269 unsigned int BLI_ghashutil_inthash(const void *ptr)
270 {
271         uintptr_t key = (uintptr_t)ptr;
272
273         key += ~(key << 16);
274         key ^=  (key >>  5);
275         key +=  (key <<  3);
276         key ^=  (key >> 13);
277         key += ~(key <<  9);
278         key ^=  (key >> 17);
279
280         return (unsigned int)(key & 0xffffffff);
281 }
282
283 int BLI_ghashutil_intcmp(const void *a, const void *b)
284 {
285         if (a == b)
286                 return 0;
287         else
288                 return (a < b) ? -1 : 1;
289 }
290
291 unsigned int BLI_ghashutil_strhash(const void *ptr)
292 {
293         const char *s = ptr;
294         unsigned int i = 0;
295         unsigned char c;
296
297         while ((c = *s++)) {
298                 i = i * 37 + c;
299         }
300
301         return i;
302 }
303 int BLI_ghashutil_strcmp(const void *a, const void *b)
304 {
305         return strcmp(a, b);
306 }
307
308 GHashPair *BLI_ghashutil_pairalloc(const void *first, int second)
309 {
310         GHashPair *pair = MEM_mallocN(sizeof(GHashPair), "GHashPair");
311         pair->first = first;
312         pair->second = second;
313         return pair;
314 }
315
316 unsigned int BLI_ghashutil_pairhash(const void *ptr)
317 {
318         const GHashPair *pair = ptr;
319         unsigned int hash = BLI_ghashutil_ptrhash(pair->first);
320         return hash ^ BLI_ghashutil_inthash(SET_INT_IN_POINTER(pair->second));
321 }
322
323 int BLI_ghashutil_paircmp(const void *a, const void *b)
324 {
325         const GHashPair *A = a;
326         const GHashPair *B = b;
327
328         int cmp = BLI_ghashutil_ptrcmp(A->first, B->first);
329         if (cmp == 0)
330                 return BLI_ghashutil_intcmp(SET_INT_IN_POINTER(A->second), SET_INT_IN_POINTER(B->second));
331         return cmp;
332 }
333
334 void BLI_ghashutil_pairfree(void *ptr)
335 {
336         MEM_freeN((void*)ptr);
337 }
338