[PATCH v1 3/4] box: introduce bitmap_majority_test routine

[Vladimir Davydov]

On Thu, Dec 27, 2018 at 02:15:54PM +0300, Kirill Shcherbatov wrote:
> A new routine bitmap_majority_test allows to test that bitmap
> a "majorates" bitmap b, i.e. test that a have at least all b bits.
> We need it to test compatibility of required fields bitmap with
> another one that is built for tuple on tuple_init_field_map.
> 
> Needed for #1012
> ---
>  src/lib/bit/bit.h    | 45 ++++++++++++++++++++++++++++++++++++++
>  test/unit/bit.c      | 52 ++++++++++++++++++++++++++++++++++++++++++++
>  test/unit/bit.result |  2 ++
>  3 files changed, 99 insertions(+)
> 
> diff --git a/src/lib/bit/bit.h b/src/lib/bit/bit.h
> index 370a0cc5d..2146a0452 100644
> --- a/src/lib/bit/bit.h
> +++ b/src/lib/bit/bit.h
> @@ -614,6 +614,51 @@ bit_iterator_next(struct bit_iterator *it)
>  	return it->word_base + bit;
>  }
>  
> +/**
> + * Check if the passed bitmap a "majorates" bitmap b (test that
> + * a contains at least all b bits). Compare first len memory
> + * blocks of sizeof(uint32_t).
> + * Return 0 when a majorates b. Otherwise -1 is returned and
> + * diff_bit_id is set - the index of first bit that present in
> + * bitmap b, but doesn't present in bitmap a.
> + */
> +static inline int
> +bitmap_majority_test(uint32_t *a, uint32_t *b, int len, uint32_t *diff_bit_id)

This function looks artificial to me, especially the fact that in case
of error it returns the first different bit in diff_bit_id (why only the
first one?).

Why do you need it, anyway? All you need to do in the next patch is:
 1. Allocate required_fields bitmap on region.
 2. Initialize it with tuple_format->required_fields.
 3. Clear bits in it as you find that corresponding tuple fields are
    present.
 4. Finally, check that the bitmap is empty. If it is not report an
    error for the first set bit.

To achieve that, you need a much simpler primitive, bit_find(), which
would find the first set bit in a bitmap. This primitive could be reused
in future, in contrast to this new function.

I just looked at bit.c and I see that it already has a bit iterator.
May be, we can simply use it for finding the first bit? It looks pretty
efficient to me.