Line data Source code
1 : /*
2 : * STX B+ Tree Test Suite v0.9
3 : * Copyright (C) 2008-2013 Timo Bingmann
4 : *
5 : * This program is free software: you can redistribute it and/or modify it
6 : * under the terms of the GNU General Public License as published by the Free
7 : * Software Foundation, either version 3 of the License, or (at your option)
8 : * any later version.
9 : *
10 : * This program is distributed in the hope that it will be useful, but WITHOUT
11 : * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 : * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
13 : * more details.
14 : *
15 : * You should have received a copy of the GNU General Public License along with
16 : * this program. If not, see <http://www.gnu.org/licenses/>.
17 : */
18 :
19 : #include "tpunit.h"
20 :
21 : #include <stdlib.h>
22 : #include <inttypes.h>
23 :
24 : #include <stx/btree_multiset.h>
25 : #include <stx/btree_multimap.h>
26 : #include <stx/btree_map.h>
27 :
28 : template <int Slots>
29 : struct SimpleTest : public tpunit::TestFixture
30 : {
31 22 : SimpleTest() : tpunit::TestFixture(
32 : TEST(SimpleTest::test_empty),
33 : TEST(SimpleTest::test_set_insert_erase_3200),
34 : TEST(SimpleTest::test_set_insert_erase_3200_descending),
35 : TEST(SimpleTest::test_map_insert_erase_3200),
36 : TEST(SimpleTest::test_map_insert_erase_3200_descending),
37 : TEST(SimpleTest::test2_map_insert_erase_strings),
38 : TEST(SimpleTest::test_set_100000_uint64),
39 : TEST(SimpleTest::test_multiset_100000_uint32)
40 22 : )
41 22 : {}
42 :
43 : template <typename KeyType>
44 : struct traits_nodebug : stx::btree_default_set_traits<KeyType>
45 : {
46 : static const bool selfverify = true;
47 : static const bool debug = false;
48 :
49 : static const int leafslots = Slots;
50 : static const int innerslots = Slots;
51 : };
52 :
53 22 : void test_empty()
54 : {
55 : typedef stx::btree_multiset<unsigned int,
56 : std::less<unsigned int>, traits_nodebug<unsigned int> > btree_type;
57 :
58 22 : btree_type bt, bt2;
59 22 : bt.verify();
60 :
61 22 : ASSERT( bt.erase(42) == false );
62 :
63 22 : ASSERT( bt == bt2 );
64 : }
65 :
66 22 : void test_set_insert_erase_3200()
67 : {
68 : typedef stx::btree_multiset<unsigned int,
69 : std::less<unsigned int>, traits_nodebug<unsigned int> > btree_type;
70 :
71 22 : btree_type bt;
72 22 : bt.verify();
73 :
74 22 : srand(34234235);
75 70422 : for(unsigned int i = 0; i < 3200; i++)
76 : {
77 70400 : ASSERT(bt.size() == i);
78 70400 : bt.insert(rand() % 100);
79 70400 : ASSERT(bt.size() == i + 1);
80 : }
81 :
82 22 : srand(34234235);
83 70422 : for(unsigned int i = 0; i < 3200; i++)
84 : {
85 70400 : ASSERT(bt.size() == 3200 - i);
86 70400 : ASSERT( bt.erase_one(rand() % 100) );
87 70400 : ASSERT(bt.size() == 3200 - i - 1);
88 : }
89 :
90 22 : ASSERT( bt.empty() );
91 : }
92 :
93 22 : void test_set_insert_erase_3200_descending()
94 : {
95 : typedef stx::btree_multiset<unsigned int,
96 : std::greater<unsigned int>, traits_nodebug<unsigned int> > btree_type;
97 :
98 22 : btree_type bt;
99 :
100 22 : srand(34234235);
101 70422 : for(unsigned int i = 0; i < 3200; i++)
102 : {
103 70400 : ASSERT(bt.size() == i);
104 70400 : bt.insert(rand() % 100);
105 70400 : ASSERT(bt.size() == i + 1);
106 : }
107 :
108 22 : srand(34234235);
109 70422 : for(unsigned int i = 0; i < 3200; i++)
110 : {
111 70400 : ASSERT(bt.size() == 3200 - i);
112 70400 : ASSERT( bt.erase_one(rand() % 100) );
113 70400 : ASSERT(bt.size() == 3200 - i - 1);
114 : }
115 :
116 22 : ASSERT( bt.empty() );
117 : }
118 :
119 22 : void test_map_insert_erase_3200()
120 : {
121 : typedef stx::btree_multimap<unsigned int, std::string,
122 : std::less<unsigned int>, traits_nodebug<unsigned int> > btree_type;
123 :
124 22 : btree_type bt;
125 :
126 22 : srand(34234235);
127 70422 : for(unsigned int i = 0; i < 3200; i++)
128 : {
129 70400 : ASSERT(bt.size() == i);
130 70400 : bt.insert2(rand() % 100, "101");
131 70400 : ASSERT(bt.size() == i + 1);
132 : }
133 :
134 22 : srand(34234235);
135 70422 : for(unsigned int i = 0; i < 3200; i++)
136 : {
137 70400 : ASSERT(bt.size() == 3200 - i);
138 70400 : ASSERT( bt.erase_one(rand() % 100) );
139 70400 : ASSERT(bt.size() == 3200 - i - 1);
140 : }
141 :
142 22 : ASSERT( bt.empty() );
143 22 : bt.verify();
144 : }
145 :
146 22 : void test_map_insert_erase_3200_descending()
147 : {
148 : typedef stx::btree_multimap<unsigned int, std::string,
149 : std::greater<unsigned int>, traits_nodebug<unsigned int> > btree_type;
150 :
151 22 : btree_type bt;
152 :
153 22 : srand(34234235);
154 70422 : for(unsigned int i = 0; i < 3200; i++)
155 : {
156 70400 : ASSERT(bt.size() == i);
157 70400 : bt.insert2(rand() % 100, "101");
158 70400 : ASSERT(bt.size() == i + 1);
159 : }
160 :
161 22 : srand(34234235);
162 70422 : for(unsigned int i = 0; i < 3200; i++)
163 : {
164 70400 : ASSERT(bt.size() == 3200 - i);
165 70400 : ASSERT( bt.erase_one(rand() % 100) );
166 70400 : ASSERT(bt.size() == 3200 - i - 1);
167 : }
168 :
169 22 : ASSERT( bt.empty() );
170 22 : bt.verify();
171 : }
172 :
173 22 : void test2_map_insert_erase_strings()
174 : {
175 : typedef stx::btree_multimap<std::string, unsigned int,
176 : std::less<std::string>, traits_nodebug<std::string> > btree_type;
177 :
178 22 : std::string letters = "abcdefghijklmnopqrstuvwxyz";
179 :
180 22 : btree_type bt;
181 :
182 594 : for(unsigned int a = 0; a < letters.size(); ++a)
183 : {
184 15444 : for(unsigned int b = 0; b < letters.size(); ++b)
185 : {
186 14872 : bt.insert2(std::string(1, letters[a]) + letters[b],
187 : a * letters.size() + b);
188 : }
189 : }
190 :
191 594 : for(unsigned int b = 0; b < letters.size(); ++b)
192 : {
193 15444 : for(unsigned int a = 0; a < letters.size(); ++a)
194 : {
195 14872 : std::string key = std::string(1, letters[a]) + letters[b];
196 :
197 14872 : ASSERT( bt.find(key)->second == a * letters.size() + b );
198 14872 : ASSERT( bt.erase_one(key) );
199 : }
200 : }
201 :
202 22 : ASSERT( bt.empty() );
203 22 : bt.verify();
204 : }
205 :
206 22 : void test_set_100000_uint64()
207 : {
208 22 : stx::btree_map<uint64_t, uint8_t> bt;
209 :
210 2199802 : for(uint64_t i = 10; i < 100000; ++i)
211 : {
212 2199780 : uint64_t key = i % 1000;
213 :
214 2199780 : if (bt.find(key) == bt.end())
215 : {
216 22000 : bt.insert( std::make_pair(key, key % 100) );
217 : }
218 : }
219 :
220 22 : ASSERT( bt.size() == 1000 );
221 : }
222 :
223 22 : void test_multiset_100000_uint32()
224 : {
225 22 : stx::btree_multiset<uint32_t> bt;
226 :
227 2200022 : for(uint64_t i = 0; i < 100000; ++i)
228 : {
229 2200000 : uint64_t key = i % 1000;
230 :
231 2200000 : bt.insert(key);
232 : }
233 :
234 22 : ASSERT( bt.size() == 100000 );
235 : }
236 : };
237 :
238 : // test binary search on different slot sizes
239 1 : struct SimpleTest<8> __SimpleTest8;
240 1 : struct SimpleTest<9> __SimpleTest9;
241 1 : struct SimpleTest<10> __SimpleTest10;
242 1 : struct SimpleTest<11> __SimpleTest11;
243 1 : struct SimpleTest<12> __SimpleTest12;
244 1 : struct SimpleTest<13> __SimpleTest13;
245 1 : struct SimpleTest<14> __SimpleTest14;
246 1 : struct SimpleTest<15> __SimpleTest15;
247 1 : struct SimpleTest<16> __SimpleTest16;
248 1 : struct SimpleTest<17> __SimpleTest17;
249 1 : struct SimpleTest<19> __SimpleTest19;
250 1 : struct SimpleTest<20> __SimpleTest20;
251 1 : struct SimpleTest<21> __SimpleTest21;
252 1 : struct SimpleTest<23> __SimpleTest23;
253 1 : struct SimpleTest<24> __SimpleTest24;
254 1 : struct SimpleTest<32> __SimpleTest32;
255 1 : struct SimpleTest<48> __SimpleTest48;
256 1 : struct SimpleTest<63> __SimpleTest63;
257 1 : struct SimpleTest<64> __SimpleTest64;
258 1 : struct SimpleTest<65> __SimpleTest65;
259 1 : struct SimpleTest<101> __SimpleTest101;
260 3 : struct SimpleTest<203> __SimpleTest203;
261 :
|
