ceph/src/rocksdb/utilities/transactions/lock/range/range_tree/lib/locktree/wfg.h

   1 /* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
   2 // vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
   3 #ident "$Id$"
   4 /*======
   5 This file is part of PerconaFT.
   6
   7
   8 Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.
   9
  10     PerconaFT is free software: you can redistribute it and/or modify
  11     it under the terms of the GNU General Public License, version 2,
  12     as published by the Free Software Foundation.
  13
  14     PerconaFT is distributed in the hope that it will be useful,
  15     but WITHOUT ANY WARRANTY; without even the implied warranty of
  16     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17     GNU General Public License for more details.
  18
  19     You should have received a copy of the GNU General Public License
  20     along with PerconaFT.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 ----------------------------------------
  23
  24     PerconaFT is free software: you can redistribute it and/or modify
  25     it under the terms of the GNU Affero General Public License, version 3,
  26     as published by the Free Software Foundation.
  27
  28     PerconaFT is distributed in the hope that it will be useful,
  29     but WITHOUT ANY WARRANTY; without even the implied warranty of
  30     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  31     GNU Affero General Public License for more details.
  32
  33     You should have received a copy of the GNU Affero General Public License
  34     along with PerconaFT.  If not, see <http://www.gnu.org/licenses/>.
  35
  36 ----------------------------------------
  37
  38    Licensed under the Apache License, Version 2.0 (the "License");
  39    you may not use this file except in compliance with the License.
  40    You may obtain a copy of the License at
  41
  42        http://www.apache.org/licenses/LICENSE-2.0
  43
  44    Unless required by applicable law or agreed to in writing, software
  45    distributed under the License is distributed on an "AS IS" BASIS,
  46    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  47    See the License for the specific language governing permissions and
  48    limitations under the License.
  49 ======= */
  50
  51 #ident \
  52     "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
  53
  54 #pragma once
  55
  56 #include <functional>
  57
  58 #include "../util/omt.h"
  59 #include "txnid_set.h"
  60
  61 namespace toku {
  62
  63 // A wfg is a 'wait-for' graph. A directed edge in represents one
  64 // txn waiting for another to finish before it can acquire a lock.
  65
  66 class wfg {
  67  public:
  68   // Create a lock request graph
  69   void create(void);
  70
  71   // Destroy the internals of the lock request graph
  72   void destroy(void);
  73
  74   // Add an edge (a_id, b_id) to the graph
  75   void add_edge(TXNID a_txnid, TXNID b_txnid);
  76
  77   // Return true if a node with the given transaction id exists in the graph.
  78   // Return false otherwise.
  79   bool node_exists(TXNID txnid);
  80
  81   // Return true if there exists a cycle from a given transaction id in the
  82   // graph. Return false otherwise.
  83   bool cycle_exists_from_txnid(TXNID txnid,
  84                                std::function<void(TXNID)> reporter);
  85
  86   // Apply a given function f to all of the nodes in the graph.  The apply
  87   // function returns when the function f is called for all of the nodes in the
  88   // graph, or the function f returns non-zero.
  89   void apply_nodes(int (*fn)(TXNID txnid, void *extra), void *extra);
  90
  91   // Apply a given function f to all of the edges whose origin is a given node
  92   // id. The apply function returns when the function f is called for all edges
  93   // in the graph rooted at node id, or the function f returns non-zero.
  94   void apply_edges(TXNID txnid,
  95                    int (*fn)(TXNID txnid, TXNID edge_txnid, void *extra),
  96                    void *extra);
  97
  98  private:
  99   struct node {
 100     // txnid for this node and the associated set of edges
 101     TXNID txnid;
 102     txnid_set edges;
 103     bool visited;
 104
 105     static node *alloc(TXNID txnid);
 106
 107     static void free(node *n);
 108   };
 109   ENSURE_POD(node);
 110
 111   toku::omt<node *> m_nodes;
 112
 113   node *find_node(TXNID txnid);
 114
 115   node *find_create_node(TXNID txnid);
 116
 117   bool cycle_exists_from_node(node *target, node *head,
 118                               std::function<void(TXNID)> reporter);
 119
 120   static int find_by_txnid(node *const &node_a, const TXNID &txnid_b);
 121 };
 122 ENSURE_POD(wfg);
 123
 124 } /* namespace toku */