Cleanup: remove redundant doxygen \file argument
[blender.git] / source / blender / blenlib / intern / smallhash.c
index adcd10f4b72f2f8055e36e9034c53bcaa8d8d2d0..9c4f60322e68b779041934514a24e41bf4ac5fa4 100644 (file)
@@ -1,6 +1,4 @@
 /*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
  * This program is free software; you can redistribute it and/or
  * modify it under the terms of the GNU General Public License
  * as published by the Free Software Foundation; either version 2
  *
  * The Original Code is Copyright (C) 2008 Blender Foundation.
  * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): Joseph Eagar.
- *
- * ***** END GPL LICENSE BLOCK *****
  */
 
-/** \file blender/blenlib/intern/smallhash.c
- *  \ingroup bli
+/** \file \ingroup bli
  *
- * A light stack-friendly hash library, it uses stack space for smallish hash tables
- * but falls back to heap memory once the stack limits reached.
+ * A light stack-friendly hash library, it uses stack space for relatively small, fixed size hash tables
+ * but falls back to heap memory once the stack limits reached (#SMSTACKSIZE).
  *
- * based on a doubling non-chaining approach  which uses more buckets then entries
+ * based on a doubling hashing approach (non-chaining) which uses more buckets then entries
  * stepping over buckets when two keys share the same hash so any key can find a free bucket.
  *
+ * See: https://en.wikipedia.org/wiki/Double_hashing
+ *
+ * \warning This should _only_ be used for small hashes where allocating a hash every time is unacceptable.
+ * Otherwise #GHash should be used instead.
  *
  * #SmallHashEntry.key
  * - ``SMHASH_KEY_UNUSED`` means the key in the cell has not been initialized.
@@ -48,7 +43,8 @@
 
 #include <string.h>
 #include <stdlib.h>
-#include <BLI_sys_types.h>
+
+#include "BLI_sys_types.h"
 
 #include "MEM_guardedalloc.h"
 
@@ -64,8 +60,8 @@
 
 /* typically this re-assigns 'h' */
 #define SMHASH_NEXT(h, hoff)  ( \
-       CHECK_TYPE_INLINE(&(h),    unsigned int *), \
-       CHECK_TYPE_INLINE(&(hoff), unsigned int *), \
+       CHECK_TYPE_INLINE(&(h),    uint *), \
+       CHECK_TYPE_INLINE(&(hoff), uint *), \
        ((h) + (((hoff) = ((hoff) * 2) + 1), (hoff))) \
        )
 
@@ -82,12 +78,17 @@ BLI_INLINE bool smallhash_val_is_used(const void *val)
 #endif
 }
 
-extern const unsigned int hashsizes[];
+extern const uint hashsizes[];
+
+BLI_INLINE uint smallhash_key(const uintptr_t key)
+{
+       return (uint)key;
+}
 
 /**
  * Check if the number of items in the smallhash is large enough to require more buckets.
  */
