[Bf-blender-cvs] [0ef4660] temp-ghash-basis: Squashed commit of temp-ghash-experiments, minus the 'hash storage' part.
Bastien Montagne
noreply at git.blender.org
Thu Mar 19 15:33:53 CET 2015
Commit: 0ef46609ee0b02713b46a3a6280c8029a09320c6
Author: Bastien Montagne
Date: Fri Mar 13 12:15:12 2015 +0100
Branches: temp-ghash-basis
https://developer.blender.org/rB0ef46609ee0b02713b46a3a6280c8029a09320c6
Squashed commit of temp-ghash-experiments, minus the 'hash storage' part.
===================================================================
M source/blender/blenlib/BLI_ghash.h
M source/blender/blenlib/BLI_hash_mm2a.h
M source/blender/blenlib/intern/BLI_ghash.c
M source/blender/blenlib/intern/hash_mm2a.c
M source/blender/makesdna/intern/CMakeLists.txt
A tests/gtests/blenlib/BLI_ghash_performance_test.cc
A tests/gtests/blenlib/BLI_ghash_test.cc
M tests/gtests/blenlib/CMakeLists.txt
===================================================================
diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h
index bf2b412..53c9296 100644
--- a/source/blender/blenlib/BLI_ghash.h
+++ b/source/blender/blenlib/BLI_ghash.h
@@ -44,6 +44,8 @@ typedef unsigned int (*GHashHashFP) (const void *key);
typedef bool (*GHashCmpFP) (const void *a, const void *b);
typedef void (*GHashKeyFreeFP) (void *key);
typedef void (*GHashValFreeFP) (void *val);
+typedef void *(*GHashKeyCopyFP) (void *key);
+typedef void *(*GHashValCopyFP) (void *val);
typedef struct GHash GHash;
@@ -54,7 +56,8 @@ typedef struct GHashIterator {
} GHashIterator;
enum {
- GHASH_FLAG_ALLOW_DUPES = (1 << 0), /* only checked for in debug mode */
+ GHASH_FLAG_ALLOW_DUPES = (1 << 0), /* Only checked for in debug mode */
+ GHASH_FLAG_ALLOW_SHRINK = (1 << 1), /* Allow to shrink buckets' size. */
};
/* *** */
@@ -62,8 +65,12 @@ enum {
GHash *BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
+GHash *BLI_ghash_copy(GHash *gh, GHashKeyCopyFP keycopyfp,
+ GHashValCopyFP valcopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
+void BLI_ghash_reserve(GHash *gh, const unsigned int nentries_reserve);
void BLI_ghash_insert(GHash *gh, void *key, void *val);
+bool BLI_ghash_add(GHash *gh, void *key, void *val);
bool BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
void *BLI_ghash_lookup(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT;
void *BLI_ghash_lookup_default(GHash *gh, const void *key, void *val_default) ATTR_WARN_UNUSED_RESULT;
@@ -78,6 +85,29 @@ int BLI_ghash_size(GHash *gh) ATTR_WARN_UNUSED_RESULT;
void BLI_ghash_flag_set(GHash *gh, unsigned int flag);
void BLI_ghash_flag_clear(GHash *gh, unsigned int flag);
+bool BLI_ghash_isdisjoint(GHash *gh1, GHash *gh2);
+bool BLI_ghash_isequal(GHash *gh1, GHash *gh2);
+bool BLI_ghash_issubset(GHash *gh1, GHash *gh2);
+bool BLI_ghash_issuperset(GHash *gh1, GHash *gh2);
+
+GHash *BLI_ghash_union(GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp, GHash *gh1, GHash *gh2, ...);
+GHash *BLI_ghash_union_reversed(
+ GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp,
+ GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
+ GHash *gh1, GHash *gh2, ...);
+GHash *BLI_ghash_intersection(
+ GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp,
+ GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
+ GHash *gh1, GHash *gh2, ...);
+GHash *BLI_ghash_difference(
+ GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp,
+ GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
+ GHash *gh1, GHash *gh2, ...);
+GHash *BLI_ghash_symmetric_difference(
+ GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp,
+ GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
+ GHash *gh1, GHash *gh2, ...);
+
/* *** */
GHashIterator *BLI_ghashIterator_new(GHash *gh) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
@@ -127,23 +157,37 @@ unsigned int BLI_ghashutil_strhash_n(const char *key, size_t n);
CHECK_TYPE_ANY(key, char *, const char *, const char * const), \
BLI_ghashutil_strhash_p(key))
unsigned int BLI_ghashutil_strhash_p(const void *key);
+unsigned int BLI_ghashutil_strhash_p_murmur(const void *key);
bool BLI_ghashutil_strcmp(const void *a, const void *b);
#define BLI_ghashutil_inthash(key) ( \
CHECK_TYPE_ANY(&(key), int *, const int *), \
BLI_ghashutil_uinthash((unsigned int)key))
unsigned int BLI_ghashutil_uinthash(unsigned int key);
+unsigned int BLI_ghashutil_inthash_p(const void *ptr);
+unsigned int BLI_ghashutil_inthash_p_murmur(const void *ptr);
+bool BLI_ghashutil_intcmp(const void *a, const void *b);
+
+
+unsigned int BLI_ghashutil_uinthash_v4(const unsigned int key[4]);
#define BLI_ghashutil_inthash_v4(key) ( \
CHECK_TYPE_ANY(key, int *, const int *), \
BLI_ghashutil_uinthash_v4((const unsigned int *)key))
-unsigned int BLI_ghashutil_uinthash_v4(const unsigned int key[4]);
#define BLI_ghashutil_inthash_v4_p \
((GSetHashFP)BLI_ghashutil_uinthash_v4)
+#define BLI_ghashutil_uinthash_v4_p \
+ ((GSetHashFP)BLI_ghashutil_uinthash_v4)
+unsigned int BLI_ghashutil_uinthash_v4_murmur(const unsigned int key[4]);
+#define BLI_ghashutil_inthash_v4_murmur(key) ( \
+ CHECK_TYPE_ANY(key, int *, const int *), \
+ BLI_ghashutil_uinthash_v4_murmur((const unsigned int *)key))
+#define BLI_ghashutil_inthash_v4_p_murmur \
+ ((GSetHashFP)BLI_ghashutil_uinthash_v4_murmur)
+#define BLI_ghashutil_uinthash_v4_p_murmur \
+ ((GSetHashFP)BLI_ghashutil_uinthash_v4_murmur)
bool BLI_ghashutil_uinthash_v4_cmp(const void *a, const void *b);
#define BLI_ghashutil_inthash_v4_cmp \
BLI_ghashutil_uinthash_v4_cmp
-unsigned int BLI_ghashutil_inthash_p(const void *ptr);
-bool BLI_ghashutil_intcmp(const void *a, const void *b);
/** \} */
@@ -178,6 +222,7 @@ typedef struct GSet GSet;
typedef GHashHashFP GSetHashFP;
typedef GHashCmpFP GSetCmpFP;
typedef GHashKeyFreeFP GSetKeyFreeFP;
+typedef GHashKeyCopyFP GSetKeyCopyFP;
/* so we can cast but compiler sees as different */
typedef struct GSetIterator {
@@ -191,6 +236,7 @@ typedef struct GSetIterator {
GSet *BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info,
const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
GSet *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
+GSet *BLI_gset_copy(GSet *gs, GSetKeyCopyFP keycopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
int BLI_gset_size(GSet *gs) ATTR_WARN_UNUSED_RESULT;
void BLI_gset_flag_set(GSet *gs, unsigned int flag);
void BLI_gset_flag_clear(GSet *gs, unsigned int flag);
@@ -202,7 +248,17 @@ bool BLI_gset_haskey(GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT;
bool BLI_gset_remove(GSet *gs, void *key, GSetKeyFreeFP keyfreefp);
void BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp,
const unsigned int nentries_reserve);
-void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp);
+void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp);
+
+bool BLI_gset_isdisjoint(GSet *gs1, GSet *gs2);
+bool BLI_gset_isequal(GSet *gs1, GSet *gs2);
+bool BLI_gset_issubset(GSet *gs1, GSet *gs2);
+bool BLI_gset_issuperset(GSet *gs1, GSet *gs2);
+
+GSet *BLI_gset_union(GSetKeyCopyFP keycopyfp, GSet *gs1, GSet *gs2, ...);
+GSet *BLI_gset_intersection(GSetKeyCopyFP keycopyfp, GSetKeyFreeFP keyfreefp, GSet *gs1, GSet *gs2, ...);
+GSet *BLI_gset_difference(GSetKeyCopyFP keycopyfp, GSetKeyFreeFP keyfreefp, GSet *gs1, GSet *gs2, ...);
+GSet *BLI_gset_symmetric_difference(GSetKeyCopyFP keycopyfp, GSetKeyFreeFP keyfreefp, GSet *gs1, GSet *gs2, ...);
GSet *BLI_gset_ptr_new_ex(const char *info,
const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
@@ -229,10 +285,15 @@ 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
+int BLI_ghash_buckets_size(GHash *gh);
+int BLI_gset_buckets_size(GSet *gs);
+
+double BLI_ghash_calc_quality(
+ GHash *gh, double *r_load, double *r_variance,
+ double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket);
+double BLI_gset_calc_quality(
+ GSet *gs, double *r_load, double *r_variance,
+ double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket);
#ifdef __cplusplus
}
diff --git a/source/blender/blenlib/BLI_hash_mm2a.h b/source/blender/blenlib/BLI_hash_mm2a.h
index 007dec4..6beaf50 100644
--- a/source/blender/blenlib/BLI_hash_mm2a.h
+++ b/source/blender/blenlib/BLI_hash_mm2a.h
@@ -42,4 +42,6 @@ void BLI_hash_mm2a_add_int(BLI_HashMurmur2A *mm2, int data);
uint32_t BLI_hash_mm2a_end(BLI_HashMurmur2A *mm2);
+uint32_t BLI_hash_mm2(const unsigned char *data, size_t len, uint32_t seed);
+
#endif /* __BLI_HASH_MM2A_H__ */
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c
index 5360ea7..e45644e 100644
--- a/source/blender/blenlib/intern/BLI_ghash.c
+++ b/source/blender/blenlib/intern/BLI_ghash.c
@@ -36,17 +36,21 @@
#include <string.h>
#include <stdlib.h>
+#include <stdarg.h>
#include <limits.h>
#include "MEM_guardedalloc.h"
#include "BLI_sys_types.h" /* for intptr_t support */
#include "BLI_utildefines.h"
+#include "BLI_hash_mm2a.h"
#include "BLI_mempool.h"
#include "BLI_ghash.h"
#include "BLI_strict_flags.h"
+#define GHASH_USE_MODULO_BUCKETS
+/* Also used by smallhash! */
const unsigned int hashsizes[] = {
5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209,
16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169,
@@ -54,24 +58,36 @@ const unsigned int hashsizes[] = {
268435459
};
-/* internal flag to ensure sets values aren't used */
-#ifndef NDEBUG
-# define GHASH_FLAG_IS_SET (1 << 8)
-# define IS_GHASH_ASSERT(gh) BLI_assert((gh->flag & GHASH_FLAG_IS_SET) == 0)
-// # define IS_GSET_ASSERT(gs) BLI_assert((gs->flag & GHASH_FLAG_IS_SET) != 0)
+#ifdef GHASH_USE_MODULO_BUCKETS
+# define GHASH_MAX_SIZE 27
#else
-# define IS_GHASH_ASSERT(gh)
-// # define IS_GSET_ASSERT(eh)
+# define GHASH_BUCKET_BIT_MIN 2
+# define GHASH_BUCKET_BIT_MAX 28 /* About 268M of buckets... */
#endif
+#define GHASH_LIMIT_GROW(_nbkt) ((_nbkt)
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list