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