| Message ID | 20220712160858.22677-4-cgzones@googlemail.com (mailing list archive) |
|---|---|
| State | Accepted |
| Commit | 12a8a00bf21d |
| 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 | 48 ++++++++++++++++++++++++++++++++++++------ > 1 file changed, 42 insertions(+), 6 deletions(-) > > diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c > index fb20e994..6a63e559 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 >
diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c index fb20e994..6a63e559 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; }
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(-)