1 : // $Id: SimpleTest.cc 113 2008-09-07 15:25:51Z tb $
2 :
3 : /*
4 : * STX B+ Tree Template Classes v0.8.3
5 : * Copyright (C) 2008 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 3 : CPPUNIT_TEST_SUITE( SimpleTest );
33 1 : CPPUNIT_TEST(test_empty);
34 2 : CPPUNIT_TEST(test_set_insert_erase_320);
35 2 : CPPUNIT_TEST(test_set_insert_erase_320_descending);
36 2 : CPPUNIT_TEST(test_map_insert_erase_320);
37 2 : CPPUNIT_TEST(test_map_insert_erase_320_descending);
38 2 : CPPUNIT_TEST(test2_map_insert_erase_strings);
39 2 : 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 2 : 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 642 : 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 642 : for(unsigned int i = 0; i < 320; i++)
84 : {
85 320 : CPPUNIT_ASSERT(bt.size() == 320 - i);
86 640 : CPPUNIT_ASSERT( bt.erase_one(rand() % 100) );
87 640 : 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 642 : 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 642 : for(unsigned int i = 0; i < 320; i++)
110 : {
111 320 : CPPUNIT_ASSERT(bt.size() == 320 - i);
112 640 : CPPUNIT_ASSERT( bt.erase_one(rand() % 100) );
113 640 : 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 642 : for(unsigned int i = 0; i < 320; i++)
128 : {
129 320 : CPPUNIT_ASSERT(bt.size() == i);
130 640 : bt.insert2(rand() % 100, "101");
131 640 : CPPUNIT_ASSERT(bt.size() == i + 1);
132 : }
133 :
134 1 : srand(34234235);
135 642 : for(unsigned int i = 0; i < 320; i++)
136 : {
137 320 : CPPUNIT_ASSERT(bt.size() == 320 - i);
138 640 : CPPUNIT_ASSERT( bt.erase_one(rand() % 100) );
139 640 : CPPUNIT_ASSERT(bt.size() == 320 - i - 1);
140 : }
141 :
142 1 : CPPUNIT_ASSERT( bt.empty() );
143 2 : 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 642 : for(unsigned int i = 0; i < 320; i++)
155 : {
156 320 : CPPUNIT_ASSERT(bt.size() == i);
157 640 : bt.insert2(rand() % 100, "101");
158 640 : CPPUNIT_ASSERT(bt.size() == i + 1);
159 : }
160 :
161 1 : srand(34234235);
162 642 : for(unsigned int i = 0; i < 320; i++)
163 : {
164 320 : CPPUNIT_ASSERT(bt.size() == 320 - i);
165 640 : CPPUNIT_ASSERT( bt.erase_one(rand() % 100) );
166 640 : CPPUNIT_ASSERT(bt.size() == 320 - i - 1);
167 : }
168 :
169 1 : CPPUNIT_ASSERT( bt.empty() );
170 2 : 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 1404 : 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 1352 : CPPUNIT_ASSERT( bt.find(key)->second == a * letters.size() + b );
198 1352 : CPPUNIT_ASSERT( bt.erase_one(key) );
199 : }
200 : }
201 :
202 1 : CPPUNIT_ASSERT( bt.empty() );
203 2 : 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 0 :
227 3 : CPPUNIT_TEST_SUITE_REGISTRATION( SimpleTest );
|
