* [PATCH 1/2] uintset: add l_uintset_subtract
@ 2022-07-22 20:27 James Prestwood
2022-07-22 20:27 ` [PATCH 2/2] unit: add unit test for l_uintset_subtract James Prestwood
2022-07-22 21:09 ` [PATCH 1/2] uintset: add l_uintset_subtract Denis Kenzior
0 siblings, 2 replies; 3+ messages in thread
From: James Prestwood @ 2022-07-22 20:27 UTC (permalink / raw)
To: ell; +Cc: James Prestwood
This subtracts set_b from set_a, and returns the new set.
---
ell/ell.sym | 1 +
ell/uintset.c | 37 +++++++++++++++++++++++++++++++++++++
ell/uintset.h | 3 +++
3 files changed, 41 insertions(+)
diff --git a/ell/ell.sym b/ell/ell.sym
index 8f4e59d..f454921 100644
--- a/ell/ell.sym
+++ b/ell/ell.sym
@@ -537,6 +537,7 @@ global:
l_uintset_foreach;
l_uintset_clone;
l_uintset_intersect;
+ l_uintset_subtract;
l_uintset_isempty;
l_uintset_size;
/* uuid */
diff --git a/ell/uintset.c b/ell/uintset.c
index 863bc56..4837bcf 100644
--- a/ell/uintset.c
+++ b/ell/uintset.c
@@ -532,6 +532,43 @@ LIB_EXPORT struct l_uintset *l_uintset_intersect(const struct l_uintset *set_a,
return intersection;
}
+/**
+ * l_uintset_subtract:
+ * @set_a: The set of numbers
+ * @set_b: The set of numbers to subtract from set_a
+ *
+ * Subtracts 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 containing set_a - set_b
+ */
+LIB_EXPORT struct l_uintset *l_uintset_subtract(const struct l_uintset *set_a,
+ const struct l_uintset *set_b)
+{
+ struct l_uintset *subtraction;
+ 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;
+
+ subtraction = l_uintset_new_from_range(set_a->min, set_a->max);
+
+ offset_max = (set_a->size + BITS_PER_LONG - 1) / BITS_PER_LONG;
+
+ /* Subtract by: set_a & ~set_b */
+ for (offset = 0; offset < offset_max; offset++) {
+ subtraction->bits[offset] =
+ set_a->bits[offset] & ~(set_b->bits[offset]);
+ }
+
+ return subtraction;
+}
+
/**
* l_uintset_isempty
* @set: The set of numbers
diff --git a/ell/uintset.h b/ell/uintset.h
index aa9de48..86ce8f7 100644
--- a/ell/uintset.h
+++ b/ell/uintset.h
@@ -60,6 +60,9 @@ void l_uintset_foreach(const struct l_uintset *set,
struct l_uintset *l_uintset_clone(const struct l_uintset *original);
struct l_uintset *l_uintset_intersect(const struct l_uintset *set_a,
const struct l_uintset *set_b);
+struct l_uintset *l_uintset_subtract(const struct l_uintset *set_a,
+ const struct l_uintset *set_b);
+
bool l_uintset_isempty(const struct l_uintset *set);
uint32_t l_uintset_size(const struct l_uintset *set);
--
2.34.1
^ permalink raw reply related [flat|nested] 3+ messages in thread
* [PATCH 2/2] unit: add unit test for l_uintset_subtract
2022-07-22 20:27 [PATCH 1/2] uintset: add l_uintset_subtract James Prestwood
@ 2022-07-22 20:27 ` James Prestwood
2022-07-22 21:09 ` [PATCH 1/2] uintset: add l_uintset_subtract Denis Kenzior
1 sibling, 0 replies; 3+ messages in thread
From: James Prestwood @ 2022-07-22 20:27 UTC (permalink / raw)
To: ell; +Cc: James Prestwood
---
unit/test-uintset.c | 54 +++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 54 insertions(+)
diff --git a/unit/test-uintset.c b/unit/test-uintset.c
index 6e3767b..a097f0b 100644
--- a/unit/test-uintset.c
+++ b/unit/test-uintset.c
@@ -388,6 +388,59 @@ static void test_uintset_size(const void *user_data)
l_uintset_free(set);
}
+static void test_uintset_subtract(const void *data)
+{
+ struct l_uintset *set_a = l_uintset_new_from_range(0, 10);
+ struct l_uintset *set_b = l_uintset_new_from_range(1, 11);
+ struct l_uintset *sub;
+
+ /* Some sanity checks */
+ assert(l_uintset_subtract(NULL, NULL) == NULL);
+ assert(l_uintset_subtract(set_a, set_b) == NULL);
+
+ l_uintset_free(set_a);
+ l_uintset_free(set_b);
+
+ set_a = l_uintset_new_from_range(0, 128);
+ set_b = l_uintset_new_from_range(0, 128);
+
+ /* (<empty>) - (<empty>) = (<empty>) */
+ sub = l_uintset_subtract(set_a, set_b);
+ assert(l_uintset_isempty(sub));
+ l_uintset_free(sub);
+
+ /* Sanity check this works across word boundaries */
+ l_uintset_put(set_b, 65);
+ l_uintset_put(set_b, 64);
+ l_uintset_put(set_b, 63);
+
+ /* (<empty>) - (65, 64, 63) = (<empty>) */
+ sub = l_uintset_subtract(set_a, set_b);
+ assert(!l_uintset_contains(sub, 64));
+ l_uintset_free(sub);
+
+ l_uintset_put(set_a, 64);
+
+ /* (64) - (65, 64, 63) = (<empty>) */
+ sub = l_uintset_subtract(set_a, set_b);
+ assert(!l_uintset_contains(sub, 64));
+ l_uintset_free(sub);
+
+ l_uintset_take(set_b, 64);
+
+ /* (64) - (65, 63) = (64) */
+ sub = l_uintset_subtract(set_a, set_b);
+ assert(l_uintset_contains(sub, 64));
+ l_uintset_free(sub);
+
+ /* (65, 63) - (64) = (65, 63) */
+ sub = l_uintset_subtract(set_b, set_a);
+ assert(l_uintset_contains(sub, 65));
+ assert(!l_uintset_contains(sub, 64));
+ assert(l_uintset_contains(sub, 63));
+ l_uintset_free(sub);
+}
+
int main(int argc, char *argv[])
{
l_test_init(&argc, &argv);
@@ -407,6 +460,7 @@ int main(int argc, char *argv[])
&intersect_data_2);
l_test_add("l_uintset isempty", test_uintset_isempty, NULL);
l_test_add("l_uintset size", test_uintset_size, NULL);
+ l_test_add("l_uintset_subtract", test_uintset_subtract, NULL);
return l_test_run();
}
--
2.34.1
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: [PATCH 1/2] uintset: add l_uintset_subtract
2022-07-22 20:27 [PATCH 1/2] uintset: add l_uintset_subtract James Prestwood
2022-07-22 20:27 ` [PATCH 2/2] unit: add unit test for l_uintset_subtract James Prestwood
@ 2022-07-22 21:09 ` Denis Kenzior
1 sibling, 0 replies; 3+ messages in thread
From: Denis Kenzior @ 2022-07-22 21:09 UTC (permalink / raw)
To: James Prestwood, ell
Hi James,
On 7/22/22 15:27, James Prestwood wrote:
> This subtracts set_b from set_a, and returns the new set.
> ---
> ell/ell.sym | 1 +
> ell/uintset.c | 37 +++++++++++++++++++++++++++++++++++++
> ell/uintset.h | 3 +++
> 3 files changed, 41 insertions(+)
>
Both applied, thanks.
Regards,
-Denis
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2022-07-22 21:24 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-07-22 20:27 [PATCH 1/2] uintset: add l_uintset_subtract James Prestwood
2022-07-22 20:27 ` [PATCH 2/2] unit: add unit test for l_uintset_subtract James Prestwood
2022-07-22 21:09 ` [PATCH 1/2] uintset: add l_uintset_subtract 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.