[PATCH v1 3/4] box: introduce bitmap_majority_test routine
Kirill Shcherbatov
kshcherbatov at tarantool.org
Thu Dec 27 14:15:54 MSK 2018
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)
+{
+ int match_cnt = 0;
+ uint32_t *a_ptr = a, *b_ptr = b;
+ uint32_t neg_impl;
+ /*
+ * "Inverted material implication" ~(~x | y) = x & ~y test
+ * is used to find the first bit that differ
+ *
+ * Example:
+ * step 0 -- skip compatible bytes
+ * x: 0b01111101
+ * y: 0b00111101
+ * x & ~y: 0b00000000 == 0 -- next, goto step 0
+ *
+ * step 1 -- the first byte that differ:
+ * x: 0b01011001
+ * y: 0b00111101
+ * x & ~y: 0b00100100
+ *
+ * step 2 -- calculate relative bit index with ctz:
+ * bit_ctz_u32(0b00100100) = 2 -- return diff_bit_id
+ */
+ while (bit_likely((neg_impl = *b_ptr & ~*a_ptr) == 0)) {
+ if (bit_unlikely(++match_cnt >= len)) {
+ return 0;
+ }
+ a_ptr++;
+ b_ptr++;
+ }
+ assert(neg_impl != 0);
+ uint32_t trailing_zeros = bit_ctz_u32(neg_impl);
+ *diff_bit_id = match_cnt * sizeof(uint32_t) * CHAR_BIT + trailing_zeros;
+ return -1;
+}
+
#undef ITER_CTZ
#undef ITER_UINT
diff --git a/test/unit/bit.c b/test/unit/bit.c
index beb89a7e4..10074c412 100644
--- a/test/unit/bit.c
+++ b/test/unit/bit.c
@@ -206,6 +206,57 @@ test_bit_iter_empty(void)
footer();
}
+static void
+test_bitmap_majority(void)
+{
+ header();
+
+ uint32_t id;
+ uint32_t req_bitmap[5];
+ memset(req_bitmap, 0, sizeof(req_bitmap));
+ bit_set(req_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 2);
+ bit_set(req_bitmap, 3 * sizeof(uint32_t) * CHAR_BIT + 1);
+ bit_set(req_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 4);
+ bit_set(req_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 2);
+ bit_set(req_bitmap, 8);
+ fail_if(bitmap_majority_test(req_bitmap, req_bitmap, 5, &id) != 0);
+
+ /*
+ * Verify that bitmap_majority_test returns difference
+ * bits ids in incremental order ignoring test extra bits.
+ */
+ uint32_t test_bitmap[5];
+ memset(test_bitmap, 0, sizeof(test_bitmap));
+ bit_set(test_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 8);
+ bit_set(test_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 1);
+ bit_set(test_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 8);
+
+ fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1);
+ fail_unless(id == 8);
+ bit_set(&test_bitmap, 8);
+
+ fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1);
+ fail_unless(id == 2 * sizeof(uint32_t) * CHAR_BIT + 2);
+ bit_set(&test_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 2);
+
+ fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1);
+ fail_unless(id == 2 * sizeof(uint32_t) * CHAR_BIT + 4);
+ bit_set(&test_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 4);
+
+ fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1);
+ fail_unless(id == 3 * sizeof(uint32_t) * CHAR_BIT + 1);
+ bit_set(&test_bitmap, 3 * sizeof(uint32_t) * CHAR_BIT + 1);
+
+ fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1);
+ fail_unless(id == 4 * sizeof(uint32_t) * CHAR_BIT + 2);
+ bit_set(&test_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 2);
+
+ /* All different bits have been fixed. */
+ fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 4, &id) != 0);
+
+ footer();
+}
+
int
main(void)
{
@@ -216,4 +267,5 @@ main(void)
test_index();
test_bit_iter();
test_bit_iter_empty();
+ test_bitmap_majority();
}
diff --git a/test/unit/bit.result b/test/unit/bit.result
index e2c5601f3..6123bc58a 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_majority ***
+ *** test_bitmap_majority: done ***
--
2.19.2
More information about the Tarantool-patches
mailing list