[Bf-blender-cvs] [23b42a5] temp-ghash-setops: Squashed commit of temp-ghash-experiments, minus the 'hash storage' part.
Bastien Montagne
noreply at git.blender.org
Fri Mar 20 12:07:17 CET 2015
Commit: 23b42a5e69b0882ff7a26ce589891af84ca9bc3e
Author: Bastien Montagne
Date: Fri Mar 13 12:15:12 2015 +0100
Branches: temp-ghash-setops
https://developer.blender.org/rB23b42a5e69b0882ff7a26ce589891af84ca9bc3e
Squashed commit of temp-ghash-experiments, minus the 'hash storage' part.
===================================================================
M source/blender/blenlib/BLI_ghash.h
M source/blender/blenlib/intern/BLI_ghash.c
M tests/gtests/blenlib/BLI_ghash_test.cc
===================================================================
diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h
index 16d18ef..49af452 100644
--- a/source/blender/blenlib/BLI_ghash.h
+++ b/source/blender/blenlib/BLI_ghash.h
@@ -89,6 +89,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;
@@ -231,6 +254,16 @@ void BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp,
const unsigned int nentries_reserve);
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;
GSet *BLI_gset_ptr_new(const char *info);
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c
index a2233c3..2b3ced5 100644
--- a/source/blender/blenlib/intern/BLI_ghash.c
+++ b/source/blender/blenlib/intern/BLI_ghash.c
@@ -598,6 +598,321 @@ static GHash *ghash_copy(GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP val
return gh_new;
}
+/**
+ * Merge \a gh2 into \a gh1 (keeping entries already in \a gh1 unchanged), and then each subsequent given GHash.
+ * If \a gh1 is NULL, a new GHash will be created first (avoids modifying \a gh1 in place).
+ * If \a reverse is True, entries present in latest GHash will override those in former GHash.
+ */
+static GHash *ghash_union(
+ const bool reverse,
+ GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp,
+ GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
+ GHash *gh1, GHash *gh2, va_list arg)
+{
+ GHash *ghn = gh2;
+
+ BLI_assert(ghn);
+
+ if (!gh1) {
+ gh1 = ghash_copy(ghn, keycopyfp, valcopyfp);
+ ghn = va_arg(arg, GHash *);
+ }
+
+ for ( ; ghn; ghn = va_arg(arg, GHash *)) {
+ unsigned int i;
+
+ BLI_assert(gh1->cmpfp == ghn->cmpfp);
+ BLI_assert(gh1->hashfp == ghn->hashfp);
+ BLI_assert(gh1->is_gset == ghn->is_gset);
+
+ for (i = 0; i < ghn->nbuckets; i++) {
+ Entry *e;
+
+ for (e = ghn->buckets[i]; e; e = e->next) {
+ Entry *e_gh1;
+ const unsigned int hash = ghash_entryhash(gh1, e);
+ const unsigned int gh1_bucket_hash = ghash_bucket_hash(gh1, hash);
+
+ if ((e_gh1 = ghash_lookup_entry_ex(gh1, e->key, hash, gh1_bucket_hash)) == NULL) {
+ Entry *e_new = BLI_mempool_alloc(gh1->entrypool);
+
+ entry_copy(gh1, e_new, ghn, e, hash, 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(((GHashEntry *)e_gh1)->val);
+
+ entry_copy(gh1, e_gh1, ghn, e, hash, keycopyfp, valcopyfp);
+ }
+ }
+ }
+ }
+
+ return gh1;
+}
+
+/**
+ * Remove all entries in \a gh1 which keys are not present in \a gh2 and all subsequent given GHash.
+ * If \a gh1 is NULL, a new GHash will be created first (avoids modifying \a gh1 in place).
+ */
+static GHash *ghash_intersection(
+ GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp,
+ GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
+ GHash *gh1, GHash *gh2, va_list arg)
+{
+ GHash *ghn = gh2;
+
+ BLI_assert(ghn);
+
+ if (!gh1) {
+ gh1 = ghash_copy(ghn, keycopyfp, valcopyfp);
+ ghn = va_arg(arg, GHash *);
+ }
+
+ BLI_assert(!valfreefp || !gh1->is_gset);
+
+ for ( ; ghn; ghn = va_arg(arg, GHash *)) {
+ unsigned int new_gh1_nentries = gh1->nentries;
+ unsigned int i;
+
+ BLI_assert(gh1->cmpfp == ghn->cmpfp);
+ BLI_assert(gh1->hashfp == ghn->hashfp);
+
+ for (i = 0; i < gh1->nbuckets; i++) {
+ Entry *e, *e_prev = NULL, *e_next;
+
+ for (e = gh1->buckets[i]; e; e = e_next) {
+ const unsigned int hash = ghash_entryhash(gh1, e);
+ const unsigned int ghn_bucket_hash = ghash_bucket_hash(ghn, hash);
+
+ e_next = e->next;
+
+ if (ghash_lookup_entry_ex(ghn, e->key, hash, ghn_bucket_hash) == NULL) {
+ if (keyfreefp) keyfreefp(e->key);
+ if (valfreefp) valfreefp(((GHashEntry *)e)->val);
+
+ if (e_prev) e_prev->next = e_next;
+ else gh1->buckets[i] = e_next;
+
+ /* We cannot resize gh1 while we are looping on it!!! */
+ new_gh1_nentries--;
+ BLI_mempool_free(gh1->entrypool, e);
+ }
+ else {
+ e_prev = e;
+ }
+ }
+ }
+
+ gh1->nentries = new_gh1_nentries;
+ /* We force shrinking here (if needed). */
+ ghash_expand_buckets(gh1, gh1->nentries, false, true);
+ }
+
+ return gh1;
+}
+
+/**
+ * Remove all entries in \a gh1 which keys are present in \a gh2 or any subsequent given GHash.
+ * If \a gh1 is NULL, a new GHash will be created first (avoids modifying \a gh1 in place).
+ */
+static GHash *ghash_difference(
+ GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp,
+ GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
+ GHash *gh1, GHash *gh2, va_list arg)
+{
+ GHash *ghn = gh2;
+
+ BLI_assert(ghn);
+
+ if (!gh1) {
+ gh1 = ghash_copy(ghn, keycopyfp, valcopyfp);
+ ghn = va_arg(arg, GHash *);
+ }
+
+ BLI_assert(!valfreefp || !gh1->is_gset);
+
+ for ( ; ghn; ghn = va_arg(arg, GHash *)) {
+ unsigned int new_gh1_nentries = gh1->nentries;
+ unsigned int i;
+
+ BLI_assert(gh1->cmpfp == ghn->cmpfp);
+ BLI_assert(gh1->hashfp == ghn->hashfp);
+
+ for (i = 0; i < gh1->nbuckets; i++) {
+ Entry *e, *e_prev = NULL, *e_next;
+
+ for (e = gh1->buckets[i]; e; e = e_next) {
+ const unsigned int hash = ghash_entryhash(gh1, e);
+ const unsigned int ghn_bucket_hash = ghash_bucket_hash(ghn, hash);
+
+ e_next = e->next;
+
+ if (ghash_lookup_entry_ex(ghn, e->key, hash, ghn_bucket_hash) != NULL) {
+ if (keyfreefp) keyfreefp(e->key);
+ if (valfreefp) valfreefp(((GHashEntry *)e)->val);
+
+ if (e_prev) e_prev->next = e_next;
+ else gh1->buckets[i] = e_next;
+
+ /* We cannot resize gh1 while we are looping on it!!! */
+ new_gh1_nentries--;
+ BLI_mempool_free(gh1->entrypool, e);
+ }
+ else {
+ e_prev = e;
+ }
+ }
+ }
+
+ gh1->nentries = new_gh1_nentries;
+ /* We force shrinking here (if needed). */
+ ghash_expand_buckets(gh1, gh1->nentries, false, true);
+ }
+
+ return gh1;
+}
+
+/**
+ * Set \a gh1 to only contain entries which keys are present in one and only one of all given ghash.
+ * If \a gh1 is NULL, a new GHash will be created first (avoids modifying \a gh1 in place).
+ */
+static GHash *ghash_symmetric_difference(
+ GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp,
+ GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
+ GHash *gh1, GHash *gh2, va_list arg)
+{
+ GHash *ghn = gh2;
+ unsigned int i;
+
+ /* Temp storage, we never copy key/values here, just borrow them from real ghash. */
+ /* Warning! rem_keys is used as gset (i.e. no val memory reserved). */
+ GHash *keys, *rem_keys;
+
+ BLI_assert(ghn);
+
+ if (!gh1) {
+ gh1 = ghash_copy(ghn, keycopyfp, valcopyfp);
+ ghn = va_arg(arg, GHash *);
+ }
+
+ BLI_assert(!valfreefp || !gh1->is_gset);
+
+ keys = ghash_copy(gh1, NULL, NULL);
+ rem_keys = ghash_new(gh1->hashfp, gh1->cmpfp, __func__, 64, true);
+
+ /* 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(gh1->is_gset == ghn->is_gset);
+
+ for (i = 0; i < ghn->nbuckets; i++) {
+ Entry *e;
+
+ for (e = ghn->buckets[i]; e; e = e->next) {
+ const unsigned int hash = ghash_entryhash(ghn, e);
+ const unsigned int keys_bucket_hash = ghash_bucket_hash(keys, hash);
+
+ if (ghash_lookup_entry_ex(keys, e->key, hash, keys_bucket_hash) != NULL) {
+ const unsigned int rem_keys_bucket_hash = ghash_bucket_hash(rem_keys, hash);
+ Entry *e_new = BLI_mempool_alloc(rem_keys->entrypool);
+
+ entry_copy(rem_keys, e_new, ghn, e, hash, 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 {
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list