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
 127         typedef std::pair<key_type const, value_type> pair_type;
 128
 129         struct less
 130         {
 131             bool operator ()( key_type const& v1, key_type const& v2 ) const
 132             {
 133                 return v1.nKey < v2.nKey;
 134             }
 135
 136             bool operator ()( key_type const& v1, int v2 ) const
 137             {
 138                 return v1.nKey < v2;
 139             }
 140
 141             bool operator ()( int v1, key_type const& v2 ) const
 142             {
 143                 return v1 < v2.nKey;
 144             }
 145
 146             bool operator ()( key_type const& v1, std::string const& v2 ) const
 147             {
 148                 return v1.nKey < std::stoi(v2 );
 149             }
 150
 151             bool operator ()( std::string const& v1, key_type const& v2 ) const
 152             {
 153                 return std::stoi( v1 ) < v2.nKey;
 154             }
 155         };
 156
 157         struct cmp {
 158             int operator ()( key_type const& v1, key_type const& v2 ) const
 159             {
 160                 if ( v1.nKey < v2.nKey )
 161                     return -1;
 162                 return v1.nKey > v2.nKey ? 1 : 0;
 163             }
 164
 165             int operator ()( key_type const& v1, int v2 ) const
 166             {
 167                 if ( v1.nKey < v2 )
 168                     return -1;
 169                 return v1.nKey > v2 ? 1 : 0;
 170             }
 171
 172             int operator ()( int v1, key_type const& v2 ) const
 173             {
 174                 if ( v1 < v2.nKey )
 175                     return -1;
 176                 return v1 > v2.nKey ? 1 : 0;
 177             }
 178
 179             int operator ()( key_type const& v1, std::string const& v2 ) const
 180             {
 181                 int n2 = std::stoi( v2 );
 182                 if ( v1.nKey < n2 )
 183                     return -1;
 184                 return v1.nKey > n2 ? 1 : 0;
 185             }
 186
 187             int operator ()( std::string const& v1, key_type const& v2 ) const
 188             {
 189                 int n1 = std::stoi( v1 );
 190                 if ( n1 < v2.nKey )
 191                     return -1;
 192                 return n1 > v2.nKey ? 1 : 0;
 193             }
 194         };
 195
 196         struct hash1 {
 197             size_t operator()( int i ) const
 198             {
 199                 return cds::opt::v::hash<int>()( i );
 200             }
 201
 202             size_t operator()( std::string const& str ) const
 203             {
 204                 return cds::opt::v::hash<int>()( std::stoi( str ));
 205             }
 206
 207             template <typename T>
 208             size_t operator()( T const& i ) const
 209             {
 210                 return cds::opt::v::hash<int>()(i.nKey);
 211             }
 212         };
 213
 214         struct other_item {
 215             int nKey;
 216
 217             other_item( int key )
 218                 : nKey( key )
 219             {}
 220         };
 221
 222         struct other_less
 223         {
 224             bool operator ()( key_type const& v1, other_item const& v2 ) const
 225             {
 226                 return v1.nKey < v2.nKey;
 227             }
 228             bool operator ()( other_item const& v1, key_type const& v2 ) const
 229             {
 230                 return v1.nKey < v2.nKey;
 231             }
 232         };
 233
 234     protected:
 235         template <class Map>
 236         void test( Map& m )
 237         {
 238             // Precondition: map is empty
 239             // Postcondition: map is empty
 240
 241             ASSERT_TRUE( m.empty());
 242             ASSERT_CONTAINER_SIZE( m, 0 );
 243
 244             typedef typename Map::value_type map_pair;
 245             size_t const kkSize = kSize;
 246
 247             std::vector<key_type> arrKeys;
 248             for ( int i = 0; i < static_cast<int>(kkSize); ++i )
 249                 arrKeys.push_back( key_type( i ));
 250             shuffle( arrKeys.begin(), arrKeys.end());
 251
 252             std::vector< value_type > arrVals;
 253             for ( size_t i = 0; i < kkSize; ++i ) {
 254                 value_type val;
 255                 val.nVal = static_cast<int>( i );
 256                 val.strVal = std::to_string( i );
 257                 arrVals.push_back( val );
 258             }
 259
 260             // insert/find
 261             for ( auto const& i : arrKeys ) {
 262                 value_type const& val( arrVals.at( i.nKey ));
 263
 264                 ASSERT_FALSE( m.contains( i.nKey ));
 265                 ASSERT_FALSE( m.contains( i ));
 266                 ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less()));
 267                 ASSERT_FALSE( m.find( i, []( map_pair const& ) {
 268                     ASSERT_TRUE( false );
 269                 } ));
 270                 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
 271                     EXPECT_TRUE( false );
 272                 } ));
 273                 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
 274                     EXPECT_TRUE( false );
 275                 } ));
 276
 277                 std::pair< bool, bool > updResult;
 278
 279                 switch ( i.nKey % 16 ) {
 280                 case 0:
 281                     ASSERT_TRUE( m.insert( i ));
 282                     ASSERT_FALSE( m.insert( i ));
 283                     ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
 284                         v.second.nVal = v.first.nKey;
 285                         v.second.strVal = std::to_string( v.first.nKey );
 286                     } ));
 287                     break;
 288                 case 1:
 289                     ASSERT_TRUE( m.insert( i.nKey ));
 290                     ASSERT_FALSE( m.insert( i.nKey ));
 291                     ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
 292                         v.second.nVal = v.first.nKey;
 293                         v.second.strVal = std::to_string( v.first.nKey );
 294                     } ));
 295                     break;
 296                 case 2:
 297                     ASSERT_TRUE( m.insert( std::to_string( i.nKey )));
 298                     ASSERT_FALSE( m.insert( std::to_string( i.nKey )));
 299                     ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
 300                         v.second.nVal = v.first.nKey;
 301                         v.second.strVal = std::to_string( v.first.nKey );
 302                     } ));
 303                     break;
 304                 case 3:
 305                     ASSERT_TRUE( m.insert( i, val ));
 306                     ASSERT_FALSE( m.insert( i, val ));
 307                     break;
 308                 case 4:
 309                     ASSERT_TRUE( m.insert( i.nKey, val.strVal ));
 310                     ASSERT_FALSE( m.insert( i.nKey, val.strVal ));
 311                     break;
 312                 case 5:
 313                     ASSERT_TRUE( m.insert( val.strVal, i.nKey ));
 314                     ASSERT_FALSE( m.insert( val.strVal, i.nKey ));
 315                     break;
 316                 case 6:
 317                     ASSERT_TRUE( m.insert_with( i, []( map_pair& v ) {
 318                         v.second.nVal = v.first.nKey;
 319                         v.second.strVal = std::to_string( v.first.nKey );
 320                     } ));
 321                     ASSERT_FALSE( m.insert_with( i, []( map_pair& v ) {
 322                         EXPECT_TRUE( false );
 323                     } ));
 324                     break;
 325                 case 7:
 326                     ASSERT_TRUE( m.insert_with( i.nKey, []( map_pair& v ) {
 327                         v.second.nVal = v.first.nKey;
 328                         v.second.strVal = std::to_string( v.first.nKey );
 329                     } ));
 330                     ASSERT_FALSE( m.insert_with( i.nKey, []( map_pair& v ) {
 331                         EXPECT_TRUE( false );
 332                     } ));
 333                     break;
 334                 case 8:
 335                     ASSERT_TRUE( m.insert_with( val.strVal, []( map_pair& v ) {
 336                         v.second.nVal = v.first.nKey;
 337                         v.second.strVal = std::to_string( v.first.nKey );
 338                     } ));
 339                     ASSERT_FALSE( m.insert_with( val.strVal, []( map_pair& v ) {
 340                         EXPECT_TRUE( false );
 341                     } ));
 342                     break;
 343                 case 9:
 344                     updResult = m.update( i.nKey, []( bool, map_pair& ) {
 345                         EXPECT_TRUE( false );
 346                     }, false );
 347                     ASSERT_FALSE( updResult.first );
 348                     ASSERT_FALSE( updResult.second );
 349
 350                     updResult = m.update( i.nKey, []( bool bNew, map_pair& v ) {
 351                         EXPECT_TRUE( bNew );
 352                         v.second.nVal = v.first.nKey;
 353                     });
 354                     ASSERT_TRUE( updResult.first );
 355                     ASSERT_TRUE( updResult.second );
 356
 357                     updResult = m.update( i.nKey, []( bool bNew, map_pair& v ) {
 358                         EXPECT_FALSE( bNew );
 359                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 360                         v.second.strVal = std::to_string( v.second.nVal );
 361                     } );
 362                     ASSERT_TRUE( updResult.first );
 363                     ASSERT_FALSE( updResult.second );
 364                     break;
 365                 case 10:
 366                     updResult = m.update( i, []( bool, map_pair& ) {
 367                         EXPECT_TRUE( false );
 368                     }, false );
 369                     ASSERT_FALSE( updResult.first );
 370                     ASSERT_FALSE( updResult.second );
 371
 372                     updResult = m.update( i, []( bool bNew, map_pair& v ) {
 373                         EXPECT_TRUE( bNew );
 374                         v.second.nVal = v.first.nKey;
 375                     });
 376                     ASSERT_TRUE( updResult.first );
 377                     ASSERT_TRUE( updResult.second );
 378
 379                     updResult = m.update( i, []( bool bNew, map_pair& v ) {
 380                         EXPECT_FALSE( bNew );
 381                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 382                         v.second.strVal = std::to_string( v.second.nVal );
 383                     } );
 384                     ASSERT_TRUE( updResult.first );
 385                     ASSERT_FALSE( updResult.second );
 386                     break;
 387                 case 11:
 388                     updResult = m.update( val.strVal, []( bool, map_pair& ) {
 389                         EXPECT_TRUE( false );
 390                     }, false );
 391                     ASSERT_FALSE( updResult.first );
 392                     ASSERT_FALSE( updResult.second );
 393
 394                     updResult = m.update( val.strVal, []( bool bNew, map_pair& v ) {
 395                         EXPECT_TRUE( bNew );
 396                         v.second.nVal = v.first.nKey;
 397                     });
 398                     ASSERT_TRUE( updResult.first );
 399                     ASSERT_TRUE( updResult.second );
 400
 401                     updResult = m.update( val.strVal, []( bool bNew, map_pair& v ) {
 402                         EXPECT_FALSE( bNew );
 403                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 404                         v.second.strVal = std::to_string( v.second.nVal );
 405                     } );
 406                     ASSERT_TRUE( updResult.first );
 407                     ASSERT_FALSE( updResult.second );
 408                     break;
 409                 case 12:
 410                     ASSERT_TRUE( m.emplace( i.nKey ));
 411                     ASSERT_FALSE( m.emplace( i.nKey ));
 412                     ASSERT_TRUE( m.find( i.nKey, []( map_pair& v ) {
 413                         v.second.nVal = v.first.nKey;
 414                         v.second.strVal = std::to_string( v.first.nKey );
 415                     } ));
 416                     break;
 417                 case 13:
 418                     ASSERT_TRUE( m.emplace( i, i.nKey ));
 419                     ASSERT_FALSE( m.emplace( i, i.nKey ));
 420                     break;
 421                 case 14:
 422                     {
 423                         std::string str = val.strVal;
 424                         ASSERT_TRUE( m.emplace( i, std::move( str )));
 425                         ASSERT_TRUE( str.empty());
 426                         str = val.strVal;
 427                         ASSERT_FALSE( m.emplace( i, std::move( str )));
 428                         ASSERT_TRUE( str.empty());
 429                     }
 430                     break;
 431                 case 15:
 432                     {
 433                         std::string str = val.strVal;
 434                         ASSERT_TRUE( m.emplace( i, i.nKey, std::move( str )));
 435                         ASSERT_TRUE( str.empty());
 436                         str = val.strVal;
 437                         ASSERT_FALSE( m.emplace( i, i.nKey, std::move( str )));
 438                         ASSERT_TRUE( str.empty());
 439                     }
 440                     break;
 441                 }
 442
 443                 ASSERT_TRUE( m.contains( i.nKey ));
 444                 ASSERT_TRUE( m.contains( i ));
 445                 ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less()));
 446                 ASSERT_TRUE( m.find( i, []( 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 );
 449                 } ));
 450                 ASSERT_TRUE( m.find( i.nKey, []( 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 );
 453                 } ));
 454                 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& v ) {
 455                     EXPECT_EQ( v.first.nKey, v.second.nVal );
 456                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 457                 } ));
 458             }
 459             ASSERT_FALSE( m.empty() );
 460             ASSERT_CONTAINER_SIZE( m, kkSize );
 461             ASSERT_FALSE( m.begin() == m.end() );
 462             ASSERT_FALSE( m.cbegin() == m.cend() );
 463
 464             shuffle( arrKeys.begin(), arrKeys.end() );
 465
 466             // erase/find
 467             for ( auto const& i : arrKeys ) {
 468                 value_type const& val( arrVals.at( i.nKey ) );
 469
 470                 ASSERT_TRUE( m.contains( i.nKey ));
 471                 ASSERT_TRUE( m.contains( val.strVal ) );
 472                 ASSERT_TRUE( m.contains( i ));
 473                 ASSERT_TRUE( m.contains( other_item( i.nKey ), other_less()));
 474                 ASSERT_TRUE( m.find( i, []( 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 );
 477                 } ));
 478                 ASSERT_TRUE( m.find( i.nKey, []( 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 );
 481                 } ));
 482                 ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& v ) {
 483                     EXPECT_EQ( v.first.nKey, v.second.nVal );
 484                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 485                 } ));
 486
 487
 488                 switch ( i.nKey % 8 ) {
 489                 case 0:
 490                     ASSERT_TRUE( m.erase( i ));
 491                     ASSERT_FALSE( m.erase( i ));
 492                     break;
 493                 case 1:
 494                     ASSERT_TRUE( m.erase( i.nKey ));
 495                     ASSERT_FALSE( m.erase( i.nKey ));
 496                     break;
 497                 case 2:
 498                     ASSERT_TRUE( m.erase( val.strVal ));
 499                     ASSERT_FALSE( m.erase( val.strVal ));
 500                     break;
 501                 case 3:
 502                     ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less()));
 503                     ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less()));
 504                     break;
 505                 case 4:
 506                     ASSERT_TRUE( m.erase( i, []( map_pair& v ) {
 507                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 508                         EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 509                     }));
 510                     ASSERT_FALSE( m.erase( i, []( map_pair& ) {
 511                         EXPECT_TRUE( false );
 512                     }));
 513                     break;
 514                 case 5:
 515                     ASSERT_TRUE( m.erase( i.nKey, []( map_pair& v ) {
 516                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 517                         EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 518                     }));
 519                     ASSERT_FALSE( m.erase( i.nKey, []( map_pair& ) {
 520                         EXPECT_TRUE( false );
 521                     }));
 522                     break;
 523                 case 6:
 524                     ASSERT_TRUE( m.erase( val.strVal, []( map_pair& v ) {
 525                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 526                         EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 527                     }));
 528                     ASSERT_FALSE( m.erase( val.strVal, []( map_pair& ) {
 529                         EXPECT_TRUE( false );
 530                     }));
 531                     break;
 532                 case 7:
 533                     ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& v ) {
 534                         EXPECT_EQ( v.first.nKey, v.second.nVal );
 535                         EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
 536                     }));
 537                     ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& ) {
 538                         EXPECT_TRUE( false );
 539                     }));
 540                     break;
 541                 }
 542
 543                 ASSERT_FALSE( m.contains( i.nKey ));
 544                 ASSERT_FALSE( m.contains( i ));
 545                 ASSERT_FALSE( m.contains( val.strVal ));
 546                 ASSERT_FALSE( m.contains( other_item( i.nKey ), other_less()));
 547                 ASSERT_FALSE( m.find( i, []( map_pair const& ) {
 548                     ASSERT_TRUE( false );
 549                 } ));
 550                 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
 551                     EXPECT_TRUE( false );
 552                 } ));
 553                 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
 554                     EXPECT_TRUE( false );
 555                 } ));
 556             }
 557             ASSERT_TRUE( m.empty() );
 558             ASSERT_CONTAINER_SIZE( m, 0 );
 559
 560             ASSERT_TRUE( m.begin() == m.end());
 561             ASSERT_TRUE( m.cbegin() == m.cend());
 562
 563             // clear
 564             for ( auto const& i : arrKeys )
 565                 ASSERT_TRUE( m.insert( i ));
 566
 567             ASSERT_FALSE( m.empty() );
 568             ASSERT_CONTAINER_SIZE( m, kkSize );
 569
 570             m.clear();
 571
 572             ASSERT_TRUE( m.empty() );
 573             ASSERT_CONTAINER_SIZE( m, 0 );
 574         }
 575     };
 576
 577 } // namespace cds_test
 578
 579 #endif // #ifndef CDSUNIT_MAP_TEST_MAP_H