12:17 a.m.
l_uintset_intersect computes the intersection of two sets
of an equal base.
---
ell/uintset.c | 37 +++++++++++++++++++++++++++++++++++++
ell/uintset.h | 3 +++
2 files changed, 40 insertions(+)
diff --git a/ell/uintset.c b/ell/uintset.c
index 3f20098..60a9822 100644
--- a/ell/uintset.c
+++ b/ell/uintset.c
@@ -469,3 +469,40 @@ LIB_EXPORT void l_uintset_foreach(struct l_uintset *set,
bit = find_next_bit(set->bits, set->size, bit + 1))
function(set->min + bit, user_data);
}
+
+/**
+ * l_uintset_intersect:
+ * @set_a: The set of numbers
+ * @set_b: The set of numbers
+ *
+ * Intersects the two sets of numbers of an equal base, e.g.:
+ * l_uintset_get_min(set_a) must be equal to l_uintset_get_min(set_b) and
+ * l_uintset_get_max(set_a) must be equal to l_uintset_get_max(set_b)
+ *
+ * Returns: A newly allocated l_uintset object containing the intersection of
+ * @set_a and @set_b. If the bases are not equal returns NULL. If either @set_a
+ * or @set_b is NULL returns NULL.
+ **/
+LIB_EXPORT struct l_uintset *l_uintset_intersect(const struct l_uintset *set_a,
+ const struct l_uintset *set_b)
+{
+ struct l_uintset *intersection;
+ uint32_t offset;
+ uint32_t offset_max;
+
+ if (unlikely(!set_a || !set_b))
+ return NULL;
+
+ if (unlikely(set_a->min != set_b->min || set_a->max != set_b->max))
+ return NULL;
+
+ intersection = l_uintset_new_from_range(set_a->min, set_a->max);
+
+ offset_max = (set_a->size + BITS_PER_LONG - 1) / BITS_PER_LONG;
+
+ for (offset = 0; offset < offset_max; offset++)
+ intersection->bits[offset] =
+ set_a->bits[offset] & set_b->bits[offset];
+
+ return intersection;
+}
diff --git a/ell/uintset.h b/ell/uintset.h
index dd03cd7..c05a21b 100644
--- a/ell/uintset.h
+++ b/ell/uintset.h
@@ -55,6 +55,9 @@ uint32_t l_uintset_find_unused(struct l_uintset *set, uint32_t start);
void l_uintset_foreach(struct l_uintset *set,
l_uintset_foreach_func_t function, void *user_data);
+struct l_uintset *l_uintset_intersect(const struct l_uintset *set_a,
+ const struct l_uintset *set_b);
+
#ifdef __cplusplus
}
#endif
--
2.13.6
12:17 a.m.
New subject: [PATCH 2/2] unit: Add l_uintset_intersect tests
---
unit/test-uintset.c | 91 +++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 91 insertions(+)
diff --git a/unit/test-uintset.c b/unit/test-uintset.c
index 4488cd9..9bd455c 100644
--- a/unit/test-uintset.c
+++ b/unit/test-uintset.c
@@ -262,6 +262,91 @@ static void test_uintset_foreach(const void *data)
l_uintset_free(check);
}
+static void test_uintset_intersect_1(const void *data)
+{
+ struct l_uintset *set_a;
+ struct l_uintset *set_b;
+
+ assert(!l_uintset_intersect(NULL, NULL));
+
+ set_a = l_uintset_new_from_range(0, 5);
+ assert(!l_uintset_intersect(NULL, set_a));
+ assert(!l_uintset_intersect(set_a, NULL));
+
+ set_b = l_uintset_new_from_range(4, 10);
+ assert(!l_uintset_intersect(set_a, set_b));
+
+ l_uintset_free(set_a);
+ l_uintset_free(set_b);
+}
+
+struct uintset_data {
+ uint32_t min;
+ uint32_t max;
+ uint32_t *vals;
+ uint32_t size;
+};
+
+struct uintset_intersect_data {
+ const struct uintset_data set_a;
+ const struct uintset_data set_b;
+ const struct uintset_data set_r;
+};
+
+uint32_t vals1[] = { 1, 2, 3 };
+uint32_t vals2[] = { 3, 4};
+uint32_t vals3[] = { 3 };
+
+static const struct uintset_intersect_data intersect_data_1 = {
+ .set_a = { 0, 4, vals1, L_ARRAY_SIZE(vals1) },
+ .set_b = { 0, 4, vals2, L_ARRAY_SIZE(vals2) },
+ .set_r = { 0, 4, vals3, L_ARRAY_SIZE(vals3) },
+};
+
+uint32_t vals4[] = { 0, 1, 64, 127 };
+uint32_t vals5[] = { 1, 25, 64, 66, 127, 135 };
+uint32_t vals6[] = { 1, 64, 127 };
+
+static const struct uintset_intersect_data intersect_data_2 = {
+ .set_a = { 0, 191, vals4, L_ARRAY_SIZE(vals4) },
+ .set_b = { 0, 191, vals5, L_ARRAY_SIZE(vals5) },
+ .set_r = { 0, 191, vals6, L_ARRAY_SIZE(vals6) },
+};
+
+static void test_uintset_intersect_2(const void *user_data)
+{
+ const struct uintset_intersect_data *data = user_data;
+ struct l_uintset *set_a;
+ struct l_uintset *set_b;
+ struct l_uintset *set_r;
+ size_t i;
+
+ set_a = l_uintset_new_from_range(data->set_a.min, data->set_a.max);
+
+ for (i = 0; i < data->set_a.size; i++)
+ l_uintset_put(set_a, data->set_a.vals[i]);
+
+ set_b = l_uintset_new_from_range(data->set_b.min, data->set_b.max);
+
+ for (i = 0; i < data->set_b.size; i++)
+ l_uintset_put(set_b, data->set_b.vals[i]);
+
+ set_r = l_uintset_intersect(set_a, set_b);
+
+ assert(set_r);
+
+ for (i = 0; i < data->set_r.size; i++) {
+ assert(l_uintset_contains(set_r, data->set_r.vals[i]));
+ assert(l_uintset_take(set_r, data->set_r.vals[i]));
+ }
+
+ assert(l_uintset_find_max(set_r) == l_uintset_get_max(set_r) + 1);
+
+ l_uintset_free(set_a);
+ l_uintset_free(set_b);
+ l_uintset_free(set_r);
+}
+
int main(int argc, char *argv[])
{
l_test_init(&argc, &argv);
@@ -273,6 +358,12 @@ int main(int argc, char *argv[])
l_test_add("l_uintset for each tests", test_uintset_foreach, NULL);
l_test_add("l_uintset find unused tests", test_uintset_find_unused,
NULL);
+ l_test_add("l_uintset intersect sanity check", test_uintset_intersect_1,
+ NULL);
+ l_test_add("l_uintset intersect test 1", test_uintset_intersect_2,
+ &intersect_data_1);
+ l_test_add("l_uintset intersect test2", test_uintset_intersect_2,
+ &intersect_data_2);
return l_test_run();
}
--
2.13.6
4:13 p.m.
New subject: [PATCH 2/2] unit: Add l_uintset_intersect tests
Hi Tim,
On 03/06/2019 06:17 PM, Tim Kourt wrote:
---
unit/test-uintset.c | 91 +++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 91 insertions(+)
diff --git a/unit/test-uintset.c b/unit/test-uintset.c
index 4488cd9..9bd455c 100644
--- a/unit/test-uintset.c
+++ b/unit/test-uintset.c
@@ -262,6 +262,91 @@ static void test_uintset_foreach(const void *data)
l_uintset_free(check);
}
+static void test_uintset_intersect_1(const void *data)
Can this be a bit more descriptive, e.g. intersect_invalid,
intersect_sanity, etc
+{
+ struct l_uintset *set_a;
+ struct l_uintset *set_b;
+
+ assert(!l_uintset_intersect(NULL, NULL));
+
+ set_a = l_uintset_new_from_range(0, 5);
+ assert(!l_uintset_intersect(NULL, set_a));
+ assert(!l_uintset_intersect(set_a, NULL));
+
+ set_b = l_uintset_new_from_range(4, 10);
+ assert(!l_uintset_intersect(set_a, set_b));
+
+ l_uintset_free(set_a);
+ l_uintset_free(set_b);
+}
+
+struct uintset_data {
+ uint32_t min;
+ uint32_t max;
+ uint32_t *vals;
+ uint32_t size;
+};
+
+struct uintset_intersect_data {
+ const struct uintset_data set_a;
+ const struct uintset_data set_b;
+ const struct uintset_data set_r;
+};
+
+uint32_t vals1[] = { 1, 2, 3 };
+uint32_t vals2[] = { 3, 4};
+uint32_t vals3[] = { 3 };
These should be static const
+
+static const struct uintset_intersect_data intersect_data_1 = {
+ .set_a = { 0, 4, vals1, L_ARRAY_SIZE(vals1) },
+ .set_b = { 0, 4, vals2, L_ARRAY_SIZE(vals2) },
+ .set_r = { 0, 4, vals3, L_ARRAY_SIZE(vals3) },
+};
+
+uint32_t vals4[] = { 0, 1, 64, 127 };
+uint32_t vals5[] = { 1, 25, 64, 66, 127, 135 };
+uint32_t vals6[] = { 1, 64, 127 };
+
And these
+static const struct uintset_intersect_data intersect_data_2 = {
+ .set_a = { 0, 191, vals4, L_ARRAY_SIZE(vals4) },
+ .set_b = { 0, 191, vals5, L_ARRAY_SIZE(vals5) },
+ .set_r = { 0, 191, vals6, L_ARRAY_SIZE(vals6) },
+};
+
+static void test_uintset_intersect_2(const void *user_data)
+{
+ const struct uintset_intersect_data *data = user_data;
+ struct l_uintset *set_a;
+ struct l_uintset *set_b;
+ struct l_uintset *set_r;
+ size_t i;
+
+ set_a = l_uintset_new_from_range(data->set_a.min, data->set_a.max);
+
+ for (i = 0; i < data->set_a.size; i++)
+ l_uintset_put(set_a, data->set_a.vals[i]);
+
+ set_b = l_uintset_new_from_range(data->set_b.min, data->set_b.max);
+
+ for (i = 0; i < data->set_b.size; i++)
+ l_uintset_put(set_b, data->set_b.vals[i]);
+
+ set_r = l_uintset_intersect(set_a, set_b);
+
+ assert(set_r);
+
+ for (i = 0; i < data->set_r.size; i++) {
+ assert(l_uintset_contains(set_r, data->set_r.vals[i]));
+ assert(l_uintset_take(set_r, data->set_r.vals[i]));
+ }
+
+ assert(l_uintset_find_max(set_r) == l_uintset_get_max(set_r) + 1);
+
+ l_uintset_free(set_a);
+ l_uintset_free(set_b);
+ l_uintset_free(set_r);
+}
+
int main(int argc, char *argv[])
{
l_test_init(&argc, &argv);
@@ -273,6 +358,12 @@ int main(int argc, char *argv[])
l_test_add("l_uintset for each tests", test_uintset_foreach, NULL);
l_test_add("l_uintset find unused tests", test_uintset_find_unused,
NULL);
+ l_test_add("l_uintset intersect sanity check", test_uintset_intersect_1,
+ NULL);
+ l_test_add("l_uintset intersect test 1", test_uintset_intersect_2,
+ &intersect_data_1);
+ l_test_add("l_uintset intersect test2", test_uintset_intersect_2,
+ &intersect_data_2);
Nitpick, but you have 'test 1' and then 'test2'. Be consistent :)
return l_test_run();
}
Regards,
-Denis
4:11 p.m.
On 03/06/2019 06:17 PM, Tim Kourt wrote:
l_uintset_intersect computes the intersection of two sets
of an equal base.
---
ell/uintset.c | 37 +++++++++++++++++++++++++++++++++++++
ell/uintset.h | 3 +++
2 files changed, 40 insertions(+)
Applied. But note that since you're adding a new public API, you should
also add an entry to ell/ell.sym. This is a necessary manual step at
the moment until Marcel fixes the build system to do this properly.
Anyhow, I fixed this for you in a follow-on commit.
Regards,
-Denis
1260
days inactive
1260
days old
3 comments
2 participants
participants (2)
-
Denis Kenzior -
Tim Kourt