[PATCH v3 3/7] lib: introduce BPS_TREE_IDENTICAL custom comparator

[Kirill Shcherbatov <kshcherbatov@tarantool.org>]

Introduce a macro BPS_TREE_IDENTICAL 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       | 82 +++++++++++++++++++++++-----------
 test/unit/bps_tree_iterator.cc | 16 ++++---
 2 files changed, 65 insertions(+), 33 deletions(-)

diff --git a/src/lib/salad/bps_tree.h b/src/lib/salad/bps_tree.h
index 09c3338f1..adf3addfb 100644
--- a/src/lib/salad/bps_tree.h
+++ b/src/lib/salad/bps_tree.h
@@ -1035,6 +1035,14 @@ struct bps_leaf_path_elem {
 	bps_tree_pos_t max_elem_pos;
 };
 
+/**
+ * Test if bps_tree_elem_t a and b represent exactly the
+ * same data.
+ */
+#ifndef BPS_TREE_IDENTICAL
+#define BPS_TREE_IDENTICAL(a, b) (a == b)
+#endif
+
 /**
  * @brief Tree construction. Fills struct bps_tree members.
  * @param tree - pointer to a tree
@@ -4592,7 +4600,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_IDENTICAL(inner->elems[i], calc_max_elem))
 				result |= 0x4000;
 		}
 		if (block->size > 1) {
@@ -4651,7 +4659,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_IDENTICAL(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 +5025,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_IDENTICAL(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_IDENTICAL(mb, elem)) {
 						result |= (1 << 5);
 						assert(!assertme);
 					}
+				}
 
 				c = 0;
 				for (unsigned int u = 0;
@@ -5113,16 +5128,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_IDENTICAL(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_IDENTICAL(mb, elem)) {
 						result |= (1 << 7);
 						assert(!assertme);
 					}
+				}
 
 				c = 0;
 				for (unsigned int u = 0;
@@ -5224,21 +5245,24 @@ 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_IDENTICAL(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_IDENTICAL(mb,
+									elem)) {
 							result |= (1 << 9);
 							assert(!assertme);
 						}
-
+					}
 					c = 0;
 					for (unsigned int v = 0;
 						v < (unsigned int) a.header.size;
@@ -5340,20 +5364,24 @@ 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_IDENTICAL(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_IDENTICAL(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..71dde7d78 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_IDENTICAL(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,12 @@ 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 +505,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 +527,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