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