dependency_graph.h 2.2 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
  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. #ifndef COMPONENTS_KEYED_SERVICE_CORE_DEPENDENCY_GRAPH_H_
  5. #define COMPONENTS_KEYED_SERVICE_CORE_DEPENDENCY_GRAPH_H_
  6. #include <map>
  7. #include <string>
  8. #include <vector>
  9. #include "base/callback.h"
  10. #include "components/keyed_service/core/keyed_service_export.h"
  11. class DependencyNode;
  12. // Dynamic graph of dependencies between nodes.
  13. class KEYED_SERVICE_EXPORT DependencyGraph {
  14. public:
  15. DependencyGraph();
  16. DependencyGraph(const DependencyGraph&) = delete;
  17. DependencyGraph& operator=(const DependencyGraph&) = delete;
  18. ~DependencyGraph();
  19. // Adds/Removes a node from our list of live nodes. Removing will
  20. // also remove live dependency links.
  21. void AddNode(DependencyNode* node);
  22. void RemoveNode(DependencyNode* node);
  23. // Adds a dependency between two nodes.
  24. void AddEdge(DependencyNode* depended, DependencyNode* dependee);
  25. // Topologically sorts nodes to produce a safe construction order
  26. // (all nodes after their dependees).
  27. [[nodiscard]] bool GetConstructionOrder(std::vector<DependencyNode*>* order);
  28. // Topologically sorts nodes to produce a safe destruction order
  29. // (all nodes before their dependees).
  30. [[nodiscard]] bool GetDestructionOrder(std::vector<DependencyNode*>* order);
  31. // Returns representation of the dependency graph in graphviz format.
  32. std::string DumpAsGraphviz(
  33. const std::string& toplevel_name,
  34. const base::RepeatingCallback<std::string(DependencyNode*)>&
  35. node_name_callback) const;
  36. private:
  37. typedef std::multimap<DependencyNode*, DependencyNode*> EdgeMap;
  38. // Populates |construction_order_| with computed construction order.
  39. // Returns true on success.
  40. [[nodiscard]] bool BuildConstructionOrder();
  41. // Keeps track of all live nodes (see AddNode, RemoveNode).
  42. std::vector<DependencyNode*> all_nodes_;
  43. // Keeps track of edges of the dependency graph.
  44. EdgeMap edges_;
  45. // Cached construction order (needs rebuild with BuildConstructionOrder
  46. // when empty).
  47. std::vector<DependencyNode*> construction_order_;
  48. };
  49. #endif // COMPONENTS_KEYED_SERVICE_CORE_DEPENDENCY_GRAPH_H_