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. 4 5#ifndef COMPONENTS_BROWSER_CONTEXT_KEYED_SERVICE_DEPENDENCY_GRAPH_H_ 6#define COMPONENTS_BROWSER_CONTEXT_KEYED_SERVICE_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/browser_context_keyed_service/browser_context_keyed_service_export.h" 15 16class DependencyNode; 17 18// Dynamic graph of dependencies between nodes. 19class BROWSER_CONTEXT_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( 35 std::vector<DependencyNode*>* order) WARN_UNUSED_RESULT; 36 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; 41 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; 47 48 private: 49 typedef std::multimap<DependencyNode*, DependencyNode*> EdgeMap; 50 51 // Populates |construction_order_| with computed construction order. 52 // Returns true on success. 53 bool BuildConstructionOrder() WARN_UNUSED_RESULT; 54 55 // Keeps track of all live nodes (see AddNode, RemoveNode). 56 std::vector<DependencyNode*> all_nodes_; 57 58 // Keeps track of edges of the dependency graph. 59 EdgeMap edges_; 60 61 // Cached construction order (needs rebuild with BuildConstructionOrder 62 // when empty). 63 std::vector<DependencyNode*> construction_order_; 64 65 DISALLOW_COPY_AND_ASSIGN(DependencyGraph); 66}; 67 68#endif // COMPONENTS_BROWSER_CONTEXT_KEYED_SERVICE_DEPENDENCY_GRAPH_H_ 69