[PATCH 1/5] vinyl: factor out function to lookup key in page

[Vladimir Davydov]

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