test/unit/striped-set/test_set.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-2017
   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_STRIPED_SET_TEST_SET_H
  32 #define CDSUNIT_STRIPED_SET_TEST_SET_H
  33
  34 #include <cds_test/check_size.h>
  35 #include <cds_test/fixture.h>
  36
  37 #include <cds/opt/hash.h>
  38 #include <functional>   // ref
  39
  40 // forward declaration
  41 namespace cds { namespace container {}}
  42
  43 namespace cds_test {
  44     namespace co = cds::opt;
  45
  46     class container_set : public fixture
  47     {
  48     public:
  49         static size_t const kSize = 1000;
  50
  51         struct stat
  52         {
  53             unsigned int nFindCount;
  54             unsigned int nUpdateNewCount;
  55             unsigned int nUpdateCount;
  56             mutable unsigned int nEraseCount;
  57
  58             stat()
  59             {
  60                 clear_stat();
  61             }
  62
  63             stat( stat const& s )
  64             {
  65                 copy_stat( s );
  66             }
  67
  68             void clear_stat()
  69             {
  70                 memset( this, 0, sizeof( *this ));
  71             }
  72
  73             void copy_stat( stat const& s )
  74             {
  75                 memcpy( this, &s, sizeof( *this ));
  76             }
  77         };
  78
  79         struct other_item {
  80             int nKey;
  81
  82             explicit other_item( int k )
  83                 : nKey( k )
  84             {}
  85
  86             int key() const
  87             {
  88                 return nKey;
  89             }
  90         };
  91
  92         struct int_item: public stat
  93         {
  94             int nKey;
  95             int nVal;
  96             std::string strVal;
  97
  98             int_item()
  99                 : nKey( 0 )
 100                 , nVal( 0 )
 101             {}
 102
 103             explicit int_item( int k )
 104                 : nKey( k )
 105                 , nVal( k * 2 )
 106             {}
 107
 108             template <typename Q>
 109             explicit int_item( Q const& src )
 110                 : nKey( src.key())
 111                 , nVal( 0 )
 112             {}
 113
 114             int_item( int_item const& src )
 115                 : stat( src )
 116                 , nKey( src.nKey )
 117                 , nVal( src.nVal )
 118                 , strVal( src.strVal )
 119             {}
 120
 121             int_item( int_item&& src )
 122                 : stat( src )
 123                 , nKey( src.nKey )
 124                 , nVal( src.nVal )
 125                 , strVal( std::move( src.strVal ))
 126             {}
 127
 128             int_item( int k, std::string&& s )
 129                 : nKey( k )
 130                 , nVal( k * 2 )
 131                 , strVal( std::move( s ))
 132             {}
 133
 134             explicit int_item( other_item const& s )
 135                 : nKey( s.key())
 136                 , nVal( s.key() * 2 )
 137             {}
 138
 139             int_item& operator=( int_item const& src )
 140             {
 141                 if ( &src != this ) {
 142                     copy_stat( src );
 143                     nKey = src.nKey;
 144                     nVal = src.nVal;
 145                     strVal = src.strVal;
 146                 }
 147                 return *this;
 148             }
 149
 150             int_item& operator=( int_item&& src )
 151             {
 152                 if ( &src != this ) {
 153                     copy_stat( src );
 154                     nKey = src.nKey;
 155                     nVal = src.nVal;
 156                     strVal = std::move( src.strVal );
 157                 }
 158                 return *this;
 159             }
 160
 161             int key() const
 162             {
 163                 return nKey;
 164             }
 165         };
 166
 167         struct hash1 {
 168             size_t operator()( int i ) const
 169             {
 170                 return co::v::hash<int>()(i);
 171             }
 172             template <typename Item>
 173             size_t operator()( const Item& i ) const
 174             {
 175                 return (*this)(i.key());
 176             }
 177         };
 178
 179         struct hash2: private hash1
 180         {
 181             typedef hash1 base_class;
 182
 183             size_t operator()( int i ) const
 184             {
 185                 size_t h = ~(base_class::operator()( i ));
 186                 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
 187             }
 188             template <typename Item>
 189             size_t operator()( const Item& i ) const
 190             {
 191                 size_t h = ~(base_class::operator()( i ));
 192                 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
 193             }
 194         };
 195
 196         struct less
 197         {
 198             bool operator ()( int_item const& v1, int_item const& v2 ) const
 199             {
 200                 return v1.key() < v2.key();
 201             }
 202
 203             template <typename Q>
 204             bool operator ()( int_item const& v1, const Q& v2 ) const
 205             {
 206                 return v1.key() < v2;
 207             }
 208
 209             template <typename Q>
 210             bool operator ()( const Q& v1, int_item const& v2 ) const
 211             {
 212                 return v1 < v2.key();
 213             }
 214         };
 215
 216         struct equal_to
 217         {
 218             bool operator ()( int_item const& v1, int_item const& v2 ) const
 219             {
 220                 return v1.key() == v2.key();
 221             }
 222
 223             template <typename Q>
 224             bool operator ()( int_item const& v1, const Q& v2 ) const
 225             {
 226                 return v1.key() == v2;
 227             }
 228
 229             template <typename Q>
 230             bool operator ()( const Q& v1, int_item const& v2 ) const
 231             {
 232                 return v1 == v2.key();
 233             }
 234         };
 235
 236         struct cmp {
 237             int operator ()( int_item const& v1, int_item const& v2 ) const
 238             {
 239                 if ( v1.key() < v2.key())
 240                     return -1;
 241                 return v1.key() > v2.key() ? 1 : 0;
 242             }
 243
 244             template <typename T>
 245             int operator ()( T const& v1, int v2 ) const
 246             {
 247                 if ( v1.key() < v2 )
 248                     return -1;
 249                 return v1.key() > v2 ? 1 : 0;
 250             }
 251
 252             template <typename T>
 253             int operator ()( int v1, T const& v2 ) const
 254             {
 255                 if ( v1 < v2.key())
 256                     return -1;
 257                 return v1 > v2.key() ? 1 : 0;
 258             }
 259         };
 260
 261         struct other_less {
 262             template <typename Q, typename T>
 263             bool operator()( Q const& lhs, T const& rhs ) const
 264             {
 265                 return lhs.key() < rhs.key();
 266             }
 267         };
 268
 269         struct other_equal_to {
 270             template <typename Q, typename T>
 271             bool operator()( Q const& lhs, T const& rhs ) const
 272             {
 273                 return lhs.key() == rhs.key();
 274             }
 275         };
 276
 277     protected:
 278         template <typename Set>
 279         void test( Set& s )
 280         {
 281             test_< true >( s );
 282         }
 283
 284         template <bool Sorted, typename Set>
 285         void test_( Set& s )
 286         {
 287             // Precondition: set is empty
 288             // Postcondition: set is empty
 289
 290             ASSERT_TRUE( s.empty());
 291             ASSERT_CONTAINER_SIZE( s, 0 );
 292             size_t const nSetSize = kSize;
 293
 294             typedef typename Set::value_type value_type;
 295             typedef typename std::conditional< Sorted, other_less, other_equal_to >::type other_predicate;
 296
 297             std::vector< value_type > data;
 298             std::vector< size_t> indices;
 299             data.reserve( kSize );
 300             indices.reserve( kSize );
 301             for ( size_t key = 0; key < kSize; ++key ) {
 302                 data.push_back( value_type( static_cast<int>(key)));
 303                 indices.push_back( key );
 304             }
 305             shuffle( indices.begin(), indices.end());
 306
 307             // insert/find
 308             for ( auto idx : indices ) {
 309                 auto& i = data[idx];
 310
 311                 ASSERT_FALSE( s.contains( i.nKey ));
 312                 ASSERT_FALSE( s.contains( i ));
 313                 ASSERT_FALSE( s.contains( other_item( i.key()), other_predicate()));
 314                 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
 315                 ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
 316                 ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
 317
 318                 std::pair<bool, bool> updResult;
 319
 320                 std::string str;
 321                 updResult = s.update( i.key(), []( bool /*bNew*/, value_type&, int )
 322                 {
 323                     ASSERT_TRUE( false );
 324                 }, false );
 325                 EXPECT_FALSE( updResult.first );
 326                 EXPECT_FALSE( updResult.second );
 327
 328                 switch ( idx % 8 ) {
 329                 case 0:
 330                     ASSERT_TRUE( s.insert( i ));
 331                     ASSERT_FALSE( s.insert( i ));
 332                     updResult = s.update( i, []( bool bNew, value_type& val, value_type const& arg)
 333                         {
 334                             EXPECT_FALSE( bNew );
 335                             EXPECT_EQ( val.key(), arg.key());
 336                         }, false );
 337                     EXPECT_TRUE( updResult.first );
 338                     EXPECT_FALSE( updResult.second );
 339                     break;
 340                 case 1:
 341                     ASSERT_TRUE( s.insert( i.key()));
 342                     ASSERT_FALSE( s.insert( i.key()));
 343                     updResult = s.update( i.key(), []( bool bNew, value_type& val, int arg)
 344                         {
 345                             EXPECT_FALSE( bNew );
 346                             EXPECT_EQ( val.key(), arg );
 347                         }, false );
 348                     EXPECT_TRUE( updResult.first );
 349                     EXPECT_FALSE( updResult.second );
 350                     break;
 351                 case 2:
 352                     ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
 353                     ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
 354                     ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
 355                         {
 356                             EXPECT_EQ( v.key(), key );
 357                             EXPECT_EQ( v.nFindCount, 1u );
 358                         }));
 359                     break;
 360                 case 3:
 361                     ASSERT_TRUE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
 362                     ASSERT_FALSE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
 363                     ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
 364                         {
 365                             EXPECT_EQ( v.key(), key );
 366                             EXPECT_EQ( v.nFindCount, 1u );
 367                         }));
 368                     break;
 369                 case 4:
 370                     updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg )
 371                         {
 372                             EXPECT_TRUE( bNew );
 373                             EXPECT_EQ( v.key(), arg.key());
 374                             ++v.nUpdateNewCount;
 375                         });
 376                     EXPECT_TRUE( updResult.first );
 377                     EXPECT_TRUE( updResult.second );
 378
 379                     updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg )
 380                         {
 381                             EXPECT_FALSE( bNew );
 382                             EXPECT_EQ( v.key(), arg.key());
 383                             ++v.nUpdateNewCount;
 384                         }, false );
 385                     EXPECT_TRUE( updResult.first );
 386                     EXPECT_FALSE( updResult.second );
 387
 388                     ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
 389                         {
 390                             EXPECT_EQ( v.key(), key );
 391                             EXPECT_EQ( v.nUpdateNewCount, 2u );
 392                         }));
 393                     break;
 394                 case 5:
 395                     updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg )
 396                         {
 397                             EXPECT_TRUE( bNew );
 398                             EXPECT_EQ( v.key(), arg );
 399                             ++v.nUpdateNewCount;
 400                         });
 401                     EXPECT_TRUE( updResult.first );
 402                     EXPECT_TRUE( updResult.second );
 403
 404                     updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg )
 405                         {
 406                             EXPECT_FALSE( bNew );
 407                             EXPECT_EQ( v.key(), arg );
 408                             ++v.nUpdateNewCount;
 409                         }, false );
 410                     EXPECT_TRUE( updResult.first );
 411                     EXPECT_FALSE( updResult.second );
 412
 413                     ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
 414                         {
 415                             EXPECT_EQ( v.key(), arg.key());
 416                             EXPECT_EQ( v.nUpdateNewCount, 2u );
 417                         }));
 418                     break;
 419                 case 6:
 420                     ASSERT_TRUE( s.emplace( i.key()));
 421                     ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
 422                         {
 423                             EXPECT_EQ( v.key(), arg.key());
 424                             EXPECT_EQ( v.nVal, arg.nVal );
 425                         }));
 426                     break;
 427                 case 7:
 428                     str = "Hello!";
 429                     ASSERT_TRUE( s.emplace( i.key(), std::move( str )));
 430                     EXPECT_TRUE( str.empty());
 431                     ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
 432                         {
 433                             EXPECT_EQ( v.key(), arg.key());
 434                             EXPECT_EQ( v.nVal, arg.nVal );
 435                             EXPECT_EQ( v.strVal, std::string( "Hello!" ));
 436                         } ));
 437                     break;
 438                 default:
 439                     // forgot anything?..
 440                     ASSERT_TRUE( false );
 441                 }
 442
 443                 ASSERT_TRUE( s.contains( i.nKey ));
 444                 ASSERT_TRUE( s.contains( i ));
 445                 ASSERT_TRUE( s.contains( other_item( i.key()), other_predicate()));
 446                 ASSERT_TRUE( s.find( i.nKey, []( value_type&, int ) {} ));
 447                 ASSERT_TRUE( s.find( i, []( value_type&, value_type const& ) {} ));
 448                 ASSERT_TRUE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
 449             }
 450
 451             ASSERT_FALSE( s.empty());
 452             ASSERT_CONTAINER_SIZE( s, nSetSize );
 453
 454             // erase
 455             shuffle( indices.begin(), indices.end());
 456             for ( auto idx : indices ) {
 457                 auto& i = data[idx];
 458
 459                 ASSERT_TRUE( s.contains( i.nKey ));
 460                 ASSERT_TRUE( s.contains( i ));
 461                 ASSERT_TRUE( s.contains( other_item( i.key()), other_predicate()));
 462                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int )
 463                     {
 464                         v.nFindCount = 1;
 465                     }));
 466                 ASSERT_TRUE( s.find( i, []( value_type& v, value_type const& )
 467                     {
 468                         EXPECT_EQ( ++v.nFindCount, 2u );
 469                     }));
 470                 ASSERT_TRUE( s.find_with( other_item( i.key()), other_predicate(), []( value_type& v, other_item const& )
 471                     {
 472                         EXPECT_EQ( ++v.nFindCount, 3u );
 473                     }));
 474
 475                 int nKey = i.key() - 1;
 476                 switch ( idx % 6 ) {
 477                 case 0:
 478                     ASSERT_TRUE( s.erase( i.key()));
 479                     ASSERT_FALSE( s.erase( i.key()));
 480                     break;
 481                 case 1:
 482                     ASSERT_TRUE( s.erase( i ));
 483                     ASSERT_FALSE( s.erase( i ));
 484                     break;
 485                 case 2:
 486                     ASSERT_TRUE( s.erase_with( other_item( i.key()), other_predicate()));
 487                     ASSERT_FALSE( s.erase_with( other_item( i.key()), other_predicate()));
 488                     break;
 489                 case 3:
 490                     ASSERT_TRUE( s.erase( i.key(), [&nKey]( value_type const& v )
 491                         {
 492                             nKey = v.key();
 493                         } ));
 494                     EXPECT_EQ( i.key(), nKey );
 495
 496                     nKey = i.key() - 1;
 497                     ASSERT_FALSE( s.erase( i.key(), [&nKey]( value_type const& v )
 498                         {
 499                             nKey = v.key();
 500                         } ));
 501                     EXPECT_EQ( i.key(), nKey + 1 );
 502                     break;
 503                 case 4:
 504                     ASSERT_TRUE( s.erase( i, [&nKey]( value_type const& v )
 505                         {
 506                             nKey = v.key();
 507                         } ));
 508                     EXPECT_EQ( i.key(), nKey );
 509
 510                     nKey = i.key() - 1;
 511                     ASSERT_FALSE( s.erase( i, [&nKey]( value_type const& v )
 512                         {
 513                             nKey = v.key();
 514                         } ));
 515                     EXPECT_EQ( i.key(), nKey + 1 );
 516                     break;
 517                 case 5:
 518                     ASSERT_TRUE( s.erase_with( other_item( i.key()), other_predicate(), [&nKey]( value_type const& v )
 519                         {
 520                             nKey = v.key();
 521                         } ));
 522                     EXPECT_EQ( i.key(), nKey );
 523
 524                     nKey = i.key() - 1;
 525                     ASSERT_FALSE( s.erase_with( other_item( i.key()), other_predicate(), [&nKey]( value_type const& v )
 526                         {
 527                             nKey = v.key();
 528                         } ));
 529                     EXPECT_EQ( i.key(), nKey + 1 );
 530                     break;
 531                 }
 532
 533                 ASSERT_FALSE( s.contains( i.nKey ));
 534                 ASSERT_FALSE( s.contains( i ));
 535                 ASSERT_FALSE( s.contains( other_item( i.key()), other_predicate()));
 536                 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
 537                 ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
 538                 ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
 539             }
 540             ASSERT_TRUE( s.empty());
 541             ASSERT_CONTAINER_SIZE( s, 0u );
 542
 543
 544             // clear
 545             for ( auto& i : data ) {
 546                 ASSERT_TRUE( s.insert( i ));
 547             }
 548
 549             ASSERT_FALSE( s.empty());
 550             ASSERT_CONTAINER_SIZE( s, nSetSize );
 551
 552             s.clear();
 553
 554             ASSERT_TRUE( s.empty());
 555             ASSERT_CONTAINER_SIZE( s, 0u );
 556         }
 557     };
 558
 559 } // namespace cds_test
 560
 561 #endif // CDSUNIT_STRIPED_SET_TEST_SET_H