libsepol/tests: add ebitmap tests
PATCH v2 1/7 libsepol/tests: add ebitmap tests
Preparation for several ebitmap related optimizations.
---
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
libsepol/tests/libsepol-tests.c +2 -0
@@ -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);
libsepol/tests/test-ebitmap.c new file +1048 -0
1,048 lines not on this page · raw message
libsepol/tests/test-ebitmap.h new file +10 -0
@@ -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__ */
Signature · 1 line
2.36.1
PATCH v2 2/7 libsepol: add ebitmap_init_range
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().
---
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(+)
libsepol/include/sepol/policydb/ebitmap.h +1 -0
@@ -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);
libsepol/src/ebitmap.c +49 -0
55 lines not on this page · raw message
libsepol/tests/test-ebitmap.c +32 -0
@@ -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);
Signature · 1 line
2.36.1
PATCH v2 3/7 libsepol/cil: use ebitmap_init_range
In reply to Christian GöttscheEspecially 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.
--- libsepol/cil/src/cil_post.c | 30 +++++++++--------------------- 1 file changed, 9 insertions(+), 21 deletions(-)
libsepol/cil/src/cil_post.c +9 -21
@@ -1191,7 +1191,6 @@ static int __cil_cat_expr_range_to_bitmap_helper(struct cil_list_item *i1, strucstruct 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 *ichar *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 {
Signature · 1 line
2.36.1
PATCH v2 4/7 libsepol: optimize ebitmap_not
In reply to Christian GöttscheIterate on nodes instead of single bits to save node resolution for each single bit.
--- libsepol/src/ebitmap.c | 48 ++++++++++++++++++++++++++++++++++++------ 1 file changed, 42 insertions(+), 6 deletions(-)
libsepol/src/ebitmap.c +42 -6
@@ -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 ; }
Signature · 1 line
2.36.1
PATCH v2 5/7 libsepol: optimize ebitmap_and
In reply to Christian GöttscheIterate on nodes instead of single bits to save node resolution for each single bit.
---
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(-)
libsepol/src/ebitmap.c +35 -6
@@ -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 ; }
Signature · 1 line
2.36.1
PATCH v2 6/7 libsepol: optimize ebitmap_xor
In reply to Christian GöttscheIterate on nodes instead of single bits to save node resolution for each single bit.
--- libsepol/src/ebitmap.c | 49 ++++++++++++++++++++++++++++++++++++------ 1 file changed, 43 insertions(+), 6 deletions(-)
libsepol/src/ebitmap.c +43 -6
@@ -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 ; }
Signature · 1 line
2.36.1
PATCH v2 7/7 libsepol: skip superfluous memset calls in ebitmap operations
In reply to Christian GöttscheThe 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().
--- libsepol/src/ebitmap.c | 3 --- 1 file changed, 3 deletions(-)
libsepol/src/ebitmap.c +0 -3
@@ -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));
Signature · 1 line
2.36.1
Quoted 4 lines · Christian Göttsche
Preparation for several ebitmap related optimizations.
Signed-off-by Christian Göttsche <[email protected]>
For this series:
Quoted 1,106 lines
---
v2:
- add more tests for multi node ebitmaps and for bits set at node bounds
- testebitmap_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.hlibsepol/tests/libsepol-tests.c +2
-0@@ -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);libsepol/tests/test-ebitmap.c new file +1048
-0@@ -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 ; +}libsepol/tests/test-ebitmap.h new file +10
-1@@ -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
Quoted 11 lines · James Carter
Quoted 4 lines · Christian Göttsche
Preparation for several ebitmap related optimizations.
Signed-off-by Christian Göttsche <[email protected]>For this series:
Acked-by James Carter <[email protected]>
This series has been merged.
Thanks,
Jim
Quoted 1,106 lines
Quoted 1,106 lines
---
v2:
- add more tests for multi node ebitmaps and for bits set at node bounds
- testebitmap_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.hlibsepol/tests/libsepol-tests.c +2
-0@@ -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);libsepol/tests/test-ebitmap.c new file +1048
-0@@ -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 ; +}libsepol/tests/test-ebitmap.h new file +10
-1@@ -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