Smallhash: refactor and fixes
[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
35  */
36
37 #include <string.h>
38 #include <stdlib.h>
39
40 #include "MEM_guardedalloc.h"
41 #include "BLI_utildefines.h"
42
43 #include "BLI_smallhash.h"
44
45 #include "BLI_strict_flags.h"
46
47 /* SMHASH_CELL_UNUSED means this cell is inside a key series,
48  * while SMHASH_CELL_FREE means this cell terminates a key series.
49  *
50  * no chance of anyone shoving INT32_MAX-2 into a *val pointer, I
51  * imagine.  hopefully.
52  *
53  * note: these have the SMHASH prefix because we may want to make them public.
54  */
55 #define SMHASH_CELL_UNUSED  ((void *)0x7FFFFFFF)
56 #define SMHASH_CELL_FREE    ((void *)0x7FFFFFFD)
57 #define SMHASH_KEY_UNUSED ((uintptr_t)-1)
58
59 /* typically this re-assigns 'h' */
60 #define SMHASH_NEXT(h, hoff)  ( \
61         CHECK_TYPE_INLINE(&(h),    unsigned int *), \
62         CHECK_TYPE_INLINE(&(hoff), unsigned int *), \
63         ((h) + (((hoff) = ((hoff) * 2) + 1), (hoff))) \
64         )
65
66 extern const unsigned int hashsizes[];
67
68 /**
69  * Check if the number of items in the smallhash is large enough to require more buckets.
70  */
71 BLI_INLINE bool smallhash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets)
72 {
73         return nentries * 3 > nbuckets;
74 }
75
76 BLI_INLINE void smallhash_init_empty(SmallHash *sh)
77 {
78         unsigned int i;
79
80         for (i = 0; i < sh->nbuckets; i++) {
81                 sh->buckets[i].key = SMHASH_KEY_UNUSED;
82                 sh->buckets[i].val = SMHASH_CELL_FREE;
83         }
84 }
85
86 BLI_INLINE SmallHashEntry *smallhash_lookup(SmallHash *sh, const uintptr_t key)
87 {
88         SmallHashEntry *e;
89         unsigned int h = (unsigned int)key;
90         unsigned int hoff = 1;
91
92         BLI_assert(key != SMHASH_KEY_UNUSED);
93
94         /* note: there are always more buckets then entries,
95          * so we know there will always be a free bucket if the key isn't found. */
96         for (e = &sh->buckets[h % sh->nbuckets];
97              e->val != SMHASH_CELL_FREE;
98              h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets])
99         {
100                 if (e->key == key) {
101                         /* should never happen because unused keys are zero'd */
102                         BLI_assert(e->val != SMHASH_CELL_UNUSED);
103                         return e;
104                 }
105         }
106
107         return NULL;
108 }
109
110 BLI_INLINE SmallHashEntry *smallhash_lookup_first_free(SmallHash *sh, const uintptr_t key)
111 {
112         SmallHashEntry *e;
113         unsigned int h = (unsigned int)key;
114         unsigned int hoff = 1;
115
116         for (e = &sh->buckets[h % sh->nbuckets];
117              !ELEM(e->val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE);
118              h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets])
119         {
120                 /* pass */
121         }
122
123         return e;
124 }
125
126 BLI_INLINE void smallhash_resize_buckets(SmallHash *sh, const unsigned int nbuckets)
127 {
128         SmallHashEntry *buckets_old = sh->buckets;
129         const unsigned int nbuckets_old = sh->nbuckets;
130         unsigned int i = 0;
131
132         BLI_assert(sh->nbuckets != nbuckets);
133
134         if (buckets_old == sh->buckets_stack && nbuckets <= SMSTACKSIZE) {
135                 SWAP(SmallHashEntry *, sh->buckets_stack, sh->buckets_copy);
136                 sh->buckets = sh->buckets_stack;
137         }
138         else {
139                 sh->buckets = MEM_mallocN(sizeof(*sh->buckets) * nbuckets, __func__);
140         }
141
142         sh->nbuckets = nbuckets;
143
144         smallhash_init_empty(sh);
145
146         for (i = 0; i < nbuckets_old; i++) {
147                 if (!ELEM(buckets_old[i].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
148                         SmallHashEntry *e = smallhash_lookup_first_free(sh, buckets_old[i].key);
149                         e->key = buckets_old[i].key;
150                         e->val = buckets_old[i].val;
151                 }
152         }
153
154         if (buckets_old != sh->buckets_stack && buckets_old != sh->buckets_copy) {
155                 MEM_freeN(buckets_old);
156         }
157 }
158
159 void BLI_smallhash_init(SmallHash *sh)
160 {
161         /* assume 'sh' is uninitialized */
162
163         sh->nentries = 0;
164         sh->cursize = 2;
165         sh->nbuckets = hashsizes[sh->cursize];
166
167         sh->buckets         = sh->_buckets_stack;
168         sh->buckets_copy    = sh->_buckets_copy;
169         sh->buckets_stack   = sh->_buckets_stack;
170
171         smallhash_init_empty(sh);
172 }
173
174 /*NOTE: does *not* free *sh itself!  only the direct data!*/
175 void BLI_smallhash_release(SmallHash *sh)
176 {
177         if (sh->buckets != sh->buckets_stack) {
178                 MEM_freeN(sh->buckets);
179         }
180 }
181
182 void BLI_smallhash_insert(SmallHash *sh, uintptr_t key, void *val)
183 {
184         SmallHashEntry *e;
185
186         BLI_assert(key != SMHASH_KEY_UNUSED);
187         BLI_assert(!ELEM(val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE));
188         BLI_assert(BLI_smallhash_haskey(sh, key) == false);
189
190         if (UNLIKELY(smallhash_test_expand_buckets(++sh->nentries, sh->nbuckets))) {
191                 smallhash_resize_buckets(sh, hashsizes[++sh->cursize]);
192         }
193
194         e = smallhash_lookup_first_free(sh, key);
195         e->key = key;
196         e->val = val;
197 }
198
199 bool BLI_smallhash_remove(SmallHash *sh, uintptr_t key)
200 {
201         SmallHashEntry *e = smallhash_lookup(sh, key);
202
203         if (e) {
204                 e->key = SMHASH_KEY_UNUSED;
205                 e->val = SMHASH_CELL_UNUSED;
206                 sh->nentries--;
207
208                 return true;
209         }
210         else {
211                 return false;
212         }
213 }
214
215 void *BLI_smallhash_lookup(SmallHash *sh, uintptr_t key)
216 {
217         SmallHashEntry *e = smallhash_lookup(sh, key);
218
219         return e ? e->val : NULL;
220 }
221
222 void **BLI_smallhash_lookup_p(SmallHash *sh, uintptr_t key)
223 {
224         SmallHashEntry *e = smallhash_lookup(sh, key);
225
226         return e ? &e->val : NULL;
227 }
228
229 bool BLI_smallhash_haskey(SmallHash *sh, uintptr_t key)
230 {
231         SmallHashEntry *e = smallhash_lookup(sh, key);
232
233         return (e != NULL);
234 }
235
236 int BLI_smallhash_count(SmallHash *sh)
237 {
238         return (int)sh->nentries;
239 }
240
241 void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
242 {
243         while (iter->i < iter->sh->nbuckets) {
244                 if ((iter->sh->buckets[iter->i].val != SMHASH_CELL_UNUSED) &&
245                     (iter->sh->buckets[iter->i].val != SMHASH_CELL_FREE))
246                 {
247                         if (key) {
248                                 *key = iter->sh->buckets[iter->i].key;
249                         }
250
251                         return iter->sh->buckets[iter->i++].val;
252                 }
253
254                 iter->i++;
255         }
256
257         return NULL;
258 }
259
260 void *BLI_smallhash_iternew(SmallHash *sh, SmallHashIter *iter, uintptr_t *key)
261 {
262         iter->sh = sh;
263         iter->i = 0;
264
265         return BLI_smallhash_iternext(iter, key);
266 }
267
268 /* note, this was called _print_smhash in knifetool.c
269  * it may not be intended for general use - campbell */
270 #if 0
271 void BLI_smallhash_print(SmallHash *sh)
272 {
273         unsigned int i, linecol = 79, c = 0;
274
275         printf("{");
276         for (i = 0; i < sh->nbuckets; i++) {
277                 if (sh->buckets[i].val == SMHASH_CELL_UNUSED) {
278                         printf("--u-");
279                 }
280                 else if (sh->buckets[i].val == SMHASH_CELL_FREE) {
281                         printf("--f-");
282                 }
283                 else {
284                         printf("%2x", (unsigned int)sh->buckets[i].key);
285                 }
286
287                 if (i != sh->nbuckets - 1)
288                         printf(", ");
289
290                 c += 6;
291
292                 if (c >= linecol) {
293                         printf("\n ");
294                         c = 0;
295                 }
296         }
297
298         fflush(stdout);
299 }
300 #endif