-BLI_INLINE bool smallhash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets)
+BLI_INLINE bool smallhash_test_expand_buckets(const uint nentries, const uint nbuckets)
 {
        /* (approx * 1.5) */
        return (nentries + (nentries >> 1)) > nbuckets;
@@ -95,7 +96,7 @@ BLI_INLINE bool smallhash_test_expand_buckets(const unsigned int nentries, const
 
 BLI_INLINE void smallhash_init_empty(SmallHash *sh)
 {
-       unsigned int i;
+       uint i;
 
        for (i = 0; i < sh->nbuckets; i++) {
                sh->buckets[i].key = SMHASH_KEY_UNUSED;
@@ -106,22 +107,22 @@ BLI_INLINE void smallhash_init_empty(SmallHash *sh)
 /**
  * Increase initial bucket size to match a reserved amount.
  */
-BLI_INLINE void smallhash_buckets_reserve(SmallHash *sh, const unsigned int nentries_reserve)
+BLI_INLINE void smallhash_buckets_reserve(SmallHash *sh, const uint nentries_reserve)
 {
        while (smallhash_test_expand_buckets(nentries_reserve, sh->nbuckets)) {
                sh->nbuckets = hashsizes[++sh->cursize];
        }
 }
 
-BLI_INLINE SmallHashEntry *smallhash_lookup(SmallHash *sh, const uintptr_t key)
+BLI_INLINE SmallHashEntry *smallhash_lookup(const SmallHash *sh, const uintptr_t key)
 {
        SmallHashEntry *e;
-       unsigned int h = (unsigned int)key;
-       unsigned int hoff = 1;
+       uint h = smallhash_key(key);
+       uint hoff = 1;
 
        BLI_assert(key != SMHASH_KEY_UNUSED);
 
-       /* note: there are always more buckets then entries,
+       /* note: there are always more buckets than entries,
         * so we know there will always be a free bucket if the key isn't found. */
        for (e = &sh->buckets[h % sh->nbuckets];
             e->val != SMHASH_CELL_FREE;
@@ -140,8 +141,8 @@ BLI_INLINE SmallHashEntry *smallhash_lookup(SmallHash *sh, const uintptr_t key)
 BLI_INLINE SmallHashEntry *smallhash_lookup_first_free(SmallHash *sh, const uintptr_t key)
 {
        SmallHashEntry *e;
-       unsigned int h = (unsigned int)key;
-       unsigned int hoff = 1;
+       uint h = smallhash_key(key);
+       uint hoff = 1;
 
        for (e = &sh->buckets[h % sh->nbuckets];
             smallhash_val_is_used(e->val);
@@ -153,12 +154,12 @@ BLI_INLINE SmallHashEntry *smallhash_lookup_first_free(SmallHash *sh, const uint
        return e;
 }
 
-BLI_INLINE void smallhash_resize_buckets(SmallHash *sh, const unsigned int nbuckets)
+BLI_INLINE void smallhash_resize_buckets(SmallHash *sh, const uint nbuckets)
 {
        SmallHashEntry *buckets_old = sh->buckets;
-       const unsigned int nbuckets_old = sh->nbuckets;
+       const uint nbuckets_old = sh->nbuckets;
        const bool was_alloc = (buckets_old != sh->buckets_stack);
-       unsigned int i = 0;
+       uint i = 0;
 
        BLI_assert(sh->nbuckets != nbuckets);
        if (nbuckets <= SMSTACKSIZE) {
@@ -190,7 +191,7 @@ BLI_INLINE void smallhash_resize_buckets(SmallHash *sh, const unsigned int nbuck
 }
 
 void BLI_smallhash_init_ex(SmallHash *sh,
-                           const unsigned int nentries_reserve)
+                           const uint nentries_reserve)
 {
        /* assume 'sh' is uninitialized */
 
@@ -216,7 +217,7 @@ void BLI_smallhash_init(SmallHash *sh)
        BLI_smallhash_init_ex(sh, 0);
 }
 
-/*NOTE: does *not* free *sh itself!  only the direct data!*/
+/* NOTE: does *not* free *sh itself!  only the direct data! */
 void BLI_smallhash_release(SmallHash *sh)
 {
        if (sh->buckets != sh->buckets_stack) {
@@ -241,6 +242,26 @@ void BLI_smallhash_insert(SmallHash *sh, uintptr_t key, void *val)
        e->val = val;
 }
 
+/**
+ * Inserts a new value to a key that may already be in ghash.
+ *
+ * Avoids #BLI_smallhash_remove, #BLI_smallhash_insert calls (double lookups)
+ *
+ * \returns true if a new key has been added.
+ */
+bool BLI_smallhash_reinsert(SmallHash *sh, uintptr_t key, void *item)
+{
+       SmallHashEntry *e = smallhash_lookup(sh, key);
+       if (e) {
+               e->val = item;
+               return false;
+       }
+       else {
+               BLI_smallhash_insert(sh, key, item);
+               return true;
+       }
+}
+
 #ifdef USE_REMOVE
 bool BLI_smallhash_remove(SmallHash *sh, uintptr_t key)
 {
@@ -259,33 +280,33 @@ bool BLI_smallhash_remove(SmallHash *sh, uintptr_t key)
 }
 #endif
 
-void *BLI_smallhash_lookup(SmallHash *sh, uintptr_t key)
+void *BLI_smallhash_lookup(const SmallHash *sh, uintptr_t key)
 {
        SmallHashEntry *e = smallhash_lookup(sh, key);
 
        return e ? e->val : NULL;
 }
 
-void **BLI_smallhash_lookup_p(SmallHash *sh, uintptr_t key)
+void **BLI_smallhash_lookup_p(const SmallHash *sh, uintptr_t key)
 {
        SmallHashEntry *e = smallhash_lookup(sh, key);
 
        return e ? &e->val : NULL;
 }
 
-bool BLI_smallhash_haskey(SmallHash *sh, uintptr_t key)
+bool BLI_smallhash_haskey(const SmallHash *sh, uintptr_t key)
 {
        SmallHashEntry *e = smallhash_lookup(sh, key);
 
        return (e != NULL);
 }
 
-int BLI_smallhash_count(SmallHash *sh)
+int BLI_smallhash_len(const SmallHash *sh)
 {
        return (int)sh->nentries;
 }
 
-void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
+BLI_INLINE SmallHashEntry *smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
 {
        while (iter->i < iter->sh->nbuckets) {
                if (smallhash_val_is_used(iter->sh->buckets[iter->i].val)) {
@@ -293,7 +314,7 @@ void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
                                *key = iter->sh->buckets[iter->i].key;
                        }
 
-                       return iter->sh->buckets[iter->i++].val;
+                       return &iter->sh->buckets[iter->i++];
                }
 
                iter->i++;
@@ -302,7 +323,21 @@ void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
        return NULL;
 }
 
-void *BLI_smallhash_iternew(SmallHash *sh, SmallHashIter *iter, uintptr_t *key)
+void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
+{
+       SmallHashEntry *e = smallhash_iternext(iter, key);
+
+       return e ? e->val : NULL;
+}
+
+void **BLI_smallhash_iternext_p(SmallHashIter *iter, uintptr_t *key)
+{
+       SmallHashEntry *e = smallhash_iternext(iter, key);
+
+       return e ? &e->val : NULL;
+}
+
+void *BLI_smallhash_iternew(const SmallHash *sh, SmallHashIter *iter, uintptr_t *key)
 {
        iter->sh = sh;
        iter->i = 0;
@@ -310,12 +345,24 @@ void *BLI_smallhash_iternew(SmallHash *sh, SmallHashIter *iter, uintptr_t *key)
        return BLI_smallhash_iternext(iter, key);
 }
 
+void **BLI_smallhash_iternew_p(const SmallHash *sh, SmallHashIter *iter, uintptr_t *key)
+{
+       iter->sh = sh;
+       iter->i = 0;
+
+       return BLI_smallhash_iternext_p(iter, key);
+}
+
+
+/** \name Debugging & Introspection
+ * \{ */
+
 /* note, this was called _print_smhash in knifetool.c
  * it may not be intended for general use - campbell */
 #if 0
 void BLI_smallhash_print(SmallHash *sh)
 {
-       unsigned int i, linecol = 79, c = 0;
+       uint i, linecol = 79, c = 0;
 
        printf("{");
        for (i = 0; i < sh->nbuckets; i++) {
@@ -326,7 +373,7 @@ void BLI_smallhash_print(SmallHash *sh)
                        printf("--f-");
                }
                else {
-                       printf("%2x", (unsigned int)sh->buckets[i].key);
+                       printf("%2x", (uint)sh->buckets[i].key);
                }
 
                if (i != sh->nbuckets - 1)
@@ -343,3 +390,41 @@ void BLI_smallhash_print(SmallHash *sh)
        fflush(stdout);
 }
 #endif
+
+#ifdef DEBUG
+/**
+ * Measure how well the hash function performs
+ * (1.0 is perfect - no stepping needed).
+ *
+ * Smaller is better!
+ */
+double BLI_smallhash_calc_quality(SmallHash *sh)
+{
+       uint64_t sum = 0;
+       uint i;
+
+       if (sh->nentries == 0)
+               return -1.0;
+
+       for (i = 0; i < sh->nbuckets; i++) {
+               if (sh->buckets[i].key != SMHASH_KEY_UNUSED) {
+                       uint64_t count = 0;
+                       SmallHashEntry *e, *e_final = &sh->buckets[i];
+                       uint h = smallhash_key(e_final->key);
+                       uint hoff = 1;
+
+                       for (e = &sh->buckets[h % sh->nbuckets];
+                            e != e_final;
+                            h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets])
+                       {
+                               count += 1;
+                       }
+
+                       sum += count;
+               }
+       }
+       return ((double)(sh->nentries + sum) / (double)sh->nentries);
+}
+#endif
+
+/** \} */