* [PATCH 1/2] uintset: Add l_uintset_intersect @ 2019-03-05 20:35 Tim Kourt 2019-03-05 20:35 ` [PATCH 2/2] unit: Add l_uintset_intersect tests Tim Kourt ` (2 more replies) 0 siblings, 3 replies; 6+ messages in thread From: Tim Kourt @ 2019-03-05 20:35 UTC (permalink / raw) To: ell [-- 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 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH 2/2] unit: Add l_uintset_intersect tests 2019-03-05 20:35 [PATCH 1/2] uintset: Add l_uintset_intersect Tim Kourt @ 2019-03-05 20:35 ` Tim Kourt 2019-03-05 21:12 ` [PATCH 1/2] uintset: Add l_uintset_intersect Andrew Zaborowski 2019-03-05 21:47 ` Denis Kenzior 2 siblings, 0 replies; 6+ messages in thread From: Tim Kourt @ 2019-03-05 20:35 UTC (permalink / raw) To: ell [-- 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 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH 1/2] uintset: Add l_uintset_intersect 2019-03-05 20:35 [PATCH 1/2] uintset: Add l_uintset_intersect Tim Kourt 2019-03-05 20:35 ` [PATCH 2/2] unit: Add l_uintset_intersect tests Tim Kourt @ 2019-03-05 21:12 ` Andrew Zaborowski 2019-03-05 21:47 ` Denis Kenzior 2 siblings, 0 replies; 6+ messages in thread From: Andrew Zaborowski @ 2019-03-05 21:12 UTC (permalink / raw) To: ell [-- 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 ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 1/2] uintset: Add l_uintset_intersect 2019-03-05 20:35 [PATCH 1/2] uintset: Add l_uintset_intersect Tim Kourt 2019-03-05 20:35 ` [PATCH 2/2] unit: Add l_uintset_intersect tests Tim Kourt 2019-03-05 21:12 ` [PATCH 1/2] uintset: Add l_uintset_intersect Andrew Zaborowski @ 2019-03-05 21:47 ` Denis Kenzior 2 siblings, 0 replies; 6+ messages in thread From: Denis Kenzior @ 2019-03-05 21:47 UTC (permalink / raw) To: ell [-- 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 ^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH 1/2] uintset: Add l_uintset_intersect @ 2019-03-07 0:17 Tim Kourt 2019-03-07 16:11 ` Denis Kenzior 0 siblings, 1 reply; 6+ messages in thread From: Tim Kourt @ 2019-03-07 0:17 UTC (permalink / raw) To: ell [-- 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 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH 1/2] uintset: Add l_uintset_intersect 2019-03-07 0:17 Tim Kourt @ 2019-03-07 16:11 ` Denis Kenzior 0 siblings, 0 replies; 6+ messages in thread From: Denis Kenzior @ 2019-03-07 16:11 UTC (permalink / raw) To: ell [-- 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 ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2019-03-07 16:11 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-03-05 20:35 [PATCH 1/2] uintset: Add l_uintset_intersect Tim Kourt 2019-03-05 20:35 ` [PATCH 2/2] unit: Add l_uintset_intersect tests Tim Kourt 2019-03-05 21:12 ` [PATCH 1/2] uintset: Add l_uintset_intersect Andrew Zaborowski 2019-03-05 21:47 ` Denis Kenzior 2019-03-07 0:17 Tim Kourt 2019-03-07 16:11 ` Denis Kenzior
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.