Fix: Compile error due to missing #define for MSVC9 (VisualC++ 2008)
[blender.git] / source / blender / blenlib / intern / smallhash.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) 2008 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Joseph Eagar.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenlib/intern/smallhash.c
29  *  \ingroup bli
30  *
31  * A light stack-friendly hash library, it uses stack space for smallish hash tables
32  * but falls back to heap memory once the stack limits reached.
33  *
34  * based on a doubling non-chaining approach  which uses more buckets then entries
35  * stepping over buckets when two keys share the same hash so any key can find a free bucket.
36  *
37  *
38  * #SmallHashEntry.key
39  * - ``SMHASH_KEY_UNUSED`` means the key in the cell has not been initialized.
40  *
41  * #SmallHashEntry.val
42  * - ``SMHASH_CELL_UNUSED`` means this cell is inside a key series.
43  * - ``SMHASH_CELL_FREE`` means this cell terminates a key series.
44  *
45  * Note that the values and keys are often pointers or index values,
46  * use the maximum values to avoid real pointers colliding with magic numbers.
47  *
48  * \note these have the SMHASH prefix because we may want to make them public.
49  */
50
51 #include <string.h>
52 #include <stdlib.h>
53 #include <BLI_sys_types.h>
54
55 #include "MEM_guardedalloc.h"
56
57 #include "BLI_utildefines.h"
58 #include "BLI_alloca.h"
59
60 #include "BLI_smallhash.h"
61
62 #include "BLI_strict_flags.h"
63
64 #define SMHASH_KEY_UNUSED   ((uintptr_t)(UINTPTR_MAX - 0))
65 #define SMHASH_CELL_FREE    ((void *)   (UINTPTR_MAX - 1))
66 #define SMHASH_CELL_UNUSED  ((void *)   (UINTPTR_MAX - 2))
67
68 /* typically this re-assigns 'h' */
69 #define SMHASH_NEXT(h, hoff)  ( \
70         CHECK_TYPE_INLINE(&(h),    unsigned int *), \
71         CHECK_TYPE_INLINE(&(hoff), unsigned int *), \
72         ((h) + (((hoff) = ((hoff) * 2) + 1), (hoff))) \
73         )
74
75
76 /* nothing uses BLI_smallhash_remove yet */
77 // #define USE_REMOVE
78
79 BLI_INLINE bool smallhash_val_is_used(const void *val)
80 {
81 #ifdef USE_REMOVE
82         return !ELEM(val, SMHASH_CELL_FREE, SMHASH_CELL_UNUSED);
83 #else
84         return (val != SMHASH_CELL_FREE);
85 #endif
86 }
87
88 extern const unsigned int hashsizes[];
89
90 /**
91  * Check if the number of items in the smallhash is large enough to require more buckets.
92  */
93 BLI_INLINE bool smallhash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets)
94 {
95         /* (approx * 1.5) */
96         return (nentries + (nentries >> 1)) > nbuckets;
97 }
98
99 BLI_INLINE void smallhash_init_empty(SmallHash *sh)
100 {
101         unsigned int i;
102
103         for (i = 0; i < sh->nbuckets; i++) {
104                 sh->buckets[i].key = SMHASH_KEY_UNUSED;
105                 sh->buckets[i].val = SMHASH_CELL_FREE;
106         }
107 }
108
109 /**
110  * Increase initial bucket size to match a reserved amount.
111  */
112 BLI_INLINE void smallhash_buckets_reserve(SmallHash *sh, const unsigned int nentries_reserve)
113 {
114         while (smallhash_test_expand_buckets(nentries_reserve, sh->nbuckets)) {
115                 sh->nbuckets = hashsizes[++sh->cursize];
116         }
117 }
118
119 BLI_INLINE SmallHashEntry *smallhash_lookup(SmallHash *sh, const uintptr_t key)
120 {
121         SmallHashEntry *e;
122         unsigned int h = (unsigned int)key;
123         unsigned int hoff = 1;
124
125         BLI_assert(key != SMHASH_KEY_UNUSED);
126
127         /* note: there are always more buckets then entries,
128          * so we know there will always be a free bucket if the key isn't found. */
129         for (e = &sh->buckets[h % sh->nbuckets];
130              e->val != SMHASH_CELL_FREE;
131              h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets])
132         {
133                 if (e->key == key) {
134                         /* should never happen because unused keys are zero'd */
135                         BLI_assert(e->val != SMHASH_CELL_UNUSED);
136                         return e;
137                 }
138         }
139
140         return NULL;
141 }
142
143 BLI_INLINE SmallHashEntry *smallhash_lookup_first_free(SmallHash *sh, const uintptr_t key)
144 {
145         SmallHashEntry *e;
146         unsigned int h = (unsigned int)key;
147         unsigned int hoff = 1;
148
149         for (e = &sh->buckets[h % sh->nbuckets];
150              smallhash_val_is_used(e->val);
151              h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets])
152         {
153                 /* pass */
154         }
155
156         return e;
157 }
158
159 BLI_INLINE void smallhash_resize_buckets(SmallHash *sh, const unsigned int nbuckets)
160 {
161         SmallHashEntry *buckets_old = sh->buckets;
162         const unsigned int nbuckets_old = sh->nbuckets;
163         const bool was_alloc = (buckets_old != sh->buckets_stack);
164         unsigned int i = 0;
165
166         BLI_assert(sh->nbuckets != nbuckets);
167         if (nbuckets <= SMSTACKSIZE) {
168                 const size_t size = sizeof(*buckets_old) * nbuckets_old;
169                 buckets_old = alloca(size);
170                 memcpy(buckets_old, sh->buckets, size);
171
172                 sh->buckets = sh->buckets_stack;
173         }
174         else {
175                 sh->buckets = MEM_mallocN(sizeof(*sh->buckets) * nbuckets, __func__);
176         }
177
178         sh->nbuckets = nbuckets;
179
180         smallhash_init_empty(sh);
181
182         for (i = 0; i < nbuckets_old; i++) {
183                 if (smallhash_val_is_used(buckets_old[i].val)) {
184                         SmallHashEntry *e = smallhash_lookup_first_free(sh, buckets_old[i].key);
185                         e->key = buckets_old[i].key;
186                         e->val = buckets_old[i].val;
187                 }
188         }
189
190         if (was_alloc) {
191                 MEM_freeN(buckets_old);
192         }
193 }
194
195 void BLI_smallhash_init_ex(SmallHash *sh,
196                            const unsigned int nentries_reserve)
197 {
198         /* assume 'sh' is uninitialized */
199
200         sh->nentries = 0;
201         sh->cursize = 2;
202         sh->nbuckets = hashsizes[sh->cursize];
203
204         sh->buckets = sh->buckets_stack;
205
206         if (nentries_reserve) {
207                 smallhash_buckets_reserve(sh, nentries_reserve);
208
209                 if (sh->nbuckets > SMSTACKSIZE) {
210                         sh->buckets = MEM_mallocN(sizeof(*sh->buckets) * sh->nbuckets, __func__);
211                 }
212         }
213
214         smallhash_init_empty(sh);
215 }
216
217 void BLI_smallhash_init(SmallHash *sh)
218 {
219         BLI_smallhash_init_ex(sh, 0);
220 }
221
222 /*NOTE: does *not* free *sh itself!  only the direct data!*/
223 void BLI_smallhash_release(SmallHash *sh)
224 {
225         if (sh->buckets != sh->buckets_stack) {
226                 MEM_freeN(sh->buckets);
227         }
228 }
229
230 void BLI_smallhash_insert(SmallHash *sh, uintptr_t key, void *val)
231 {
232         SmallHashEntry *e;
233
234         BLI_assert(key != SMHASH_KEY_UNUSED);
235         BLI_assert(smallhash_val_is_used(val));
236         BLI_assert(BLI_smallhash_haskey(sh, key) == false);
237
238         if (UNLIKELY(smallhash_test_expand_buckets(++sh->nentries, sh->nbuckets))) {
239                 smallhash_resize_buckets(sh, hashsizes[++sh->cursize]);
240         }
241
242         e = smallhash_lookup_first_free(sh, key);
243         e->key = key;
244         e->val = val;
245 }
246
247 #ifdef USE_REMOVE
248 bool BLI_smallhash_remove(SmallHash *sh, uintptr_t key)
249 {
250         SmallHashEntry *e = smallhash_lookup(sh, key);
251
252         if (e) {
253                 e->key = SMHASH_KEY_UNUSED;
254                 e->val = SMHASH_CELL_UNUSED;
255                 sh->nentries--;
256
257                 return true;
258         }
259         else {
260                 return false;
261         }
262 }
263 #endif
264
265 void *BLI_smallhash_lookup(SmallHash *sh, uintptr_t key)
266 {
267         SmallHashEntry *e = smallhash_lookup(sh, key);
268
269         return e ? e->val : NULL;
270 }
271
272 void **BLI_smallhash_lookup_p(SmallHash *sh, uintptr_t key)
273 {
274         SmallHashEntry *e = smallhash_lookup(sh, key);
275
276         return e ? &e->val : NULL;
277 }
278
279 bool BLI_smallhash_haskey(SmallHash *sh, uintptr_t key)
280 {
281         SmallHashEntry *e = smallhash_lookup(sh, key);
282
283         return (e != NULL);
284 }
285
286 int BLI_smallhash_count(SmallHash *sh)
287 {
288         return (int)sh->nentries;
289 }
290
291 void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
292 {
293         while (iter->i < iter->sh->nbuckets) {
294                 if (smallhash_val_is_used(iter->sh->buckets[iter->i].val)) {
295                         if (key) {
296                                 *key = iter->sh->buckets[iter->i].key;
297                         }
298
299                         return iter->sh->buckets[iter->i++].val;
300                 }
301
302                 iter->i++;
303         }
304
305         return NULL;
306 }
307
308 void *BLI_smallhash_iternew(SmallHash *sh, SmallHashIter *iter, uintptr_t *key)
309 {
310         iter->sh = sh;
311         iter->i = 0;
312
313         return BLI_smallhash_iternext(iter, key);
314 }
315
316 /* note, this was called _print_smhash in knifetool.c
317  * it may not be intended for general use - campbell */
318 #if 0
319 void BLI_smallhash_print(SmallHash *sh)
320 {
321         unsigned int i, linecol = 79, c = 0;
322
323         printf("{");
324         for (i = 0; i < sh->nbuckets; i++) {
325                 if (sh->buckets[i].val == SMHASH_CELL_UNUSED) {
326                         printf("--u-");
327                 }
328                 else if (sh->buckets[i].val == SMHASH_CELL_FREE) {
329                         printf("--f-");
330                 }
331                 else {
332                         printf("%2x", (unsigned int)sh->buckets[i].key);
333                 }
334
335                 if (i != sh->nbuckets - 1)
336                         printf(", ");
337
338                 c += 6;
339
340                 if (c >= linecol) {
341                         printf("\n ");
342                         c = 0;
343                 }
344         }
345
346         fflush(stdout);
347 }
348 #endif