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