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 "test.h"
40
41 #include <string.h>
42
43 #include <portability/memory.h>
44
45 #include <locktree/range_buffer.h>
46
47 namespace toku {
48
49 const size_t num_points = 60;
50
get_dbt_by_iteration(size_t i)51 static const DBT *get_dbt_by_iteration(size_t i) {
52 if (i == 0) {
53 return toku_dbt_negative_infinity();
54 } else if (i < (num_points - 1)) {
55 return get_dbt(i);
56 } else {
57 return toku_dbt_positive_infinity();
58 }
59 }
60
test_points(void)61 static void test_points(void) {
62 range_buffer buffer;
63 buffer.create();
64
65 for (size_t i = 0; i < num_points; i++) {
66 const DBT *point = get_dbt_by_iteration(i);
67 buffer.append(point, point);
68 }
69
70 size_t i = 0;
71 range_buffer::iterator iter(&buffer);
72 range_buffer::iterator::record rec;
73 while (iter.current(&rec)) {
74 const DBT *expected_point = get_dbt_by_iteration(i);
75 invariant(compare_dbts(nullptr, expected_point, rec.get_left_key()) == 0);
76 invariant(compare_dbts(nullptr, expected_point, rec.get_right_key()) == 0);
77 iter.next();
78 i++;
79 }
80 invariant(i == num_points);
81
82 buffer.destroy();
83 }
84
test_ranges(void)85 static void test_ranges(void) {
86 range_buffer buffer;
87 buffer.create();
88
89 // we are going to store adjacent points as ranges,
90 // so make sure there are an even number of points.
91 invariant(num_points % 2 == 0);
92
93 for (size_t i = 0; i < num_points; i += 2) {
94 const DBT *left = get_dbt_by_iteration(i);
95 const DBT *right = get_dbt_by_iteration(i + 1);
96 buffer.append(left, right);
97 }
98
99 size_t i = 0;
100 range_buffer::iterator iter(&buffer);
101 range_buffer::iterator::record rec;
102 while (iter.current(&rec)) {
103 const DBT *expected_left = get_dbt_by_iteration(i);
104 const DBT *expected_right = get_dbt_by_iteration(i + 1);
105 invariant(compare_dbts(nullptr, expected_left, rec.get_left_key()) == 0);
106 invariant(compare_dbts(nullptr, expected_right, rec.get_right_key()) == 0);
107 iter.next();
108 i += 2;
109 }
110 invariant(i == num_points);
111
112 buffer.destroy();
113
114 }
115
test_mixed(void)116 static void test_mixed(void) {
117 range_buffer buffer;
118 buffer.create();
119 buffer.destroy();
120
121 // we are going to store adjacent points as ranges,
122 // followed by a single point, so make sure the
123 // number of points is a multiple of 3.
124 invariant(num_points % 3 == 0);
125
126 for (size_t i = 0; i < num_points; i += 3) {
127 const DBT *left = get_dbt_by_iteration(i);
128 const DBT *right = get_dbt_by_iteration(i + 1);
129 const DBT *point = get_dbt_by_iteration(i + 2);
130 buffer.append(left, right);
131 buffer.append(point, point);
132 }
133
134 size_t i = 0;
135 range_buffer::iterator iter(&buffer);
136 range_buffer::iterator::record rec;
137 while (iter.current(&rec)) {
138 const DBT *expected_left = get_dbt_by_iteration(i);
139 const DBT *expected_right = get_dbt_by_iteration(i + 1);
140 invariant(compare_dbts(nullptr, expected_left, rec.get_left_key()) == 0);
141 invariant(compare_dbts(nullptr, expected_right, rec.get_right_key()) == 0);
142 iter.next();
143
144 const DBT *expected_point = get_dbt_by_iteration(i + 2);
145 bool had_point = iter.current(&rec);
146 invariant(had_point);
147 invariant(compare_dbts(nullptr, expected_point, rec.get_left_key()) == 0);
148 invariant(compare_dbts(nullptr, expected_point, rec.get_right_key()) == 0);
149 iter.next();
150 i += 3;
151 }
152 invariant(i == num_points);
153
154 buffer.destroy();
155 }
156
test_small_and_large_points(void)157 static void test_small_and_large_points(void) {
158 range_buffer buffer;
159 buffer.create();
160 buffer.destroy();
161
162 // Test a bug where a small append would cause
163 // the range buffer to not grow properly for
164 // a subsequent large append.
165 const size_t small_size = 32;
166 const size_t large_size = 16 * 1024;
167 char *small_buf = (char *) toku_xmalloc(small_size);
168 char *large_buf = (char *) toku_xmalloc(large_size);
169 DBT small_dbt, large_dbt;
170 memset(&small_dbt, 0, sizeof(DBT));
171 memset(&large_dbt, 0, sizeof(DBT));
172 small_dbt.data = small_buf;
173 small_dbt.size = small_size;
174 large_dbt.data = large_buf;
175 large_dbt.size = large_size;
176
177 // Append a small dbt, the buf should be able to fit it.
178 buffer.append(&small_dbt, &small_dbt);
179 invariant(buffer.total_memory_size() >= small_dbt.size);
180 // Append a large dbt, the buf should be able to fit it.
181 buffer.append(&large_dbt, &large_dbt);
182 invariant(buffer.total_memory_size() >= (small_dbt.size + large_dbt.size));
183
184 toku_free(small_buf);
185 toku_free(large_buf);
186 buffer.destroy();
187 }
188
189 } /* namespace toku */
190
main(void)191 int main(void) {
192 toku::test_points();
193 toku::test_ranges();
194 toku::test_mixed();
195 toku::test_small_and_large_points();
196 return 0;
197 }
198