Use xrange() rather than range() for loop iterations.
[blender.git] / source / blender / blenlib / intern / BLI_ghash.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): none yet.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  * A general (pointer -> pointer) hash table ADT
29  */
30
31 #include <stdlib.h>
32 #include <string.h>
33
34 #include "MEM_guardedalloc.h"
35 #include "BLI_ghash.h"
36
37 #include "BLO_sys_types.h" // for intptr_t support
38
39 #ifdef HAVE_CONFIG_H
40 #include <config.h>
41 #endif
42
43 /***/
44
45 static unsigned int hashsizes[]= {
46         1, 3, 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 typedef struct Entry Entry;
55 struct Entry {
56         Entry *next;
57         
58         void *key, *val;
59 };
60
61 struct GHash {
62         GHashHashFP     hashfp;
63         GHashCmpFP      cmpfp;
64         
65         Entry **buckets;
66         int nbuckets, nentries, cursize;
67 };
68
69 /***/
70
71 GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp) {
72         GHash *gh= MEM_mallocN(sizeof(*gh), "GHash");
73         gh->hashfp= hashfp;
74         gh->cmpfp= cmpfp;
75         
76         gh->cursize= 0;
77         gh->nentries= 0;
78         gh->nbuckets= hashsizes[gh->cursize];
79         
80         gh->buckets= malloc(gh->nbuckets*sizeof(*gh->buckets));
81         memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
82         
83         return gh;
84 }
85
86 void BLI_ghash_insert(GHash *gh, void *key, void *val) {
87         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
88         Entry *e= malloc(sizeof(*e));
89
90         e->key= key;
91         e->val= val;
92         e->next= gh->buckets[hash];
93         gh->buckets[hash]= e;
94         
95         if (++gh->nentries>gh->nbuckets*3) {
96                 Entry *e, **old= gh->buckets;
97                 int i, nold= gh->nbuckets;
98                 
99                 gh->nbuckets= hashsizes[++gh->cursize];
100                 gh->buckets= malloc(gh->nbuckets*sizeof(*gh->buckets));
101                 memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
102                 
103                 for (i=0; i<nold; i++) {
104                         for (e= old[i]; e;) {
105                                 Entry *n= e->next;
106                                 
107                                 hash= gh->hashfp(e->key)%gh->nbuckets;
108                                 e->next= gh->buckets[hash];
109                                 gh->buckets[hash]= e;
110                                 
111                                 e= n;
112                         }
113                 }
114                 
115                 free(old);
116         }
117 }
118
119 void* BLI_ghash_lookup(GHash *gh, void *key) 
120 {
121         if(gh) {
122                 unsigned int hash= gh->hashfp(key)%gh->nbuckets;
123                 Entry *e;
124                 
125                 for (e= gh->buckets[hash]; e; e= e->next)
126                         if (gh->cmpfp(key, e->key)==0)
127                                 return e->val;
128         }       
129         return NULL;
130 }
131
132 int BLI_ghash_remove (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
133 {
134         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
135         Entry *e;
136         Entry *p = 0;
137
138         for (e= gh->buckets[hash]; e; e= e->next) {
139                 if (gh->cmpfp(key, e->key)==0) {
140                         Entry *n= e->next;
141
142                         if (keyfreefp) keyfreefp(e->key);
143                         if (valfreefp) valfreefp(e->val);
144                         free(e);
145
146
147                         e= n;
148                         if (p)
149                                 p->next = n;
150                         else
151                                 gh->buckets[hash] = n;
152
153                         --gh->nentries;
154                         return 1;
155                 }
156                 p = e;
157         }
158  
159         return 0;
160 }
161
162 int BLI_ghash_haskey(GHash *gh, void *key) {
163         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
164         Entry *e;
165         
166         for (e= gh->buckets[hash]; e; e= e->next)
167                 if (gh->cmpfp(key, e->key)==0)
168                         return 1;
169         
170         return 0;
171 }
172
173 int BLI_ghash_size(GHash *gh) {
174         return gh->nentries;
175 }
176
177 void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) {
178         int i;
179         
180         for (i=0; i<gh->nbuckets; i++) {
181                 Entry *e;
182                 
183                 for (e= gh->buckets[i]; e; ) {
184                         Entry *n= e->next;
185                         
186                         if (keyfreefp) keyfreefp(e->key);
187                         if (valfreefp) valfreefp(e->val);
188                         free(e);
189                         
190                         e= n;
191                 }
192         }
193         
194         free(gh->buckets);
195         gh->buckets = 0;
196         gh->nentries = 0;
197         gh->nbuckets = 0;
198         MEM_freeN(gh);
199 }
200
201 /***/
202
203 struct GHashIterator {
204         GHash *gh;
205         int curBucket;
206         Entry *curEntry;
207 };
208
209 GHashIterator *BLI_ghashIterator_new(GHash *gh) {
210         GHashIterator *ghi= malloc(sizeof(*ghi));
211         ghi->gh= gh;
212         ghi->curEntry= NULL;
213         ghi->curBucket= -1;
214         while (!ghi->curEntry) {
215                 ghi->curBucket++;
216                 if (ghi->curBucket==ghi->gh->nbuckets)
217                         break;
218                 ghi->curEntry= ghi->gh->buckets[ghi->curBucket];
219         }
220         return ghi;
221 }
222 void BLI_ghashIterator_free(GHashIterator *ghi) {
223         free(ghi);
224 }
225
226 void *BLI_ghashIterator_getKey(GHashIterator *ghi) {
227         return ghi->curEntry?ghi->curEntry->key:NULL;
228 }
229 void *BLI_ghashIterator_getValue(GHashIterator *ghi) {
230         return ghi->curEntry?ghi->curEntry->val:NULL;
231 }
232
233 void BLI_ghashIterator_step(GHashIterator *ghi) {
234         if (ghi->curEntry) {
235         ghi->curEntry= ghi->curEntry->next;
236                 while (!ghi->curEntry) {
237                         ghi->curBucket++;
238                         if (ghi->curBucket==ghi->gh->nbuckets)
239                                 break;
240                         ghi->curEntry= ghi->gh->buckets[ghi->curBucket];
241                 }
242         }
243 }
244 int BLI_ghashIterator_isDone(GHashIterator *ghi) {
245         return !ghi->curEntry;
246 }
247
248 /***/
249
250 unsigned int BLI_ghashutil_ptrhash(void *key) {
251         return (unsigned int) key;
252 }
253 int BLI_ghashutil_ptrcmp(void *a, void *b) {
254         if (a==b)
255                 return 0;
256         else
257                 return (a<b)?-1:1;
258 }
259
260 unsigned int BLI_ghashutil_inthash(void *ptr) {
261         uintptr_t key = (uintptr_t)ptr;
262
263         key += ~(key << 16);
264         key ^=  (key >>  5);
265         key +=  (key <<  3);
266         key ^=  (key >> 13);
267         key += ~(key <<  9);
268         key ^=  (key >> 17);
269
270         return (unsigned int)(key & 0xffffffff);
271 }
272
273 int BLI_ghashutil_intcmp(void *a, void *b) {
274         if (a==b)
275                 return 0;
276         else
277                 return (a<b)?-1:1;
278 }
279
280 unsigned int BLI_ghashutil_strhash(void *ptr) {
281         char *s= ptr;
282         unsigned int i= 0;
283         unsigned char c;
284         
285         while ( (c= *s++) )
286                 i= i*37 + c;
287                 
288         return i;
289 }
290 int BLI_ghashutil_strcmp(void *a, void *b) {
291         return strcmp(a, b);
292 }