AU: More graph utilities
EdgeProperties: support for listing blocks in a write-before
dependency. Blocks historically have only been listed for a
read-before dep. operator== for Extent and EdgeProperties.
Vertex: ability to mark invalid. An invalid vertex is not part of the
graph.
graph utils: Functions to add and drop dependencies.
Overloaded GetElement() to pull an element at a given index from
either a vector<Extent> or RepeatedPtrField<Extent>.
DumpGraph function, useful for debugging.
BUG=none
TEST=unittests
Review URL: http://codereview.chromium.org/3596007
diff --git a/graph_utils_unittest.cc b/graph_utils_unittest.cc
index d947ddd..cfa2b5c 100644
--- a/graph_utils_unittest.cc
+++ b/graph_utils_unittest.cc
@@ -4,8 +4,11 @@
#include <utility>
#include <vector>
+
#include <gtest/gtest.h>
+
#include "update_engine/graph_utils.h"
+#include "update_engine/extent_ranges.h"
using std::make_pair;
using std::vector;
@@ -38,4 +41,62 @@
EXPECT_EQ(4, graph_utils::EdgeWeight(graph, make_pair(0, 1)));
}
+TEST(GraphUtilsTest, BlocksInExtentsTest) {
+ {
+ vector<Extent> extents;
+ EXPECT_EQ(0, graph_utils::BlocksInExtents(extents));
+ extents.push_back(ExtentForRange(0, 1));
+ EXPECT_EQ(1, graph_utils::BlocksInExtents(extents));
+ extents.push_back(ExtentForRange(23, 55));
+ EXPECT_EQ(56, graph_utils::BlocksInExtents(extents));
+ extents.push_back(ExtentForRange(1, 2));
+ EXPECT_EQ(58, graph_utils::BlocksInExtents(extents));
+ }
+ {
+ google::protobuf::RepeatedPtrField<Extent> extents;
+ EXPECT_EQ(0, graph_utils::BlocksInExtents(extents));
+ *extents.Add() = ExtentForRange(0, 1);
+ EXPECT_EQ(1, graph_utils::BlocksInExtents(extents));
+ *extents.Add() = ExtentForRange(23, 55);
+ EXPECT_EQ(56, graph_utils::BlocksInExtents(extents));
+ *extents.Add() = ExtentForRange(1, 2);
+ EXPECT_EQ(58, graph_utils::BlocksInExtents(extents));
+ }
+}
+
+TEST(GraphUtilsTest, DepsTest) {
+ Graph graph(3);
+
+ graph_utils::AddReadBeforeDep(&graph[0], 1, 3);
+ EXPECT_EQ(1, graph[0].out_edges.size());
+ {
+ Extent& extent = graph[0].out_edges[1].extents[0];
+ EXPECT_EQ(3, extent.start_block());
+ EXPECT_EQ(1, extent.num_blocks());
+ }
+ graph_utils::AddReadBeforeDep(&graph[0], 1, 4);
+ EXPECT_EQ(1, graph[0].out_edges.size());
+ {
+ Extent& extent = graph[0].out_edges[1].extents[0];
+ EXPECT_EQ(3, extent.start_block());
+ EXPECT_EQ(2, extent.num_blocks());
+ }
+ graph_utils::AddReadBeforeDepExtents(&graph[2], 1,
+ vector<Extent>(1, ExtentForRange(5, 2)));
+ EXPECT_EQ(1, graph[2].out_edges.size());
+ {
+ Extent& extent = graph[2].out_edges[1].extents[0];
+ EXPECT_EQ(5, extent.start_block());
+ EXPECT_EQ(2, extent.num_blocks());
+ }
+ // Change most recent edge from read-before to write-before
+ graph[2].out_edges[1].write_extents.swap(graph[2].out_edges[1].extents);
+ graph_utils::DropWriteBeforeDeps(&graph[2].out_edges);
+ EXPECT_EQ(0, graph[2].out_edges.size());
+
+ EXPECT_EQ(1, graph[0].out_edges.size());
+ graph_utils::DropIncomingEdgesTo(&graph, 1);
+ EXPECT_EQ(0, graph[0].out_edges.size());
+}
+
} // namespace chromeos_update_engine