/system/update_engine/payload_generator/ |
H A D | tarjan.cc | 35 Graph* graph, 40 for (Graph::iterator it = graph->begin(); it != graph->end(); ++it) 44 Tarjan(vertex, graph); 49 void TarjanAlgorithm::Tarjan(Vertex::Index vertex, Graph* graph) { argument 50 CHECK_EQ((*graph)[vertex].index, kInvalidIndex); 51 (*graph)[vertex].index = index_; 52 (*graph)[vertex].lowlink = index_; 55 for (Vertex::EdgeMap::iterator it = (*graph)[vertex].out_edges.begin(); 56 it != (*graph)[verte 34 Execute(Vertex::Index vertex, Graph* graph, vector<Vertex::Index>* out) argument [all...] |
H A D | graph_utils_unittest.cc | 36 Graph graph(2); 38 graph[0].out_edges.insert(make_pair(1, EdgeProperties())); 40 vector<Extent>& extents = graph[0].out_edges[1].extents; 56 EXPECT_EQ(4U, graph_utils::EdgeWeight(graph, make_pair(0, 1))); 61 Graph graph(3); 63 graph_utils::AddReadBeforeDep(&graph[0], 1, 3); 64 EXPECT_EQ(1U, graph[0].out_edges.size()); 66 Extent& extent = graph[0].out_edges[1].extents[0]; 70 graph_utils::AddReadBeforeDep(&graph[0], 1, 4); 71 EXPECT_EQ(1U, graph[ [all...] |
H A D | topological_sort.cc | 30 void TopologicalSortVisit(const Graph& graph, argument 39 for (Vertex::EdgeMap::const_iterator it = graph[node].out_edges.begin(); 40 it != graph[node].out_edges.end(); ++it) { 41 TopologicalSortVisit(graph, visited_nodes, nodes, it->first); 48 void TopologicalSort(const Graph& graph, vector<Vertex::Index>* out) { argument 51 for (Vertex::Index i = 0; i < graph.size(); i++) { 52 TopologicalSortVisit(graph, &visited_nodes, out, i);
|
H A D | topological_sort.h | 26 // Performs a topological sort on the directed graph 'graph' and stores 28 // For example, this graph: 37 // Note: results are undefined if there is a cycle in the graph. 38 void TopologicalSort(const Graph& graph, std::vector<Vertex::Index>* out);
|
H A D | topological_sort_unittest.cc | 66 Graph graph(kNodeCount); 68 graph[n_i].out_edges.insert(make_pair(n_j, EdgeProperties())); 69 graph[n_i].out_edges.insert(make_pair(n_c, EdgeProperties())); 70 graph[n_i].out_edges.insert(make_pair(n_e, EdgeProperties())); 71 graph[n_i].out_edges.insert(make_pair(n_h, EdgeProperties())); 72 graph[n_c].out_edges.insert(make_pair(n_b, EdgeProperties())); 73 graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties())); 74 graph[n_e].out_edges.insert(make_pair(n_d, EdgeProperties())); 75 graph[n_e].out_edges.insert(make_pair(n_g, EdgeProperties())); 76 graph[n_ [all...] |
H A D | cycle_breaker_unittest.cc | 39 void SetOpForNodes(Graph* graph) { argument 40 for (Vertex& vertex : *graph) { 60 Graph graph(kNodeCount); 61 SetOpForNodes(&graph); 63 graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties())); 64 graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties())); 65 graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties())); 66 graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties())); 67 graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties())); 68 graph[n_ [all...] |
H A D | inplace_generator_unittest.cc | 184 Graph graph; local 187 // Create nodes in graph 189 graph.resize(graph.size() + 1); 190 graph.back().aop.op.set_type(InstallOperation::MOVE); 196 StoreExtents(extents, graph.back().aop.op.mutable_src_extents()); 197 blocks[3].reader = graph.size() - 1; 198 blocks[5].reader = graph.size() - 1; 199 blocks[7].reader = graph.size() - 1; 206 StoreExtents(extents, graph [all...] |
H A D | graph_utils.h | 34 uint64_t EdgeWeight(const Graph& graph, const Edge& edge); 36 // These add a read-before dependency from graph[src] -> graph[dst]. If the dep 47 // For each node N in graph, drop all edges N->|index|. 48 void DropIncomingEdgesTo(Graph* graph, Vertex::Index index); 50 void DumpGraph(const Graph& graph);
|
H A D | inplace_generator.cc | 83 // their destination extents given the index of the operations in the graph. 86 explicit IndexedInstallOperationsDstComparator(Graph* graph) argument 87 : graph_(graph) {} 101 void InplaceGenerator::CheckGraph(const Graph& graph) { argument 102 for (const Vertex& v : graph) { 139 bool InplaceGenerator::CutEdges(Graph* graph, argument 150 (*graph)[edge.first].out_edges[edge.second].extents; 152 scratch_blocks_used += graph_utils::EdgeWeight(*graph, edge); 154 scratch_allocator.Allocate(graph_utils::EdgeWeight(*graph, edge)); 156 cuts.back().new_vertex = graph 207 CreateEdges( Graph* graph, const vector<Block>& blocks) argument 274 MoveAndSortFullOpsToBack( Graph* graph, vector<Vertex::Index>* op_indexes) argument 323 ConvertCutsToFull( Graph* graph, const string& new_part, BlobFileWriter* blob_file, vector<Vertex::Index>* op_indexes, vector<vector<Vertex::Index>::size_type>* reverse_op_indexes, const vector<CutEdgeVertexes>& cuts) argument 361 AssignBlockForAdjoiningCuts( Graph* graph, const string& new_part, BlobFileWriter* blob_file, vector<Vertex::Index>* op_indexes, vector<vector<Vertex::Index>::size_type>* reverse_op_indexes, const vector<CutEdgeVertexes>& cuts) argument 477 AssignTempBlocks( Graph* graph, const string& new_part, BlobFileWriter* blob_file, vector<Vertex::Index>* op_indexes, vector<vector<Vertex::Index>::size_type>* reverse_op_indexes, const vector<CutEdgeVertexes>& cuts) argument 525 NoTempBlocksRemain(const Graph& graph) argument 552 ConvertCutToFullOp(Graph* graph, const CutEdgeVertexes& cut, const string& new_part, BlobFileWriter* blob_file) argument 600 ConvertGraphToDag(Graph* graph, const string& new_part, BlobFileWriter* blob_file, vector<Vertex::Index>* final_order, Vertex::Index scratch_vertex) argument 670 AddInstallOpToBlocksVector( const InstallOperation& operation, const Graph& graph, Vertex::Index vertex, vector<Block>* blocks) argument 704 AddInstallOpToGraph(Graph* graph, Vertex::Index existing_vertex, vector<Block>* blocks, const InstallOperation operation, const string& op_name) argument 744 Graph graph; local [all...] |
H A D | tarjan_unittest.cc | 47 Graph graph(kNodeCount); 49 graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties())); 50 graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties())); 51 graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties())); 52 graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties())); 53 graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties())); 54 graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties())); 55 graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties())); 56 graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties())); 57 graph[n_ [all...] |
H A D | graph_utils.cc | 38 uint64_t EdgeWeight(const Graph& graph, const Edge& edge) { argument 41 graph[edge.first].out_edges.find(edge.second)->second.extents; 94 // For each node N in graph, drop all edges N->|index|. 95 void DropIncomingEdgesTo(Graph* graph, Vertex::Index index) { argument 97 // edges in the graph. 98 for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) { 124 void DumpGraph(const Graph& graph) { argument 125 LOG(INFO) << "Graph length: " << graph.size(); 126 for (Graph::size_type i = 0, e = graph [all...] |
H A D | tarjan.h | 21 // Strongly Connected Components in a graph. 24 // in the graph. This implementation will only find the strongly connected 39 Graph* graph, 42 void Tarjan(Vertex::Index vertex, Graph* graph);
|
H A D | inplace_generator.h | 59 // each of which has a corresponding vertex in a graph. 71 // Checks all the operations in the graph have a type assigned. 72 static void CheckGraph(const Graph& graph); 86 // Cuts 'edges' from 'graph' according to the AU algorithm. This means 93 static bool CutEdges(Graph* graph, 97 // Creates all the edges for the graph. Writers of a block point to 100 static void CreateEdges(Graph* graph, 104 // which the op is performed -> graph vertex index, and produces the 105 // reverse: a mapping from graph vertex index -> op_indexes index. 116 // Given a topologically sorted graph |op_indexe [all...] |
H A D | cycle_breaker.h | 21 // finding all elementary cycles (a.k.a. circuits) in a directed graph. 32 // In a sample graph representative of a typical workload, I found over 46 void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges);
|
H A D | cycle_breaker.cc | 39 void CycleBreaker::BreakCycles(const Graph& graph, set<Edge>* out_cut_edges) { argument 45 subgraph_ = graph; 47 // The paper calls for the "adjacency structure (i.e., graph) of 50 // We arbitrarily order each vertex by its index in the graph. Thus, 58 InstallOperation_Type op_type = graph[i].aop.op.type(); 84 // If there's a link from *it -> *jt in the graph,
|
/system/core/libmemunreachable/ |
H A D | Tarjan.h | 68 void Execute(Graph<T>& graph, SCCList<T>& out); 71 void Tarjan(Node<T>* vertex, Graph<T>& graph); 79 void TarjanAlgorithm<T>::Execute(Graph<T>& graph, SCCList<T>& out) { argument 83 for (auto& it: graph) { 88 for (auto& it: graph) { 90 Tarjan(it, graph); 97 void TarjanAlgorithm<T>::Tarjan(Node<T>* vertex, Graph<T>& graph) { argument 106 Tarjan(vertex_next, graph); 126 void Tarjan(Graph<T>& graph, SCCList<T>& out) { argument 127 TarjanAlgorithm<T> tarjan{graph [all...] |