On Mon, 29 Nov 2021 at 18:48, James Carter <jwcart2@xxxxxxxxx> wrote:
>
> On Thu, Nov 25, 2021 at 3:03 PM Christian Göttsche
> <cgzones@xxxxxxxxxxxxxx> wrote:
> >
> > Add a subtract method for ebitmaps.
> >
> > Signed-off-by: Christian Göttsche <cgzones@xxxxxxxxxxxxxx>
> > ---
> > v2:
> > - add shortcut for empty ebitmaps
> > ---
> > libsepol/include/sepol/policydb/ebitmap.h | 1 +
> > libsepol/src/ebitmap.c | 18 ++++++++++++++++++
> > 2 files changed, 19 insertions(+)
> >
> > diff --git a/libsepol/include/sepol/policydb/ebitmap.h b/libsepol/include/sepol/policydb/ebitmap.h
> > index 81d0c7a6..daca67a2 100644
> > --- a/libsepol/include/sepol/policydb/ebitmap.h
> > +++ b/libsepol/include/sepol/policydb/ebitmap.h
> > @@ -83,6 +83,7 @@ static inline int ebitmap_node_get_bit(const ebitmap_node_t * n, unsigned int bi
> > extern int ebitmap_cmp(const ebitmap_t * e1, const ebitmap_t * e2);
> > extern int ebitmap_or(ebitmap_t * dst, const ebitmap_t * e1, const ebitmap_t * e2);
> > extern int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1);
> > +extern int ebitmap_subtract(ebitmap_t *dst, const ebitmap_t *e1);
> > extern int ebitmap_and(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2);
> > extern int ebitmap_xor(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2);
> > extern int ebitmap_not(ebitmap_t *dst, const ebitmap_t *e1, unsigned int maxbit);
> > diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c
> > index 1de3816a..80f0e201 100644
> > --- a/libsepol/src/ebitmap.c
> > +++ b/libsepol/src/ebitmap.c
> > @@ -72,6 +72,24 @@ int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1)
> > return 0;
> > }
> >
> > +int ebitmap_subtract(ebitmap_t *dst, const ebitmap_t *e1)
> > +{
> > + unsigned int i, length;
> > +
> > + if (ebitmap_is_empty(dst) || ebitmap_is_empty(e1))
> > + return 0;
> > +
> > + length = min(ebitmap_length(dst), ebitmap_length(e1));
> > + for (i=0; i < length; i++) {
> > + if (ebitmap_get_bit(e1, i)) {
> > + int rc = ebitmap_set_bit(dst, i, 0);
> > + if (rc < 0)
> > + return rc;
> > + }
> > + }
> > + return 0;
> > +}
> > +
> > 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));
> > --
> > 2.34.0
> >
>
> We already have ebitmap_andnot() which does the same thing (although
> it does take three ebitmaps). Also, subtract is not a bit operation,
> so it doesn't seem to fit.
ebitmap_andnot() does perform a not and an and operation (so two
iterations over the ebitmaps) and allocates a temporary ebitmap on the
way.
So I think this new helper has its justification for performance reasons.
Do you prefer another name, e.g. ebitmap_rel_comp() (see
https://en.wikipedia.org/wiki/Complement_(set_theory)#Relative_complement)?
> Thanks,
> Jim
