Move payload generator files to payload_generator/ directory.
This creates a new subdirectory payload_generator/ with all the
payload generator specific files.
The SConstruct file is updated to continue building all the files
together, including those in the subdirectories, since some parts
of the update_engine are using parts of the payload generation code.
To reduce this code coupling, a new payload_constants.h file is
introduced, with few constants used on the payload definition by both
the payload generation and the payload performer.
Finally, includes are updated and in some cases removed when they
weren't used. Order of includes is also fixed to comply with the
style guide.
BUG=chromium:374377
TEST=Build and unittests still pass. delta_generator still present on base directory.
Change-Id: I454bbc7a66c70ebb19fd596c352c7be40a081f3d
Reviewed-on: https://chromium-review.googlesource.com/200325
Reviewed-by: Alex Deymo <deymo@chromium.org>
Commit-Queue: Alex Deymo <deymo@chromium.org>
Tested-by: Alex Deymo <deymo@chromium.org>
diff --git a/payload_generator/cycle_breaker.h b/payload_generator/cycle_breaker.h
new file mode 100644
index 0000000..d0ae3fd
--- /dev/null
+++ b/payload_generator/cycle_breaker.h
@@ -0,0 +1,59 @@
+// 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.
+
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_
+
+// This is a modified implementation of Donald B. Johnson's algorithm for
+// finding all elementary cycles (a.k.a. circuits) in a directed graph.
+// See the paper "Finding All the Elementary Circuits of a Directed Graph"
+// at http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf
+// for reference.
+
+// Note: this version of the algorithm not only finds cycles, but breaks them.
+// It uses a simple greedy algorithm for cutting: when a cycle is discovered,
+// the edge with the least weight is cut. Longer term we may wish to do
+// something more intelligent, since the goal is (ideally) to minimize the
+// sum of the weights of all cut cycles. In practice, it's intractable
+// to consider all cycles before cutting any; there are simply too many.
+// In a sample graph representative of a typical workload, I found over
+// 5 * 10^15 cycles.
+
+#include <set>
+#include <vector>
+
+#include "update_engine/payload_generator/graph_types.h"
+
+namespace chromeos_update_engine {
+
+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();
+ void Unblock(Vertex::Index u);
+ bool Circuit(Vertex::Index vertex, Vertex::Index depth);
+ bool StackContainsCutEdge() const;
+
+ std::vector<bool> blocked_; // "blocked" in the paper
+ Vertex::Index current_vertex_; // "s" in the paper
+ std::vector<Vertex::Index> stack_; // the stack variable in the paper
+ Graph subgraph_; // "A_K" in the paper
+ 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
+
+#endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_