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_MAP_TEST_MAP_H
32 #define CDSUNIT_MAP_TEST_MAP_H
34 #include <cds_test/check_size.h>
35 #include <cds_test/fixture.h>
37 #include <cds/opt/hash.h>
39 // forward declaration
40 namespace cds { namespace container {} }
44 class container_map: public fixture
47 static size_t const kSize = 1000;
52 explicit key_type( int n )
56 explicit key_type( std::string const& str )
57 : nKey( std::stoi( str ))
69 explicit value_type( int n )
71 , strVal( std::to_string( n ))
74 explicit value_type( std::string const& str )
75 : nVal( std::stoi( str ))
79 explicit value_type( std::string&& str )
80 : nVal( std::stoi( str ))
81 , strVal( std::move( str ))
84 value_type( int n, std::string const& str )
89 value_type( int n, std::string&& str )
91 , strVal( std::move( str ))
94 value_type( value_type&& v )
96 , strVal( std::move( v.strVal ))
99 value_type( value_type const& v )
104 value_type& operator=( value_type const& v )
113 value_type& operator=( value_type&& v )
117 strVal = std::move( v.strVal );
123 typedef std::pair<key_type const, value_type> pair_type;
127 bool operator ()( key_type const& v1, key_type const& v2 ) const
129 return v1.nKey < v2.nKey;
132 bool operator ()( key_type const& v1, int v2 ) const
137 bool operator ()( int v1, key_type const& v2 ) const
142 bool operator ()( key_type const& v1, std::string const& v2 ) const
144 return v1.nKey < std::stoi(v2 );
147 bool operator ()( std::string const& v1, key_type const& v2 ) const
149 return std::stoi( v1 ) < v2.nKey;
154 int operator ()( key_type const& v1, key_type const& v2 ) const
156 if ( v1.nKey < v2.nKey )
158 return v1.nKey > v2.nKey ? 1 : 0;
161 int operator ()( key_type const& v1, int v2 ) const
165 return v1.nKey > v2 ? 1 : 0;
168 int operator ()( int v1, key_type const& v2 ) const
172 return v1 > v2.nKey ? 1 : 0;
175 int operator ()( key_type const& v1, std::string const& v2 ) const
177 int n2 = std::stoi( v2 );
180 return v1.nKey > n2 ? 1 : 0;
183 int operator ()( std::string const& v1, key_type const& v2 ) const
185 int n1 = std::stoi( v1 );
188 return n1 > v2.nKey ? 1 : 0;
193 size_t operator()( int i ) const
195 return cds::opt::v::hash<int>()( i );
198 size_t operator()( std::string const& str ) const
200 return cds::opt::v::hash<int>()( std::stoi( str ));
203 template <typename T>
204 size_t operator()( T const& i ) const
206 return cds::opt::v::hash<int>()(i.nKey);
213 other_item( int key )
220 bool operator ()( key_type const& v1, other_item const& v2 ) const
222 return v1.nKey < v2.nKey;
224 bool operator ()( other_item const& v1, key_type const& v2 ) const
226 return v1.nKey < v2.nKey;
234 // Precondition: map is empty
235 // Postcondition: map is empty
237 ASSERT_TRUE( m.empty());
238 ASSERT_CONTAINER_SIZE( m, 0 );
240 typedef Map::value_type map_pair;
242 std::vector<key_type> arrKeys;
243 for ( int i = 0; i < static_cast<int>(kSize); ++i )
244 arrKeys.push_back( key_type( i ));
245 shuffle( arrKeys.begin(), arrKeys.end());
247 std::vector< value_type > arrVals;
248 for ( size_t i = 0; i < kSize; ++i ) {
250 val.nVal = static_cast<int>( i );
251 val.strVal = std::to_string( i );
252 arrVals.push_back( val );
256 for ( auto const& i : arrKeys ) {
257 value_type const& val( arrVals.at( i.nKey ));
259 ASSERT_FALSE( m.contains( i.nKey ));
260 ASSERT_FALSE( m.contains( i ));
261 ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less()));
262 ASSERT_FALSE( m.find( i, []( map_pair const& ) {
263 ASSERT_TRUE( false );
265 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
266 EXPECT_TRUE( false );
268 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
269 EXPECT_TRUE( false );
272 std::pair< bool, bool > updResult;
274 switch ( i.nKey % 16 ) {
276 ASSERT_TRUE( m.insert( i ));
277 ASSERT_FALSE( m.insert( i ));
278 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
279 v.second.nVal = v.first.nKey;
280 v.second.strVal = std::to_string( v.first.nKey );
284 ASSERT_TRUE( m.insert( i.nKey ));
285 ASSERT_FALSE( m.insert( i.nKey ));
286 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
287 v.second.nVal = v.first.nKey;
288 v.second.strVal = std::to_string( v.first.nKey );
292 ASSERT_TRUE( m.insert( std::to_string( i.nKey )));
293 ASSERT_FALSE( m.insert( std::to_string( i.nKey )));
294 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
295 v.second.nVal = v.first.nKey;
296 v.second.strVal = std::to_string( v.first.nKey );
300 ASSERT_TRUE( m.insert( i, val ));
301 ASSERT_FALSE( m.insert( i, val ));
304 ASSERT_TRUE( m.insert( i.nKey, val.strVal ));
305 ASSERT_FALSE( m.insert( i.nKey, val.strVal ));
308 ASSERT_TRUE( m.insert( val.strVal, i.nKey ));
309 ASSERT_FALSE( m.insert( val.strVal, i.nKey ));
312 ASSERT_TRUE( m.insert_with( i, []( map_pair& v ) {
313 v.second.nVal = v.first.nKey;
314 v.second.strVal = std::to_string( v.first.nKey );
316 ASSERT_FALSE( m.insert_with( i, []( map_pair& v ) {
317 EXPECT_TRUE( false );
321 ASSERT_TRUE( m.insert_with( i.nKey, []( map_pair& v ) {
322 v.second.nVal = v.first.nKey;
323 v.second.strVal = std::to_string( v.first.nKey );
325 ASSERT_FALSE( m.insert_with( i.nKey, []( map_pair& v ) {
326 EXPECT_TRUE( false );
330 ASSERT_TRUE( m.insert_with( val.strVal, []( map_pair& v ) {
331 v.second.nVal = v.first.nKey;
332 v.second.strVal = std::to_string( v.first.nKey );
334 ASSERT_FALSE( m.insert_with( val.strVal, []( map_pair& v ) {
335 EXPECT_TRUE( false );
339 updResult = m.update( i.nKey, []( bool, map_pair& ) {
340 EXPECT_TRUE( false );
342 ASSERT_FALSE( updResult.first );
343 ASSERT_FALSE( updResult.second );
345 updResult = m.update( i.nKey, []( bool bNew, map_pair& v ) {
347 v.second.nVal = v.first.nKey;
349 ASSERT_TRUE( updResult.first );
350 ASSERT_TRUE( updResult.second );
352 updResult = m.update( i.nKey, []( bool bNew, map_pair& v ) {
353 EXPECT_FALSE( bNew );
354 EXPECT_EQ( v.first.nKey, v.second.nVal );
355 v.second.strVal = std::to_string( v.second.nVal );
357 ASSERT_TRUE( updResult.first );
358 ASSERT_FALSE( updResult.second );
361 updResult = m.update( i, []( bool, map_pair& ) {
362 EXPECT_TRUE( false );
364 ASSERT_FALSE( updResult.first );
365 ASSERT_FALSE( updResult.second );
367 updResult = m.update( i, []( bool bNew, map_pair& v ) {
369 v.second.nVal = v.first.nKey;
371 ASSERT_TRUE( updResult.first );
372 ASSERT_TRUE( updResult.second );
374 updResult = m.update( i, []( bool bNew, map_pair& v ) {
375 EXPECT_FALSE( bNew );
376 EXPECT_EQ( v.first.nKey, v.second.nVal );
377 v.second.strVal = std::to_string( v.second.nVal );
379 ASSERT_TRUE( updResult.first );
380 ASSERT_FALSE( updResult.second );
383 updResult = m.update( val.strVal, []( bool, map_pair& ) {
384 EXPECT_TRUE( false );
386 ASSERT_FALSE( updResult.first );
387 ASSERT_FALSE( updResult.second );
389 updResult = m.update( val.strVal, []( bool bNew, map_pair& v ) {
391 v.second.nVal = v.first.nKey;
393 ASSERT_TRUE( updResult.first );
394 ASSERT_TRUE( updResult.second );
396 updResult = m.update( val.strVal, []( bool bNew, map_pair& v ) {
397 EXPECT_FALSE( bNew );
398 EXPECT_EQ( v.first.nKey, v.second.nVal );
399 v.second.strVal = std::to_string( v.second.nVal );
401 ASSERT_TRUE( updResult.first );
402 ASSERT_FALSE( updResult.second );
405 ASSERT_TRUE( m.emplace( i.nKey ));
406 ASSERT_FALSE( m.emplace( i.nKey ));
407 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
408 v.second.nVal = v.first.nKey;
409 v.second.strVal = std::to_string( v.first.nKey );
413 ASSERT_TRUE( m.emplace( i, i.nKey ));
414 ASSERT_FALSE( m.emplace( i, i.nKey ));
418 std::string str = val.strVal;
419 ASSERT_TRUE( m.emplace( i, std::move( str )));
420 ASSERT_TRUE( str.empty());
422 ASSERT_FALSE( m.emplace( i, std::move( str )));
423 ASSERT_TRUE( str.empty());
428 std::string str = val.strVal;
429 ASSERT_TRUE( m.emplace( i, i.nKey, std::move( str )));
430 ASSERT_TRUE( str.empty());
432 ASSERT_FALSE( m.emplace( i, i.nKey, std::move( str )));
433 ASSERT_TRUE( str.empty());
438 ASSERT_TRUE( m.contains( i.nKey ));
439 ASSERT_TRUE( m.contains( i ));
440 ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less()));
441 ASSERT_TRUE( m.find( i, []( map_pair const& v ) {
442 EXPECT_EQ( v.first.nKey, v.second.nVal );
443 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
445 ASSERT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
446 EXPECT_EQ( v.first.nKey, v.second.nVal );
447 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
449 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& v ) {
450 EXPECT_EQ( v.first.nKey, v.second.nVal );
451 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
454 ASSERT_FALSE( m.empty() );
455 ASSERT_CONTAINER_SIZE( m, kSize );
456 ASSERT_FALSE( m.begin() == m.end() );
457 ASSERT_FALSE( m.cbegin() == m.cend() );
459 shuffle( arrKeys.begin(), arrKeys.end() );
462 for ( auto const& i : arrKeys ) {
463 value_type const& val( arrVals.at( i.nKey ) );
465 ASSERT_TRUE( m.contains( i.nKey ));
466 ASSERT_TRUE( m.contains( val.strVal ) );
467 ASSERT_TRUE( m.contains( i ));
468 ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less()));
469 ASSERT_TRUE( m.find( i, []( map_pair const& v ) {
470 EXPECT_EQ( v.first.nKey, v.second.nVal );
471 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
473 ASSERT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
474 EXPECT_EQ( v.first.nKey, v.second.nVal );
475 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
477 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& v ) {
478 EXPECT_EQ( v.first.nKey, v.second.nVal );
479 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
483 switch ( i.nKey % 8 ) {
485 ASSERT_TRUE( m.erase( i ));
486 ASSERT_FALSE( m.erase( i ));
489 ASSERT_TRUE( m.erase( i.nKey ));
490 ASSERT_FALSE( m.erase( i.nKey ));
493 ASSERT_TRUE( m.erase( val.strVal ));
494 ASSERT_FALSE( m.erase( val.strVal ));
497 ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less()));
498 ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less()));
501 ASSERT_TRUE( m.erase( i, []( map_pair& v ) {
502 EXPECT_EQ( v.first.nKey, v.second.nVal );
503 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
505 ASSERT_FALSE( m.erase( i, []( map_pair& ) {
506 EXPECT_TRUE( false );
510 ASSERT_TRUE( m.erase( i.nKey, []( map_pair& v ) {
511 EXPECT_EQ( v.first.nKey, v.second.nVal );
512 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
514 ASSERT_FALSE( m.erase( i.nKey, []( map_pair& ) {
515 EXPECT_TRUE( false );
519 ASSERT_TRUE( m.erase( val.strVal, []( map_pair& v ) {
520 EXPECT_EQ( v.first.nKey, v.second.nVal );
521 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
523 ASSERT_FALSE( m.erase( val.strVal, []( map_pair& ) {
524 EXPECT_TRUE( false );
528 ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& v ) {
529 EXPECT_EQ( v.first.nKey, v.second.nVal );
530 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
532 ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& ) {
533 EXPECT_TRUE( false );
538 ASSERT_FALSE( m.contains( i.nKey ));
539 ASSERT_FALSE( m.contains( i ));
540 ASSERT_FALSE( m.contains( val.strVal ));
541 ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less()));
542 ASSERT_FALSE( m.find( i, []( map_pair const& ) {
543 ASSERT_TRUE( false );
545 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
546 EXPECT_TRUE( false );
548 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
549 EXPECT_TRUE( false );
552 ASSERT_TRUE( m.empty() );
553 ASSERT_CONTAINER_SIZE( m, 0 );
555 ASSERT_TRUE( m.begin() == m.end());
556 ASSERT_TRUE( m.cbegin() == m.cend());
559 for ( auto const& i : arrKeys )
560 ASSERT_TRUE( m.insert( i ));
562 ASSERT_FALSE( m.empty() );
563 ASSERT_CONTAINER_SIZE( m, kSize );
567 ASSERT_TRUE( m.empty() );
568 ASSERT_CONTAINER_SIZE( m, 0 );
572 } // namespace cds_test
574 #endif // #ifndef CDSUNIT_MAP_TEST_MAP_H