24#define GHASH_INTERNAL_API
35#define GHASH_USE_MODULO_BUCKETS
41 5, 11, 17, 37, 67, 131, 257, 521, 1031,
42 2053, 4099, 8209, 16411, 32771, 65537, 131101, 262147, 524309,
43 1048583, 2097169, 4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 268435459,
46#ifdef GHASH_USE_MODULO_BUCKETS
47# define GHASH_MAX_SIZE 27
50# define GHASH_BUCKET_BIT_MIN 2
51# define GHASH_BUCKET_BIT_MAX 28
62#define GHASH_LIMIT_GROW(_nbkt) (((_nbkt) * 3) / 4)
63#define GHASH_LIMIT_SHRINK(_nbkt) (((_nbkt) * 3) / 16)
80#define GHASH_ENTRY_SIZE(_is_gset) ((_is_gset) ? sizeof(GSetEntry) : sizeof(GHashEntry))
90#ifdef GHASH_USE_MODULO_BUCKETS
93 uint bucket_mask, bucket_bit, bucket_bit_min;
113 dst->
key = (keycopyfp) ? keycopyfp(src->
key) : src->
key;
115 if ((gh_dst->
flag & GHASH_FLAG_IS_GSET) == 0) {
116 if ((gh_src->
flag & GHASH_FLAG_IS_GSET) == 0) {
119 valcopyfp((
reinterpret_cast<GHashEntry *
>(
const_cast<Entry *
>(src)))->val) :
123 (
reinterpret_cast<GHashEntry *
>(dst))->val =
nullptr;
149#ifdef GHASH_USE_MODULO_BUCKETS
152 return hash & gh->bucket_mask;
164 if (gh->
buckets[curr_bucket]) {
167 for (; curr_bucket < gh->
nbuckets; curr_bucket++) {
168 if (gh->
buckets[curr_bucket]) {
172 for (curr_bucket = 0; curr_bucket < gh->
nbuckets; curr_bucket++) {
173 if (gh->
buckets[curr_bucket]) {
195#ifdef GHASH_USE_MODULO_BUCKETS
197 gh->bucket_mask = nbuckets - 1;
203 if (nbuckets > nbuckets_old) {
204 for (i = 0; i < nbuckets_old; i++) {
205 for (
Entry *
e = buckets_old[i], *e_next;
e;
e = e_next) {
209 e->next = buckets_new[bucket_index];
210 buckets_new[bucket_index] =
e;
215 for (i = 0; i < nbuckets_old; i++) {
216#ifdef GHASH_USE_MODULO_BUCKETS
217 for (
Entry *
e = buckets_old[i], *e_next;
e;
e = e_next) {
221 e->next = buckets_new[bucket_index];
222 buckets_new[bucket_index] =
e;
231 for (
e = buckets_old[i];
e &&
e->next;
e =
e->next) {
235 e->next = buckets_new[bucket_index];
236 buckets_new[bucket_index] = buckets_old[i];
245 MEM_delete(buckets_old);
257 if (gh->
buckets && (nentries < gh->limit_grow)) [[likely]] {
263#ifdef GHASH_USE_MODULO_BUCKETS
269 while ((nentries > gh->
limit_grow) && (gh->bucket_bit < GHASH_BUCKET_BIT_MAX)) {
270 new_nbuckets = 1u << ++gh->bucket_bit;
276#ifdef GHASH_USE_MODULO_BUCKETS
279 gh->bucket_bit_min = gh->bucket_bit;
294 const bool user_defined,
295 const bool force_shrink)
309#ifdef GHASH_USE_MODULO_BUCKETS
310 while ((nentries < gh->limit_shrink) && (gh->
cursize > gh->
size_min)) {
315 while ((nentries < gh->limit_shrink) && (gh->bucket_bit > gh->bucket_bit_min)) {
316 new_nbuckets = 1u << --gh->bucket_bit;
322#ifdef GHASH_USE_MODULO_BUCKETS
325 gh->bucket_bit_min = gh->bucket_bit;
345#ifdef GHASH_USE_MODULO_BUCKETS
350 gh->bucket_bit = GHASH_BUCKET_BIT_MIN;
351 gh->bucket_bit_min = GHASH_BUCKET_BIT_MIN;
352 gh->
nbuckets = 1u << gh->bucket_bit;
374 for (
e = gh->
buckets[bucket_index];
e;
e =
e->next) {
375 if (gh->
cmpfp(key,
e->key) ==
false) [[unlikely]] {
392 const uint bucket_index)
396 for (
Entry *e_prev =
nullptr, *
e = gh->
buckets[bucket_index];
e; e_prev =
e,
e =
e->next) {
397 if (gh->
cmpfp(key,
e->key) ==
false) [[unlikely]] {
420 const uint nentries_reserve,
463 const uint bucket_index,
468 e->next = gh->
buckets[bucket_index];
485 e->next = gh->
buckets[bucket_index];
561 const uint bucket_index)
573 valfreefp((
reinterpret_cast<GHashEntry *
>(
e))->val);
577 e_prev->
next =
e->next;
580 gh->
buckets[bucket_index] =
e->next;
609 state->curr_bucket = curr_bucket;
623 for (i = 0; i < gh->
nbuckets; i++) {
631 valfreefp((
reinterpret_cast<GHashEntry *
>(
e))->val);
654 for (i = 0; i < gh->
nbuckets; i++) {
685 const uint nentries_reserve)
687 return ghash_new(hashfp, cmpfp, info, nentries_reserve, 0);
728 void *key_prev =
e->
e.key;
739 return e ?
e->val :
nullptr;
746 return e ?
e->val : val_default;
753 return e ? &
e->val :
nullptr;
761 const bool haskey = (
e !=
nullptr);
777 const bool haskey = (
e !=
nullptr);
783 gh,
const_cast<void *
>(key), bucket_index,
reinterpret_cast<Entry *
>(
e));
844 *r_key = *r_val =
nullptr;
851 const uint nentries_reserve)
853 if (keyfreefp || valfreefp) {
869 if (keyfreefp || valfreefp) {
945 const uint nentries_reserve)
947 return reinterpret_cast<GSet *
>(
948 ghash_new(hashfp, cmpfp, info, nentries_reserve, GHASH_FLAG_IS_GSET));
958 return reinterpret_cast<GSet *
>(
964 return (
reinterpret_cast<GHash *
>(
const_cast<GSet *
>(gs)))->nentries;
985 const bool haskey = (
e !=
nullptr);
991 const_cast<void *
>(key),
1054 (
reinterpret_cast<GHash *
>(gs))->flag |= flag;
1059 (
reinterpret_cast<GHash *
>(gs))->flag &= ~flag;
1074 return e ?
e->key :
nullptr;
1083 void *key_ret =
e->key;
1108 double *r_prop_empty_buckets,
1109 double *r_prop_overloaded_buckets,
1110 int *r_biggest_bucket)
1122 if (r_prop_empty_buckets) {
1123 *r_prop_empty_buckets = 1.0;
1125 if (r_prop_overloaded_buckets) {
1126 *r_prop_overloaded_buckets = 0.0;
1128 if (r_biggest_bucket) {
1129 *r_biggest_bucket = 0;
1139 if (r_biggest_bucket) {
1140 *r_biggest_bucket = 0;
1148 for (i = 0; i < gh->
nbuckets; i++) {
1154 sum += (double(count) - mean) * (
double(count) - mean);
1156 *r_variance = sum / double(gh->
nbuckets - 1);
1165 for (i = 0; i < gh->
nbuckets; i++) {
1171 if (r_biggest_bucket) {
1172 *r_biggest_bucket =
max_ii(*r_biggest_bucket,
int(count));
1174 if (r_prop_overloaded_buckets && (count > overloaded_buckets_threshold)) {
1177 if (r_prop_empty_buckets && !count) {
1180 sum += count * (count + 1);
1182 if (r_prop_overloaded_buckets) {
1183 *r_prop_overloaded_buckets = double(sum_overloaded) / double(gh->
nbuckets);
1185 if (r_prop_empty_buckets) {
1186 *r_prop_empty_buckets = double(sum_empty) / double(gh->
nbuckets);
1188 return (
double(sum) *
double(gh->
nbuckets) /
1195 double *r_prop_empty_buckets,
1196 double *r_prop_overloaded_buckets,
1197 int *r_biggest_bucket)
1202 r_prop_empty_buckets,
1203 r_prop_overloaded_buckets,
#define GHASH_ENTRY_SIZE(_is_gset)
#define GHASH_LIMIT_SHRINK(_nbkt)
#define GHASH_LIMIT_GROW(_nbkt)
Read Blender memory allocation and freeing.
#define BLI_assert_unreachable()
BLI_INLINE uint ghash_bucket_index(const GHash *gh, const uint hash)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
bool BLI_ghash_ensure_p_ex(GHash *gh, const void *key, void ***r_key, void ***r_val) ATTR_WARN_UNUSED_RESULT
void BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp)
bool BLI_gset_ensure_p_ex(GSet *gs, const void *key, void ***r_key)
unsigned __int64 uint64_t
BLI_STATIC_ASSERT(ARRAY_SIZE(data_mode_strings)==CTX_MODE_NUM+1, "Must have a string for each context mode") const char *CTX_data_mode_string(const bContext *C)
BLI_INLINE void ghash_insert_ex(GHash *gh, void *key, void *val, const uint bucket_index)
GHash * BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
int BLI_ghash_buckets_len(const GHash *gh)
void * BLI_ghash_lookup_default(const GHash *gh, const void *key, void *val_default) ATTR_WARN_UNUSED_RESULT
BLI_INLINE Entry * ghash_lookup_entry_prev_ex(GHash *gh, const void *key, Entry **r_e_prev, const uint bucket_index)
void * BLI_ghash_replace_key(GHash *gh, void *key)
void * BLI_gset_lookup(const GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT
BLI_INLINE bool ghash_insert_safe_keyonly(GHash *gh, void *key, const bool override, GHashKeyFreeFP keyfreefp)
unsigned int(*) GHashHashFP(const void *key)
static Entry * ghash_remove_ex(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp, const uint bucket_index)
bool BLI_gset_reinsert(GSet *gs, void *key, GSetKeyFreeFP keyfreefp)
void * BLI_ghash_lookup(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
void * BLI_gset_pop_key(GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT
bool BLI_gset_pop(GSet *gs, GSetIterState *state, void **r_key) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void(*) GHashKeyFreeFP(void *key)
GHashKeyFreeFP GSetKeyFreeFP
MINLINE int max_ii(int a, int b)
void BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp, unsigned int nentries_reserve)
double BLI_ghash_calc_quality(const GHash *gh)
BLI_INLINE uint ghash_keyhash(const GHash *gh, const void *key)
void BLI_gset_flag_set(GSet *gs, unsigned int flag)
double BLI_gset_calc_quality(const GSet *gs)
bool(*) GHashCmpFP(const void *a, const void *b)
void BLI_ghash_insert(GHash *gh, void *key, void *val)
void BLI_ghash_clear_ex(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp, unsigned int nentries_reserve)
void BLI_mempool_free(BLI_mempool *pool, void *addr) ATTR_NONNULL(1
void BLI_ghash_flag_clear(GHash *gh, unsigned int flag)
double BLI_ghash_calc_quality_ex(const GHash *gh, double *r_load, double *r_variance, double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket)
void ** BLI_ghash_lookup_p(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
void * BLI_ghash_popkey(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp) ATTR_WARN_UNUSED_RESULT
int BLI_gset_buckets_len(const GSet *gs)
void BLI_mempool_destroy(BLI_mempool *pool) ATTR_NONNULL(1)
void *(*) GHashKeyCopyFP(const void *key)
void BLI_ghashIterator_step(GHashIterator *ghi)
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
BLI_INLINE uint ghash_entryhash(const GHash *gh, const Entry *e)
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
static void ghash_buckets_contract(GHash *gh, const uint nentries, const bool user_defined, const bool force_shrink)
static void ghash_buckets_expand(GHash *gh, const uint nentries, const bool user_defined)
GHashIterState GSetIterState
BLI_INLINE bool ghash_insert_safe(GHash *gh, void *key, void *val, const bool override, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
bool BLI_ghash_ensure_p(GHash *gh, void *key, void ***r_val) ATTR_WARN_UNUSED_RESULT
static void ghash_free_cb(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
BLI_mempool * BLI_mempool_create(unsigned int esize, unsigned int elem_num, unsigned int pchunk, unsigned int flag) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL
BLI_INLINE void ghash_buckets_reset(GHash *gh, const uint nentries)
void BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
BLI_INLINE Entry * ghash_lookup_entry(const GHash *gh, const void *key)
BLI_INLINE Entry * ghash_lookup_entry_ex(const GHash *gh, const void *key, const uint bucket_index)
void BLI_ghash_flag_set(GHash *gh, unsigned int flag)
void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp)
static void ghash_buckets_resize(GHash *gh, const uint nbuckets)
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
GSet * BLI_gset_copy(const GSet *gs, GSetKeyCopyFP keycopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
@ GHASH_FLAG_ALLOW_SHRINK
static Entry * ghash_pop(GHash *gh, GHashIterState *state)
unsigned int BLI_ghash_len(const GHash *gh) ATTR_WARN_UNUSED_RESULT
void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh)
void * BLI_gset_replace_key(GSet *gs, void *key)
static GHash * ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info, const uint nentries_reserve, const uint flag)
void BLI_gset_flag_clear(GSet *gs, unsigned int flag)
GSet * BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
void void BLI_mempool_clear_ex(BLI_mempool *pool, int elem_num_reserve) ATTR_NONNULL(1)
GHash * BLI_ghash_copy(const GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
static const uint hashsizes[]
void BLI_gset_insert(GSet *gs, void *key)
bool BLI_gset_remove(GSet *gs, const void *key, GSetKeyFreeFP keyfreefp)
void(*) GHashValFreeFP(void *val)
GHashIterator * BLI_ghashIterator_new(GHash *gh) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
bool BLI_ghash_remove(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
unsigned int BLI_gset_len(const GSet *gs) ATTR_WARN_UNUSED_RESULT
void BLI_ghash_reserve(GHash *gh, unsigned int nentries_reserve)
static GHash * ghash_copy(const GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
void *(*) GHashValCopyFP(const void *val)
bool BLI_gset_haskey(const GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
bool BLI_ghash_pop(GHash *gh, GHashIterState *state, void **r_key, void **r_val) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
GSet * BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
BLI_INLINE void ghash_insert_ex_keyonly(GHash *gh, void *key, const uint bucket_index)
GHash * BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
int BLI_mempool_len(const BLI_mempool *pool) ATTR_NONNULL(1)
BLI_INLINE uint ghash_find_next_bucket_index(const GHash *gh, uint curr_bucket)
BLI_INLINE void ghash_insert(GHash *gh, void *key, void *val)
bool BLI_ghash_haskey(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
bool BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
BLI_INLINE void ghash_insert_ex_keyonly_entry(GHash *gh, void *key, const uint bucket_index, Entry *e)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
BLI_INLINE void ghash_entry_copy(GHash *gh_dst, Entry *dst, const GHash *gh_src, const Entry *src, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
double BLI_gset_calc_quality_ex(const GSet *gs, double *r_load, double *r_variance, double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket)
bool BLI_gset_add(GSet *gs, void *key)
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void BLI_ghashIterator_free(GHashIterator *ghi)