Home | History | Annotate | Download | only in browser_context_keyed_service 
      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 
     16 class DependencyNode;
     17 
     18 // Dynamic graph of dependencies between nodes.
     19 class 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