1 : // $Id: LargeTest.cc 35 2007-04-27 11:26:33Z tb $
2 :
3 : /*
4 : * STX B+ Tree Template Classes v0.7
5 : * Copyright (C) 2007 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 8 : {
32 3 : CPPUNIT_TEST_SUITE( LargeTest );
33 1 : CPPUNIT_TEST(test_3200_10);
34 2 : CPPUNIT_TEST(test_320_1000);
35 2 : CPPUNIT_TEST(test_320_10000);
36 2 : CPPUNIT_TEST(test_sequence);
37 2 : CPPUNIT_TEST_SUITE_END();
38 :
39 : protected:
40 :
41 : struct traits_nodebug
42 : {
43 : static const bool selfverify = true;
44 : static const bool debug = false;
45 :
46 : static const int leafslots = 8;
47 : static const int innerslots = 8;
48 : };
49 :
50 3 : void test_multi(const unsigned int insnum, const unsigned int modulo)
51 : {
52 : typedef stx::btree_multiset<unsigned int,
53 : std::less<unsigned int>, struct traits_nodebug> btree_type;
54 :
55 3 : btree_type bt;
56 :
57 : typedef std::multiset<unsigned int> multiset_type;
58 3 : multiset_type set;
59 :
60 : // *** insert
61 3 : srand(34234235);
62 7686 : for(unsigned int i = 0; i < insnum; i++)
63 : {
64 3840 : unsigned int k = rand() % modulo;
65 :
66 3840 : CPPUNIT_ASSERT( bt.size() == set.size() );
67 3840 : bt.insert(k);
68 3840 : set.insert(k);
69 3840 : CPPUNIT_ASSERT( bt.count(k) == set.count(k) );
70 :
71 7680 : CPPUNIT_ASSERT( bt.size() == set.size() );
72 : }
73 :
74 3 : CPPUNIT_ASSERT( bt.size() == insnum );
75 :
76 : // *** iterate
77 3 : btree_type::iterator bi = bt.begin();
78 3 : multiset_type::const_iterator si = set.begin();
79 7686 : for(; bi != bt.end() && si != set.end(); ++bi, ++si)
80 : {
81 3840 : CPPUNIT_ASSERT( *si == bi.key() );
82 : }
83 3 : CPPUNIT_ASSERT( bi == bt.end() );
84 6 : CPPUNIT_ASSERT( si == set.end() );
85 :
86 : // *** existance
87 3 : srand(34234235);
88 7686 : for(unsigned int i = 0; i < insnum; i++)
89 : {
90 3840 : unsigned int k = rand() % modulo;
91 :
92 3840 : CPPUNIT_ASSERT( bt.exists(k) );
93 : }
94 :
95 : // *** counting
96 3 : srand(34234235);
97 7686 : for(unsigned int i = 0; i < insnum; i++)
98 : {
99 3840 : unsigned int k = rand() % modulo;
100 :
101 3840 : CPPUNIT_ASSERT( bt.count(k) == set.count(k) );
102 : }
103 :
104 : // *** deletion
105 3 : srand(34234235);
106 3843 : for(unsigned int i = 0; i < insnum; i++)
107 : {
108 3840 : unsigned int k = rand() % modulo;
109 :
110 3840 : if (set.find(k) != set.end())
111 : {
112 3840 : CPPUNIT_ASSERT( bt.size() == set.size() );
113 :
114 7680 : CPPUNIT_ASSERT( bt.exists(k) );
115 7680 : CPPUNIT_ASSERT( bt.erase_one(k) );
116 7680 : set.erase( set.find(k) );
117 :
118 3840 : CPPUNIT_ASSERT( bt.size() == set.size() );
119 : }
120 : }
121 :
122 3 : CPPUNIT_ASSERT( bt.empty() );
123 6 : CPPUNIT_ASSERT( set.empty() );
124 3 : }
125 :
126 1 : void test_3200_10()
127 : {
128 1 : test_multi(3200, 10);
129 1 : }
130 :
131 1 : void test_320_1000()
132 : {
133 1 : test_multi(320, 1000);
134 1 : }
135 :
136 1 : void test_320_10000()
137 : {
138 1 : test_multi(320, 10000);
139 1 : }
140 :
141 1 : void test_sequence()
142 : {
143 : typedef stx::btree_multiset<unsigned int,
144 : std::less<unsigned int>, struct traits_nodebug> btree_type;
145 :
146 1 : btree_type bt;
147 :
148 1 : const unsigned int insnum = 10000;
149 :
150 : typedef std::multiset<unsigned int> multiset_type;
151 1 : multiset_type set;
152 :
153 : // *** insert
154 1 : srand(34234235);
155 20002 : for(unsigned int i = 0; i < insnum; i++)
156 : {
157 10000 : unsigned int k = i;
158 :
159 10000 : CPPUNIT_ASSERT( bt.size() == set.size() );
160 10000 : bt.insert(k);
161 10000 : set.insert(k);
162 10000 : CPPUNIT_ASSERT( bt.count(k) == set.count(k) );
163 :
164 20000 : CPPUNIT_ASSERT( bt.size() == set.size() );
165 : }
166 :
167 1 : CPPUNIT_ASSERT( bt.size() == insnum );
168 :
169 : // *** iterate
170 1 : btree_type::iterator bi = bt.begin();
171 1 : multiset_type::const_iterator si = set.begin();
172 20002 : for(; bi != bt.end() && si != set.end(); ++bi, ++si)
173 : {
174 10000 : CPPUNIT_ASSERT( *si == bi.key() );
175 : }
176 1 : CPPUNIT_ASSERT( bi == bt.end() );
177 2 : CPPUNIT_ASSERT( si == set.end() );
178 :
179 : // *** existance
180 1 : srand(34234235);
181 20002 : for(unsigned int i = 0; i < insnum; i++)
182 : {
183 10000 : unsigned int k = i;
184 :
185 10000 : CPPUNIT_ASSERT( bt.exists(k) );
186 : }
187 :
188 : // *** counting
189 1 : srand(34234235);
190 20002 : for(unsigned int i = 0; i < insnum; i++)
191 : {
192 10000 : unsigned int k = i;
193 :
194 10000 : CPPUNIT_ASSERT( bt.count(k) == set.count(k) );
195 : }
196 :
197 : // *** deletion
198 1 : srand(34234235);
199 10001 : for(unsigned int i = 0; i < insnum; i++)
200 : {
201 10000 : unsigned int k = i;
202 :
203 10000 : if (set.find(k) != set.end())
204 : {
205 10000 : CPPUNIT_ASSERT( bt.size() == set.size() );
206 :
207 20000 : CPPUNIT_ASSERT( bt.exists(k) );
208 20000 : CPPUNIT_ASSERT( bt.erase_one(k) );
209 20000 : set.erase( set.find(k) );
210 :
211 10000 : CPPUNIT_ASSERT( bt.size() == set.size() );
212 : }
213 : }
214 :
215 1 : CPPUNIT_ASSERT( bt.empty() );
216 2 : CPPUNIT_ASSERT( set.empty() );
217 1 : }
218 :
219 : };
220 0 :
221 3 : CPPUNIT_TEST_SUITE_REGISTRATION( LargeTest );
|
