| /system/update_engine/payload_generator/ |
| D | graph_types.h | 53 struct Vertex { struct
54 Vertex() : valid(true), index(-1), lowlink(-1) {} in Vertex() argument
57 typedef std::map<std::vector<Vertex>::size_type, EdgeProperties> EdgeMap; argument
64 typedef std::set<std::vector<Vertex>::size_type> SubgraphEdgeMap; argument
68 std::vector<Vertex>::size_type index; argument
69 std::vector<Vertex>::size_type lowlink; argument
74 typedef std::vector<Vertex>::size_type Index; argument
75 static const Vertex::Index kInvalidIndex; argument
78 typedef std::vector<Vertex> Graph;
80 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,
106 const std::vector<Vertex::Index>& op_indexes,
107 std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes);
111 static void SortCutsByTopoOrder(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 | tarjan.h | 38 void Execute(Vertex::Index vertex,
40 std::vector<Vertex::Index>* out);
43 void Tarjan(Vertex::Index vertex, Graph* graph);
45 Vertex::Index index_;
46 Vertex::Index required_vertex_;
47 std::vector<Vertex::Index> stack_;
48 std::vector<std::vector<Vertex::Index>> components_;
|
| 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_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, Vertex::Index dst, uint64_t block);
39 void AddReadBeforeDepExtents(Vertex* src,
40 Vertex::Index dst,
43 void DropWriteBeforeDeps(Vertex::EdgeMap* edge_map);
46 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()
49 void TopologicalSort(const Graph& graph, vector<Vertex::Index>* out) { in TopologicalSort()
50 set<Vertex::Index> visited_nodes; in TopologicalSort()
52 for (Vertex::Index i = 0; i < graph.size(); i++) { in TopologicalSort()
|
| D | cycle_breaker.cc | 76 vector<Vertex::Index> component_indexes; in BreakCycles()
80 for (vector<Vertex::Index>::iterator it = component_indexes.begin(); in BreakCycles()
84 for (vector<Vertex::Index>::iterator jt = component_indexes.begin(); in BreakCycles()
111 CHECK_GE(stack_.size(), static_cast<vector<Vertex::Index>::size_type>(2)); in HandleCircuit()
115 for (vector<Vertex::Index>::const_iterator it = stack_.begin(); in HandleCircuit()
136 void CycleBreaker::Unblock(Vertex::Index u) { in Unblock()
139 for (Vertex::EdgeMap::iterator it = blocked_graph_[u].out_edges.begin(); in Unblock()
141 Vertex::Index w = it->first; in Unblock()
149 for (vector<Vertex::Index>::const_iterator it = ++stack_.begin(), in StackContainsCutEdge()
161 bool CycleBreaker::Circuit(Vertex::Index vertex, Vertex::Index depth) { in Circuit()
[all …]
|
| D | tarjan.cc | 30 const vector<Vertex>::size_type kInvalidIndex = -1;
33 void TarjanAlgorithm::Execute(Vertex::Index vertex, in Execute()
35 vector<Vertex::Index>* out) { in Execute()
48 void TarjanAlgorithm::Tarjan(Vertex::Index vertex, Graph* graph) { in Tarjan()
54 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, Vertex::Index dst, uint64_t block) { in AddReadBeforeDep()
51 Vertex::EdgeMap::iterator edge_it = src->out_edges.find(dst); in AddReadBeforeDep()
54 pair<Vertex::EdgeMap::iterator, bool> result = in AddReadBeforeDep()
62 void AddReadBeforeDepExtents(Vertex* src, in AddReadBeforeDepExtents()
63 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()
114 for (Vertex::EdgeMap::const_iterator it = out_edges.begin(), in DumpOutEdges()
|
| D | inplace_generator.cc | 104 for (const Vertex& v : graph) { in CheckGraph()
109 void InplaceGenerator::SubstituteBlocks(Vertex* vertex, in SubstituteBlocks()
209 if (blocks[i].reader == Vertex::kInvalidIndex || in CreateEdges()
210 blocks[i].writer == Vertex::kInvalidIndex) in CreateEdges()
216 Vertex::EdgeMap::iterator edge_it = in CreateEdges()
234 const vector<vector<Vertex::Index>::size_type>& table) in SortCutsByTopoOrderLess()
241 const vector<vector<Vertex::Index>::size_type>& table_;
247 const vector<Vertex::Index>& op_indexes, in GenerateReverseTopoOrderMap()
248 vector<vector<Vertex::Index>::size_type>* reverse_op_indexes) { in GenerateReverseTopoOrderMap()
249 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 | topological_sort.h | 38 void TopologicalSort(const Graph& graph, std::vector<Vertex::Index>* out);
|
| D | inplace_generator_unittest.cc | 54 void GenVertex(Vertex* out, in GenVertex()
148 EXPECT_EQ(Vertex::kInvalidIndex, block.reader); in TEST_F()
149 EXPECT_EQ(Vertex::kInvalidIndex, block.writer); in TEST_F()
159 Vertex vertex; in TEST_F()
247 cut_edges.find(std::pair<Vertex::Index, Vertex::Index>(1, 0))); in TEST_F()
375 vector<Vertex::Index> op_indexes; in TEST_F()
386 vector<vector<Vertex::Index>::size_type> reverse_op_indexes; in TEST_F()
416 vector<Vertex::Index> vect(graph.size()); in TEST_F()
418 for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) { in TEST_F()
483 vector<Vertex::Index> final_order; in TEST_F()
[all …]
|