From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Kirill Shcherbatov Subject: [PATCH v1 3/4] box: introduce bitmap_majority_test routine Date: Thu, 27 Dec 2018 14:15:54 +0300 Message-Id: In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit To: tarantool-patches@freelists.org, vdavydov.dev@gmail.com Cc: kostja@tarantool.org, Kirill Shcherbatov List-ID: 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