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 typename Map::value_type map_pair;
241 size_t const kkSize = kSize;
243 std::vector<key_type> arrKeys;
244 for ( int i = 0; i < static_cast<int>(kkSize); ++i )
245 arrKeys.push_back( key_type( i ));
246 shuffle( arrKeys.begin(), arrKeys.end());
248 std::vector< value_type > arrVals;
249 for ( size_t i = 0; i < kkSize; ++i ) {
251 val.nVal = static_cast<int>( i );
252 val.strVal = std::to_string( i );
253 arrVals.push_back( val );
257 for ( auto const& i : arrKeys ) {
258 value_type const& val( arrVals.at( i.nKey ));
260 ASSERT_FALSE( m.contains( i.nKey ));
261 ASSERT_FALSE( m.contains( i ));
262 ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less()));
263 ASSERT_FALSE( m.find( i, []( map_pair const& ) {
264 ASSERT_TRUE( false );
266 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
267 EXPECT_TRUE( false );
269 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
270 EXPECT_TRUE( false );
273 std::pair< bool, bool > updResult;
275 switch ( i.nKey % 16 ) {
277 ASSERT_TRUE( m.insert( i ));
278 ASSERT_FALSE( m.insert( i ));
279 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
280 v.second.nVal = v.first.nKey;
281 v.second.strVal = std::to_string( v.first.nKey );
285 ASSERT_TRUE( m.insert( i.nKey ));
286 ASSERT_FALSE( m.insert( i.nKey ));
287 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
288 v.second.nVal = v.first.nKey;
289 v.second.strVal = std::to_string( v.first.nKey );
293 ASSERT_TRUE( m.insert( std::to_string( i.nKey )));
294 ASSERT_FALSE( m.insert( std::to_string( i.nKey )));
295 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
296 v.second.nVal = v.first.nKey;
297 v.second.strVal = std::to_string( v.first.nKey );
301 ASSERT_TRUE( m.insert( i, val ));
302 ASSERT_FALSE( m.insert( i, val ));
305 ASSERT_TRUE( m.insert( i.nKey, val.strVal ));
306 ASSERT_FALSE( m.insert( i.nKey, val.strVal ));
309 ASSERT_TRUE( m.insert( val.strVal, i.nKey ));
310 ASSERT_FALSE( m.insert( val.strVal, i.nKey ));
313 ASSERT_TRUE( m.insert_with( i, []( map_pair& v ) {
314 v.second.nVal = v.first.nKey;
315 v.second.strVal = std::to_string( v.first.nKey );
317 ASSERT_FALSE( m.insert_with( i, []( map_pair& v ) {
318 EXPECT_TRUE( false );
322 ASSERT_TRUE( m.insert_with( i.nKey, []( map_pair& v ) {
323 v.second.nVal = v.first.nKey;
324 v.second.strVal = std::to_string( v.first.nKey );
326 ASSERT_FALSE( m.insert_with( i.nKey, []( map_pair& v ) {
327 EXPECT_TRUE( false );
331 ASSERT_TRUE( m.insert_with( val.strVal, []( map_pair& v ) {
332 v.second.nVal = v.first.nKey;
333 v.second.strVal = std::to_string( v.first.nKey );
335 ASSERT_FALSE( m.insert_with( val.strVal, []( map_pair& v ) {
336 EXPECT_TRUE( false );
340 updResult = m.update( i.nKey, []( bool, map_pair& ) {
341 EXPECT_TRUE( false );
343 ASSERT_FALSE( updResult.first );
344 ASSERT_FALSE( updResult.second );
346 updResult = m.update( i.nKey, []( bool bNew, map_pair& v ) {
348 v.second.nVal = v.first.nKey;
350 ASSERT_TRUE( updResult.first );
351 ASSERT_TRUE( updResult.second );
353 updResult = m.update( i.nKey, []( bool bNew, map_pair& v ) {
354 EXPECT_FALSE( bNew );
355 EXPECT_EQ( v.first.nKey, v.second.nVal );
356 v.second.strVal = std::to_string( v.second.nVal );
358 ASSERT_TRUE( updResult.first );
359 ASSERT_FALSE( updResult.second );
362 updResult = m.update( i, []( bool, map_pair& ) {
363 EXPECT_TRUE( false );
365 ASSERT_FALSE( updResult.first );
366 ASSERT_FALSE( updResult.second );
368 updResult = m.update( i, []( bool bNew, map_pair& v ) {
370 v.second.nVal = v.first.nKey;
372 ASSERT_TRUE( updResult.first );
373 ASSERT_TRUE( updResult.second );
375 updResult = m.update( i, []( bool bNew, map_pair& v ) {
376 EXPECT_FALSE( bNew );
377 EXPECT_EQ( v.first.nKey, v.second.nVal );
378 v.second.strVal = std::to_string( v.second.nVal );
380 ASSERT_TRUE( updResult.first );
381 ASSERT_FALSE( updResult.second );
384 updResult = m.update( val.strVal, []( bool, map_pair& ) {
385 EXPECT_TRUE( false );
387 ASSERT_FALSE( updResult.first );
388 ASSERT_FALSE( updResult.second );
390 updResult = m.update( val.strVal, []( bool bNew, map_pair& v ) {
392 v.second.nVal = v.first.nKey;
394 ASSERT_TRUE( updResult.first );
395 ASSERT_TRUE( updResult.second );
397 updResult = m.update( val.strVal, []( bool bNew, map_pair& v ) {
398 EXPECT_FALSE( bNew );
399 EXPECT_EQ( v.first.nKey, v.second.nVal );
400 v.second.strVal = std::to_string( v.second.nVal );
402 ASSERT_TRUE( updResult.first );
403 ASSERT_FALSE( updResult.second );
406 ASSERT_TRUE( m.emplace( i.nKey ));
407 ASSERT_FALSE( m.emplace( i.nKey ));
408 ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
409 v.second.nVal = v.first.nKey;
410 v.second.strVal = std::to_string( v.first.nKey );
414 ASSERT_TRUE( m.emplace( i, i.nKey ));
415 ASSERT_FALSE( m.emplace( i, i.nKey ));
419 std::string str = val.strVal;
420 ASSERT_TRUE( m.emplace( i, std::move( str )));
421 ASSERT_TRUE( str.empty());
423 ASSERT_FALSE( m.emplace( i, std::move( str )));
424 ASSERT_TRUE( str.empty());
429 std::string str = val.strVal;
430 ASSERT_TRUE( m.emplace( i, i.nKey, std::move( str )));
431 ASSERT_TRUE( str.empty());
433 ASSERT_FALSE( m.emplace( i, i.nKey, std::move( str )));
434 ASSERT_TRUE( str.empty());
439 ASSERT_TRUE( m.contains( i.nKey ));
440 ASSERT_TRUE( m.contains( i ));
441 ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less()));
442 ASSERT_TRUE( m.find( i, []( map_pair const& v ) {
443 EXPECT_EQ( v.first.nKey, v.second.nVal );
444 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
446 ASSERT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
447 EXPECT_EQ( v.first.nKey, v.second.nVal );
448 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
450 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& v ) {
451 EXPECT_EQ( v.first.nKey, v.second.nVal );
452 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
455 ASSERT_FALSE( m.empty() );
456 ASSERT_CONTAINER_SIZE( m, kkSize );
457 ASSERT_FALSE( m.begin() == m.end() );
458 ASSERT_FALSE( m.cbegin() == m.cend() );
460 shuffle( arrKeys.begin(), arrKeys.end() );
463 for ( auto const& i : arrKeys ) {
464 value_type const& val( arrVals.at( i.nKey ) );
466 ASSERT_TRUE( m.contains( i.nKey ));
467 ASSERT_TRUE( m.contains( val.strVal ) );
468 ASSERT_TRUE( m.contains( i ));
469 ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less()));
470 ASSERT_TRUE( m.find( i, []( map_pair const& v ) {
471 EXPECT_EQ( v.first.nKey, v.second.nVal );
472 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
474 ASSERT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
475 EXPECT_EQ( v.first.nKey, v.second.nVal );
476 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
478 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& v ) {
479 EXPECT_EQ( v.first.nKey, v.second.nVal );
480 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
484 switch ( i.nKey % 8 ) {
486 ASSERT_TRUE( m.erase( i ));
487 ASSERT_FALSE( m.erase( i ));
490 ASSERT_TRUE( m.erase( i.nKey ));
491 ASSERT_FALSE( m.erase( i.nKey ));
494 ASSERT_TRUE( m.erase( val.strVal ));
495 ASSERT_FALSE( m.erase( val.strVal ));
498 ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less()));
499 ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less()));
502 ASSERT_TRUE( m.erase( i, []( map_pair& v ) {
503 EXPECT_EQ( v.first.nKey, v.second.nVal );
504 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
506 ASSERT_FALSE( m.erase( i, []( map_pair& ) {
507 EXPECT_TRUE( false );
511 ASSERT_TRUE( m.erase( i.nKey, []( map_pair& v ) {
512 EXPECT_EQ( v.first.nKey, v.second.nVal );
513 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
515 ASSERT_FALSE( m.erase( i.nKey, []( map_pair& ) {
516 EXPECT_TRUE( false );
520 ASSERT_TRUE( m.erase( val.strVal, []( map_pair& v ) {
521 EXPECT_EQ( v.first.nKey, v.second.nVal );
522 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
524 ASSERT_FALSE( m.erase( val.strVal, []( map_pair& ) {
525 EXPECT_TRUE( false );
529 ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& v ) {
530 EXPECT_EQ( v.first.nKey, v.second.nVal );
531 EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
533 ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& ) {
534 EXPECT_TRUE( false );
539 ASSERT_FALSE( m.contains( i.nKey ));
540 ASSERT_FALSE( m.contains( i ));
541 ASSERT_FALSE( m.contains( val.strVal ));
542 ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less()));
543 ASSERT_FALSE( m.find( i, []( map_pair const& ) {
544 ASSERT_TRUE( false );
546 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
547 EXPECT_TRUE( false );
549 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
550 EXPECT_TRUE( false );
553 ASSERT_TRUE( m.empty() );
554 ASSERT_CONTAINER_SIZE( m, 0 );
556 ASSERT_TRUE( m.begin() == m.end());
557 ASSERT_TRUE( m.cbegin() == m.cend());
560 for ( auto const& i : arrKeys )
561 ASSERT_TRUE( m.insert( i ));
563 ASSERT_FALSE( m.empty() );
564 ASSERT_CONTAINER_SIZE( m, kkSize );
568 ASSERT_TRUE( m.empty() );
569 ASSERT_CONTAINER_SIZE( m, 0 );
573 } // namespace cds_test
575 #endif // #ifndef CDSUNIT_MAP_TEST_MAP_H