1 files changed, 67 insertions, 0 deletions
diff --git a/components/browser_context_keyed_service/dependency_graph.h b/components/browser_context_keyed_service/dependency_graph.h
new file mode 100644
index 0000000..0f5d66a
--- /dev/null
+++ b/components/browser_context_keyed_service/dependency_graph.h
@@ -0,0 +1,67 @@
+// 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.
+
+#ifndef COMPONENTS_BROWSER_CONTEXT_KEYED_SERVICE_DEPENDENCY_GRAPH_H_
+#define COMPONENTS_BROWSER_CONTEXT_KEYED_SERVICE_DEPENDENCY_GRAPH_H_
+
+#include <map>
+#include <string>
+#include <vector>
+
+#include "base/callback.h"
+#include "base/compiler_specific.h"
+
+class DependencyNode;
+
+// Dynamic graph of dependencies between nodes.
+class DependencyGraph {
+ public:
+  DependencyGraph();
+  ~DependencyGraph();
+
+  // Adds/Removes a node from our list of live nodes. Removing will
+  // also remove live dependency links.
+  void AddNode(DependencyNode* node);
+  void RemoveNode(DependencyNode* node);
+
+  // Adds a dependency between two nodes.
+  void AddEdge(DependencyNode* depended, DependencyNode* dependee);
+
+  // Topologically sorts nodes to produce a safe construction order
+  // (all nodes after their dependees).
+  bool GetConstructionOrder(
+      std::vector<DependencyNode*>* order) WARN_UNUSED_RESULT;
+
+  // Topologically sorts nodes to produce a safe destruction order
+  // (all nodes before their dependees).
+  bool GetDestructionOrder(
+      std::vector<DependencyNode*>* order) WARN_UNUSED_RESULT;
+
+  // Returns representation of the dependency graph in graphviz format.
+  std::string DumpAsGraphviz(
+      const std::string& toplevel_name,
+      const base::Callback<std::string(DependencyNode*)>&
+      node_name_callback) const;
+
+ private:
+  typedef std::multimap<DependencyNode*, DependencyNode*> EdgeMap;
+
+  // Populates |construction_order_| with computed construction order.
+  // Returns true on success.
+  bool BuildConstructionOrder() WARN_UNUSED_RESULT;
+
+  // Keeps track of all live nodes (see AddNode, RemoveNode).
+  std::vector<DependencyNode*> all_nodes_;
+
+  // Keeps track of edges of the dependency graph.
+  EdgeMap edges_;
+
+  // Cached construction order (needs rebuild with BuildConstructionOrder
+  // when empty).
+  std::vector<DependencyNode*> construction_order_;
+
+  DISALLOW_COPY_AND_ASSIGN(DependencyGraph);
+};
+
+#endif  // COMPONENTS_BROWSER_CONTEXT_KEYED_SERVICE_DEPENDENCY_GRAPH_H_