Tarantool development patches archive
 help / color / mirror / Atom feed
From: Vladimir Davydov <vdavydov.dev@gmail.com>
To: Kirill Shcherbatov <kshcherbatov@tarantool.org>
Cc: tarantool-patches@freelists.org, kostja@tarantool.org
Subject: Re: [PATCH v1 3/4] box: introduce bitmap_majority_test routine
Date: Thu, 27 Dec 2018 21:59:06 +0300	[thread overview]
Message-ID: <20181227185906.redzzw3hbugxasb6@esperanza> (raw)
In-Reply-To: <ab60e98b04a7659bcd294423dbb63886e69b1723.1545909237.git.kshcherbatov@tarantool.org>

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.

  reply	other threads:[~2018-12-27 18:59 UTC|newest]

Thread overview: 18+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-12-27 11:15 [PATCH v1 0/4] box: JSON preparatory patchset Kirill Shcherbatov
2018-12-27 11:15 ` [PATCH v1 1/4] lib: introduce json_tree_snprint_path Kirill Shcherbatov
2018-12-27 18:51   ` Vladimir Davydov
2018-12-27 11:15 ` [PATCH v1 2/4] lib: introduce json_token_is_leaf helper Kirill Shcherbatov
2018-12-27 18:52   ` Vladimir Davydov
2018-12-27 11:15 ` [PATCH v1 3/4] box: introduce bitmap_majority_test routine Kirill Shcherbatov
2018-12-27 18:59   ` Vladimir Davydov [this message]
2018-12-29 12:58     ` [tarantool-patches] " Kirill Shcherbatov
2018-12-29 13:19       ` Vladimir Davydov
2018-12-29 13:57         ` Kirill Shcherbatov
2018-12-29 16:16           ` Vladimir Davydov
2018-12-27 11:15 ` [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap Kirill Shcherbatov
2018-12-27 11:48   ` [tarantool-patches] " Konstantin Osipov
2018-12-27 19:12   ` Vladimir Davydov
2018-12-29 12:58     ` [tarantool-patches] " Kirill Shcherbatov
2018-12-29 13:22       ` Vladimir Davydov
2018-12-29 16:25       ` Vladimir Davydov
2018-12-27 19:13 ` [PATCH v1 0/4] box: JSON preparatory patchset Vladimir Davydov

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20181227185906.redzzw3hbugxasb6@esperanza \
    --to=vdavydov.dev@gmail.com \
    --cc=kostja@tarantool.org \
    --cc=kshcherbatov@tarantool.org \
    --cc=tarantool-patches@freelists.org \
    --subject='Re: [PATCH v1 3/4] box: introduce bitmap_majority_test routine' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox