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