From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Vladimir Davydov Subject: [PATCH 1/5] vinyl: factor out function to lookup key in page Date: Wed, 29 May 2019 18:12:47 +0300 Message-Id: In-Reply-To: References: In-Reply-To: References: To: tarantool-patches@freelists.org List-ID: 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