Blender V5.3
BLI_ghash.cc File Reference
#include <algorithm>
#include <climits>
#include <cstdarg>
#include <cstdlib>
#include "MEM_guardedalloc.h"
#include "BLI_math_base_c.hh"
#include "BLI_mempool.hh"
#include "BLI_sys_types.hh"
#include "BLI_utildefines.hh"
#include "BLI_ghash.hh"
#include "BLI_strict_flags.hh"

Go to the source code of this file.

Classes

struct  blender::Entry
struct  blender::GHashEntry
struct  blender::GHash

Namespaces

namespace  blender
 BMesh Iterators.

Macros

#define GHASH_INTERNAL_API

Functions

Internal Utility API
BLI_INLINE void blender::ghash_entry_copy (GHash *gh_dst, Entry *dst, const GHash *gh_src, const Entry *src, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
BLI_INLINE uint blender::ghash_keyhash (const GHash *gh, const void *key)
BLI_INLINE uint blender::ghash_entryhash (const GHash *gh, const Entry *e)
BLI_INLINE uint blender::ghash_bucket_index (const GHash *gh, const uint hash)
BLI_INLINE uint blender::ghash_find_next_bucket_index (const GHash *gh, uint curr_bucket)
static void blender::ghash_buckets_resize (GHash *gh, const uint nbuckets)
static void blender::ghash_buckets_expand (GHash *gh, const uint nentries, const bool user_defined)
static void blender::ghash_buckets_contract (GHash *gh, const uint nentries, const bool user_defined, const bool force_shrink)
BLI_INLINE void blender::ghash_buckets_reset (GHash *gh, const uint nentries)
BLI_INLINE Entry * blender::ghash_lookup_entry_ex (const GHash *gh, const void *key, const uint bucket_index)
BLI_INLINE Entry * blender::ghash_lookup_entry_prev_ex (GHash *gh, const void *key, Entry **r_e_prev, const uint bucket_index)
BLI_INLINE Entry * blender::ghash_lookup_entry (const GHash *gh, const void *key)
static GHash * blender::ghash_new (GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info, const uint nentries_reserve, const uint flag)
BLI_INLINE void blender::ghash_insert_ex (GHash *gh, void *key, void *val, const uint bucket_index)
BLI_INLINE void blender::ghash_insert_ex_keyonly_entry (GHash *gh, void *key, const uint bucket_index, Entry *e)
BLI_INLINE void blender::ghash_insert_ex_keyonly (GHash *gh, void *key, const uint bucket_index)
BLI_INLINE void blender::ghash_insert (GHash *gh, void *key, void *val)
BLI_INLINE bool blender::ghash_insert_safe (GHash *gh, void *key, void *val, const bool override, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
BLI_INLINE bool blender::ghash_insert_safe_keyonly (GHash *gh, void *key, const bool override, GHashKeyFreeFP keyfreefp)
static Entry * blender::ghash_remove_ex (GHash *gh, const void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp, const uint bucket_index)
static Entry * blender::ghash_pop (GHash *gh, GHashIterState *state)
static void blender::ghash_free_cb (GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
static GHash * blender::ghash_copy (const GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
GHash API

Defined in BLI_ghash.c

GHash * blender::BLI_ghash_new_ex (GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
GHash * blender::BLI_ghash_new (GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
GHash * blender::BLI_ghash_copy (const GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
void blender::BLI_ghash_reserve (GHash *gh, unsigned int nentries_reserve)
unsigned int blender::BLI_ghash_len (const GHash *gh) ATTR_WARN_UNUSED_RESULT
void blender::BLI_ghash_insert (GHash *gh, void *key, void *val)
bool blender::BLI_ghash_reinsert (GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
void * blender::BLI_ghash_replace_key (GHash *gh, void *key)
void * blender::BLI_ghash_lookup (const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
void * blender::BLI_ghash_lookup_default (const GHash *gh, const void *key, void *val_default) ATTR_WARN_UNUSED_RESULT
void ** blender::BLI_ghash_lookup_p (GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
bool blender::BLI_ghash_ensure_p (GHash *gh, void *key, void ***r_val) ATTR_WARN_UNUSED_RESULT
bool blender::BLI_ghash_ensure_p_ex (GHash *gh, const void *key, void ***r_key, void ***r_val) ATTR_WARN_UNUSED_RESULT
bool blender::BLI_ghash_remove (GHash *gh, const void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
void * blender::BLI_ghash_popkey (GHash *gh, const void *key, GHashKeyFreeFP keyfreefp) ATTR_WARN_UNUSED_RESULT
bool blender::BLI_ghash_haskey (const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
bool blender::BLI_ghash_pop (GHash *gh, GHashIterState *state, void **r_key, void **r_val) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void blender::BLI_ghash_clear_ex (GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp, unsigned int nentries_reserve)
void blender::BLI_ghash_clear (GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
void blender::BLI_ghash_free (GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
void blender::BLI_ghash_flag_set (GHash *gh, unsigned int flag)
void blender::BLI_ghash_flag_clear (GHash *gh, unsigned int flag)
GHash Iterator
GHashIterator * blender::BLI_ghashIterator_new (GHash *gh) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
void blender::BLI_ghashIterator_init (GHashIterator *ghi, GHash *gh)
void blender::BLI_ghashIterator_step (GHashIterator *ghi)
void blender::BLI_ghashIterator_free (GHashIterator *ghi)
GSet Public API
GSet * blender::BLI_gset_new_ex (GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
GSet * blender::BLI_gset_new (GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
GSet * blender::BLI_gset_copy (const GSet *gs, GSetKeyCopyFP keycopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
unsigned int blender::BLI_gset_len (const GSet *gs) ATTR_WARN_UNUSED_RESULT
void blender::BLI_gset_insert (GSet *gs, void *key)
bool blender::BLI_gset_add (GSet *gs, void *key)
bool blender::BLI_gset_ensure_p_ex (GSet *gs, const void *key, void ***r_key)
bool blender::BLI_gset_reinsert (GSet *gs, void *key, GSetKeyFreeFP keyfreefp)
void * blender::BLI_gset_replace_key (GSet *gs, void *key)
bool blender::BLI_gset_remove (GSet *gs, const void *key, GSetKeyFreeFP keyfreefp)
bool blender::BLI_gset_haskey (const GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT
bool blender::BLI_gset_pop (GSet *gs, GSetIterState *state, void **r_key) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void blender::BLI_gset_clear_ex (GSet *gs, GSetKeyFreeFP keyfreefp, unsigned int nentries_reserve)
void blender::BLI_gset_clear (GSet *gs, GSetKeyFreeFP keyfreefp)
void blender::BLI_gset_free (GSet *gs, GSetKeyFreeFP keyfreefp)
void blender::BLI_gset_flag_set (GSet *gs, unsigned int flag)
void blender::BLI_gset_flag_clear (GSet *gs, unsigned int flag)
void * blender::BLI_gset_lookup (const GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT
void * blender::BLI_gset_pop_key (GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT
Debugging & Introspection
int blender::BLI_ghash_buckets_len (const GHash *gh)
int blender::BLI_gset_buckets_len (const GSet *gs)
double blender::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)
double blender::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)
double blender::BLI_ghash_calc_quality (const GHash *gh)
double blender::BLI_gset_calc_quality (const GSet *gs)

Structs & Constants

#define GHASH_USE_MODULO_BUCKETS
#define GHASH_MAX_SIZE   27
#define GHASH_LIMIT_GROW(_nbkt)
#define GHASH_LIMIT_SHRINK(_nbkt)
#define GHASH_ENTRY_SIZE(_is_gset)
using blender::GSetEntry = Entry
static const uint blender::hashsizes []
 blender::BLI_STATIC_ASSERT (ARRAY_SIZE(hashsizes)==GHASH_MAX_SIZE, "Invalid 'hashsizes' size")

Detailed Description

A general (pointer -> pointer) chaining hash table for 'Abstract Data Types' (known as an ADT Hash Table).

Definition in file BLI_ghash.cc.

Macro Definition Documentation

◆ GHASH_ENTRY_SIZE

#define GHASH_ENTRY_SIZE ( _is_gset)
Value:
((_is_gset) ? sizeof(GSetEntry) : sizeof(GHashEntry))

Definition at line 80 of file BLI_ghash.cc.

Referenced by blender::ghash_new().

◆ GHASH_INTERNAL_API

#define GHASH_INTERNAL_API

Definition at line 24 of file BLI_ghash.cc.

◆ GHASH_LIMIT_GROW

#define GHASH_LIMIT_GROW ( _nbkt)
Value:
(((_nbkt) * 3) / 4)
Note
Max load GHASH_LIMIT_GROW used to be 3. (pre 2.74). Python uses 0.6666, tommyhashlib even goes down to 0.5. Reducing our from 3 to 0.75 gives huge speedup (about twice quicker pure GHash insertions/lookup, about 25% - 30% quicker 'dynamic-topology' stroke drawing e.g.). Min load GHASH_LIMIT_SHRINK is a quarter of max load, to avoid resizing to quickly.

Definition at line 62 of file BLI_ghash.cc.

Referenced by blender::BLI_ghash_calc_quality_ex(), blender::ghash_buckets_contract(), blender::ghash_buckets_expand(), blender::ghash_buckets_reset(), and blender::ghash_copy().

◆ GHASH_LIMIT_SHRINK

#define GHASH_LIMIT_SHRINK ( _nbkt)
Value:
(((_nbkt) * 3) / 16)

Definition at line 63 of file BLI_ghash.cc.

Referenced by blender::ghash_buckets_contract(), blender::ghash_buckets_expand(), and blender::ghash_buckets_reset().

◆ GHASH_MAX_SIZE

#define GHASH_MAX_SIZE   27

Definition at line 47 of file BLI_ghash.cc.

Referenced by blender::BLI_STATIC_ASSERT(), and blender::ghash_buckets_expand().

◆ GHASH_USE_MODULO_BUCKETS

#define GHASH_USE_MODULO_BUCKETS

Definition at line 35 of file BLI_ghash.cc.