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