diff options
Diffstat (limited to 'source/blender/blenlib/BLI_ghash.h')
| -rw-r--r-- | source/blender/blenlib/BLI_ghash.h | 243 |
1 files changed, 241 insertions, 2 deletions
diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h index a2c5c6349a5..0194f9aad40 100644 --- a/source/blender/blenlib/BLI_ghash.h +++ b/source/blender/blenlib/BLI_ghash.h @@ -43,6 +43,10 @@ extern "C" { # endif #endif +/* -------------------------------------------------------------------- */ +/** \name GHash Types + * \{ */ + typedef unsigned int (*GHashHashFP)(const void *key); /** returns false when equal */ typedef bool (*GHashCmpFP)(const void *a, const void *b); @@ -74,53 +78,191 @@ enum { #endif }; +/** \} */ + /* -------------------------------------------------------------------- */ /** \name GHash API * * Defined in `BLI_ghash.c` * \{ */ +/** + * Creates a new, empty GHash. + * + * \param hashfp: Hash callback. + * \param cmpfp: Comparison callback. + * \param info: Identifier string for the GHash. + * \param nentries_reserve: Optionally reserve the number of members that the hash will hold. + * Use this to avoid resizing buckets if the size is known or can be closely approximated. + * \return An empty GHash. + */ GHash *BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info, const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; +/** + * Wraps #BLI_ghash_new_ex with zero entries reserved. + */ GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; +/** + * Copy given GHash. Keys and values are also copied if relevant callback is provided, + * else pointers remain the same. + */ GHash *BLI_ghash_copy(const GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; +/** + * Frees the GHash and its members. + * + * \param gh: The GHash to free. + * \param keyfreefp: Optional callback to free the key. + * \param valfreefp: Optional callback to free the value. + */ void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp); +/** + * Reserve given amount of entries (resize \a gh accordingly if needed). + */ void BLI_ghash_reserve(GHash *gh, const unsigned int nentries_reserve); +/** + * Insert a key/value pair into the \a gh. + * + * \note Duplicates are not checked, + * the caller is expected to ensure elements are unique unless + * GHASH_FLAG_ALLOW_DUPES flag is set. + */ void BLI_ghash_insert(GHash *gh, void *key, void *val); +/** + * Inserts a new value to a key that may already be in ghash. + * + * Avoids #BLI_ghash_remove, #BLI_ghash_insert calls (double lookups) + * + * \returns true if a new key has been added. + */ bool BLI_ghash_reinsert( GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp); +/** + * Replaces the key of an item in the \a gh. + * + * Use when a key is re-allocated or its memory location is changed. + * + * \returns The previous key or NULL if not found, the caller may free if it's needed. + */ void *BLI_ghash_replace_key(GHash *gh, void *key); +/** + * Lookup the value of \a key in \a gh. + * + * \param key: The key to lookup. + * \returns the value for \a key or NULL. + * + * \note When NULL is a valid value, use #BLI_ghash_lookup_p to differentiate a missing key + * from a key with a NULL value. (Avoids calling #BLI_ghash_haskey before #BLI_ghash_lookup) + */ void *BLI_ghash_lookup(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT; +/** + * A version of #BLI_ghash_lookup which accepts a fallback argument. + */ void *BLI_ghash_lookup_default(const GHash *gh, const void *key, void *val_default) ATTR_WARN_UNUSED_RESULT; +/** + * Lookup a pointer to the value of \a key in \a gh. + * + * \param key: The key to lookup. + * \returns the pointer to value for \a key or NULL. + * + * \note This has 2 main benefits over #BLI_ghash_lookup. + * - A NULL return always means that \a key isn't in \a gh. + * - The value can be modified in-place without further function calls (faster). + */ void **BLI_ghash_lookup_p(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT; +/** + * Ensure \a key is exists in \a gh. + * + * This handles the common situation where the caller needs ensure a key is added to \a gh, + * constructing a new value in the case the key isn't found. + * Otherwise use the existing value. + * + * Such situations typically incur multiple lookups, however this function + * avoids them by ensuring the key is added, + * returning a pointer to the value so it can be used or initialized by the caller. + * + * \returns true when the value didn't need to be added. + * (when false, the caller _must_ initialize the value). + */ bool BLI_ghash_ensure_p(GHash *gh, void *key, void ***r_val) ATTR_WARN_UNUSED_RESULT; +/** + * A version of #BLI_ghash_ensure_p that allows caller to re-assign the key. + * Typically used when the key is to be duplicated. + * + * \warning Caller _must_ write to \a r_key when returning false. + */ bool BLI_ghash_ensure_p_ex(GHash *gh, const void *key, void ***r_key, void ***r_val) ATTR_WARN_UNUSED_RESULT; +/** + * Remove \a key from \a gh, or return false if the key wasn't found. + * + * \param key: The key to remove. + * \param keyfreefp: Optional callback to free the key. + * \param valfreefp: Optional callback to free the value. + * \return true if \a key was removed from \a gh. + */ bool BLI_ghash_remove(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp); +/** + * Wraps #BLI_ghash_clear_ex with zero entries reserved. + */ void BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp); +/** + * Reset \a gh clearing all entries. + * + * \param keyfreefp: Optional callback to free the key. + * \param valfreefp: Optional callback to free the value. + * \param nentries_reserve: Optionally reserve the number of members that the hash will hold. + */ void BLI_ghash_clear_ex(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp, const unsigned int nentries_reserve); +/** + * Remove \a key from \a gh, returning the value or NULL if the key wasn't found. + * + * \param key: The key to remove. + * \param keyfreefp: Optional callback to free the key. + * \return the value of \a key int \a gh or NULL. + */ void *BLI_ghash_popkey(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp) ATTR_WARN_UNUSED_RESULT; +/** + * \return true if the \a key is in \a gh. + */ bool BLI_ghash_haskey(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT; +/** + * Remove a random entry from \a gh, returning true + * if a key/value pair could be removed, false otherwise. + * + * \param r_key: The removed key. + * \param r_val: The removed value. + * \param state: Used for efficient removal. + * \return true if there was something to pop, false if ghash was already empty. + */ bool BLI_ghash_pop(GHash *gh, GHashIterState *state, void **r_key, void **r_val) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +/** + * \return size of the GHash. + */ unsigned int BLI_ghash_len(const GHash *gh) ATTR_WARN_UNUSED_RESULT; +/** + * Sets a GHash flag. + */ void BLI_ghash_flag_set(GHash *gh, unsigned int flag); +/** + * Clear a GHash flag. + */ void BLI_ghash_flag_clear(GHash *gh, unsigned int flag); /** \} */ @@ -129,10 +271,36 @@ void BLI_ghash_flag_clear(GHash *gh, unsigned int flag); /** \name GHash Iterator * \{ */ +/** + * Create a new GHashIterator. The hash table must not be mutated + * while the iterator is in use, and the iterator will step exactly + * #BLI_ghash_len(gh) times before becoming done. + * + * \param gh: The GHash to iterate over. + * \return Pointer to a new iterator. + */ GHashIterator *BLI_ghashIterator_new(GHash *gh) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; +/** + * Init an already allocated GHashIterator. The hash table must not + * be mutated while the iterator is in use, and the iterator will + * step exactly #BLI_ghash_len(gh) times before becoming done. + * + * \param ghi: The GHashIterator to initialize. + * \param gh: The GHash to iterate over. + */ void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh); +/** + * Free a GHashIterator. + * + * \param ghi: The iterator to free. + */ void BLI_ghashIterator_free(GHashIterator *ghi); +/** + * Steps the iterator to the next index. + * + * \param ghi: The iterator. + */ void BLI_ghashIterator_step(GHashIterator *ghi); BLI_INLINE void *BLI_ghashIterator_getKey(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT; @@ -178,12 +346,11 @@ BLI_INLINE bool BLI_ghashIterator_done(const GHashIterator *ghi) /** \} */ /* -------------------------------------------------------------------- */ -/** \name GSet API +/** \name GSet Types * A 'set' implementation (unordered collection of unique elements). * * Internally this is a 'GHash' without any keys, * which is why this API's are in the same header & source file. - * * \{ */ typedef struct GSet GSet; @@ -195,6 +362,13 @@ typedef GHashKeyCopyFP GSetKeyCopyFP; typedef GHashIterState GSetIterState; +/** \} */ + +/** \name GSet Public API + * + * Use ghash API to give 'set' functionality + * \{ */ + GSet *BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info, @@ -202,17 +376,55 @@ GSet *BLI_gset_new_ex(GSetHashFP hashfp, GSet *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; +/** + * Copy given GSet. Keys are also copied if callback is provided, else pointers remain the same. + */ GSet *BLI_gset_copy(const GSet *gs, GSetKeyCopyFP keycopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT; unsigned int BLI_gset_len(const GSet *gs) ATTR_WARN_UNUSED_RESULT; void BLI_gset_flag_set(GSet *gs, unsigned int flag); void BLI_gset_flag_clear(GSet *gs, unsigned int flag); void BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp); +/** + * Adds the key to the set (no checks for unique keys!). + * Matching #BLI_ghash_insert + */ void BLI_gset_insert(GSet *gs, void *key); +/** + * A version of BLI_gset_insert which checks first if the key is in the set. + * \returns true if a new key has been added. + * + * \note GHash has no equivalent to this because typically the value would be different. + */ bool BLI_gset_add(GSet *gs, void *key); +/** + * Set counterpart to #BLI_ghash_ensure_p_ex. + * similar to BLI_gset_add, except it returns the key pointer. + * + * \warning Caller _must_ write to \a r_key when returning false. + */ bool BLI_gset_ensure_p_ex(GSet *gs, const void *key, void ***r_key); +/** + * Adds the key to the set (duplicates are managed). + * Matching #BLI_ghash_reinsert + * + * \returns true if a new key has been added. + */ bool BLI_gset_reinsert(GSet *gh, void *key, GSetKeyFreeFP keyfreefp); +/** + * Replaces the key to the set if it's found. + * Matching #BLI_ghash_replace_key + * + * \returns The old key or NULL if not found. + */ void *BLI_gset_replace_key(GSet *gs, void *key); bool BLI_gset_haskey(const GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT; +/** + * Remove a random entry from \a gs, returning true if a key could be removed, false otherwise. + * + * \param r_key: The removed key. + * \param state: Used for efficient removal. + * \return true if there was something to pop, false if gset was already empty. + */ bool BLI_gset_pop(GSet *gs, GSetIterState *state, void **r_key) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BLI_gset_remove(GSet *gs, const void *key, GSetKeyFreeFP keyfreefp); @@ -220,7 +432,14 @@ void BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp, const unsigned int nen void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp); /* When set's are used for key & value. */ +/** + * Returns the pointer to the key if it's found. + */ void *BLI_gset_lookup(const GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT; +/** + * Returns the pointer to the key if it's found, removing it from the GSet. + * \note Caller must handle freeing. + */ void *BLI_gset_pop_key(GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT; /** \} */ @@ -282,9 +501,19 @@ BLI_INLINE bool BLI_gsetIterator_done(const GSetIterator *gsi) /* For testing, debugging only */ #ifdef GHASH_INTERNAL_API +/** + * \return number of buckets in the GHash. + */ int BLI_ghash_buckets_len(const GHash *gh); int BLI_gset_buckets_len(const GSet *gs); +/** + * Measure how well the hash function performs (1.0 is approx as good as random distribution), + * and return a few other stats like load, + * variance of the distribution of the entries in the buckets, etc. + * + * Smaller is better! + */ double BLI_ghash_calc_quality_ex(GHash *gh, double *r_load, double *r_variance, @@ -300,6 +529,7 @@ double BLI_gset_calc_quality_ex(GSet *gs, double BLI_ghash_calc_quality(GHash *gh); double BLI_gset_calc_quality(GSet *gs); #endif /* GHASH_INTERNAL_API */ + /** \} */ /* -------------------------------------------------------------------- */ @@ -346,6 +576,15 @@ double BLI_gset_calc_quality(GSet *gs); unsigned int BLI_ghashutil_ptrhash(const void *key); bool BLI_ghashutil_ptrcmp(const void *a, const void *b); +/** + * This function implements the widely used `djb` hash apparently posted + * by Daniel Bernstein to `comp.lang.c` some time ago. The 32 bit + * unsigned hash value starts at 5381 and for each byte 'c' in the + * string, is updated: `hash = hash * 33 + c`. + * This function uses the signed value of each byte. + * + * NOTE: this is the same hash method that glib 2.34.0 uses. + */ unsigned int BLI_ghashutil_strhash_n(const char *key, size_t n); #define BLI_ghashutil_strhash(key) \ (CHECK_TYPE_ANY(key, char *, const char *, const char *const), BLI_ghashutil_strhash_p(key)) |