components/browser_context_keyed_service/dependency_graph.h

   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_