From 8e0903378a5003e0ebd8150116bf60c851fb012e Mon Sep 17 00:00:00 2001 From: Yingxin Cheng Date: Thu, 15 Apr 2021 14:53:51 +0800 Subject: [PATCH] crimson/onode-staged-tree: test merge in leaf node Signed-off-by: Yingxin Cheng --- .../onode_manager/staged-fltree/node.cc | 31 +- .../onode_manager/staged-fltree/node.h | 3 + .../staged-fltree/node_extent_manager/dummy.h | 2 + .../onode_manager/staged-fltree/tree.h | 3 +- .../seastore/onode_tree/test_staged_fltree.cc | 296 ++++++++++++------ 5 files changed, 223 insertions(+), 112 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 c04580d4191..1e92555de48 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node.cc +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node.cc @@ -95,12 +95,17 @@ void tree_cursor_t::assert_next_to( #endif } +template tree_cursor_t::future> tree_cursor_t::erase(context_t c, bool get_next) { assert(is_tracked()); - return ref_leaf_node->erase(c, position, get_next); + return ref_leaf_node->erase(c, position, get_next); } +template tree_cursor_t::future> +tree_cursor_t::erase(context_t, bool); +template tree_cursor_t::future> +tree_cursor_t::erase(context_t, bool); MatchKindCMP tree_cursor_t::compare_to( const tree_cursor_t& o, value_magic_t magic) const @@ -488,18 +493,21 @@ Node::get_next_cursor_from_parent(context_t c) return parent_info().ptr->get_next_cursor(c, parent_info().position); } +template node_future<> Node::try_merge_adjacent(context_t c, bool update_parent_index) { impl->validate_non_empty(); assert(!is_root()); Ref this_ref = this; - if (!impl->is_size_underflow()) { - if (update_parent_index) { - return fix_parent_index(c); - } else { - parent_info().ptr->validate_child_tracked(*this); - return node_ertr::now(); + if constexpr (!FORCE_MERGE) { + if (!impl->is_size_underflow()) { + if (update_parent_index) { + return fix_parent_index(c); + } else { + parent_info().ptr->validate_child_tracked(*this); + return node_ertr::now(); + } } } @@ -583,6 +591,8 @@ Node::try_merge_adjacent(context_t c, bool update_parent_index) // XXX: rebalance }); } +template node_future<> Node::try_merge_adjacent(context_t, bool); +template node_future<> Node::try_merge_adjacent(context_t, bool); node_future<> Node::erase_node(context_t c, Ref&& this_ref) { @@ -1637,6 +1647,7 @@ LeafNode::get_next_cursor(context_t c, const search_position_t& pos) } } +template node_future> LeafNode::erase(context_t c, const search_position_t& pos, bool get_next) { @@ -1702,13 +1713,17 @@ LeafNode::erase(context_t c, const search_position_t& pos, bool get_next) next_pos.is_end() ? update_parent_index = true : update_parent_index = false; } - return try_merge_adjacent(c, update_parent_index); + return try_merge_adjacent(c, update_parent_index); } }).safe_then([next_cursor] { return next_cursor; }); }); } +template node_future> +LeafNode::erase(context_t, const search_position_t&, bool); +template node_future> +LeafNode::erase(context_t, const search_position_t&, bool); node_future<> LeafNode::extend_value( context_t c, const search_position_t& pos, 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 e5161d8e8f4..0cb6c2289fb 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node.h @@ -129,6 +129,7 @@ class tree_cursor_t final void assert_next_to(const tree_cursor_t&, value_magic_t) const; /// Erases the key-value pair from tree. + template future> erase(context_t, bool get_next); MatchKindCMP compare_to(const tree_cursor_t&, value_magic_t) const; @@ -431,6 +432,7 @@ class Node node_future<> apply_split_to_parent(context_t, Ref, bool); node_future> get_next_cursor_from_parent(context_t); + template node_future<> try_merge_adjacent(context_t, bool); node_future<> erase_node(context_t, Ref&&); node_future<> fix_parent_index(context_t); @@ -626,6 +628,7 @@ class LeafNode final : public Node { * If get_next is true, returns the cursor pointing to the next key-value * pair that followed the erased element, which can be nullptr if is end. */ + template node_future> erase( context_t, const search_position_t&, bool get_next); diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager/dummy.h b/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager/dummy.h index ad86a3df610..297cd98b7c0 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager/dummy.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager/dummy.h @@ -71,6 +71,8 @@ class DummyNodeExtentManager final: public NodeExtentManager { static constexpr size_t ALIGNMENT = 4096; public: ~DummyNodeExtentManager() override = default; + std::size_t size() const { return allocate_map.size(); } + protected: bool is_read_isolated() const override { return false; } 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 06e9ca11429..62db82fc7fe 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/tree.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/tree.h @@ -110,10 +110,11 @@ class Btree { }); } + template btree_future erase(Transaction& t) { assert(!is_end()); auto this_obj = *this; - return p_cursor->erase(p_tree->get_context(t), true + return p_cursor->erase(p_tree->get_context(t), true ).safe_then([this_obj, this] (Ref next_cursor) { assert(p_cursor->is_invalid()); if (next_cursor) { diff --git a/src/test/crimson/seastore/onode_tree/test_staged_fltree.cc b/src/test/crimson/seastore/onode_tree/test_staged_fltree.cc index da86ef83625..3b8d53eb3c1 100644 --- a/src/test/crimson/seastore/onode_tree/test_staged_fltree.cc +++ b/src/test/crimson/seastore/onode_tree/test_staged_fltree.cc @@ -11,6 +11,7 @@ #include "crimson/common/log.h" #include "crimson/os/seastore/onode_manager/staged-fltree/node.h" #include "crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager.h" +#include "crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager/dummy.h" #include "crimson/os/seastore/onode_manager/staged-fltree/node_layout.h" #include "crimson/os/seastore/onode_manager/staged-fltree/tree.h" #include "crimson/os/seastore/onode_manager/staged-fltree/tree_utils.h" @@ -23,6 +24,7 @@ using namespace crimson::os::seastore::onode; namespace { constexpr bool IS_DUMMY_SYNC = false; + using DummyManager = DummyNodeExtentManager; [[maybe_unused]] seastar::logger& logger() { return crimson::get_logger(ceph_subsys_test); @@ -486,25 +488,35 @@ class TestTree { }); } - seastar::future<> split(const ghobject_t& key, const test_item_t& value, - const split_expectation_t& expected) { - return seastar::async([this, key, value, expected] { - TestBtree tree_clone(NodeExtentManager::create_dummy(IS_DUMMY_SYNC)); + seastar::future<> split_merge( + const ghobject_t& key, + const test_item_t& value, + const split_expectation_t& expected, + std::optional next_key) { + return seastar::async([this, key, value, expected, next_key] { + // clone + auto ref_dummy = NodeExtentManager::create_dummy(IS_DUMMY_SYNC); + auto p_dummy = static_cast(ref_dummy.get()); + TestBtree tree_clone(std::move(ref_dummy)); auto ref_t_clone = make_test_transaction(); Transaction& t_clone = *ref_t_clone; tree_clone.test_clone_from(t_clone, t, tree).unsafe_get0(); - logger().info("insert {}:", key_hobj_t(key)); + // insert and split + logger().info("\n\nINSERT-SPLIT {}:", key_hobj_t(key)); auto [cursor, success] = tree_clone.insert( t_clone, key, {value.get_payload_size()}).unsafe_get0(); initialize_cursor_from_item(t, key, value, cursor, success); - std::ostringstream oss; - tree_clone.dump(t_clone, oss); - logger().info("dump new root:\n{}", oss.str()); + { + std::ostringstream oss; + tree_clone.dump(t_clone, oss); + logger().info("dump new root:\n{}", oss.str()); + } EXPECT_EQ(tree_clone.height(t_clone).unsafe_get0(), 2); - for (auto& [k, v, c] : insert_history) { + for (auto& [k, val] : insert_history) { + auto& [v, c] = val; auto result = tree_clone.find(t_clone, k).unsafe_get0(); EXPECT_NE(result, tree_clone.end()); validate_cursor_from_item(k, v, result); @@ -513,6 +525,39 @@ class TestTree { EXPECT_NE(result, tree_clone.end()); validate_cursor_from_item(key, value, result); EXPECT_TRUE(last_split.match(expected)); + EXPECT_EQ(p_dummy->size(), 3); + + // erase and merge + logger().info("\n\nERASE-MERGE {}:", key_hobj_t(key)); + auto nxt_cursor = cursor.erase(t_clone).unsafe_get0(); + + { + // track root again to dump + auto begin = tree_clone.begin(t_clone).unsafe_get0(); + std::ignore = begin; + std::ostringstream oss; + tree_clone.dump(t_clone, oss); + logger().info("dump root:\n{}", oss.str()); + } + + if (next_key.has_value()) { + auto found = insert_history.find(*next_key); + ceph_assert(found != insert_history.end()); + validate_cursor_from_item( + *next_key, std::get<0>(found->second), nxt_cursor); + } else { + EXPECT_TRUE(nxt_cursor.is_end()); + } + + for (auto& [k, val] : insert_history) { + auto& [v, c] = val; + auto result = tree_clone.find(t_clone, k).unsafe_get0(); + EXPECT_NE(result, tree_clone.end()); + validate_cursor_from_item(k, v, result); + } + + EXPECT_EQ(tree_clone.height(t_clone).unsafe_get0(), 1); + EXPECT_EQ(p_dummy->size(), 1); }); } @@ -526,7 +571,7 @@ class TestTree { auto [cursor, success] = tree.insert( t, key, {value.get_payload_size()}).unsafe_get0(); initialize_cursor_from_item(t, key, value, cursor, success); - insert_history.emplace_back(key, value, cursor); + insert_history.emplace(key, std::make_tuple(value, cursor)); }); } @@ -537,13 +582,13 @@ class TestTree { context_t c; TestBtree tree; Values values; - std::vector> insert_history; + std::map> insert_history; }; struct c_dummy_test_t : public seastar_test_suite_t {}; -TEST_F(c_dummy_test_t, 4_split_leaf_node) +TEST_F(c_dummy_test_t, 4_split_merge_leaf_node) { run_async([this] { { @@ -553,119 +598,158 @@ TEST_F(c_dummy_test_t, 4_split_leaf_node) auto value = test.create_value(1144); logger().info("\n---------------------------------------------" "\nsplit at stage 2; insert to left front at stage 2, 1, 0\n"); - test.split(make_ghobj(1, 1, 1, "ns3", "oid3", 3, 3), value, - {2u, 2u, true, InsertType::BEGIN}).get0(); - test.split(make_ghobj(2, 2, 2, "ns1", "oid1", 3, 3), value, - {2u, 1u, true, InsertType::BEGIN}).get0(); - test.split(make_ghobj(2, 2, 2, "ns2", "oid2", 1, 1), value, - {2u, 0u, true, InsertType::BEGIN}).get0(); + test.split_merge(make_ghobj(1, 1, 1, "ns3", "oid3", 3, 3), value, + {2u, 2u, true, InsertType::BEGIN}, + {make_ghobj(2, 2, 2, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(2, 2, 2, "ns1", "oid1", 3, 3), value, + {2u, 1u, true, InsertType::BEGIN}, + {make_ghobj(2, 2, 2, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(2, 2, 2, "ns2", "oid2", 1, 1), value, + {2u, 0u, true, InsertType::BEGIN}, + {make_ghobj(2, 2, 2, "ns2", "oid2", 2, 2)}).get0(); logger().info("\n---------------------------------------------" "\nsplit at stage 2; insert to left back at stage 0, 1, 2, 1, 0\n"); - test.split(make_ghobj(2, 2, 2, "ns4", "oid4", 5, 5), value, - {2u, 0u, true, InsertType::LAST}).get0(); - test.split(make_ghobj(2, 2, 2, "ns5", "oid5", 3, 3), value, - {2u, 1u, true, InsertType::LAST}).get0(); - test.split(make_ghobj(2, 3, 3, "ns3", "oid3", 3, 3), value, - {2u, 2u, true, InsertType::LAST}).get0(); - test.split(make_ghobj(3, 3, 3, "ns1", "oid1", 3, 3), value, - {2u, 1u, true, InsertType::LAST}).get0(); - test.split(make_ghobj(3, 3, 3, "ns2", "oid2", 1, 1), value, - {2u, 0u, true, InsertType::LAST}).get0(); + test.split_merge(make_ghobj(2, 2, 2, "ns4", "oid4", 5, 5), value, + {2u, 0u, true, InsertType::LAST}, + {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(2, 2, 2, "ns5", "oid5", 3, 3), value, + {2u, 1u, true, InsertType::LAST}, + {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(2, 3, 3, "ns3", "oid3", 3, 3), value, + {2u, 2u, true, InsertType::LAST}, + {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns1", "oid1", 3, 3), value, + {2u, 1u, true, InsertType::LAST}, + {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns2", "oid2", 1, 1), value, + {2u, 0u, true, InsertType::LAST}, + {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0(); auto value0 = test.create_value(1416); logger().info("\n---------------------------------------------" "\nsplit at stage 2; insert to right front at stage 0, 1, 2, 1, 0\n"); - test.split(make_ghobj(3, 3, 3, "ns4", "oid4", 5, 5), value0, - {2u, 0u, false, InsertType::BEGIN}).get0(); - test.split(make_ghobj(3, 3, 3, "ns5", "oid5", 3, 3), value0, - {2u, 1u, false, InsertType::BEGIN}).get0(); - test.split(make_ghobj(3, 4, 4, "ns3", "oid3", 3, 3), value0, - {2u, 2u, false, InsertType::BEGIN}).get0(); - test.split(make_ghobj(4, 4, 4, "ns1", "oid1", 3, 3), value0, - {2u, 1u, false, InsertType::BEGIN}).get0(); - test.split(make_ghobj(4, 4, 4, "ns2", "oid2", 1, 1), value0, - {2u, 0u, false, InsertType::BEGIN}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns4", "oid4", 5, 5), value0, + {2u, 0u, false, InsertType::BEGIN}, + {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns5", "oid5", 3, 3), value0, + {2u, 1u, false, InsertType::BEGIN}, + {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(3, 4, 4, "ns3", "oid3", 3, 3), value0, + {2u, 2u, false, InsertType::BEGIN}, + {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(4, 4, 4, "ns1", "oid1", 3, 3), value0, + {2u, 1u, false, InsertType::BEGIN}, + {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(4, 4, 4, "ns2", "oid2", 1, 1), value0, + {2u, 0u, false, InsertType::BEGIN}, + {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0(); logger().info("\n---------------------------------------------" "\nsplit at stage 2; insert to right back at stage 0, 1, 2\n"); - test.split(make_ghobj(4, 4, 4, "ns4", "oid4", 5, 5), value0, - {2u, 0u, false, InsertType::LAST}).get0(); - test.split(make_ghobj(4, 4, 4, "ns5", "oid5", 3, 3), value0, - {2u, 1u, false, InsertType::LAST}).get0(); - test.split(make_ghobj(5, 5, 5, "ns3", "oid3", 3, 3), value0, - {2u, 2u, false, InsertType::LAST}).get0(); + test.split_merge(make_ghobj(4, 4, 4, "ns4", "oid4", 5, 5), value0, + {2u, 0u, false, InsertType::LAST}, + std::nullopt).get0(); + test.split_merge(make_ghobj(4, 4, 4, "ns5", "oid5", 3, 3), value0, + {2u, 1u, false, InsertType::LAST}, + std::nullopt).get0(); + test.split_merge(make_ghobj(5, 5, 5, "ns3", "oid3", 3, 3), value0, + {2u, 2u, false, InsertType::LAST}, + std::nullopt).get0(); auto value1 = test.create_value(316); logger().info("\n---------------------------------------------" "\nsplit at stage 1; insert to left middle at stage 0, 1, 2, 1, 0\n"); - test.split(make_ghobj(2, 2, 2, "ns4", "oid4", 5, 5), value1, - {1u, 0u, true, InsertType::MID}).get0(); - test.split(make_ghobj(2, 2, 2, "ns5", "oid5", 3, 3), value1, - {1u, 1u, true, InsertType::MID}).get0(); - test.split(make_ghobj(2, 2, 3, "ns3", "oid3", 3, 3), value1, - {1u, 2u, true, InsertType::MID}).get0(); - test.split(make_ghobj(3, 3, 3, "ns1", "oid1", 3, 3), value1, - {1u, 1u, true, InsertType::MID}).get0(); - test.split(make_ghobj(3, 3, 3, "ns2", "oid2", 1, 1), value1, - {1u, 0u, true, InsertType::MID}).get0(); + test.split_merge(make_ghobj(2, 2, 2, "ns4", "oid4", 5, 5), value1, + {1u, 0u, true, InsertType::MID}, + {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(2, 2, 2, "ns5", "oid5", 3, 3), value1, + {1u, 1u, true, InsertType::MID}, + {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(2, 2, 3, "ns3", "oid3", 3, 3), value1, + {1u, 2u, true, InsertType::MID}, + {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns1", "oid1", 3, 3), value1, + {1u, 1u, true, InsertType::MID}, + {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns2", "oid2", 1, 1), value1, + {1u, 0u, true, InsertType::MID}, + {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0(); logger().info("\n---------------------------------------------" "\nsplit at stage 1; insert to left back at stage 0, 1, 0\n"); - test.split(make_ghobj(3, 3, 3, "ns2", "oid2", 5, 5), value1, - {1u, 0u, true, InsertType::LAST}).get0(); - test.split(make_ghobj(3, 3, 3, "ns2", "oid3", 3, 3), value1, - {1u, 1u, true, InsertType::LAST}).get0(); - test.split(make_ghobj(3, 3, 3, "ns3", "oid3", 1, 1), value1, - {1u, 0u, true, InsertType::LAST}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns2", "oid2", 5, 5), value1, + {1u, 0u, true, InsertType::LAST}, + {make_ghobj(3, 3, 3, "ns3", "oid3", 2, 2)}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns2", "oid3", 3, 3), value1, + {1u, 1u, true, InsertType::LAST}, + {make_ghobj(3, 3, 3, "ns3", "oid3", 2, 2)}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns3", "oid3", 1, 1), value1, + {1u, 0u, true, InsertType::LAST}, + {make_ghobj(3, 3, 3, "ns3", "oid3", 2, 2)}).get0(); auto value2 = test.create_value(452); logger().info("\n---------------------------------------------" "\nsplit at stage 1; insert to right front at stage 0, 1, 0\n"); - test.split(make_ghobj(3, 3, 3, "ns3", "oid3", 5, 5), value2, - {1u, 0u, false, InsertType::BEGIN}).get0(); - test.split(make_ghobj(3, 3, 3, "ns3", "oid4", 3, 3), value2, - {1u, 1u, false, InsertType::BEGIN}).get0(); - test.split(make_ghobj(3, 3, 3, "ns4", "oid4", 1, 1), value2, - {1u, 0u, false, InsertType::BEGIN}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns3", "oid3", 5, 5), value2, + {1u, 0u, false, InsertType::BEGIN}, + {make_ghobj(3, 3, 3, "ns4", "oid4", 2, 2)}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns3", "oid4", 3, 3), value2, + {1u, 1u, false, InsertType::BEGIN}, + {make_ghobj(3, 3, 3, "ns4", "oid4", 2, 2)}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns4", "oid4", 1, 1), value2, + {1u, 0u, false, InsertType::BEGIN}, + {make_ghobj(3, 3, 3, "ns4", "oid4", 2, 2)}).get0(); logger().info("\n---------------------------------------------" "\nsplit at stage 1; insert to right middle at stage 0, 1, 2, 1, 0\n"); - test.split(make_ghobj(3, 3, 3, "ns4", "oid4", 5, 5), value2, - {1u, 0u, false, InsertType::MID}).get0(); - test.split(make_ghobj(3, 3, 3, "ns5", "oid5", 3, 3), value2, - {1u, 1u, false, InsertType::MID}).get0(); - test.split(make_ghobj(3, 3, 4, "ns3", "oid3", 3, 3), value2, - {1u, 2u, false, InsertType::MID}).get0(); - test.split(make_ghobj(4, 4, 4, "ns1", "oid1", 3, 3), value2, - {1u, 1u, false, InsertType::MID}).get0(); - test.split(make_ghobj(4, 4, 4, "ns2", "oid2", 1, 1), value2, - {1u, 0u, false, InsertType::MID}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns4", "oid4", 5, 5), value2, + {1u, 0u, false, InsertType::MID}, + {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns5", "oid5", 3, 3), value2, + {1u, 1u, false, InsertType::MID}, + {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(3, 3, 4, "ns3", "oid3", 3, 3), value2, + {1u, 2u, false, InsertType::MID}, + {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(4, 4, 4, "ns1", "oid1", 3, 3), value2, + {1u, 1u, false, InsertType::MID}, + {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(4, 4, 4, "ns2", "oid2", 1, 1), value2, + {1u, 0u, false, InsertType::MID}, + {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0(); auto value3 = test.create_value(834); logger().info("\n---------------------------------------------" "\nsplit at stage 0; insert to right middle at stage 0, 1, 2, 1, 0\n"); - test.split(make_ghobj(3, 3, 3, "ns4", "oid4", 5, 5), value3, - {0u, 0u, false, InsertType::MID}).get0(); - test.split(make_ghobj(3, 3, 3, "ns5", "oid5", 3, 3), value3, - {0u, 1u, false, InsertType::MID}).get0(); - test.split(make_ghobj(3, 3, 4, "ns3", "oid3", 3, 3), value3, - {0u, 2u, false, InsertType::MID}).get0(); - test.split(make_ghobj(4, 4, 4, "ns1", "oid1", 3, 3), value3, - {0u, 1u, false, InsertType::MID}).get0(); - test.split(make_ghobj(4, 4, 4, "ns2", "oid2", 1, 1), value3, - {0u, 0u, false, InsertType::MID}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns4", "oid4", 5, 5), value3, + {0u, 0u, false, InsertType::MID}, + {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns5", "oid5", 3, 3), value3, + {0u, 1u, false, InsertType::MID}, + {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(3, 3, 4, "ns3", "oid3", 3, 3), value3, + {0u, 2u, false, InsertType::MID}, + {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(4, 4, 4, "ns1", "oid1", 3, 3), value3, + {0u, 1u, false, InsertType::MID}, + {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0(); + test.split_merge(make_ghobj(4, 4, 4, "ns2", "oid2", 1, 1), value3, + {0u, 0u, false, InsertType::MID}, + {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0(); logger().info("\n---------------------------------------------" "\nsplit at stage 0; insert to right front at stage 0\n"); - test.split(make_ghobj(3, 3, 3, "ns4", "oid4", 2, 3), value3, - {0u, 0u, false, InsertType::BEGIN}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns4", "oid4", 2, 3), value3, + {0u, 0u, false, InsertType::BEGIN}, + {make_ghobj(3, 3, 3, "ns4", "oid4", 3, 3)}).get0(); auto value4 = test.create_value(572); logger().info("\n---------------------------------------------" "\nsplit at stage 0; insert to left back at stage 0\n"); - test.split(make_ghobj(3, 3, 3, "ns2", "oid2", 3, 4), value4, - {0u, 0u, true, InsertType::LAST}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns2", "oid2", 3, 4), value4, + {0u, 0u, true, InsertType::LAST}, + {make_ghobj(3, 3, 3, "ns2", "oid2", 4, 4)}).get0(); } { @@ -674,14 +758,17 @@ TEST_F(c_dummy_test_t, 4_split_leaf_node) auto value = test.create_value(1996); logger().info("\n---------------------------------------------" "\nsplit at [0, 0, 0]; insert to left front at stage 2, 1, 0\n"); - test.split(make_ghobj(1, 1, 1, "ns3", "oid3", 3, 3), value, - {2u, 2u, true, InsertType::BEGIN}).get0(); + test.split_merge(make_ghobj(1, 1, 1, "ns3", "oid3", 3, 3), value, + {2u, 2u, true, InsertType::BEGIN}, + {make_ghobj(2, 2, 2, "ns2", "oid2", 2, 2)}).get0(); EXPECT_TRUE(last_split.match_split_pos({0, {0, {0}}})); - test.split(make_ghobj(2, 2, 2, "ns1", "oid1", 3, 3), value, - {2u, 1u, true, InsertType::BEGIN}).get0(); + test.split_merge(make_ghobj(2, 2, 2, "ns1", "oid1", 3, 3), value, + {2u, 1u, true, InsertType::BEGIN}, + {make_ghobj(2, 2, 2, "ns2", "oid2", 2, 2)}).get0(); EXPECT_TRUE(last_split.match_split_pos({0, {0, {0}}})); - test.split(make_ghobj(2, 2, 2, "ns2", "oid2", 1, 1), value, - {2u, 0u, true, InsertType::BEGIN}).get0(); + test.split_merge(make_ghobj(2, 2, 2, "ns2", "oid2", 1, 1), value, + {2u, 0u, true, InsertType::BEGIN}, + {make_ghobj(2, 2, 2, "ns2", "oid2", 2, 2)}).get0(); EXPECT_TRUE(last_split.match_split_pos({0, {0, {0}}})); } @@ -697,14 +784,17 @@ TEST_F(c_dummy_test_t, 4_split_leaf_node) auto value = test.create_value(1640); logger().info("\n---------------------------------------------" "\nsplit at [END, END, END]; insert to right at stage 0, 1, 2\n"); - test.split(make_ghobj(3, 3, 3, "ns3", "oid3", 4, 4), value, - {0u, 0u, false, InsertType::BEGIN}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns3", "oid3", 4, 4), value, + {0u, 0u, false, InsertType::BEGIN}, + std::nullopt).get0(); EXPECT_TRUE(last_split.match_split_pos({1, {0, {1}}})); - test.split(make_ghobj(3, 3, 3, "ns4", "oid4", 3, 3), value, - {1u, 1u, false, InsertType::BEGIN}).get0(); + test.split_merge(make_ghobj(3, 3, 3, "ns4", "oid4", 3, 3), value, + {1u, 1u, false, InsertType::BEGIN}, + std::nullopt).get0(); EXPECT_TRUE(last_split.match_split_pos({1, {1, {0}}})); - test.split(make_ghobj(4, 4, 4, "ns3", "oid3", 3, 3), value, - {2u, 2u, false, InsertType::BEGIN}).get0(); + test.split_merge(make_ghobj(4, 4, 4, "ns3", "oid3", 3, 3), value, + {2u, 2u, false, InsertType::BEGIN}, + std::nullopt).get0(); EXPECT_TRUE(last_split.match_split_pos({2, {0, {0}}})); } }); -- 2.39.5