[Bf-blender-cvs] [ced0a84] temp-ghash-experiments: Cleanup (reduce a bit passing size of entries around by storing it in ghash itself).
Bastien Montagne
noreply at git.blender.org
Fri Mar 6 14:06:41 CET 2015
Commit: ced0a84e86e39dac83b1aa2220806a83176797e8
Author: Bastien Montagne
Date: Thu Mar 5 17:25:26 2015 +0100
Branches: temp-ghash-experiments
https://developer.blender.org/rBced0a84e86e39dac83b1aa2220806a83176797e8
Cleanup (reduce a bit passing size of entries around by storing it in ghash itself).
===================================================================
M source/blender/blenlib/intern/BLI_ghash.c
===================================================================
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c
index 97dd363..4963805 100644
--- a/source/blender/blenlib/intern/BLI_ghash.c
+++ b/source/blender/blenlib/intern/BLI_ghash.c
@@ -119,6 +119,9 @@ struct GHash {
unsigned int nentries;
unsigned int flag;
+
+ /* Entries metadata */
+ size_t entry_size;
};
/* -------------------------------------------------------------------- */
@@ -343,6 +346,7 @@ 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)entry_size, 64, 64, BLI_MEMPOOL_NOP);
+ gh->entry_size = entry_size;
return gh;
}
@@ -490,10 +494,11 @@ static void ghash_free_cb(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP va
/**
* Copy the GHash.
*/
-static GHash *ghash_copy(GHash *gh, const size_t entry_size, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
+static GHash *ghash_copy(GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
{
GHash *gh_new;
unsigned int i;
+ const size_t entry_size = gh->entry_size;
gh_new = ghash_new(gh->hashfp, gh->cmpfp, __func__, 0, entry_size);
ghash_expand_buckets(gh_new, gh->nentries, false, false);
@@ -526,7 +531,7 @@ static GHash *ghash_copy(GHash *gh, const size_t entry_size, GHashKeyCopyFP keyc
* If \a reverse is True, entries present in latest GHash will override those in former GHash.
*/
static GHash *ghash_union(
- const bool reverse, const size_t entry_size,
+ const bool reverse,
GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp,
GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
GHash *gh1, GHash *gh2, va_list arg)
@@ -536,38 +541,43 @@ static GHash *ghash_union(
BLI_assert(ghn);
if (!gh1) {
- gh1 = ghash_copy(ghn, entry_size, keycopyfp, valcopyfp);
+ gh1 = ghash_copy(ghn, keycopyfp, valcopyfp);
ghn = va_arg(arg, GHash *);
}
- for ( ; ghn; ghn = va_arg(arg, GHash *)) {
- unsigned int i;
+ {
+ const size_t entry_size = gh1->entry_size;
- BLI_assert(gh1->cmpfp == ghn->cmpfp);
- BLI_assert(gh1->hashfp == ghn->hashfp);
+ for ( ; ghn; ghn = va_arg(arg, GHash *)) {
+ unsigned int i;
- for (i = 0; i < ghn->nbuckets; i++) {
- Entry *e;
+ BLI_assert(gh1->cmpfp == ghn->cmpfp);
+ BLI_assert(gh1->hashfp == ghn->hashfp);
+ BLI_assert(entry_size == ghn->entry_size);
- for (e = ghn->buckets[i]; e; e = e->next) {
- Entry *e_gh1;
- const unsigned int gh1_bucket_hash = ghash_bucket_hash(gh1, e->hash);
+ for (i = 0; i < ghn->nbuckets; i++) {
+ Entry *e;
- if ((e_gh1 = ghash_lookup_entry_ex(gh1, e->key, e->hash, gh1_bucket_hash)) == NULL) {
- Entry *e_new = BLI_mempool_alloc(gh1->entrypool);
+ for (e = ghn->buckets[i]; e; e = e->next) {
+ Entry *e_gh1;
+ const unsigned int gh1_bucket_hash = ghash_bucket_hash(gh1, e->hash);
- entry_copy(e_new, e, entry_size, keycopyfp, valcopyfp);
+ if ((e_gh1 = ghash_lookup_entry_ex(gh1, e->key, e->hash, gh1_bucket_hash)) == NULL) {
+ Entry *e_new = BLI_mempool_alloc(gh1->entrypool);
- /* As with copy, this does not preserve order (but this would be even less meaningful here). */
- e_new->next = gh1->buckets[gh1_bucket_hash];
- gh1->buckets[gh1_bucket_hash] = e_new;
- ghash_expand_buckets(gh1, ++gh1->nentries, false, false);
- }
- else if (reverse) {
- if (keyfreefp) keyfreefp(e_gh1->key);
- if (valfreefp) valfreefp(e_gh1->val);
+ entry_copy(e_new, e, entry_size, keycopyfp, valcopyfp);
+
+ /* As with copy, this does not preserve order (but this would be even less meaningful here). */
+ e_new->next = gh1->buckets[gh1_bucket_hash];
+ gh1->buckets[gh1_bucket_hash] = e_new;
+ ghash_expand_buckets(gh1, ++gh1->nentries, false, false);
+ }
+ else if (reverse) {
+ if (keyfreefp) keyfreefp(e_gh1->key);
+ if (valfreefp) valfreefp(e_gh1->val);
- entry_copy(e_gh1, e, entry_size, keycopyfp, valcopyfp);
+ entry_copy(e_gh1, e, entry_size, keycopyfp, valcopyfp);
+ }
}
}
}
@@ -581,7 +591,6 @@ static GHash *ghash_union(
* If \a gh1 is NULL, a new GHash will be created first (avoids modifying \a gh1 in place).
*/
static GHash *ghash_intersection(
- const size_t entry_size,
GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp,
GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
GHash *gh1, GHash *gh2, va_list arg)
@@ -591,7 +600,7 @@ static GHash *ghash_intersection(
BLI_assert(ghn);
if (!gh1) {
- gh1 = ghash_copy(ghn, entry_size, keycopyfp, valcopyfp);
+ gh1 = ghash_copy(ghn, keycopyfp, valcopyfp);
ghn = va_arg(arg, GHash *);
}
@@ -640,7 +649,6 @@ static GHash *ghash_intersection(
* If \a gh1 is NULL, a new GHash will be created first (avoids modifying \a gh1 in place).
*/
static GHash *ghash_difference(
- const size_t entry_size,
GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp,
GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
GHash *gh1, GHash *gh2, va_list arg)
@@ -650,7 +658,7 @@ static GHash *ghash_difference(
BLI_assert(ghn);
if (!gh1) {
- gh1 = ghash_copy(ghn, entry_size, keycopyfp, valcopyfp);
+ gh1 = ghash_copy(ghn, keycopyfp, valcopyfp);
ghn = va_arg(arg, GHash *);
}
@@ -699,7 +707,6 @@ static GHash *ghash_difference(
* If \a gh1 is NULL, a new GHash will be created first (avoids modifying \a gh1 in place).
*/
static GHash *ghash_symmetric_difference(
- const size_t entry_size,
GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp,
GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
GHash *gh1, GHash *gh2, va_list arg)
@@ -714,123 +721,128 @@ static GHash *ghash_symmetric_difference(
BLI_assert(ghn);
if (!gh1) {
- gh1 = ghash_copy(ghn, entry_size, keycopyfp, valcopyfp);
+ gh1 = ghash_copy(ghn, keycopyfp, valcopyfp);
ghn = va_arg(arg, GHash *);
}
- keys = ghash_copy(gh1, entry_size, NULL, NULL);
+ keys = ghash_copy(gh1, NULL, NULL);
rem_keys = ghash_new(gh1->hashfp, gh1->cmpfp, __func__, 64, GSET_ENTRY_SIZE);
- /* First pass: all key found at least once is in keys, all key found at least twice is in rem_keys. */
- for ( ; ghn; ghn = va_arg(arg, GHash *)) {
- BLI_assert(gh1->cmpfp == ghn->cmpfp);
- BLI_assert(gh1->hashfp == ghn->hashfp);
+ {
+ const size_t entry_size = gh1->entry_size;
- for (i = 0; i < ghn->nbuckets; i++) {
- Entry *e;
+ /* First pass: all key found at least once is in keys, all key found at least twice is in rem_keys. */
+ for ( ; ghn; ghn = va_arg(arg, GHash *)) {
+ BLI_assert(gh1->cmpfp == ghn->cmpfp);
+ BLI_assert(gh1->hashfp == ghn->hashfp);
+ BLI_assert(entry_size = ghn->entry_size);
- for (e = ghn->buckets[i]; e; e = e->next) {
- const unsigned int keys_bucket_hash = ghash_bucket_hash(keys, e->hash);
+ for (i = 0; i < ghn->nbuckets; i++) {
+ Entry *e;
- if (ghash_lookup_entry_ex(keys, e->key, e->hash, keys_bucket_hash) != NULL) {
- const unsigned int rem_keys_bucket_hash = ghash_bucket_hash(rem_keys, e->hash);
- Entry *e_new = BLI_mempool_alloc(rem_keys->entrypool);
+ for (e = ghn->buckets[i]; e; e = e->next) {
+ const unsigned int keys_bucket_hash = ghash_bucket_hash(keys, e->hash);
- entry_copy(e_new, e, GSET_ENTRY_SIZE, NULL, NULL);
+ if (ghash_lookup_entry_ex(keys, e->key, e->hash, keys_bucket_hash) != NULL) {
+ const unsigned int rem_keys_bucket_hash = ghash_bucket_hash(rem_keys, e->hash);
+ Entry *e_new = BLI_mempool_alloc(rem_keys->entrypool);
- /* As with copy, this does not preserve order (but this would be even less meaningful here). */
- e_new->next = rem_keys->buckets[rem_keys_bucket_hash];
- rem_keys->buckets[rem_keys_bucket_hash] = e_new;
- ghash_expand_buckets(rem_keys, ++rem_keys->nentries, false, false);
- }
- else {
- Entry *e_new = BLI_mempool_alloc(keys->entrypool);
+ entry_copy(e_new, e, GSET_ENTRY_SIZE, NULL, NULL);
- entry_copy(e_new, e, entry_size, NULL, NULL);
+ /* As with copy, this does not preserve order (but this would be even less meaningful here). */
+ e_new->next = rem_keys->buckets[rem_keys_bucket_hash];
+ rem_keys->buckets[rem_keys_bucket_hash] = e_new;
+ ghash_expand_buckets(rem_keys, ++rem_keys->nentries, false, false);
+ }
+ else {
+ Entry *e_new = BLI_mempool_alloc(keys->entrypool);
- /* As with copy, this does not preserve order (but this would be even less meaningful here). */
- e_new->next = keys->buckets[keys_bucket_hash];
- keys->buckets[keys_bucket_hash] = e_new;
- ghash_expand_buckets(keys, ++keys->nentries, false, false);
+ entry_copy(e_new, e, entry_size, NULL, NULL);
+
+ /* As with copy, this does not preserve order (but this would be even less meaningful here). */
+ e_new->next = keys->buckets[keys_bucket_hash];
+ keys->buckets[keys_bucket_hash] = e_new;
+ ghash_expand_buckets(keys, ++keys->nentries, false, false);
+ }
}
}
}
- }
- /* Now, keys we actually want are (keys - rem_keys) */
- for (i = 0; i < rem_keys->nbuckets; i++) {
- Entry *e;
-
- for (e = rem_keys->buckets[i]; e; e = e->next) {
- Entry *e_prev = NULL, *e_curr;
- const unsigned int keys_bucket_hash = ghash_bucket_hash(keys, e->hash);
- const unsigned int gh1_bucket_hash = ghash_bucket_hash(gh1, e->hash);
+ /* Now, keys we actually want are (keys - rem_keys) */
+ for (i = 0; i < rem_keys->nbuckets; i++) {
+ Entry *e;
- for (e_curr = keys->buckets[keys_bucket_hash]; e_curr; e_prev = e_curr, e_curr = e_curr->next) {
- if (UNLIKELY(e_curr->hash == e->hash)) {
- if (LIKELY(keys->cmpfp(e_curr->key, e->key) == false)) {
- if (e_prev) e_prev->next = e_curr->next;
- else keys->buckets[keys_bucket_hash] = e_curr->next;
+ for (e = rem_keys->buckets[i]; e; e = e->next) {
+ Entry *e_prev = NULL, *e_curr;
+ const unsigned int keys_bucket_hash = ghash_bucket_hash(keys, e->hash);
+ const unsigned int gh1_bucket_hash = ghash_bucket_hash(gh1, e->hash);
- /* We do not care about shrinking keys'
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list