svn merge ^/trunk/blender -r43616:43639
[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
37 #include "MEM_guardedalloc.h"
38
39
40
41 // #include "BLI_blenlib.h"
42
43 #include "BLI_utildefines.h"
44 #include "BLI_mempool.h"
45 #include "BLI_ghash.h"
46
47 #include "BLO_sys_types.h" // for intptr_t support
48 /***/
49
50 unsigned int hashsizes[]= {
51         5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 
52         16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 
53         4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 
54         268435459
55 };
56
57 /***/
58
59 GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
60 {
61         GHash *gh= MEM_mallocN(sizeof(*gh), info);
62         gh->hashfp= hashfp;
63         gh->cmpfp= cmpfp;
64         gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, TRUE, FALSE);
65
66         gh->cursize= 0;
67         gh->nentries= 0;
68         gh->nbuckets= hashsizes[gh->cursize];
69         
70         gh->buckets= MEM_mallocN(gh->nbuckets*sizeof(*gh->buckets), "buckets");
71         memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
72         
73         return gh;
74 }
75
76 int BLI_ghash_size(GHash *gh)
77 {
78         return gh->nentries;
79 }
80
81 void BLI_ghash_insert(GHash *gh, void *key, void *val)
82 {
83         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
84         Entry *e= (Entry*) BLI_mempool_alloc(gh->entrypool);
85
86         e->key= key;
87         e->val= val;
88         e->next= gh->buckets[hash];
89         gh->buckets[hash]= e;
90
91         if (++gh->nentries>(float)gh->nbuckets/2) {
92                 Entry **old= gh->buckets;
93                 int i, nold= gh->nbuckets;
94
95                 gh->nbuckets= hashsizes[++gh->cursize];
96                 gh->buckets= (Entry**)MEM_mallocN(gh->nbuckets*sizeof(*gh->buckets), "buckets");
97                 memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
98
99                 for (i=0; i<nold; i++) {
100                         for (e= old[i]; e;) {
101                                 Entry *n= e->next;
102
103                                 hash= gh->hashfp(e->key)%gh->nbuckets;
104                                 e->next= gh->buckets[hash];
105                                 gh->buckets[hash]= e;
106
107                                 e= n;
108                         }
109                 }
110
111                 MEM_freeN(old);
112         }
113 }
114
115 void *BLI_ghash_lookup(GHash *gh, const void *key)
116 {
117         if(gh) {
118                 unsigned int hash= gh->hashfp(key)%gh->nbuckets;
119                 Entry *e;
120
121                 for (e= gh->buckets[hash]; e; e= e->next)
122                         if (gh->cmpfp(key, e->key)==0)
123                                 return e->val;
124         }
125         return NULL;
126 }
127
128 int BLI_ghash_remove (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
129 {
130         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
131         Entry *e;
132         Entry *p = NULL;
133
134         for (e= gh->buckets[hash]; e; e= e->next) {
135                 if (gh->cmpfp(key, e->key)==0) {
136                         Entry *n= e->next;
137
138                         if (keyfreefp) keyfreefp(e->key);
139                         if (valfreefp) valfreefp(e->val);
140                         BLI_mempool_free(gh->entrypool, e);
141
142                         /* correct but 'e' isnt used before return */
143                         /* e= n; */ /*UNUSED*/
144                         if (p)
145                                 p->next = n;
146                         else
147                                 gh->buckets[hash] = n;
148
149                         --gh->nentries;
150                         return 1;
151                 }
152                 p = e;
153         }
154
155         return 0;
156 }
157
158 int BLI_ghash_haskey(GHash *gh, void *key)
159 {
160         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
161         Entry *e;
162
163         for (e= gh->buckets[hash]; e; e= e->next)
164                 if (gh->cmpfp(key, e->key)==0)
165                         return 1;
166
167         return 0;
168 }
169
170 void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
171 {
172         int i;
173         
174         if (keyfreefp || valfreefp) {
175                 for (i=0; i<gh->nbuckets; i++) {
176                         Entry *e;
177                         
178                         for (e= gh->buckets[i]; e; ) {
179                                 Entry *n= e->next;
180                                 
181                                 if (keyfreefp) keyfreefp(e->key);
182                                 if (valfreefp) valfreefp(e->val);
183
184                                 e= n;
185                         }
186                 }
187         }
188         
189         MEM_freeN(gh->buckets);
190         BLI_mempool_destroy(gh->entrypool);
191         gh->buckets = NULL;
192         gh->nentries = 0;
193         gh->nbuckets = 0;
194         MEM_freeN(gh);
195 }
196
197 /***/
198
199 GHashIterator *BLI_ghashIterator_new(GHash *gh)
200 {
201         GHashIterator *ghi= MEM_mallocN(sizeof(*ghi), "ghash iterator");
202         ghi->gh= gh;
203         ghi->curEntry= NULL;
204         ghi->curBucket= -1;
205         while (!ghi->curEntry) {
206                 ghi->curBucket++;
207                 if (ghi->curBucket==ghi->gh->nbuckets)
208                         break;
209                 ghi->curEntry= ghi->gh->buckets[ghi->curBucket];
210         }
211         return ghi;
212 }
213 void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh)
214 {
215         ghi->gh= gh;
216         ghi->curEntry= NULL;
217         ghi->curBucket= -1;
218         while (!ghi->curEntry) {
219                 ghi->curBucket++;
220                 if (ghi->curBucket==ghi->gh->nbuckets)
221                         break;
222                 ghi->curEntry= ghi->gh->buckets[ghi->curBucket];
223         }
224 }
225 void BLI_ghashIterator_free(GHashIterator *ghi)
226 {
227         MEM_freeN(ghi);
228 }
229
230 void *BLI_ghashIterator_getKey(GHashIterator *ghi)
231 {
232         return ghi->curEntry?ghi->curEntry->key:NULL;
233 }
234 void *BLI_ghashIterator_getValue(GHashIterator *ghi)
235 {
236         return ghi->curEntry?ghi->curEntry->val:NULL;
237 }
238
239 void BLI_ghashIterator_step(GHashIterator *ghi)
240 {
241         if (ghi->curEntry) {
242                 ghi->curEntry= ghi->curEntry->next;
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 }
251 int BLI_ghashIterator_isDone(GHashIterator *ghi)
252 {
253         return !ghi->curEntry;
254 }
255
256 /***/
257
258 unsigned int BLI_ghashutil_ptrhash(const void *key)
259 {
260         return (unsigned int)(intptr_t)key;
261 }
262 int BLI_ghashutil_ptrcmp(const void *a, const void *b)
263 {
264         if (a==b)
265                 return 0;
266         else
267                 return (a<b)?-1:1;
268 }
269
270 unsigned int BLI_ghashutil_inthash(const void *ptr)
271 {
272         uintptr_t key = (uintptr_t)ptr;
273
274         key += ~(key << 16);
275         key ^=  (key >>  5);
276         key +=  (key <<  3);
277         key ^=  (key >> 13);
278         key += ~(key <<  9);
279         key ^=  (key >> 17);
280
281         return (unsigned int)(key & 0xffffffff);
282 }
283
284 int BLI_ghashutil_intcmp(const void *a, const void *b)
285 {
286         if (a==b)
287                 return 0;
288         else
289                 return (a<b)?-1:1;
290 }
291
292 unsigned int BLI_ghashutil_strhash(const void *ptr)
293 {
294         const char *s= ptr;
295         unsigned int i= 0;
296         unsigned char c;
297         
298         while ( (c= *s++) )
299                 i= i*37 + c;
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