AU: Cyclebreaker optimization

cycle_breaker_unittest.cc

 // Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include <set>
 #include <string>
 #include <utility>
 #include <vector>
 #include <gtest/gtest.h>
 #include "base/logging.h"
 #include "update_engine/cycle_breaker.h"
 #include "update_engine/graph_types.h"
 #include "update_engine/utils.h"
 
 using std::make_pair;
 using std::pair;
 using std::set;
 using std::string;
 using std::vector;
 
 namespace chromeos_update_engine {
 
+namespace {
+void SetOpForNodes(Graph* graph) {
+  for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) {
+    it->op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+  }
+}
+}  // namespace {}
+
 class CycleBreakerTest : public ::testing::Test {};
 
 TEST(CycleBreakerTest, SimpleTest) {
   int counter = 0;
   const Vertex::Index n_a = counter++;
   const Vertex::Index n_b = counter++;
   const Vertex::Index n_c = counter++;
   const Vertex::Index n_d = counter++;
   const Vertex::Index n_e = counter++;
   const Vertex::Index n_f = counter++;
   const Vertex::Index n_g = counter++;
   const Vertex::Index n_h = counter++;
   const Graph::size_type kNodeCount = counter++;
 
   Graph graph(kNodeCount);
+  SetOpForNodes(&graph);
 
   graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties()));
   graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties()));
   graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties()));
   graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties()));
   graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties()));
   graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties()));
   graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties()));
   graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties()));
   graph[n_e].out_edges.insert(make_pair(n_f, EdgeProperties()));
@@ skipping 54 matching lines @@
 // such that the original cutting algo would cut edges (s). We changed
 // the algorithm to cut cycles (t) instead, since they are closer to the
 // root, and that can massively speed up cycle cutting.
 TEST(CycleBreakerTest, AggressiveCutTest) {
   int counter = 0;
   
   const int kNodesPerGroup = 4;
   const int kGroups = 33;
   
   Graph graph(kGroups * kNodesPerGroup + 1);  // + 1 for the root node
+  SetOpForNodes(&graph);
   
   const Vertex::Index n_root = counter++;
 
   Vertex::Index last_hub = n_root;
   for (int i = 0; i < kGroups; i++) {
     uint64_t weight = 5;
     if (i == 0)
       weight = 2;
     else if (i == (kGroups - 1))
       weight = 1;
@@ skipping 37 matching lines @@
   const Vertex::Index n_d = counter++;
   const Vertex::Index n_e = counter++;
   const Vertex::Index n_f = counter++;
   const Vertex::Index n_g = counter++;
   const Vertex::Index n_h = counter++;
   const Vertex::Index n_i = counter++;
   const Vertex::Index n_j = counter++;
   const Graph::size_type kNodeCount = counter++;
 
   Graph graph(kNodeCount);
+  SetOpForNodes(&graph);
 
   graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 4));
   graph[n_a].out_edges.insert(EdgeWithWeight(n_f, 3));
   graph[n_a].out_edges.insert(EdgeWithWeight(n_h, 2));
   graph[n_b].out_edges.insert(EdgeWithWeight(n_a, 3));
   graph[n_b].out_edges.insert(EdgeWithWeight(n_c, 4));
   graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 5));
   graph[n_c].out_edges.insert(EdgeWithWeight(n_d, 3));
   graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 6));
   graph[n_d].out_edges.insert(EdgeWithWeight(n_e, 3));
@@ skipping 22 matching lines @@
 
 TEST(CycleBreakerTest, UnblockGraphTest) {
   int counter = 0;
   const Vertex::Index n_a = counter++;
   const Vertex::Index n_b = counter++;
   const Vertex::Index n_c = counter++;
   const Vertex::Index n_d = counter++;
   const Graph::size_type kNodeCount = counter++;
 
   Graph graph(kNodeCount);
+  SetOpForNodes(&graph);
 
   graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1));
   graph[n_a].out_edges.insert(EdgeWithWeight(n_c, 1));
   graph[n_b].out_edges.insert(EdgeWithWeight(n_c, 2));
   graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 2));
   graph[n_b].out_edges.insert(EdgeWithWeight(n_d, 2));
   graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 2));
 
   CycleBreaker breaker;
   
   set<Edge> broken_edges;
   breaker.BreakCycles(graph, &broken_edges);
 
   // These are required to be broken:
   EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_b)));
   EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_c)));
 }
 
+TEST(CycleBreakerTest, SkipOpsTest) {
+  int counter = 0;
+  const Vertex::Index n_a = counter++;
+  const Vertex::Index n_b = counter++;
+  const Vertex::Index n_c = counter++;
+  const Graph::size_type kNodeCount = counter++;
+
+  Graph graph(kNodeCount);
+  SetOpForNodes(&graph);
+  graph[n_a].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+  graph[n_c].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+
+  graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1));
+  graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 1));
+
+  CycleBreaker breaker;
+  
+  set<Edge> broken_edges;
+  breaker.BreakCycles(graph, &broken_edges);
+  
+  EXPECT_EQ(2, breaker.skipped_ops());
+}
+
 }  // namespace chromeos_update_engine