Tarantool development patches archive
 help / color / mirror / Atom feed
From: Kirill Shcherbatov <kshcherbatov@tarantool.org>
To: tarantool-patches@freelists.org, vdavydov.dev@gmail.com
Cc: Kirill Shcherbatov <kshcherbatov@tarantool.org>
Subject: [PATCH v1 1/4] lib: introduce BPS_TREE_EQUAL custom comparator
Date: Tue,  5 Feb 2019 14:58:36 +0300	[thread overview]
Message-ID: <11600ac4b30c072b5b8c4132a658aaff13083504.1549367041.git.kshcherbatov@tarantool.org> (raw)
In-Reply-To: <cover.1549367041.git.kshcherbatov@tarantool.org>

Introduce a macro BPS_TREE_EQUAL for BPS TREE class. This makes
possible to define custom comparators for stucture-based leafs.
Previously, a C++ comparison operator "!=" override was used for
this purpose. Due to the fact that we are not going to rework on
C++ C-only components of Tarantool like memtx_tree, we needed a
way to make complex structures comparisons using preprocessor.

Needed for #3961
---
 src/lib/salad/bps_tree.h       | 74 +++++++++++++++++++++-------------
 test/unit/bps_tree_iterator.cc | 15 ++++---
 2 files changed, 56 insertions(+), 33 deletions(-)

diff --git a/src/lib/salad/bps_tree.h b/src/lib/salad/bps_tree.h
index 8d1a62108..1419af3f7 100644
--- a/src/lib/salad/bps_tree.h
+++ b/src/lib/salad/bps_tree.h
@@ -1035,6 +1035,10 @@ struct bps_leaf_path_elem {
 	bps_tree_pos_t max_elem_pos;
 };
 
+#ifndef BPS_TREE_EQUAL
+#define BPS_TREE_EQUAL(a, b) (a == b)
+#endif
+
 /**
  * @brief Tree construction. Fills struct bps_tree members.
  * @param tree - pointer to a tree
@@ -4592,7 +4596,7 @@ bps_tree_debug_check_block(const struct bps_tree *tree, struct bps_block *block,
 						       inner->child_ids[i]);
 			bps_tree_elem_t calc_max_elem =
 				bps_tree_debug_find_max_elem(tree, tmp_block);
-			if (inner->elems[i] != calc_max_elem)
+			if (!BPS_TREE_EQUAL(inner->elems[i], calc_max_elem))
 				result |= 0x4000;
 		}
 		if (block->size > 1) {
@@ -4651,7 +4655,8 @@ bps_tree_debug_check(const struct bps_tree *tree)
 		return result;
 	}
 	struct bps_block *root = bps_tree_root(tree);
-	if (tree->max_elem != bps_tree_debug_find_max_elem(tree, root))
+	bps_tree_elem_t elem = bps_tree_debug_find_max_elem(tree, root);
+	if (!BPS_TREE_EQUAL(tree->max_elem, elem))
 		result |= 0x8;
 	size_t calc_count = 0;
 	bps_tree_block_id_t expected_prev_id = (bps_tree_block_id_t)(-1);
@@ -5016,16 +5021,22 @@ bps_tree_debug_check_move_to_right_leaf(struct bps_tree *tree, bool assertme)
 					assert(!assertme);
 				}
 
-				if (a.header.size)
-					if (ma != a.elems[a.header.size - 1]) {
+				if (a.header.size) {
+					bps_tree_elem_t elem =
+						a.elems[a.header.size - 1];
+					if (!BPS_TREE_EQUAL(ma, elem)) {
 						result |= (1 << 5);
 						assert(!assertme);
 					}
-				if (b.header.size)
-					if (mb != b.elems[b.header.size - 1]) {
+				}
+				if (b.header.size) {
+					bps_tree_elem_t elem =
+						b.elems[b.header.size - 1];
+					if (!BPS_TREE_EQUAL(mb, elem)) {
 						result |= (1 << 5);
 						assert(!assertme);
 					}
+				}
 
 				c = 0;
 				for (unsigned int u = 0;
@@ -5113,16 +5124,22 @@ bps_tree_debug_check_move_to_left_leaf(struct bps_tree *tree, bool assertme)
 					assert(!assertme);
 				}
 
-				if (a.header.size)
-					if (ma != a.elems[a.header.size - 1]) {
+				if (a.header.size) {
+					bps_tree_elem_t elem =
+						a.elems[a.header.size - 1];
+					if (!BPS_TREE_EQUAL(ma, elem)) {
 						result |= (1 << 7);
 						assert(!assertme);
 					}
-				if (b.header.size)
-					if (mb != b.elems[b.header.size - 1]) {
+				}
+				if (b.header.size) {
+					bps_tree_elem_t elem =
+						b.elems[b.header.size - 1];
+					if (!BPS_TREE_EQUAL(mb, elem)) {
 						result |= (1 << 7);
 						assert(!assertme);
 					}
+				}
 
 				c = 0;
 				for (unsigned int u = 0;
@@ -5224,21 +5241,22 @@ bps_tree_debug_check_insert_and_move_to_right_leaf(struct bps_tree *tree,
 						assert(!assertme);
 					}
 
-					if (i - u + 1)
-						if (ma
-							!= a.elems[a.header.size
-								- 1]) {
+					if (i - u + 1) {
+						bps_tree_elem_t elem =
+							a.elems[a.header.size - 1];
+						if (!BPS_TREE_EQUAL(ma, elem)) {
 							result |= (1 << 9);
 							assert(!assertme);
 						}
-					if (j + u)
-						if (mb
-							!= b.elems[b.header.size
-								- 1]) {
+					}
+					if (j + u) {
+						bps_tree_elem_t elem =
+							b.elems[b.header.size - 1];
+						if (!BPS_TREE_EQUAL(mb, elem)) {
 							result |= (1 << 9);
 							assert(!assertme);
 						}
-
+					}
 					c = 0;
 					for (unsigned int v = 0;
 						v < (unsigned int) a.header.size;
@@ -5340,20 +5358,22 @@ bps_tree_debug_check_insert_and_move_to_left_leaf(struct bps_tree *tree,
 						assert(!assertme);
 					}
 
-					if (i + u)
-						if (ma
-							!= a.elems[a.header.size
-								- 1]) {
+					if (i + u) {
+						bps_tree_elem_t elem =
+							a.elems[a.header.size - 1];
+						if (!BPS_TREE_EQUAL(ma, elem)) {
 							result |= (1 << 11);
 							assert(!assertme);
 						}
-					if (j - u + 1)
-						if (mb
-							!= b.elems[b.header.size
-								- 1]) {
+					}
+					if (j - u + 1) {
+						bps_tree_elem_t elem =
+							b.elems[b.header.size - 1];
+						if (!BPS_TREE_EQUAL(mb, elem)) {
 							result |= (1 << 11);
 							assert(!assertme);
 						}
+					}
 
 					c = 0;
 					for (unsigned int v = 0;
diff --git a/test/unit/bps_tree_iterator.cc b/test/unit/bps_tree_iterator.cc
index 3c2d7f7c4..318aac1ec 100644
--- a/test/unit/bps_tree_iterator.cc
+++ b/test/unit/bps_tree_iterator.cc
@@ -10,18 +10,16 @@
 struct elem_t {
 	long first;
 	long second;
-	bool operator!= (const struct elem_t& another) const
-	{
-		return first != another.first || second != another.second;
-	}
 };
 
+static bool equal(const elem_t &a, const elem_t &b);
 static int compare(const elem_t &a, const elem_t &b);
 static int compare_key(const elem_t &a, long b);
 
 #define BPS_TREE_NAME test
 #define BPS_TREE_BLOCK_SIZE 128 /* value is to low specially for tests */
 #define BPS_TREE_EXTENT_SIZE 1024 /* value is to low specially for tests */
