| /system/update_engine/payload_generator/ |
| D | graph_types.h | 53 struct Vertex { struct
54 Vertex() : in Vertex() argument
60 typedef std::map<std::vector<Vertex>::size_type, EdgeProperties> EdgeMap; argument
67 typedef std::set<std::vector<Vertex>::size_type> SubgraphEdgeMap; argument
71 std::vector<Vertex>::size_type index; argument
72 std::vector<Vertex>::size_type lowlink; argument
77 typedef std::vector<Vertex>::size_type Index; argument
78 static const Vertex::Index kInvalidIndex; argument
81 typedef std::vector<Vertex> Graph;
83 typedef std::pair<Vertex::Index, Vertex::Index> Edge;
|
| D | inplace_generator.h | 46 Vertex::Index new_vertex;
47 Vertex::Index old_src;
48 Vertex::Index old_dst;
64 Block() : reader(Vertex::kInvalidIndex), writer(Vertex::kInvalidIndex) {} in Block()
65 Vertex::Index reader;
66 Vertex::Index writer;
82 static void SubstituteBlocks(Vertex* vertex,
107 const std::vector<Vertex::Index>& op_indexes,
108 std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes);
113 const std::vector<Vertex::Index>& op_indexes,
[all …]
|
| D | topological_sort_unittest.cc | 54 const Vertex::Index n_a = counter++; in TEST()
55 const Vertex::Index n_b = counter++; in TEST()
56 const Vertex::Index n_c = counter++; in TEST()
57 const Vertex::Index n_d = counter++; in TEST()
58 const Vertex::Index n_e = counter++; in TEST()
59 const Vertex::Index n_f = counter++; in TEST()
60 const Vertex::Index n_g = counter++; in TEST()
61 const Vertex::Index n_h = counter++; in TEST()
62 const Vertex::Index n_i = counter++; in TEST()
63 const Vertex::Index n_j = counter++; in TEST()
[all …]
|
| D | cycle_breaker_unittest.cc | 40 for (Vertex& vertex : *graph) { in SetOpForNodes()
50 const Vertex::Index n_a = counter++; in TEST()
51 const Vertex::Index n_b = counter++; in TEST()
52 const Vertex::Index n_c = counter++; in TEST()
53 const Vertex::Index n_d = counter++; in TEST()
54 const Vertex::Index n_e = counter++; in TEST()
55 const Vertex::Index n_f = counter++; in TEST()
56 const Vertex::Index n_g = counter++; in TEST()
57 const Vertex::Index n_h = counter++; in TEST()
98 pair<Vertex::Index, EdgeProperties> EdgeWithWeight(Vertex::Index dest, in EdgeWithWeight()
[all …]
|
| D | tarjan.h | 38 void Execute(Vertex::Index vertex,
40 std::vector<Vertex::Index>* out);
42 void Tarjan(Vertex::Index vertex, Graph* graph);
44 Vertex::Index index_;
45 Vertex::Index required_vertex_;
46 std::vector<Vertex::Index> stack_;
47 std::vector<std::vector<Vertex::Index>> components_;
|
| D | tarjan_unittest.cc | 37 const Vertex::Index n_a = 0; in TEST()
38 const Vertex::Index n_b = 1; in TEST()
39 const Vertex::Index n_c = 2; in TEST()
40 const Vertex::Index n_d = 3; in TEST()
41 const Vertex::Index n_e = 4; in TEST()
42 const Vertex::Index n_f = 5; in TEST()
43 const Vertex::Index n_g = 6; in TEST()
44 const Vertex::Index n_h = 7; in TEST()
64 for (Vertex::Index i = n_a; i <= n_e; i++) { in TEST()
65 vector<Vertex::Index> vertex_indexes; in TEST()
[all …]
|
| D | graph_utils.h | 38 void AddReadBeforeDep(Vertex* src,
39 Vertex::Index dst,
41 void AddReadBeforeDepExtents(Vertex* src,
42 Vertex::Index dst,
45 void DropWriteBeforeDeps(Vertex::EdgeMap* edge_map);
48 void DropIncomingEdgesTo(Graph* graph, Vertex::Index index);
|
| D | topological_sort.cc | 31 set<Vertex::Index>* visited_nodes, in TopologicalSortVisit()
32 vector<Vertex::Index>* nodes, in TopologicalSortVisit()
33 Vertex::Index node) { in TopologicalSortVisit()
39 for (Vertex::EdgeMap::const_iterator it = graph[node].out_edges.begin(); in TopologicalSortVisit()
48 void TopologicalSort(const Graph& graph, vector<Vertex::Index>* out) { in TopologicalSort()
49 set<Vertex::Index> visited_nodes; in TopologicalSort()
51 for (Vertex::Index i = 0; i < graph.size(); i++) { in TopologicalSort()
|
| D | cycle_breaker.cc | 75 vector<Vertex::Index> component_indexes; in BreakCycles()
79 for (vector<Vertex::Index>::iterator it = component_indexes.begin(); in BreakCycles()
82 for (vector<Vertex::Index>::iterator jt = component_indexes.begin(); in BreakCycles()
109 static_cast<vector<Vertex::Index>::size_type>(2)); in HandleCircuit()
113 for (vector<Vertex::Index>::const_iterator it = stack_.begin(); in HandleCircuit()
133 void CycleBreaker::Unblock(Vertex::Index u) { in Unblock()
136 for (Vertex::EdgeMap::iterator it = blocked_graph_[u].out_edges.begin(); in Unblock()
138 Vertex::Index w = it->first; in Unblock()
146 for (vector<Vertex::Index>::const_iterator it = ++stack_.begin(), in StackContainsCutEdge()
156 bool CycleBreaker::Circuit(Vertex::Index vertex, Vertex::Index depth) { in Circuit()
[all …]
|
| D | tarjan.cc | 31 const vector<Vertex>::size_type kInvalidIndex = -1;
34 void TarjanAlgorithm::Execute(Vertex::Index vertex, in Execute()
36 vector<Vertex::Index>* out) { in Execute()
49 void TarjanAlgorithm::Tarjan(Vertex::Index vertex, Graph* graph) { in Tarjan()
55 for (Vertex::EdgeMap::iterator it = (*graph)[vertex].out_edges.begin(); in Tarjan()
57 Vertex::Index vertex_next = it->first; in Tarjan()
68 vector<Vertex::Index> component; in Tarjan()
69 Vertex::Index other_vertex; in Tarjan()
|
| D | cycle_breaker.h | 52 void Unblock(Vertex::Index u);
53 bool Circuit(Vertex::Index vertex, Vertex::Index depth);
57 Vertex::Index current_vertex_; // "s" in the paper
58 std::vector<Vertex::Index> stack_; // the stack variable in the paper
|
| D | graph_utils.cc | 50 void AddReadBeforeDep(Vertex* src, in AddReadBeforeDep()
51 Vertex::Index dst, in AddReadBeforeDep()
53 Vertex::EdgeMap::iterator edge_it = src->out_edges.find(dst); in AddReadBeforeDep()
56 pair<Vertex::EdgeMap::iterator, bool> result = in AddReadBeforeDep()
64 void AddReadBeforeDepExtents(Vertex* src, in AddReadBeforeDepExtents()
65 Vertex::Index dst, in AddReadBeforeDepExtents()
79 void DropWriteBeforeDeps(Vertex::EdgeMap* edge_map) { in DropWriteBeforeDeps()
81 for (Vertex::EdgeMap::iterator it = edge_map->begin(); in DropWriteBeforeDeps()
95 void DropIncomingEdgesTo(Graph* graph, Vertex::Index index) { in DropIncomingEdgesTo()
113 void DumpOutEdges(const Vertex::EdgeMap& out_edges) { in DumpOutEdges()
[all …]
|
| D | inplace_generator.cc | 102 for (const Vertex& v : graph) { in CheckGraph()
108 Vertex* vertex, in SubstituteBlocks()
213 if (blocks[i].reader == Vertex::kInvalidIndex || in CreateEdges()
214 blocks[i].writer == Vertex::kInvalidIndex) in CreateEdges()
220 Vertex::EdgeMap::iterator edge_it = in CreateEdges()
238 const vector<vector<Vertex::Index>::size_type>& table) in SortCutsByTopoOrderLess()
244 const vector<vector<Vertex::Index>::size_type>& table_;
250 const vector<Vertex::Index>& op_indexes, in GenerateReverseTopoOrderMap()
251 vector<vector<Vertex::Index>::size_type>* reverse_op_indexes) { in GenerateReverseTopoOrderMap()
252 vector<vector<Vertex::Index>::size_type> table(op_indexes.size()); in GenerateReverseTopoOrderMap()
[all …]
|
| D | graph_types.cc | 21 const Vertex::Index Vertex::kInvalidIndex = static_cast<Vertex::Index>(-1);
|
| D | inplace_generator_unittest.cc | 53 void GenVertex(Vertex* out, in GenVertex()
146 EXPECT_EQ(Vertex::kInvalidIndex, block.reader); in TEST_F()
147 EXPECT_EQ(Vertex::kInvalidIndex, block.writer); in TEST_F()
157 Vertex vertex; in TEST_F()
245 std::pair<Vertex::Index, Vertex::Index>(1, 0))); in TEST_F()
373 vector<Vertex::Index> op_indexes; in TEST_F()
384 vector<vector<Vertex::Index>::size_type> reverse_op_indexes; in TEST_F()
414 vector<Vertex::Index> vect(graph.size()); in TEST_F()
416 for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) { in TEST_F()
481 vector<Vertex::Index> final_order; in TEST_F()
[all …]
|
| D | topological_sort.h | 38 void TopologicalSort(const Graph& graph, std::vector<Vertex::Index>* out);
|