From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Kirill Shcherbatov Subject: [PATCH v1 1/4] lib: introduce BPS_TREE_EQUAL custom comparator Date: Tue, 5 Feb 2019 14:58:36 +0300 Message-Id: <11600ac4b30c072b5b8c4132a658aaff13083504.1549367041.git.kshcherbatov@tarantool.org> In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit To: tarantool-patches@freelists.org, vdavydov.dev@gmail.com Cc: Kirill Shcherbatov List-ID: 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