[PATCH 1/2] uintset: Add l_uintset_intersect

[PATCH 1/2] uintset: Add l_uintset_intersect

[Tim Kourt]

[-- Attachment #1: Type: text/plain, Size: 2167 bytes --]

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

[PATCH 2/2] unit: Add l_uintset_intersect tests

[Tim Kourt]

[-- Attachment #1: Type: text/plain, Size: 3332 bytes --]

---
 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

Re: [PATCH 1/2] uintset: Add l_uintset_intersect

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 559 bytes --]

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

Re: [PATCH 2/2] unit: Add l_uintset_intersect tests

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 3844 bytes --]

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

[PATCH 2/2] unit: Add l_uintset_intersect tests

[Tim Kourt]

[-- Attachment #1: Type: text/plain, Size: 4291 bytes --]

---
 unit/test-uintset.c | 115 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 115 insertions(+)

diff --git a/unit/test-uintset.c b/unit/test-uintset.c
index 42d9698..277cf6a 100644
--- a/unit/test-uintset.c
+++ b/unit/test-uintset.c
@@ -167,6 +167,111 @@ static void test_uintset_find_unused(const void *data)
 	l_uintset_free(set);
 }
 
+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(6, 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, 3, vals1, L_ARRAY_SIZE(vals1) },
+	.set_b = { 3, 5, vals2, L_ARRAY_SIZE(vals2) },
+	.set_r = { 3, 3, vals3, L_ARRAY_SIZE(vals3) },
+};
+
+uint32_t vals4[] = { 0, 1, 65, 129 };
+uint32_t vals5[] = { 1, 25, 65, 66, 129, 135 };
+uint32_t vals6[] = { 1, 65, 129 };
+
+static const struct uintset_intersect_data intersect_data_2 = {
+	.set_a = { 0, 129, vals4, L_ARRAY_SIZE(vals4) },
+	.set_b = { 1, 135, vals5, L_ARRAY_SIZE(vals5) },
+	.set_r = { 1, 129, vals6, L_ARRAY_SIZE(vals6) },
+};
+
+uint32_t vals7[] = { 0, 191 };
+uint32_t vals8[] = { 0, 191 };
+uint32_t vals9[] = { 0, 191 };
+
+static const struct uintset_intersect_data intersect_data_3 = {
+	.set_a = { 0, 192, vals7, L_ARRAY_SIZE(vals7) },
+	.set_b = { 0, 192, vals8, L_ARRAY_SIZE(vals8) },
+	.set_r = { 0, 192, vals9, L_ARRAY_SIZE(vals9) },
+};
+
+uint32_t vals10[] = { 63 };
+uint32_t vals11[] = { 63 };
+uint32_t vals12[] = { 63 };
+
+static const struct uintset_intersect_data intersect_data_4 = {
+	.set_a = { 0, 127, vals10, L_ARRAY_SIZE(vals10) },
+	.set_b = { 0, 127, vals11, L_ARRAY_SIZE(vals11) },
+	.set_r = { 0, 127, vals12, L_ARRAY_SIZE(vals12) },
+};
+
+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);
@@ -175,6 +280,16 @@ int main(int argc, char *argv[])
 	l_test_add("l_uintset sanity check #2", test_uintset_2, NULL);
 	l_test_add("l_uintset sanity check #3", test_uintset_3, NULL);
 	l_test_add("l_uintset sanity check #4", test_uintset_4, NULL);
+	l_test_add("l_uintset intersect sanity check", test_uintset_intersect_1,
+									NULL);
+	l_test_add("l_uintset intersect test1", test_uintset_intersect_2,
+							&intersect_data_1);
+	l_test_add("l_uintset intersect test2", test_uintset_intersect_2,
+							&intersect_data_2);
+	l_test_add("l_uintset intersect test3", test_uintset_intersect_2,
+							&intersect_data_3);
+	l_test_add("l_uintset intersect test4", test_uintset_intersect_2,
+							&intersect_data_4);
 	l_test_add("l_uintset find unused tests", test_uintset_find_unused,
 							NULL);
 
-- 
2.13.6