On Tue, Nov 30, 2021 at 6:13 AM Christian Göttsche
<cgzones@xxxxxxxxxxxxxx> wrote:
>
> 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)?
>
I do prefer that name and will be fine with the patch with that name.
Thanks,
Jim
> > Thanks,
> > Jim
