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