From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Thu, 27 Dec 2018 21:59:06 +0300 From: Vladimir Davydov Subject: Re: [PATCH v1 3/4] box: introduce bitmap_majority_test routine Message-ID: <20181227185906.redzzw3hbugxasb6@esperanza> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: To: Kirill Shcherbatov Cc: tarantool-patches@freelists.org, kostja@tarantool.org List-ID: 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.