Blender  V3.3
smallhash.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2008 Blender Foundation. All rights reserved. */
3 
31 #include <stdlib.h>
32 #include <string.h>
33 
34 #include "BLI_sys_types.h"
35 
36 #include "MEM_guardedalloc.h"
37 
38 #include "BLI_utildefines.h"
39 
40 #include "BLI_smallhash.h"
41 
42 #include "BLI_strict_flags.h"
43 
44 #define SMHASH_KEY_UNUSED ((uintptr_t)(UINTPTR_MAX - 0))
45 #define SMHASH_CELL_FREE ((void *)(UINTPTR_MAX - 1))
46 #define SMHASH_CELL_UNUSED ((void *)(UINTPTR_MAX - 2))
47 
48 /* typically this re-assigns 'h' */
49 #define SMHASH_NEXT(h, hoff) \
50  (CHECK_TYPE_INLINE(&(h), uint *), \
51  CHECK_TYPE_INLINE(&(hoff), uint *), \
52  ((h) + (((hoff) = ((hoff)*2) + 1), (hoff))))
53 
54 /* nothing uses BLI_smallhash_remove yet */
55 // #define USE_REMOVE
56 
57 BLI_INLINE bool smallhash_val_is_used(const void *val)
58 {
59 #ifdef USE_REMOVE
61 #else
62  return (val != SMHASH_CELL_FREE);
63 #endif
64 }
65 
66 extern const uint BLI_ghash_hash_sizes[];
67 #define hashsizes BLI_ghash_hash_sizes
68 
70 {
71  return (uint)key;
72 }
73 
77 BLI_INLINE bool smallhash_test_expand_buckets(const uint nentries, const uint nbuckets)
78 {
79  /* (approx * 1.5) */
80  return (nentries + (nentries >> 1)) > nbuckets;
81 }
82 
84 {
85  uint i;
86 
87  for (i = 0; i < sh->nbuckets; i++) {
88  sh->buckets[i].key = SMHASH_KEY_UNUSED;
89  sh->buckets[i].val = SMHASH_CELL_FREE;
90  }
91 }
92 
96 BLI_INLINE void smallhash_buckets_reserve(SmallHash *sh, const uint nentries_reserve)
97 {
98  while (smallhash_test_expand_buckets(nentries_reserve, sh->nbuckets)) {
99  sh->nbuckets = hashsizes[++sh->cursize];
100  }
101 }
102 
104 {
105  SmallHashEntry *e;
106  uint h = smallhash_key(key);
107  uint hoff = 1;
108 
110 
111  /* NOTE: there are always more buckets than entries,
112  * so we know there will always be a free bucket if the key isn't found. */
113  for (e = &sh->buckets[h % sh->nbuckets]; e->val != SMHASH_CELL_FREE;
114  h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) {
115  if (e->key == key) {
116  /* should never happen because unused keys are zero'd */
118  return e;
119  }
120  }
121 
122  return NULL;
123 }
124 
126 {
127  SmallHashEntry *e;
128  uint h = smallhash_key(key);
129  uint hoff = 1;
130 
131  for (e = &sh->buckets[h % sh->nbuckets]; smallhash_val_is_used(e->val);
132  h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) {
133  /* pass */
134  }
135 
136  return e;
137 }
138 
140 {
141  SmallHashEntry *buckets_old = sh->buckets;
142  const uint nbuckets_old = sh->nbuckets;
143  const bool was_alloc = (buckets_old != sh->buckets_stack);
144  uint i = 0;
145 
146  BLI_assert(sh->nbuckets != nbuckets);
147  if (nbuckets <= SMSTACKSIZE) {
148  const size_t size = sizeof(*buckets_old) * nbuckets_old;
149  buckets_old = alloca(size);
150  memcpy(buckets_old, sh->buckets, size);
151 
152  sh->buckets = sh->buckets_stack;
153  }
154  else {
155  sh->buckets = MEM_mallocN(sizeof(*sh->buckets) * nbuckets, __func__);
156  }
157 
158  sh->nbuckets = nbuckets;
159 
161 
162  for (i = 0; i < nbuckets_old; i++) {
163  if (smallhash_val_is_used(buckets_old[i].val)) {
164  SmallHashEntry *e = smallhash_lookup_first_free(sh, buckets_old[i].key);
165  e->key = buckets_old[i].key;
166  e->val = buckets_old[i].val;
167  }
168  }
169 
170  if (was_alloc) {
171  MEM_freeN(buckets_old);
172  }
173 }
174 
175 void BLI_smallhash_init_ex(SmallHash *sh, const uint nentries_reserve)
176 {
177  /* assume 'sh' is uninitialized */
178 
179  sh->nentries = 0;
180  sh->cursize = 2;
181  sh->nbuckets = hashsizes[sh->cursize];
182 
183  sh->buckets = sh->buckets_stack;
184 
185  if (nentries_reserve) {
186  smallhash_buckets_reserve(sh, nentries_reserve);
187 
188  if (sh->nbuckets > SMSTACKSIZE) {
189  sh->buckets = MEM_mallocN(sizeof(*sh->buckets) * sh->nbuckets, __func__);
190  }
191  }
192 
194 }
195 
197 {
199 }
200 
202 {
203  if (sh->buckets != sh->buckets_stack) {
204  MEM_freeN(sh->buckets);
205  }
206 }
207 
209 {
210  SmallHashEntry *e;
211 
214  BLI_assert(BLI_smallhash_haskey(sh, key) == false);
215 
216  if (UNLIKELY(smallhash_test_expand_buckets(++sh->nentries, sh->nbuckets))) {
217  smallhash_resize_buckets(sh, hashsizes[++sh->cursize]);
218  }
219 
221  e->key = key;
222  e->val = item;
223 }
224 
226 {
228  if (e) {
229  e->val = item;
230  return false;
231  }
232 
233  BLI_smallhash_insert(sh, key, item);
234  return true;
235 }
236 
237 #ifdef USE_REMOVE
239 {
241 
242  if (e) {
243  e->key = SMHASH_KEY_UNUSED;
244  e->val = SMHASH_CELL_UNUSED;
245  sh->nentries--;
246 
247  return true;
248  }
249  else {
250  return false;
251  }
252 }
253 #endif
254 
256 {
258 
259  return e ? e->val : NULL;
260 }
261 
263 {
265 
266  return e ? &e->val : NULL;
267 }
268 
270 {
272 
273  return (e != NULL);
274 }
275 
277 {
278  return (int)sh->nentries;
279 }
280 
282 {
283  while (iter->i < iter->sh->nbuckets) {
284  if (smallhash_val_is_used(iter->sh->buckets[iter->i].val)) {
285  if (key) {
286  *key = iter->sh->buckets[iter->i].key;
287  }
288 
289  return &iter->sh->buckets[iter->i++];
290  }
291 
292  iter->i++;
293  }
294 
295  return NULL;
296 }
297 
299 {
300  SmallHashEntry *e = smallhash_iternext(iter, key);
301 
302  return e ? e->val : NULL;
303 }
304 
306 {
307  SmallHashEntry *e = smallhash_iternext(iter, key);
308 
309  return e ? &e->val : NULL;
310 }
311 
313 {
314  iter->sh = sh;
315  iter->i = 0;
316 
317  return BLI_smallhash_iternext(iter, key);
318 }
319 
321 {
322  iter->sh = sh;
323  iter->i = 0;
324 
325  return BLI_smallhash_iternext_p(iter, key);
326 }
327 
328 /* -------------------------------------------------------------------- */
332 /* NOTE(campbell): this was called _print_smhash in knifetool.c
333  * it may not be intended for general use. */
334 #if 0
335 void BLI_smallhash_print(SmallHash *sh)
336 {
337  uint i, linecol = 79, c = 0;
338 
339  printf("{");
340  for (i = 0; i < sh->nbuckets; i++) {
341  if (sh->buckets[i].val == SMHASH_CELL_UNUSED) {
342  printf("--u-");
343  }
344  else if (sh->buckets[i].val == SMHASH_CELL_FREE) {
345  printf("--f-");
346  }
347  else {
348  printf("%2x", (uint)sh->buckets[i].key);
349  }
350 
351  if (i != sh->nbuckets - 1) {
352  printf(", ");
353  }
354 
355  c += 6;
356 
357  if (c >= linecol) {
358  printf("\n ");
359  c = 0;
360  }
361  }
362 
363  fflush(stdout);
364 }
365 #endif
366 
367 #ifdef DEBUG
368 double BLI_smallhash_calc_quality(SmallHash *sh)
369 {
370  uint64_t sum = 0;
371  uint i;
372 
373  if (sh->nentries == 0) {
374  return -1.0;
375  }
376 
377  for (i = 0; i < sh->nbuckets; i++) {
378  if (sh->buckets[i].key != SMHASH_KEY_UNUSED) {
379  uint64_t count = 0;
380  SmallHashEntry *e, *e_final = &sh->buckets[i];
381  uint h = smallhash_key(e_final->key);
382  uint hoff = 1;
383 
384  for (e = &sh->buckets[h % sh->nbuckets]; e != e_final;
385  h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) {
386  count += 1;
387  }
388 
389  sum += count;
390  }
391  }
392  return ((double)(sh->nentries + sum) / (double)sh->nentries);
393 }
394 #endif
395 
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_INLINE
#define SMSTACKSIZE
Definition: BLI_smallhash.h:25
bool BLI_smallhash_remove(SmallHash *sh, uintptr_t key) ATTR_NONNULL(1)
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned int uint
Definition: BLI_sys_types.h:67
#define UNLIKELY(x)
#define ELEM(...)
Read Guarded memory(de)allocation.
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
static T sum(const btAlignedObjectArray< T > &items)
int count
ccl_gpu_kernel_postfix ccl_global float int int int int sh
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
static unsigned c
Definition: RandGen.cpp:83
void ** BLI_smallhash_lookup_p(const SmallHash *sh, uintptr_t key)
Definition: smallhash.c:262
void BLI_smallhash_insert(SmallHash *sh, uintptr_t key, void *item)
Definition: smallhash.c:208
void BLI_smallhash_init_ex(SmallHash *sh, const uint nentries_reserve)
Definition: smallhash.c:175
BLI_INLINE bool smallhash_val_is_used(const void *val)
Definition: smallhash.c:57
#define SMHASH_CELL_UNUSED
Definition: smallhash.c:46
BLI_INLINE SmallHashEntry * smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
Definition: smallhash.c:281
#define hashsizes
Definition: smallhash.c:67
bool BLI_smallhash_reinsert(SmallHash *sh, uintptr_t key, void *item)
Definition: smallhash.c:225
BLI_INLINE SmallHashEntry * smallhash_lookup_first_free(SmallHash *sh, const uintptr_t key)
Definition: smallhash.c:125
BLI_INLINE void smallhash_init_empty(SmallHash *sh)
Definition: smallhash.c:83
BLI_INLINE void smallhash_buckets_reserve(SmallHash *sh, const uint nentries_reserve)
Definition: smallhash.c:96
#define SMHASH_CELL_FREE
Definition: smallhash.c:45
BLI_INLINE void smallhash_resize_buckets(SmallHash *sh, const uint nbuckets)
Definition: smallhash.c:139
void * BLI_smallhash_lookup(const SmallHash *sh, uintptr_t key)
Definition: smallhash.c:255
bool BLI_smallhash_haskey(const SmallHash *sh, uintptr_t key)
Definition: smallhash.c:269
BLI_INLINE SmallHashEntry * smallhash_lookup(const SmallHash *sh, const uintptr_t key)
Definition: smallhash.c:103
#define SMHASH_KEY_UNUSED
Definition: smallhash.c:44
void ** BLI_smallhash_iternew_p(const SmallHash *sh, SmallHashIter *iter, uintptr_t *key)
Definition: smallhash.c:320
BLI_INLINE uint smallhash_key(const uintptr_t key)
Definition: smallhash.c:69
void BLI_smallhash_release(SmallHash *sh)
Definition: smallhash.c:201
const uint BLI_ghash_hash_sizes[]
Definition: BLI_ghash.c:40
void BLI_smallhash_init(SmallHash *sh)
Definition: smallhash.c:196
int BLI_smallhash_len(const SmallHash *sh)
Definition: smallhash.c:276
void ** BLI_smallhash_iternext_p(SmallHashIter *iter, uintptr_t *key)
Definition: smallhash.c:305
void * BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
Definition: smallhash.c:298
BLI_INLINE bool smallhash_test_expand_buckets(const uint nentries, const uint nbuckets)
Definition: smallhash.c:77
#define SMHASH_NEXT(h, hoff)
Definition: smallhash.c:49
void * BLI_smallhash_iternew(const SmallHash *sh, SmallHashIter *iter, uintptr_t *key)
Definition: smallhash.c:312
_W64 unsigned int uintptr_t
Definition: stdint.h:119
unsigned __int64 uint64_t
Definition: stdint.h:90
uintptr_t key
Definition: BLI_smallhash.h:17
unsigned int i
Definition: BLI_smallhash.h:37
const SmallHash * sh
Definition: BLI_smallhash.h:36
SmallHashEntry * buckets
Definition: BLI_smallhash.h:31
unsigned int nbuckets
Definition: BLI_smallhash.h:27