| Message ID | 20220712160858.22677-5-cgzones@googlemail.com (mailing list archive) |
|---|---|
| State | Accepted |
| Commit | efcd00814879 |
| Headers | show |
| Series | [1/7] libsepol/tests: add ebitmap tests | expand |
On Tue, Jul 12, 2022 at 12:09 PM Christian Göttsche <cgzones@googlemail.com> wrote: > > 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 | 42 +++++++++++++++++++++++++++++++++++------- > 1 file changed, 35 insertions(+), 7 deletions(-) > > diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c > index 6a63e559..c3d706e9 100644 > --- a/libsepol/src/ebitmap.c > +++ b/libsepol/src/ebitmap.c > @@ -74,15 +74,43 @@ 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; I would like to see braces around the last two clauses. Thanks, Jim > } > + > + if (prev) > + dst->highbit = prev->startbit + MAPSIZE; > + > return 0; > } > > -- > 2.36.1 >
diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c index 6a63e559..c3d706e9 100644 --- a/libsepol/src/ebitmap.c +++ b/libsepol/src/ebitmap.c @@ -74,15 +74,43 @@ 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; }
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 | 42 +++++++++++++++++++++++++++++++++++------- 1 file changed, 35 insertions(+), 7 deletions(-)