commit before doing some hefty shapekey change, will break compilation
[blender-staging.git] / source / blender / blenlib / BLI_ghash.h
1 /**
2  * A general (pointer -> pointer) hash table ADT
3  * 
4  * $Id$
5  *
6  * ***** BEGIN GPL LICENSE BLOCK *****
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, write to the Free Software Foundation,
20  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
21  *
22  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
23  * All rights reserved.
24  *
25  * The Original Code is: all of this file.
26  *
27  * Contributor(s): none yet.
28  *
29  * ***** END GPL LICENSE BLOCK *****
30  */
31  
32 #ifndef BLI_GHASH_H
33 #define BLI_GHASH_H
34
35 #include "stdio.h"
36 #include "stdlib.h"
37 #include "string.h"
38
39 #include "BKE_utildefines.h"
40
41 #include "BLI_mempool.h"
42 #include "BLI_blenlib.h"
43
44 typedef unsigned int    (*GHashHashFP)          (void *key);
45 typedef int                             (*GHashCmpFP)           (void *a, void *b);
46 typedef void                    (*GHashKeyFreeFP)       (void *key);
47 typedef void                    (*GHashValFreeFP)       (void *val);
48
49 typedef struct Entry {
50         struct Entry *next;
51         
52         void *key, *val;
53 } Entry;
54
55 typedef struct GHash {
56         GHashHashFP     hashfp;
57         GHashCmpFP      cmpfp;
58         
59         Entry **buckets;
60         struct BLI_mempool *entrypool;
61         int nbuckets, nentries, cursize;
62 } GHash;
63
64 typedef struct GHashIterator {
65         GHash *gh;
66         int curBucket;
67         struct Entry *curEntry;
68 } GHashIterator;
69
70 GHash*  BLI_ghash_new           (GHashHashFP hashfp, GHashCmpFP cmpfp);
71 void    BLI_ghash_free          (GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
72
73 //BM_INLINE void        BLI_ghash_insert        (GHash *gh, void *key, void *val);
74 //BM_INLINE int         BLI_ghash_remove        (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
75 //BM_INLINE void*       BLI_ghash_lookup        (GHash *gh, void *key);
76 //BM_INLINE int         BLI_ghash_haskey        (GHash *gh, void *key);
77
78 int             BLI_ghash_size          (GHash *gh);
79
80 /* *** */
81
82         /**
83          * Create a new GHashIterator. The hash table must not be mutated
84          * while the iterator is in use, and the iterator will step exactly
85          * BLI_ghash_size(gh) times before becoming done.
86          * 
87          * @param gh The GHash to iterate over.
88          * @return Pointer to a new DynStr.
89          */
90 GHashIterator*  BLI_ghashIterator_new           (GHash *gh);
91         /**
92          * Init an already allocated GHashIterator. The hash table must not
93          * be mutated while the iterator is in use, and the iterator will
94          * step exactly BLI_ghash_size(gh) times before becoming done.
95          * 
96          * @param ghi The GHashIterator to initialize.
97          * @param gh The GHash to iterate over.
98          */
99 void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh);
100         /**
101          * Free a GHashIterator.
102          *
103          * @param ghi The iterator to free.
104          */
105 void                    BLI_ghashIterator_free          (GHashIterator *ghi);
106
107         /**
108          * Retrieve the key from an iterator.
109          *
110          * @param ghi The iterator.
111          * @return The key at the current index, or NULL if the 
112          * iterator is done.
113          */
114 void*                   BLI_ghashIterator_getKey        (GHashIterator *ghi);
115         /**
116          * Retrieve the value from an iterator.
117          *
118          * @param ghi The iterator.
119          * @return The value at the current index, or NULL if the 
120          * iterator is done.
121          */
122 void*                   BLI_ghashIterator_getValue      (GHashIterator *ghi);
123         /**
124          * Steps the iterator to the next index.
125          *
126          * @param ghi The iterator.
127          */
128 void                    BLI_ghashIterator_step          (GHashIterator *ghi);
129         /**
130          * Determine if an iterator is done (has reached the end of
131          * the hash table).
132          *
133          * @param ghi The iterator.
134          * @return True if done, False otherwise.
135          */
136 int                             BLI_ghashIterator_isDone        (GHashIterator *ghi);
137
138 /* *** */
139
140 unsigned int    BLI_ghashutil_ptrhash   (void *key);
141 int                             BLI_ghashutil_ptrcmp    (void *a, void *b);
142
143 unsigned int    BLI_ghashutil_strhash   (void *key);
144 int                             BLI_ghashutil_strcmp    (void *a, void *b);
145
146 unsigned int    BLI_ghashutil_inthash   (void *ptr);
147 int                             BLI_ghashutil_intcmp(void *a, void *b);
148
149 /*begin of macro-inlined functions*/
150 extern unsigned int hashsizes[];
151
152 #if 0
153 #define BLI_ghash_insert(gh, _k, _v){\
154         unsigned int _hash= (gh)->hashfp(_k)%gh->nbuckets;\
155         Entry *_e= BLI_mempool_alloc((gh)->entrypool);\
156         _e->key= _k;\
157         _e->val= _v;\
158         _e->next= (gh)->buckets[_hash];\
159         (gh)->buckets[_hash]= _e;\
160         if (++(gh)->nentries>(gh)->nbuckets*3) {\
161                 Entry *_e, **_old= (gh)->buckets;\
162                 int _i, _nold= (gh)->nbuckets;\
163                 (gh)->nbuckets= hashsizes[++(gh)->cursize];\
164                 (gh)->buckets= malloc((gh)->nbuckets*sizeof(*(gh)->buckets));\
165                 memset((gh)->buckets, 0, (gh)->nbuckets*sizeof(*(gh)->buckets));\
166                 for (_i=0; _i<_nold; _i++) {\
167                         for (_e= _old[_i]; _e;) {\
168                                 Entry *_n= _e->next;\
169                                 _hash= (gh)->hashfp(_e->key)%(gh)->nbuckets;\
170                                 _e->next= (gh)->buckets[_hash];\
171                                 (gh)->buckets[_hash]= _e;\
172                                 _e= _n;\
173                         }\
174                 }\
175                 free(_old); } }
176 #endif
177
178 /*---------inlined functions---------*/
179 BM_INLINE void BLI_ghash_insert(GHash *gh, void *key, void *val) {
180         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
181         Entry *e= (Entry*) BLI_mempool_alloc(gh->entrypool);
182
183         e->key= key;
184         e->val= val;
185         e->next= gh->buckets[hash];
186         gh->buckets[hash]= e;
187         
188         if (++gh->nentries>gh->nbuckets*3) {
189                 Entry *e, **old= gh->buckets;
190                 int i, nold= gh->nbuckets;
191                 
192                 gh->nbuckets= hashsizes[++gh->cursize];
193                 gh->buckets= malloc(gh->nbuckets*sizeof(*gh->buckets));
194                 memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
195                 
196                 for (i=0; i<nold; i++) {
197                         for (e= old[i]; e;) {
198                                 Entry *n= e->next;
199                                 
200                                 hash= gh->hashfp(e->key)%gh->nbuckets;
201                                 e->next= gh->buckets[hash];
202                                 gh->buckets[hash]= e;
203                                 
204                                 e= n;
205                         }
206                 }
207                 
208                 free(old);
209         }
210 }
211
212 BM_INLINE void* BLI_ghash_lookup(GHash *gh, void *key) 
213 {
214         if(gh) {
215                 unsigned int hash= gh->hashfp(key)%gh->nbuckets;
216                 Entry *e;
217                 
218                 for (e= gh->buckets[hash]; e; e= e->next)
219                         if (gh->cmpfp(key, e->key)==0)
220                                 return e->val;
221         }       
222         return NULL;
223 }
224
225 BM_INLINE int BLI_ghash_remove (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
226 {
227         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
228         Entry *e;
229         Entry *p = 0;
230
231         for (e= gh->buckets[hash]; e; e= e->next) {
232                 if (gh->cmpfp(key, e->key)==0) {
233                         Entry *n= e->next;
234
235                         if (keyfreefp) keyfreefp(e->key);
236                         if (valfreefp) valfreefp(e->val);
237                         BLI_mempool_free(gh->entrypool, e);
238
239
240                         e= n;
241                         if (p)
242                                 p->next = n;
243                         else
244                                 gh->buckets[hash] = n;
245
246                         --gh->nentries;
247                         return 1;
248                 }
249                 p = e;
250         }
251  
252         return 0;
253 }
254
255 BM_INLINE int BLI_ghash_haskey(GHash *gh, void *key) {
256         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
257         Entry *e;
258         
259         for (e= gh->buckets[hash]; e; e= e->next)
260                 if (gh->cmpfp(key, e->key)==0)
261                         return 1;
262         
263         return 0;
264 }
265
266 #endif