Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source
diff options
context:
space:
mode:
authorCampbell Barton <ideasman42@gmail.com>2014-08-23 15:15:15 +0400
committerCampbell Barton <ideasman42@gmail.com>2014-08-23 15:18:11 +0400
commit151800662fc76998e42796efcc4d9b181c57c1b3 (patch)
tree66612d096411457442a80a4ad00539364418a6a9 /source
parentfb49c5aa5662da3c2434c75ea6283408c01d6c23 (diff)
Smallhash: BLI_smallhash_calc_quality
Also add inline hashing function to measure different methods.
Diffstat (limited to 'source')
-rw-r--r--source/blender/blenlib/BLI_smallhash.h4
-rw-r--r--source/blender/blenlib/intern/smallhash.c50
2 files changed, 52 insertions, 2 deletions
diff --git a/source/blender/blenlib/BLI_smallhash.h b/source/blender/blenlib/BLI_smallhash.h
index b2fec6f870c..b80044bccff 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 adcd10f4b72..0cf9f69b9ae 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
+
+/** \} */