Branch data Line data Source code
1 : : // $Id: LargeTest.cc 128 2011-05-18 07:23:35Z tb $
2 : :
3 : : /*
4 : : * STX B+ Tree Template Classes v0.8.6
5 : : * Copyright (C) 2008-2011 Timo Bingmann
6 : : *
7 : : * This library is free software; you can redistribute it and/or modify it
8 : : * under the terms of the GNU Lesser General Public License as published by the
9 : : * Free Software Foundation; either version 2.1 of the License, or (at your
10 : : * option) any later version.
11 : : *
12 : : * This library is distributed in the hope that it will be useful, but WITHOUT
13 : : * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : : * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
15 : : * for more details.
16 : : *
17 : : * You should have received a copy of the GNU Lesser General Public License
18 : : * along with this library; if not, write to the Free Software Foundation,
19 : : * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 : : */
21 : :
22 : : #include <cppunit/extensions/HelperMacros.h>
23 : :
24 : : #include <stdlib.h>
25 : : #include <time.h>
26 : :
27 : : #include <stx/btree_multiset.h>
28 : : #include <set>
29 : :
30 : : class LargeTest : public CPPUNIT_NS::TestFixture
31 [ + - ][ # # ]: 16 : {
32 [ + - ][ + - ]: 2 : CPPUNIT_TEST_SUITE( LargeTest );
[ # # ]
33 : 1 : CPPUNIT_TEST(test_320_mod_1000);
34 : 1 : CPPUNIT_TEST(test_320_mod_10000);
35 : 1 : CPPUNIT_TEST(test_3200_mod_10);
36 : 1 : CPPUNIT_TEST(test_3200_mod_100);
37 : 1 : CPPUNIT_TEST(test_3200_mod_1000);
38 : 1 : CPPUNIT_TEST(test_3200_mod_10000);
39 : 1 : CPPUNIT_TEST(test_32000_mod_10000);
40 : 1 : CPPUNIT_TEST(test_sequence);
41 : 2 : CPPUNIT_TEST_SUITE_END();
42 : :
43 : : protected:
44 : :
45 : : struct traits_nodebug
46 : : {
47 : : static const bool selfverify = true;
48 : : static const bool debug = false;
49 : :
50 : : static const int leafslots = 8;
51 : : static const int innerslots = 8;
52 : : };
53 : :
54 : 7 : void test_multi(const unsigned int insnum, const unsigned int modulo)
55 : : {
56 : : typedef stx::btree_multiset<unsigned int,
57 : : std::less<unsigned int>, struct traits_nodebug> btree_type;
58 : :
59 : 7 : btree_type bt;
60 : :
61 : : typedef std::multiset<unsigned int> multiset_type;
62 : 7 : multiset_type set;
63 : :
64 : : // *** insert
65 : 7 : srand(34234235);
66 [ + + ]: 45447 : for(unsigned int i = 0; i < insnum; i++)
67 : : {
68 : 45440 : unsigned int k = rand() % modulo;
69 : :
70 : 45440 : CPPUNIT_ASSERT( bt.size() == set.size() );
71 : 45440 : bt.insert(k);
72 : 45440 : set.insert(k);
73 : 45440 : CPPUNIT_ASSERT( bt.count(k) == set.count(k) );
74 : :
75 : 45440 : CPPUNIT_ASSERT( bt.size() == set.size() );
76 : : }
77 : :
78 : 7 : CPPUNIT_ASSERT( bt.size() == insnum );
79 : :
80 : : // *** iterate
81 : 7 : btree_type::iterator bi = bt.begin();
82 : 7 : multiset_type::const_iterator si = set.begin();
83 [ + + ][ + - ]: 45447 : for(; bi != bt.end() && si != set.end(); ++bi, ++si)
[ + + ]
84 : : {
85 : 45440 : CPPUNIT_ASSERT( *si == bi.key() );
86 : : }
87 : 7 : CPPUNIT_ASSERT( bi == bt.end() );
88 : 7 : CPPUNIT_ASSERT( si == set.end() );
89 : :
90 : : // *** existance
91 : 7 : srand(34234235);
92 [ + + ]: 45447 : for(unsigned int i = 0; i < insnum; i++)
93 : : {
94 : 45440 : unsigned int k = rand() % modulo;
95 : :
96 : 45440 : CPPUNIT_ASSERT( bt.exists(k) );
97 : : }
98 : :
99 : : // *** counting
100 : 7 : srand(34234235);
101 [ + + ]: 45447 : for(unsigned int i = 0; i < insnum; i++)
102 : : {
103 : 45440 : unsigned int k = rand() % modulo;
104 : :
105 : 45440 : CPPUNIT_ASSERT( bt.count(k) == set.count(k) );
106 : : }
107 : :
108 : : // *** deletion
109 : 7 : srand(34234235);
110 [ + + ]: 45447 : for(unsigned int i = 0; i < insnum; i++)
111 : : {
112 : 45440 : unsigned int k = rand() % modulo;
113 : :
114 [ + - ]: 45440 : if (set.find(k) != set.end())
115 : : {
116 : 45440 : CPPUNIT_ASSERT( bt.size() == set.size() );
117 : :
118 : 45440 : CPPUNIT_ASSERT( bt.exists(k) );
119 : 45440 : CPPUNIT_ASSERT( bt.erase_one(k) );
120 : 45440 : set.erase( set.find(k) );
121 : :
122 : 45440 : CPPUNIT_ASSERT( bt.size() == set.size() );
123 : 45440 : CPPUNIT_ASSERT( std::equal(bt.begin(), bt.end(), set.begin()) );
124 : : }
125 : : }
126 : :
127 : 7 : CPPUNIT_ASSERT( bt.empty() );
128 : 7 : CPPUNIT_ASSERT( set.empty() );
129 : 7 : }
130 : :
131 : 1 : void test_320_mod_1000()
132 : : {
133 : 1 : test_multi(320, 1000);
134 : 1 : }
135 : :
136 : 1 : void test_320_mod_10000()
137 : : {
138 : 1 : test_multi(320, 10000);
139 : 1 : }
140 : :
141 : 1 : void test_3200_mod_10()
142 : : {
143 : 1 : test_multi(3200, 10);
144 : 1 : }
145 : :
146 : 1 : void test_3200_mod_100()
147 : : {
148 : 1 : test_multi(3200, 100);
149 : 1 : }
150 : :
151 : 1 : void test_3200_mod_1000()
152 : : {
153 : 1 : test_multi(3200, 1000);
154 : 1 : }
155 : :
156 : 1 : void test_3200_mod_10000()
157 : : {
158 : 1 : test_multi(3200, 10000);
159 : 1 : }
160 : :
161 : 1 : void test_32000_mod_10000()
162 : : {
163 : 1 : test_multi(32000, 10000);
164 : 1 : }
165 : :
166 : 1 : void test_sequence()
167 : : {
168 : : typedef stx::btree_multiset<unsigned int,
169 : : std::less<unsigned int>, struct traits_nodebug> btree_type;
170 : :
171 : 1 : btree_type bt;
172 : :
173 : 1 : const unsigned int insnum = 10000;
174 : :
175 : : typedef std::multiset<unsigned int> multiset_type;
176 : 1 : multiset_type set;
177 : :
178 : : // *** insert
179 : 1 : srand(34234235);
180 [ + + ]: 10001 : for(unsigned int i = 0; i < insnum; i++)
181 : : {
182 : 10000 : unsigned int k = i;
183 : :
184 : 10000 : CPPUNIT_ASSERT( bt.size() == set.size() );
185 : 10000 : bt.insert(k);
186 : 10000 : set.insert(k);
187 : 10000 : CPPUNIT_ASSERT( bt.count(k) == set.count(k) );
188 : :
189 : 10000 : CPPUNIT_ASSERT( bt.size() == set.size() );
190 : : }
191 : :
192 : 1 : CPPUNIT_ASSERT( bt.size() == insnum );
193 : :
194 : : // *** iterate
195 : 1 : btree_type::iterator bi = bt.begin();
196 : 1 : multiset_type::const_iterator si = set.begin();
197 [ + + ][ + - ]: 10001 : for(; bi != bt.end() && si != set.end(); ++bi, ++si)
[ + + ]
198 : : {
199 : 10000 : CPPUNIT_ASSERT( *si == bi.key() );
200 : : }
201 : 1 : CPPUNIT_ASSERT( bi == bt.end() );
202 : 1 : CPPUNIT_ASSERT( si == set.end() );
203 : :
204 : : // *** existance
205 : 1 : srand(34234235);
206 [ + + ]: 10001 : for(unsigned int i = 0; i < insnum; i++)
207 : : {
208 : 10000 : unsigned int k = i;
209 : :
210 : 10000 : CPPUNIT_ASSERT( bt.exists(k) );
211 : : }
212 : :
213 : : // *** counting
214 : 1 : srand(34234235);
215 [ + + ]: 10001 : for(unsigned int i = 0; i < insnum; i++)
216 : : {
217 : 10000 : unsigned int k = i;
218 : :
219 : 10000 : CPPUNIT_ASSERT( bt.count(k) == set.count(k) );
220 : : }
221 : :
222 : : // *** deletion
223 : 1 : srand(34234235);
224 [ + + ]: 10001 : for(unsigned int i = 0; i < insnum; i++)
225 : : {
226 : 10000 : unsigned int k = i;
227 : :
228 [ + - ]: 10000 : if (set.find(k) != set.end())
229 : : {
230 : 10000 : CPPUNIT_ASSERT( bt.size() == set.size() );
231 : :
232 : 10000 : CPPUNIT_ASSERT( bt.exists(k) );
233 : 10000 : CPPUNIT_ASSERT( bt.erase_one(k) );
234 : 10000 : set.erase( set.find(k) );
235 : :
236 : 10000 : CPPUNIT_ASSERT( bt.size() == set.size() );
237 : 10000 : CPPUNIT_ASSERT( std::equal(bt.begin(), bt.end(), set.begin()) );
238 : : }
239 : : }
240 : :
241 : 1 : CPPUNIT_ASSERT( bt.empty() );
242 : 1 : CPPUNIT_ASSERT( set.empty() );
243 : 1 : }
244 : :
245 : : };
246 : :
247 [ + - ][ + - ]: 3 : CPPUNIT_TEST_SUITE_REGISTRATION( LargeTest );
|