diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-08-25 16:17:46 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-08-25 16:17:46 +0400 |
commit | 3a9eb9b49716aad15156180da6e8018241b80cf8 (patch) | |
tree | d961c2c0f35e3a87a2dab4aaffac2511ed42dfd1 | |
parent | 150af65d9f4794a3397dabb307c37d42607ec07a (diff) |
doxygen docs for ghash/edgehash
-rw-r--r-- | source/blender/blenlib/intern/BLI_ghash.c | 185 | ||||
-rw-r--r-- | source/blender/blenlib/intern/edgehash.c | 19 |
2 files changed, 166 insertions, 38 deletions
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index 918fc55df72..21326227794 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -84,18 +84,29 @@ struct GHash { /* -------------------------------------------------------------------- */ /* GHash API */ -/* internal utility API */ +/** \name Internal Utility API + * \{ */ +/** + * Check if the number of items in the GHash is large enough to require more buckets. + */ BLI_INLINE bool ghash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets) { return (nentries > nbuckets * 3); } +/** + * Get the hash for a key. + */ BLI_INLINE unsigned int ghash_keyhash(GHash *gh, const void *key) { return gh->hashfp(key) % gh->nbuckets; } +/** + * Internal lookup function. + * Takes a hash argument to avoid calling #ghash_keyhash multiple times. + */ BLI_INLINE Entry *ghash_lookup_entry_ex(GHash *gh, const void *key, const unsigned int hash) { @@ -109,12 +120,19 @@ BLI_INLINE Entry *ghash_lookup_entry_ex(GHash *gh, const void *key, return NULL; } +/** + * Internal lookup function. Only wraps #ghash_lookup_entry_ex + */ BLI_INLINE Entry *ghash_lookup_entry(GHash *gh, const void *key) { const unsigned int hash = ghash_keyhash(gh, key); return ghash_lookup_entry_ex(gh, key, hash); } +/** + * Internal insert function. + * Takes a hash argument to avoid calling #ghash_keyhash multiple times. + */ static void ghash_insert_ex(GHash *gh, void *key, void *val, unsigned int hash) { @@ -148,10 +166,22 @@ static void ghash_insert_ex(GHash *gh, void *key, void *val, MEM_freeN(old); } } +/** \} */ -/* Public API */ +/** \name Public API + * \{ */ +/** + * 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) { @@ -178,16 +208,29 @@ GHash *BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info, return gh; } +/** + * Wraps #BLI_ghash_new_ex with zero entries reserved. + */ GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) { return BLI_ghash_new_ex(hashfp, cmpfp, info, 0); } +/** + * \return size of the GHash. + */ int BLI_ghash_size(GHash *gh) { return (int)gh->nentries; } +/** + * 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) { const unsigned int hash = ghash_keyhash(gh, key); @@ -195,7 +238,8 @@ void BLI_ghash_insert(GHash *gh, void *key, void *val) } /** - * Assign a new value to a key that may already be in ghash. + * Inserts a new value to a key that may already be in ghash. + * * Avoids #BLI_ghash_remove, #BLI_ghash_insert calls (double lookups) */ void BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) @@ -214,18 +258,45 @@ void BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreef } } +/** + * 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(GHash *gh, const void *key) { Entry *e = ghash_lookup_entry(gh, key); return e ? e->val : NULL; } +/** + * 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 benifits 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) { Entry *e = ghash_lookup_entry(gh, key); return e ? &e->val : NULL; } +/** + * 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, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) { const unsigned int hash = ghash_keyhash(gh, key); @@ -256,6 +327,13 @@ bool BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFr /* same as above but return the value, * no free value argument since it will be returned */ +/** + * 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_pop(GHash *gh, void *key, GHashKeyFreeFP keyfreefp) { const unsigned int hash = ghash_keyhash(gh, key); @@ -284,11 +362,20 @@ void *BLI_ghash_pop(GHash *gh, void *key, GHashKeyFreeFP keyfreefp) return NULL; } +/** + * \return true if the \a key is in \a gh. + */ bool BLI_ghash_haskey(GHash *gh, const void *key) { return (ghash_lookup_entry(gh, key) != NULL); } +/** + * Reset \a gh clearing all entries. + * + * \param keyfreefp Optional callback to free the key. + * \param valfreefp Optional callback to free the value. + */ void BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) { unsigned int i; @@ -316,6 +403,13 @@ void BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfree gh->buckets = MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets"); } +/** + * 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) { unsigned int i; @@ -343,20 +437,31 @@ void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreef MEM_freeN(gh); } +/** + * Sets a GHash flag. + */ void BLI_ghash_flag_set(GHash *gh, unsigned int flag) { gh->flag |= flag; } +/** + * Clear a GHash flag. + */ void BLI_ghash_flag_clear(GHash *gh, unsigned int flag) { gh->flag &= ~flag; } +/** \} */ + /* -------------------------------------------------------------------- */ /* GHash Iterator API */ +/** \name Iterator API + * \{ */ + GHashIterator *BLI_ghashIterator_new(GHash *gh) { GHashIterator *ghi = MEM_mallocN(sizeof(*ghi), "ghash iterator"); @@ -406,6 +511,12 @@ bool BLI_ghashIterator_done(GHashIterator *ghi) return ghi->curEntry == NULL; } +/** \} */ + + +/** \name Generic Key Hash & Comparison Functions + * \{ */ + /***/ #if 0 @@ -480,6 +591,43 @@ int BLI_ghashutil_strcmp(const void *a, const void *b) return strcmp(a, b); } +GHashPair *BLI_ghashutil_pairalloc(const void *first, const void *second) +{ + GHashPair *pair = MEM_mallocN(sizeof(GHashPair), "GHashPair"); + pair->first = first; + pair->second = second; + return pair; +} + +unsigned int BLI_ghashutil_pairhash(const void *ptr) +{ + const GHashPair *pair = ptr; + unsigned int hash = BLI_ghashutil_ptrhash(pair->first); + return hash ^ BLI_ghashutil_ptrhash(pair->second); +} + +int BLI_ghashutil_paircmp(const void *a, const void *b) +{ + const GHashPair *A = a; + const GHashPair *B = b; + + int cmp = BLI_ghashutil_ptrcmp(A->first, B->first); + if (cmp == 0) + return BLI_ghashutil_ptrcmp(A->second, B->second); + return cmp; +} + +void BLI_ghashutil_pairfree(void *ptr) +{ + MEM_freeN(ptr); +} + +/** \} */ + + +/** \name Convenience Creation Functions + * \{ */ + GHash *BLI_ghash_ptr_new_ex(const char *info, const unsigned int nentries_reserve) { @@ -524,33 +672,4 @@ GHash *BLI_ghash_pair_new(const char *info) return BLI_ghash_pair_new_ex(info, 0); } -GHashPair *BLI_ghashutil_pairalloc(const void *first, const void *second) -{ - GHashPair *pair = MEM_mallocN(sizeof(GHashPair), "GHashPair"); - pair->first = first; - pair->second = second; - return pair; -} - -unsigned int BLI_ghashutil_pairhash(const void *ptr) -{ - const GHashPair *pair = ptr; - unsigned int hash = BLI_ghashutil_ptrhash(pair->first); - return hash ^ BLI_ghashutil_ptrhash(pair->second); -} - -int BLI_ghashutil_paircmp(const void *a, const void *b) -{ - const GHashPair *A = a; - const GHashPair *B = b; - - int cmp = BLI_ghashutil_ptrcmp(A->first, B->first); - if (cmp == 0) - return BLI_ghashutil_ptrcmp(A->second, B->second); - return cmp; -} - -void BLI_ghashutil_pairfree(void *ptr) -{ - MEM_freeN(ptr); -} +/** \} */ diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c index dac107187f3..cae23356782 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -82,9 +82,8 @@ struct EdgeHash { /* -------------------------------------------------------------------- */ /* EdgeHash API */ -/* internal utility API */ - -#define EDGE_HASH(v0, v1) ((v0 * 39) ^ (v1 * 31)) +/** \name Internal Utility API + * \{ */ BLI_INLINE bool edgehash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets) { @@ -94,7 +93,8 @@ BLI_INLINE bool edgehash_test_expand_buckets(const unsigned int nentries, const BLI_INLINE unsigned int edgehash_keyhash(EdgeHash *eh, unsigned int v0, unsigned int v1) { BLI_assert(v0 < v1); - return EDGE_HASH(v0, v1) % eh->nbuckets; + + return ((v0 * 39) ^ (v1 * 31)) % eh->nbuckets; } BLI_INLINE EdgeEntry *edgehash_lookup_entry_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, @@ -156,9 +156,11 @@ static void edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, v MEM_freeN(old); } } +/** \} */ -#undef EDGE_HASH +/** \name Public API + * \{ */ /* Public API */ @@ -305,10 +307,15 @@ void BLI_edgehash_flag_clear(EdgeHash *eh, unsigned int flag) eh->flag &= ~flag; } +/** \} */ + /* -------------------------------------------------------------------- */ /* EdgeHash Iterator API */ +/** \name Iterator API + * \{ */ + struct EdgeHashIterator { EdgeHash *eh; unsigned int curBucket; @@ -398,3 +405,5 @@ bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi) { return (ehi->curEntry == NULL); } + +/** \} */ |