1 files changed, 166 insertions, 0 deletions
diff --git a/components/browser_context_keyed_service/dependency_graph.cc b/components/browser_context_keyed_service/dependency_graph.cc
new file mode 100644
index 0000000..253f5dd
--- /dev/null
+++ b/components/browser_context_keyed_service/dependency_graph.cc
@@ -0,0 +1,166 @@
+// 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;
+}