1 // Copyright 2014 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. 4 5 #ifndef COMPONENTS_KEYED_SERVICE_CORE_DEPENDENCY_GRAPH_H_ 6 #define COMPONENTS_KEYED_SERVICE_CORE_DEPENDENCY_GRAPH_H_ 7 8 #include <map> 9 #include <string> 10 #include <vector> 11 12 #include "base/callback.h" 13 #include "base/compiler_specific.h" 14 #include "components/keyed_service/core/keyed_service_export.h" 15 16 class DependencyNode; 17 18 // Dynamic graph of dependencies between nodes. 19 class KEYED_SERVICE_EXPORT DependencyGraph { 20 public: 21 DependencyGraph(); 22 ~DependencyGraph(); 23 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); 28 29 // Adds a dependency between two nodes. 30 void AddEdge(DependencyNode* depended, DependencyNode* dependee); 31 32 // Topologically sorts nodes to produce a safe construction order 33 // (all nodes after their dependees). 34 bool GetConstructionOrder(std::vector<DependencyNode*>* order) 35 WARN_UNUSED_RESULT; 36 37 // Topologically sorts nodes to produce a safe destruction order 38 // (all nodes before their dependees). 39 bool GetDestructionOrder(std::vector<DependencyNode*>* order) 40 WARN_UNUSED_RESULT; 41 42 // Returns representation of the dependency graph in graphviz format. 43 std::string DumpAsGraphviz(const std::string& toplevel_name, 44 const base::Callback<std::string(DependencyNode*)>& 45 node_name_callback) const; 46 47 private: 48 typedef std::multimap<DependencyNode*, DependencyNode*> EdgeMap; 49 50 // Populates |construction_order_| with computed construction order. 51 // Returns true on success. 52 bool BuildConstructionOrder() WARN_UNUSED_RESULT; 53 54 // Keeps track of all live nodes (see AddNode, RemoveNode). 55 std::vector<DependencyNode*> all_nodes_; 56 57 // Keeps track of edges of the dependency graph. 58 EdgeMap edges_; 59 60 // Cached construction order (needs rebuild with BuildConstructionOrder 61 // when empty). 62 std::vector<DependencyNode*> construction_order_; 63 64 DISALLOW_COPY_AND_ASSIGN(DependencyGraph); 65 }; 66 67 #endif // COMPONENTS_KEYED_SERVICE_CORE_DEPENDENCY_GRAPH_H_ 68