Tarantool development patches archive
 help / color / mirror / Atom feed
From: Vladimir Davydov <vdavydov.dev@gmail.com>
To: kostja@tarantool.org
Cc: tarantool-patches@freelists.org
Subject: [PATCH 12/12] vinyl: zap vy_read_iterator::curr_stmt
Date: Sun, 15 Apr 2018 22:55:25 +0300	[thread overview]
Message-ID: <18579339c8a5137c020753d917d47f86fb536ef9.1523820298.git.vdavydov.dev@gmail.com> (raw)
In-Reply-To: <cover.1523820298.git.vdavydov.dev@gmail.com>
In-Reply-To: <cover.1523820298.git.vdavydov.dev@gmail.com>

It isn't really a part of the iterator state - it is only used while
looking up the next key. The name is confusing, too. It isn't the
current statement - it's the current candidate for the next key.
Let's remove it from vy_read_iterator struct and pass it explictily
in arguments, and call it next_key.
---
 src/box/vy_read_iterator.c | 96 +++++++++++++++++++++++-----------------------
 src/box/vy_read_iterator.h |  7 ++--
 2 files changed, 50 insertions(+), 53 deletions(-)

diff --git a/src/box/vy_read_iterator.c b/src/box/vy_read_iterator.c
index b171aa60..61c3b683 100644
--- a/src/box/vy_read_iterator.c
+++ b/src/box/vy_read_iterator.c
@@ -131,8 +131,8 @@ vy_read_iterator_unpin_slices(struct vy_read_iterator *itr)
 }
 
 /**
- * Return true if the current statement is outside the current
- * range and hence we should move to the next range.
+ * Return true if the current candidate for the next key is outside
+ * the current range and hence we should move to the next range.
  *
  * If we are looking for a match (EQ, REQ) and the search key
  * doesn't intersect with the current range's boundary, the next
@@ -140,23 +140,23 @@ vy_read_iterator_unpin_slices(struct vy_read_iterator *itr)
  * and hence there's no point in iterating to it.
  */
 static bool
