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 typename Map::value_type map_pair;
 241             size_t const kkSize = kSize;
 242
 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());
 247
 248             std::vector< value_type > arrVals;
 249             for ( size_t i = 0; i < kkSize; ++i ) {
 250                 value_type val;
 251                 val.nVal = static_cast<int>( i );
 252                 val.strVal = std::to_string( i );
 253                 arrVals.push_back( val );
 254             }
 255
 256             // insert/find
 257             for ( auto const& i : arrKeys ) {
 258                 value_type const& val( arrVals.at( i.nKey ));
 259
 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 );
 265                 } ));
 266                 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
 267                     EXPECT_TRUE( false );
 268                 } ));
 269                 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
 270                     EXPECT_TRUE( false );
 271                 } ));
 272
 273                 std::pair< bool, bool > updResult;
 274
 275                 switch ( i.nKey % 16 ) {
 276                 case 0:
 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 );
 282                     } ));
 283                     break;
 284                 case 1:
 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 );
 290                     } ));
 291                     break;
 292                 case 2:
 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 );
 298                     } ));
 299                     break;
 300                 case 3:
 301                     ASSERT_TRUE( m.insert( i, val ));
 302                     ASSERT_FALSE( m.insert( i, val ));
 303                     break;
 304                 case 4:
 305                     ASSERT_TRUE( m.insert( i.nKey, val.strVal ));
 306                     ASSERT_FALSE( m.insert( i.nKey, val.strVal ));
 307                     break;
 308                 case 5:
 309                     ASSERT_TRUE( m.insert( val.strVal, i.nKey ));
 310                     ASSERT_FALSE( m.insert( val.strVal, i.nKey ));
 311                     break;
 312                 case 6:
 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 );
 316                     } ));
 317                     ASSERT_FALSE( m.insert_with( i, []( map_pair& v ) {
 318                         EXPECT_TRUE( false );
 319                     } ));
 320                     break;
 321                 case 7:
 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 );
 325                     } ));
 326                     ASSERT_FALSE( m.insert_with( i.nKey, []( map_pair& v ) {
 327                         EXPECT_TRUE( false );
 328                     } ));
 329                     break;
 330                 case 8:
 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 );
 334                     } ));
 335                     ASSERT_FALSE( m.insert_with( val.strVal, []( map_pair& v ) {
 336                         EXPECT_TRUE( false );
 337                     } ));
 338                     break;
 339                 case 9:
 340                     updResult = m.update( i.nKey, []( bool, map_pair& ) {
 341                         EXPECT_TRUE( false );
 342                     }, false );
 343                     ASSERT_FALSE( updResult.first );
 344                     ASSERT_FALSE( updResult.second );
 345
 346                     updResult = m.update( i.nKey, []( bool bNew, map_pair& v ) {
 347                         EXPECT_TRUE( bNew );
 348                         v.second.nVal = v.first.nKey;
 349                     });
 350                     ASSERT_TRUE( updResult.first );
 351                     ASSERT_TRUE( updResult.second );
 352
 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 );
 357                     } );
 358                     ASSERT_TRUE( updResult.first );
 359                     ASSERT_FALSE( updResult.second );
 360                     break;
 361                 case 10:
 362                     updResult = m.update( i, []( bool, map_pair& ) {
 363                         EXPECT_TRUE( false );
 364                     }, false );
 365                     ASSERT_FALSE( updResult.first );
 366                     ASSERT_FALSE( updResult.second );
 367
 368                     updResult = m.update( i, []( bool bNew, map_pair& v ) {
 369                         EXPECT_TRUE( bNew );
 370                         v.second.nVal = v.first.nKey;
 371                     });
 372                     ASSERT_TRUE( updResult.first );
 373                     ASSERT_TRUE( updResult.second );
 374
 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 );
 379                     } );
 380                     ASSERT_TRUE( updResult.first );
 381                     ASSERT_FALSE( updResult.second );
 382                     break;
 383                 case 11:
 384                     updResult = m.update( val.strVal, []( bool, map_pair& ) {
 385                         EXPECT_TRUE( false );
 386                     }, false );
 387                     ASSERT_FALSE( updResult.first );
 388                     ASSERT_FALSE( updResult.second );
 389
 390                     updResult = m.update( val.strVal, []( bool bNew, map_pair& v ) {
 391                         EXPECT_TRUE( bNew );
 392                         v.second.nVal = v.first.nKey;
 393                     });
 394                     ASSERT_TRUE( updResult.first );
 395                     ASSERT_TRUE( updResult.second );
 396
 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 );
 401                     } );
 402                     ASSERT_TRUE( updResult.first );
 403                     ASSERT_FALSE( updResult.second );
 404                     break;
 405                 case 12:
 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 );
 411                     } ));
 412                     break;
 413                 case 13:
 414                     ASSERT_TRUE( m.emplace( i, i.nKey ));
 415                     ASSERT_FALSE( m.emplace( i, i.nKey ));
 416                     break;
 417                 case 14:
 418                     {
 419                         std::string str = val.strVal;
 420                         ASSERT_TRUE( m.emplace( i, std::move( str )));
 421                         ASSERT_TRUE( str.empty());
 422                         str = val.strVal;
 423                         ASSERT_FALSE( m.emplace( i, std::move( str )));
 424                         ASSERT_TRUE( str.empty());
 425                     }
 426                     break;
 427                 case 15:
 428                     {
 429                         std::string str = val.strVal;
 430                         ASSERT_TRUE( m.emplace( i, i.nKey, std::move( str )));
 431                         ASSERT_TRUE( str.empty());
 432                         str = val.strVal;
 433                         ASSERT_FALSE( m.emplace( i, i.nKey, std::move( str )));
 434                         ASSERT_TRUE( str.empty());
 435                     }
 436                     break;
 437                 }
 438
 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 );
 445                 } ));
 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 );
 449                 } ));
 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 );
 453                 } ));
 454             }
 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() );
 459
 460             shuffle( arrKeys.begin(), arrKeys.end() );
 461
 462             // erase/find
 463             for ( auto const& i : arrKeys ) {
 464                 value_type const& val( arrVals.at( i.nKey ) );
 465
 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 );
 473                 } ));
 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 );
 477                 } ));
 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 );
 481                 } ));
 482
 483
 484                 switch ( i.nKey % 8 ) {
 485                 case 0:
 486                     ASSERT_TRUE( m.erase( i ));
 487                     ASSERT_FALSE( m.erase( i ));
 488                     break;
 489                 case 1:
 490                     ASSERT_TRUE( m.erase( i.nKey ));
 491                     ASSERT_FALSE( m.erase( i.nKey ));
 492                     break;
 493                 case 2:
 494                     ASSERT_TRUE( m.erase( val.strVal ));
 495                     ASSERT_FALSE( m.erase( val.strVal ));
 496                     break;
 497                 case 3:
 498                     ASSERT_TRUE( m.erase_with( other_item( i.nKey ), other_less()));
 499                     ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less()));
 500                     break;
 501                 case 4:
 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 );
 505                     }));
 506                     ASSERT_FALSE( m.erase( i, []( map_pair& ) {
 507                         EXPECT_TRUE( false );
 508                     }));
 509                     break;
 510                 case 5:
 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 );
 514                     }));
 515                     ASSERT_FALSE( m.erase( i.nKey, []( map_pair& ) {
 516                         EXPECT_TRUE( false );
 517                     }));
 518                     break;
 519                 case 6:
 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 );
 523                     }));
 524                     ASSERT_FALSE( m.erase( val.strVal, []( map_pair& ) {
 525                         EXPECT_TRUE( false );
 526                     }));
 527                     break;
 528                 case 7:
 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 );
 532                     }));
 533                     ASSERT_FALSE( m.erase_with( other_item( i.nKey ), other_less(), []( map_pair& ) {
 534                         EXPECT_TRUE( false );
 535                     }));
 536                     break;
 537                 }
 538
 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 );
 545                 } ));
 546                 ASSERT_FALSE( m.find( i.nKey, []( map_pair const& ) {
 547                     EXPECT_TRUE( false );
 548                 } ));
 549                 ASSERT_FALSE( m.find_with( other_item( i.nKey ), other_less(), []( map_pair const& ) {
 550                     EXPECT_TRUE( false );
 551                 } ));
 552             }
 553             ASSERT_TRUE( m.empty() );
 554             ASSERT_CONTAINER_SIZE( m, 0 );
 555
 556             ASSERT_TRUE( m.begin() == m.end());
 557             ASSERT_TRUE( m.cbegin() == m.cend());
 558
 559             // clear
 560             for ( auto const& i : arrKeys )
 561                 ASSERT_TRUE( m.insert( i ));
 562
 563             ASSERT_FALSE( m.empty() );
 564             ASSERT_CONTAINER_SIZE( m, kkSize );
 565
 566             m.clear();
 567
 568             ASSERT_TRUE( m.empty() );
 569             ASSERT_CONTAINER_SIZE( m, 0 );
 570         }
 571     };
 572
 573 } // namespace cds_test
 574
 575 #endif // #ifndef CDSUNIT_MAP_TEST_MAP_H