diff options
Diffstat (limited to 'src/mongo/base/initializer_dependency_graph.cpp')
| -rw-r--r-- | src/mongo/base/initializer_dependency_graph.cpp | 149 |
1 files changed, 149 insertions, 0 deletions
diff --git a/src/mongo/base/initializer_dependency_graph.cpp b/src/mongo/base/initializer_dependency_graph.cpp new file mode 100644 index 00000000000..90e259167f4 --- /dev/null +++ b/src/mongo/base/initializer_dependency_graph.cpp @@ -0,0 +1,149 @@ +/* Copyright 2012 10gen Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "mongo/base/initializer_dependency_graph.h" + +#include <algorithm> +#include <iterator> + +namespace mongo { + + InitializerDependencyGraph::InitializerDependencyGraph() {} + InitializerDependencyGraph::~InitializerDependencyGraph() {} + + Status InitializerDependencyGraph::addInitializer(const std::string& name, + const InitializerFunction& fn, + const std::vector<std::string>& prerequisites, + const std::vector<std::string>& dependents) { + if (!fn) + return Status(ErrorCodes::BadValue, "Illegal to supply a NULL function"); + + NodeData& newNode = _nodes[name]; + if (newNode.fn) { + return Status(ErrorCodes::DuplicateKey, name); + } + + newNode.fn = fn; + + for (size_t i = 0; i < prerequisites.size(); ++i) { + newNode.prerequisites.insert(prerequisites[i]); + } + + for (size_t i = 0; i < dependents.size(); ++i) { + _nodes[dependents[i]].prerequisites.insert(name); + } + + return Status::OK; + } + + InitializerFunction InitializerDependencyGraph::getInitializerFunction( + const std::string& name) const { + + NodeMap::const_iterator iter = _nodes.find(name); + if (iter == _nodes.end()) + return InitializerFunction(); + return iter->second.fn; + } + + Status InitializerDependencyGraph::topSort(std::vector<std::string>* sortedNames) const { + /* + * This top-sort is implemented by performing a depth-first traversal of the dependency + * graph, once for each node. "visitedNodeNames" tracks the set of node names ever visited, + * and it is used to prune each DFS. A node that has been visited once on any DFS is never + * visited again. Complexity of this implementation is O(n+m) where "n" is the number of + * nodes and "m" is the number of prerequisite edges. Space complexity is O(n), in both + * stack space and size of the "visitedNodeNames" set. + * + * "inProgressNodeNames" is used to detect and report cycles. + */ + + std::vector<std::string> inProgressNodeNames; + unordered_set<std::string> visitedNodeNames; + + sortedNames->clear(); + for (NodeMap::const_iterator iter = _nodes.begin(), end = _nodes.end(); + iter != end; ++iter) { + + Status status = recursiveTopSort(_nodes, + *iter, + &inProgressNodeNames, + &visitedNodeNames, + sortedNames); + if (Status::OK != status) + return status; + } + return Status::OK; + } + + Status InitializerDependencyGraph::recursiveTopSort( + const NodeMap& nodeMap, + const Node& currentNode, + std::vector<std::string>* inProgressNodeNames, + unordered_set<std::string>* visitedNodeNames, + std::vector<std::string>* sortedNames) { + + /* + * The top sort is performed by depth-first traversal starting at each node in the + * dependency graph, short-circuited any time a node is seen that has already been visited + * in any traversal. "visitedNodeNames" is the set of nodes that have been successfully + * visited, while "inProgressNodeNames" are nodes currently in the exploration chain. This + * structure is kept explicitly to facilitate cycle detection. + * + * This function implements a depth-first traversal, and is called once for each node in the + * graph by topSort(), above. + */ + + if ((*visitedNodeNames).count(currentNode.first)) + return Status::OK; + + if (!currentNode.second.fn) + return Status(ErrorCodes::BadValue, currentNode.first); + + inProgressNodeNames->push_back(currentNode.first); + + std::vector<std::string>::iterator firstOccurence = std::find( + inProgressNodeNames->begin(), inProgressNodeNames->end(), currentNode.first); + if (firstOccurence + 1 != inProgressNodeNames->end()) { + sortedNames->clear(); + std::copy(firstOccurence, inProgressNodeNames->end(), std::back_inserter(*sortedNames)); + return Status(ErrorCodes::GraphContainsCycle, "Cycle in dependency graph"); + } + + for (unordered_set<std::string>::const_iterator + iter = currentNode.second.prerequisites.begin(), + end = currentNode.second.prerequisites.end(); + iter != end; ++iter) { + + NodeMap::const_iterator nextNode = nodeMap.find(*iter); + if (nextNode == nodeMap.end()) + return Status(ErrorCodes::BadValue, *iter); + + Status status = recursiveTopSort(nodeMap, + *nextNode, + inProgressNodeNames, + visitedNodeNames, + sortedNames); + if (Status::OK != status) + return status; + } + sortedNames->push_back(currentNode.first); + if (inProgressNodeNames->back() != currentNode.first) + return Status(ErrorCodes::InternalError, "inProgressNodeNames stack corrupt"); + inProgressNodeNames->pop_back(); + visitedNodeNames->insert(currentNode.first); + return Status::OK; + } + +} // namespace mongo |