Blender
V3.3
|
#include <stdlib.h>
#include <string.h>
#include "BLI_sys_types.h"
#include "MEM_guardedalloc.h"
#include "BLI_utildefines.h"
#include "BLI_smallhash.h"
#include "BLI_strict_flags.h"
Go to the source code of this file.
Macros | |
#define | SMHASH_KEY_UNUSED ((uintptr_t)(UINTPTR_MAX - 0)) |
#define | SMHASH_CELL_FREE ((void *)(UINTPTR_MAX - 1)) |
#define | SMHASH_CELL_UNUSED ((void *)(UINTPTR_MAX - 2)) |
#define | SMHASH_NEXT(h, hoff) |
#define | hashsizes BLI_ghash_hash_sizes |
Variables | |
const uint | BLI_ghash_hash_sizes [] |
A light stack-friendly hash library, it uses stack space for relatively small, fixed size hash tables but falls back to heap memory once the stack limits reached (SMSTACKSIZE).
based on a doubling hashing approach (non-chaining) which uses more buckets than entries stepping over buckets when two keys share the same hash so any key can find a free bucket.
See: https://en.wikipedia.org/wiki/Double_hashing
SMHASH_KEY_UNUSED
means the key in the cell has not been initialized.SMHASH_CELL_UNUSED
means this cell is inside a key series.SMHASH_CELL_FREE
means this cell terminates a key series.Note that the values and keys are often pointers or index values, use the maximum values to avoid real pointers colliding with magic numbers.
Definition in file smallhash.c.
#define hashsizes BLI_ghash_hash_sizes |
Definition at line 67 of file smallhash.c.
#define SMHASH_CELL_FREE ((void *)(UINTPTR_MAX - 1)) |
Definition at line 45 of file smallhash.c.
#define SMHASH_CELL_UNUSED ((void *)(UINTPTR_MAX - 2)) |
Definition at line 46 of file smallhash.c.
#define SMHASH_KEY_UNUSED ((uintptr_t)(UINTPTR_MAX - 0)) |
Definition at line 44 of file smallhash.c.
#define SMHASH_NEXT | ( | h, | |
hoff | |||
) |
Definition at line 49 of file smallhash.c.
Definition at line 269 of file smallhash.c.
References e, NULL, sh, and smallhash_lookup().
Referenced by BLI_smallhash_insert(), and knife_find_line_hits().
Definition at line 196 of file smallhash.c.
References BLI_smallhash_init_ex(), and sh.
Referenced by knife_find_line_hits(), and knife_make_cuts().
Definition at line 175 of file smallhash.c.
References hashsizes, MEM_mallocN, sh, smallhash_buckets_reserve(), smallhash_init_empty(), and SMSTACKSIZE.
Referenced by BLI_smallhash_init().
Definition at line 208 of file smallhash.c.
References BLI_assert, BLI_smallhash_haskey(), e, hashsizes, sh, smallhash_lookup_first_free(), smallhash_resize_buckets(), smallhash_test_expand_buckets(), smallhash_val_is_used(), SMHASH_KEY_UNUSED, and UNLIKELY.
Referenced by BLI_smallhash_reinsert(), knife_find_line_hits(), and knife_make_cuts().
void* BLI_smallhash_iternew | ( | const SmallHash * | sh, |
SmallHashIter * | iter, | ||
uintptr_t * | key | ||
) |
Definition at line 312 of file smallhash.c.
References BLI_smallhash_iternext(), SmallHashIter::i, sh, and SmallHashIter::sh.
Referenced by knife_find_line_hits(), and knife_make_cuts().
void** BLI_smallhash_iternew_p | ( | const SmallHash * | sh, |
SmallHashIter * | iter, | ||
uintptr_t * | key | ||
) |
Definition at line 320 of file smallhash.c.
References BLI_smallhash_iternext_p(), SmallHashIter::i, sh, and SmallHashIter::sh.
Referenced by knife_find_line_hits().
void* BLI_smallhash_iternext | ( | SmallHashIter * | iter, |
uintptr_t * | key | ||
) |
Definition at line 298 of file smallhash.c.
References e, NULL, and smallhash_iternext().
Referenced by BLI_smallhash_iternew(), knife_find_line_hits(), and knife_make_cuts().
void** BLI_smallhash_iternext_p | ( | SmallHashIter * | iter, |
uintptr_t * | key | ||
) |
Definition at line 305 of file smallhash.c.
References e, NULL, and smallhash_iternext().
Referenced by BLI_smallhash_iternew_p(), and knife_find_line_hits().
int BLI_smallhash_len | ( | const SmallHash * | sh | ) |
Definition at line 276 of file smallhash.c.
References sh.
Definition at line 255 of file smallhash.c.
References e, NULL, sh, and smallhash_lookup().
Referenced by knife_find_line_hits(), and knife_make_cuts().
Definition at line 262 of file smallhash.c.
References e, NULL, sh, and smallhash_lookup().
Inserts a new value to a key that may already be in GHash.
Avoids BLI_smallhash_remove, BLI_smallhash_insert calls (double lookups)
Definition at line 225 of file smallhash.c.
References BLI_smallhash_insert(), e, sh, and smallhash_lookup().
Referenced by knife_find_line_hits().
Definition at line 201 of file smallhash.c.
Referenced by knife_find_line_hits(), and knife_make_cuts().
BLI_INLINE void smallhash_buckets_reserve | ( | SmallHash * | sh, |
const uint | nentries_reserve | ||
) |
Increase initial bucket size to match a reserved amount.
Definition at line 96 of file smallhash.c.
References hashsizes, sh, and smallhash_test_expand_buckets().
Referenced by BLI_smallhash_init_ex().
BLI_INLINE void smallhash_init_empty | ( | SmallHash * | sh | ) |
Definition at line 83 of file smallhash.c.
References sh, SMHASH_CELL_FREE, and SMHASH_KEY_UNUSED.
Referenced by BLI_smallhash_init_ex(), and smallhash_resize_buckets().
BLI_INLINE SmallHashEntry* smallhash_iternext | ( | SmallHashIter * | iter, |
uintptr_t * | key | ||
) |
Definition at line 281 of file smallhash.c.
References SmallHash::buckets, SmallHashIter::i, SmallHashEntry::key, SmallHash::nbuckets, NULL, SmallHashIter::sh, smallhash_val_is_used(), and SmallHashEntry::val.
Referenced by BLI_smallhash_iternext(), and BLI_smallhash_iternext_p().
BLI_INLINE uint smallhash_key | ( | const uintptr_t | key | ) |
Definition at line 69 of file smallhash.c.
Referenced by smallhash_lookup(), and smallhash_lookup_first_free().
BLI_INLINE SmallHashEntry* smallhash_lookup | ( | const SmallHash * | sh, |
const uintptr_t | key | ||
) |
Definition at line 103 of file smallhash.c.
References BLI_assert, e, NULL, sh, smallhash_key(), SMHASH_CELL_FREE, SMHASH_CELL_UNUSED, SMHASH_KEY_UNUSED, and SMHASH_NEXT.
Referenced by BLI_smallhash_haskey(), BLI_smallhash_lookup(), BLI_smallhash_lookup_p(), and BLI_smallhash_reinsert().
BLI_INLINE SmallHashEntry* smallhash_lookup_first_free | ( | SmallHash * | sh, |
const uintptr_t | key | ||
) |
Definition at line 125 of file smallhash.c.
References e, sh, smallhash_key(), smallhash_val_is_used(), and SMHASH_NEXT.
Referenced by BLI_smallhash_insert(), and smallhash_resize_buckets().
BLI_INLINE void smallhash_resize_buckets | ( | SmallHash * | sh, |
const uint | nbuckets | ||
) |
Definition at line 139 of file smallhash.c.
References BLI_assert, e, SmallHashEntry::key, MEM_freeN, MEM_mallocN, sh, size(), smallhash_init_empty(), smallhash_lookup_first_free(), smallhash_val_is_used(), SMSTACKSIZE, and SmallHashEntry::val.
Referenced by BLI_smallhash_insert().
BLI_INLINE bool smallhash_test_expand_buckets | ( | const uint | nentries, |
const uint | nbuckets | ||
) |
Check if the number of items in the smallhash is large enough to require more buckets.
Definition at line 77 of file smallhash.c.
Referenced by BLI_smallhash_insert(), and smallhash_buckets_reserve().
BLI_INLINE bool smallhash_val_is_used | ( | const void * | val | ) |
Definition at line 57 of file smallhash.c.
References ELEM, SMHASH_CELL_FREE, and SMHASH_CELL_UNUSED.
Referenced by BLI_smallhash_insert(), smallhash_iternext(), smallhash_lookup_first_free(), and smallhash_resize_buckets().
|
extern |
Next prime after 2^n
(skipping 2 & 3).
BLI_edgehash
& BLI_smallhash
. Definition at line 40 of file BLI_ghash.c.