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
  61         struct value_type {
  62             int nVal;
  63             std::string strVal;
  64
  65             value_type()
  66                 : nVal( 0 )
  67             {}
  68
  69             explicit value_type( int n )
  70                 : nVal( n )
  71                 , strVal( std::to_string( n ))
  72             {}
  73
  74             explicit value_type( std::string const& str )
  75                 : nVal( std::stoi( str ))
  76                 , strVal( str )
  77             {}
  78
  79             explicit value_type( std::string&& str )
  80                 : nVal( std::stoi( str ))
  81                 , strVal( std::move( str ))
  82             {}
  83
  84             value_type( int n, std::string const& str )
  85                 : nVal( n )
  86                 , strVal( str )
  87             {}
  88
  89             value_type( int n, std::string&& str )
  90                 : nVal( n )
  91                 , strVal( std::move( str ))
  92             {}
  93
  94             value_type( value_type&& v )
  95                 : nVal( v.nVal )
  96                 , strVal( std::move( v.strVal ))
  97             {}
  98
  99             value_type( value_type const& v )
 100                 : nVal( v.nVal )
 101                 , strVal( v.strVal )
 102             {}
 103
 104             value_type& operator=( value_type const& v )
 105             {
 106                 if ( this != &v ) {
 107                     nVal = v.nVal;
 108                     strVal = v.strVal;
 109                 }
 110                 return *this;
 111             }
 112
 113             value_type& operator=( value_type&& v )
 114             {
 115                 if ( this != &v ) {
 116                     nVal = v.nVal;
 117                     strVal = std::move( v.strVal );
 118                 }
 119                 return *this;
 120             }
 121         };
 122
 123         typedef std::pair<key_type const, value_type> pair_type;
 124
 125         struct less
 126         {
 127             bool operator ()( key_type const& v1, key_type const& v2 ) const
 128             {
 129                 return v1.nKey < v2.nKey;
 130             }
 131
 132             bool operator ()( key_type const& v1, int v2 ) const
 133             {
 134                 return v1.nKey < v2;
 135             }
 136
 137             bool operator ()( int v1, key_type const& v2 ) const
 138             {
 139                 return v1 < v2.nKey;
 140             }
 141
 142             bool operator ()( key_type const& v1, std::string const& v2 ) const
 143             {
 144                 return v1.nKey < std::stoi(v2 );
 145             }
 146
 147             bool operator ()( std::string const& v1, key_type const& v2 ) const
 148             {
 149                 return std::stoi( v1 ) < v2.nKey;
 150             }
 151         };
 152
 153         struct cmp {
 154             int operator ()( key_type const& v1, key_type const& v2 ) const
 155             {
 156                 if ( v1.nKey < v2.nKey )
 157                     return -1;
 158                 return v1.nKey > v2.nKey ? 1 : 0;
 159             }
 160
 161             int operator ()( key_type const& v1, int v2 ) const
 162             {
 163                 if ( v1.nKey < v2 )
 164                     return -1;
 165                 return v1.nKey > v2 ? 1 : 0;
 166             }
 167
 168             int operator ()( int v1, key_type const& v2 ) const
 169             {
 170                 if ( v1 < v2.nKey )
 171                     return -1;
 172                 return v1 > v2.nKey ? 1 : 0;
 173             }
 174
 175             int operator ()( key_type const& v1, std::string const& v2 ) const
 176             {
 177                 int n2 = std::stoi( v2 );
 178                 if ( v1.nKey < n2 )
 179                     return -1;
 180                 return v1.nKey > n2 ? 1 : 0;
 181             }
 182
 183             int operator ()( std::string const& v1, key_type const& v2 ) const
 184             {
 185                 int n1 = std::stoi( v1 );
 186                 if ( n1 < v2.nKey )
 187                     return -1;
 188                 return n1 > v2.nKey ? 1 : 0;
 189             }
 190         };
 191
 192         struct hash1 {
 193             size_t operator()( int i ) const
 194             {
 195                 return cds::opt::v::hash<int>()( i );
 196             }
 197
 198             size_t operator()( std::string const& str ) const
 199             {
 200                 return cds::opt::v::hash<int>()( std::stoi( str ));
 201             }
 202
 203             template <typename T>
 204             size_t operator()( T const& i ) const
 205             {
 206                 return cds::opt::v::hash<int>()(i.nKey);
 207             }
 208         };
 209
 210         struct other_item {
 211             int nKey;
 212
 213             other_item( int key )
 214                 : nKey( key )
 215             {}
 216         };
 217
 218         struct other_less
 219         {
 220             bool operator ()( key_type const& v1, other_item const& v2 ) const
 221             {
 222                 return v1.nKey < v2.nKey;
 223             }
 224             bool operator ()( other_item const& v1, key_type const& v2 ) const
 225             {
 226                 return v1.nKey < v2.nKey;
 227             }
 228         };
 229
 230     protected:
 231         template <class Map>
 232         void test( Map& m )
 233         {
 234             // Precondition: map is empty
 235             // Postcondition: map is empty
 236
 237             ASSERT_TRUE( m.empty());
 238             ASSERT_CONTAINER_SIZE( m, 0 );
 239
 240             typedef Map::value_type map_pair;
 241
 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());
 246
 247             std::vector< value_type > arrVals;
 248             for ( size_t i = 0; i < kSize; ++i ) {
 249                 value_type val;
 250                 val.nVal = static_cast<int>( i );
 251                 val.strVal = std::to_string( i );
 252                 arrVals.push_back( val );
 253             }
 254
 255             // insert/find
 256             for ( auto const& i : arrKeys ) {
 257                 value_type const& val( arrVals.at( i.nKey ));
 258
 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 );
 264                 } ));
 265                 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
 266                     EXPECT_TRUE( false );
 267                 } ));
 268                 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
 269                     EXPECT_TRUE( false );
 270                 } ));
 271
 272                 std::pair< bool, bool > updResult;
 273
 274                 switch ( i.nKey % 16 ) {
 275                 case 0:
 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 );
 281                     } ));
 282                     break;
 283                 case 1:
 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 );
 289                     } ));
 290                     break;
 291                 case 2:
 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 );
 297                     } ));
 298                     break;
 299                 case 3:
 300                     ASSERT_TRUE( m.insert( i, val ));
 301                     ASSERT_FALSE( m.insert( i, val ));
 302                     break;
 303                 case 4:
 304                     ASSERT_TRUE( m.insert( i.nKey, val.strVal ));
 305                     ASSERT_FALSE( m.insert( i.nKey, val.strVal ));
 306                     break;
 307                 case 5:
 308                     ASSERT_TRUE( m.insert( val.strVal, i.nKey ));
 309                     ASSERT_FALSE( m.insert( val.strVal, i.nKey ));
 310                     break;
 311                 case 6:
 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 );
 315                     } ));
 316                     ASSERT_FALSE( m.insert_with( i, []( map_pair& v ) {
 317                         EXPECT_TRUE( false );
 318                     } ));
 319                     break;
 320                 case 7:
 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 );
 324                     } ));
 325                     ASSERT_FALSE( m.insert_with( i.nKey, []( map_pair& v ) {
 326                         EXPECT_TRUE( false );
 327                     } ));
 328                     break;
 329                 case 8:
 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 );
 333                     } ));
 334                     ASSERT_FALSE( m.insert_with( val.strVal, []( map_pair& v ) {
 335                         EXPECT_TRUE( false );
 336                     } ));
 337                     break;
 338                 case 9:
 339                     updResult = m.update( i.nKey, []( bool, map_pair& ) {
 340                         EXPECT_TRUE( false );
 341                     }, false );
 342                     ASSERT_FALSE( updResult.first );
 343                     ASSERT_FALSE( updResult.second );
 344
 345                     updResult = m.update( i.nKey, []( bool bNew, map_pair& v ) {
 346                         EXPECT_TRUE( bNew );
 347                         v.second.nVal = v.first.nKey;
 348                     });
 349                     ASSERT_TRUE( updResult.first );
 350                     ASSERT_TRUE( updResult.second );
 351
 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 );
 356                     } );
 357                     ASSERT_TRUE( updResult.first );
 358                     ASSERT_FALSE( updResult.second );
 359                     break;
 360                 case 10:
 361                     updResult = m.update( i, []( bool, map_pair& ) {
 362                         EXPECT_TRUE( false );
 363                     }, false );
 364                     ASSERT_FALSE( updResult.first );
 365                     ASSERT_FALSE( updResult.second );
 366
 367                     updResult = m.update( i, []( bool bNew, map_pair& v ) {
 368                         EXPECT_TRUE( bNew );
 369                         v.second.nVal = v.first.nKey;
 370                     });
 371                     ASSERT_TRUE( updResult.first );
 372                     ASSERT_TRUE( updResult.second );
 373
 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 );
 378                     } );
 379                     ASSERT_TRUE( updResult.first );
 380                     ASSERT_FALSE( updResult.second );
 381                     break;
 382                 case 11:
 383                     updResult = m.update( val.strVal, []( bool, map_pair& ) {
 384                         EXPECT_TRUE( false );
 385                     }, false );
 386                     ASSERT_FALSE( updResult.first );
 387                     ASSERT_FALSE( updResult.second );
 388
 389                     updResult = m.update( val.strVal, []( bool bNew, map_pair& v ) {
 390                         EXPECT_TRUE( bNew );
 391                         v.second.nVal = v.first.nKey;
 392                     });
 393                     ASSERT_TRUE( updResult.first );
 394                     ASSERT_TRUE( updResult.second );
 395
 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 );
 400                     } );
 401                     ASSERT_TRUE( updResult.first );
 402                     ASSERT_FALSE( updResult.second );
 403                     break;
 404                 case 12:
 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 );
 410                     } ));
 411                     break;
 412                 case 13:
 413                     ASSERT_TRUE( m.emplace( i, i.nKey ));
 414                     ASSERT_FALSE( m.emplace( i, i.nKey ));
 415                     break;
 416                 case 14:
 417                     {
 418                         std::string str = val.strVal;
 419                         ASSERT_TRUE( m.emplace( i, std::move( str )));
 420                         ASSERT_TRUE( str.empty());
 421                         str = val.strVal;
 422                         ASSERT_FALSE( m.emplace( i, std::move( str )));
 423                         ASSERT_TRUE( str.empty());
 424                     }
 425                     break;
 426                 case 15:
 427                     {
 428                         std::string str = val.strVal;
 429                         ASSERT_TRUE( m.emplace( i, i.nKey, std::move( str )));
 430                         ASSERT_TRUE( str.empty());
 431                         str = val.strVal;
 432                         ASSERT_FALSE( m.emplace( i, i.nKey, std::move( str )));
 433                         ASSERT_TRUE( str.empty());
 434                     }
 435                     break;
 436                 }
 437
 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 );
 444                 } ));
 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 );
 448                 } ));
 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 );
 452                 } ));
 453             }
 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() );
 458
 459             shuffle( arrKeys.begin(), arrKeys.end() );
 460
 461             // erase/find
 462             for ( auto const& i : arrKeys ) {
 463                 value_type const& val( arrVals.at( i.nKey ) );
 464
 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 );
 472                 } ));
 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 );
 476                 } ));
 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 );
 480                 } ));
 481
 482
 483                 switch ( i.nKey % 8 ) {
 484                 case 0:
 485                     ASSERT_TRUE( m.erase( i ));
 486                     ASSERT_FALSE( m.erase( i ));
 487                     break;
 488                 case 1:
 489                     ASSERT_TRUE( m.erase( i.nKey ));
 490                     ASSERT_FALSE( m.erase( i.nKey ));
 491                     break;
 492                 case 2:
 493                     ASSERT_TRUE( m.erase( val.strVal ));
 494                     ASSERT_FALSE( m.erase( val.strVal ));
 495                     break;
 496                 case 3:
 497                     ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less()));
 498                     ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less()));
 499                     break;
 500                 case 4:
 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 );
 504                     }));
 505                     ASSERT_FALSE( m.erase( i, []( map_pair& ) {
 506                         EXPECT_TRUE( false );
 507                     }));
 508                     break;
 509                 case 5:
 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 );
 513                     }));
 514                     ASSERT_FALSE( m.erase( i.nKey, []( map_pair& ) {
 515                         EXPECT_TRUE( false );
 516                     }));
 517                     break;
 518                 case 6:
 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 );
 522                     }));
 523                     ASSERT_FALSE( m.erase( val.strVal, []( map_pair& ) {
 524                         EXPECT_TRUE( false );
 525                     }));
 526                     break;
 527                 case 7:
 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 );
 531                     }));
 532                     ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& ) {
 533                         EXPECT_TRUE( false );
 534                     }));
 535                     break;
 536                 }
 537
 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 );
 544                 } ));
 545                 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
 546                     EXPECT_TRUE( false );
 547                 } ));
 548                 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
 549                     EXPECT_TRUE( false );
 550                 } ));
 551             }
 552             ASSERT_TRUE( m.empty() );
 553             ASSERT_CONTAINER_SIZE( m, 0 );
 554
 555             ASSERT_TRUE( m.begin() == m.end());
 556             ASSERT_TRUE( m.cbegin() == m.cend());
 557
 558             // clear
 559             for ( auto const& i : arrKeys )
 560                 ASSERT_TRUE( m.insert( i ));
 561
 562             ASSERT_FALSE( m.empty() );
 563             ASSERT_CONTAINER_SIZE( m, kSize );
 564
 565             m.clear();
 566
 567             ASSERT_TRUE( m.empty() );
 568             ASSERT_CONTAINER_SIZE( m, 0 );
 569         }
 570     };
 571
 572 } // namespace cds_test
 573
 574 #endif // #ifndef CDSUNIT_MAP_TEST_MAP_H