[PATCH v3 3/7] lib: introduce BPS_TREE_IDENTICAL custom comparator
Kirill Shcherbatov
kshcherbatov at tarantool.org
Fri Feb 22 18:42:28 MSK 2019
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
More information about the Tarantool-patches
mailing list