Cleanup: remove redundant, invalid info from headers
[blender.git] / source / blender / blenlib / intern / smallhash.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2008 Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file blender/blenlib/intern/smallhash.c
21  *  \ingroup bli
22  *
23  * A light stack-friendly hash library, it uses stack space for relatively small, fixed size hash tables
24  * but falls back to heap memory once the stack limits reached (#SMSTACKSIZE).
25  *
26  * based on a doubling hashing approach (non-chaining) which uses more buckets then entries
27  * stepping over buckets when two keys share the same hash so any key can find a free bucket.
28  *
29  * See: https://en.wikipedia.org/wiki/Double_hashing
30  *
31  * \warning This should _only_ be used for small hashes where allocating a hash every time is unacceptable.
32  * Otherwise #GHash should be used instead.
33  *
34  * #SmallHashEntry.key
35  * - ``SMHASH_KEY_UNUSED`` means the key in the cell has not been initialized.
36  *
37  * #SmallHashEntry.val
38  * - ``SMHASH_CELL_UNUSED`` means this cell is inside a key series.
39  * - ``SMHASH_CELL_FREE`` means this cell terminates a key series.
40  *
41  * Note that the values and keys are often pointers or index values,
42  * use the maximum values to avoid real pointers colliding with magic numbers.
43  */
44
45 #include <string.h>
46 #include <stdlib.h>
47
48 #include "BLI_sys_types.h"
49
50 #include "MEM_guardedalloc.h"
51
52 #include "BLI_utildefines.h"
53
54 #include "BLI_smallhash.h"
55
56 #include "BLI_strict_flags.h"
57
58 #define SMHASH_KEY_UNUSED   ((uintptr_t)(UINTPTR_MAX - 0))
59 #define SMHASH_CELL_FREE    ((void *)   (UINTPTR_MAX - 1))
60 #define SMHASH_CELL_UNUSED  ((void *)   (UINTPTR_MAX - 2))
61
62 /* typically this re-assigns 'h' */
63 #define SMHASH_NEXT(h, hoff)  ( \
64         CHECK_TYPE_INLINE(&(h),    uint *), \
65         CHECK_TYPE_INLINE(&(hoff), uint *), \
66         ((h) + (((hoff) = ((hoff) * 2) + 1), (hoff))) \
67         )
68
69
70 /* nothing uses BLI_smallhash_remove yet */
71 // #define USE_REMOVE
72
73 BLI_INLINE bool smallhash_val_is_used(const void *val)
74 {
75 #ifdef USE_REMOVE
76         return !ELEM(val, SMHASH_CELL_FREE, SMHASH_CELL_UNUSED);
77 #else
78         return (val != SMHASH_CELL_FREE);
79 #endif
80 }
81
82 extern const uint hashsizes[];
83
84 BLI_INLINE uint smallhash_key(const uintptr_t key)
85 {
86         return (uint)key;
87 }
88
89 /**
90  * Check if the number of items in the smallhash is large enough to require more buckets.
91  */
92 BLI_INLINE bool smallhash_test_expand_buckets(const uint nentries, const uint nbuckets)
93 {
94         /* (approx * 1.5) */
95         return (nentries + (nentries >> 1)) > nbuckets;
96 }
97
98 BLI_INLINE void smallhash_init_empty(SmallHash *sh)
99 {
100         uint i;
101
102         for (i = 0; i < sh->nbuckets; i++) {
103                 sh->buckets[i].key = SMHASH_KEY_UNUSED;
104                 sh->buckets[i].val = SMHASH_CELL_FREE;
105         }
106 }
107
108 /**
109  * Increase initial bucket size to match a reserved amount.
110  */
111 BLI_INLINE void smallhash_buckets_reserve(SmallHash *sh, const uint nentries_reserve)
112 {
113         while (smallhash_test_expand_buckets(nentries_reserve, sh->nbuckets)) {
114                 sh->nbuckets = hashsizes[++sh->cursize];
115         }
116 }
117
118 BLI_INLINE SmallHashEntry *smallhash_lookup(const SmallHash *sh, const uintptr_t key)
119 {
120         SmallHashEntry *e;
121         uint h = smallhash_key(key);
122         uint hoff = 1;
123
124         BLI_assert(key != SMHASH_KEY_UNUSED);
125
126         /* note: there are always more buckets than entries,
127          * so we know there will always be a free bucket if the key isn't found. */
128         for (e = &sh->buckets[h % sh->nbuckets];
129              e->val != SMHASH_CELL_FREE;
130              h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets])
131         {
132                 if (e->key == key) {
133                         /* should never happen because unused keys are zero'd */
134                         BLI_assert(e->val != SMHASH_CELL_UNUSED);
135                         return e;
136                 }
137         }
138
139         return NULL;
140 }
141
142 BLI_INLINE SmallHashEntry *smallhash_lookup_first_free(SmallHash *sh, const uintptr_t key)
143 {
144         SmallHashEntry *e;
145         uint h = smallhash_key(key);
146         uint hoff = 1;
147
148         for (e = &sh->buckets[h % sh->nbuckets];
149              smallhash_val_is_used(e->val);
150              h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets])
151         {
152                 /* pass */
153         }
154
155         return e;
156 }
157
158 BLI_INLINE void smallhash_resize_buckets(SmallHash *sh, const uint nbuckets)
159 {
160         SmallHashEntry *buckets_old = sh->buckets;
161         const uint nbuckets_old = sh->nbuckets;
162         const bool was_alloc = (buckets_old != sh->buckets_stack);
163         uint i = 0;
164
165         BLI_assert(sh->nbuckets != nbuckets);
166         if (nbuckets <= SMSTACKSIZE) {
167                 const size_t size = sizeof(*buckets_old) * nbuckets_old;
168                 buckets_old = alloca(size);
169                 memcpy(buckets_old, sh->buckets, size);
170
171                 sh->buckets = sh->buckets_stack;
172         }
173         else {
174                 sh->buckets = MEM_mallocN(sizeof(*sh->buckets) * nbuckets, __func__);
175         }
176
177         sh->nbuckets = nbuckets;
178
179         smallhash_init_empty(sh);
180
181         for (i = 0; i < nbuckets_old; i++) {
182                 if (smallhash_val_is_used(buckets_old[i].val)) {
183                         SmallHashEntry *e = smallhash_lookup_first_free(sh, buckets_old[i].key);
184                         e->key = buckets_old[i].key;
185                         e->val = buckets_old[i].val;
186                 }
187         }
188
189         if (was_alloc) {
190                 MEM_freeN(buckets_old);
191         }
192 }
193
194 void BLI_smallhash_init_ex(SmallHash *sh,
195                            const uint nentries_reserve)
196 {
197         /* assume 'sh' is uninitialized */
198
199         sh->nentries = 0;
200         sh->cursize = 2;
201         sh->nbuckets = hashsizes[sh->cursize];
202
203         sh->buckets = sh->buckets_stack;
204
205         if (nentries_reserve) {
206                 smallhash_buckets_reserve(sh, nentries_reserve);
207
208                 if (sh->nbuckets > SMSTACKSIZE) {
209                         sh->buckets = MEM_mallocN(sizeof(*sh->buckets) * sh->nbuckets, __func__);
210                 }
211         }
212
213         smallhash_init_empty(sh);
214 }
215
216 void BLI_smallhash_init(SmallHash *sh)
217 {
218         BLI_smallhash_init_ex(sh, 0);
219 }
220
221 /* NOTE: does *not* free *sh itself!  only the direct data! */
222 void BLI_smallhash_release(SmallHash *sh)
223 {
224         if (sh->buckets != sh->buckets_stack) {
225                 MEM_freeN(sh->buckets);
226         }
227 }
228
229 void BLI_smallhash_insert(SmallHash *sh, uintptr_t key, void *val)
230 {
231         SmallHashEntry *e;
232
233         BLI_assert(key != SMHASH_KEY_UNUSED);
234         BLI_assert(smallhash_val_is_used(val));
235         BLI_assert(BLI_smallhash_haskey(sh, key) == false);
236
237         if (UNLIKELY(smallhash_test_expand_buckets(++sh->nentries, sh->nbuckets))) {
238                 smallhash_resize_buckets(sh, hashsizes[++sh->cursize]);
239         }
240
241         e = smallhash_lookup_first_free(sh, key);
242         e->key = key;
243         e->val = val;
244 }
245
246 /**
247  * Inserts a new value to a key that may already be in ghash.
248  *
249  * Avoids #BLI_smallhash_remove, #BLI_smallhash_insert calls (double lookups)
250  *
251  * \returns true if a new key has been added.
252  */
253 bool BLI_smallhash_reinsert(SmallHash *sh, uintptr_t key, void *item)
254 {
255         SmallHashEntry *e = smallhash_lookup(sh, key);
256         if (e) {
257                 e->val = item;
258                 return false;
259         }
260         else {
261                 BLI_smallhash_insert(sh, key, item);
262                 return true;
263         }
264 }
265
266 #ifdef USE_REMOVE
267 bool BLI_smallhash_remove(SmallHash *sh, uintptr_t key)
268 {
269         SmallHashEntry *e = smallhash_lookup(sh, key);
270
271         if (e) {
272                 e->key = SMHASH_KEY_UNUSED;
273                 e->val = SMHASH_CELL_UNUSED;
274                 sh->nentries--;
275
276                 return true;
277         }
278         else {
279                 return false;
280         }
281 }
282 #endif
283
284 void *BLI_smallhash_lookup(const SmallHash *sh, uintptr_t key)
285 {
286         SmallHashEntry *e = smallhash_lookup(sh, key);
287
288         return e ? e->val : NULL;
289 }
290
291 void **BLI_smallhash_lookup_p(const SmallHash *sh, uintptr_t key)
292 {
293         SmallHashEntry *e = smallhash_lookup(sh, key);
294
295         return e ? &e->val : NULL;
296 }
297
298 bool BLI_smallhash_haskey(const SmallHash *sh, uintptr_t key)
299 {
300         SmallHashEntry *e = smallhash_lookup(sh, key);
301
302         return (e != NULL);
303 }
304
305 int BLI_smallhash_len(const SmallHash *sh)
306 {
307         return (int)sh->nentries;
308 }
309
310 BLI_INLINE SmallHashEntry *smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
311 {
312         while (iter->i < iter->sh->nbuckets) {
313                 if (smallhash_val_is_used(iter->sh->buckets[iter->i].val)) {
314                         if (key) {
315                                 *key = iter->sh->buckets[iter->i].key;
316                         }
317
318                         return &iter->sh->buckets[iter->i++];
319                 }
320
321                 iter->i++;
322         }
323
324         return NULL;
325 }
326
327 void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
328 {
329         SmallHashEntry *e = smallhash_iternext(iter, key);
330
331         return e ? e->val : NULL;
332 }
333
334 void **BLI_smallhash_iternext_p(SmallHashIter *iter, uintptr_t *key)
335 {
336         SmallHashEntry *e = smallhash_iternext(iter, key);
337
338         return e ? &e->val : NULL;
339 }
340
341 void *BLI_smallhash_iternew(const SmallHash *sh, SmallHashIter *iter, uintptr_t *key)
342 {
343         iter->sh = sh;
344         iter->i = 0;
345
346         return BLI_smallhash_iternext(iter, key);
347 }
348
349 void **BLI_smallhash_iternew_p(const SmallHash *sh, SmallHashIter *iter, uintptr_t *key)
350 {
351         iter->sh = sh;
352         iter->i = 0;
353
354         return BLI_smallhash_iternext_p(iter, key);
355 }
356
357
358 /** \name Debugging & Introspection
359  * \{ */
360
361 /* note, this was called _print_smhash in knifetool.c
362  * it may not be intended for general use - campbell */
363 #if 0
364 void BLI_smallhash_print(SmallHash *sh)
365 {
366         uint i, linecol = 79, c = 0;
367
368         printf("{");
369         for (i = 0; i < sh->nbuckets; i++) {
370                 if (sh->buckets[i].val == SMHASH_CELL_UNUSED) {
371                         printf("--u-");
372                 }
373                 else if (sh->buckets[i].val == SMHASH_CELL_FREE) {
374                         printf("--f-");
375                 }
376                 else {
377                         printf("%2x", (uint)sh->buckets[i].key);
378                 }
379
380                 if (i != sh->nbuckets - 1)
381                         printf(", ");
382
383                 c += 6;
384
385                 if (c >= linecol) {
386                         printf("\n ");
387                         c = 0;
388                 }
389         }
390
391         fflush(stdout);
392 }
393 #endif
394
395 #ifdef DEBUG
396 /**
397  * Measure how well the hash function performs
398  * (1.0 is perfect - no stepping needed).
399  *
400  * Smaller is better!
401  */
402 double BLI_smallhash_calc_quality(SmallHash *sh)
403 {
404         uint64_t sum = 0;
405         uint i;
406
407         if (sh->nentries == 0)
408                 return -1.0;
409
410         for (i = 0; i < sh->nbuckets; i++) {
411                 if (sh->buckets[i].key != SMHASH_KEY_UNUSED) {
412                         uint64_t count = 0;
413                         SmallHashEntry *e, *e_final = &sh->buckets[i];
414                         uint h = smallhash_key(e_final->key);
415                         uint hoff = 1;
416
417                         for (e = &sh->buckets[h % sh->nbuckets];
418                              e != e_final;
419                              h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets])
420                         {
421                                 count += 1;
422                         }
423
424                         sum += count;
425                 }
426         }
427         return ((double)(sh->nentries + sum) / (double)sh->nentries);
428 }
429 #endif
430
431 /** \} */