Commit: 8554fa2fad63c20ff0c23894ad0b41087d149a32
Author: Campbell Barton
Date: Mon Jul 14 23:59:47 2014 +1000
https://developer.blender.org/rB8554fa2fad63c20ff0c23894ad0b41087d149a32
GHash, EdgeHash: add debugging function to measure the hash quality
Can use to check on improvements to hash functions.
===================================================================
M source/blender/blenlib/BLI_edgehash.h
M source/blender/blenlib/BLI_ghash.h
M source/blender/blenlib/intern/BLI_ghash.c
M source/blender/blenlib/intern/edgehash.c
===================================================================
diff --git a/source/blender/blenlib/BLI_edgehash.h
b/source/blender/blenlib/BLI_edgehash.h
index c0529d9..a5ec69c 100644
--- a/source/blender/blenlib/BLI_edgehash.h
+++ b/source/blender/blenlib/BLI_edgehash.h
@@ -114,5 +114,9 @@ BLI_INLINE void BLI_edgesetIterator_getKey(EdgeSetIterator
*esi, unsigned int *r
BLI_INLINE void BLI_edgesetIterator_step(EdgeSetIterator *esi) {
BLI_edgehashIterator_step((EdgeHashIterator *)esi); }
BLI_INLINE bool BLI_edgesetIterator_isDone(EdgeSetIterator *esi) { return
BLI_edgehashIterator_isDone((EdgeHashIterator *)esi); }
+#ifdef DEBUG
+double BLI_edgehash_calc_quality(EdgeHash *eh);
+double BLI_edgeset_calc_quality(EdgeSet *es);
+#endif
#endif /* __BLI_EDGEHASH_H__ */
diff --git a/source/blender/blenlib/BLI_ghash.h
b/source/blender/blenlib/BLI_ghash.h
index a59023d..dc29a12 100644
--- a/source/blender/blenlib/BLI_ghash.h
+++ b/source/blender/blenlib/BLI_ghash.h
@@ -224,6 +224,11 @@ BLI_INLINE bool BLI_gsetIterator_done(GSetIterator *gsi) {
return BLI_ghashItera
BLI_gsetIterator_done(&gs_iter_) == false;
\
BLI_gsetIterator_step(&gs_iter_), i_++)
+#ifdef DEBUG
+double BLI_ghash_calc_quality(GHash *gh);
+double BLI_gset_calc_quality(GSet *gs);
+#endif
+
#ifdef __cplusplus
}
#endif
diff --git a/source/blender/blenlib/intern/BLI_ghash.c
b/source/blender/blenlib/intern/BLI_ghash.c
index b30553d..d24c180 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
+/** \} */
diff --git a/source/blender/blenlib/intern/edgehash.c
b/source/blender/blenlib/intern/edgehash.c
index aa571bb..b4b3f0d 100644
--- a/source/blender/blenlib/intern/edgehash.c
+++ b/source/blender/blenlib/intern/edgehash.c
@@ -623,3 +623,38 @@ void BLI_edgeset_free(EdgeSet *es)
}
/** \} */
+
+/** \name Debugging & Introspection
+ * \{ */
+#ifdef DEBUG
+
+/**
+ * Measure how well the hash function performs
+ * (1.0 is approx as good as random distribution).
+ */
+double BLI_edgehash_calc_quality(EdgeHash *eh)
+{
+ uint64_t sum = 0;
+ unsigned int i;
+
+ if (eh->nentries == 0)
+ return -1.0;
+
+ for (i = 0; i < eh->nbuckets; i++) {
+ uint64_t count = 0;
+ EdgeEntry *e;
+ for (e = eh->buckets[i]; e; e = e->next) {
+ count += 1;
+ }
+ sum += count * (count + 1);
+ }
+ return ((double)sum * (double)eh->nbuckets /
+ ((double)eh->nentries * (eh->nentries + 2 * eh->nbuckets - 1)));
+}
+double BLI_edgeset_calc_quality(EdgeSet *es)
+{
+ return BLI_edgehash_calc_quality((EdgeHash *)es);
+}
+
+#endif
+/** \} */
_______________________________________________
Bf-blender-cvs mailing list
Bf-blender-cvs@blender.org
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
