svn merge ^/trunk/blender -r41226:41227 .
[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         GHash *gh= MEM_mallocN(sizeof(*gh), info);
61         gh->hashfp= hashfp;
62         gh->cmpfp= cmpfp;
63         gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, 1, 0);
64
65         gh->cursize= 0;
66         gh->nentries= 0;
67         gh->nbuckets= hashsizes[gh->cursize];
68         
69         gh->buckets= MEM_mallocN(gh->nbuckets*sizeof(*gh->buckets), "buckets");
70         memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
71         
72         return gh;
73 }
74
75 int BLI_ghash_size(GHash *gh) {
76         return gh->nentries;
77 }
78
79 void BLI_ghash_insert(GHash *gh, void *key, void *val) {
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         if(gh) {
114                 unsigned int hash= gh->hashfp(key)%gh->nbuckets;
115                 Entry *e;
116
117                 for (e= gh->buckets[hash]; e; e= e->next)
118                         if (gh->cmpfp(key, e->key)==0)
119                                 return e->val;
120         }
121         return NULL;
122 }
123
124 int BLI_ghash_remove (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
125 {
126         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
127         Entry *e;
128         Entry *p = NULL;
129
130         for (e= gh->buckets[hash]; e; e= e->next) {
131                 if (gh->cmpfp(key, e->key)==0) {
132                         Entry *n= e->next;
133
134                         if (keyfreefp) keyfreefp(e->key);
135                         if (valfreefp) valfreefp(e->val);
136                         BLI_mempool_free(gh->entrypool, e);
137
138                         /* correct but 'e' isnt used before return */
139                         /* e= n; */ /*UNUSED*/
140                         if (p)
141                                 p->next = n;
142                         else
143                                 gh->buckets[hash] = n;
144
145                         --gh->nentries;
146                         return 1;
147                 }
148                 p = e;
149         }
150
151         return 0;
152 }
153
154 int BLI_ghash_haskey(GHash *gh, void *key) {
155         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
156         Entry *e;
157
158         for (e= gh->buckets[hash]; e; e= e->next)
159                 if (gh->cmpfp(key, e->key)==0)
160                         return 1;
161
162         return 0;
163 }
164
165 void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) {
166         int i;
167         
168         if (keyfreefp || valfreefp) {
169                 for (i=0; i<gh->nbuckets; i++) {
170                         Entry *e;
171                         
172                         for (e= gh->buckets[i]; e; ) {
173                                 Entry *n= e->next;
174                                 
175                                 if (keyfreefp) keyfreefp(e->key);
176                                 if (valfreefp) valfreefp(e->val);
177
178                                 e= n;
179                         }
180                 }
181         }
182         
183         MEM_freeN(gh->buckets);
184         BLI_mempool_destroy(gh->entrypool);
185         gh->buckets = NULL;
186         gh->nentries = 0;
187         gh->nbuckets = 0;
188         MEM_freeN(gh);
189 }
190
191 /***/
192
193 GHashIterator *BLI_ghashIterator_new(GHash *gh) {
194         GHashIterator *ghi= MEM_mallocN(sizeof(*ghi), "ghash iterator");
195         ghi->gh= gh;
196         ghi->curEntry= NULL;
197         ghi->curBucket= -1;
198         while (!ghi->curEntry) {
199                 ghi->curBucket++;
200                 if (ghi->curBucket==ghi->gh->nbuckets)
201                         break;
202                 ghi->curEntry= ghi->gh->buckets[ghi->curBucket];
203         }
204         return ghi;
205 }
206 void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh) {
207         ghi->gh= gh;
208         ghi->curEntry= NULL;
209         ghi->curBucket= -1;
210         while (!ghi->curEntry) {
211                 ghi->curBucket++;
212                 if (ghi->curBucket==ghi->gh->nbuckets)
213                         break;
214                 ghi->curEntry= ghi->gh->buckets[ghi->curBucket];
215         }
216 }
217 void BLI_ghashIterator_free(GHashIterator *ghi) {
218         MEM_freeN(ghi);
219 }
220
221 void *BLI_ghashIterator_getKey(GHashIterator *ghi) {
222         return ghi->curEntry?ghi->curEntry->key:NULL;
223 }
224 void *BLI_ghashIterator_getValue(GHashIterator *ghi) {
225         return ghi->curEntry?ghi->curEntry->val:NULL;
226 }
227
228 void BLI_ghashIterator_step(GHashIterator *ghi) {
229         if (ghi->curEntry) {
230                 ghi->curEntry= ghi->curEntry->next;
231                 while (!ghi->curEntry) {
232                         ghi->curBucket++;
233                         if (ghi->curBucket==ghi->gh->nbuckets)
234                                 break;
235                         ghi->curEntry= ghi->gh->buckets[ghi->curBucket];
236                 }
237         }
238 }
239 int BLI_ghashIterator_isDone(GHashIterator *ghi) {
240         return !ghi->curEntry;
241 }
242
243 /***/
244
245 unsigned int BLI_ghashutil_ptrhash(const void *key) {
246         return (unsigned int)(intptr_t)key;
247 }
248 int BLI_ghashutil_ptrcmp(const void *a, const void *b) {
249         if (a==b)
250                 return 0;
251         else
252                 return (a<b)?-1:1;
253 }
254
255 unsigned int BLI_ghashutil_inthash(const void *ptr) {
256         uintptr_t key = (uintptr_t)ptr;
257
258         key += ~(key << 16);
259         key ^=  (key >>  5);
260         key +=  (key <<  3);
261         key ^=  (key >> 13);
262         key += ~(key <<  9);
263         key ^=  (key >> 17);
264
265         return (unsigned int)(key & 0xffffffff);
266 }
267
268 int BLI_ghashutil_intcmp(const void *a, const void *b) {
269         if (a==b)
270                 return 0;
271         else
272                 return (a<b)?-1:1;
273 }
274
275 unsigned int BLI_ghashutil_strhash(const void *ptr) {
276         const char *s= ptr;
277         unsigned int i= 0;
278         unsigned char c;
279         
280         while ( (c= *s++) )
281                 i= i*37 + c;
282                 
283         return i;
284 }
285 int BLI_ghashutil_strcmp(const void *a, const void *b) {
286         return strcmp(a, b);
287 }