Commit: 151800662fc76998e42796efcc4d9b181c57c1b3
Author: Campbell Barton
Date: Sat Aug 23 21:15:15 2014 +1000
Branches: master
https://developer.blender.org/rB151800662fc76998e42796efcc4d9b181c57c1b3
Smallhash: BLI_smallhash_calc_quality
Also add inline hashing function to measure different methods.
===================================================================
M source/blender/blenlib/BLI_smallhash.h
M source/blender/blenlib/intern/smallhash.c
===================================================================
diff --git a/source/blender/blenlib/BLI_smallhash.h
b/source/blender/blenlib/BLI_smallhash.h
index b2fec6f..b80044b 100644
--- a/source/blender/blenlib/BLI_smallhash.h
+++ b/source/blender/blenlib/BLI_smallhash.h
@@ -70,4 +70,8 @@ void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t
*key) ATTR_NONNUL
void *BLI_smallhash_iternew(SmallHash *sh, SmallHashIter *iter, uintptr_t
*key) ATTR_NONNULL(1) ATTR_WARN_UNUSED_RESULT;
/* void BLI_smallhash_print(SmallHash *sh); */ /* UNUSED */
+#ifdef DEBUG
+double BLI_smallhash_calc_quality(SmallHash *sh);
+#endif
+
#endif /* __BLI_SMALLHASH_H__ */
diff --git a/source/blender/blenlib/intern/smallhash.c
b/source/blender/blenlib/intern/smallhash.c
index adcd10f..0cf9f69 100644
--- a/source/blender/blenlib/intern/smallhash.c
+++ b/source/blender/blenlib/intern/smallhash.c
@@ -84,6 +84,11 @@ BLI_INLINE bool smallhash_val_is_used(const void *val)
extern const unsigned int hashsizes[];
+BLI_INLINE unsigned int smallhash_key(const uintptr_t key)
+{
+ return (unsigned int)key;
+}
+
/**
* Check if the number of items in the smallhash is large enough to require
more buckets.
*/
@@ -116,7 +121,7 @@ BLI_INLINE void smallhash_buckets_reserve(SmallHash *sh,
const unsigned int nent
BLI_INLINE SmallHashEntry *smallhash_lookup(SmallHash *sh, const uintptr_t key)
{
SmallHashEntry *e;
- unsigned int h = (unsigned int)key;
+ unsigned int h = smallhash_key(key);
unsigned int hoff = 1;
BLI_assert(key != SMHASH_KEY_UNUSED);
@@ -140,7 +145,7 @@ 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 h = smallhash_key(key);
unsigned int hoff = 1;
for (e = &sh->buckets[h % sh->nbuckets];
@@ -310,6 +315,9 @@ void *BLI_smallhash_iternew(SmallHash *sh, SmallHashIter
*iter, uintptr_t *key)
return BLI_smallhash_iternext(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
@@ -343,3 +351,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;
+ unsigned int 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];
+ unsigned int h = smallhash_key(e_final->key);
+ unsigned int 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
+
+/** \} */
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
