[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