diff mbox series

[2/7] libsepol: add ebitmap_init_range

Message ID 20220712160858.22677-2-cgzones@googlemail.com (mailing list archive)
State Accepted
Commit 6f9e682c15ba
Headers show
Series [1/7] libsepol/tests: add ebitmap tests | expand

Commit Message

Christian Göttsche July 12, 2022, 4:08 p.m. UTC 
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>
---
 libsepol/include/sepol/policydb/ebitmap.h |  1 +
 libsepol/src/ebitmap.c                    | 49 +++++++++++++++++++++++
 libsepol/tests/test-ebitmap.c             | 32 +++++++++++++++
 3 files changed, 82 insertions(+)

Comments

James Carter July 18, 2022, 8:43 p.m. UTC | #1 
On Tue, Jul 12, 2022 at 12:09 PM Christian Göttsche
<cgzones@googlemail.com> wrote:
>
> 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>
> ---
>  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..fb20e994 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));
> +               }
> +

I view braces in if-else statements as all or nothing. If you need
them for one clause, then use them for all clauses.

Everything else about this patch looks good.

Thanks,
Jim


> +               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 a21f18c0..1a49aa5f 100644
> --- a/libsepol/tests/test-ebitmap.c
> +++ b/libsepol/tests/test-ebitmap.c
> @@ -135,6 +135,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;
> @@ -701,6 +732,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
>
diff mbox series

Patch

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..fb20e994 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 a21f18c0..1a49aa5f 100644
--- a/libsepol/tests/test-ebitmap.c
+++ b/libsepol/tests/test-ebitmap.c
@@ -135,6 +135,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;
@@ -701,6 +732,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);