doxygen docs for ghash/edgehash
authorCampbell Barton <ideasman42@gmail.com>
Sun, 25 Aug 2013 12:17:46 +0000 (12:17 +0000)
committerCampbell Barton <ideasman42@gmail.com>
Sun, 25 Aug 2013 12:17:46 +0000 (12:17 +0000)
source/blender/blenlib/intern/BLI_ghash.c
source/blender/blenlib/intern/edgehash.c

index 918fc55df722fca75a8e9af2879bfce3fed20e70..21326227794005cbd3bd63ce57d030864dae01ba 100644 (file)
@@ -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);
-}
+/** \} */
index dac107187f3ede376b5afc0c05ffd13de123d57a..cae233567823b862d0ffea2e5ed03ba240a251ea 100644 (file)
@@ -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);
 }
+
+/** \} */