+#define BPS_TREE_EQUAL(a, b) equal(a, b)
 #define BPS_TREE_COMPARE(a, b, arg) compare(a, b)
 #define BPS_TREE_COMPARE_KEY(a, b, arg) compare_key(a, b)
 #define bps_tree_elem_t struct elem_t
@@ -29,6 +27,11 @@ static int compare_key(const elem_t &a, long b);
 #define bps_tree_arg_t int
 #include "salad/bps_tree.h"
 
+static bool equal(const elem_t &a, const elem_t &b)
+{
+	return a.first == b.first && a.second == b.second;
+}
+
 static int compare(const elem_t &a, const elem_t &b)
 {
 	return a.first < b.first ? -1 : a.first > b.first ? 1 :
@@ -501,7 +504,7 @@ iterator_freeze_check()
 		}
 		int tested_count = 0;
 		while ((e = test_iterator_get_elem(&tree, &iterator1))) {
-			if (*e != comp_buf1[tested_count]) {
+			if (!equal(*e, comp_buf1[tested_count])) {
 				fail("version restore failed (1)", "true");
 			}
 			tested_count++;
@@ -523,7 +526,7 @@ iterator_freeze_check()
 
 		tested_count = 0;
 		while ((e = test_iterator_get_elem(&tree, &iterator2))) {
-			if (*e != comp_buf1[tested_count]) {
+			if (!equal(*e, comp_buf1[tested_count])) {
 				fail("version restore failed (1)", "true");
 			}
 			tested_count++;
-- 
2.20.1

  reply	other threads:[~2019-02-05 11:58 UTC|newest]

Thread overview: 9+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-02-05 11:58 [PATCH v1 0/4] box: introduce hint option for memtx tree index Kirill Shcherbatov
2019-02-05 11:58 ` Kirill Shcherbatov [this message]
2019-02-11 15:46   ` [PATCH v1 1/4] lib: introduce BPS_TREE_EQUAL custom comparator Vladimir Davydov
2019-02-05 11:58 ` [PATCH v1 2/4] box: rework memtx_tree class to be reusable Kirill Shcherbatov
2019-02-11 15:49   ` Vladimir Davydov
2019-02-05 11:58 ` [PATCH v1 3/4] box: introduce tuple compare hint Kirill Shcherbatov
2019-02-11 15:57   ` Vladimir Davydov
2019-02-05 11:58 ` [PATCH v1 4/4] box: introduce hint option for memtx tree index Kirill Shcherbatov
2019-02-11 16:12   ` 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=11600ac4b30c072b5b8c4132a658aaff13083504.1549367041.git.kshcherbatov@tarantool.org \
    --to=kshcherbatov@tarantool.org \
    --cc=tarantool-patches@freelists.org \
    --cc=vdavydov.dev@gmail.com \
    --subject='Re: [PATCH v1 1/4] lib: introduce BPS_TREE_EQUAL custom comparator' \
    /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