| Message ID | 20211124190815.12757-1-cgzones@googlemail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | [RFC,v2,1/4] libsepol: introduce ebitmap_subtract() | expand |
On Thu, Nov 25, 2021 at 3:03 PM Christian Göttsche <cgzones@googlemail.com> wrote: > > Add a subtract method for ebitmaps. > > Signed-off-by: Christian Göttsche <cgzones@googlemail.com> > --- > 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. Thanks, Jim
On Mon, 29 Nov 2021 at 18:48, James Carter <jwcart2@gmail.com> wrote: > > On Thu, Nov 25, 2021 at 3:03 PM Christian Göttsche > <cgzones@googlemail.com> wrote: > > > > Add a subtract method for ebitmaps. > > > > Signed-off-by: Christian Göttsche <cgzones@googlemail.com> > > --- > > 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
On Tue, Nov 30, 2021 at 6:13 AM Christian Göttsche <cgzones@googlemail.com> wrote: > > On Mon, 29 Nov 2021 at 18:48, James Carter <jwcart2@gmail.com> wrote: > > > > On Thu, Nov 25, 2021 at 3:03 PM Christian Göttsche > > <cgzones@googlemail.com> wrote: > > > > > > Add a subtract method for ebitmaps. > > > > > > Signed-off-by: Christian Göttsche <cgzones@googlemail.com> > > > --- > > > 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
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));
Add a subtract method for ebitmaps. Signed-off-by: Christian Göttsche <cgzones@googlemail.com> --- v2: - add shortcut for empty ebitmaps --- libsepol/include/sepol/policydb/ebitmap.h | 1 + libsepol/src/ebitmap.c | 18 ++++++++++++++++++ 2 files changed, 19 insertions(+)