Initial results of my profiling of the animation system.
[blender.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 #include "MEM_guardedalloc.h"
41
42 #include "BLI_mempool.h"
43 #include "BLI_blenlib.h"
44
45 typedef unsigned int    (*GHashHashFP)          (void *key);
46 typedef int                             (*GHashCmpFP)           (void *a, void *b);
47 typedef void                    (*GHashKeyFreeFP)       (void *key);
48 typedef void                    (*GHashValFreeFP)       (void *val);
49
50 typedef struct Entry {
51         struct Entry *next;
52         
53         void *key, *val;
54 } Entry;
55
56 typedef struct GHash {
57         GHashHashFP     hashfp;
58         GHashCmpFP      cmpfp;
59         
60         Entry **buckets;
61         struct BLI_mempool *entrypool;
62         int nbuckets, nentries, cursize;
63 } GHash;
64
65 typedef struct GHashIterator {
66         GHash *gh;
67         int curBucket;
68         struct Entry *curEntry;
69 } GHashIterator;
70
71 GHash*  BLI_ghash_new           (GHashHashFP hashfp, GHashCmpFP cmpfp);
72 void    BLI_ghash_free          (GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
73
74 //BM_INLINE void        BLI_ghash_insert        (GHash *gh, void *key, void *val);
75 //BM_INLINE int         BLI_ghash_remove        (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
76 //BM_INLINE void*       BLI_ghash_lookup        (GHash *gh, void *key);
77 //BM_INLINE int         BLI_ghash_haskey        (GHash *gh, void *key);
78
79 int             BLI_ghash_size          (GHash *gh);
80
81 /* *** */
82
83         /**
84          * Create a new GHashIterator. The hash table must not be mutated
85          * while the iterator is in use, and the iterator will step exactly
86          * BLI_ghash_size(gh) times before becoming done.
87          * 
88          * @param gh The GHash to iterate over.
89          * @return Pointer to a new DynStr.
90          */
91 GHashIterator*  BLI_ghashIterator_new           (GHash *gh);
92         /**
93          * Init an already allocated GHashIterator. The hash table must not
94          * be mutated while the iterator is in use, and the iterator will
95          * step exactly BLI_ghash_size(gh) times before becoming done.
96          * 
97          * @param ghi The GHashIterator to initialize.
98          * @param gh The GHash to iterate over.
99          */
100 void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh);
101         /**
102          * Free a GHashIterator.
103          *
104          * @param ghi The iterator to free.
105          */
106 void                    BLI_ghashIterator_free          (GHashIterator *ghi);
107
108         /**
109          * Retrieve the key from an iterator.
110          *
111          * @param ghi The iterator.
112          * @return The key at the current index, or NULL if the 
113          * iterator is done.
114          */
115 void*                   BLI_ghashIterator_getKey        (GHashIterator *ghi);
116         /**
117          * Retrieve the value from an iterator.
118          *
119          * @param ghi The iterator.
120          * @return The value at the current index, or NULL if the 
121          * iterator is done.
122          */
123 void*                   BLI_ghashIterator_getValue      (GHashIterator *ghi);
124         /**
125          * Steps the iterator to the next index.
126          *
127          * @param ghi The iterator.
128          */
129 void                    BLI_ghashIterator_step          (GHashIterator *ghi);
130         /**
131          * Determine if an iterator is done (has reached the end of
132          * the hash table).
133          *
134          * @param ghi The iterator.
135          * @return True if done, False otherwise.
136          */
137 int                             BLI_ghashIterator_isDone        (GHashIterator *ghi);
138
139 /* *** */
140
141 unsigned int    BLI_ghashutil_ptrhash   (void *key);
142 int                             BLI_ghashutil_ptrcmp    (void *a, void *b);
143
144 unsigned int    BLI_ghashutil_strhash   (void *key);
145 int                             BLI_ghashutil_strcmp    (void *a, void *b);
146
147 unsigned int    BLI_ghashutil_inthash   (void *ptr);
148 int                             BLI_ghashutil_intcmp(void *a, void *b);
149
150 /*begin of macro-inlined functions*/
151 extern unsigned int hashsizes[];
152
153 #if 0
154 #define BLI_ghash_insert(gh, _k, _v){\
155         unsigned int _hash= (gh)->hashfp(_k)%gh->nbuckets;\
156         Entry *_e= BLI_mempool_alloc((gh)->entrypool);\
157         _e->key= _k;\
158         _e->val= _v;\
159         _e->next= (gh)->buckets[_hash];\
160         (gh)->buckets[_hash]= _e;\
161         if (++(gh)->nentries>(gh)->nbuckets*3) {\
162                 Entry *_e, **_old= (gh)->buckets;\
163                 int _i, _nold= (gh)->nbuckets;\
164                 (gh)->nbuckets= hashsizes[++(gh)->cursize];\
165                 (gh)->buckets= malloc((gh)->nbuckets*sizeof(*(gh)->buckets));\
166                 memset((gh)->buckets, 0, (gh)->nbuckets*sizeof(*(gh)->buckets));\
167                 for (_i=0; _i<_nold; _i++) {\
168                         for (_e= _old[_i]; _e;) {\
169                                 Entry *_n= _e->next;\
170                                 _hash= (gh)->hashfp(_e->key)%(gh)->nbuckets;\
171                                 _e->next= (gh)->buckets[_hash];\
172                                 (gh)->buckets[_hash]= _e;\
173                                 _e= _n;\
174                         }\
175                 }\
176                 free(_old); } }
177 #endif
178
179 /*---------inlined functions---------*/
180 BM_INLINE void BLI_ghash_insert(GHash *gh, void *key, void *val) {
181         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
182         Entry *e= (Entry*) BLI_mempool_alloc(gh->entrypool);
183
184         e->key= key;
185         e->val= val;
186         e->next= gh->buckets[hash];
187         gh->buckets[hash]= e;
188         
189         if (++gh->nentries>(float)gh->nbuckets/2) {
190                 Entry *e, **old= gh->buckets;
191                 int i, nold= gh->nbuckets;
192                 
193                 gh->nbuckets= hashsizes[++gh->cursize];
194                 gh->buckets= (Entry**)MEM_mallocN(gh->nbuckets*sizeof(*gh->buckets), "buckets");
195                 memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
196                 
197                 for (i=0; i<nold; i++) {
198                         for (e= old[i]; e;) {
199                                 Entry *n= e->next;
200                                 
201                                 hash= gh->hashfp(e->key)%gh->nbuckets;
202                                 e->next= gh->buckets[hash];
203                                 gh->buckets[hash]= e;
204                                 
205                                 e= n;
206                         }
207                 }
208                 
209                 MEM_freeN(old);
210         }
211 }
212
213 BM_INLINE void* BLI_ghash_lookup(GHash *gh, void *key) 
214 {
215         if(gh) {
216                 unsigned int hash= gh->hashfp(key)%gh->nbuckets;
217                 Entry *e;
218                 
219                 for (e= gh->buckets[hash]; e; e= e->next)
220                         if (gh->cmpfp(key, e->key)==0)
221                                 return e->val;
222         }       
223         return NULL;
224 }
225
226 BM_INLINE int BLI_ghash_remove (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
227 {
228         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
229         Entry *e;
230         Entry *p = 0;
231
232         for (e= gh->buckets[hash]; e; e= e->next) {
233                 if (gh->cmpfp(key, e->key)==0) {
234                         Entry *n= e->next;
235
236                         if (keyfreefp) keyfreefp(e->key);
237                         if (valfreefp) valfreefp(e->val);
238                         BLI_mempool_free(gh->entrypool, e);
239
240
241                         e= n;
242                         if (p)
243                                 p->next = n;
244                         else
245                                 gh->buckets[hash] = n;
246
247                         --gh->nentries;
248                         return 1;
249                 }
250                 p = e;
251         }
252  
253         return 0;
254 }
255
256 BM_INLINE int BLI_ghash_haskey(GHash *gh, void *key) {
257         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
258         Entry *e;
259         
260         for (e= gh->buckets[hash]; e; e= e->next)
261                 if (gh->cmpfp(key, e->key)==0)
262                         return 1;
263         
264         return 0;
265 }
266
267 #endif