| /** |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you 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. |
| **/ |
| |
| #ifndef QUICKSTEP_TRANSACTION_DIRECTED_GRAPH_HPP_ |
| #define QUICKSTEP_TRANSACTION_DIRECTED_GRAPH_HPP_ |
| |
| #include <algorithm> |
| #include <cstddef> |
| #include <cstdint> |
| #include <iterator> |
| #include <memory> |
| #include <unordered_set> |
| #include <vector> |
| |
| #include "transaction/Transaction.hpp" |
| #include "utility/Macros.hpp" |
| |
| #include "glog/logging.h" |
| |
| namespace quickstep { |
| namespace transaction { |
| |
| /** \addtogroup Transaction |
| * @{ |
| */ |
| |
| /** |
| * @brief Class for representing a directed graph. Vertices are transaction |
| * ids, edges are wait-for relations. |
| **/ |
| class DirectedGraph { |
| public: |
| typedef std::uint64_t node_id; |
| |
| /** |
| * @brief Default constructor |
| **/ |
| DirectedGraph() {} |
| |
| /** |
| * @brief Adds a new node to the graph with the given transaction id. |
| * It does not check whether the transaction id is valid or not. |
| * |
| * @param transaction_id_payload Transaction id that will be contained |
| * in the node. |
| * @return Id of the newly created node. |
| **/ |
| inline |
| node_id addNodeUnchecked(const transaction_id transaction_id_payload) { |
| nodes_.emplace_back(transaction_id_payload); |
| return nodes_.size() - 1; |
| } |
| |
| /** |
| * @brief Adds a new node to the graph with the given transaction id. |
| * It checks whether the transaction id is valid or not. |
| * |
| * @param transaction_id_payload Transaction id that will be contained |
| * in the node. |
| * @return Id of the newly created node. |
| **/ |
| node_id addNodeCheckExists(const transaction_id transaction_id_payload) { |
| for (const auto &node : nodes_) { |
| CHECK(transaction_id_payload != node.getData()); |
| } |
| |
| nodes_.emplace_back(transaction_id_payload); |
| return nodes_.size() - 1; |
| } |
| |
| /** |
| * @brief Adds an edge between nodes. It does not check whether the |
| * parameters are valid node ids. |
| * @warning Does not check arguments are legit. It may cause |
| * out of range errors. |
| * |
| * @param fromNode The node that edge is originated. |
| * @param toNode The node that edge is ended. |
| **/ |
| void addEdgeUnchecked(node_id from_node, node_id to_node) { |
| nodes_[from_node].addOutgoingEdge(to_node); |
| } |
| |
| /** |
| * @brief Adds an edge between nodes. It checks whether the |
| * parameters are valid node ids. |
| * |
| * @param fromNode The node that edge is orginated. |
| * @param toNode The node that edge is ended. |
| **/ |
| void addEdgeCheckExists(node_id from_node, node_id to_node) { |
| CHECK(from_node < getNumNodes() && to_node < getNumNodes()); |
| nodes_[from_node].addOutgoingEdge(to_node); |
| } |
| |
| /** |
| * @brief Check whether there is a directed edge. |
| * @warning When parameters are not valid ids, it may cause |
| * out of range errors. |
| * |
| * @param fromNode Id of the node that edge is originated from. |
| * @param toNode Id of the node that edge is ended. |
| * @return True if there is an edge, false otherwise. |
| **/ |
| bool hasEdge(node_id from_node, node_id to_node) const { |
| DCHECK(from_node < getNumNodes() && to_node < getNumNodes()); |
| return nodes_[from_node].hasOutgoingEdge(to_node); |
| } |
| |
| /** |
| * @brief Get data (transaction id) contained in the node. |
| * |
| * @param node Id of the node that the data is got from. |
| * @return Id of the transaction that this node contains. |
| **/ |
| transaction_id getDataFromNode(node_id node) const { |
| DCHECK(node < getNumNodes()); |
| return nodes_[node].getData(); |
| } |
| |
| /** |
| * @brief Calculate how many nodes the graph has. |
| * |
| * @return The number of nodes the graph has. |
| **/ |
| std::size_t getNumNodes() const { |
| return nodes_.size(); |
| } |
| |
| /** |
| * @brief Gives the node ids that this node has edges to. |
| * |
| * @param id Id of the corresponding node. |
| * @return Vector of node ids that id has edges to. |
| **/ |
| inline std::vector<node_id> getAdjacentNodes(node_id id) const { |
| return nodes_[id].getOutgoingEdges(); |
| } |
| |
| private: |
| // Class for representing a graph node. |
| class DirectedGraphNode { |
| public: |
| explicit DirectedGraphNode(const transaction_id payload) |
| : transaction_id_payload_(payload) {} |
| |
| void addOutgoingEdge(node_id to_node) { |
| outgoing_edges_.insert(to_node); |
| } |
| |
| bool hasOutgoingEdge(node_id to_node) const { |
| return outgoing_edges_.count(to_node) == 1; |
| } |
| |
| std::vector<node_id> getOutgoingEdges() const { |
| // TODO(hakan): Benchmark this version and the alternative which the |
| // function returns const reference and the uniqueness |
| // is imposed in the outgoing_edges_ as a vector. |
| std::vector<node_id> result; |
| std::copy(outgoing_edges_.begin(), outgoing_edges_.end(), |
| std::back_inserter(result)); |
| return result; |
| } |
| |
| transaction_id getData() const { |
| return transaction_id_payload_; |
| } |
| |
| private: |
| const transaction_id transaction_id_payload_; |
| |
| // Endpoint nodes of outgoing edges originated from this node. |
| std::unordered_set<node_id> outgoing_edges_; |
| }; |
| |
| // The list of nodes that are created. NodeId is the index of that |
| // node in this buffer. |
| std::vector<DirectedGraphNode> nodes_; |
| |
| DISALLOW_COPY_AND_ASSIGN(DirectedGraph); |
| }; |
| |
| /** @} */ |
| |
| } // namespace transaction |
| } // namespace quickstep |
| |
| #endif // QUICKSTEP_TRANSACTION_DIRECTED_GRAPH_HPP_ |