From: Vladimir Davydov <vdavydov.dev@gmail.com> To: tarantool-patches@freelists.org Subject: [PATCH 1/5] vinyl: factor out function to lookup key in page Date: Wed, 29 May 2019 18:12:47 +0300 [thread overview] Message-ID: <f498e09dab1047e0c07671127edfa835e2ea89d0.1559142561.git.vdavydov.dev@gmail.com> (raw) In-Reply-To: <cover.1559142561.git.vdavydov.dev@gmail.com> In-Reply-To: <cover.1559142561.git.vdavydov.dev@gmail.com> This function is a part of the run iterator API so we can't use it in a reader thread. Let's make it an independent helper. As a good side effect, we can now reuse it in the slice stream implementation. --- src/box/vy_run.c | 105 +++++++++++++++++++++++-------------------------------- 1 file changed, 44 insertions(+), 61 deletions(-) diff --git a/src/box/vy_run.c b/src/box/vy_run.c index 3b38aac6..84e0f50b 100644 --- a/src/box/vy_run.c +++ b/src/box/vy_run.c @@ -744,6 +744,41 @@ vy_page_stmt(struct vy_page *page, uint32_t stmt_no, } /** + * Binary search in page + * In terms of STL, makes lower_bound for EQ,GE,LT and upper_bound for GT,LE + * Additionally *equal_key argument is set to true if the found value is + * equal to given key (untouched otherwise) + * @retval position in the page + */ +static uint32_t +vy_page_find_key(struct vy_page *page, struct vy_entry key, + struct key_def *cmp_def, struct tuple_format *format, + enum iterator_type iterator_type, bool *equal_key) +{ + uint32_t beg = 0; + uint32_t end = page->row_count; + /* for upper bound we change zero comparison result to -1 */ + int zero_cmp = (iterator_type == ITER_GT || + iterator_type == ITER_LE ? -1 : 0); + while (beg != end) { + uint32_t mid = beg + (end - beg) / 2; + struct vy_entry fnd_key = vy_page_stmt(page, mid, cmp_def, + format); + if (fnd_key.stmt == NULL) + return end; + int cmp = vy_entry_compare(fnd_key, key, cmp_def); + cmp = cmp ? cmp : zero_cmp; + *equal_key = *equal_key || cmp == 0; + if (cmp < 0) + beg = mid + 1; + else + end = mid; + tuple_unref(fnd_key.stmt); + } + return end; +} + +/** * End iteration and free cached data. */ static void @@ -1055,42 +1090,6 @@ vy_run_iterator_read(struct vy_run_iterator *itr, } /** - * Binary search in page - * In terms of STL, makes lower_bound for EQ,GE,LT and upper_bound for GT,LE - * Additionally *equal_key argument is set to true if the found value is - * equal to given key (untouched otherwise) - * @retval position in the page - */ -static uint32_t -vy_run_iterator_search_in_page(struct vy_run_iterator *itr, - enum iterator_type iterator_type, - struct vy_entry key, - struct vy_page *page, bool *equal_key) -{ - uint32_t beg = 0; - uint32_t end = page->row_count; - /* for upper bound we change zero comparison result to -1 */ - int zero_cmp = (iterator_type == ITER_GT || - iterator_type == ITER_LE ? -1 : 0); - while (beg != end) { - uint32_t mid = beg + (end - beg) / 2; - struct vy_entry fnd_key = vy_page_stmt(page, mid, itr->cmp_def, - itr->format); - if (fnd_key.stmt == NULL) - return end; - int cmp = vy_entry_compare(fnd_key, key, itr->cmp_def); - cmp = cmp ? cmp : zero_cmp; - *equal_key = *equal_key || cmp == 0; - if (cmp < 0) - beg = mid + 1; - else - end = mid; - tuple_unref(fnd_key.stmt); - } - return end; -} - -/** * Binary search in a run for the given key. * In terms of STL, makes lower_bound for EQ,GE,LT and upper_bound for GT,LE * Resulting wide position is stored it *pos argument @@ -1116,9 +1115,9 @@ vy_run_iterator_search(struct vy_run_iterator *itr, if (rc != 0) return rc; bool equal_in_page = false; - pos->pos_in_page = vy_run_iterator_search_in_page(itr, iterator_type, - key, page, - &equal_in_page); + pos->pos_in_page = vy_page_find_key(page, key, itr->cmp_def, + itr->format, iterator_type, + &equal_in_page); if (pos->pos_in_page == page->row_count) { pos->page_no++; pos->pos_in_page = 0; @@ -2600,28 +2599,12 @@ vy_slice_stream_search(struct vy_stmt_stream *virt_stream) if (vy_slice_stream_read_page(stream) != 0) return -1; - /** - * Binary search in page. Find the first position in page with - * tuple >= stream->slice->begin. - */ - uint32_t beg = 0; - uint32_t end = stream->page->row_count; - while (beg != end) { - uint32_t mid = beg + (end - beg) / 2; - struct vy_entry fnd_key = vy_page_stmt(stream->page, mid, - stream->cmp_def, - stream->format); - if (fnd_key.stmt == NULL) - return -1; - int cmp = vy_entry_compare(fnd_key, stream->slice->begin, - stream->cmp_def); - if (cmp < 0) - beg = mid + 1; - else - end = mid; - tuple_unref(fnd_key.stmt); - } - stream->pos_in_page = end; + bool unused; + stream->pos_in_page = vy_page_find_key(stream->page, + stream->slice->begin, + stream->cmp_def, + stream->format, + ITER_GE, &unused); if (stream->pos_in_page == stream->page->row_count) { /* The first tuple is in the beginning of the next page */ -- 2.11.0
next prev parent reply other threads:[~2019-05-29 15:12 UTC|newest] Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top 2019-05-29 15:12 [PATCH 0/5] Hand over key lookup in a page to vinyl reader thread Vladimir Davydov 2019-05-29 15:12 ` Vladimir Davydov [this message] 2019-05-29 18:16 ` [tarantool-patches] Re: [PATCH 1/5] vinyl: factor out function to lookup key in page Konstantin Osipov 2019-05-29 15:12 ` [PATCH 2/5] vinyl: pass page info by reference to reader thread Vladimir Davydov 2019-05-29 18:16 ` [tarantool-patches] " Konstantin Osipov 2019-05-29 15:12 ` [PATCH 3/5] vinyl: encapsulate reader thread selection logic in a helper function Vladimir Davydov 2019-05-29 18:24 ` [tarantool-patches] " Konstantin Osipov 2019-05-29 15:12 ` [PATCH 4/5] vinyl: do not allow to cancel a fiber reading a page Vladimir Davydov 2019-05-29 18:35 ` [tarantool-patches] " Konstantin Osipov 2019-05-29 15:12 ` [PATCH 5/5] vinyl: lookup key in reader thread Vladimir Davydov 2019-05-29 18:41 ` [tarantool-patches] " Konstantin Osipov 2019-05-30 8:42 ` [PATCH 0/5] Hand over key lookup in a page to vinyl " Vladimir Davydov 2019-05-30 14:20 ` 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=f498e09dab1047e0c07671127edfa835e2ea89d0.1559142561.git.vdavydov.dev@gmail.com \ --to=vdavydov.dev@gmail.com \ --cc=tarantool-patches@freelists.org \ --subject='Re: [PATCH 1/5] vinyl: factor out function to lookup key in page' \ /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