From 16f858968f2e066069ceaf4aea3deebf22a188d7 Mon Sep 17 00:00:00 2001 From: Karol Herbst Date: Fri, 15 May 2020 11:11:13 +0200 Subject: [PATCH 1/1] util/set: add _mesa_set_intersects v2 (Jason Ekstrand): add asserts and iterate over smaller set Signed-off-by: Karol Herbst Reviewed-by: Jason Ekstrand Part-of: --- 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 -- 2.30.2