REQUIRE(num_nodes_traversed == tree.get_num_nodes());
}
+static void test_tree_empty(const WakeupTree& tree)
+{
+ REQUIRE(tree.empty());
+ REQUIRE(tree.get_num_entries() == 0);
+ REQUIRE(tree.get_num_nodes() == 1);
+ REQUIRE_FALSE(tree.get_min_single_process_node().has_value());
+ REQUIRE_FALSE(tree.get_min_single_process_actor().has_value());
+ test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{}});
+}
+
TEST_CASE("simgrid::mc::odpor::WakeupTree: Constructing Trees")
{
SECTION("Constructing empty trees")
{
- WakeupTree tree;
- REQUIRE(tree.empty());
- REQUIRE(tree.get_num_entries() == 0);
- REQUIRE(tree.get_num_nodes() == 1);
- REQUIRE_FALSE(tree.get_min_single_process_node().has_value());
- REQUIRE_FALSE(tree.get_min_single_process_actor().has_value());
- test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{}});
+ test_tree_empty(WakeupTree());
}
SECTION("Testing subtree creation and manipulation")
// the tree should be empty
REQUIRE(tree.empty());
}
+
+ SECTION("Removing the first single-process subtree from an empty tree has no effect")
+ {
+ WakeupTree empty_tree;
+ test_tree_empty(empty_tree);
+
+ empty_tree.remove_min_single_process_subtree();
+
+ // There should be no effect: the tree should still be empty
+ // and the function should have no effect
+ test_tree_empty(empty_tree);
+ }
}
}
const auto a1 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 4);
const auto a2 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 1);
const auto a3 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 4);
+ const auto a4 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 2);
Execution execution;
execution.push_transition(a0);
execution.push_transition(a1);
execution.push_transition(a2);
execution.push_transition(a3);
+ execution.push_transition(a4);
REQUIRE(execution.get_racing_events_of(2) == std::unordered_set<Execution::EventHandle>{0});
REQUIRE(execution.get_racing_events_of(3) == std::unordered_set<Execution::EventHandle>{0});
// / /
// a0 a1
// / /
- // a3 a2
+ // a3 a4
//
// Recall that new nodes (in this case the one with
// action `a2`) are added such that they are "greater than" (under
// the tree's `<` relation) all those that exist under the given parent.
- tree.insert(Execution(), {a1, a2});
+ tree.insert(Execution(), {a1, a4});
test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
- PartialExecution{a1, a2}, PartialExecution{a1},
+ PartialExecution{a1, a4}, PartialExecution{a1},
PartialExecution{}});
}
+
+ SECTION("Inserting an equivalent sequence to a leaf should preserve the tree as-is")
+ {
+ // `a1.a2` is equivalent to `a1.a3` since `a2` and `a3` are independent
+ // (`E ⊢ p ◊ w` where `p := proc(a2)` and `w := a3`). Thus, the tree
+ // should now STILL look as follows:
+ //
+ // {}
+ // / /
+ // a0 a1
+ // /
+ // a3
+ //
+ // Recall that new nodes (in this case the one with
+ // action `a2`) are added such that they are "greater than" (under
+ // the tree's `<` relation) all those that exist under the given parent.
+ tree.insert(Execution(), {a1, a3});
+ test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
+ PartialExecution{a1}, PartialExecution{}});
+ }
}
SECTION("Performing Arbitrary Insertions")
const auto a3 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 1);
const auto a4 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 2);
const auto a5 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 4);
-
- Execution execution;
- execution.push_transition(a0);
- execution.push_transition(a1);
- execution.push_transition(a2);
- execution.push_transition(a3);
- execution.push_transition(a4);
- execution.push_transition(a5);
-
WakeupTree tree;
SECTION("Attempting to insert the empty sequence into an empty tree should have no effect")
}
}
}
+
+ SECTION("Insertion with more subtle equivalents")
+ {
+ const auto cd_1 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 1);
+ const auto i_2 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 2);
+ const auto i_3 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 3);
+ const auto d_1 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 1);
+ const auto d_2 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 2);
+ WakeupTree complex_tree;
+ // After the insertions below, the tree looks like the following:
+ // {}
+ // / /
+ // cd_1 i_2
+ // / /
+ // i_2 d_2
+ // / /
+ // d_1 cd_1
+ // / / /
+ // i_3 d_1 i_3
+ // / / /
+ // d_2 i_3 d_2
+ // / / /
+ // d_2 d_2 d_1
+ //
+ // d_1.i_3.d_2 is equivalent to i_3.d_2.d_1
+ complex_tree.insert(Execution(), {cd_1, i_2, d_1, i_3, d_2, d_2});
+ complex_tree.insert(Execution(), {i_2, d_2, cd_1, d_1, i_3, d_2});
+ complex_tree.insert(Execution(), {i_2, d_2, cd_1, i_3, d_2, d_1});
+ REQUIRE(complex_tree.get_num_nodes() == 16);
+ test_tree_iterator(complex_tree, std::vector<PartialExecution>{{cd_1, i_2, d_1, i_3, d_2, d_2},
+ {cd_1, i_2, d_1, i_3, d_2},
+ {cd_1, i_2, d_1, i_3},
+ {cd_1, i_2, d_1},
+ {cd_1, i_2},
+ {cd_1},
+ {i_2, d_2, cd_1, d_1, i_3, d_2},
+ {i_2, d_2, cd_1, d_1, i_3},
+ {i_2, d_2, cd_1, d_1},
+ {i_2, d_2, cd_1, i_3, d_2, d_1},
+ {i_2, d_2, cd_1, i_3, d_2},
+ {i_2, d_2, cd_1, i_3},
+ {i_2, d_2, cd_1},
+ {i_2, d_2},
+ {i_2},
+ {}});
+ // Here we note that the sequence that we are attempting to insert, viz.
+ //
+ // i_3.i_2.d_2.cd_1.d_2.d_1
+ //
+ // is already equivalent to
+ //
+ // i_2.d_2.cd_1.i_3.d_2.d_1
+ complex_tree.insert(Execution(), {i_3, i_2, d_2, cd_1, d_2, d_1});
+ REQUIRE(complex_tree.get_num_nodes() == 16);
+
+ // Here we note that the sequence that we are attempting to insert, viz.
+ //
+ // i_2.d_2.cd_1.d_1.i_3
+ //
+ // is already equivalent to
+ //
+ // i_2.d_2.cd_1.i_3.d_2.d_1
+ complex_tree.insert(Execution(), {i_2, d_2, cd_1, d_1, i_3});
+ REQUIRE(complex_tree.get_num_nodes() == 16);
+
+ // Here we note that the sequence that we are attempting to insert, viz.
+ //
+ // i_2.d_2.cd_1
+ //
+ // is accounted for by an interior node of the tree. Since there is no
+ // "extra" portions that are different from what is already
+ // contained in the tree, nothing is added and the tree stays the same
+ complex_tree.insert(Execution(), {i_2, d_2, cd_1});
+ REQUIRE(complex_tree.get_num_nodes() == 16);
+ }
}
\ No newline at end of file
