1 2 /** 3 * Copyright (C) 2018-present MongoDB, Inc. 4 * 5 * This program is free software: you can redistribute it and/or modify 6 * it under the terms of the Server Side Public License, version 1, 7 * as published by MongoDB, Inc. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * Server Side Public License for more details. 13 * 14 * You should have received a copy of the Server Side Public License 15 * along with this program. If not, see 16 * <http://www.mongodb.com/licensing/server-side-public-license>. 17 * 18 * As a special exception, the copyright holders give permission to link the 19 * code of portions of this program with the OpenSSL library under certain 20 * conditions as described in each individual source file and distribute 21 * linked combinations including the program with the OpenSSL library. You 22 * must comply with the Server Side Public License in all respects for 23 * all of the code used other than as permitted herein. If you modify file(s) 24 * with this exception, you may extend this exception to your version of the 25 * file(s), but you are not obligated to do so. If you do not wish to do so, 26 * delete this exception statement from your version. If you delete this 27 * exception statement from all source files in the program, then also delete 28 * it in the license file. 29 */ 30 31 #pragma once 32 33 #include <string> 34 #include <utility> 35 #include <vector> 36 37 #include "mongo/base/disallow_copying.h" 38 #include "mongo/base/initializer_function.h" 39 #include "mongo/base/status.h" 40 #include "mongo/platform/unordered_map.h" 41 #include "mongo/platform/unordered_set.h" 42 43 namespace mongo { 44 45 /** 46 * Representation of a dependency graph of "initialization operations." 47 * 48 * Each operation has a unique name, a function object implementing the operation's behavior, 49 * and a set of prerequisite operations, which may be empty. A legal graph contains no cycles. 50 * 51 * Instances of this class are used in two phases. In the first phase, the graph is constructed 52 * by repeated calls to addInitializer(). In the second phase, a user calls the topSort() 53 * method to produce an initialization order that respects the dependencies among operations, and 54 * then uses the getInitializerFunction() to get the behavior function for each operation, in 55 * turn. 56 * 57 * Concurrency Notes: The user is responsible for synchronization. Multiple threads may 58 * simultaneously call the const functions, getInitializerFunction and topSort, on the same 59 * instance of InitializerDependencyGraph. However, no thread may call addInitializer while any 60 * thread is executing those functions or addInitializer on the same instance. 61 */ 62 class InitializerDependencyGraph { 63 MONGO_DISALLOW_COPYING(InitializerDependencyGraph); 64 65 public: 66 InitializerDependencyGraph(); 67 ~InitializerDependencyGraph(); 68 69 /** 70 * Add a new initializer node, named "name", to the dependency graph, with the given 71 * behavior, "fn", and the given "prerequisites" (input dependencies) and "dependents" 72 * (output dependencies). 73 * 74 * If "!fn" (fn is NULL in function pointer parlance), returns status with code 75 * ErrorCodes::badValue. If "name" is a duplicate of a name already present in the graph, 76 * returns "ErrorCodes::duplicateKey". Otherwise, returns Status::OK() and adds the new node 77 * to the graph. Note that cycles in the dependency graph are not discovered in this phase. 78 * Rather, they're discovered by topSort, below. 79 */ 80 Status addInitializer(const std::string& name, 81 const InitializerFunction& fn, 82 const std::vector<std::string>& prerequisites, 83 const std::vector<std::string>& dependents); 84 85 /** 86 * Given a dependency operation node named "name", return its behavior function. Returns 87 * a value that evaluates to "false" in boolean context, otherwise. 88 */ 89 InitializerFunction getInitializerFunction(const std::string& name) const; 90 91 /** 92 * Construct a topological sort of the dependency graph, and store that order into 93 * "sortedNames". Returns Status::OK() on success. 94 * 95 * If the graph contains a cycle, returns ErrorCodes::graphContainsCycle, and "sortedNames" 96 * is an ordered sequence of nodes involved in a cycle. In this case, the first and last 97 * element of "sortedNames" will be equal. 98 * 99 * If any node in the graph names a prerequisite that was never added to the graph via 100 * addInitializer, this function will return ErrorCodes::badValue. 101 * 102 * Any other return value indicates an internal error, and should not occur. 103 */ 104 Status topSort(std::vector<std::string>* sortedNames) const; 105 106 private: 107 struct NodeData { 108 InitializerFunction fn; 109 unordered_set<std::string> prerequisites; 110 }; 111 112 typedef unordered_map<std::string, NodeData> NodeMap; 113 typedef NodeMap::value_type Node; 114 115 /** 116 * Helper function to recursively top-sort a graph. Used by topSort(). 117 */ 118 static Status recursiveTopSort(const NodeMap& nodeMap, 119 const Node& currentNode, 120 std::vector<std::string>* inProgressNodeNames, 121 unordered_set<std::string>* visitedNodeNames, 122 std::vector<std::string>* sortedNames); 123 124 /** 125 * Map of all named nodes. Nodes named as prerequisites or dependents but not explicitly 126 * added via addInitializer will either be absent from this map or be present with 127 * NodeData::fn set to a false-ish value. 128 */ 129 NodeMap _nodes; 130 }; 131 132 } // namespace mongo 133