1 // Copyright 2013 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 #ifndef COMPONENTS_BROWSER_CONTEXT_KEYED_SERVICE_DEPENDENCY_GRAPH_H_
6 #define COMPONENTS_BROWSER_CONTEXT_KEYED_SERVICE_DEPENDENCY_GRAPH_H_
12 #include "base/callback.h"
13 #include "base/compiler_specific.h"
14 #include "components/browser_context_keyed_service/browser_context_keyed_service_export.h"
18 // Dynamic graph of dependencies between nodes.
19 class BROWSER_CONTEXT_KEYED_SERVICE_EXPORT DependencyGraph {
24 // Adds/Removes a node from our list of live nodes. Removing will
25 // also remove live dependency links.
26 void AddNode(DependencyNode* node);
27 void RemoveNode(DependencyNode* node);
29 // Adds a dependency between two nodes.
30 void AddEdge(DependencyNode* depended, DependencyNode* dependee);
32 // Topologically sorts nodes to produce a safe construction order
33 // (all nodes after their dependees).
34 bool GetConstructionOrder(
35 std::vector<DependencyNode*>* order) WARN_UNUSED_RESULT;
37 // Topologically sorts nodes to produce a safe destruction order
38 // (all nodes before their dependees).
39 bool GetDestructionOrder(
40 std::vector<DependencyNode*>* order) WARN_UNUSED_RESULT;
42 // Returns representation of the dependency graph in graphviz format.
43 std::string DumpAsGraphviz(
44 const std::string& toplevel_name,
45 const base::Callback<std::string(DependencyNode*)>&
46 node_name_callback) const;
49 typedef std::multimap<DependencyNode*, DependencyNode*> EdgeMap;
51 // Populates |construction_order_| with computed construction order.
52 // Returns true on success.
53 bool BuildConstructionOrder() WARN_UNUSED_RESULT;
55 // Keeps track of all live nodes (see AddNode, RemoveNode).
56 std::vector<DependencyNode*> all_nodes_;
58 // Keeps track of edges of the dependency graph.
61 // Cached construction order (needs rebuild with BuildConstructionOrder
63 std::vector<DependencyNode*> construction_order_;
65 DISALLOW_COPY_AND_ASSIGN(DependencyGraph);
68 #endif // COMPONENTS_BROWSER_CONTEXT_KEYED_SERVICE_DEPENDENCY_GRAPH_H_