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 <time.h>
23 :
24 : #include <stx/btree_multiset.h>
25 : #include <set>
26 :
27 : struct LargeTest : public tpunit::TestFixture
28 : {
29 1 : LargeTest() : tpunit::TestFixture(
30 : TEST(LargeTest::test_320_mod_1000),
31 : TEST(LargeTest::test_320_mod_10000),
32 : TEST(LargeTest::test_3200_mod_10),
33 : TEST(LargeTest::test_3200_mod_100),
34 : TEST(LargeTest::test_3200_mod_1000),
35 : TEST(LargeTest::test_3200_mod_10000),
36 : TEST(LargeTest::test_32000_mod_10000),
37 : TEST(LargeTest::test_sequence)
38 1 : )
39 1 : {}
40 :
41 : template <typename KeyType>
42 : struct traits_nodebug : stx::btree_default_set_traits<KeyType>
43 : {
44 : static const bool selfverify = true;
45 : static const bool debug = false;
46 :
47 : static const int leafslots = 8;
48 : static const int innerslots = 8;
49 : };
50 :
51 7 : void test_multi(const unsigned int insnum, const unsigned int modulo)
52 : {
53 : typedef stx::btree_multiset<unsigned int,
54 : std::less<unsigned int>, traits_nodebug<unsigned int> > btree_type;
55 :
56 7 : btree_type bt;
57 :
58 : typedef std::multiset<unsigned int> multiset_type;
59 7 : multiset_type set;
60 :
61 : // *** insert
62 7 : srand(34234235);
63 45447 : for(unsigned int i = 0; i < insnum; i++)
64 : {
65 45440 : unsigned int k = rand() % modulo;
66 :
67 45440 : ASSERT( bt.size() == set.size() );
68 45440 : bt.insert(k);
69 45440 : set.insert(k);
70 45440 : ASSERT( bt.count(k) == set.count(k) );
71 :
72 45440 : ASSERT( bt.size() == set.size() );
73 : }
74 :
75 7 : ASSERT( bt.size() == insnum );
76 :
77 : // *** iterate
78 7 : btree_type::iterator bi = bt.begin();
79 7 : multiset_type::const_iterator si = set.begin();
80 45447 : for(; bi != bt.end() && si != set.end(); ++bi, ++si)
81 : {
82 45440 : ASSERT( *si == bi.key() );
83 : }
84 7 : ASSERT( bi == bt.end() );
85 7 : ASSERT( si == set.end() );
86 :
87 : // *** existance
88 7 : srand(34234235);
89 45447 : for(unsigned int i = 0; i < insnum; i++)
90 : {
91 45440 : unsigned int k = rand() % modulo;
92 :
93 45440 : ASSERT( bt.exists(k) );
94 : }
95 :
96 : // *** counting
97 7 : srand(34234235);
98 45447 : for(unsigned int i = 0; i < insnum; i++)
99 : {
100 45440 : unsigned int k = rand() % modulo;
101 :
102 45440 : ASSERT( bt.count(k) == set.count(k) );
103 : }
104 :
105 : // *** deletion
106 7 : srand(34234235);
107 45447 : for(unsigned int i = 0; i < insnum; i++)
108 : {
109 45440 : unsigned int k = rand() % modulo;
110 :
111 45440 : if (set.find(k) != set.end())
112 : {
113 45440 : ASSERT( bt.size() == set.size() );
114 :
115 45440 : ASSERT( bt.exists(k) );
116 45440 : ASSERT( bt.erase_one(k) );
117 45440 : set.erase( set.find(k) );
118 :
119 45440 : ASSERT( bt.size() == set.size() );
120 45440 : ASSERT( std::equal(bt.begin(), bt.end(), set.begin()) );
121 : }
122 : }
123 :
124 7 : ASSERT( bt.empty() );
125 7 : ASSERT( set.empty() );
126 : }
127 :
128 1 : void test_320_mod_1000()
129 : {
130 1 : test_multi(320, 1000);
131 1 : }
132 :
133 1 : void test_320_mod_10000()
134 : {
135 1 : test_multi(320, 10000);
136 1 : }
137 :
138 1 : void test_3200_mod_10()
139 : {
140 1 : test_multi(3200, 10);
141 1 : }
142 :
143 1 : void test_3200_mod_100()
144 : {
145 1 : test_multi(3200, 100);
146 1 : }
147 :
148 1 : void test_3200_mod_1000()
149 : {
150 1 : test_multi(3200, 1000);
151 1 : }
152 :
153 1 : void test_3200_mod_10000()
154 : {
155 1 : test_multi(3200, 10000);
156 1 : }
157 :
158 1 : void test_32000_mod_10000()
159 : {
160 1 : test_multi(32000, 10000);
161 1 : }
162 :
163 1 : void test_sequence()
164 : {
165 : typedef stx::btree_multiset<unsigned int,
166 : std::less<unsigned int>, traits_nodebug<unsigned int> > btree_type;
167 :
168 1 : btree_type bt;
169 :
170 1 : const unsigned int insnum = 10000;
171 :
172 : typedef std::multiset<unsigned int> multiset_type;
173 1 : multiset_type set;
174 :
175 : // *** insert
176 1 : srand(34234235);
177 10001 : for(unsigned int i = 0; i < insnum; i++)
178 : {
179 10000 : unsigned int k = i;
180 :
181 10000 : ASSERT( bt.size() == set.size() );
182 10000 : bt.insert(k);
183 10000 : set.insert(k);
184 10000 : ASSERT( bt.count(k) == set.count(k) );
185 :
186 10000 : ASSERT( bt.size() == set.size() );
187 : }
188 :
189 1 : ASSERT( bt.size() == insnum );
190 :
191 : // *** iterate
192 1 : btree_type::iterator bi = bt.begin();
193 1 : multiset_type::const_iterator si = set.begin();
194 10001 : for(; bi != bt.end() && si != set.end(); ++bi, ++si)
195 : {
196 10000 : ASSERT( *si == bi.key() );
197 : }
198 1 : ASSERT( bi == bt.end() );
199 1 : ASSERT( si == set.end() );
200 :
201 : // *** existance
202 1 : srand(34234235);
203 10001 : for(unsigned int i = 0; i < insnum; i++)
204 : {
205 10000 : unsigned int k = i;
206 :
207 10000 : ASSERT( bt.exists(k) );
208 : }
209 :
210 : // *** counting
211 1 : srand(34234235);
212 10001 : for(unsigned int i = 0; i < insnum; i++)
213 : {
214 10000 : unsigned int k = i;
215 :
216 10000 : ASSERT( bt.count(k) == set.count(k) );
217 : }
218 :
219 : // *** deletion
220 1 : srand(34234235);
221 10001 : for(unsigned int i = 0; i < insnum; i++)
222 : {
223 10000 : unsigned int k = i;
224 :
225 10000 : if (set.find(k) != set.end())
226 : {
227 10000 : ASSERT( bt.size() == set.size() );
228 :
229 10000 : ASSERT( bt.exists(k) );
230 10000 : ASSERT( bt.erase_one(k) );
231 10000 : set.erase( set.find(k) );
232 :
233 10000 : ASSERT( bt.size() == set.size() );
234 10000 : ASSERT( std::equal(bt.begin(), bt.end(), set.begin()) );
235 : }
236 : }
237 :
238 1 : ASSERT( bt.empty() );
239 1 : ASSERT( set.empty() );
240 : }
241 :
242 3 : } __LargeTest;
243 :
|
