From 6a26a045809e1f2c3fb842637f5a94d9b8a3d9be Mon Sep 17 00:00:00 2001 From: Yingxin Cheng Date: Thu, 4 Feb 2021 14:41:27 +0800 Subject: [PATCH] crimson/onode-staged-tree: implement comparators for Cursor Signed-off-by: Yingxin Cheng --- .../onode_manager/staged-fltree/node.cc | 20 ++++++++++ .../onode_manager/staged-fltree/node.h | 2 + .../staged-fltree/stages/stage_types.h | 40 +++++++++---------- .../onode_manager/staged-fltree/tree.h | 30 ++++++++++---- 4 files changed, 65 insertions(+), 27 deletions(-) diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/node.cc b/src/crimson/os/seastore/onode_manager/staged-fltree/node.cc index ff9162cb237..8585f461a88 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node.cc +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node.cc @@ -91,6 +91,26 @@ void tree_cursor_t::assert_next_to( #endif } +MatchKindCMP tree_cursor_t::compare_to( + const tree_cursor_t& o, value_magic_t magic) const +{ + // singleton + if (this == &o) { + return MatchKindCMP::EQ; + } + + MatchKindCMP ret; + if (ref_leaf_node == o.ref_leaf_node) { + ret = position.compare_to(o.position); + } else { + auto key = get_key_view(magic); + auto o_key = o.get_key_view(magic); + ret = key.compare_to(o_key); + } + assert(ret != MatchKindCMP::EQ); + return ret; +} + tree_cursor_t::future<> tree_cursor_t::extend_value(context_t c, value_size_t extend_size) { diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/node.h b/src/crimson/os/seastore/onode_manager/staged-fltree/node.h index 5c98addf2b7..9c9c02e103c 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node.h @@ -100,6 +100,8 @@ class tree_cursor_t final /// Check that this is next to prv void assert_next_to(const tree_cursor_t&, value_magic_t) const; + MatchKindCMP compare_to(const tree_cursor_t&, value_magic_t) const; + // public to Value /// Get the latest value_header_t pointer for read. diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/stage_types.h b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/stage_types.h index 6081cb263ef..2a7de82f524 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/stage_types.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/stage_types.h @@ -149,21 +149,21 @@ struct staged_position_t { } } - int cmp(const me_t& o) const { + MatchKindCMP compare_to(const me_t& o) const { if (index > o.index) { - return 1; + return MatchKindCMP::GT; } else if (index < o.index) { - return -1; + return MatchKindCMP::LT; } else { - return nxt.cmp(o.nxt); + return nxt.compare_to(o.nxt); } } - bool operator>(const me_t& o) const { return cmp(o) > 0; } - bool operator>=(const me_t& o) const { return cmp(o) >= 0; } - bool operator<(const me_t& o) const { return cmp(o) < 0; } - bool operator<=(const me_t& o) const { return cmp(o) <= 0; } - bool operator==(const me_t& o) const { return cmp(o) == 0; } - bool operator!=(const me_t& o) const { return cmp(o) != 0; } + bool operator>(const me_t& o) const { return (int)compare_to(o) > 0; } + bool operator>=(const me_t& o) const { return (int)compare_to(o) >= 0; } + bool operator<(const me_t& o) const { return (int)compare_to(o) < 0; } + bool operator<=(const me_t& o) const { return (int)compare_to(o) <= 0; } + bool operator==(const me_t& o) const { return (int)compare_to(o) == 0; } + bool operator!=(const me_t& o) const { return (int)compare_to(o) != 0; } void assert_next_to(const me_t& prv) const { #ifndef NDEBUG @@ -243,21 +243,21 @@ struct staged_position_t { return index; } - int cmp(const staged_position_t& o) const { + MatchKindCMP compare_to(const staged_position_t& o) const { if (index > o.index) { - return 1; + return MatchKindCMP::GT; } else if (index < o.index) { - return -1; + return MatchKindCMP::LT; } else { - return 0; + return MatchKindCMP::EQ; } } - bool operator>(const me_t& o) const { return cmp(o) > 0; } - bool operator>=(const me_t& o) const { return cmp(o) >= 0; } - bool operator<(const me_t& o) const { return cmp(o) < 0; } - bool operator<=(const me_t& o) const { return cmp(o) <= 0; } - bool operator==(const me_t& o) const { return cmp(o) == 0; } - bool operator!=(const me_t& o) const { return cmp(o) != 0; } + bool operator>(const me_t& o) const { return (int)compare_to(o) > 0; } + bool operator>=(const me_t& o) const { return (int)compare_to(o) >= 0; } + bool operator<(const me_t& o) const { return (int)compare_to(o) < 0; } + bool operator<=(const me_t& o) const { return (int)compare_to(o) <= 0; } + bool operator==(const me_t& o) const { return (int)compare_to(o) == 0; } + bool operator!=(const me_t& o) const { return (int)compare_to(o) != 0; } me_t& operator-=(const me_t& o) { assert(is_valid_index(o.index)); diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/tree.h b/src/crimson/os/seastore/onode_manager/staged-fltree/tree.h index 377d86ae5e2..f4c1d5f966d 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/tree.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/tree.h @@ -89,12 +89,12 @@ class Btree { *p_tree->nm, p_tree->value_builder, p_cursor); } - bool operator==(const Cursor& x) const { - return p_cursor == x.p_cursor; - } - bool operator!=(const Cursor& x) const { - return !(*this == x); - } + bool operator>(const Cursor& o) const { return (int)compare_to(o) > 0; } + bool operator>=(const Cursor& o) const { return (int)compare_to(o) >= 0; } + bool operator<(const Cursor& o) const { return (int)compare_to(o) < 0; } + bool operator<=(const Cursor& o) const { return (int)compare_to(o) <= 0; } + bool operator==(const Cursor& o) const { return (int)compare_to(o) != 0; } + bool operator!=(const Cursor& o) const { return (int)compare_to(o) == 0; } btree_future get_next(Transaction& t) { assert(!is_end()); @@ -103,7 +103,9 @@ class Btree { ).safe_then([this_obj] (Ref next_cursor) { next_cursor->assert_next_to( *this_obj.p_cursor, this_obj.p_tree->value_builder.get_header_magic()); - return Cursor{this_obj.p_tree, next_cursor}; + auto ret = Cursor{this_obj.p_tree, next_cursor}; + assert(this_obj < ret); + return ret; }); } @@ -117,6 +119,20 @@ class Btree { } Cursor(Btree* p_tree) : p_tree{p_tree} {} + MatchKindCMP compare_to(const Cursor& o) const { + assert(p_tree == o.p_tree); + if (p_cursor && o.p_cursor) { + return p_cursor->compare_to( + *o.p_cursor, p_tree->value_builder.get_header_magic()); + } else if (!p_cursor && !o.p_cursor) { + return MatchKindCMP::EQ; + } else if (!p_cursor) { + return MatchKindCMP::GT; + } else { // !o.p_cursor + return MatchKindCMP::LT; + } + } + static Cursor make_end(Btree* p_tree) { return {p_tree}; } -- 2.39.5