]>
Commit | Line | Data |
---|---|---|
1e59de90 TL |
1 | /* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */ |
2 | // vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4: | |
3 | #ifndef ROCKSDB_LITE | |
4 | #ifndef OS_WIN | |
5 | #ident "$Id$" | |
6 | /*====== | |
7 | This file is part of PerconaFT. | |
8 | ||
9 | ||
10 | Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. | |
11 | ||
12 | PerconaFT is free software: you can redistribute it and/or modify | |
13 | it under the terms of the GNU General Public License, version 2, | |
14 | as published by the Free Software Foundation. | |
15 | ||
16 | PerconaFT is distributed in the hope that it will be useful, | |
17 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
18 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
19 | GNU General Public License for more details. | |
20 | ||
21 | You should have received a copy of the GNU General Public License | |
22 | along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. | |
23 | ||
24 | ---------------------------------------- | |
25 | ||
26 | PerconaFT is free software: you can redistribute it and/or modify | |
27 | it under the terms of the GNU Affero General Public License, version 3, | |
28 | as published by the Free Software Foundation. | |
29 | ||
30 | PerconaFT is distributed in the hope that it will be useful, | |
31 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
32 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
33 | GNU Affero General Public License for more details. | |
34 | ||
35 | You should have received a copy of the GNU Affero General Public License | |
36 | along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. | |
37 | ||
38 | ---------------------------------------- | |
39 | ||
40 | Licensed under the Apache License, Version 2.0 (the "License"); | |
41 | you may not use this file except in compliance with the License. | |
42 | You may obtain a copy of the License at | |
43 | ||
44 | http://www.apache.org/licenses/LICENSE-2.0 | |
45 | ||
46 | Unless required by applicable law or agreed to in writing, software | |
47 | distributed under the License is distributed on an "AS IS" BASIS, | |
48 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
49 | See the License for the specific language governing permissions and | |
50 | limitations under the License. | |
51 | ======= */ | |
52 | ||
53 | #ident \ | |
54 | "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." | |
55 | ||
56 | #include "../db.h" | |
57 | #include "../portability/memory.h" | |
58 | // PORT #include <toku_assert.h> | |
59 | #include <memory.h> | |
60 | #include <string.h> | |
61 | ||
62 | #include "txnid_set.h" | |
63 | #include "wfg.h" | |
64 | ||
65 | namespace toku { | |
66 | ||
67 | // Create a lock request graph | |
68 | void wfg::create(void) { m_nodes.create(); } | |
69 | ||
70 | // Destroy the internals of the lock request graph | |
71 | void wfg::destroy(void) { | |
72 | uint32_t n_nodes = m_nodes.size(); | |
73 | for (uint32_t i = 0; i < n_nodes; i++) { | |
74 | node *n; | |
75 | int r = m_nodes.fetch(i, &n); | |
76 | invariant_zero(r); | |
77 | invariant_notnull(n); | |
78 | if (r) continue; // Get rid of "may be used uninitialized" warning | |
79 | node::free(n); | |
80 | } | |
81 | m_nodes.destroy(); | |
82 | } | |
83 | ||
84 | // Add an edge (a_id, b_id) to the graph | |
85 | void wfg::add_edge(TXNID a_txnid, TXNID b_txnid) { | |
86 | node *a_node = find_create_node(a_txnid); | |
87 | node *b_node = find_create_node(b_txnid); | |
88 | a_node->edges.add(b_node->txnid); | |
89 | } | |
90 | ||
91 | // Return true if a node with the given transaction id exists in the graph. | |
92 | // Return false otherwise. | |
93 | bool wfg::node_exists(TXNID txnid) { | |
94 | node *n = find_node(txnid); | |
95 | return n != NULL; | |
96 | } | |
97 | ||
98 | bool wfg::cycle_exists_from_node(node *target, node *head, | |
99 | std::function<void(TXNID)> reporter) { | |
100 | bool cycle_found = false; | |
101 | head->visited = true; | |
102 | uint32_t n_edges = head->edges.size(); | |
103 | for (uint32_t i = 0; i < n_edges && !cycle_found; i++) { | |
104 | TXNID edge_id = head->edges.get(i); | |
105 | if (target->txnid == edge_id) { | |
106 | cycle_found = true; | |
107 | if (reporter) reporter(edge_id); | |
108 | } else { | |
109 | node *new_head = find_node(edge_id); | |
110 | if (new_head && !new_head->visited) { | |
111 | cycle_found = cycle_exists_from_node(target, new_head, reporter); | |
112 | if (cycle_found && reporter) reporter(edge_id); | |
113 | } | |
114 | } | |
115 | } | |
116 | head->visited = false; | |
117 | return cycle_found; | |
118 | } | |
119 | ||
120 | // Return true if there exists a cycle from a given transaction id in the graph. | |
121 | // Return false otherwise. | |
122 | bool wfg::cycle_exists_from_txnid(TXNID txnid, | |
123 | std::function<void(TXNID)> reporter) { | |
124 | node *a_node = find_node(txnid); | |
125 | bool cycles_found = false; | |
126 | if (a_node) { | |
127 | cycles_found = cycle_exists_from_node(a_node, a_node, reporter); | |
128 | } | |
129 | return cycles_found; | |
130 | } | |
131 | ||
132 | // Apply a given function f to all of the nodes in the graph. The apply | |
133 | // function returns when the function f is called for all of the nodes in the | |
134 | // graph, or the function f returns non-zero. | |
135 | void wfg::apply_nodes(int (*fn)(TXNID id, void *extra), void *extra) { | |
136 | int r = 0; | |
137 | uint32_t n_nodes = m_nodes.size(); | |
138 | for (uint32_t i = 0; i < n_nodes && r == 0; i++) { | |
139 | node *n; | |
140 | r = m_nodes.fetch(i, &n); | |
141 | invariant_zero(r); | |
142 | if (r) continue; // Get rid of "may be used uninitialized" warning | |
143 | r = fn(n->txnid, extra); | |
144 | } | |
145 | } | |
146 | ||
147 | // Apply a given function f to all of the edges whose origin is a given node id. | |
148 | // The apply function returns when the function f is called for all edges in the | |
149 | // graph rooted at node id, or the function f returns non-zero. | |
150 | void wfg::apply_edges(TXNID txnid, | |
151 | int (*fn)(TXNID txnid, TXNID edge_txnid, void *extra), | |
152 | void *extra) { | |
153 | node *n = find_node(txnid); | |
154 | if (n) { | |
155 | int r = 0; | |
156 | uint32_t n_edges = n->edges.size(); | |
157 | for (uint32_t i = 0; i < n_edges && r == 0; i++) { | |
158 | r = fn(txnid, n->edges.get(i), extra); | |
159 | } | |
160 | } | |
161 | } | |
162 | ||
163 | // find node by id | |
164 | wfg::node *wfg::find_node(TXNID txnid) { | |
165 | node *n = nullptr; | |
166 | int r = m_nodes.find_zero<TXNID, find_by_txnid>(txnid, &n, nullptr); | |
167 | invariant(r == 0 || r == DB_NOTFOUND); | |
168 | return n; | |
169 | } | |
170 | ||
171 | // this is the omt comparison function | |
172 | // nodes are compared by their txnid. | |
173 | int wfg::find_by_txnid(node *const &node_a, const TXNID &txnid_b) { | |
174 | TXNID txnid_a = node_a->txnid; | |
175 | if (txnid_a < txnid_b) { | |
176 | return -1; | |
177 | } else if (txnid_a == txnid_b) { | |
178 | return 0; | |
179 | } else { | |
180 | return 1; | |
181 | } | |
182 | } | |
183 | ||
184 | // insert a new node | |
185 | wfg::node *wfg::find_create_node(TXNID txnid) { | |
186 | node *n; | |
187 | uint32_t idx; | |
188 | int r = m_nodes.find_zero<TXNID, find_by_txnid>(txnid, &n, &idx); | |
189 | if (r == DB_NOTFOUND) { | |
190 | n = node::alloc(txnid); | |
191 | r = m_nodes.insert_at(n, idx); | |
192 | invariant_zero(r); | |
193 | } | |
194 | invariant_notnull(n); | |
195 | return n; | |
196 | } | |
197 | ||
198 | wfg::node *wfg::node::alloc(TXNID txnid) { | |
199 | node *XCALLOC(n); | |
200 | n->txnid = txnid; | |
201 | n->visited = false; | |
202 | n->edges.create(); | |
203 | return n; | |
204 | } | |
205 | ||
206 | void wfg::node::free(wfg::node *n) { | |
207 | n->edges.destroy(); | |
208 | toku_free(n); | |
209 | } | |
210 | ||
211 | } /* namespace toku */ | |
212 | #endif // OS_WIN | |
213 | #endif // ROCKSDB_LITE |