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 "concurrent_tree_unit_test.h"
40
41 namespace toku {
42
test_lkr_acquire_release(void)43 void concurrent_tree_unit_test::test_lkr_acquire_release(void) {
44 comparator cmp;
45 cmp.create(compare_dbts, nullptr);
46
47 // we'll test a tree that has values 0..20
48 const uint64_t min = 0;
49 const uint64_t max = 20;
50
51 // acquire/release should work regardless of how the
52 // data was inserted into the tree, so we test it
53 // on a tree whose elements were populated starting
54 // at each value 0..20 (so we get different rotation
55 // behavior for each starting value in the tree).
56 for (uint64_t start = min; start <= max; start++) {
57 concurrent_tree tree;
58 tree.create(&cmp);
59 populate_tree(&tree, start, min, max);
60 invariant(!tree.is_empty());
61
62 for (uint64_t i = 0; i <= max; i++) {
63 concurrent_tree::locked_keyrange lkr;
64 lkr.prepare(&tree);
65 invariant(lkr.m_tree == &tree);
66 invariant(lkr.m_subtree->is_root());
67
68 keyrange range;
69 range.create(get_dbt(i), get_dbt(i));
70 lkr.acquire(range);
71 // the tree is not empty so the subtree root should not be empty
72 invariant(!lkr.m_subtree->is_empty());
73
74 // if the subtree root does not overlap then one of its children
75 // must exist and have an overlapping range.
76 if (!lkr.m_subtree->m_range.overlaps(cmp, range)) {
77 treenode *left = lkr.m_subtree->m_left_child.ptr;
78 treenode *right = lkr.m_subtree->m_right_child.ptr;
79 if (left != nullptr) {
80 // left exists, so if it does not overlap then the right must
81 if (!left->m_range.overlaps(cmp, range)) {
82 invariant_notnull(right);
83 invariant(right->m_range.overlaps(cmp, range));
84 }
85 } else {
86 // no left child, so the right must exist and be overlapping
87 invariant_notnull(right);
88 invariant(right->m_range.overlaps(cmp, range));
89 }
90 }
91
92 lkr.release();
93 }
94
95 // remove everything one by one and then destroy
96 keyrange range;
97 concurrent_tree::locked_keyrange lkr;
98 lkr.prepare(&tree);
99 invariant(lkr.m_subtree->is_root());
100 range.create(get_dbt(min), get_dbt(max));
101 lkr.acquire(range);
102 invariant(lkr.m_subtree->is_root());
103 for (uint64_t i = 0; i <= max; i++) {
104 range.create(get_dbt(i), get_dbt(i));
105 lkr.remove(range);
106 }
107 lkr.release();
108 tree.destroy();
109 }
110
111 cmp.destroy();
112 }
113
114 } /* namespace toku */
115
main(void)116 int main(void) {
117 toku::concurrent_tree_unit_test test;
118 test.test_lkr_acquire_release();
119 return 0;
120 }
121