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

  • From: Kirill Shcherbatov <kshcherbatov@xxxxxxxxxxxxx>
  • To: tarantool-patches@xxxxxxxxxxxxx, vdavydov.dev@xxxxxxxxx
  • Date: Fri, 22 Feb 2019 18:42:28 +0300

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


Other related posts: