[Bf-blender-cvs] [e7cbfa9] temp-ghash-experiments: GHash: add copy/isdisjoint/isequal/issubset/issuperset, with gtests.
Bastien Montagne
noreply at git.blender.org
Sun Mar 1 21:28:18 CET 2015
Commit: e7cbfa9d405c2c1abbbbfc10ef12e7f3fa926277
Author: Bastien Montagne
Date: Sun Mar 1 21:25:44 2015 +0100
Branches: temp-ghash-experiments
https://developer.blender.org/rBe7cbfa9d405c2c1abbbbfc10ef12e7f3fa926277
GHash: add copy/isdisjoint/isequal/issubset/issuperset, with gtests.
We still need union/intersection/difference/symetric_difference...
===================================================================
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 e36ebd4..3d34ef2 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;
@@ -63,6 +65,8 @@ 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);
@@ -81,6 +85,11 @@ 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);
+
/* *** */
GHashIterator *BLI_ghashIterator_new(GHash *gh) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
@@ -195,6 +204,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 {
@@ -208,6 +218,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);
@@ -219,7 +230,12 @@ 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_ptr_new_ex(const char *info,
const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c
index 590fe74..3cd8c79 100644
--- a/source/blender/blenlib/intern/BLI_ghash.c
+++ b/source/blender/blenlib/intern/BLI_ghash.c
@@ -429,6 +429,41 @@ static void ghash_free_cb(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP va
}
}
}
+
+/**
+ * Copy the GHash.
+ */
+static GHash *ghash_copy(GHash *gh, const unsigned int entry_size, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
+{
+ GHash *gh_new;
+ unsigned int i;
+
+ gh_new = ghash_new(gh->hashfp, gh->cmpfp, __func__, gh->nentries, entry_size);
+
+ for (i = 0; i < gh->nbuckets; i++) {
+ Entry *e;
+
+ for (e = gh->buckets[i]; e; e = e->next) {
+ Entry *e_new = BLI_mempool_alloc(gh_new->entrypool);
+ const unsigned int gh_new_bucket_hash = ghash_bucket_hash(gh_new, e->hash);
+
+ *e_new = *e;
+ if (keycopyfp) e_new->key = keycopyfp(e->key);
+ if (valcopyfp) e_new->val = valcopyfp(e->val);
+
+ /* Warning! This means entries in buckets in new copy will be in reversed order!
+ * This shall not be an issue though, since order should never be assumed in ghash. */
+ /* Note: We cannot use i here, since there is no guaranty that gh and gh_new
+ * have the same number of buckets! */
+ e_new->next = gh_new->buckets[gh_new_bucket_hash];
+ gh_new->buckets[gh_new_bucket_hash] = e_new;
+ }
+ }
+ gh_new->nentries = gh->nentries;
+
+ return gh_new;
+}
+
/** \} */
@@ -462,6 +497,14 @@ GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
}
/**
+ * Copy given GHash. Keys and values are also copied if relevant callback is provided, else pointers remain the same.
+ */
+GHash *BLI_ghash_copy(GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
+{
+ return ghash_copy(gh, sizeof(Entry), keycopyfp, valcopyfp);
+}
+
+/**
* Reverve given ammount of entries (resize \a gh accordingly if needed).
*/
void BLI_ghash_reserve(GHash *gh, const unsigned int nentries_reserve)
@@ -692,6 +735,97 @@ void BLI_ghash_flag_clear(GHash *gh, unsigned int flag)
gh->flag &= ~flag;
}
+/**
+ * Check whether no key from \a gh1 exists in \a gh2.
+ */
+bool BLI_ghash_isdisjoint(GHash *gh1, GHash *gh2)
+{
+ /* Note: For now, take a basic, brute force approach.
+ * If we switch from modulo to masking, we may have ways to optimize this, though. */
+ unsigned int i;
+
+ if (gh1->nentries > gh2->nentries) {
+ SWAP(GHash *, gh1, gh2);
+ }
+
+ for (i = 0; i < gh1->nbuckets; i++) {
+ Entry *e;
+
+ for (e = gh1->buckets[i]; e; e = e->next) {
+ const unsigned int gh2_bucket_hash = ghash_bucket_hash(gh2, e->hash);
+ if (ghash_lookup_entry_ex(gh2, e->key, e->hash, gh2_bucket_hash)) {
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+/**
+ * Check whether \a gh1 and \a gh2 contain exactly the same keys.
+ */
+bool BLI_ghash_isequal(GHash *gh1, GHash *gh2)
+{
+ unsigned int i;
+
+ if (gh1->nentries != gh2->nentries) {
+ return false;
+ }
+
+ for (i = 0; i < gh1->nbuckets; i++) {
+ Entry *e;
+
+ for (e = gh1->buckets[i]; e; e = e->next) {
+ unsigned int gh2_bucket_hash = ghash_bucket_hash(gh2, e->hash);
+ if (!ghash_lookup_entry_ex(gh2, e->key, e->hash, gh2_bucket_hash)) {
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+/**
+ * Check whether \a gh2 keys are a subset of \a gh1 keys.
+ * gh1 >= gh2
+ *
+ * Note: Strict subset is (gh1 >= gh2) && (gh1->nentries != gh2->nentries).
+ */
+bool BLI_ghash_issubset(GHash *gh1, GHash *gh2)
+{
+ unsigned int i;
+
+ if (gh1->nentries < gh2->nentries) {
+ return false;
+ }
+
+ for (i = 0; i < gh2->nbuckets; i++) {
+ Entry *e;
+
+ for (e = gh2->buckets[i]; e; e = e->next) {
+ const unsigned int gh1_bucket_hash = ghash_bucket_hash(gh1, e->hash);
+ if (!ghash_lookup_entry_ex(gh1, e->key, e->hash, gh1_bucket_hash)) {
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+/**
+ * Check whether \a gh2 keys are a superset of \a gh1 keys.
+ * gh1 <= gh2
+ *
+ * Note: Strict superset is (gh1 <= gh2) && (gh1->nentries != gh2->nentries).
+ */
+bool BLI_ghash_issuperset(GHash *gh1, GHash *gh2)
+{
+ return BLI_ghash_issubset(gh2, gh1);
+}
+
/** \} */
@@ -1038,7 +1172,9 @@ GHash *BLI_ghash_pair_new(const char *info)
/* Use ghash API to give 'set' functionality */
/* TODO: typical set functions
- * isdisjoint/issubset/issuperset/union/intersection/difference etc */
+ * union/intersection/difference etc */
+
+#define GSET_ENTRY_SIZE sizeof(Entry) - sizeof(void *)
/** \name GSet Functions
* \{ */
@@ -1047,7 +1183,7 @@ GSet *BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info,
{
GSet *gs = (GSet *)ghash_new(hashfp, cmpfp, info,
nentries_reserve,
- sizeof(Entry) - sizeof(void *));
+ GSET_ENTRY_SIZE);
#ifndef NDEBUG
((GHash *)gs)->flag |= GHASH_FLAG_IS_SET;
#endif
@@ -1059,6 +1195,14 @@ GSet *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info)
return BLI_gset_new_ex(hashfp, cmpfp, info, 0);
}
+/**
+ * Copy given GSet. Keys are also copied if callback is provided, else pointers remain the same.
+ */
+GSet *BLI_gset_copy(GSet *gs, GHashKeyCopyFP keycopyfp)
+{
+ return (GSet *)ghash_copy((GHash *)gs, GSET_ENTRY_SIZE, keycopyfp, NULL);
+}
+
int BLI_gset_size(GSet *gs)
{
return (int)((GHash *)gs)->nentries;
@@ -1155,6 +1299,26 @@ void BLI_gset_flag_clear(GSet *gs, unsigned int flag)
((GHash *)gs)->flag &= ~flag;
}
+bool BLI_gset_isdisjoint(GSet *gs1, GSet *gs2)
+{
+ return BLI_ghash_isdisjoint((GHash *)gs1, (GHash *)gs2);
+}
+
+bool BLI_gset_isequal(GSet *gs1, GSet *gs2)
+{
+ return BLI_ghash_isequal((GHash *)gs1, (GHash *)gs2);
+}
+
+bool BLI_gset_issubset(GSet *gs1, GSet *gs2)
+{
+ return BLI_ghash_issubset((GHash *)gs1, (GHash *)gs2);
+}
+
+bool BLI_gset_issuperset(GSet *gs1, GSet *gs2)
+{
+ return BLI_ghash_issubset((GHash *)gs2, (GHash *)gs1);
+}
+
/** \} */
More information about the Bf-blender-cvs
mailing list