uintset: Add l_uintset_intersect

PATCH In review Tim Kourt 3 participants 4 messages Mar 5, 2019

Share & tools

Tim Kourt

author

2019-03-05 20:35 UTC #0 lore raw

PATCH 1/2 uintset: Add l_uintset_intersect

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(+)

ell/uintset.c +96 -0

index 1d96e68..6b657b8 100644
@@ -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;
+}

ell/uintset.h +3 -0

index 474c5e4..9986086 100644
@@ -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

Signature · 1 line

2.13.6

Tim Kourt

author

2019-03-05 20:35 UTC #1 lore raw

PATCH 2/2 unit: Add l_uintset_intersect tests

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

unit/test-uintset.c +115 -0

index 42d9698..277cf6a 100644
@@ -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);

Signature · 1 line

2.13.6

Andrew Zaborowski

2019-03-05 21:12 UTC #2 lore raw

In reply to Tim Kourt

Hi Tim,

Quoted 83 lines · Tim Kourt

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

ell/uintset.c +59 -0

index 1d96e68..6b657b8 100644
@@ -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;

ell/uintset.c LIB_EXPORT uint32_t l_uintset_find_min(struct l_uintset *set) · line 475

Quoted 10 lines

ell/uintset.c +10 -0

+       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(...).

Quoted 14 lines

ell/uintset.c +14 -0

+       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;
+               }
+

ell/uintset.c LIB_EXPORT uint32_t l_uintset_find_min(struct l_uintset *set) · line 499

Quoted 10 lines

ell/uintset.c +10 -0

+               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

Denis Kenzior

2019-03-05 21:47 UTC #3 lore raw

In reply to Tim Kourt

Hi Tim,

Quoted 4 lines · Tim Kourt

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

Quoted 5 lines

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

<snip>

Quoted 14 lines

ell/uintset.c +14 -0

+
+/**
+ * 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;

ell/uintset.c LIB_EXPORT uint32_t l_uintset_find_min(struct l_uintset *set) · line 473

Quoted 10 lines

ell/uintset.c +10 -0

+	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