AU: Cyclebreaker optimization

cycle_breaker.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 "update_engine/cycle_breaker.h"
 #include <inttypes.h>
 #include <set>
 #include <utility>
 #include "base/string_util.h"
 #include "update_engine/graph_utils.h"
@@ skipping 16 matching lines @@
   subgraph_ = graph;
     
   // The paper calls for the "adjacency structure (i.e., graph) of
   // strong (-ly connected) component K with least vertex in subgraph
   // induced by {s, s + 1, ..., n}".
   // We arbitrarily order each vertex by its index in the graph. Thus,
   // each iteration, we are looking at the subgraph {s, s + 1, ..., n}
   // and looking for the strongly connected component with vertex s.
 
   TarjanAlgorithm tarjan;
+  skipped_ops_ = 0;
     
   for (Graph::size_type i = 0; i < subgraph_.size(); i++) {
+    DeltaArchiveManifest_InstallOperation_Type op_type = graph[i].op.type();
+    if (op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+        op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
+      skipped_ops_++;
+      continue;
+    }
+
     if (i > 0) {
       // Erase node (i - 1) from subgraph_. First, erase what it points to
       subgraph_[i - 1].out_edges.clear();
       // Now, erase any pointers to node (i - 1)
       for (Graph::size_type j = i; j < subgraph_.size(); j++) {
         subgraph_[j].out_edges.erase(i - 1);
       }
     }
 
     // Calculate SCC (strongly connected component) with vertex i.
@@ skipping 15 matching lines @@
 
     current_vertex_ = i;
     blocked_.clear();
     blocked_.resize(subgraph_.size());
     blocked_graph_.clear();
     blocked_graph_.resize(subgraph_.size());
     Circuit(current_vertex_, 0);
   }
   
   out_cut_edges->swap(cut_edges_);
+  LOG(INFO) << "Cycle breaker skipped " << skipped_ops_ << " ops.";
   DCHECK(stack_.empty());
 }
 
 static const size_t kMaxEdgesToConsider = 2;
 
 void CycleBreaker::HandleCircuit() {
   stack_.push_back(current_vertex_);
   CHECK_GE(stack_.size(), 2);
   Edge min_edge = make_pair(stack_[0], stack_[1]);
   uint64_t min_edge_weight = kuint64max;
@@ skipping 25 matching lines @@
        it != blocked_graph_[u].out_edges.end(); ) {
     Vertex::Index w = it->first;
     blocked_graph_[u].out_edges.erase(it++);
     if (blocked_[w])
       Unblock(w);
   }
 }
 
 bool CycleBreaker::StackContainsCutEdge() const {
   for (std::vector<Vertex::Index>::const_iterator it = ++stack_.begin(),
-        e = stack_.end(); it != e; ++it) {
+           e = stack_.end(); it != e; ++it) {
     Edge edge = make_pair(*(it - 1), *it);
     if (utils::SetContainsKey(cut_edges_, edge)) {
       return true;
     }
   }
   return false;
 }
 
 bool CycleBreaker::Circuit(Vertex::Index vertex, Vertex::Index depth) {
   // "vertex" was "v" in the original paper.
@@ skipping 45 matching lines @@
                                                       EdgeProperties()));
       }
     }
   }
   CHECK_EQ(vertex, stack_.back());
   stack_.pop_back();
   return found;
 }
 
 }  // namespace chromeos_update_engine