12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667 |
- // Copyright 2014 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #ifndef COMPONENTS_KEYED_SERVICE_CORE_DEPENDENCY_GRAPH_H_
- #define COMPONENTS_KEYED_SERVICE_CORE_DEPENDENCY_GRAPH_H_
- #include <map>
- #include <string>
- #include <vector>
- #include "base/callback.h"
- #include "components/keyed_service/core/keyed_service_export.h"
- class DependencyNode;
- // Dynamic graph of dependencies between nodes.
- class KEYED_SERVICE_EXPORT DependencyGraph {
- public:
- DependencyGraph();
- DependencyGraph(const DependencyGraph&) = delete;
- DependencyGraph& operator=(const DependencyGraph&) = delete;
- ~DependencyGraph();
- // Adds/Removes a node from our list of live nodes. Removing will
- // also remove live dependency links.
- void AddNode(DependencyNode* node);
- void RemoveNode(DependencyNode* node);
- // Adds a dependency between two nodes.
- void AddEdge(DependencyNode* depended, DependencyNode* dependee);
- // Topologically sorts nodes to produce a safe construction order
- // (all nodes after their dependees).
- [[nodiscard]] bool GetConstructionOrder(std::vector<DependencyNode*>* order);
- // Topologically sorts nodes to produce a safe destruction order
- // (all nodes before their dependees).
- [[nodiscard]] bool GetDestructionOrder(std::vector<DependencyNode*>* order);
- // Returns representation of the dependency graph in graphviz format.
- std::string DumpAsGraphviz(
- const std::string& toplevel_name,
- const base::RepeatingCallback<std::string(DependencyNode*)>&
- node_name_callback) const;
- private:
- typedef std::multimap<DependencyNode*, DependencyNode*> EdgeMap;
- // Populates |construction_order_| with computed construction order.
- // Returns true on success.
- [[nodiscard]] bool BuildConstructionOrder();
- // Keeps track of all live nodes (see AddNode, RemoveNode).
- std::vector<DependencyNode*> all_nodes_;
- // Keeps track of edges of the dependency graph.
- EdgeMap edges_;
- // Cached construction order (needs rebuild with BuildConstructionOrder
- // when empty).
- std::vector<DependencyNode*> construction_order_;
- };
- #endif // COMPONENTS_KEYED_SERVICE_CORE_DEPENDENCY_GRAPH_H_
|