[Bf-blender-cvs] [d55fd7e] temp-ghash-basis: Address coments from review.
Bastien Montagne
noreply at git.blender.org
Thu Mar 19 15:33:58 CET 2015
Commit: d55fd7edc4a23d0f7cec84c7aed5f7facdf7b44a
Author: Bastien Montagne
Date: Thu Mar 19 13:50:41 2015 +0100
Branches: temp-ghash-basis
https://developer.blender.org/rBd55fd7edc4a23d0f7cec84c7aed5f7facdf7b44a
Address coments from review.
===================================================================
M source/blender/blenlib/BLI_ghash.h
M source/blender/blenlib/intern/BLI_ghash.c
===================================================================
diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h
index adfa7fb..0243ed6 100644
--- a/source/blender/blenlib/BLI_ghash.h
+++ b/source/blender/blenlib/BLI_ghash.h
@@ -58,6 +58,9 @@ typedef struct GHashIterator {
enum {
GHASH_FLAG_ALLOW_DUPES = (1 << 0), /* Only checked for in debug mode */
GHASH_FLAG_ALLOW_SHRINK = (1 << 1), /* Allow to shrink buckets' size. */
+
+ /* Internal usage only */
+ GHASH_FLAG_IS_GSET = (1 << 16), /* Whether the GHash is actually used as GSet (no value storage). */
};
/* *** */
@@ -255,12 +258,14 @@ BLI_INLINE bool BLI_gsetIterator_done(GSetIterator *gsi) { return BLI_ghashItera
int BLI_ghash_buckets_size(GHash *gh);
int BLI_gset_buckets_size(GSet *gs);
-double BLI_ghash_calc_quality(
+double BLI_ghash_calc_quality_ex(
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(
+double BLI_gset_calc_quality_ex(
GSet *gs, double *r_load, double *r_variance,
double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket);
+double BLI_ghash_calc_quality(GHash *gh);
+double BLI_gset_calc_quality(GSet *gs);
#ifdef __cplusplus
}
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c
index cc0f6c4..6a37aa1 100644
--- a/source/blender/blenlib/intern/BLI_ghash.c
+++ b/source/blender/blenlib/intern/BLI_ghash.c
@@ -103,8 +103,7 @@ struct GHash {
#endif
unsigned int nentries;
- unsigned short flag;
- bool is_gset;
+ unsigned int flag;
};
@@ -112,8 +111,8 @@ BLI_INLINE void entry_copy(
GHash *gh_dst, Entry *dst, GHash *gh_src, Entry *src,
const unsigned int UNUSED(hash), GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
{
- const bool is_gset_dst = gh_dst->is_gset;
- const bool is_gset_src = gh_src->is_gset;
+ const bool is_gset_dst = (gh_dst->flag & GHASH_FLAG_IS_GSET) != 0;
+ const bool is_gset_src = (gh_src->flag & GHASH_FLAG_IS_GSET) != 0;
dst->key = (keycopyfp) ? keycopyfp(src->key) : src->key;
@@ -243,31 +242,34 @@ BLI_INLINE void ghash_expand_buckets(
new_nbuckets = gh->nbuckets;
- while ((nentries > gh->limit_grow) &&
#ifdef GHASH_USE_MODULO_BUCKETS
- (gh->cursize < GHASH_MAX_SIZE - 1))
+ while ((nentries > gh->limit_grow) && (gh->cursize < GHASH_MAX_SIZE - 1))
{
new_nbuckets = hashsizes[++gh->cursize];
+ gh->limit_grow = GHASH_LIMIT_GROW(new_nbuckets);
+ }
#else
- (gh->bucket_bit < GHASH_BUCKET_BIT_MAX))
+ while ((nentries > gh->limit_grow) && (gh->bucket_bit < GHASH_BUCKET_BIT_MAX))
{
new_nbuckets = 1u << ++gh->bucket_bit;
-#endif
gh->limit_grow = GHASH_LIMIT_GROW(new_nbuckets);
}
+#endif
+
if (force_shrink || (gh->flag & GHASH_FLAG_ALLOW_SHRINK)) {
- while ((nentries < gh->limit_shrink) &&
#ifdef GHASH_USE_MODULO_BUCKETS
- (gh->cursize > gh->size_min))
+ while ((nentries < gh->limit_shrink) && (gh->cursize > gh->size_min))
{
new_nbuckets = hashsizes[--gh->cursize];
-#else
- (gh->bucket_bit > gh->bucket_bit_min))
- {
- new_nbuckets = 1u << --gh->bucket_bit;
-#endif
gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets);
}
+#else
+ while ((nentries < gh->limit_shrink) && (gh->bucket_bit > gh->bucket_bit_min))
+ {
+ new_nbuckets = 1u << --gh->bucket_bit;
+ gh->limit_shrink = GHASH_LIMIT_SHRINK(new_nbuckets);
+ }
+#endif
}
if (user_defined) {
@@ -319,7 +321,7 @@ BLI_INLINE void ghash_buckets_reset(GHash *gh, const unsigned int nentries)
* Takes hash and bucket_hash arguments to avoid calling #ghash_keyhash and #ghash_bucket_hash multiple times.
*/
BLI_INLINE Entry *ghash_lookup_entry_ex(
- GHash *gh, const void *key, const unsigned int UNUSED(hash), const unsigned int bucket_hash)
+ GHash *gh, const void *key, const unsigned int bucket_hash)
{
Entry *e;
/* If we do not store GHash, not worth computing it for each entry here!
@@ -339,8 +341,7 @@ BLI_INLINE Entry *ghash_lookup_entry_ex(
* Useful when modifying buckets somehow (like removing an entry...).
*/
BLI_INLINE Entry *ghash_lookup_entry_prev_ex(
- GHash *gh, const void *key, Entry **e_prev_r,
- const unsigned int UNUSED(hash), const unsigned int bucket_hash)
+ GHash *gh, const void *key, Entry **e_prev_r, const unsigned int bucket_hash)
{
Entry *e;
@@ -363,12 +364,11 @@ BLI_INLINE Entry *ghash_lookup_entry(GHash *gh, const void *key)
{
const unsigned int hash = ghash_keyhash(gh, key);
const unsigned int bucket_hash = ghash_bucket_hash(gh, hash);
- return ghash_lookup_entry_ex(gh, key, hash, bucket_hash);
+ return ghash_lookup_entry_ex(gh, key, bucket_hash);
}
static GHash *ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
- const unsigned int nentries_reserve,
- const bool is_gset)
+ const unsigned int nentries_reserve, const bool is_gset)
{
GHash *gh = MEM_mallocN(sizeof(*gh), info);
@@ -378,7 +378,9 @@ static GHash *ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
gh->buckets = NULL;
ghash_buckets_reset(gh, nentries_reserve);
gh->entrypool = BLI_mempool_create((unsigned int)GHASH_ENTRY_SIZE(is_gset), 64, 64, BLI_MEMPOOL_NOP);
- gh->is_gset = is_gset;
+ if (is_gset) {
+ gh->flag |= GHASH_FLAG_IS_GSET;
+ }
return gh;
}
@@ -388,12 +390,12 @@ static GHash *ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
* Takes hash and bucket_hash arguments to avoid calling #ghash_keyhash and #ghash_bucket_hash multiple times.
*/
BLI_INLINE void ghash_insert_ex(
- GHash *gh, void *key, void *val, const unsigned int UNUSED(hash), const unsigned int bucket_hash)
+ GHash *gh, void *key, void *val, const unsigned int bucket_hash)
{
GHashEntry *e = BLI_mempool_alloc(gh->entrypool);
BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0));
- BLI_assert(!gh->is_gset);
+ BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
e->e.next = gh->buckets[bucket_hash];
e->e.key = key;
@@ -407,12 +409,12 @@ BLI_INLINE void ghash_insert_ex(
* Insert function that doesn't set the value (use for GSet)
*/
BLI_INLINE void ghash_insert_ex_keyonly(
- GHash *gh, void *key, const unsigned int UNUSED(hash), const unsigned int bucket_hash)
+ GHash *gh, void *key, const unsigned int bucket_hash)
{
GSetEntry *e = BLI_mempool_alloc(gh->entrypool);
BLI_assert((gh->flag & GHASH_FLAG_ALLOW_DUPES) || (BLI_ghash_haskey(gh, key) == 0));
- BLI_assert(gh->is_gset);
+ BLI_assert((gh->flag & GHASH_FLAG_IS_GSET) != 0);
e->next = gh->buckets[bucket_hash];
e->key = key;
@@ -426,7 +428,7 @@ BLI_INLINE void ghash_insert(GHash *gh, void *key, void *val)
const unsigned int hash = ghash_keyhash(gh, key);
const unsigned int bucket_hash = ghash_bucket_hash(gh, hash);
- ghash_insert_ex(gh, key, val, hash, bucket_hash);
+ ghash_insert_ex(gh, key, val, bucket_hash);
}
BLI_INLINE bool ghash_insert_safe(
@@ -434,9 +436,9 @@ BLI_INLINE bool ghash_insert_safe(
{
const unsigned int hash = ghash_keyhash(gh, key);
const unsigned int bucket_hash = ghash_bucket_hash(gh, hash);
- GHashEntry *e = (GHashEntry *)ghash_lookup_entry_ex(gh, key, hash, bucket_hash);
+ GHashEntry *e = (GHashEntry *)ghash_lookup_entry_ex(gh, key, bucket_hash);
- BLI_assert(!gh->is_gset);
+ BLI_assert(!(gh->flag & GHASH_FLAG_IS_GSET));
if (e) {
if (override) {
@@ -448,7 +450,7 @@ BLI_INLINE bool ghash_insert_safe(
return false;
}
else {
- ghash_insert_ex(gh, key, val, hash, bucket_hash);
+ ghash_insert_ex(gh, key, val, bucket_hash);
return true;
}
}
@@ -457,9 +459,9 @@ BLI_INLINE bool ghash_insert_safe_keyonly(GHash *gh, void *key, const bool overr
{
const unsigned int hash = ghash_keyhash(gh, key);
const unsigned int bucket_hash = ghash_bucket_hash(gh, hash);
- GSetEntry *e = ghash_lookup_entry_ex(gh, key, hash, bucket_hash);
+ GSetEntry *e = ghash_lookup_entry_ex(gh, key, bucket_hash);
- BLI_assert(gh->is_gset);
+ BLI_assert((gh->flag & GHASH_FLAG_IS_GSET) != 0);
if (e) {
if (override) {
@@ -469,7 +471,7 @@ BLI_INLINE bool ghash_insert_safe_keyonly(GHash *gh, void *key, const bool overr
return false;
}
else {
- ghash_insert_ex_keyonly(gh, key, hash, bucket_hash);
+ ghash_insert_ex_keyonly(gh, key, bucket_hash);
return true;
}
}
@@ -479,12 +481,12 @@ BLI_INLINE bool ghash_insert_safe_keyonly(GHash *gh, void *key, const bool overr
*/
static Entry *ghash_remove_ex(
GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
- const unsigned int hash, const unsigned int bucket_hash)
+ const unsigned int bucket_hash)
{
Entry *e_prev;
- Entry *e = ghash_lookup_entry_prev_ex(gh, key, &e_prev, hash, bucket_hash);
+ Entry *e = ghash_lookup_entry_prev_ex(gh, key, &e_prev, bucket_hash);
- BLI_assert(!valfreefp|| !gh->is_gset);
+ BLI_assert(!valfreefp|| !(gh->flag & GHASH_FLAG_IS_GSET));
if (e) {
if (keyfreefp) keyfreefp(e->key);
@@ -507,7 +509,7 @@ static void ghash_free_cb(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP va
unsigned int i;
BLI_assert(keyfreefp || valfreefp);
- BLI_assert(!valfreefp|| !gh->is_gset);
+ BLI_assert(!valfreefp|| !(gh->flag & GHASH_FLAG_IS_GSET));
for (i = 0; i < gh->nbuckets; i++) {
Entry *e;
@@ -526,10 +528,11 @@ static GHash *ghash_copy(GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP val
{
GHash *gh_new;
unsigned int i;
+ const bool is_gset = (gh->flag & GHASH_FLAG_IS_GSET) != 0;
- BLI_assert(!valcopyfp || !gh->is_gset);
+ BLI_assert(!valcopyfp || !is_gset);
- gh_new = ghash_new(gh->hashfp, gh->cmpfp, __func__, 0, gh->is_gset);
+ gh_new = ghash_new(gh->hashfp, gh->cmpfp, __func__, 0, is_gset);
ghash_expand_buckets(gh_new, gh->nentries, false, false);
for (i = 0; i < gh->nbuckets; i++) {
@@ -657,7 +660,7 @@ bool BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreef
void *BLI_ghash_lookup(GHash *gh, const void *key)
{
GHashEntry *e = (GHashEntry *)ghash_lookup_entry(gh, key);
- BLI_assert(!gh->is_gset);
+ BLI_assert
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list