5:35 a.m.
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
5:35 a.m.
New subject: [PATCH 2/2] unit: Add l_uintset_intersect tests
---
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
6:12 a.m.
Hi Tim,
On Tue, 5 Mar 2019 at 21:35, Tim Kourt <tim.a.kourt(a)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
6:47 a.m.
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
723
days inactive
723
days old
3 comments
3 participants
participants (3)
-
Andrew Zaborowski -
Denis Kenzior -
Tim Kourt