[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

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

[Denis Kenzior]

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

Hi Tim,

On 03/05/2019 02:35 PM, Tim Kourt wrote:
> l_uintset_intersect computes the intersection of two sets.
> In addition, it introduces find_next_bit(…) that is used to
> efficiently loop through the set bits in the set and may have
> multiple implication in the future.

implications or applications?  If it is the first, that sounds ominous...

> ---
>   ell/uintset.c | 96 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>   ell/uintset.h |  3 ++
>   2 files changed, 99 insertions(+)
> 

<snip>

> +
> +/**
> + * l_uintset_intersect:
> + * @set_a: The set of numbers
> + * @set_b: The set of numbers
> + *
> + * Returns: A newly allocated l_uintset object containing intersection of
> + * @set_a and @set_b. If @set_a and @set_b cannot be intersected 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 min;
> +	uint32_t max;
> +	unsigned int bit_a;
> +	unsigned int bit_b;
> +
> +	if (unlikely(!set_a) || unlikely(!set_b))
> +		return NULL;
> +
> +	if (set_a->max < set_b->min || set_b->max < set_a->min)
> +		return NULL;

So honestly I would implement a fast version which works for sets where 
min and max are the same.  This is really what you want anyway for the 
scan_freq_set stuff, right?  That should be a very simple bitwise and 
operation...

I'm not completely sure of the utility of this more generalized 
intersect operation that you have implemented here.  Do you foresee a 
need for something like this?

Regards,
-Denis

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

[Andrew Zaborowski]

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

Hi Tim,

On Tue, 5 Mar 2019 at 21:35, Tim Kourt <tim.a.kourt@linux.intel.com> wrote:
> l_uintset_intersect computes the intersection of two sets.
> In addition, it introduces find_next_bit(…) that is used to
> efficiently loop through the set bits in the set and may have
> multiple implication in the future.
> ---
>  ell/uintset.c | 96 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  ell/uintset.h |  3 ++
>  2 files changed, 99 insertions(+)
>
> diff --git a/ell/uintset.c b/ell/uintset.c
> index 1d96e68..6b657b8 100644
> --- a/ell/uintset.c
> +++ b/ell/uintset.c
> @@ -122,6 +122,49 @@ static unsigned long find_last_bit(const unsigned long *addr, unsigned int size)
>         return size;
>  }
>
> +static unsigned long find_next_bit(const unsigned long *addr,
> +                                                       unsigned long size,
> +                                                       unsigned long bit)
> +{
> +       unsigned long mask;
> +       unsigned long offset;
> +
> +       if (bit >= size)
> +               return size;
> +
> +       addr += bit / BITS_PER_LONG;
> +       offset = bit % BITS_PER_LONG;
> +       bit -= offset;
> +
> +       if (offset) {
> +               mask = *addr & ~(~0UL >> (BITS_PER_LONG - offset));
> +               if (mask)
> +                       return bit + __ffs(mask);
> +
> +               bit += BITS_PER_LONG;
> +               addr++;
> +       }
> +
> +       for (size -= bit; size >= BITS_PER_LONG;
> +                       size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
> +               if (!*addr)
> +                       continue;
> +
> +               return bit + __ffs(*addr);
> +       }
> +
> +       if (!size)
> +               return bit;
> +
> +       mask = *addr & (~0UL >> (BITS_PER_LONG - size));
> +       if (mask)
> +               bit += __ffs(mask);
> +       else
> +               bit += size;
> +
> +       return bit;
> +}
> +
>  struct l_uintset {
>         unsigned long *bits;
>         uint16_t size;
> @@ -404,3 +447,56 @@ LIB_EXPORT uint32_t l_uintset_find_min(struct l_uintset *set)
>
>         return bit + set->min;
>  }
> +
> +/**
> + * l_uintset_intersect:
> + * @set_a: The set of numbers
> + * @set_b: The set of numbers
> + *
> + * Returns: A newly allocated l_uintset object containing intersection of
> + * @set_a and @set_b. If @set_a and @set_b cannot be intersected 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 min;
> +       uint32_t max;
> +       unsigned int bit_a;
> +       unsigned int bit_b;
> +
> +       if (unlikely(!set_a) || unlikely(!set_b))
> +               return NULL;
> +
> +       if (set_a->max < set_b->min || set_b->max < set_a->min)
> +               return NULL;
> +
> +       min = set_a->min <= set_b->min ? set_a->min : set_b->min;

So this basically does min = MIN(set_a->min, set_b->min) but could
safely do MAX(...).

> +       max = set_a->max >= set_b->max ? set_a->max : set_b->max;
> +
> +       intersection = l_uintset_new_from_range(min, max);
> +
> +       bit_a = find_first_bit(set_a->bits, set_a->size);
> +       bit_b = find_first_bit(set_b->bits, set_b->size);
> +
> +       while (bit_a < set_a->size && bit_b < set_b->size) {
> +               if (set_a->min + bit_a < set_b->min + bit_b) {
> +                       bit_a = find_next_bit(set_a->bits, set_a->size,
> +                                                               bit_a + 1);
> +                       continue;
> +               }
> +
> +               if (set_a->min + bit_a > set_b->min + bit_b) {
> +                       bit_b = find_next_bit(set_b->bits, set_b->size,
> +                                                               bit_b + 1);
> +                       continue;
> +               }
> +
> +               l_uintset_put(intersection, set_a->min + bit_a);
> +               bit_a = find_next_bit(set_a->bits, set_a->size, bit_a + 1);
> +               bit_b = find_next_bit(set_b->bits, set_b->size, bit_b + 1);
> +       }

Here you could also assign entire words in intersection->bits (with
some shifting required) and skip to the next non-zero word afterwards
although that wouldn't even be much faster than just assigning 0 by
&ing the words from set_a and set_b.

Best regards

[PATCH 1/2] uintset: Add l_uintset_intersect

[Tim Kourt]

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

l_uintset_intersect computes the intersection of two sets.
In addition, it introduces find_next_bit(…) that is used to
efficiently loop through the set bits in the set and may have
multiple implication in the future.
---
 ell/uintset.c | 96 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ell/uintset.h |  3 ++
 2 files changed, 99 insertions(+)

diff --git a/ell/uintset.c b/ell/uintset.c
index 1d96e68..6b657b8 100644
--- a/ell/uintset.c
+++ b/ell/uintset.c
@@ -122,6 +122,49 @@ static unsigned long find_last_bit(const unsigned long *addr, unsigned int size)
 	return size;
 }
 
+static unsigned long find_next_bit(const unsigned long *addr,
+							unsigned long size,
+							unsigned long bit)
+{
+	unsigned long mask;
+	unsigned long offset;
+
+	if (bit >= size)
+		return size;
+
+	addr += bit / BITS_PER_LONG;
+	offset = bit % BITS_PER_LONG;
+	bit -= offset;
+
+	if (offset) {
+		mask = *addr & ~(~0UL >> (BITS_PER_LONG - offset));
+		if (mask)
+			return bit + __ffs(mask);
+
+		bit += BITS_PER_LONG;
+		addr++;
+	}
+
+	for (size -= bit; size >= BITS_PER_LONG;
+			size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
+		if (!*addr)
+			continue;
+
+		return bit + __ffs(*addr);
+	}
+
+	if (!size)
+		return bit;
+
+	mask = *addr & (~0UL >> (BITS_PER_LONG - size));
+	if (mask)
+		bit += __ffs(mask);
+	else
+		bit += size;
+
+	return bit;
+}
+
 struct l_uintset {
 	unsigned long *bits;
 	uint16_t size;
@@ -404,3 +447,56 @@ LIB_EXPORT uint32_t l_uintset_find_min(struct l_uintset *set)
 
 	return bit + set->min;
 }
+
+/**
+ * l_uintset_intersect:
+ * @set_a: The set of numbers
+ * @set_b: The set of numbers
+ *
+ * Returns: A newly allocated l_uintset object containing intersection of
+ * @set_a and @set_b. If @set_a and @set_b cannot be intersected 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 min;
+	uint32_t max;
+	unsigned int bit_a;
+	unsigned int bit_b;
+
+	if (unlikely(!set_a) || unlikely(!set_b))
+		return NULL;
+
+	if (set_a->max < set_b->min || set_b->max < set_a->min)
+		return NULL;
+
+	min = set_a->min <= set_b->min ? set_a->min : set_b->min;
+	max = set_a->max >= set_b->max ? set_a->max : set_b->max;
+
+	intersection = l_uintset_new_from_range(min, max);
+
+	bit_a = find_first_bit(set_a->bits, set_a->size);
+	bit_b = find_first_bit(set_b->bits, set_b->size);
+
+	while (bit_a < set_a->size && bit_b < set_b->size) {
+		if (set_a->min + bit_a < set_b->min + bit_b) {
+			bit_a = find_next_bit(set_a->bits, set_a->size,
+								bit_a + 1);
+			continue;
+		}
+
+		if (set_a->min + bit_a > set_b->min + bit_b) {
+			bit_b = find_next_bit(set_b->bits, set_b->size,
+								bit_b + 1);
+			continue;
+		}
+
+		l_uintset_put(intersection, set_a->min + bit_a);
+		bit_a = find_next_bit(set_a->bits, set_a->size, bit_a + 1);
+		bit_b = find_next_bit(set_b->bits, set_b->size, bit_b + 1);
+	}
+
+	return intersection;
+}
diff --git a/ell/uintset.h b/ell/uintset.h
index 474c5e4..9986086 100644
--- a/ell/uintset.h
+++ b/ell/uintset.h
@@ -50,6 +50,9 @@ uint32_t l_uintset_find_min(struct l_uintset *set);
 uint32_t l_uintset_find_unused_min(struct l_uintset *set);
 uint32_t l_uintset_find_unused(struct l_uintset *set, uint32_t start);
 
+struct l_uintset *l_uintset_intersect(const struct l_uintset *set_a,
+						const struct l_uintset *set_b);
+
 #ifdef __cplusplus
 }
 #endif
-- 
2.13.6