Re: [tarantool-patches] Re: [PATCH v1 3/4] box: introduce bitmap_majority_test routine

[Vladimir Davydov <vdavydov.dev@gmail.com>]

On Sat, Dec 29, 2018 at 03:58:32PM +0300, Kirill Shcherbatov wrote:
> > 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.
> 
> You are right. Your approach is much better.
> ====================================
> 
> A new bit_find helper returns the index of the first bit set in
> bitmap, bitmap_size returns size of bitmap allocation by count
> of bits to work with.
> 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    | 25 +++++++++++++++++++++++++
>  test/unit/bit.c      | 33 +++++++++++++++++++++++++++++++++
>  test/unit/bit.result |  2 ++
>  3 files changed, 60 insertions(+)
> 
> diff --git a/src/lib/bit/bit.h b/src/lib/bit/bit.h
> index 370a0cc5d..fc3a5ba21 100644
> --- a/src/lib/bit/bit.h
> +++ b/src/lib/bit/bit.h
> @@ -614,6 +614,31 @@ bit_iterator_next(struct bit_iterator *it)
>  	return it->word_base + bit;
>  }
>  
> +/**
> + * Return a number of a first set bit in data or SIZE_MAX
> + * if no bits are set in data.
> + */
> +static inline size_t
> +bit_find(const void *data, size_t size)
> +{
> +	struct bit_iterator it;
> +	bit_iterator_init(&it, data, size, true);
> +	return bit_iterator_next(&it);
> +}

Ouch, you seems to have misunderstood me. What I meant when I talked
about the need of bit_find() was: *if* bit_iterator is not fast enough,
introduce an efficient bit_find() helper, *otherwise* use bit_iterator -
there's no point wrapping bit_iterator_next() in a new helper function.
Sorry for misunderstanding.

> +
> +/** Return size of bitmap by bit_count - count of bits to set. */
> +static inline size_t
> +bitmap_size(size_t bit_count)

This helper should be closer to the beginning of the file, because
header files are typically organized as follows: first macros and
trivial inline helpers, then more complex structures and functions.

> +{
> +	/*
> +	 * Memory size must be sizeof(uint32_t)-aligned as

sizeof(uint32_t)? But you align by (long). Please fix the comment.
I guess we can say that the size of a bitmap should be word-aligned.

> +	 * bit_sit/bit_clear operations use unt32_t words to
> +	 * setup bits.
> +	 */
> +	return DIV_ROUND_UP(DIV_ROUND_UP(bit_count, CHAR_BIT),
> +			    sizeof(unsigned long)) * sizeof(unsigned long);

This is correct indeed, and I guess it's OK to leave it as is, but to me
first converting bit count to byte count and only then to word count
looks confusing. Why not convert bit count to word count directly?

	size_t word_count = DIV_ROUND_UP(bit_count, CHAR_BIT * sizeof(long));
	return word_count * sizeof(long);

> +}
> +
>  #undef ITER_CTZ
>  #undef ITER_UINT
>  
> diff --git a/test/unit/bit.c b/test/unit/bit.c
> index beb89a7e4..8f68a6a83 100644
> --- a/test/unit/bit.c
> +++ b/test/unit/bit.c
> @@ -206,6 +206,38 @@ test_bit_iter_empty(void)
>  	footer();
>  }
>  
> +static void
> +test_bitmap(void)
> +{
> +	header();
> +
> +	fail_if(bitmap_size(0) != 0);
> +	fail_if(bitmap_size(1) != sizeof(unsigned long));
> +	fail_if(bitmap_size(4) != sizeof(unsigned long));
> +	fail_if(bitmap_size(CHAR_BIT * sizeof(unsigned long)) !=

I think we should use is() for testing bitmap_size().