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