Mesa (master): util/set: add _mesa_set_intersects

[GitLab Mirror]

Module: Mesa
Branch: master
Commit: 16f858968f2e066069ceaf4aea3deebf22a188d7
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=16f858968f2e066069ceaf4aea3deebf22a188d7

Author: Karol Herbst <kherbst at redhat.com>
Date:   Fri May 15 11:11:13 2020 +0200

util/set: add _mesa_set_intersects

v2 (Jason Ekstrand): add asserts and iterate over smaller set

Signed-off-by: Karol Herbst <kherbst at redhat.com>
Reviewed-by: Jason Ekstrand <jason at jlekstrand.net>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/2401>

---

 src/util/set.c | 20 ++++++++++++++++++++
 src/util/set.h |  3 +++
 2 files changed, 23 insertions(+)

diff --git a/src/util/set.c b/src/util/set.c
index ffe0fe808ea..a9012b4e6d4 100644
--- a/src/util/set.c
+++ b/src/util/set.c
@@ -570,3 +570,23 @@ _mesa_pointer_set_create(void *mem_ctx)
    return _mesa_set_create(mem_ctx, _mesa_hash_pointer,
                            _mesa_key_pointer_equal);
 }
+
+bool
+_mesa_set_intersects(struct set *a, struct set *b)
+{
+   assert(a->key_hash_function == b->key_hash_function);
+   assert(a->key_equals_function == b->key_equals_function);
+
+   /* iterate over the set with less entries */
+   if (b->entries < a->entries) {
+      struct set *tmp = a;
+      a = b;
+      b = tmp;
+   }
+
+   set_foreach(a, entry) {
+      if (_mesa_set_search_pre_hashed(b, entry->hash, entry->key))
+         return true;
+   }
+   return false;
+}
diff --git a/src/util/set.h b/src/util/set.h
index 55857aca7ab..2e0a2d66f85 100644
--- a/src/util/set.h
+++ b/src/util/set.h
@@ -110,6 +110,9 @@ _mesa_set_random_entry(struct set *set,
 struct set *
 _mesa_pointer_set_create(void *mem_ctx);
 
+bool
+_mesa_set_intersects(struct set *a, struct set *b);
+
 /**
  * This foreach function is safe against deletion, but not against
  * insertion (which may rehash the set, making entry a dangling