-vy_read_iterator_range_is_done(struct vy_read_iterator *itr)
+vy_read_iterator_range_is_done(struct vy_read_iterator *itr,
+			       struct tuple *next_key)
 {
-	struct tuple *stmt = itr->curr_stmt;
 	struct vy_range *range = itr->curr_range;
 	struct key_def *cmp_def = itr->lsm->cmp_def;
 	int dir = iterator_direction(itr->iterator_type);
 
 	if (dir > 0 && range->end != NULL &&
-	    (stmt == NULL || vy_tuple_compare_with_key(stmt,
-				range->end, cmp_def) >= 0) &&
+	    (next_key == NULL || vy_tuple_compare_with_key(next_key,
+					range->end, cmp_def) >= 0) &&
 	    (itr->iterator_type != ITER_EQ ||
 	     vy_stmt_compare_with_key(itr->key, range->end, cmp_def) >= 0))
 		return true;
 
 	if (dir < 0 && range->begin != NULL &&
-	    (stmt == NULL || vy_tuple_compare_with_key(stmt,
-				range->begin, cmp_def) < 0) &&
+	    (next_key == NULL || vy_tuple_compare_with_key(next_key,
+					range->begin, cmp_def) < 0) &&
 	    (itr->iterator_type != ITER_REQ ||
 	     vy_stmt_compare_with_key(itr->key, range->begin, cmp_def) <= 0))
 		return true;
@@ -215,20 +215,21 @@ vy_read_iterator_is_exact_match(struct vy_read_iterator *itr,
 /**
  * Check if the statement at which the given read source
  * is positioned precedes the current candidate for the
- * next key ('curr_stmt') and update the latter if so.
+ * next key ('next_key') and update the latter if so.
  * The 'stop' flag is set if the next key is found and
  * older sources don't need to be evaluated.
  */
 static void
 vy_read_iterator_evaluate_src(struct vy_read_iterator *itr,
-			      struct vy_read_src *src, bool *stop)
+			      struct vy_read_src *src,
+			      struct tuple **next_key, bool *stop)
 {
 	uint32_t src_id = src - itr->src;
 	struct tuple *stmt = vy_history_last_stmt(&src->history);
-	int cmp = vy_read_iterator_cmp_stmt(itr, stmt, itr->curr_stmt);
+	int cmp = vy_read_iterator_cmp_stmt(itr, stmt, *next_key);
 	if (cmp < 0) {
 		assert(stmt != NULL);
-		itr->curr_stmt = stmt;
+		*next_key = stmt;
 		itr->front_id++;
 	}
 	if (cmp <= 0)
@@ -278,7 +279,7 @@ vy_read_src_is_behind(struct vy_read_iterator *itr, struct vy_read_src *src)
  *      front_id of the read iterator were used on the previous
  *      iteration and hence need to be advanced.
  *
- * 2. Update the candidate for the next key ('curr_stmt') if the
+ * 2. Update the candidate for the next key ('next_key') if the
  *    statement at which the source is positioned precedes it.
  *    The 'stop' flag is set if older sources do not need to be
  *    scanned (e.g. because a chain was found in the cache).
@@ -286,7 +287,8 @@ vy_read_src_is_behind(struct vy_read_iterator *itr, struct vy_read_src *src)
  */
 
 static NODISCARD int
-vy_read_iterator_scan_txw(struct vy_read_iterator *itr, bool *stop)
+vy_read_iterator_scan_txw(struct vy_read_iterator *itr,
+			  struct tuple **next_key, bool *stop)
 {
 	struct vy_read_src *src = &itr->src[itr->txw_src];
 	struct vy_txw_iterator *src_itr = &src->txw_iterator;
@@ -310,12 +312,13 @@ vy_read_iterator_scan_txw(struct vy_read_iterator *itr, bool *stop)
 	if (rc < 0)
 		return -1;
 
-	vy_read_iterator_evaluate_src(itr, src, stop);
+	vy_read_iterator_evaluate_src(itr, src, next_key, stop);
 	return 0;
 }
 
 static NODISCARD int
-vy_read_iterator_scan_cache(struct vy_read_iterator *itr, bool *stop)
+vy_read_iterator_scan_cache(struct vy_read_iterator *itr,
+			    struct tuple **next_key, bool *stop)
 {
 	bool is_interval = false;
 	struct vy_read_src *src = &itr->src[itr->cache_src];
@@ -336,7 +339,7 @@ vy_read_iterator_scan_cache(struct vy_read_iterator *itr, bool *stop)
 	if (rc < 0)
 		return -1;
 
-	vy_read_iterator_evaluate_src(itr, src, stop);
+	vy_read_iterator_evaluate_src(itr, src, next_key, stop);
 	if (is_interval) {
 		itr->skipped_src = itr->cache_src + 1;
 		*stop = true;
@@ -345,8 +348,8 @@ vy_read_iterator_scan_cache(struct vy_read_iterator *itr, bool *stop)
 }
 
 static NODISCARD int
-vy_read_iterator_scan_mem(struct vy_read_iterator *itr,
-			  uint32_t mem_src, bool *stop)
+vy_read_iterator_scan_mem(struct vy_read_iterator *itr, uint32_t mem_src,
+			  struct tuple **next_key, bool *stop)
 {
 	int rc;
 	struct vy_read_src *src = &itr->src[mem_src];
@@ -367,13 +370,13 @@ vy_read_iterator_scan_mem(struct vy_read_iterator *itr,
 	if (rc < 0)
 		return -1;
 
-	vy_read_iterator_evaluate_src(itr, src, stop);
+	vy_read_iterator_evaluate_src(itr, src, next_key, stop);
 	return 0;
 }
 
 static NODISCARD int
-vy_read_iterator_scan_disk(struct vy_read_iterator *itr,
-			   uint32_t disk_src, bool *stop)
+vy_read_iterator_scan_disk(struct vy_read_iterator *itr, uint32_t disk_src,
+			   struct tuple **next_key, bool *stop)
 {
 	int rc = 0;
 	struct vy_read_src *src = &itr->src[disk_src];
@@ -391,17 +394,18 @@ vy_read_iterator_scan_disk(struct vy_read_iterator *itr,
 	if (rc < 0)
 		return -1;
 
-	vy_read_iterator_evaluate_src(itr, src, stop);
+	vy_read_iterator_evaluate_src(itr, src, next_key, stop);
 	return 0;
 }
 
 /**
  * Restore the position of the active in-memory tree iterator
- * after a yield caused by a disk read and update 'curr_stmt'
+ * after a yield caused by a disk read and update 'next_key'
  * if necessary.
  */
 static NODISCARD int
-vy_read_iterator_restore_mem(struct vy_read_iterator *itr)
+vy_read_iterator_restore_mem(struct vy_read_iterator *itr,
+			     struct tuple **next_key)
 {
 	int rc;
 	int cmp;
@@ -415,7 +419,7 @@ vy_read_iterator_restore_mem(struct vy_read_iterator *itr)
 		return 0; /* nothing changed */
 
 	struct tuple *stmt = vy_history_last_stmt(&src->history);
-	cmp = vy_read_iterator_cmp_stmt(itr, stmt, itr->curr_stmt);
+	cmp = vy_read_iterator_cmp_stmt(itr, stmt, *next_key);
 	if (cmp > 0) {
 		/*
 		 * Memory trees are append-only so if the
@@ -430,7 +434,7 @@ vy_read_iterator_restore_mem(struct vy_read_iterator *itr)
 		 * The new statement precedes the current
 		 * candidate for the next key.
 		 */
-		itr->curr_stmt = stmt;
+		*next_key = stmt;
 		itr->front_id++;
 	} else {
 		/*
@@ -464,7 +468,7 @@ vy_read_iterator_advance(struct vy_read_iterator *itr)
 		 * There may be one statement at max satisfying
 		 * EQ with a full key.
 		 */
-		itr->curr_stmt = NULL;
+		itr->front_id++;
 		return 0;
 	}
 	/*
@@ -478,25 +482,26 @@ vy_read_iterator_advance(struct vy_read_iterator *itr)
 		vy_read_iterator_restore(itr);
 	}
 restart:
-	itr->curr_stmt = NULL;
 	itr->prev_front_id = itr->front_id;
+	itr->front_id++;
 
 	/*
 	 * Look up the next key in read sources starting
 	 * from the one that stores newest data.
 	 */
 	bool stop = false;
-	if (vy_read_iterator_scan_txw(itr, &stop) != 0)
+	struct tuple *next_key = NULL;
+	if (vy_read_iterator_scan_txw(itr, &next_key, &stop) != 0)
 		return -1;
 	if (stop)
 		goto done;
-	if (vy_read_iterator_scan_cache(itr, &stop) != 0)
+	if (vy_read_iterator_scan_cache(itr, &next_key, &stop) != 0)
 		return -1;
 	if (stop)
 		goto done;
 
 	for (uint32_t i = itr->mem_src; i < itr->disk_src; i++) {
-		if (vy_read_iterator_scan_mem(itr, i, &stop) != 0)
+		if (vy_read_iterator_scan_mem(itr, i, &next_key, &stop) != 0)
 			return -1;
 		if (stop)
 			goto done;
@@ -505,7 +510,7 @@ rescan_disk:
 	/* The following code may yield as it needs to access disk. */
 	vy_read_iterator_pin_slices(itr);
 	for (uint32_t i = itr->disk_src; i < itr->src_count; i++) {
-		if (vy_read_iterator_scan_disk(itr, i, &stop) != 0) {
+		if (vy_read_iterator_scan_disk(itr, i, &next_key, &stop) != 0) {
 			vy_read_iterator_unpin_slices(itr);
 			return -1;
 		}
@@ -531,21 +536,21 @@ rescan_disk:
 	 * as it is owned exclusively by the current fiber so the only
 	 * source to check is the active in-memory tree.
 	 */
-	if (vy_read_iterator_restore_mem(itr) != 0)
+	if (vy_read_iterator_restore_mem(itr, &next_key) != 0)
 		return -1;
 	/*
 	 * Scan the next range in case we transgressed the current
 	 * range's boundaries.
 	 */
-	if (vy_read_iterator_range_is_done(itr)) {
+	if (vy_read_iterator_range_is_done(itr, next_key)) {
 		vy_read_iterator_next_range(itr);
 		goto rescan_disk;
 	}
 done:
 #ifndef NDEBUG
 	/* Check that the statement meets search criteria. */
-	if (itr->curr_stmt != NULL) {
-		int cmp = vy_stmt_compare(itr->curr_stmt, itr->key,
+	if (next_key != NULL) {
+		int cmp = vy_stmt_compare(next_key, itr->key,
 					  itr->lsm->cmp_def);
 		cmp *= iterator_direction(itr->iterator_type);
 		if (itr->iterator_type == ITER_GT ||
@@ -558,15 +563,14 @@ done:
 	 * Ensure the read iterator does not return duplicates
 	 * and respects statement order.
 	 */
-	if (itr->last_stmt != NULL && itr->curr_stmt != NULL) {
-	       assert(vy_read_iterator_cmp_stmt(itr, itr->curr_stmt,
+	if (itr->last_stmt != NULL && next_key != NULL) {
+	       assert(vy_read_iterator_cmp_stmt(itr, next_key,
 						itr->last_stmt) > 0);
 	}
 #endif
-	if (itr->need_check_eq && itr->curr_stmt != NULL &&
-	    vy_stmt_compare(itr->curr_stmt, itr->key,
-			    itr->lsm->cmp_def) != 0)
-		itr->curr_stmt = NULL;
+	if (itr->need_check_eq && next_key != NULL &&
+	    vy_stmt_compare(next_key, itr->key, itr->lsm->cmp_def) != 0)
+		itr->front_id++;
 	return 0;
 }
 
@@ -684,7 +688,6 @@ vy_read_iterator_cleanup(struct vy_read_iterator *itr)
 		vy_run_iterator_close(&src->run_iterator);
 	}
 
-	itr->curr_stmt = NULL;
 	itr->txw_src = UINT32_MAX;
 	itr->cache_src = UINT32_MAX;
 	itr->mem_src = UINT32_MAX;
@@ -818,11 +821,6 @@ static NODISCARD int
 vy_read_iterator_apply_history(struct vy_read_iterator *itr,
 			       struct tuple **ret)
 {
-	if (itr->curr_stmt == NULL) {
-		*ret = NULL;
-		return 0;
-	}
-
 	struct vy_lsm *lsm = itr->lsm;
 	struct vy_history history;
 	vy_history_create(&history, &lsm->env->history_node_pool);
diff --git a/src/box/vy_read_iterator.h b/src/box/vy_read_iterator.h
index 07c6ef8f..2cac1087 100644
--- a/src/box/vy_read_iterator.h
+++ b/src/box/vy_read_iterator.h
@@ -92,8 +92,6 @@ struct vy_read_iterator {
 	uint32_t src_count;
 	/** Maximal capacity of the src array. */
 	uint32_t src_capacity;
-	/** Statement returned by the current merge source. */
-	struct tuple *curr_stmt;
 	/** Offset of the transaction write set source. */
 	uint32_t txw_src;
 	/** Offset of the cache source. */
@@ -105,8 +103,9 @@ struct vy_read_iterator {
 	/** Offset of the first skipped source. */
 	uint32_t skipped_src;
 	/**
-	 * front_id of the current source and all sources
-	 * that are on the same key.
+	 * vy_read_src::front_id <= front_id for any source.
+	 * vy_read_src::front_id == front_id iff the source
+	 * iterator is positioned at the next key.
 	 */
 	uint32_t front_id;
 	/**
-- 
2.11.0

  parent reply	other threads:[~2018-04-15 19:55 UTC|newest]

Thread overview: 17+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-04-15 19:55 [PATCH 00/12] vinyl: prepare read iterator for index rebuild Vladimir Davydov
2018-04-15 19:55 ` [PATCH 01/12] vinyl: rename vy_stmt_history to vy_history Vladimir Davydov
2018-04-15 19:55 ` [PATCH 02/12] vinyl: factor out vy_history_apply from vy_point_lookup_apply_history Vladimir Davydov
2018-05-14 18:19   ` [tarantool-patches] " Vladislav Shpilevoy
2018-04-15 19:55 ` [PATCH 03/12] vinyl: add vy_history_append_stmt helper Vladimir Davydov
2018-04-15 19:55 ` [PATCH 04/12] vinyl: zap iterator_src_type enum Vladimir Davydov
2018-04-15 19:55 ` [PATCH 05/12] vinyl: encapsulate key history with struct Vladimir Davydov
2018-04-15 19:55 ` [PATCH 06/12] vinyl: refine vy_history_cleanup Vladimir Davydov
2018-04-15 19:55 ` [PATCH 07/12] vinyl: move vy_history to its own source file Vladimir Davydov
2018-04-15 19:55 ` [PATCH 08/12] vinyl: use mempool for vy_history_node allocations Vladimir Davydov
2018-04-15 19:55 ` [PATCH 09/12] vinyl: consolidate skip optimization checks in read iterator Vladimir Davydov
2018-05-14 18:25   ` [tarantool-patches] " Vladislav Shpilevoy
2018-05-15 15:00     ` Vladimir Davydov
2018-04-15 19:55 ` [PATCH 10/12] vinyl: refactor vy_read_iterator_next Vladimir Davydov
2018-04-15 19:55 ` [PATCH 11/12] vinyl: make read iterator always return newest tuple version Vladimir Davydov
2018-04-15 19:55 ` Vladimir Davydov [this message]
2018-05-04 18:05 ` [tarantool-patches] Re: [PATCH 00/12] vinyl: prepare read iterator for index rebuild Vladislav Shpilevoy

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=18579339c8a5137c020753d917d47f86fb536ef9.1523820298.git.vdavydov.dev@gmail.com \
    --to=vdavydov.dev@gmail.com \
    --cc=kostja@tarantool.org \
    --cc=tarantool-patches@freelists.org \
    --subject='Re: [PATCH 12/12] vinyl: zap vy_read_iterator::curr_stmt' \
    /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