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