* [PATCH v2 1/7] libsepol/tests: add ebitmap tests
@ 2022-07-19 15:30 Christian Göttsche
2022-07-19 15:30 ` [PATCH v2 2/7] libsepol: add ebitmap_init_range Christian Göttsche
` (6 more replies)
0 siblings, 7 replies; 9+ messages in thread
From: Christian Göttsche @ 2022-07-19 15:30 UTC (permalink / raw)
To: selinux; +Cc: Christian Göttsche
Preparation for several ebitmap related optimizations.
Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
v2:
- add more tests for multi node ebitmaps and for bits set at node
bounds
- test ebitmap_for_each_bit()
---
libsepol/tests/libsepol-tests.c | 2 +
libsepol/tests/test-ebitmap.c | 1048 +++++++++++++++++++++++++++++++
libsepol/tests/test-ebitmap.h | 10 +
3 files changed, 1060 insertions(+)
create mode 100644 libsepol/tests/test-ebitmap.c
create mode 100644 libsepol/tests/test-ebitmap.h
diff --git a/libsepol/tests/libsepol-tests.c b/libsepol/tests/libsepol-tests.c
index dc8fd5ce..5ae6bedc 100644
--- a/libsepol/tests/libsepol-tests.c
+++ b/libsepol/tests/libsepol-tests.c
@@ -19,6 +19,7 @@
*/
#include "test-cond.h"
+#include "test-ebitmap.h"
#include "test-linker.h"
#include "test-expander.h"
#include "test-deps.h"
@@ -64,6 +65,7 @@ static bool do_tests(int interactive, int verbose)
if (CUE_SUCCESS != CU_initialize_registry())
return CU_get_error();
+ DECLARE_SUITE(ebitmap);
DECLARE_SUITE(cond);
DECLARE_SUITE(linker);
DECLARE_SUITE(expander);
diff --git a/libsepol/tests/test-ebitmap.c b/libsepol/tests/test-ebitmap.c
new file mode 100644
index 00000000..fad5bd75
--- /dev/null
+++ b/libsepol/tests/test-ebitmap.c
@@ -0,0 +1,1048 @@
+#include "test-ebitmap.h"
+
+#include <stdlib.h>
+#include <time.h>
+
+#include <sepol/debug.h>
+#include <sepol/policydb/ebitmap.h>
+
+#define RANDOM_ROUNDS 10
+
+
+static int ebitmap_init_random(ebitmap_t *e, unsigned int length, int set_chance)
+{
+ unsigned int i;
+ int rc;
+
+ if (set_chance <= 0 || set_chance > 100)
+ return -EINVAL;
+
+ ebitmap_init(e);
+
+ for (i = 0; i < length; i++) {
+ if ((random() % 100) < set_chance) {
+ rc = ebitmap_set_bit(e, i, 1);
+ if (rc)
+ return rc;
+ }
+ }
+
+ return 0;
+}
+
+static void test_ebitmap_init_destroy(void)
+{
+ ebitmap_t e;
+
+ /* verify idempotence */
+ ebitmap_init(&e);
+ ebitmap_init(&e);
+ ebitmap_init(&e);
+
+ CU_ASSERT(ebitmap_is_empty(&e));
+ CU_ASSERT_PTR_NULL(ebitmap_startnode(&e));
+
+ /* verify idempotence */
+ ebitmap_destroy(&e);
+ ebitmap_destroy(&e);
+ ebitmap_destroy(&e);
+
+ CU_ASSERT(ebitmap_is_empty(&e));
+ CU_ASSERT_PTR_NULL(ebitmap_startnode(&e));
+}
+
+static void test_ebitmap_cmp(void)
+{
+ ebitmap_t e1, e2;
+
+ ebitmap_init(&e1);
+ ebitmap_init(&e2);
+
+ CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 10, 1), 0);
+ CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 63, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 63, 1), 0);
+ CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 64, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 64, 1), 0);
+ CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1022, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1022, 1), 0);
+ CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1023, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1023, 1), 0);
+ CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1024, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1024, 1), 0);
+ CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1025, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1025, 1), 0);
+ CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 255, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 255, 1), 0);
+ CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 256, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 256, 1), 0);
+ CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 639, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 639, 1), 0);
+ CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 640, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 640, 1), 0);
+ CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 900, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 900, 1), 0);
+ CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+ ebitmap_destroy(&e2);
+
+ CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
+
+ ebitmap_destroy(&e1);
+
+ CU_ASSERT(ebitmap_cmp(&e1, &e2));
+}
+
+static void test_ebitmap_set_and_get(void)
+{
+ ebitmap_t e;
+
+ ebitmap_init(&e);
+
+ CU_ASSERT(ebitmap_is_empty(&e));
+ CU_ASSERT_TRUE(ebitmap_is_empty(&e));
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 0);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 0);
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e, UINT32_MAX, 1), -EINVAL);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 10, 0), 0);
+ CU_ASSERT(ebitmap_is_empty(&e));
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 0);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 0);
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 10, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 1);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 10);
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 1);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 100, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 2);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 100);
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 100), 1);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 50, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 3);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 100);
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 50), 1);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1023, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 4);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023);
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1023), 1);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1024, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 5);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1024);
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1024), 1);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1050, 1), 0);
+ CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 6);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1050);
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1050), 1);
+
+ {
+ ebitmap_node_t *n;
+ unsigned int bit, count;
+
+ /* iterate all allocated bits */
+ count = 0;
+ ebitmap_for_each_bit(&e, n, bit) {
+ CU_ASSERT( bit < 64 ||
+ (64 <= bit && bit < 128) ||
+ (960 <= bit && bit < 1024) ||
+ (1024 <= bit && bit < 1088));
+ count++;
+ }
+ CU_ASSERT_EQUAL(count, 4 * 64);
+
+ count = 0;
+ ebitmap_for_each_positive_bit(&e, n, bit) {
+ CU_ASSERT(bit == 10 ||
+ bit == 50 ||
+ bit == 100 ||
+ bit == 1023 ||
+ bit == 1024 ||
+ bit == 1050);
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&e, bit), 1);
+ count++;
+ }
+ CU_ASSERT_EQUAL(count, 6);
+ }
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1024, 0), 0);
+ CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 5);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1050);
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1024), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1050, 0), 0);
+ CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 4);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023);
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1050), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 100, 0), 0);
+ CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 3);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023);
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 100), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 10, 0), 0);
+ CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 2);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023);
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 50, 0), 0);
+ CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 1);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023);
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 50), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1023, 0), 0);
+ CU_ASSERT_TRUE(ebitmap_is_empty(&e));
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 0);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 0);
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1023), 0);
+
+ ebitmap_destroy(&e);
+}
+
+static void test_ebitmap_or(void)
+{
+ ebitmap_t e1, e2, e3, e4;
+
+ ebitmap_init(&e1);
+ ebitmap_init(&e2);
+ ebitmap_init(&e3);
+ ebitmap_init(&e4);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 100, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 101, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 318, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 319, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 383, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 384, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 449, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1013, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 11, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 101, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 430, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 665, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 11, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 100, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 101, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 318, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 319, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 383, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 384, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 449, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 665, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 1013, 1), 0);
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_or(&dst, &e1, &e1), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e1));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_or(&dst, &e2, &e2), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e2));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_or(&dst, &e1, &e2), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_or(&dst, &e3, &e3), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_or(&dst, &e3, &e4), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_or(&dst, &e4, &e4), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+ ebitmap_destroy(&dst);
+ }
+
+ ebitmap_destroy(&e4);
+ ebitmap_destroy(&e3);
+ ebitmap_destroy(&e2);
+ ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap_and(void)
+{
+ {
+ ebitmap_t e1, e2, e12, e3, e4;
+
+ ebitmap_init(&e1);
+ ebitmap_init(&e2);
+ ebitmap_init(&e12);
+ ebitmap_init(&e3);
+ ebitmap_init(&e4);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 100, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 101, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 318, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 319, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 383, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 384, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 449, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1013, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 11, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 101, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 319, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 665, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 101, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 319, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 11, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 100, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 101, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 318, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 319, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 383, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 384, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 449, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 665, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 1013, 1), 0);
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_and(&dst, &e1, &e1), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e1));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_and(&dst, &e2, &e2), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e2));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_and(&dst, &e1, &e2), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e12));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_and(&dst, &e3, &e3), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_and(&dst, &e1, &e3), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e1));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_and(&dst, &e2, &e3), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e2));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_and(&dst, &e4, &e4), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_and(&dst, &e3, &e4), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+ ebitmap_destroy(&dst);
+ }
+
+ ebitmap_destroy(&e4);
+ ebitmap_destroy(&e3);
+ ebitmap_destroy(&e12);
+ ebitmap_destroy(&e2);
+ ebitmap_destroy(&e1);
+ }
+
+ {
+ ebitmap_t e5;
+ ebitmap_t e6;
+ ebitmap_t e56;
+ ebitmap_t dst;
+
+ ebitmap_init(&e5);
+ ebitmap_init(&e6);
+ ebitmap_init(&e56);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 64, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 192, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 319, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 320, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 192, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 319, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_and(&dst, &e5, &e6), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e56));
+
+ ebitmap_destroy(&dst);
+ ebitmap_destroy(&e56);
+ ebitmap_destroy(&e6);
+ ebitmap_destroy(&e5);
+ }
+}
+
+static void test_ebitmap_xor(void)
+{
+ {
+ ebitmap_t e1, e2, e3, e4;
+
+ ebitmap_init(&e1);
+ ebitmap_init(&e2);
+ ebitmap_init(&e3);
+ ebitmap_init(&e4);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 5, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 3, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 6, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 9, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 3, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 5, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 6, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 9, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
+
+ {
+ ebitmap_t dst1, dst2;
+
+ CU_ASSERT_EQUAL(ebitmap_xor(&dst1, &e1, &e1), 0);
+ CU_ASSERT(ebitmap_cmp(&dst1, &e4));
+ CU_ASSERT_EQUAL(ebitmap_xor(&dst2, &dst1, &e1), 0);
+ CU_ASSERT(ebitmap_cmp(&dst2, &e1));
+
+ ebitmap_destroy(&dst2);
+ ebitmap_destroy(&dst1);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e2, &e2), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e3, &e3), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e4, &e4), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e1, &e2), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e2, &e4), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e2));
+
+ ebitmap_destroy(&dst);
+ }
+
+ ebitmap_destroy(&e4);
+ ebitmap_destroy(&e3);
+ ebitmap_destroy(&e2);
+ ebitmap_destroy(&e1);
+ }
+
+ {
+ ebitmap_t e5;
+ ebitmap_t e6;
+ ebitmap_t e56;
+ ebitmap_t dst;
+
+ ebitmap_init(&e5);
+ ebitmap_init(&e6);
+ ebitmap_init(&e56);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 64, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 192, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 319, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 320, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 63, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 64, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 191, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 318, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 320, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e5, &e6), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e56));
+
+ ebitmap_destroy(&dst);
+ ebitmap_destroy(&e56);
+ ebitmap_destroy(&e6);
+ ebitmap_destroy(&e5);
+ }
+}
+
+static void test_ebitmap_not(void)
+{
+ {
+ ebitmap_t e1, e2, e3, e4;
+
+ ebitmap_init(&e1);
+ ebitmap_init(&e2);
+ ebitmap_init(&e3);
+ ebitmap_init(&e4);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 0, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 5, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 2, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 3, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 4, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 6, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 7, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 8, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 9, 1), 0);
+
+ {
+ ebitmap_t dst1, dst2;
+
+ CU_ASSERT_EQUAL(ebitmap_not(&dst1, &e3, 10), 0);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&dst1), 9);
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&dst1), 10);
+
+ CU_ASSERT_EQUAL(ebitmap_not(&dst2, &dst1, 10), 0);
+ CU_ASSERT(ebitmap_cmp(&dst2, &e3));
+
+ ebitmap_destroy(&dst2);
+ ebitmap_destroy(&dst1);
+ }
+
+ {
+ ebitmap_t dst1, dst2;
+
+ CU_ASSERT_EQUAL(ebitmap_not(&dst1, &e1, 11), 0);
+ CU_ASSERT(ebitmap_cmp(&dst1, &e2));
+ CU_ASSERT_EQUAL(ebitmap_not(&dst2, &dst1, 11), 0);
+ CU_ASSERT(ebitmap_cmp(&dst2, &e1));
+
+ ebitmap_destroy(&dst2);
+ ebitmap_destroy(&dst1);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_not(&dst, &e1, 8), 0);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&dst), 7);
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&dst), 5);
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_not(&dst, &e1, 12), 0);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&dst), 11);
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&dst), 8);
+
+ ebitmap_destroy(&dst);
+ }
+
+ ebitmap_destroy(&e3);
+ ebitmap_destroy(&e2);
+ ebitmap_destroy(&e1);
+ }
+
+ {
+ ebitmap_t e5;
+ ebitmap_t e5not;
+ ebitmap_node_t *n;
+ unsigned int bit;
+
+ ebitmap_init(&e5);
+ ebitmap_init(&e5not);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0);
+
+ for (bit = 0; bit < 317; bit++)
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5not, bit, 1), 0);
+ ebitmap_for_each_positive_bit(&e5, n, bit)
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5not, bit, 0), 0);
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_not(&dst, &e5, 317), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e5not));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_not(&dst, &e5, 318), 0);
+ CU_ASSERT_FALSE(ebitmap_cmp(&dst, &e5not));
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5not, 317, 1), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e5not));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_not(&dst, &e5, 319), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e5not));
+
+ ebitmap_destroy(&dst);
+ }
+
+ ebitmap_destroy(&e5not);
+ ebitmap_destroy(&e5);
+ }
+}
+
+static void test_ebitmap_andnot(void)
+{
+ {
+ ebitmap_t e1, e2, e12, e3, e4;
+
+ ebitmap_init(&e1);
+ ebitmap_init(&e2);
+ ebitmap_init(&e12);
+ ebitmap_init(&e3);
+ ebitmap_init(&e4);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 100, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 101, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 430, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1013, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 11, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 101, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 665, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 10, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 100, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 430, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 1013, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 11, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 100, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 101, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 665, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 1013, 1), 0);
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e1, &e1, 1024), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e2, &e2, 1024), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e1, &e2, 1024), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e12));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e3, &e3, 1024), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e1, &e3, 1024), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e2, &e12, 1024), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e2));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e4, &e4, 1024), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e3, &e4, 1024), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+ ebitmap_destroy(&dst);
+ }
+
+ ebitmap_destroy(&e4);
+ ebitmap_destroy(&e3);
+ ebitmap_destroy(&e12);
+ ebitmap_destroy(&e2);
+ ebitmap_destroy(&e1);
+ }
+
+ {
+ ebitmap_t e5;
+ ebitmap_t e6;
+ ebitmap_t e56;
+
+ ebitmap_init(&e5);
+ ebitmap_init(&e6);
+ ebitmap_init(&e56);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 64, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 192, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 319, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 320, 1), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 63, 1), 0);
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 191, 1), 0);
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 317), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e56));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 318), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e56));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 319), 0);
+ CU_ASSERT_FALSE(ebitmap_cmp(&dst, &e56));
+
+ CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 318, 1), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e56));
+
+ ebitmap_destroy(&dst);
+ }
+
+ {
+ ebitmap_t dst;
+
+ CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 320), 0);
+ CU_ASSERT(ebitmap_cmp(&dst, &e56));
+
+ ebitmap_destroy(&dst);
+ }
+
+ ebitmap_destroy(&e56);
+ ebitmap_destroy(&e6);
+ ebitmap_destroy(&e5);
+ }
+}
+
+static void test_ebitmap__random_impl(unsigned int length, int set_chance)
+{
+ ebitmap_t e1, e2, dst_cpy, dst_or, dst_and, dst_xor1, dst_xor2, dst_not1, dst_not2, dst_andnot;
+ unsigned int i;
+
+ CU_ASSERT_EQUAL(ebitmap_init_random(&e1, length, set_chance), 0);
+ CU_ASSERT_EQUAL(ebitmap_init_random(&e2, length, set_chance), 0);
+
+ CU_ASSERT_EQUAL(ebitmap_cpy(&dst_cpy, &e1), 0);
+ CU_ASSERT(ebitmap_cmp(&dst_cpy, &e1));
+
+ CU_ASSERT_EQUAL(ebitmap_or(&dst_or, &e1, &e2), 0);
+ for (i = 0; i < length; i++)
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_or, i), ebitmap_get_bit(&e1, i) | ebitmap_get_bit(&e2, i));
+
+ CU_ASSERT_EQUAL(ebitmap_and(&dst_and, &e1, &e2), 0);
+ for (i = 0; i < length; i++)
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_and, i), ebitmap_get_bit(&e1, i) & ebitmap_get_bit(&e2, i));
+
+ CU_ASSERT_EQUAL(ebitmap_xor(&dst_xor1, &e1, &e2), 0);
+ for (i = 0; i < length; i++)
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_xor1, i), ebitmap_get_bit(&e1, i) ^ ebitmap_get_bit(&e2, i));
+ CU_ASSERT_EQUAL(ebitmap_xor(&dst_xor2, &dst_xor1, &e2), 0);
+ CU_ASSERT(ebitmap_cmp(&dst_xor2, &e1));
+
+ CU_ASSERT_EQUAL(ebitmap_not(&dst_not1, &e1, length), 0);
+ for (i = 0; i < length; i++)
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_not1, i), !ebitmap_get_bit(&e1, i));
+ CU_ASSERT_EQUAL(ebitmap_not(&dst_not2, &dst_not1, length), 0);
+ CU_ASSERT(ebitmap_cmp(&dst_not2, &e1));
+
+ CU_ASSERT_EQUAL(ebitmap_andnot(&dst_andnot, &e1, &e2, length), 0);
+ for (i = 0; i < length; i++)
+ CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_andnot, i), ebitmap_get_bit(&e1, i) & !ebitmap_get_bit(&e2, i));
+
+ ebitmap_destroy(&dst_andnot);
+ ebitmap_destroy(&dst_not2);
+ ebitmap_destroy(&dst_not1);
+ ebitmap_destroy(&dst_xor2);
+ ebitmap_destroy(&dst_xor1);
+ ebitmap_destroy(&dst_and);
+ ebitmap_destroy(&dst_or);
+ ebitmap_destroy(&dst_cpy);
+ ebitmap_destroy(&e2);
+ ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap__random(void)
+{
+ unsigned int i;
+
+ for (i = 0; i < RANDOM_ROUNDS; i++)
+ test_ebitmap__random_impl(5, 10);
+
+ for (i = 0; i < RANDOM_ROUNDS; i++)
+ test_ebitmap__random_impl(5, 90);
+
+ for (i = 0; i < RANDOM_ROUNDS; i++)
+ test_ebitmap__random_impl(1024, 50);
+
+ for (i = 0; i < RANDOM_ROUNDS; i++)
+ test_ebitmap__random_impl(8000, 5);
+
+ for (i = 0; i < RANDOM_ROUNDS; i++)
+ test_ebitmap__random_impl(8000, 95);
+}
+
+/*
+ * External hooks
+ */
+
+int ebitmap_test_init(void)
+{
+ srandom(time(NULL));
+
+ /* silence ebitmap_set_bit() failure message */
+ sepol_debug(0);
+
+ return 0;
+}
+
+int ebitmap_test_cleanup(void)
+{
+ return 0;
+}
+
+#define ADD_TEST(name) \
+ do { \
+ if (NULL == CU_add_test(suite, #name, test_##name)) { \
+ return CU_get_error(); \
+ } \
+ } while (0)
+
+int ebitmap_add_tests(CU_pSuite suite)
+{
+ ADD_TEST(ebitmap_init_destroy);
+ ADD_TEST(ebitmap_cmp);
+ ADD_TEST(ebitmap_set_and_get);
+ ADD_TEST(ebitmap_or);
+ ADD_TEST(ebitmap_and);
+ ADD_TEST(ebitmap_xor);
+ ADD_TEST(ebitmap_not);
+ ADD_TEST(ebitmap_andnot);
+ ADD_TEST(ebitmap__random);
+ return 0;
+}
diff --git a/libsepol/tests/test-ebitmap.h b/libsepol/tests/test-ebitmap.h
new file mode 100644
index 00000000..952a0421
--- /dev/null
+++ b/libsepol/tests/test-ebitmap.h
@@ -0,0 +1,10 @@
+#ifndef TEST_EBITMAP_H__
+#define TEST_EBITMAP_H__
+
+#include <CUnit/Basic.h>
+
+int ebitmap_test_init(void);
+int ebitmap_test_cleanup(void);
+int ebitmap_add_tests(CU_pSuite suite);
+
+#endif /* TEST_EBITMAP_H__ */
--
2.36.1
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH v2 2/7] libsepol: add ebitmap_init_range
2022-07-19 15:30 [PATCH v2 1/7] libsepol/tests: add ebitmap tests Christian Göttsche
@ 2022-07-19 15:30 ` Christian Göttsche
2022-07-19 15:30 ` [PATCH v2 3/7] libsepol/cil: use ebitmap_init_range Christian Göttsche
` (5 subsequent siblings)
6 siblings, 0 replies; 9+ messages in thread
From: Christian Göttsche @ 2022-07-19 15:30 UTC (permalink / raw)
To: selinux; +Cc: Christian Göttsche
Add an initializer for ebitmaps that sets all bits in a given range to
save node traversals for each bit to set, compared to calling
ebitmap_init() followed by iterating ebitmap_set_bit().
Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
v2:
use braces for all if-else branches when used for at least one of them
---
libsepol/include/sepol/policydb/ebitmap.h | 1 +
libsepol/src/ebitmap.c | 49 +++++++++++++++++++++++
libsepol/tests/test-ebitmap.c | 32 +++++++++++++++
3 files changed, 82 insertions(+)
diff --git a/libsepol/include/sepol/policydb/ebitmap.h b/libsepol/include/sepol/policydb/ebitmap.h
index 81d0c7a6..85b7ccfb 100644
--- a/libsepol/include/sepol/policydb/ebitmap.h
+++ b/libsepol/include/sepol/policydb/ebitmap.h
@@ -94,6 +94,7 @@ extern int ebitmap_contains(const ebitmap_t * e1, const ebitmap_t * e2);
extern int ebitmap_match_any(const ebitmap_t *e1, const ebitmap_t *e2);
extern int ebitmap_get_bit(const ebitmap_t * e, unsigned int bit);
extern int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value);
+extern int ebitmap_init_range(ebitmap_t * e, unsigned int minbit, unsigned int maxbit);
extern unsigned int ebitmap_highest_set_bit(const ebitmap_t * e);
extern void ebitmap_destroy(ebitmap_t * e);
extern int ebitmap_read(ebitmap_t * e, void *fp);
diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c
index bd98c0f8..0f9afd62 100644
--- a/libsepol/src/ebitmap.c
+++ b/libsepol/src/ebitmap.c
@@ -349,6 +349,55 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
return 0;
}
+int ebitmap_init_range(ebitmap_t * e, unsigned int minbit, unsigned int maxbit)
+{
+ ebitmap_node_t *new, *prev = NULL;
+ uint32_t minstartbit = minbit & ~(MAPSIZE - 1);
+ uint32_t maxstartbit = maxbit & ~(MAPSIZE - 1);
+ uint32_t minhighbit = minstartbit + MAPSIZE;
+ uint32_t maxhighbit = maxstartbit + MAPSIZE;
+ uint32_t startbit;
+ MAPTYPE mask;
+
+ ebitmap_init(e);
+
+ if (minbit > maxbit)
+ return -EINVAL;
+
+ if (minhighbit == 0 || maxhighbit == 0)
+ return -EOVERFLOW;
+
+ for (startbit = minstartbit; startbit <= maxstartbit; startbit += MAPSIZE) {
+ new = malloc(sizeof(ebitmap_node_t));
+ if (!new)
+ return -ENOMEM;
+
+ new->next = NULL;
+ new->startbit = startbit;
+
+ if (startbit != minstartbit && startbit != maxstartbit) {
+ new->map = ~((MAPTYPE)0);
+ } else if (startbit != maxstartbit) {
+ new->map = ~((MAPTYPE)0) << (minbit - startbit);
+ } else if (startbit != minstartbit) {
+ new->map = ~((MAPTYPE)0) >> (MAPSIZE - (maxbit - startbit + 1));
+ } else {
+ mask = ~((MAPTYPE)0) >> (MAPSIZE - (maxbit - minbit + 1));
+ new->map = (mask << (minbit - startbit));
+ }
+
+ if (prev)
+ prev->next = new;
+ else
+ e->node = new;
+ prev = new;
+ }
+
+ e->highbit = maxhighbit;
+
+ return 0;
+}
+
unsigned int ebitmap_highest_set_bit(const ebitmap_t * e)
{
const ebitmap_node_t *n;
diff --git a/libsepol/tests/test-ebitmap.c b/libsepol/tests/test-ebitmap.c
index fad5bd75..8774555e 100644
--- a/libsepol/tests/test-ebitmap.c
+++ b/libsepol/tests/test-ebitmap.c
@@ -253,6 +253,37 @@ static void test_ebitmap_set_and_get(void)
ebitmap_destroy(&e);
}
+static void test_ebitmap_init_range(void)
+{
+ ebitmap_t e1, e2, e3, e4, e5, e6;
+
+ CU_ASSERT_EQUAL(ebitmap_init_range(&e1, 0, 0), 0);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e1), 0);
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e1), 1);
+
+ CU_ASSERT_EQUAL(ebitmap_init_range(&e2, 0, 5), 0);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e2), 5);
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e2), 6);
+
+ CU_ASSERT_EQUAL(ebitmap_init_range(&e3, 20, 100), 0);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e3), 100);
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e3), 81);
+
+ CU_ASSERT_EQUAL(ebitmap_init_range(&e4, 100, 400), 0);
+ CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e4), 400);
+ CU_ASSERT_EQUAL(ebitmap_cardinality(&e4), 301);
+
+ CU_ASSERT_EQUAL(ebitmap_init_range(&e5, 10, 5), -EINVAL);
+ CU_ASSERT_EQUAL(ebitmap_init_range(&e6, 0, UINT32_MAX), -EOVERFLOW);
+
+ ebitmap_destroy(&e6);
+ ebitmap_destroy(&e5);
+ ebitmap_destroy(&e4);
+ ebitmap_destroy(&e3);
+ ebitmap_destroy(&e2);
+ ebitmap_destroy(&e1);
+}
+
static void test_ebitmap_or(void)
{
ebitmap_t e1, e2, e3, e4;
@@ -1038,6 +1069,7 @@ int ebitmap_add_tests(CU_pSuite suite)
ADD_TEST(ebitmap_init_destroy);
ADD_TEST(ebitmap_cmp);
ADD_TEST(ebitmap_set_and_get);
+ ADD_TEST(ebitmap_init_range);
ADD_TEST(ebitmap_or);
ADD_TEST(ebitmap_and);
ADD_TEST(ebitmap_xor);
--
2.36.1
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH v2 3/7] libsepol/cil: use ebitmap_init_range
2022-07-19 15:30 [PATCH v2 1/7] libsepol/tests: add ebitmap tests Christian Göttsche
2022-07-19 15:30 ` [PATCH v2 2/7] libsepol: add ebitmap_init_range Christian Göttsche
@ 2022-07-19 15:30 ` Christian Göttsche
2022-07-19 15:30 ` [PATCH v2 4/7] libsepol: optimize ebitmap_not Christian Göttsche
` (4 subsequent siblings)
6 siblings, 0 replies; 9+ messages in thread
From: Christian Göttsche @ 2022-07-19 15:30 UTC (permalink / raw)
To: selinux; +Cc: Christian Göttsche
Especially in the case of __cil_permissionx_expr_range_to_bitmap_helper()
it substitutes hundreds of thousand of calls to ebitmap_set_bit() during
semodule(8) on a policy widely using extended permissions.
Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
libsepol/cil/src/cil_post.c | 30 +++++++++---------------------
1 file changed, 9 insertions(+), 21 deletions(-)
diff --git a/libsepol/cil/src/cil_post.c b/libsepol/cil/src/cil_post.c
index 714ce227..6e95225f 100644
--- a/libsepol/cil/src/cil_post.c
+++ b/libsepol/cil/src/cil_post.c
@@ -1191,7 +1191,6 @@ static int __cil_cat_expr_range_to_bitmap_helper(struct cil_list_item *i1, struc
struct cil_tree_node *n2 = d2->nodes->head->data;
struct cil_cat *c1 = (struct cil_cat *)d1;
struct cil_cat *c2 = (struct cil_cat *)d2;
- int i;
if (n1->flavor == CIL_CATSET || n2->flavor == CIL_CATSET) {
cil_log(CIL_ERR, "Category sets cannont be used in a category range\n");
@@ -1213,12 +1212,10 @@ static int __cil_cat_expr_range_to_bitmap_helper(struct cil_list_item *i1, struc
goto exit;
}
- for (i = c1->value; i <= c2->value; i++) {
- if (ebitmap_set_bit(bitmap, i, 1)) {
- cil_log(CIL_ERR, "Failed to set cat bit\n");
- ebitmap_destroy(bitmap);
- goto exit;
- }
+ if (ebitmap_init_range(bitmap, c1->value, c2->value)) {
+ cil_log(CIL_ERR, "Failed to set cat bit\n");
+ ebitmap_destroy(bitmap);
+ goto exit;
}
return SEPOL_OK;
@@ -1234,7 +1231,6 @@ static int __cil_permissionx_expr_range_to_bitmap_helper(struct cil_list_item *i
char *p2 = i2->data;
uint16_t v1;
uint16_t v2;
- uint32_t i;
rc = __cil_permx_str_to_int(p1, &v1);
if (rc != SEPOL_OK) {
@@ -1246,12 +1242,10 @@ static int __cil_permissionx_expr_range_to_bitmap_helper(struct cil_list_item *i
goto exit;
}
- for (i = v1; i <= v2; i++) {
- if (ebitmap_set_bit(bitmap, i, 1)) {
- cil_log(CIL_ERR, "Failed to set permissionx bit\n");
- ebitmap_destroy(bitmap);
- goto exit;
- }
+ if (ebitmap_init_range(bitmap, v1, v2)) {
+ cil_log(CIL_ERR, "Failed to set permissionx bits\n");
+ ebitmap_destroy(bitmap);
+ goto exit;
}
return SEPOL_OK;
@@ -1318,9 +1312,7 @@ static int __cil_expr_to_bitmap(struct cil_list *expr, ebitmap_t *out, int max,
enum cil_flavor op = (enum cil_flavor)(uintptr_t)curr->data;
if (op == CIL_ALL) {
- ebitmap_init(&b1); /* all zeros */
- rc = ebitmap_not(&tmp, &b1, max);
- ebitmap_destroy(&b1);
+ rc = ebitmap_init_range(&tmp, 0, max - 1);
if (rc != SEPOL_OK) {
cil_log(CIL_INFO, "Failed to expand 'all' operator\n");
ebitmap_destroy(&tmp);
@@ -1328,19 +1320,15 @@ static int __cil_expr_to_bitmap(struct cil_list *expr, ebitmap_t *out, int max,
}
} else if (op == CIL_RANGE) {
if (flavor == CIL_CAT) {
- ebitmap_init(&tmp);
rc = __cil_cat_expr_range_to_bitmap_helper(curr->next, curr->next->next, &tmp);
if (rc != SEPOL_OK) {
cil_log(CIL_INFO, "Failed to expand category range\n");
- ebitmap_destroy(&tmp);
goto exit;
}
} else if (flavor == CIL_PERMISSIONX) {
- ebitmap_init(&tmp);
rc = __cil_permissionx_expr_range_to_bitmap_helper(curr->next, curr->next->next, &tmp);
if (rc != SEPOL_OK) {
cil_log(CIL_INFO, "Failed to expand category range\n");
- ebitmap_destroy(&tmp);
goto exit;
}
} else {
--
2.36.1
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH v2 4/7] libsepol: optimize ebitmap_not
2022-07-19 15:30 [PATCH v2 1/7] libsepol/tests: add ebitmap tests Christian Göttsche
2022-07-19 15:30 ` [PATCH v2 2/7] libsepol: add ebitmap_init_range Christian Göttsche
2022-07-19 15:30 ` [PATCH v2 3/7] libsepol/cil: use ebitmap_init_range Christian Göttsche
@ 2022-07-19 15:30 ` Christian Göttsche
2022-07-19 15:30 ` [PATCH v2 5/7] libsepol: optimize ebitmap_and Christian Göttsche
` (3 subsequent siblings)
6 siblings, 0 replies; 9+ messages in thread
From: Christian Göttsche @ 2022-07-19 15:30 UTC (permalink / raw)
To: selinux; +Cc: Christian Göttsche
Iterate on nodes instead of single bits to save node resolution for each
single bit.
Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
libsepol/src/ebitmap.c | 48 ++++++++++++++++++++++++++++++++++++------
1 file changed, 42 insertions(+), 6 deletions(-)
diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c
index 0f9afd62..c9164c5e 100644
--- a/libsepol/src/ebitmap.c
+++ b/libsepol/src/ebitmap.c
@@ -101,14 +101,50 @@ int ebitmap_xor(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
int ebitmap_not(ebitmap_t *dst, const ebitmap_t *e1, unsigned int maxbit)
{
- unsigned int i;
+ const ebitmap_node_t *n;
+ ebitmap_node_t *new, *prev = NULL;
+ uint32_t startbit, cur_startbit;
+ MAPTYPE map;
+
ebitmap_init(dst);
- for (i=0; i < maxbit; i++) {
- int val = ebitmap_get_bit(e1, i);
- int rc = ebitmap_set_bit(dst, i, !val);
- if (rc < 0)
- return rc;
+
+ n = e1->node;
+ for (cur_startbit = 0; cur_startbit < maxbit; cur_startbit += MAPSIZE) {
+ if (n && n->startbit == cur_startbit) {
+ startbit = n->startbit;
+ map = ~n->map;
+
+ n = n->next;
+ } else {
+ startbit = cur_startbit;
+ map = ~((MAPTYPE) 0);
+ }
+
+ if (maxbit - cur_startbit < MAPSIZE)
+ map &= (((MAPTYPE)1) << (maxbit - cur_startbit)) - 1;
+
+ if (map != 0) {
+ new = malloc(sizeof(ebitmap_node_t));
+ if (!new) {
+ ebitmap_destroy(dst);
+ return -ENOMEM;
+ }
+
+ new->startbit = startbit;
+ new->map = map;
+ new->next = NULL;
+
+ if (prev)
+ prev->next = new;
+ else
+ dst->node = new;
+ prev = new;
+ }
}
+
+ if (prev)
+ dst->highbit = prev->startbit + MAPSIZE;
+
return 0;
}
--
2.36.1
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH v2 5/7] libsepol: optimize ebitmap_and
2022-07-19 15:30 [PATCH v2 1/7] libsepol/tests: add ebitmap tests Christian Göttsche
` (2 preceding siblings ...)
2022-07-19 15:30 ` [PATCH v2 4/7] libsepol: optimize ebitmap_not Christian Göttsche
@ 2022-07-19 15:30 ` Christian Göttsche
2022-07-19 15:30 ` [PATCH v2 6/7] libsepol: optimize ebitmap_xor Christian Göttsche
` (2 subsequent siblings)
6 siblings, 0 replies; 9+ messages in thread
From: Christian Göttsche @ 2022-07-19 15:30 UTC (permalink / raw)
To: selinux; +Cc: Christian Göttsche
Iterate on nodes instead of single bits to save node resolution for each
single bit.
Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
v2:
use braces for all if-else branches when used for at least one of them
---
libsepol/src/ebitmap.c | 41 +++++++++++++++++++++++++++++++++++------
1 file changed, 35 insertions(+), 6 deletions(-)
diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c
index c9164c5e..6dbbddfd 100644
--- a/libsepol/src/ebitmap.c
+++ b/libsepol/src/ebitmap.c
@@ -74,15 +74,44 @@ int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1)
int ebitmap_and(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
{
- unsigned int i, length = min(ebitmap_length(e1), ebitmap_length(e2));
+ const ebitmap_node_t *n1, *n2;
+ ebitmap_node_t *new, *prev = NULL;
+
ebitmap_init(dst);
- for (i=0; i < length; i++) {
- if (ebitmap_get_bit(e1, i) && ebitmap_get_bit(e2, i)) {
- int rc = ebitmap_set_bit(dst, i, 1);
- if (rc < 0)
- return rc;
+
+ n1 = e1->node;
+ n2 = e2->node;
+ while (n1 && n2) {
+ if (n1->startbit == n2->startbit) {
+ if (n1->map & n2->map) {
+ new = malloc(sizeof(ebitmap_node_t));
+ if (!new) {
+ ebitmap_destroy(dst);
+ return -ENOMEM;
+ }
+ new->startbit = n1->startbit;
+ new->map = n1->map & n2->map;
+ new->next = NULL;
+
+ if (prev)
+ prev->next = new;
+ else
+ dst->node = new;
+ prev = new;
+ }
+
+ n1 = n1->next;
+ n2 = n2->next;
+ } else if (n1->startbit > n2->startbit) {
+ n2 = n2->next;
+ } else {
+ n1 = n1->next;
}
}
+
+ if (prev)
+ dst->highbit = prev->startbit + MAPSIZE;
+
return 0;
}
--
2.36.1
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH v2 6/7] libsepol: optimize ebitmap_xor
2022-07-19 15:30 [PATCH v2 1/7] libsepol/tests: add ebitmap tests Christian Göttsche
` (3 preceding siblings ...)
2022-07-19 15:30 ` [PATCH v2 5/7] libsepol: optimize ebitmap_and Christian Göttsche
@ 2022-07-19 15:30 ` Christian Göttsche
2022-07-19 15:30 ` [PATCH v2 7/7] libsepol: skip superfluous memset calls in ebitmap operations Christian Göttsche
2022-07-20 19:51 ` [PATCH v2 1/7] libsepol/tests: add ebitmap tests James Carter
6 siblings, 0 replies; 9+ messages in thread
From: Christian Göttsche @ 2022-07-19 15:30 UTC (permalink / raw)
To: selinux; +Cc: Christian Göttsche
Iterate on nodes instead of single bits to save node resolution for each
single bit.
Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
libsepol/src/ebitmap.c | 49 ++++++++++++++++++++++++++++++++++++------
1 file changed, 43 insertions(+), 6 deletions(-)
diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c
index 6dbbddfd..7d26f949 100644
--- a/libsepol/src/ebitmap.c
+++ b/libsepol/src/ebitmap.c
@@ -117,14 +117,51 @@ int ebitmap_and(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
int ebitmap_xor(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
{
- unsigned int i, length = max(ebitmap_length(e1), ebitmap_length(e2));
+ const ebitmap_node_t *n1, *n2;
+ ebitmap_node_t *new, *prev = NULL;
+ uint32_t startbit;
+ MAPTYPE map;
+
ebitmap_init(dst);
- for (i=0; i < length; i++) {
- int val = ebitmap_get_bit(e1, i) ^ ebitmap_get_bit(e2, i);
- int rc = ebitmap_set_bit(dst, i, val);
- if (rc < 0)
- return rc;
+
+ n1 = e1->node;
+ n2 = e2->node;
+ while (n1 || n2) {
+ if (n1 && n2 && n1->startbit == n2->startbit) {
+ startbit = n1->startbit;
+ map = n1->map ^ n2->map;
+ n1 = n1->next;
+ n2 = n2->next;
+ } else if (!n2 || (n1 && n1->startbit < n2->startbit)) {
+ startbit = n1->startbit;
+ map = n1->map;
+ n1 = n1->next;
+ } else {
+ startbit = n2->startbit;
+ map = n2->map;
+ n2 = n2->next;
+ }
+
+ if (map != 0) {
+ new = malloc(sizeof(ebitmap_node_t));
+ if (!new) {
+ ebitmap_destroy(dst);
+ return -ENOMEM;
+ }
+ new->startbit = startbit;
+ new->map = map;
+ new->next = NULL;
+ if (prev)
+ prev->next = new;
+ else
+ dst->node = new;
+ prev = new;
+ }
}
+
+ if (prev)
+ dst->highbit = prev->startbit + MAPSIZE;
+
return 0;
}
--
2.36.1
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH v2 7/7] libsepol: skip superfluous memset calls in ebitmap operations
2022-07-19 15:30 [PATCH v2 1/7] libsepol/tests: add ebitmap tests Christian Göttsche
` (4 preceding siblings ...)
2022-07-19 15:30 ` [PATCH v2 6/7] libsepol: optimize ebitmap_xor Christian Göttsche
@ 2022-07-19 15:30 ` Christian Göttsche
2022-07-20 19:51 ` [PATCH v2 1/7] libsepol/tests: add ebitmap tests James Carter
6 siblings, 0 replies; 9+ messages in thread
From: Christian Göttsche @ 2022-07-19 15:30 UTC (permalink / raw)
To: selinux; +Cc: Christian Göttsche
The three members of struct ebitmap_node are all unconditionally
initialized. Hinder compilers to optimize malloc() and memset() into
calloc(), which might be slightly slower. Especially affects
ebitmap_or().
Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
libsepol/src/ebitmap.c | 3 ---
1 file changed, 3 deletions(-)
diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c
index 7d26f949..3ec1042f 100644
--- a/libsepol/src/ebitmap.c
+++ b/libsepol/src/ebitmap.c
@@ -31,7 +31,6 @@ int ebitmap_or(ebitmap_t * dst, const ebitmap_t * e1, const ebitmap_t * e2)
ebitmap_destroy(dst);
return -ENOMEM;
}
- memset(new, 0, sizeof(ebitmap_node_t));
if (n1 && n2 && n1->startbit == n2->startbit) {
new->startbit = n1->startbit;
new->map = n1->map | n2->map;
@@ -290,7 +289,6 @@ int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src)
ebitmap_destroy(dst);
return -ENOMEM;
}
- memset(new, 0, sizeof(ebitmap_node_t));
new->startbit = n->startbit;
new->map = n->map;
new->next = 0;
@@ -430,7 +428,6 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
if (!new)
return -ENOMEM;
- memset(new, 0, sizeof(ebitmap_node_t));
new->startbit = startbit;
new->map = (MAPBIT << (bit - new->startbit));
--
2.36.1
^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH v2 1/7] libsepol/tests: add ebitmap tests
2022-07-19 15:30 [PATCH v2 1/7] libsepol/tests: add ebitmap tests Christian Göttsche
` (5 preceding siblings ...)
2022-07-19 15:30 ` [PATCH v2 7/7] libsepol: skip superfluous memset calls in ebitmap operations Christian Göttsche
@ 2022-07-20 19:51 ` James Carter
2022-08-09 15:19 ` James Carter
6 siblings, 1 reply; 9+ messages in thread
From: James Carter @ 2022-07-20 19:51 UTC (permalink / raw)
To: Christian Göttsche; +Cc: SElinux list
On Tue, Jul 19, 2022 at 11:34 AM Christian Göttsche
<cgzones@googlemail.com> wrote:
>
> Preparation for several ebitmap related optimizations.
>
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
For this series:
Acked-by: James Carter <jwcart2@gmail.com>
> ---
> v2:
> - add more tests for multi node ebitmaps and for bits set at node
> bounds
> - test ebitmap_for_each_bit()
> ---
> libsepol/tests/libsepol-tests.c | 2 +
> libsepol/tests/test-ebitmap.c | 1048 +++++++++++++++++++++++++++++++
> libsepol/tests/test-ebitmap.h | 10 +
> 3 files changed, 1060 insertions(+)
> create mode 100644 libsepol/tests/test-ebitmap.c
> create mode 100644 libsepol/tests/test-ebitmap.h
>
> diff --git a/libsepol/tests/libsepol-tests.c b/libsepol/tests/libsepol-tests.c
> index dc8fd5ce..5ae6bedc 100644
> --- a/libsepol/tests/libsepol-tests.c
> +++ b/libsepol/tests/libsepol-tests.c
> @@ -19,6 +19,7 @@
> */
>
> #include "test-cond.h"
> +#include "test-ebitmap.h"
> #include "test-linker.h"
> #include "test-expander.h"
> #include "test-deps.h"
> @@ -64,6 +65,7 @@ static bool do_tests(int interactive, int verbose)
> if (CUE_SUCCESS != CU_initialize_registry())
> return CU_get_error();
>
> + DECLARE_SUITE(ebitmap);
> DECLARE_SUITE(cond);
> DECLARE_SUITE(linker);
> DECLARE_SUITE(expander);
> diff --git a/libsepol/tests/test-ebitmap.c b/libsepol/tests/test-ebitmap.c
> new file mode 100644
> index 00000000..fad5bd75
> --- /dev/null
> +++ b/libsepol/tests/test-ebitmap.c
> @@ -0,0 +1,1048 @@
> +#include "test-ebitmap.h"
> +
> +#include <stdlib.h>
> +#include <time.h>
> +
> +#include <sepol/debug.h>
> +#include <sepol/policydb/ebitmap.h>
> +
> +#define RANDOM_ROUNDS 10
> +
> +
> +static int ebitmap_init_random(ebitmap_t *e, unsigned int length, int set_chance)
> +{
> + unsigned int i;
> + int rc;
> +
> + if (set_chance <= 0 || set_chance > 100)
> + return -EINVAL;
> +
> + ebitmap_init(e);
> +
> + for (i = 0; i < length; i++) {
> + if ((random() % 100) < set_chance) {
> + rc = ebitmap_set_bit(e, i, 1);
> + if (rc)
> + return rc;
> + }
> + }
> +
> + return 0;
> +}
> +
> +static void test_ebitmap_init_destroy(void)
> +{
> + ebitmap_t e;
> +
> + /* verify idempotence */
> + ebitmap_init(&e);
> + ebitmap_init(&e);
> + ebitmap_init(&e);
> +
> + CU_ASSERT(ebitmap_is_empty(&e));
> + CU_ASSERT_PTR_NULL(ebitmap_startnode(&e));
> +
> + /* verify idempotence */
> + ebitmap_destroy(&e);
> + ebitmap_destroy(&e);
> + ebitmap_destroy(&e);
> +
> + CU_ASSERT(ebitmap_is_empty(&e));
> + CU_ASSERT_PTR_NULL(ebitmap_startnode(&e));
> +}
> +
> +static void test_ebitmap_cmp(void)
> +{
> + ebitmap_t e1, e2;
> +
> + ebitmap_init(&e1);
> + ebitmap_init(&e2);
> +
> + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 10, 1), 0);
> + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 63, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 63, 1), 0);
> + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 64, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 64, 1), 0);
> + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1022, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1022, 1), 0);
> + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1023, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1023, 1), 0);
> + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1024, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1024, 1), 0);
> + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1025, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1025, 1), 0);
> + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 255, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 255, 1), 0);
> + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 256, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 256, 1), 0);
> + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 639, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 639, 1), 0);
> + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 640, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 640, 1), 0);
> + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 900, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 900, 1), 0);
> + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> +
> + ebitmap_destroy(&e2);
> +
> + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> +
> + ebitmap_destroy(&e1);
> +
> + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> +}
> +
> +static void test_ebitmap_set_and_get(void)
> +{
> + ebitmap_t e;
> +
> + ebitmap_init(&e);
> +
> + CU_ASSERT(ebitmap_is_empty(&e));
> + CU_ASSERT_TRUE(ebitmap_is_empty(&e));
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 0);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 0);
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, UINT32_MAX, 1), -EINVAL);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 10, 0), 0);
> + CU_ASSERT(ebitmap_is_empty(&e));
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 0);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 0);
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 10, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 1);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 10);
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 1);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 100, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 2);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 100);
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 100), 1);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 50, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 3);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 100);
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 50), 1);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1023, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 4);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023);
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1023), 1);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1024, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 5);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1024);
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1024), 1);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1050, 1), 0);
> + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 6);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1050);
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1050), 1);
> +
> + {
> + ebitmap_node_t *n;
> + unsigned int bit, count;
> +
> + /* iterate all allocated bits */
> + count = 0;
> + ebitmap_for_each_bit(&e, n, bit) {
> + CU_ASSERT( bit < 64 ||
> + (64 <= bit && bit < 128) ||
> + (960 <= bit && bit < 1024) ||
> + (1024 <= bit && bit < 1088));
> + count++;
> + }
> + CU_ASSERT_EQUAL(count, 4 * 64);
> +
> + count = 0;
> + ebitmap_for_each_positive_bit(&e, n, bit) {
> + CU_ASSERT(bit == 10 ||
> + bit == 50 ||
> + bit == 100 ||
> + bit == 1023 ||
> + bit == 1024 ||
> + bit == 1050);
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, bit), 1);
> + count++;
> + }
> + CU_ASSERT_EQUAL(count, 6);
> + }
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1024, 0), 0);
> + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 5);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1050);
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1024), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1050, 0), 0);
> + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 4);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023);
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1050), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 100, 0), 0);
> + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 3);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023);
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 100), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 10, 0), 0);
> + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 2);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023);
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 50, 0), 0);
> + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 1);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023);
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 50), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1023, 0), 0);
> + CU_ASSERT_TRUE(ebitmap_is_empty(&e));
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 0);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 0);
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1023), 0);
> +
> + ebitmap_destroy(&e);
> +}
> +
> +static void test_ebitmap_or(void)
> +{
> + ebitmap_t e1, e2, e3, e4;
> +
> + ebitmap_init(&e1);
> + ebitmap_init(&e2);
> + ebitmap_init(&e3);
> + ebitmap_init(&e4);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 100, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 101, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 318, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 319, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 383, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 384, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 449, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1013, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 11, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 101, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 430, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 665, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 11, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 100, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 101, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 318, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 319, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 383, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 384, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 449, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 665, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 1013, 1), 0);
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_or(&dst, &e1, &e1), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e1));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_or(&dst, &e2, &e2), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e2));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_or(&dst, &e1, &e2), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e3));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_or(&dst, &e3, &e3), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e3));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_or(&dst, &e3, &e4), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e3));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_or(&dst, &e4, &e4), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + ebitmap_destroy(&e4);
> + ebitmap_destroy(&e3);
> + ebitmap_destroy(&e2);
> + ebitmap_destroy(&e1);
> +}
> +
> +static void test_ebitmap_and(void)
> +{
> + {
> + ebitmap_t e1, e2, e12, e3, e4;
> +
> + ebitmap_init(&e1);
> + ebitmap_init(&e2);
> + ebitmap_init(&e12);
> + ebitmap_init(&e3);
> + ebitmap_init(&e4);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 100, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 101, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 318, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 319, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 383, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 384, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 449, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1013, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 11, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 101, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 319, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 665, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 101, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 319, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 11, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 100, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 101, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 318, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 319, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 383, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 384, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 449, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 665, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 1013, 1), 0);
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e1, &e1), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e1));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e2, &e2), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e2));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e1, &e2), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e12));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e3, &e3), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e3));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e1, &e3), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e1));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e2, &e3), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e2));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e4, &e4), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e3, &e4), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + ebitmap_destroy(&e4);
> + ebitmap_destroy(&e3);
> + ebitmap_destroy(&e12);
> + ebitmap_destroy(&e2);
> + ebitmap_destroy(&e1);
> + }
> +
> + {
> + ebitmap_t e5;
> + ebitmap_t e6;
> + ebitmap_t e56;
> + ebitmap_t dst;
> +
> + ebitmap_init(&e5);
> + ebitmap_init(&e6);
> + ebitmap_init(&e56);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 64, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 192, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 319, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 320, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 192, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 319, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e5, &e6), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e56));
> +
> + ebitmap_destroy(&dst);
> + ebitmap_destroy(&e56);
> + ebitmap_destroy(&e6);
> + ebitmap_destroy(&e5);
> + }
> +}
> +
> +static void test_ebitmap_xor(void)
> +{
> + {
> + ebitmap_t e1, e2, e3, e4;
> +
> + ebitmap_init(&e1);
> + ebitmap_init(&e2);
> + ebitmap_init(&e3);
> + ebitmap_init(&e4);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 5, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 3, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 6, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 9, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 3, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 5, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 6, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 9, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
> +
> + {
> + ebitmap_t dst1, dst2;
> +
> + CU_ASSERT_EQUAL(ebitmap_xor(&dst1, &e1, &e1), 0);
> + CU_ASSERT(ebitmap_cmp(&dst1, &e4));
> + CU_ASSERT_EQUAL(ebitmap_xor(&dst2, &dst1, &e1), 0);
> + CU_ASSERT(ebitmap_cmp(&dst2, &e1));
> +
> + ebitmap_destroy(&dst2);
> + ebitmap_destroy(&dst1);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e2, &e2), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e3, &e3), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e4, &e4), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e1, &e2), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e3));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e2, &e4), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e2));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + ebitmap_destroy(&e4);
> + ebitmap_destroy(&e3);
> + ebitmap_destroy(&e2);
> + ebitmap_destroy(&e1);
> + }
> +
> + {
> + ebitmap_t e5;
> + ebitmap_t e6;
> + ebitmap_t e56;
> + ebitmap_t dst;
> +
> + ebitmap_init(&e5);
> + ebitmap_init(&e6);
> + ebitmap_init(&e56);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 64, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 192, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 319, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 320, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 63, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 64, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 191, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 318, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 320, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e5, &e6), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e56));
> +
> + ebitmap_destroy(&dst);
> + ebitmap_destroy(&e56);
> + ebitmap_destroy(&e6);
> + ebitmap_destroy(&e5);
> + }
> +}
> +
> +static void test_ebitmap_not(void)
> +{
> + {
> + ebitmap_t e1, e2, e3, e4;
> +
> + ebitmap_init(&e1);
> + ebitmap_init(&e2);
> + ebitmap_init(&e3);
> + ebitmap_init(&e4);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 0, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 5, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 2, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 3, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 4, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 6, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 7, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 8, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 9, 1), 0);
> +
> + {
> + ebitmap_t dst1, dst2;
> +
> + CU_ASSERT_EQUAL(ebitmap_not(&dst1, &e3, 10), 0);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&dst1), 9);
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&dst1), 10);
> +
> + CU_ASSERT_EQUAL(ebitmap_not(&dst2, &dst1, 10), 0);
> + CU_ASSERT(ebitmap_cmp(&dst2, &e3));
> +
> + ebitmap_destroy(&dst2);
> + ebitmap_destroy(&dst1);
> + }
> +
> + {
> + ebitmap_t dst1, dst2;
> +
> + CU_ASSERT_EQUAL(ebitmap_not(&dst1, &e1, 11), 0);
> + CU_ASSERT(ebitmap_cmp(&dst1, &e2));
> + CU_ASSERT_EQUAL(ebitmap_not(&dst2, &dst1, 11), 0);
> + CU_ASSERT(ebitmap_cmp(&dst2, &e1));
> +
> + ebitmap_destroy(&dst2);
> + ebitmap_destroy(&dst1);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_not(&dst, &e1, 8), 0);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&dst), 7);
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&dst), 5);
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_not(&dst, &e1, 12), 0);
> + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&dst), 11);
> + CU_ASSERT_EQUAL(ebitmap_cardinality(&dst), 8);
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + ebitmap_destroy(&e3);
> + ebitmap_destroy(&e2);
> + ebitmap_destroy(&e1);
> + }
> +
> + {
> + ebitmap_t e5;
> + ebitmap_t e5not;
> + ebitmap_node_t *n;
> + unsigned int bit;
> +
> + ebitmap_init(&e5);
> + ebitmap_init(&e5not);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0);
> +
> + for (bit = 0; bit < 317; bit++)
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5not, bit, 1), 0);
> + ebitmap_for_each_positive_bit(&e5, n, bit)
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5not, bit, 0), 0);
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_not(&dst, &e5, 317), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e5not));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_not(&dst, &e5, 318), 0);
> + CU_ASSERT_FALSE(ebitmap_cmp(&dst, &e5not));
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5not, 317, 1), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e5not));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_not(&dst, &e5, 319), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e5not));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + ebitmap_destroy(&e5not);
> + ebitmap_destroy(&e5);
> + }
> +}
> +
> +static void test_ebitmap_andnot(void)
> +{
> + {
> + ebitmap_t e1, e2, e12, e3, e4;
> +
> + ebitmap_init(&e1);
> + ebitmap_init(&e2);
> + ebitmap_init(&e12);
> + ebitmap_init(&e3);
> + ebitmap_init(&e4);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 100, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 101, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 430, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1013, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 11, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 101, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 665, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 10, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 100, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 430, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 1013, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 11, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 100, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 101, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 665, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 1013, 1), 0);
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e1, &e1, 1024), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e2, &e2, 1024), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e1, &e2, 1024), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e12));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e3, &e3, 1024), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e1, &e3, 1024), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e2, &e12, 1024), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e2));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e4, &e4, 1024), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e3, &e4, 1024), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e3));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + ebitmap_destroy(&e4);
> + ebitmap_destroy(&e3);
> + ebitmap_destroy(&e12);
> + ebitmap_destroy(&e2);
> + ebitmap_destroy(&e1);
> + }
> +
> + {
> + ebitmap_t e5;
> + ebitmap_t e6;
> + ebitmap_t e56;
> +
> + ebitmap_init(&e5);
> + ebitmap_init(&e6);
> + ebitmap_init(&e56);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 64, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 192, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 319, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 320, 1), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 63, 1), 0);
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 191, 1), 0);
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 317), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e56));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 318), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e56));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 319), 0);
> + CU_ASSERT_FALSE(ebitmap_cmp(&dst, &e56));
> +
> + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 318, 1), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e56));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + {
> + ebitmap_t dst;
> +
> + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 320), 0);
> + CU_ASSERT(ebitmap_cmp(&dst, &e56));
> +
> + ebitmap_destroy(&dst);
> + }
> +
> + ebitmap_destroy(&e56);
> + ebitmap_destroy(&e6);
> + ebitmap_destroy(&e5);
> + }
> +}
> +
> +static void test_ebitmap__random_impl(unsigned int length, int set_chance)
> +{
> + ebitmap_t e1, e2, dst_cpy, dst_or, dst_and, dst_xor1, dst_xor2, dst_not1, dst_not2, dst_andnot;
> + unsigned int i;
> +
> + CU_ASSERT_EQUAL(ebitmap_init_random(&e1, length, set_chance), 0);
> + CU_ASSERT_EQUAL(ebitmap_init_random(&e2, length, set_chance), 0);
> +
> + CU_ASSERT_EQUAL(ebitmap_cpy(&dst_cpy, &e1), 0);
> + CU_ASSERT(ebitmap_cmp(&dst_cpy, &e1));
> +
> + CU_ASSERT_EQUAL(ebitmap_or(&dst_or, &e1, &e2), 0);
> + for (i = 0; i < length; i++)
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_or, i), ebitmap_get_bit(&e1, i) | ebitmap_get_bit(&e2, i));
> +
> + CU_ASSERT_EQUAL(ebitmap_and(&dst_and, &e1, &e2), 0);
> + for (i = 0; i < length; i++)
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_and, i), ebitmap_get_bit(&e1, i) & ebitmap_get_bit(&e2, i));
> +
> + CU_ASSERT_EQUAL(ebitmap_xor(&dst_xor1, &e1, &e2), 0);
> + for (i = 0; i < length; i++)
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_xor1, i), ebitmap_get_bit(&e1, i) ^ ebitmap_get_bit(&e2, i));
> + CU_ASSERT_EQUAL(ebitmap_xor(&dst_xor2, &dst_xor1, &e2), 0);
> + CU_ASSERT(ebitmap_cmp(&dst_xor2, &e1));
> +
> + CU_ASSERT_EQUAL(ebitmap_not(&dst_not1, &e1, length), 0);
> + for (i = 0; i < length; i++)
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_not1, i), !ebitmap_get_bit(&e1, i));
> + CU_ASSERT_EQUAL(ebitmap_not(&dst_not2, &dst_not1, length), 0);
> + CU_ASSERT(ebitmap_cmp(&dst_not2, &e1));
> +
> + CU_ASSERT_EQUAL(ebitmap_andnot(&dst_andnot, &e1, &e2, length), 0);
> + for (i = 0; i < length; i++)
> + CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_andnot, i), ebitmap_get_bit(&e1, i) & !ebitmap_get_bit(&e2, i));
> +
> + ebitmap_destroy(&dst_andnot);
> + ebitmap_destroy(&dst_not2);
> + ebitmap_destroy(&dst_not1);
> + ebitmap_destroy(&dst_xor2);
> + ebitmap_destroy(&dst_xor1);
> + ebitmap_destroy(&dst_and);
> + ebitmap_destroy(&dst_or);
> + ebitmap_destroy(&dst_cpy);
> + ebitmap_destroy(&e2);
> + ebitmap_destroy(&e1);
> +}
> +
> +static void test_ebitmap__random(void)
> +{
> + unsigned int i;
> +
> + for (i = 0; i < RANDOM_ROUNDS; i++)
> + test_ebitmap__random_impl(5, 10);
> +
> + for (i = 0; i < RANDOM_ROUNDS; i++)
> + test_ebitmap__random_impl(5, 90);
> +
> + for (i = 0; i < RANDOM_ROUNDS; i++)
> + test_ebitmap__random_impl(1024, 50);
> +
> + for (i = 0; i < RANDOM_ROUNDS; i++)
> + test_ebitmap__random_impl(8000, 5);
> +
> + for (i = 0; i < RANDOM_ROUNDS; i++)
> + test_ebitmap__random_impl(8000, 95);
> +}
> +
> +/*
> + * External hooks
> + */
> +
> +int ebitmap_test_init(void)
> +{
> + srandom(time(NULL));
> +
> + /* silence ebitmap_set_bit() failure message */
> + sepol_debug(0);
> +
> + return 0;
> +}
> +
> +int ebitmap_test_cleanup(void)
> +{
> + return 0;
> +}
> +
> +#define ADD_TEST(name) \
> + do { \
> + if (NULL == CU_add_test(suite, #name, test_##name)) { \
> + return CU_get_error(); \
> + } \
> + } while (0)
> +
> +int ebitmap_add_tests(CU_pSuite suite)
> +{
> + ADD_TEST(ebitmap_init_destroy);
> + ADD_TEST(ebitmap_cmp);
> + ADD_TEST(ebitmap_set_and_get);
> + ADD_TEST(ebitmap_or);
> + ADD_TEST(ebitmap_and);
> + ADD_TEST(ebitmap_xor);
> + ADD_TEST(ebitmap_not);
> + ADD_TEST(ebitmap_andnot);
> + ADD_TEST(ebitmap__random);
> + return 0;
> +}
> diff --git a/libsepol/tests/test-ebitmap.h b/libsepol/tests/test-ebitmap.h
> new file mode 100644
> index 00000000..952a0421
> --- /dev/null
> +++ b/libsepol/tests/test-ebitmap.h
> @@ -0,0 +1,10 @@
> +#ifndef TEST_EBITMAP_H__
> +#define TEST_EBITMAP_H__
> +
> +#include <CUnit/Basic.h>
> +
> +int ebitmap_test_init(void);
> +int ebitmap_test_cleanup(void);
> +int ebitmap_add_tests(CU_pSuite suite);
> +
> +#endif /* TEST_EBITMAP_H__ */
> --
> 2.36.1
>
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH v2 1/7] libsepol/tests: add ebitmap tests
2022-07-20 19:51 ` [PATCH v2 1/7] libsepol/tests: add ebitmap tests James Carter
@ 2022-08-09 15:19 ` James Carter
0 siblings, 0 replies; 9+ messages in thread
From: James Carter @ 2022-08-09 15:19 UTC (permalink / raw)
To: Christian Göttsche; +Cc: SElinux list
On Wed, Jul 20, 2022 at 3:51 PM James Carter <jwcart2@gmail.com> wrote:
>
> On Tue, Jul 19, 2022 at 11:34 AM Christian Göttsche
> <cgzones@googlemail.com> wrote:
> >
> > Preparation for several ebitmap related optimizations.
> >
> > Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
>
> For this series:
> Acked-by: James Carter <jwcart2@gmail.com>
>
This series has been merged.
Thanks,
Jim
> > ---
> > v2:
> > - add more tests for multi node ebitmaps and for bits set at node
> > bounds
> > - test ebitmap_for_each_bit()
> > ---
> > libsepol/tests/libsepol-tests.c | 2 +
> > libsepol/tests/test-ebitmap.c | 1048 +++++++++++++++++++++++++++++++
> > libsepol/tests/test-ebitmap.h | 10 +
> > 3 files changed, 1060 insertions(+)
> > create mode 100644 libsepol/tests/test-ebitmap.c
> > create mode 100644 libsepol/tests/test-ebitmap.h
> >
> > diff --git a/libsepol/tests/libsepol-tests.c b/libsepol/tests/libsepol-tests.c
> > index dc8fd5ce..5ae6bedc 100644
> > --- a/libsepol/tests/libsepol-tests.c
> > +++ b/libsepol/tests/libsepol-tests.c
> > @@ -19,6 +19,7 @@
> > */
> >
> > #include "test-cond.h"
> > +#include "test-ebitmap.h"
> > #include "test-linker.h"
> > #include "test-expander.h"
> > #include "test-deps.h"
> > @@ -64,6 +65,7 @@ static bool do_tests(int interactive, int verbose)
> > if (CUE_SUCCESS != CU_initialize_registry())
> > return CU_get_error();
> >
> > + DECLARE_SUITE(ebitmap);
> > DECLARE_SUITE(cond);
> > DECLARE_SUITE(linker);
> > DECLARE_SUITE(expander);
> > diff --git a/libsepol/tests/test-ebitmap.c b/libsepol/tests/test-ebitmap.c
> > new file mode 100644
> > index 00000000..fad5bd75
> > --- /dev/null
> > +++ b/libsepol/tests/test-ebitmap.c
> > @@ -0,0 +1,1048 @@
> > +#include "test-ebitmap.h"
> > +
> > +#include <stdlib.h>
> > +#include <time.h>
> > +
> > +#include <sepol/debug.h>
> > +#include <sepol/policydb/ebitmap.h>
> > +
> > +#define RANDOM_ROUNDS 10
> > +
> > +
> > +static int ebitmap_init_random(ebitmap_t *e, unsigned int length, int set_chance)
> > +{
> > + unsigned int i;
> > + int rc;
> > +
> > + if (set_chance <= 0 || set_chance > 100)
> > + return -EINVAL;
> > +
> > + ebitmap_init(e);
> > +
> > + for (i = 0; i < length; i++) {
> > + if ((random() % 100) < set_chance) {
> > + rc = ebitmap_set_bit(e, i, 1);
> > + if (rc)
> > + return rc;
> > + }
> > + }
> > +
> > + return 0;
> > +}
> > +
> > +static void test_ebitmap_init_destroy(void)
> > +{
> > + ebitmap_t e;
> > +
> > + /* verify idempotence */
> > + ebitmap_init(&e);
> > + ebitmap_init(&e);
> > + ebitmap_init(&e);
> > +
> > + CU_ASSERT(ebitmap_is_empty(&e));
> > + CU_ASSERT_PTR_NULL(ebitmap_startnode(&e));
> > +
> > + /* verify idempotence */
> > + ebitmap_destroy(&e);
> > + ebitmap_destroy(&e);
> > + ebitmap_destroy(&e);
> > +
> > + CU_ASSERT(ebitmap_is_empty(&e));
> > + CU_ASSERT_PTR_NULL(ebitmap_startnode(&e));
> > +}
> > +
> > +static void test_ebitmap_cmp(void)
> > +{
> > + ebitmap_t e1, e2;
> > +
> > + ebitmap_init(&e1);
> > + ebitmap_init(&e2);
> > +
> > + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 10, 1), 0);
> > + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 63, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 63, 1), 0);
> > + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 64, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 64, 1), 0);
> > + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1022, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1022, 1), 0);
> > + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1023, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1023, 1), 0);
> > + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1024, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1024, 1), 0);
> > + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1025, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1025, 1), 0);
> > + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 255, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 255, 1), 0);
> > + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 256, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 256, 1), 0);
> > + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 639, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 639, 1), 0);
> > + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 640, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 640, 1), 0);
> > + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 900, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 900, 1), 0);
> > + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> > +
> > + ebitmap_destroy(&e2);
> > +
> > + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
> > +
> > + ebitmap_destroy(&e1);
> > +
> > + CU_ASSERT(ebitmap_cmp(&e1, &e2));
> > +}
> > +
> > +static void test_ebitmap_set_and_get(void)
> > +{
> > + ebitmap_t e;
> > +
> > + ebitmap_init(&e);
> > +
> > + CU_ASSERT(ebitmap_is_empty(&e));
> > + CU_ASSERT_TRUE(ebitmap_is_empty(&e));
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 0);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 0);
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, UINT32_MAX, 1), -EINVAL);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 10, 0), 0);
> > + CU_ASSERT(ebitmap_is_empty(&e));
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 0);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 0);
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 10, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 1);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 10);
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 1);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 100, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 2);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 100);
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 100), 1);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 50, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 3);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 100);
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 50), 1);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1023, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 4);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023);
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1023), 1);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1024, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 5);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1024);
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1024), 1);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1050, 1), 0);
> > + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 6);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1050);
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1050), 1);
> > +
> > + {
> > + ebitmap_node_t *n;
> > + unsigned int bit, count;
> > +
> > + /* iterate all allocated bits */
> > + count = 0;
> > + ebitmap_for_each_bit(&e, n, bit) {
> > + CU_ASSERT( bit < 64 ||
> > + (64 <= bit && bit < 128) ||
> > + (960 <= bit && bit < 1024) ||
> > + (1024 <= bit && bit < 1088));
> > + count++;
> > + }
> > + CU_ASSERT_EQUAL(count, 4 * 64);
> > +
> > + count = 0;
> > + ebitmap_for_each_positive_bit(&e, n, bit) {
> > + CU_ASSERT(bit == 10 ||
> > + bit == 50 ||
> > + bit == 100 ||
> > + bit == 1023 ||
> > + bit == 1024 ||
> > + bit == 1050);
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, bit), 1);
> > + count++;
> > + }
> > + CU_ASSERT_EQUAL(count, 6);
> > + }
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1024, 0), 0);
> > + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 5);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1050);
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1024), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1050, 0), 0);
> > + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 4);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023);
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1050), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 100, 0), 0);
> > + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 3);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023);
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 100), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 10, 0), 0);
> > + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 2);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023);
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 50, 0), 0);
> > + CU_ASSERT_FALSE(ebitmap_is_empty(&e));
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 1);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023);
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 50), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1023, 0), 0);
> > + CU_ASSERT_TRUE(ebitmap_is_empty(&e));
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 0);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 0);
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1023), 0);
> > +
> > + ebitmap_destroy(&e);
> > +}
> > +
> > +static void test_ebitmap_or(void)
> > +{
> > + ebitmap_t e1, e2, e3, e4;
> > +
> > + ebitmap_init(&e1);
> > + ebitmap_init(&e2);
> > + ebitmap_init(&e3);
> > + ebitmap_init(&e4);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 100, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 101, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 318, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 319, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 383, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 384, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 449, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1013, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 11, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 101, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 430, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 665, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 11, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 100, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 101, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 318, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 319, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 383, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 384, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 449, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 665, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 1013, 1), 0);
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_or(&dst, &e1, &e1), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e1));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_or(&dst, &e2, &e2), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e2));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_or(&dst, &e1, &e2), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e3));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_or(&dst, &e3, &e3), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e3));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_or(&dst, &e3, &e4), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e3));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_or(&dst, &e4, &e4), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + ebitmap_destroy(&e4);
> > + ebitmap_destroy(&e3);
> > + ebitmap_destroy(&e2);
> > + ebitmap_destroy(&e1);
> > +}
> > +
> > +static void test_ebitmap_and(void)
> > +{
> > + {
> > + ebitmap_t e1, e2, e12, e3, e4;
> > +
> > + ebitmap_init(&e1);
> > + ebitmap_init(&e2);
> > + ebitmap_init(&e12);
> > + ebitmap_init(&e3);
> > + ebitmap_init(&e4);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 100, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 101, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 318, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 319, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 383, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 384, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 449, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1013, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 11, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 101, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 319, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 665, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 101, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 319, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 11, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 100, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 101, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 318, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 319, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 383, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 384, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 449, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 665, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 1013, 1), 0);
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e1, &e1), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e1));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e2, &e2), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e2));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e1, &e2), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e12));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e3, &e3), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e3));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e1, &e3), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e1));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e2, &e3), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e2));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e4, &e4), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e3, &e4), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + ebitmap_destroy(&e4);
> > + ebitmap_destroy(&e3);
> > + ebitmap_destroy(&e12);
> > + ebitmap_destroy(&e2);
> > + ebitmap_destroy(&e1);
> > + }
> > +
> > + {
> > + ebitmap_t e5;
> > + ebitmap_t e6;
> > + ebitmap_t e56;
> > + ebitmap_t dst;
> > +
> > + ebitmap_init(&e5);
> > + ebitmap_init(&e6);
> > + ebitmap_init(&e56);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 64, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 192, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 319, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 320, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 192, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 319, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e5, &e6), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e56));
> > +
> > + ebitmap_destroy(&dst);
> > + ebitmap_destroy(&e56);
> > + ebitmap_destroy(&e6);
> > + ebitmap_destroy(&e5);
> > + }
> > +}
> > +
> > +static void test_ebitmap_xor(void)
> > +{
> > + {
> > + ebitmap_t e1, e2, e3, e4;
> > +
> > + ebitmap_init(&e1);
> > + ebitmap_init(&e2);
> > + ebitmap_init(&e3);
> > + ebitmap_init(&e4);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 5, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 3, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 6, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 9, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 3, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 5, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 6, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 9, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
> > +
> > + {
> > + ebitmap_t dst1, dst2;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_xor(&dst1, &e1, &e1), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst1, &e4));
> > + CU_ASSERT_EQUAL(ebitmap_xor(&dst2, &dst1, &e1), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst2, &e1));
> > +
> > + ebitmap_destroy(&dst2);
> > + ebitmap_destroy(&dst1);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e2, &e2), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e3, &e3), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e4, &e4), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e1, &e2), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e3));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e2, &e4), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e2));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + ebitmap_destroy(&e4);
> > + ebitmap_destroy(&e3);
> > + ebitmap_destroy(&e2);
> > + ebitmap_destroy(&e1);
> > + }
> > +
> > + {
> > + ebitmap_t e5;
> > + ebitmap_t e6;
> > + ebitmap_t e56;
> > + ebitmap_t dst;
> > +
> > + ebitmap_init(&e5);
> > + ebitmap_init(&e6);
> > + ebitmap_init(&e56);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 64, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 192, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 319, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 320, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 63, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 64, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 191, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 318, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 320, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e5, &e6), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e56));
> > +
> > + ebitmap_destroy(&dst);
> > + ebitmap_destroy(&e56);
> > + ebitmap_destroy(&e6);
> > + ebitmap_destroy(&e5);
> > + }
> > +}
> > +
> > +static void test_ebitmap_not(void)
> > +{
> > + {
> > + ebitmap_t e1, e2, e3, e4;
> > +
> > + ebitmap_init(&e1);
> > + ebitmap_init(&e2);
> > + ebitmap_init(&e3);
> > + ebitmap_init(&e4);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 0, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 5, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 2, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 3, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 4, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 6, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 7, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 8, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 9, 1), 0);
> > +
> > + {
> > + ebitmap_t dst1, dst2;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_not(&dst1, &e3, 10), 0);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&dst1), 9);
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&dst1), 10);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_not(&dst2, &dst1, 10), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst2, &e3));
> > +
> > + ebitmap_destroy(&dst2);
> > + ebitmap_destroy(&dst1);
> > + }
> > +
> > + {
> > + ebitmap_t dst1, dst2;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_not(&dst1, &e1, 11), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst1, &e2));
> > + CU_ASSERT_EQUAL(ebitmap_not(&dst2, &dst1, 11), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst2, &e1));
> > +
> > + ebitmap_destroy(&dst2);
> > + ebitmap_destroy(&dst1);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_not(&dst, &e1, 8), 0);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&dst), 7);
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&dst), 5);
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_not(&dst, &e1, 12), 0);
> > + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&dst), 11);
> > + CU_ASSERT_EQUAL(ebitmap_cardinality(&dst), 8);
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + ebitmap_destroy(&e3);
> > + ebitmap_destroy(&e2);
> > + ebitmap_destroy(&e1);
> > + }
> > +
> > + {
> > + ebitmap_t e5;
> > + ebitmap_t e5not;
> > + ebitmap_node_t *n;
> > + unsigned int bit;
> > +
> > + ebitmap_init(&e5);
> > + ebitmap_init(&e5not);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0);
> > +
> > + for (bit = 0; bit < 317; bit++)
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5not, bit, 1), 0);
> > + ebitmap_for_each_positive_bit(&e5, n, bit)
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5not, bit, 0), 0);
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_not(&dst, &e5, 317), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e5not));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_not(&dst, &e5, 318), 0);
> > + CU_ASSERT_FALSE(ebitmap_cmp(&dst, &e5not));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5not, 317, 1), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e5not));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_not(&dst, &e5, 319), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e5not));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + ebitmap_destroy(&e5not);
> > + ebitmap_destroy(&e5);
> > + }
> > +}
> > +
> > +static void test_ebitmap_andnot(void)
> > +{
> > + {
> > + ebitmap_t e1, e2, e12, e3, e4;
> > +
> > + ebitmap_init(&e1);
> > + ebitmap_init(&e2);
> > + ebitmap_init(&e12);
> > + ebitmap_init(&e3);
> > + ebitmap_init(&e4);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 100, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 101, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 430, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1013, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 11, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 101, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 665, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 10, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 100, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 430, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 1013, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 11, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 100, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 101, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 665, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 1013, 1), 0);
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e1, &e1, 1024), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e2, &e2, 1024), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e1, &e2, 1024), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e12));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e3, &e3, 1024), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e1, &e3, 1024), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e2, &e12, 1024), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e2));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e4, &e4, 1024), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e4));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e3, &e4, 1024), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e3));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + ebitmap_destroy(&e4);
> > + ebitmap_destroy(&e3);
> > + ebitmap_destroy(&e12);
> > + ebitmap_destroy(&e2);
> > + ebitmap_destroy(&e1);
> > + }
> > +
> > + {
> > + ebitmap_t e5;
> > + ebitmap_t e6;
> > + ebitmap_t e56;
> > +
> > + ebitmap_init(&e5);
> > + ebitmap_init(&e6);
> > + ebitmap_init(&e56);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 64, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 192, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 319, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 320, 1), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 63, 1), 0);
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 191, 1), 0);
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 317), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e56));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 318), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e56));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 319), 0);
> > + CU_ASSERT_FALSE(ebitmap_cmp(&dst, &e56));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 318, 1), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e56));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + {
> > + ebitmap_t dst;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 320), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst, &e56));
> > +
> > + ebitmap_destroy(&dst);
> > + }
> > +
> > + ebitmap_destroy(&e56);
> > + ebitmap_destroy(&e6);
> > + ebitmap_destroy(&e5);
> > + }
> > +}
> > +
> > +static void test_ebitmap__random_impl(unsigned int length, int set_chance)
> > +{
> > + ebitmap_t e1, e2, dst_cpy, dst_or, dst_and, dst_xor1, dst_xor2, dst_not1, dst_not2, dst_andnot;
> > + unsigned int i;
> > +
> > + CU_ASSERT_EQUAL(ebitmap_init_random(&e1, length, set_chance), 0);
> > + CU_ASSERT_EQUAL(ebitmap_init_random(&e2, length, set_chance), 0);
> > +
> > + CU_ASSERT_EQUAL(ebitmap_cpy(&dst_cpy, &e1), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst_cpy, &e1));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_or(&dst_or, &e1, &e2), 0);
> > + for (i = 0; i < length; i++)
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_or, i), ebitmap_get_bit(&e1, i) | ebitmap_get_bit(&e2, i));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_and(&dst_and, &e1, &e2), 0);
> > + for (i = 0; i < length; i++)
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_and, i), ebitmap_get_bit(&e1, i) & ebitmap_get_bit(&e2, i));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_xor(&dst_xor1, &e1, &e2), 0);
> > + for (i = 0; i < length; i++)
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_xor1, i), ebitmap_get_bit(&e1, i) ^ ebitmap_get_bit(&e2, i));
> > + CU_ASSERT_EQUAL(ebitmap_xor(&dst_xor2, &dst_xor1, &e2), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst_xor2, &e1));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_not(&dst_not1, &e1, length), 0);
> > + for (i = 0; i < length; i++)
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_not1, i), !ebitmap_get_bit(&e1, i));
> > + CU_ASSERT_EQUAL(ebitmap_not(&dst_not2, &dst_not1, length), 0);
> > + CU_ASSERT(ebitmap_cmp(&dst_not2, &e1));
> > +
> > + CU_ASSERT_EQUAL(ebitmap_andnot(&dst_andnot, &e1, &e2, length), 0);
> > + for (i = 0; i < length; i++)
> > + CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_andnot, i), ebitmap_get_bit(&e1, i) & !ebitmap_get_bit(&e2, i));
> > +
> > + ebitmap_destroy(&dst_andnot);
> > + ebitmap_destroy(&dst_not2);
> > + ebitmap_destroy(&dst_not1);
> > + ebitmap_destroy(&dst_xor2);
> > + ebitmap_destroy(&dst_xor1);
> > + ebitmap_destroy(&dst_and);
> > + ebitmap_destroy(&dst_or);
> > + ebitmap_destroy(&dst_cpy);
> > + ebitmap_destroy(&e2);
> > + ebitmap_destroy(&e1);
> > +}
> > +
> > +static void test_ebitmap__random(void)
> > +{
> > + unsigned int i;
> > +
> > + for (i = 0; i < RANDOM_ROUNDS; i++)
> > + test_ebitmap__random_impl(5, 10);
> > +
> > + for (i = 0; i < RANDOM_ROUNDS; i++)
> > + test_ebitmap__random_impl(5, 90);
> > +
> > + for (i = 0; i < RANDOM_ROUNDS; i++)
> > + test_ebitmap__random_impl(1024, 50);
> > +
> > + for (i = 0; i < RANDOM_ROUNDS; i++)
> > + test_ebitmap__random_impl(8000, 5);
> > +
> > + for (i = 0; i < RANDOM_ROUNDS; i++)
> > + test_ebitmap__random_impl(8000, 95);
> > +}
> > +
> > +/*
> > + * External hooks
> > + */
> > +
> > +int ebitmap_test_init(void)
> > +{
> > + srandom(time(NULL));
> > +
> > + /* silence ebitmap_set_bit() failure message */
> > + sepol_debug(0);
> > +
> > + return 0;
> > +}
> > +
> > +int ebitmap_test_cleanup(void)
> > +{
> > + return 0;
> > +}
> > +
> > +#define ADD_TEST(name) \
> > + do { \
> > + if (NULL == CU_add_test(suite, #name, test_##name)) { \
> > + return CU_get_error(); \
> > + } \
> > + } while (0)
> > +
> > +int ebitmap_add_tests(CU_pSuite suite)
> > +{
> > + ADD_TEST(ebitmap_init_destroy);
> > + ADD_TEST(ebitmap_cmp);
> > + ADD_TEST(ebitmap_set_and_get);
> > + ADD_TEST(ebitmap_or);
> > + ADD_TEST(ebitmap_and);
> > + ADD_TEST(ebitmap_xor);
> > + ADD_TEST(ebitmap_not);
> > + ADD_TEST(ebitmap_andnot);
> > + ADD_TEST(ebitmap__random);
> > + return 0;
> > +}
> > diff --git a/libsepol/tests/test-ebitmap.h b/libsepol/tests/test-ebitmap.h
> > new file mode 100644
> > index 00000000..952a0421
> > --- /dev/null
> > +++ b/libsepol/tests/test-ebitmap.h
> > @@ -0,0 +1,10 @@
> > +#ifndef TEST_EBITMAP_H__
> > +#define TEST_EBITMAP_H__
> > +
> > +#include <CUnit/Basic.h>
> > +
> > +int ebitmap_test_init(void);
> > +int ebitmap_test_cleanup(void);
> > +int ebitmap_add_tests(CU_pSuite suite);
> > +
> > +#endif /* TEST_EBITMAP_H__ */
> > --
> > 2.36.1
> >
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2022-08-09 15:19 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-07-19 15:30 [PATCH v2 1/7] libsepol/tests: add ebitmap tests Christian Göttsche
2022-07-19 15:30 ` [PATCH v2 2/7] libsepol: add ebitmap_init_range Christian Göttsche
2022-07-19 15:30 ` [PATCH v2 3/7] libsepol/cil: use ebitmap_init_range Christian Göttsche
2022-07-19 15:30 ` [PATCH v2 4/7] libsepol: optimize ebitmap_not Christian Göttsche
2022-07-19 15:30 ` [PATCH v2 5/7] libsepol: optimize ebitmap_and Christian Göttsche
2022-07-19 15:30 ` [PATCH v2 6/7] libsepol: optimize ebitmap_xor Christian Göttsche
2022-07-19 15:30 ` [PATCH v2 7/7] libsepol: skip superfluous memset calls in ebitmap operations Christian Göttsche
2022-07-20 19:51 ` [PATCH v2 1/7] libsepol/tests: add ebitmap tests James Carter
2022-08-09 15:19 ` James Carter
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).