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

[Kirill Shcherbatov <kshcherbatov@tarantool.org>]

> 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);
+}
+
+/** Return size of bitmap by bit_count - count of bits to set. */
+static inline size_t
+bitmap_size(size_t bit_count)
+{
+	/*
+	 * Memory size must be sizeof(uint32_t)-aligned as
+	 * 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);
+}
+
 #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)) !=
+		sizeof(unsigned long));
+	fail_if(bitmap_size(CHAR_BIT * sizeof(unsigned long) + 1) !=
+		2 * sizeof(unsigned long));
+
+	uint32_t test[5];
+	memset(test, 0, sizeof(test));
+	bit_set(test, 2 * sizeof(uint32_t) * CHAR_BIT + 4);
+	bit_set(test, 2 * sizeof(uint32_t) * CHAR_BIT + 2);
+	bit_set(test, 8);
+
+	fail_if(bit_find(test, 5 * sizeof(uint32_t)) != 8);
+	bit_clear(test, 8);
+	fail_if(bit_find(test, 5 * sizeof(uint32_t)) !=
+		2 * sizeof(uint32_t) * CHAR_BIT + 2);
+	bit_clear(test, 2 * sizeof(uint32_t) * CHAR_BIT + 2);
+	fail_if(bit_find(test, 5 * sizeof(uint32_t)) !=
+		2 * sizeof(uint32_t) * CHAR_BIT + 4);
+	bit_clear(test, 2 * sizeof(uint32_t) * CHAR_BIT + 4);
+	fail_if(bit_find(test, 5 * sizeof(uint32_t)) != SIZE_MAX);
+
+	footer();
+}
+
 int
 main(void)
 {
@@ -216,4 +248,5 @@ main(void)
 	test_index();
 	test_bit_iter();
 	test_bit_iter_empty();
+	test_bitmap();
 }
diff --git a/test/unit/bit.result b/test/unit/bit.result
index e2c5601f3..ab9ae9d92 100644
--- a/test/unit/bit.result
+++ b/test/unit/bit.result
@@ -891,3 +891,5 @@ Clear: 0, 1, 2, 4, 5, 6, 7, 8, 10, 12, 13, 14, 15, 19, 20, 21, 23, 26, 28, 30, 3
 	*** test_bit_iter: done ***
 	*** test_bit_iter_empty ***
 	*** test_bit_iter_empty: done ***
+	*** test_bitmap ***
+	*** test_bitmap: done ***
-- 
2.19.2