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 // generate a tree with unsorted pivots and check that ft->verify finds them
40
41
42 #include <ft-cachetable-wrappers.h>
43 #include "test.h"
44
45 static FTNODE
make_node(FT_HANDLE ft,int height)46 make_node(FT_HANDLE ft, int height) {
47 FTNODE node = NULL;
48 int n_children = (height == 0) ? 1 : 0;
49 toku_create_new_ftnode(ft, &node, height, n_children);
50 if (n_children) BP_STATE(node,0) = PT_AVAIL;
51 return node;
52 }
53
54 static void
append_leaf(FTNODE leafnode,void * key,size_t keylen,void * val,size_t vallen)55 append_leaf(FTNODE leafnode, void *key, size_t keylen, void *val, size_t vallen) {
56 assert(leafnode->height == 0);
57
58 DBT thekey; toku_fill_dbt(&thekey, key, keylen);
59 DBT theval; toku_fill_dbt(&theval, val, vallen);
60
61 // get an index that we can use to create a new leaf entry
62 uint32_t idx = BLB_DATA(leafnode, 0)->num_klpairs();
63
64 // apply an insert to the leaf node
65 MSN msn = next_dummymsn();
66 ft_msg msg(&thekey, &theval, FT_INSERT, msn, toku_xids_get_root_xids());
67 txn_gc_info gc_info(nullptr, TXNID_NONE, TXNID_NONE, false);
68 toku_ft_bn_apply_msg_once(
69 BLB(leafnode, 0),
70 msg,
71 idx,
72 keylen,
73 NULL,
74 &gc_info,
75 NULL,
76 NULL,
77 NULL);
78
79 // don't forget to dirty the node
80 leafnode->set_dirty();
81 }
82
83 static void
populate_leaf(FTNODE leafnode,int seq,int n,int * minkey,int * maxkey)84 populate_leaf(FTNODE leafnode, int seq, int n, int *minkey, int *maxkey) {
85 for (int i = 0; i < n; i++) {
86 int k = htonl(seq + i);
87 int v = seq + i;
88 append_leaf(leafnode, &k, sizeof k, &v, sizeof v);
89 }
90 *minkey = htonl(seq);
91 *maxkey = htonl(seq + n - 1);
92 }
93
94 static FTNODE
make_tree(FT_HANDLE ft,int height,int fanout,int nperleaf,int * seq,int * minkey,int * maxkey)95 make_tree(FT_HANDLE ft, int height, int fanout, int nperleaf, int *seq, int *minkey, int *maxkey) {
96 FTNODE node;
97 if (height == 0) {
98 node = make_node(ft, 0);
99 populate_leaf(node, *seq, nperleaf, minkey, maxkey);
100 *seq += nperleaf;
101 } else {
102 node = make_node(ft, height);
103 int minkeys[fanout], maxkeys[fanout];
104 for (int childnum = 0; childnum < fanout; childnum++) {
105 FTNODE child = make_tree(ft, height-1, fanout, nperleaf, seq, &minkeys[childnum], &maxkeys[childnum]);
106 if (childnum == 0) {
107 toku_ft_nonleaf_append_child(node, child, NULL);
108 } else {
109 int k = minkeys[fanout - childnum - 1]; // use unsorted pivots
110 DBT pivotkey;
111 toku_ft_nonleaf_append_child(node, child, toku_fill_dbt(&pivotkey, &k, sizeof k));
112 }
113 toku_unpin_ftnode(ft->ft, child);
114 }
115 *minkey = minkeys[0];
116 *maxkey = maxkeys[0];
117 for (int i = 1; i < fanout; i++) {
118 if (memcmp(minkey, &minkeys[i], sizeof minkeys[i]) > 0)
119 *minkey = minkeys[i];
120 if (memcmp(maxkey, &maxkeys[i], sizeof maxkeys[i]) < 0)
121 *maxkey = maxkeys[i];
122 }
123 }
124 return node;
125 }
126
UU()127 static UU() void
128 deleted_row(UU() DB *db, UU() DBT *key, UU() DBT *val) {
129 }
130
131 static void
test_make_tree(int height,int fanout,int nperleaf,int do_verify)132 test_make_tree(int height, int fanout, int nperleaf, int do_verify) {
133 int r;
134
135 // cleanup
136 const char *fname = TOKU_TEST_FILENAME;
137 r = unlink(fname);
138 assert(r == 0 || (r == -1 && errno == ENOENT));
139
140 // create a cachetable
141 CACHETABLE ct = NULL;
142 toku_cachetable_create(&ct, 0, ZERO_LSN, nullptr);
143
144 // create the ft
145 TOKUTXN null_txn = NULL;
146 FT_HANDLE ft = NULL;
147 r = toku_open_ft_handle(fname, 1, &ft, 1024, 256, TOKU_DEFAULT_COMPRESSION_METHOD, ct, null_txn, toku_builtin_compare_fun);
148 assert(r == 0);
149
150 // make a tree
151 int seq = 0, minkey, maxkey;
152 FTNODE newroot = make_tree(ft, height, fanout, nperleaf, &seq, &minkey, &maxkey);
153
154 // discard the old root block
155 toku_ft_set_new_root_blocknum(ft->ft, newroot->blocknum);
156
157 // unpin the new root
158 toku_unpin_ftnode(ft->ft, newroot);
159
160 if (do_verify) {
161 r = toku_verify_ft(ft);
162 assert(r != 0);
163 }
164
165 // flush to the file system
166 r = toku_close_ft_handle_nolsn(ft, 0);
167 assert(r == 0);
168
169 // shutdown the cachetable
170 toku_cachetable_close(&ct);
171 }
172
173 static int
usage(void)174 usage(void) {
175 return 1;
176 }
177
178 int
test_main(int argc,const char * argv[])179 test_main (int argc , const char *argv[]) {
180 int height = 1;
181 int fanout = 3;
182 int nperleaf = 8;
183 int do_verify = 1;
184 initialize_dummymsn();
185 for (int i = 1; i < argc; i++) {
186 const char *arg = argv[i];
187 if (strcmp(arg, "-v") == 0) {
188 verbose++;
189 continue;
190 }
191 if (strcmp(arg, "-q") == 0) {
192 verbose = 0;
193 continue;
194 }
195 if (strcmp(arg, "--height") == 0 && i+1 < argc) {
196 height = atoi(argv[++i]);
197 continue;
198 }
199 if (strcmp(arg, "--fanout") == 0 && i+1 < argc) {
200 fanout = atoi(argv[++i]);
201 continue;
202 }
203 if (strcmp(arg, "--nperleaf") == 0 && i+1 < argc) {
204 nperleaf = atoi(argv[++i]);
205 continue;
206 }
207 if (strcmp(arg, "--verify") == 0 && i+1 < argc) {
208 do_verify = atoi(argv[++i]);
209 continue;
210 }
211 return usage();
212 }
213 test_make_tree(height, fanout, nperleaf, do_verify);
214 return 0;
215 }
216