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/*======
5This file is part of PerconaFT.
6
7
8Copyright (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#ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
38
39#include <db.h>
40#include <toku_assert.h>
41#include <memory.h>
42#include <string.h>
43
44#include "txnid_set.h"
45#include "wfg.h"
46
47namespace toku {
48
49// Create a lock request graph
50void wfg::create(void) {
51 m_nodes.create();
52}
53
54// Destroy the internals of the lock request graph
55void wfg::destroy(void) {
56 size_t n_nodes = m_nodes.size();
57 for (size_t i = 0; i < n_nodes; i++) {
58 node *n;
59 int r = m_nodes.fetch(i, &n);
60 invariant_zero(r);
61 invariant_notnull(n);
62 node::free(n);
63 }
64 m_nodes.destroy();
65}
66
67// Add an edge (a_id, b_id) to the graph
68void wfg::add_edge(TXNID a_txnid, TXNID b_txnid) {
69 node *a_node = find_create_node(a_txnid);
70 node *b_node = find_create_node(b_txnid);
71 a_node->edges.add(b_node->txnid);
72}
73
74// Return true if a node with the given transaction id exists in the graph.
75// Return false otherwise.
76bool wfg::node_exists(TXNID txnid) {
77 node *n = find_node(txnid);
78 return n != NULL;
79}
80
81bool wfg::cycle_exists_from_node(node *target, node *head) {
82 bool cycle_found = false;
83 head->visited = true;
84 size_t n_edges = head->edges.size();
85 for (size_t i = 0; i < n_edges && !cycle_found; i++) {
86 TXNID edge_id = head->edges.get(i);
87 if (target->txnid == edge_id) {
88 cycle_found = true;
89 } else {
90 node *new_head = find_node(edge_id);
91 if (new_head && !new_head->visited) {
92 cycle_found = cycle_exists_from_node(target, new_head);
93 }
94 }
95 }
96 head->visited = false;
97 return cycle_found;
98}
99
100// Return true if there exists a cycle from a given transaction id in the graph.
101// Return false otherwise.
102bool wfg::cycle_exists_from_txnid(TXNID txnid) {
103 node *a_node = find_node(txnid);
104 bool cycles_found = false;
105 if (a_node) {
106 cycles_found = cycle_exists_from_node(a_node, a_node);
107 }
108 return cycles_found;
109}
110
111// Apply a given function f to all of the nodes in the graph. The apply function
112// returns when the function f is called for all of the nodes in the graph, or the
113// function f returns non-zero.
114void wfg::apply_nodes(int (*fn)(TXNID id, void *extra), void *extra) {
115 int r = 0;
116 size_t n_nodes = m_nodes.size();
117 for (size_t i = 0; i < n_nodes && r == 0; i++) {
118 node *n;
119 r = m_nodes.fetch(i, &n);
120 invariant_zero(r);
121 r = fn(n->txnid, extra);
122 }
123}
124
125// Apply a given function f to all of the edges whose origin is a given node id.
126// The apply function returns when the function f is called for all edges in the
127// graph rooted at node id, or the function f returns non-zero.
128void wfg::apply_edges(TXNID txnid,
129 int (*fn)(TXNID txnid, TXNID edge_txnid, void *extra), void *extra) {
130 node *n = find_node(txnid);
131 if (n) {
132 int r = 0;
133 size_t n_edges = n->edges.size();
134 for (size_t i = 0; i < n_edges && r == 0; i++) {
135 r = fn(txnid, n->edges.get(i), extra);
136 }
137 }
138}
139
140// find node by id
141wfg::node *wfg::find_node(TXNID txnid) {
142 node *n = nullptr;
143 int r = m_nodes.find_zero<TXNID, find_by_txnid>(txnid, &n, nullptr);
144 invariant(r == 0 || r == DB_NOTFOUND);
145 return n;
146}
147
148// this is the omt comparison function
149// nodes are compared by their txnid.
150int wfg::find_by_txnid(node *const &node_a, const TXNID &txnid_b) {
151 TXNID txnid_a = node_a->txnid;
152 if (txnid_a < txnid_b) {
153 return -1;
154 } else if (txnid_a == txnid_b) {
155 return 0;
156 } else {
157 return 1;
158 }
159}
160
161// insert a new node
162wfg::node *wfg::find_create_node(TXNID txnid) {
163 node *n;
164 uint32_t idx;
165 int r = m_nodes.find_zero<TXNID, find_by_txnid>(txnid, &n, &idx);
166 if (r == DB_NOTFOUND) {
167 n = node::alloc(txnid);
168 r = m_nodes.insert_at(n, idx);
169 invariant_zero(r);
170 }
171 invariant_notnull(n);
172 return n;
173}
174
175wfg::node *wfg::node::alloc(TXNID txnid) {
176 node *XCALLOC(n);
177 n->txnid = txnid;
178 n->visited = false;
179 n->edges.create();
180 return n;
181}
182
183void wfg::node::free(wfg::node *n) {
184 n->edges.destroy();
185 toku_free(n);
186}
187
188} /* namespace toku */
189