[Bf-blender-cvs] [1518006] master: Smallhash: BLI_smallhash_calc_quality

[Campbell Barton]

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
+
+/** \} */