2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSUNIT_TREE_TEST_TREE_MAP_H
32 #define CDSUNIT_TREE_TEST_TREE_MAP_H
34 #include "test_tree_map_data.h"
36 // forward declaration
37 namespace cds { namespace container {} }
41 class container_tree_map: public tree_map_fixture
44 static size_t const kSize = 1000;
50 // Precondition: map is empty
51 // Postcondition: map is empty
53 ASSERT_TRUE( m.empty());
54 ASSERT_CONTAINER_SIZE( m, 0 );
56 typedef typename Map::value_type map_pair;
57 size_t const kkSize = kSize;
59 std::vector<key_type> arrKeys;
60 for ( int i = 0; i < static_cast<int>(kkSize); ++i )
61 arrKeys.push_back( key_type( i ));
62 shuffle( arrKeys.begin(), arrKeys.end());
64 std::vector< value_type > arrVals;
65 for ( size_t i = 0; i < kkSize; ++i ) {
67 val.nVal = static_cast<int>( i );
68 val.strVal = std::to_string( i );
69 arrVals.push_back( val );
73 for ( auto const& i : arrKeys ) {
74 value_type const& val( arrVals.at( i.nKey ));
76 ASSERT_FALSE( m.contains( i.nKey ));
77 ASSERT_FALSE( m.contains( i ));
78 ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less()));
79 ASSERT_FALSE( m.find( i, []( map_pair const& ) {
82 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
85 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
89 std::pair< bool, bool > updResult;
91 switch ( i.nKey % 16 ) {
93 ASSERT_TRUE( m.insert( i ));
94 ASSERT_FALSE( m.insert( i ));
95 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
96 v.second.nVal = v.first.nKey;
97 v.second.strVal = std::to_string( v.first.nKey );
101 ASSERT_TRUE( m.insert( i.nKey ));
102 ASSERT_FALSE( m.insert( i.nKey ));
103 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
104 v.second.nVal = v.first.nKey;
105 v.second.strVal = std::to_string( v.first.nKey );
109 ASSERT_TRUE( m.insert( std::to_string( i.nKey )));
110 ASSERT_FALSE( m.insert( std::to_string( i.nKey )));
111 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
112 v.second.nVal = v.first.nKey;
113 v.second.strVal = std::to_string( v.first.nKey );
117 ASSERT_TRUE( m.insert( i, val ));
118 ASSERT_FALSE( m.insert( i, val ));
121 ASSERT_TRUE( m.insert( i.nKey, val.strVal ));
122 ASSERT_FALSE( m.insert( i.nKey, val.strVal ));
125 ASSERT_TRUE( m.insert( val.strVal, i.nKey ));
126 ASSERT_FALSE( m.insert( val.strVal, i.nKey ));
129 ASSERT_TRUE( m.insert_with( i, []( map_pair& v ) {
130 v.second.nVal = v.first.nKey;
131 v.second.strVal = std::to_string( v.first.nKey );
133 ASSERT_FALSE( m.insert_with( i, []( map_pair& v ) {
134 EXPECT_TRUE( false );
138 ASSERT_TRUE( m.insert_with( i.nKey, []( map_pair& v ) {
139 v.second.nVal = v.first.nKey;
140 v.second.strVal = std::to_string( v.first.nKey );
142 ASSERT_FALSE( m.insert_with( i.nKey, []( map_pair& v ) {
143 EXPECT_TRUE( false );
147 ASSERT_TRUE( m.insert_with( val.strVal, []( map_pair& v ) {
148 v.second.nVal = v.first.nKey;
149 v.second.strVal = std::to_string( v.first.nKey );
151 ASSERT_FALSE( m.insert_with( val.strVal, []( map_pair& v ) {
152 EXPECT_TRUE( false );
156 updResult = m.update( i.nKey, []( bool, map_pair& ) {
157 EXPECT_TRUE( false );
159 ASSERT_FALSE( updResult.first );
160 ASSERT_FALSE( updResult.second );
162 updResult = m.update( i.nKey, []( bool bNew, map_pair& v ) {
164 v.second.nVal = v.first.nKey;
166 ASSERT_TRUE( updResult.first );
167 ASSERT_TRUE( updResult.second );
169 updResult = m.update( i.nKey, []( bool bNew, map_pair& v ) {
170 EXPECT_FALSE( bNew );
171 EXPECT_EQ( v.first.nKey, v.second.nVal );
172 v.second.strVal = std::to_string( v.second.nVal );
174 ASSERT_TRUE( updResult.first );
175 ASSERT_FALSE( updResult.second );
178 updResult = m.update( i, []( bool, map_pair& ) {
179 EXPECT_TRUE( false );
181 ASSERT_FALSE( updResult.first );
182 ASSERT_FALSE( updResult.second );
184 updResult = m.update( i, []( bool bNew, map_pair& v ) {
186 v.second.nVal = v.first.nKey;
188 ASSERT_TRUE( updResult.first );
189 ASSERT_TRUE( updResult.second );
191 updResult = m.update( i, []( bool bNew, map_pair& v ) {
192 EXPECT_FALSE( bNew );
193 EXPECT_EQ( v.first.nKey, v.second.nVal );
194 v.second.strVal = std::to_string( v.second.nVal );
196 ASSERT_TRUE( updResult.first );
197 ASSERT_FALSE( updResult.second );
200 updResult = m.update( val.strVal, []( bool, map_pair& ) {
201 EXPECT_TRUE( false );
203 ASSERT_FALSE( updResult.first );
204 ASSERT_FALSE( updResult.second );
206 updResult = m.update( val.strVal, []( bool bNew, map_pair& v ) {
208 v.second.nVal = v.first.nKey;
210 ASSERT_TRUE( updResult.first );
211 ASSERT_TRUE( updResult.second );
213 updResult = m.update( val.strVal, []( bool bNew, map_pair& v ) {
214 EXPECT_FALSE( bNew );
215 EXPECT_EQ( v.first.nKey, v.second.nVal );
216 v.second.strVal = std::to_string( v.second.nVal );
218 ASSERT_TRUE( updResult.first );
219 ASSERT_FALSE( updResult.second );
222 ASSERT_TRUE( m.emplace( i.nKey ));
223 ASSERT_FALSE( m.emplace( i.nKey ));
224 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
225 v.second.nVal = v.first.nKey;
226 v.second.strVal = std::to_string( v.first.nKey );
230 ASSERT_TRUE( m.emplace( i, i.nKey ));
231 ASSERT_FALSE( m.emplace( i, i.nKey ));
235 std::string str = val.strVal;
236 ASSERT_TRUE( m.emplace( i, std::move( str )));
237 ASSERT_TRUE( str.empty());
239 ASSERT_FALSE( m.emplace( i, std::move( str )));
240 ASSERT_TRUE( str.empty());
245 std::string str = val.strVal;
246 ASSERT_TRUE( m.emplace( i, i.nKey, std::move( str )));
247 ASSERT_TRUE( str.empty());
249 ASSERT_FALSE( m.emplace( i, i.nKey, std::move( str )));
250 ASSERT_TRUE( str.empty());
255 ASSERT_TRUE( m.contains( i.nKey ));
256 ASSERT_TRUE( m.contains( i ));
257 ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less()));
258 ASSERT_TRUE( m.find( i, []( map_pair const& v ) {
259 EXPECT_EQ( v.first.nKey, v.second.nVal );
260 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
262 ASSERT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
263 EXPECT_EQ( v.first.nKey, v.second.nVal );
264 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
266 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& v ) {
267 EXPECT_EQ( v.first.nKey, v.second.nVal );
268 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
271 ASSERT_FALSE( m.empty() );
272 ASSERT_CONTAINER_SIZE( m, kkSize );
274 ASSERT_TRUE( m.check_consistency());
276 shuffle( arrKeys.begin(), arrKeys.end() );
279 for ( auto const& i : arrKeys ) {
280 value_type const& val( arrVals.at( i.nKey ) );
282 ASSERT_TRUE( m.contains( i.nKey ));
283 ASSERT_TRUE( m.contains( val.strVal ) );
284 ASSERT_TRUE( m.contains( i ));
285 ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less()));
286 ASSERT_TRUE( m.find( i, []( map_pair const& v ) {
287 EXPECT_EQ( v.first.nKey, v.second.nVal );
288 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
290 ASSERT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
291 EXPECT_EQ( v.first.nKey, v.second.nVal );
292 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
294 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& v ) {
295 EXPECT_EQ( v.first.nKey, v.second.nVal );
296 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
300 switch ( i.nKey % 8 ) {
302 ASSERT_TRUE( m.erase( i ));
303 ASSERT_FALSE( m.erase( i ));
306 ASSERT_TRUE( m.erase( i.nKey ));
307 ASSERT_FALSE( m.erase( i.nKey ));
310 ASSERT_TRUE( m.erase( val.strVal ));
311 ASSERT_FALSE( m.erase( val.strVal ));
314 ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less()));
315 ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less()));
318 ASSERT_TRUE( m.erase( i, []( map_pair& v ) {
319 EXPECT_EQ( v.first.nKey, v.second.nVal );
320 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
322 ASSERT_FALSE( m.erase( i, []( map_pair& ) {
323 EXPECT_TRUE( false );
327 ASSERT_TRUE( m.erase( i.nKey, []( map_pair& v ) {
328 EXPECT_EQ( v.first.nKey, v.second.nVal );
329 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
331 ASSERT_FALSE( m.erase( i.nKey, []( map_pair& ) {
332 EXPECT_TRUE( false );
336 ASSERT_TRUE( m.erase( val.strVal, []( map_pair& v ) {
337 EXPECT_EQ( v.first.nKey, v.second.nVal );
338 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
340 ASSERT_FALSE( m.erase( val.strVal, []( map_pair& ) {
341 EXPECT_TRUE( false );
345 ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& v ) {
346 EXPECT_EQ( v.first.nKey, v.second.nVal );
347 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
349 ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& ) {
350 EXPECT_TRUE( false );
355 ASSERT_FALSE( m.contains( i.nKey ));
356 ASSERT_FALSE( m.contains( i ));
357 ASSERT_FALSE( m.contains( val.strVal ));
358 ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less()));
359 ASSERT_FALSE( m.find( i, []( map_pair const& ) {
360 ASSERT_TRUE( false );
362 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
363 EXPECT_TRUE( false );
365 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
366 EXPECT_TRUE( false );
369 ASSERT_TRUE( m.empty() );
370 ASSERT_CONTAINER_SIZE( m, 0 );
373 for ( auto const& i : arrKeys )
374 ASSERT_TRUE( m.insert( i ));
376 ASSERT_FALSE( m.empty() );
377 ASSERT_CONTAINER_SIZE( m, kkSize );
381 ASSERT_TRUE( m.empty() );
382 ASSERT_CONTAINER_SIZE( m, 0 );
386 } // namespace cds_test
388 #endif // #ifndef CDSUNIT_TREE_TEST_TREE_MAP_H