GHash, EdgeHash: add debugging function to measure the hash quality

Can use to check on improvements to hash functions.

1 files changed, 36 insertions, 0 deletions

diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c
index b30553d0b5e..d24c180dae6 100644
--- a/source/blender/blenlib/intern/BLI_ghash.c
+++ b/source/blender/blenlib/intern/BLI_ghash.c
@@ -996,3 +996,39 @@ GSet *BLI_gset_pair_new(const char *info)
 }
 
 /** \} */
+
+
+/** \name Debugging & Introspection
+ * \{ */
+#ifdef DEBUG
+
+/**
+ * Measure how well the hash function performs
+ * (1.0 is approx as good as random distribution).
+ */
+double BLI_ghash_calc_quality(GHash *gh)
+{
+	uint64_t sum = 0;
+	unsigned int i;
+
+	if (gh->nentries == 0)
+		return -1.0;
+
+	for (i = 0; i < gh->nbuckets; i++) {
+		uint64_t count = 0;
+		Entry *e;
+		for (e = gh->buckets[i]; e; e = e->next) {
+			count += 1;
+		}
+		sum += count * (count + 1);
+	}
+	return ((double)sum * (double)gh->nbuckets /
+	        ((double)gh->nentries * (gh->nentries + 2 * gh->nbuckets - 1)));
+}
+double BLI_gset_calc_quality(GSet *gs)
+{
+	return BLI_ghash_calc_quality((GHash *)gs);
+}
+
+#endif
+/** \} */