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