test/unit/map/test_map.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  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.
  18
  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.
  29 */
  30
  31 #ifndef CDSUNIT_MAP_TEST_MAP_H
  32 #define CDSUNIT_MAP_TEST_MAP_H
  33
  34 #include <cds_test/check_size.h>
  35 #include <cds_test/fixture.h>
  36
  37 #include <cds/opt/hash.h>
  38
  39 // forward declaration
  40 namespace cds { namespace container {} }
  41
  42 namespace cds_test {
  43
  44     class container_map: public fixture
  45     {
  46     public:
  47         static size_t const kSize = 1000;
  48
  49         struct key_type {
  50             int nKey;
  51
  52             explicit key_type( int n )
  53                 : nKey( n )
  54             {}
  55
  56             explicit key_type( std::string const& str )
  57                 : nKey( std::stoi( str ))
  58             {}
  59
  60             key_type( key_type const& s )
  61                 : nKey( s.nKey )
  62             {}
  63         };
  64
  65         struct value_type {
  66             int nVal;
  67             std::string strVal;
  68
  69             value_type()
  70                 : nVal( 0 )
  71             {}
  72
  73             explicit value_type( int n )
  74                 : nVal( n )
  75                 , strVal( std::to_string( n ))
  76             {}
  77
  78             explicit value_type( std::string const& str )
  79                 : nVal( std::stoi( str ))
  80                 , strVal( str )
  81             {}
  82
  83             explicit value_type( std::string&& str )
  84                 : nVal( std::stoi( str ))
  85                 , strVal( std::move( str ))
  86             {}
  87
  88             value_type( int n, std::string const& str )
  89                 : nVal( n )
  90                 , strVal( str )
  91             {}
  92
  93             value_type( int n, std::string&& str )
  94                 : nVal( n )
  95                 , strVal( std::move( str ))
  96             {}
  97
  98             value_type( value_type&& v )
  99                 : nVal( v.nVal )
 100                 , strVal( std::move( v.strVal ))
 101             {}
 102
 103             value_type( value_type const& v )
 104                 : nVal( v.nVal )
 105                 , strVal( v.strVal )
 106             {}
 107
 108             value_type& operator=( value_type const& v )
 109             {
 110                 if ( this != &v ) {
 111                     nVal = v.nVal;
 112                     strVal = v.strVal;
 113                 }
 114                 return *this;
 115             }
 116
 117             value_type& operator=( value_type&& v )
 118             {
 119                 if ( this != &v ) {
 120                     nVal = v.nVal;
 121                     strVal = std::move( v.strVal );
 122                 }
 123                 return *this;
 124             }
 125
 126             value_type& operator=( int i )
 127             {
 128                 nVal = i;
 129                 strVal = std::to_string( i );
 130                 return *this;
 131             }
 132
 133             value_type& operator=( std::string const& s )
 134             {
 135                 nVal = std::stoi( s );
 136                 strVal = s;
 137                 return *this;
 138             }
 139         };
 140
 141         typedef std::pair<key_type const, value_type> pair_type;
 142
 143         struct less
 144         {
 145             bool operator ()( key_type const& v1, key_type const& v2 ) const
 146             {
 147                 return v1.nKey < v2.nKey;
 148             }
 149
 150             bool operator ()( key_type const& v1, int v2 ) const
 151             {
 152                 return v1.nKey < v2;
 153             }
 154
 155             bool operator ()( int v1, key_type const& v2 ) const
 156             {
 157                 return v1 < v2.nKey;
 158             }
 159
 160             bool operator ()( key_type const& v1, std::string const& v2 ) const
 161             {
 162                 return v1.nKey < std::stoi(v2 );
 163             }
 164
 165             bool operator ()( std::string const& v1, key_type const& v2 ) const
 166             {
 167                 return std::stoi( v1 ) < v2.nKey;
 168             }
 169         };
 170
 171         struct cmp {
 172             int operator ()( key_type const& v1, key_type const& v2 ) const
 173             {
 174                 if ( v1.nKey < v2.nKey )
 175                     return -1;
 176                 return v1.nKey > v2.nKey ? 1 : 0;
 177             }
 178
 179             int operator ()( key_type const& v1, int v2 ) const
 180             {
 181                 if ( v1.nKey < v2 )
 182                     return -1;
 183                 return v1.nKey > v2 ? 1 : 0;
 184             }
 185
 186             int operator ()( int v1, key_type const& v2 ) const
 187             {
 188                 if ( v1 < v2.nKey )
 189                     return -1;
 190                 return v1 > v2.nKey ? 1 : 0;
 191             }
 192
 193             int operator ()( key_type const& v1, std::string const& v2 ) const
 194             {
 195                 int n2 = std::stoi( v2 );
 196                 if ( v1.nKey < n2 )
 197                     return -1;
 198                 return v1.nKey > n2 ? 1 : 0;
 199             }
 200
 201             int operator ()( std::string const& v1, key_type const& v2 ) const
 202             {
 203                 int n1 = std::stoi( v1 );
 204                 if ( n1 < v2.nKey )
 205                     return -1;
 206                 return n1 > v2.nKey ? 1 : 0;
 207             }
 208         };
 209
 210         struct hash1 {
 211             size_t operator()( int i ) const
 212             {
 213                 return cds::opt::v::hash<int>()( i );
 214             }
 215
 216             size_t operator()( std::string const& str ) const
 217             {
 218                 return cds::opt::v::hash<int>()( std::stoi( str ));
 219             }
 220
 221             template <typename T>
 222             size_t operator()( T const& i ) const
 223             {
 224                 return cds::opt::v::hash<int>()(i.nKey);
 225             }
 226         };
 227
 228         struct other_item {
 229             int nKey;
 230
 231             other_item( int key )
 232                 : nKey( key )
 233             {}
 234         };
 235
 236         struct other_less
 237         {
 238             bool operator ()( key_type const& v1, other_item const& v2 ) const
 239             {
 240                 return v1.nKey < v2.nKey;
 241             }
 242             bool operator ()( other_item const& v1, key_type const& v2 ) const
 243             {
 244                 return v1.nKey < v2.nKey;
 245             }
 246         };
 247
 248     protected:
 249         template <class Map>
 250         void test( Map& m )
 251         {
 252             // Precondition: map is empty
 253             // Postcondition: map is empty
 254
 255             ASSERT_TRUE( m.empty());
 256             ASSERT_CONTAINER_SIZE( m, 0 );
 257
 258             typedef typename Map::value_type map_pair;
 259             size_t const kkSize = kSize;
 260
 261             std::vector<key_type> arrKeys;
 262             for ( int i = 0; i < static_cast<int>(kkSize); ++i )
 263                 arrKeys.push_back( key_type( i ));
 264             shuffle( arrKeys.begin(), arrKeys.end());
 265
 266             std::vector< value_type > arrVals;
 267             for ( size_t i = 0; i < kkSize; ++i ) {
 268                 value_type val;
 269                 val.nVal = static_cast<int>( i );
 270                 val.strVal = std::to_string( i );
 271                 arrVals.push_back( val );
 272             }
 273
 274             // insert/find
 275             for ( auto const& i : arrKeys ) {
 276                 value_type const& val( arrVals.at( i.nKey ));
 277
 278                 ASSERT_FALSE( m.contains( i.nKey ));
 279                 ASSERT_FALSE( m.contains( i ));
 280                 ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less()));
 281                 ASSERT_FALSE( m.find( i, []( map_pair const& ) {
 282                     ASSERT_TRUE( false );
 283                 } ));
 284                 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
 285                     EXPECT_TRUE( false );
 286                 } ));
 287                 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
 288                     EXPECT_TRUE( false );
 289                 } ));
 290
 291                 std::pair< bool, bool > updResult;
 292
 293                 switch ( i.nKey % 16 ) {
 294                 case 0:
 295                     ASSERT_TRUE( m.insert( i ));
 296                     ASSERT_FALSE( m.insert( i ));
 297                     ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
 298                         v.second.nVal = v.first.nKey;
 299                         v.second.strVal = std::to_string( v.first.nKey );
 300                     } ));
 301                     break;
 302                 case 1:
 303                     ASSERT_TRUE( m.insert( i.nKey ));
 304                     ASSERT_FALSE( m.insert( i.nKey ));
 305                     ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
 306                         v.second.nVal = v.first.nKey;
 307                         v.second.strVal = std::to_string( v.first.nKey );
 308                     } ));
 309                     break;
 310                 case 2:
 311                     ASSERT_TRUE( m.insert( std::to_string( i.nKey )));
 312                     ASSERT_FALSE( m.insert( std::to_string( i.nKey )));
 313                     ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
 314                         v.second.nVal = v.first.nKey;
 315                         v.second.strVal = std::to_string( v.first.nKey );
 316                     } ));
 317                     break;
 318                 case 3:
 319                     ASSERT_TRUE( m.insert( i, val ));
 320                     ASSERT_FALSE( m.insert( i, val ));
 321                     break;
 322                 case 4:
 323                     ASSERT_TRUE( m.insert( i.nKey, val.strVal ));
 324                     ASSERT_FALSE( m.insert( i.nKey, val.strVal ));
 325                     break;
 326                 case 5:
 327                     ASSERT_TRUE( m.insert( val.strVal, i.nKey ));
 328                     ASSERT_FALSE( m.insert( val.strVal, i.nKey ));
 329                     break;
 330                 case 6:
 331                     ASSERT_TRUE( m.insert_with( i, []( map_pair& v ) {
 332                         v.second.nVal = v.first.nKey;
 333                         v.second.strVal = std::to_string( v.first.nKey );
 334                     } ));
 335                     ASSERT_FALSE( m.insert_with( i, []( map_pair& v ) {
 336                         EXPECT_TRUE( false );
 337                     } ));
 338                     break;
 339                 case 7:
 340                     ASSERT_TRUE( m.insert_with( i.nKey, []( map_pair& v ) {
 341                         v.second.nVal = v.first.nKey;
 342                         v.second.strVal = std::to_string( v.first.nKey );
 343                     } ));
 344                     ASSERT_FALSE( m.insert_with( i.nKey, []( map_pair& v ) {
 345                         EXPECT_TRUE( false );
 346                     } ));
 347                     break;
 348                 case 8:
 349                     ASSERT_TRUE( m.insert_with( val.strVal, []( map_pair& v ) {
 350                         v.second.nVal = v.first.nKey;
 351                         v.second.strVal = std::to_string( v.first.nKey );
 352                     } ));
 353                     ASSERT_FALSE( m.insert_with( val.strVal, []( map_pair& v ) {
 354                         EXPECT_TRUE( false );
 355                     } ));
 356                     break;
 357                 case 9:
 358                     updResult = m.update( i.nKey, []( bool, map_pair& ) {
 359                         EXPECT_TRUE( false );
 360                     }, false );
 361                     ASSERT_FALSE( updResult.first );
 362                     ASSERT_FALSE( updResult.second );
 363
 364                     updResult = m.update( i.nKey, []( bool bNew, map_pair& v ) {
 365                         EXPECT_TRUE( bNew );
 366                         v.second.nVal = v.first.nKey;
 367                     });
 368                     ASSERT_TRUE( updResult.first );
 369                     ASSERT_TRUE( updResult.second );
 370
 371                     updResult = m.update( i.nKey, []( bool bNew, map_pair& v ) {
 372                         EXPECT_FALSE( bNew );
 373                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 374                         v.second.strVal = std::to_string( v.second.nVal );
 375                     } );
 376                     ASSERT_TRUE( updResult.first );
 377                     ASSERT_FALSE( updResult.second );
 378                     break;
 379                 case 10:
 380                     updResult = m.update( i, []( bool, map_pair& ) {
 381                         EXPECT_TRUE( false );
 382                     }, false );
 383                     ASSERT_FALSE( updResult.first );
 384                     ASSERT_FALSE( updResult.second );
 385
 386                     updResult = m.update( i, []( bool bNew, map_pair& v ) {
 387                         EXPECT_TRUE( bNew );
 388                         v.second.nVal = v.first.nKey;
 389                     });
 390                     ASSERT_TRUE( updResult.first );
 391                     ASSERT_TRUE( updResult.second );
 392
 393                     updResult = m.update( i, []( bool bNew, map_pair& v ) {
 394                         EXPECT_FALSE( bNew );
 395                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 396                         v.second.strVal = std::to_string( v.second.nVal );
 397                     } );
 398                     ASSERT_TRUE( updResult.first );
 399                     ASSERT_FALSE( updResult.second );
 400                     break;
 401                 case 11:
 402                     updResult = m.update( val.strVal, []( bool, map_pair& ) {
 403                         EXPECT_TRUE( false );
 404                     }, false );
 405                     ASSERT_FALSE( updResult.first );
 406                     ASSERT_FALSE( updResult.second );
 407
 408                     updResult = m.update( val.strVal, []( bool bNew, map_pair& v ) {
 409                         EXPECT_TRUE( bNew );
 410                         v.second.nVal = v.first.nKey;
 411                     });
 412                     ASSERT_TRUE( updResult.first );
 413                     ASSERT_TRUE( updResult.second );
 414
 415                     updResult = m.update( val.strVal, []( bool bNew, map_pair& v ) {
 416                         EXPECT_FALSE( bNew );
 417                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 418                         v.second.strVal = std::to_string( v.second.nVal );
 419                     } );
 420                     ASSERT_TRUE( updResult.first );
 421                     ASSERT_FALSE( updResult.second );
 422                     break;
 423                 case 12:
 424                     ASSERT_TRUE( m.emplace( i.nKey ));
 425                     ASSERT_FALSE( m.emplace( i.nKey ));
 426                     ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
 427                         v.second.nVal = v.first.nKey;
 428                         v.second.strVal = std::to_string( v.first.nKey );
 429                     } ));
 430                     break;
 431                 case 13:
 432                     ASSERT_TRUE( m.emplace( i, i.nKey ));
 433                     ASSERT_FALSE( m.emplace( i, i.nKey ));
 434                     break;
 435                 case 14:
 436                     {
 437                         std::string str = val.strVal;
 438                         ASSERT_TRUE( m.emplace( i, std::move( str )));
 439                         ASSERT_TRUE( str.empty());
 440                         str = val.strVal;
 441                         ASSERT_FALSE( m.emplace( i, std::move( str )));
 442                         ASSERT_TRUE( str.empty());
 443                     }
 444                     break;
 445                 case 15:
 446                     {
 447                         std::string str = val.strVal;
 448                         ASSERT_TRUE( m.emplace( i, i.nKey, std::move( str )));
 449                         ASSERT_TRUE( str.empty());
 450                         str = val.strVal;
 451                         ASSERT_FALSE( m.emplace( i, i.nKey, std::move( str )));
 452                         ASSERT_TRUE( str.empty());
 453                     }
 454                     break;
 455                 }
 456
 457                 ASSERT_TRUE( m.contains( i.nKey ));
 458                 ASSERT_TRUE( m.contains( i ));
 459                 ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less()));
 460                 ASSERT_TRUE( m.find( i, []( map_pair const& v ) {
 461                     EXPECT_EQ( v.first.nKey, v.second.nVal );
 462                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 463                 } ));
 464                 ASSERT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
 465                     EXPECT_EQ( v.first.nKey, v.second.nVal );
 466                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 467                 } ));
 468                 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& v ) {
 469                     EXPECT_EQ( v.first.nKey, v.second.nVal );
 470                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 471                 } ));
 472             }
 473             ASSERT_FALSE( m.empty() );
 474             ASSERT_CONTAINER_SIZE( m, kkSize );
 475             ASSERT_FALSE( m.begin() == m.end() );
 476             ASSERT_FALSE( m.cbegin() == m.cend() );
 477
 478             shuffle( arrKeys.begin(), arrKeys.end() );
 479
 480             // erase/find
 481             for ( auto const& i : arrKeys ) {
 482                 value_type const& val( arrVals.at( i.nKey ) );
 483
 484                 ASSERT_TRUE( m.contains( i.nKey ));
 485                 ASSERT_TRUE( m.contains( val.strVal ) );
 486                 ASSERT_TRUE( m.contains( i ));
 487                 ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less()));
 488                 ASSERT_TRUE( m.find( i, []( map_pair const& v ) {
 489                     EXPECT_EQ( v.first.nKey, v.second.nVal );
 490                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 491                 } ));
 492                 ASSERT_TRUE( m.find( i.nKey, []( map_pair const& v ) {
 493                     EXPECT_EQ( v.first.nKey, v.second.nVal );
 494                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 495                 } ));
 496                 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& v ) {
 497                     EXPECT_EQ( v.first.nKey, v.second.nVal );
 498                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 499                 } ));
 500
 501
 502                 switch ( i.nKey % 8 ) {
 503                 case 0:
 504                     ASSERT_TRUE( m.erase( i ));
 505                     ASSERT_FALSE( m.erase( i ));
 506                     break;
 507                 case 1:
 508                     ASSERT_TRUE( m.erase( i.nKey ));
 509                     ASSERT_FALSE( m.erase( i.nKey ));
 510                     break;
 511                 case 2:
 512                     ASSERT_TRUE( m.erase( val.strVal ));
 513                     ASSERT_FALSE( m.erase( val.strVal ));
 514                     break;
 515                 case 3:
 516                     ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less()));
 517                     ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less()));
 518                     break;
 519                 case 4:
 520                     ASSERT_TRUE( m.erase( i, []( map_pair& v ) {
 521                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 522                         EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 523                     }));
 524                     ASSERT_FALSE( m.erase( i, []( map_pair& ) {
 525                         EXPECT_TRUE( false );
 526                     }));
 527                     break;
 528                 case 5:
 529                     ASSERT_TRUE( m.erase( i.nKey, []( map_pair& v ) {
 530                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 531                         EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 532                     }));
 533                     ASSERT_FALSE( m.erase( i.nKey, []( map_pair& ) {
 534                         EXPECT_TRUE( false );
 535                     }));
 536                     break;
 537                 case 6:
 538                     ASSERT_TRUE( m.erase( val.strVal, []( map_pair& v ) {
 539                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 540                         EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 541                     }));
 542                     ASSERT_FALSE( m.erase( val.strVal, []( map_pair& ) {
 543                         EXPECT_TRUE( false );
 544                     }));
 545                     break;
 546                 case 7:
 547                     ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& v ) {
 548                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 549                         EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 550                     }));
 551                     ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& ) {
 552                         EXPECT_TRUE( false );
 553                     }));
 554                     break;
 555                 }
 556
 557                 ASSERT_FALSE( m.contains( i.nKey ));
 558                 ASSERT_FALSE( m.contains( i ));
 559                 ASSERT_FALSE( m.contains( val.strVal ));
 560                 ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less()));
 561                 ASSERT_FALSE( m.find( i, []( map_pair const& ) {
 562                     ASSERT_TRUE( false );
 563                 } ));
 564                 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
 565                     EXPECT_TRUE( false );
 566                 } ));
 567                 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
 568                     EXPECT_TRUE( false );
 569                 } ));
 570             }
 571             ASSERT_TRUE( m.empty() );
 572             ASSERT_CONTAINER_SIZE( m, 0 );
 573
 574             ASSERT_TRUE( m.begin() == m.end());
 575             ASSERT_TRUE( m.cbegin() == m.cend());
 576
 577             // clear
 578             for ( auto const& i : arrKeys )
 579                 ASSERT_TRUE( m.insert( i ));
 580
 581             ASSERT_FALSE( m.empty() );
 582             ASSERT_CONTAINER_SIZE( m, kkSize );
 583
 584             m.clear();
 585
 586             ASSERT_TRUE( m.empty() );
 587             ASSERT_CONTAINER_SIZE( m, 0 );
 588         }
 589     };
 590
 591 } // namespace cds_test
 592
 593 #endif // #ifndef CDSUNIT_MAP_TEST_MAP_H