Branch data Line data Source code
1 : : // $Id: SimpleTest.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 : :
26 : : #include <stx/btree_multiset.h>
27 : : #include <stx/btree_multimap.h>
28 : : #include <stx/btree_map.h>
29 : :
30 : : class SimpleTest : public CPPUNIT_NS::TestFixture
31 [ + - ][ # # ]: 14 : {
32 [ + - ][ + - ]: 2 : CPPUNIT_TEST_SUITE( SimpleTest );
[ # # ]
33 : 1 : CPPUNIT_TEST(test_empty);
34 : 1 : CPPUNIT_TEST(test_set_insert_erase_320);
35 : 1 : CPPUNIT_TEST(test_set_insert_erase_320_descending);
36 : 1 : CPPUNIT_TEST(test_map_insert_erase_320);
37 : 1 : CPPUNIT_TEST(test_map_insert_erase_320_descending);
38 : 1 : CPPUNIT_TEST(test2_map_insert_erase_strings);
39 : 1 : CPPUNIT_TEST(test_set_100000_uint64);
40 : 2 : CPPUNIT_TEST_SUITE_END();
41 : :
42 : : protected:
43 : :
44 : : struct traits_nodebug
45 : : {
46 : : static const bool selfverify = true;
47 : : static const bool debug = false;
48 : :
49 : : static const int leafslots = 8;
50 : : static const int innerslots = 8;
51 : : };
52 : :
53 : 1 : void test_empty()
54 : : {
55 : : typedef stx::btree_multiset<unsigned int,
56 : : std::less<unsigned int>, struct traits_nodebug> btree_type;
57 : :
58 : 1 : btree_type bt, bt2;
59 : 1 : bt.verify();
60 : :
61 : 1 : CPPUNIT_ASSERT( bt.erase(42) == false );
62 : :
63 : 1 : CPPUNIT_ASSERT( bt == bt2 );
64 : 1 : }
65 : :
66 : 1 : void test_set_insert_erase_320()
67 : : {
68 : : typedef stx::btree_multiset<unsigned int,
69 : : std::less<unsigned int>, struct traits_nodebug> btree_type;
70 : :
71 : 1 : btree_type bt;
72 : 1 : bt.verify();
73 : :
74 : 1 : srand(34234235);
75 [ + + ]: 321 : for(unsigned int i = 0; i < 320; i++)
76 : : {
77 : 320 : CPPUNIT_ASSERT(bt.size() == i);
78 : 320 : bt.insert(rand() % 100);
79 : 320 : CPPUNIT_ASSERT(bt.size() == i + 1);
80 : : }
81 : :
82 : 1 : srand(34234235);
83 [ + + ]: 321 : for(unsigned int i = 0; i < 320; i++)
84 : : {
85 : 320 : CPPUNIT_ASSERT(bt.size() == 320 - i);
86 : 320 : CPPUNIT_ASSERT( bt.erase_one(rand() % 100) );
87 : 320 : CPPUNIT_ASSERT(bt.size() == 320 - i - 1);
88 : : }
89 : :
90 : 1 : CPPUNIT_ASSERT( bt.empty() );
91 : 1 : }
92 : :
93 : 1 : void test_set_insert_erase_320_descending()
94 : : {
95 : : typedef stx::btree_multiset<unsigned int,
96 : : std::greater<unsigned int>, struct traits_nodebug> btree_type;
97 : :
98 : 1 : btree_type bt;
99 : :
100 : 1 : srand(34234235);
101 [ + + ]: 321 : for(unsigned int i = 0; i < 320; i++)
102 : : {
103 : 320 : CPPUNIT_ASSERT(bt.size() == i);
104 : 320 : bt.insert(rand() % 100);
105 : 320 : CPPUNIT_ASSERT(bt.size() == i + 1);
106 : : }
107 : :
108 : 1 : srand(34234235);
109 [ + + ]: 321 : for(unsigned int i = 0; i < 320; i++)
110 : : {
111 : 320 : CPPUNIT_ASSERT(bt.size() == 320 - i);
112 : 320 : CPPUNIT_ASSERT( bt.erase_one(rand() % 100) );
113 : 320 : CPPUNIT_ASSERT(bt.size() == 320 - i - 1);
114 : : }
115 : :
116 : 1 : CPPUNIT_ASSERT( bt.empty() );
117 : 1 : }
118 : :
119 : 1 : void test_map_insert_erase_320()
120 : : {
121 : : typedef stx::btree_multimap<unsigned int, std::string,
122 : : std::less<unsigned int>, struct traits_nodebug> btree_type;
123 : :
124 : 1 : btree_type bt;
125 : :
126 : 1 : srand(34234235);
127 [ + + ]: 321 : for(unsigned int i = 0; i < 320; i++)
128 : : {
129 : 320 : CPPUNIT_ASSERT(bt.size() == i);
130 : 320 : bt.insert2(rand() % 100, "101");
131 : 320 : CPPUNIT_ASSERT(bt.size() == i + 1);
132 : : }
133 : :
134 : 1 : srand(34234235);
135 [ + + ]: 321 : for(unsigned int i = 0; i < 320; i++)
136 : : {
137 : 320 : CPPUNIT_ASSERT(bt.size() == 320 - i);
138 : 320 : CPPUNIT_ASSERT( bt.erase_one(rand() % 100) );
139 : 320 : CPPUNIT_ASSERT(bt.size() == 320 - i - 1);
140 : : }
141 : :
142 : 1 : CPPUNIT_ASSERT( bt.empty() );
143 : 1 : bt.verify();
144 : 1 : }
145 : :
146 : 1 : void test_map_insert_erase_320_descending()
147 : : {
148 : : typedef stx::btree_multimap<unsigned int, std::string,
149 : : std::greater<unsigned int>, struct traits_nodebug> btree_type;
150 : :
151 : 1 : btree_type bt;
152 : :
153 : 1 : srand(34234235);
154 [ + + ]: 321 : for(unsigned int i = 0; i < 320; i++)
155 : : {
156 : 320 : CPPUNIT_ASSERT(bt.size() == i);
157 : 320 : bt.insert2(rand() % 100, "101");
158 : 320 : CPPUNIT_ASSERT(bt.size() == i + 1);
159 : : }
160 : :
161 : 1 : srand(34234235);
162 [ + + ]: 321 : for(unsigned int i = 0; i < 320; i++)
163 : : {
164 : 320 : CPPUNIT_ASSERT(bt.size() == 320 - i);
165 : 320 : CPPUNIT_ASSERT( bt.erase_one(rand() % 100) );
166 : 320 : CPPUNIT_ASSERT(bt.size() == 320 - i - 1);
167 : : }
168 : :
169 : 1 : CPPUNIT_ASSERT( bt.empty() );
170 : 1 : bt.verify();
171 : 1 : }
172 : :
173 : 1 : void test2_map_insert_erase_strings()
174 : : {
175 : : typedef stx::btree_multimap<std::string, unsigned int,
176 : : std::less<std::string>, struct traits_nodebug> btree_type;
177 : :
178 : 1 : std::string letters = "abcdefghijklmnopqrstuvwxyz";
179 : :
180 : 1 : btree_type bt;
181 : :
182 [ + + ]: 27 : for(unsigned int a = 0; a < letters.size(); ++a)
183 : : {
184 [ + + ]: 702 : for(unsigned int b = 0; b < letters.size(); ++b)
185 : : {
186 : : bt.insert2(std::string(1, letters[a]) + letters[b],
187 : 676 : a * letters.size() + b);
188 : : }
189 : : }
190 : :
191 [ + + ]: 27 : for(unsigned int b = 0; b < letters.size(); ++b)
192 : : {
193 [ + + ]: 702 : for(unsigned int a = 0; a < letters.size(); ++a)
194 : : {
195 : 676 : std::string key = std::string(1, letters[a]) + letters[b];
196 : :
197 : 676 : CPPUNIT_ASSERT( bt.find(key)->second == a * letters.size() + b );
198 : 676 : CPPUNIT_ASSERT( bt.erase_one(key) );
199 : : }
200 : : }
201 : :
202 : 1 : CPPUNIT_ASSERT( bt.empty() );
203 : 1 : bt.verify();
204 : 1 : }
205 : :
206 : : typedef unsigned char uint8_t;
207 : : typedef unsigned long long uint64_t;
208 : :
209 : 1 : void test_set_100000_uint64()
210 : : {
211 : 1 : stx::btree_map<uint64_t, uint8_t> bt;
212 : :
213 [ + + ]: 99991 : for(uint64_t i = 10; i < 100000; ++i)
214 : : {
215 : 99990 : uint64_t key = i % 1000;
216 : :
217 [ + + ]: 99990 : if (bt.find(key) == bt.end())
218 : : {
219 : 1000 : bt.insert( std::make_pair(key, key % 100) );
220 : : }
221 : : }
222 : :
223 : 1 : CPPUNIT_ASSERT( bt.size() == 1000 );
224 : 1 : }
225 : : };
226 : :
227 [ + - ][ + - ]: 3 : CPPUNIT_TEST_SUITE_REGISTRATION( SimpleTest );
|