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 :
23 : #include <stx/btree_multimap.h>
24 : #include <set>
25 :
26 : struct BoundTest : public tpunit::TestFixture
27 : {
28 1 : BoundTest() : tpunit::TestFixture(
29 : TEST(BoundTest::test_3200_10),
30 : TEST(BoundTest::test_320_1000)
31 1 : )
32 1 : {}
33 :
34 : template <typename KeyType>
35 : struct traits_nodebug : stx::btree_default_set_traits<KeyType>
36 : {
37 : static const bool selfverify = true;
38 : static const bool debug = false;
39 :
40 : static const int leafslots = 8;
41 : static const int innerslots = 8;
42 : };
43 :
44 2 : void test_multi(const unsigned int insnum, const int modulo)
45 : {
46 : typedef stx::btree_multimap<unsigned int, unsigned int,
47 : std::less<unsigned int>, traits_nodebug<unsigned int> > btree_type;
48 2 : btree_type bt;
49 :
50 : typedef std::multiset<unsigned int> multiset_type;
51 2 : multiset_type set;
52 :
53 : // *** insert
54 2 : srand(34234235);
55 3522 : for(unsigned int i = 0; i < insnum; i++)
56 : {
57 3520 : unsigned int k = rand() % modulo;
58 3520 : unsigned int v = 234;
59 :
60 3520 : ASSERT( bt.size() == set.size() );
61 3520 : bt.insert2(k, v);
62 3520 : set.insert(k);
63 3520 : ASSERT( bt.count(k) == set.count(k) );
64 :
65 3520 : ASSERT( bt.size() == set.size() );
66 : }
67 :
68 2 : ASSERT( bt.size() == insnum );
69 :
70 : // *** iterate
71 : {
72 2 : btree_type::iterator bi = bt.begin();
73 2 : multiset_type::const_iterator si = set.begin();
74 3522 : for(; bi != bt.end() && si != set.end(); ++bi, ++si)
75 : {
76 3520 : ASSERT( *si == bi.key() );
77 : }
78 2 : ASSERT( bi == bt.end() );
79 2 : ASSERT( si == set.end() );
80 : }
81 :
82 : // *** existance
83 2 : srand(34234235);
84 3522 : for(unsigned int i = 0; i < insnum; i++)
85 : {
86 3520 : unsigned int k = rand() % modulo;
87 :
88 3520 : ASSERT( bt.exists(k) );
89 : }
90 :
91 : // *** counting
92 2 : srand(34234235);
93 3522 : for(unsigned int i = 0; i < insnum; i++)
94 : {
95 3520 : unsigned int k = rand() % modulo;
96 :
97 3520 : ASSERT( bt.count(k) == set.count(k) );
98 : }
99 :
100 : // *** lower_bound
101 1212 : for(int k = 0; k < modulo + 100; k++)
102 : {
103 1210 : multiset_type::const_iterator si = set.lower_bound(k);
104 1210 : btree_type::const_iterator bi = bt.lower_bound(k);
105 :
106 1210 : if ( bi == bt.end() )
107 203 : ASSERT( si == set.end() );
108 1007 : else if ( si == set.end() )
109 0 : ASSERT( bi == bt.end() );
110 : else
111 1007 : ASSERT( *si == bi.key() );
112 : }
113 :
114 : // *** upper_bound
115 1212 : for(int k = 0; k < modulo + 100; k++)
116 : {
117 1210 : multiset_type::const_iterator si = set.upper_bound(k);
118 1210 : btree_type::const_iterator bi = bt.upper_bound(k);
119 :
120 1210 : if ( bi == bt.end() )
121 205 : ASSERT( si == set.end() );
122 1005 : else if ( si == set.end() )
123 0 : ASSERT( bi == bt.end() );
124 : else
125 1005 : ASSERT( *si == bi.key() );
126 : }
127 :
128 : // *** equal_range
129 1212 : for(int k = 0; k < modulo + 100; k++)
130 : {
131 1210 : std::pair<multiset_type::const_iterator, multiset_type::const_iterator> si = set.equal_range(k);
132 1210 : std::pair<btree_type::const_iterator, btree_type::const_iterator> bi = bt.equal_range(k);
133 :
134 1210 : if ( bi.first == bt.end() )
135 203 : ASSERT( si.first == set.end() );
136 1007 : else if ( si.first == set.end() )
137 0 : ASSERT( bi.first == bt.end() );
138 : else
139 1007 : ASSERT( *si.first == bi.first.key() );
140 :
141 1210 : if ( bi.second == bt.end() )
142 205 : ASSERT( si.second == set.end() );
143 1005 : else if ( si.second == set.end() )
144 0 : ASSERT( bi.second == bt.end() );
145 : else
146 1005 : ASSERT( *si.second == bi.second.key() );
147 : }
148 :
149 : // *** deletion
150 2 : srand(34234235);
151 3522 : for(unsigned int i = 0; i < insnum; i++)
152 : {
153 3520 : unsigned int k = rand() % modulo;
154 :
155 3520 : if (set.find(k) != set.end())
156 : {
157 3520 : ASSERT( bt.size() == set.size() );
158 :
159 3520 : ASSERT( bt.exists(k) );
160 3520 : ASSERT( bt.erase_one(k) );
161 3520 : set.erase( set.find(k) );
162 :
163 3520 : ASSERT( bt.size() == set.size() );
164 : }
165 : }
166 :
167 2 : ASSERT( bt.empty() );
168 2 : ASSERT( set.empty() );
169 : }
170 :
171 1 : void test_3200_10()
172 : {
173 1 : test_multi(3200, 10);
174 1 : }
175 :
176 1 : void test_320_1000()
177 : {
178 1 : test_multi(320, 1000);
179 1 : }
180 :
181 3 : } __BoundTest;
182 :
|
