AU: Cyclebreaker optimization
When using the cycle breaker, we know that operations that are full
(REPLACE, REPLACE_BZ) can't have any incoming edges, and thus can't be
in a cycle.
To help reduce CPU usage, change the cycle breaker to skip nodes that
are REPLACE or REPLACE_BZ.
BUG=7294
TEST=Attached unittests, generated delta update and applied it
Review URL: http://codereview.chromium.org/3618006
diff --git a/cycle_breaker.h b/cycle_breaker.h
index 9c10c17..f1fa677 100644
--- a/cycle_breaker.h
+++ b/cycle_breaker.h
@@ -28,8 +28,11 @@
class CycleBreaker {
public:
+ CycleBreaker() : skipped_ops_(0) {}
// out_cut_edges is replaced with the cut edges.
void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges);
+
+ size_t skipped_ops() const { return skipped_ops_; }
private:
void HandleCircuit();
@@ -44,6 +47,10 @@
Graph blocked_graph_; // "B" in the paper
std::set<Edge> cut_edges_;
+
+ // Number of operations skipped b/c we know they don't have any
+ // incoming edges.
+ size_t skipped_ops_;
};
} // namespace chromeos_update_engine