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