| // Copyright 2013 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "components/browser_context_keyed_service/dependency_graph.h" |
| |
| #include <algorithm> |
| #include <deque> |
| #include <iterator> |
| |
| DependencyGraph::DependencyGraph() { |
| } |
| |
| DependencyGraph::~DependencyGraph() { |
| } |
| |
| void DependencyGraph::AddNode(DependencyNode* node) { |
| all_nodes_.push_back(node); |
| construction_order_.clear(); |
| } |
| |
| void DependencyGraph::RemoveNode(DependencyNode* node) { |
| all_nodes_.erase(std::remove(all_nodes_.begin(), |
| all_nodes_.end(), |
| node), |
| all_nodes_.end()); |
| |
| // Remove all dependency edges that contain this node. |
| EdgeMap::iterator it = edges_.begin(); |
| while (it != edges_.end()) { |
| EdgeMap::iterator temp = it; |
| ++it; |
| |
| if (temp->first == node || temp->second == node) |
| edges_.erase(temp); |
| } |
| |
| construction_order_.clear(); |
| } |
| |
| void DependencyGraph::AddEdge(DependencyNode* depended, |
| DependencyNode* dependee) { |
| edges_.insert(std::make_pair(depended, dependee)); |
| construction_order_.clear(); |
| } |
| |
| bool DependencyGraph::GetConstructionOrder( |
| std::vector<DependencyNode*>* order) { |
| if (construction_order_.empty() && !BuildConstructionOrder()) |
| return false; |
| |
| *order = construction_order_; |
| return true; |
| } |
| |
| bool DependencyGraph::GetDestructionOrder( |
| std::vector<DependencyNode*>* order) { |
| if (construction_order_.empty() && !BuildConstructionOrder()) |
| return false; |
| |
| *order = construction_order_; |
| |
| // Destroy nodes in reverse order. |
| std::reverse(order->begin(), order->end()); |
| |
| return true; |
| } |
| |
| bool DependencyGraph::BuildConstructionOrder() { |
| // Step 1: Build a set of nodes with no incoming edges. |
| std::deque<DependencyNode*> queue; |
| std::copy(all_nodes_.begin(), |
| all_nodes_.end(), |
| std::back_inserter(queue)); |
| |
| std::deque<DependencyNode*>::iterator queue_end = queue.end(); |
| for (EdgeMap::const_iterator it = edges_.begin(); |
| it != edges_.end(); ++it) { |
| queue_end = std::remove(queue.begin(), queue_end, it->second); |
| } |
| queue.erase(queue_end, queue.end()); |
| |
| // Step 2: Do the Kahn topological sort. |
| std::vector<DependencyNode*> output; |
| EdgeMap edges(edges_); |
| while (!queue.empty()) { |
| DependencyNode* node = queue.front(); |
| queue.pop_front(); |
| output.push_back(node); |
| |
| std::pair<EdgeMap::iterator, EdgeMap::iterator> range = |
| edges.equal_range(node); |
| EdgeMap::iterator it = range.first; |
| while (it != range.second) { |
| DependencyNode* dest = it->second; |
| EdgeMap::iterator temp = it; |
| it++; |
| edges.erase(temp); |
| |
| bool has_incoming_edges = false; |
| for (EdgeMap::iterator jt = edges.begin(); jt != edges.end(); ++jt) { |
| if (jt->second == dest) { |
| has_incoming_edges = true; |
| break; |
| } |
| } |
| |
| if (!has_incoming_edges) |
| queue.push_back(dest); |
| } |
| } |
| |
| if (!edges.empty()) { |
| // Dependency graph has a cycle. |
| return false; |
| } |
| |
| construction_order_ = output; |
| return true; |
| } |
| |
| std::string DependencyGraph::DumpAsGraphviz( |
| const std::string& toplevel_name, |
| const base::Callback<std::string(DependencyNode*)>& |
| node_name_callback) const { |
| std::string result("digraph {\n"); |
| |
| // Make a copy of all nodes. |
| std::deque<DependencyNode*> nodes; |
| std::copy(all_nodes_.begin(), all_nodes_.end(), std::back_inserter(nodes)); |
| |
| // State all dependencies and remove |second| so we don't generate an |
| // implicit dependency on the top level node. |
| std::deque<DependencyNode*>::iterator nodes_end(nodes.end()); |
| result.append(" /* Dependencies */\n"); |
| for (EdgeMap::const_iterator it = edges_.begin(); it != edges_.end(); ++it) { |
| result.append(" "); |
| result.append(node_name_callback.Run(it->second)); |
| result.append(" -> "); |
| result.append(node_name_callback.Run(it->first)); |
| result.append(";\n"); |
| |
| nodes_end = std::remove(nodes.begin(), nodes_end, it->second); |
| } |
| nodes.erase(nodes_end, nodes.end()); |
| |
| // Every node that doesn't depend on anything else will implicitly depend on |
| // the top level node. |
| result.append("\n /* Toplevel attachments */\n"); |
| for (std::deque<DependencyNode*>::const_iterator it = |
| nodes.begin(); it != nodes.end(); ++it) { |
| result.append(" "); |
| result.append(node_name_callback.Run(*it)); |
| result.append(" -> "); |
| result.append(toplevel_name); |
| result.append(";\n"); |
| } |
| |
| result.append("\n /* Toplevel node */\n"); |
| result.append(" "); |
| result.append(toplevel_name); |
| result.append(" [shape=box];\n"); |
| |
| result.append("}\n"); |
| return result; |
| } |