| Message ID | 20220712160858.22677-6-cgzones@googlemail.com (mailing list archive) |
|---|---|
| State | Accepted |
| Commit | f1740455253d |
| 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> Acked-by: James Carter <jwcart2@gmail.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 c3d706e9..e0541abb 100644 > --- a/libsepol/src/ebitmap.c > +++ b/libsepol/src/ebitmap.c > @@ -116,14 +116,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 >
diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c index c3d706e9..e0541abb 100644 --- a/libsepol/src/ebitmap.c +++ b/libsepol/src/ebitmap.c @@ -116,14 +116,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; }
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(-)