diff options
author | Lennart Poettering <lennart@poettering.net> | 2020-11-18 13:48:02 +0100 |
---|---|---|
committer | Lennart Poettering <lennart@poettering.net> | 2021-02-18 16:38:27 +0100 |
commit | e4304fb8d46328b2587e3f0b8b538aa66b45a22c (patch) | |
tree | a4dbf317fa9462a419a0075088c5a7715fc328d0 | |
parent | 95aa3937da91ba6bb30fab33740cc5a53484780c (diff) | |
download | systemd-e4304fb8d46328b2587e3f0b8b538aa66b45a22c.tar.gz |
basic: add set_equal() helper
-rw-r--r-- | src/basic/hashmap.c | 32 | ||||
-rw-r--r-- | src/basic/set.h | 2 | ||||
-rw-r--r-- | src/test/test-set.c | 73 |
3 files changed, 107 insertions, 0 deletions
diff --git a/src/basic/hashmap.c b/src/basic/hashmap.c index c118289b99..e354c67adc 100644 --- a/src/basic/hashmap.c +++ b/src/basic/hashmap.c @@ -2036,3 +2036,35 @@ int set_strjoin(Set *s, const char *separator, bool wrap_with_separator, char ** *ret = TAKE_PTR(str); return 0; } + +bool set_equal(Set *a, Set *b) { + void *p; + + /* Checks whether each entry of 'a' is also in 'b' and vice versa, i.e. the two sets contain the same + * entries */ + + if (a == b) + return true; + + if (set_isempty(a) && set_isempty(b)) + return true; + + if (set_size(a) != set_size(b)) /* Cheap check that hopefully catches a lot of inequality cases + * already */ + return false; + + SET_FOREACH(p, a) + if (!set_contains(b, p)) + return false; + + /* If we have the same hashops, then we don't need to check things backwards given we compared the + * size and that all of a is in b. */ + if (a->b.hash_ops == b->b.hash_ops) + return true; + + SET_FOREACH(p, b) + if (!set_contains(a, p)) + return false; + + return true; +} diff --git a/src/basic/set.h b/src/basic/set.h index 57ff713039..52b6f4984c 100644 --- a/src/basic/set.h +++ b/src/basic/set.h @@ -152,3 +152,5 @@ DEFINE_TRIVIAL_CLEANUP_FUNC(Set*, set_free_free); #define _cleanup_set_free_free_ _cleanup_(set_free_freep) int set_strjoin(Set *s, const char *separator, bool wrap_with_separator, char **ret); + +bool set_equal(Set *a, Set *b); diff --git a/src/test/test-set.c b/src/test/test-set.c index b4d07b2078..f89c968f21 100644 --- a/src/test/test-set.c +++ b/src/test/test-set.c @@ -1,5 +1,6 @@ /* SPDX-License-Identifier: LGPL-2.1-or-later */ +#include "random-util.h" #include "set.h" #include "strv.h" @@ -227,6 +228,77 @@ static void test_set_strjoin(void) { assert_se(STR_IN_SET(joined, "xxxaaaxxxbbbxxx", "xxxbbbxxxaaaxxx")); } +static void test_set_equal(void) { + _cleanup_set_free_ Set *a = NULL, *b = NULL; + void *p; + int r; + + assert_se(a = set_new(NULL)); + assert_se(b = set_new(NULL)); + + assert_se(set_equal(a, a)); + assert_se(set_equal(b, b)); + assert_se(set_equal(a, b)); + assert_se(set_equal(b, a)); + assert_se(set_equal(NULL, a)); + assert_se(set_equal(NULL, b)); + assert_se(set_equal(a, NULL)); + assert_se(set_equal(b, NULL)); + assert_se(set_equal(NULL, NULL)); + + for (unsigned i = 0; i < 333; i++) { + p = INT32_TO_PTR(1 + (random_u32() & 0xFFFU)); + + r = set_put(a, p); + assert_se(r >= 0 || r == -EEXIST); + } + + assert_se(set_put(a, INT32_TO_PTR(0x1000U)) >= 0); + + assert_se(set_size(a) >= 2); + assert_se(set_size(a) <= 334); + + assert_se(!set_equal(a, b)); + assert_se(!set_equal(b, a)); + assert_se(!set_equal(a, NULL)); + + SET_FOREACH(p, a) + assert_se(set_put(b, p) >= 0); + + assert_se(set_equal(a, b)); + assert_se(set_equal(b, a)); + + assert_se(set_remove(a, INT32_TO_PTR(0x1000U)) == INT32_TO_PTR(0x1000U)); + + assert_se(!set_equal(a, b)); + assert_se(!set_equal(b, a)); + + assert_se(set_remove(b, INT32_TO_PTR(0x1000U)) == INT32_TO_PTR(0x1000U)); + + assert_se(set_equal(a, b)); + assert_se(set_equal(b, a)); + + assert_se(set_put(b, INT32_TO_PTR(0x1001U)) >= 0); + + assert_se(!set_equal(a, b)); + assert_se(!set_equal(b, a)); + + assert_se(set_put(a, INT32_TO_PTR(0x1001U)) >= 0); + + assert_se(set_equal(a, b)); + assert_se(set_equal(b, a)); + + set_clear(a); + + assert_se(!set_equal(a, b)); + assert_se(!set_equal(b, a)); + + set_clear(b); + + assert_se(set_equal(a, b)); + assert_se(set_equal(b, a)); +} + int main(int argc, const char *argv[]) { test_set_steal_first(); test_set_free_with_destructor(); @@ -238,6 +310,7 @@ int main(int argc, const char *argv[]) { test_set_ensure_put(); test_set_ensure_consume(); test_set_strjoin(); + test_set_equal(); return 0; } |