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 #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
38
39 #include <locktree/wfg.h>
40
41 namespace toku {
42
43 enum {
44 WFG_TEST_MAX_TXNID = 10
45 };
46
47 struct visit_extra {
48 bool nodes_visited[WFG_TEST_MAX_TXNID];
49 bool edges_visited[WFG_TEST_MAX_TXNID][WFG_TEST_MAX_TXNID];
50
cleartoku::visit_extra51 void clear(void) {
52 memset(nodes_visited, 0, sizeof(nodes_visited));
53 memset(edges_visited, 0, sizeof(edges_visited));
54 }
55 };
56
57 // wfg node visit callback
visit_nodes(TXNID txnid,void * extra)58 static int visit_nodes(TXNID txnid, void *extra) {
59 visit_extra *ve = static_cast<visit_extra *>(extra);
60 invariant(txnid < WFG_TEST_MAX_TXNID);
61 invariant(!ve->nodes_visited[txnid]);
62 ve->nodes_visited[txnid] = true;
63 return 0;
64 }
65
66 // wfg edge visit callback
visit_edges(TXNID txnid,TXNID edge_txnid,void * extra)67 static int visit_edges(TXNID txnid, TXNID edge_txnid, void *extra) {
68 visit_extra *ve = static_cast<visit_extra *>(extra);
69 invariant(txnid < WFG_TEST_MAX_TXNID);
70 invariant(edge_txnid < WFG_TEST_MAX_TXNID);
71 invariant(!ve->edges_visited[txnid][edge_txnid]);
72 ve->edges_visited[txnid][edge_txnid] = true;
73 return 0;
74 }
75
76 // the graph should only have 3 nodes labelled 0 1 and 2
verify_only_nodes_012_exist(wfg * g)77 static void verify_only_nodes_012_exist(wfg *g) {
78 visit_extra ve;
79 ve.clear();
80 g->apply_nodes(visit_nodes, &ve);
81 for (int i = 0; i < WFG_TEST_MAX_TXNID; i++) {
82 if (i == 0 || i == 1 || i == 2) {
83 invariant(ve.nodes_visited[i]);
84 } else {
85 invariant(!ve.nodes_visited[i]);
86 }
87 }
88 }
89
90 // the graph should only have edges 0->1 and 1->2
verify_only_edges_01_12_exist(wfg * g)91 static void verify_only_edges_01_12_exist(wfg *g) {
92 visit_extra ve;
93 ve.clear();
94 g->apply_edges(0, visit_edges, &ve);
95 g->apply_edges(1, visit_edges, &ve);
96 g->apply_edges(2, visit_edges, &ve);
97 for (int i = 0; i < WFG_TEST_MAX_TXNID; i++) {
98 for (int j = 0; j < WFG_TEST_MAX_TXNID; j++) {
99 if ((i == 0 && j == 1) || (i == 1 && j == 2)) {
100 invariant(ve.edges_visited[i][j]);
101 } else {
102 invariant(!ve.edges_visited[i][j]);
103 }
104 }
105 }
106 }
107
test_add_cycle_exists()108 static void test_add_cycle_exists() {
109 wfg g;
110 g.create();
111
112 // test that adding edges works and is idempotent
113
114 g.add_edge(0, 1);
115 invariant(g.node_exists(0));
116 invariant(g.node_exists(1));
117 g.add_edge(1, 2);
118 invariant(g.node_exists(0));
119 invariant(g.node_exists(1));
120 invariant(g.node_exists(2));
121
122 // verify that adding edges with the same nodes
123 // does not store multiple nodes with the same txnid.
124 verify_only_nodes_012_exist(&g);
125 verify_only_edges_01_12_exist(&g);
126 g.add_edge(0, 1);
127 g.add_edge(1, 2);
128 verify_only_nodes_012_exist(&g);
129 verify_only_edges_01_12_exist(&g);
130
131 // confirm that no cycle exists from txnid 0 1 or 2
132 invariant(!g.cycle_exists_from_txnid(0));
133 invariant(!g.cycle_exists_from_txnid(1));
134 invariant(!g.cycle_exists_from_txnid(2));
135
136 // add 2,3 and 3,1. now there should be a cycle
137 // from 1 2 and 3 but not 0.
138 //
139 // 0 --> 1 --> 2
140 // ^ /
141 // ^ 3 <
142 g.add_edge(2, 3);
143 g.add_edge(3, 1);
144 invariant(!g.cycle_exists_from_txnid(0));
145 invariant(g.cycle_exists_from_txnid(1));
146 invariant(g.cycle_exists_from_txnid(2));
147 invariant(g.cycle_exists_from_txnid(3));
148
149 // add 2,4. should not have a cycle from 4, but yes from 2.
150 g.add_edge(2, 4);
151 invariant(!g.cycle_exists_from_txnid(4));
152 invariant(g.cycle_exists_from_txnid(2));
153
154 g.destroy();
155 }
156
test_find_cycles()157 static void test_find_cycles() {
158 wfg g;
159 g.create();
160
161 // TODO: verify that finding cycles works
162
163 g.destroy();
164 }
165
166 } /* namespace toku */
167
main(void)168 int main(void) {
169 toku::test_add_cycle_exists();
170 toku::test_find_cycles();
171 return 0;
172 }
173