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
 155         struct simple_item_counter {
 156             size_t  m_nCount;
 157
 158             simple_item_counter()
 159                 : m_nCount(0)
 160             {}
 161
 162             size_t operator ++()
 163             {
 164                 return ++m_nCount;
 165             }
 166
 167             size_t operator --()
 168             {
 169                 return --m_nCount;
 170             }
 171
 172             void reset()
 173             {
 174                 m_nCount = 0;
 175             }
 176
 177             operator size_t() const
 178             {
 179                 return m_nCount;
 180             }
 181         };
 182
 183
 184         template <typename T>
 185         struct less
 186         {
 187             bool operator ()(const T& v1, const T& v2 ) const
 188             {
 189                 return v1.key() < v2.key();
 190             }
 191
 192             template <typename Q>
 193             bool operator ()(const T& v1, const Q& v2 ) const
 194             {
 195                 return v1.key() < v2;
 196             }
 197
 198             template <typename Q>
 199             bool operator ()(const Q& v1, const T& v2 ) const
 200             {
 201                 return v1 < v2.key();
 202             }
 203         };
 204
 205         template <typename T>
 206         struct cmp {
 207             int operator ()(const T& v1, const T& v2 ) const
 208             {
 209                 if ( v1.key() < v2.key() )
 210                     return -1;
 211                 return v1.key() > v2.key() ? 1 : 0;
 212             }
 213
 214             template <typename Q>
 215             int operator ()(const T& v1, const Q& v2 ) const
 216             {
 217                 if ( v1.key() < v2 )
 218                     return -1;
 219                 return v1.key() > v2 ? 1 : 0;
 220             }
 221
 222             template <typename Q>
 223             int operator ()(const Q& v1, const T& v2 ) const
 224             {
 225                 if ( v1 < v2.key() )
 226                     return -1;
 227                 return v1 > v2.key() ? 1 : 0;
 228             }
 229         };
 230
 231         template <typename T>
 232         struct equal_to {
 233             int operator ()( const T& v1, const T& v2 ) const
 234             {
 235                 return v1.key() == v2.key();
 236             }
 237
 238             template <typename Q>
 239             int operator ()( const T& v1, const Q& v2 ) const
 240             {
 241                 return v1.key() == v2;
 242             }
 243
 244             template <typename Q>
 245             int operator ()( const Q& v1, const T& v2 ) const
 246             {
 247                 return v1 == v2.key();
 248             }
 249         };
 250
 251         struct other_item {
 252             int nKey;
 253
 254             explicit other_item( int k )
 255                 : nKey( k )
 256             {}
 257
 258             int key() const
 259             {
 260                 return nKey;
 261             }
 262         };
 263
 264         struct other_less {
 265             template <typename Q, typename T>
 266             bool operator()( Q const& lhs, T const& rhs ) const
 267             {
 268                 return lhs.key() < rhs.key();
 269             }
 270         };
 271
 272         struct other_equal_to {
 273             template <typename Q, typename T>
 274             bool operator()( Q const& lhs, T const& rhs ) const
 275             {
 276                 return lhs.key() == rhs.key();
 277             }
 278         };
 279
 280         struct mock_disposer
 281         {
 282             template <typename T>
 283             void operator ()( T * p )
 284             {
 285                 ++p->nDisposeCount;
 286             }
 287         };
 288
 289     protected:
 290         template <typename Set>
 291         void test( Set& s )
 292         {
 293             test_< true >( s );
 294         }
 295
 296         template <bool Sorted, class Set>
 297         void test_( Set& s )
 298         {
 299             // Precondition: set is empty
 300             // Postcondition: set is empty
 301
 302             ASSERT_TRUE( s.empty() );
 303             ASSERT_CONTAINER_SIZE( s, 0 );
 304
 305             typedef typename Set::value_type value_type;
 306             typedef typename std::conditional< Sorted, other_less, other_equal_to >::type other_predicate;
 307             size_t const nSetSize = kSize;
 308
 309             std::vector< value_type > data;
 310             std::vector< size_t> indices;
 311             data.reserve( kSize );
 312             indices.reserve( kSize );
 313             for ( size_t key = 0; key < kSize; ++key ) {
 314                 data.push_back( value_type( static_cast<int>( key )));
 315                 indices.push_back( key );
 316             }
 317             shuffle( indices.begin(), indices.end() );
 318
 319             // insert/find
 320             for ( auto idx : indices ) {
 321                 auto& i = data[ idx ];
 322
 323                 ASSERT_FALSE( s.contains( i.nKey ));
 324                 ASSERT_FALSE( s.contains( i ));
 325                 ASSERT_FALSE( s.contains( other_item( i.key()), other_predicate()));
 326                 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
 327                 ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
 328
 329                 std::pair<bool, bool> updResult;
 330
 331                 updResult = s.update( i, []( bool bNew, value_type&, value_type& )
 332                 {
 333                     ASSERT_TRUE( false );
 334                 }, false );
 335                 EXPECT_FALSE( updResult.first );
 336                 EXPECT_FALSE( updResult.second );
 337
 338                 switch ( i.key() % 3 ) {
 339                 case 0:
 340                     ASSERT_TRUE( s.insert( i ));
 341                     ASSERT_FALSE( s.insert( i ));
 342                     updResult = s.update( i, []( bool bNew, value_type& val, value_type& arg)
 343                         {
 344                             EXPECT_FALSE( bNew );
 345                             EXPECT_EQ( &val, &arg );
 346                         }, false );
 347                     EXPECT_TRUE( updResult.first );
 348                     EXPECT_FALSE( updResult.second );
 349                     break;
 350                 case 1:
 351                     EXPECT_EQ( i.nUpdateNewCount, 0 );
 352                     ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
 353                     EXPECT_EQ( i.nUpdateNewCount, 1 );
 354                     ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ) );
 355                     EXPECT_EQ( i.nUpdateNewCount, 1 );
 356                     i.nUpdateNewCount = 0;
 357                     break;
 358                 case 2:
 359                     updResult = s.update( i, []( bool bNew, value_type& val, value_type& arg )
 360                     {
 361                         EXPECT_TRUE( bNew );
 362                         EXPECT_EQ( &val, &arg );
 363                     });
 364                     EXPECT_TRUE( updResult.first );
 365                     EXPECT_TRUE( updResult.second );
 366                     break;
 367                 }
 368
 369                 ASSERT_TRUE( s.contains( i.nKey ) );
 370                 ASSERT_TRUE( s.contains( i ) );
 371                 ASSERT_TRUE( s.contains( other_item( i.key() ), other_predicate()));
 372                 EXPECT_EQ( i.nFindCount, 0 );
 373                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
 374                 EXPECT_EQ( i.nFindCount, 1 );
 375                 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_predicate(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
 376                 EXPECT_EQ( i.nFindCount, 2 );
 377             }
 378             ASSERT_FALSE( s.empty() );
 379             ASSERT_CONTAINER_SIZE( s, nSetSize );
 380
 381             std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
 382
 383             // erase
 384             shuffle( indices.begin(), indices.end() );
 385             for ( auto idx : indices ) {
 386                 auto& i = data[ idx ];
 387
 388                 ASSERT_TRUE( s.contains( i.nKey ) );
 389                 ASSERT_TRUE( s.contains( i ) );
 390                 ASSERT_TRUE( s.contains( other_item( i.key() ), other_predicate() ) );
 391                 EXPECT_EQ( i.nFindCount, 0 );
 392                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ) );
 393                 EXPECT_EQ( i.nFindCount, 1 );
 394                 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_predicate(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ) );
 395                 EXPECT_EQ( i.nFindCount, 2 );
 396
 397                 value_type v( i );
 398                 switch ( i.key() % 6 ) {
 399                 case 0:
 400                     ASSERT_FALSE( s.unlink( v ));
 401                     ASSERT_TRUE( s.unlink( i ));
 402                     ASSERT_FALSE( s.unlink( i ) );
 403                     break;
 404                 case 1:
 405                     ASSERT_TRUE( s.erase( i.key()));
 406                     ASSERT_FALSE( s.erase( i.key() ) );
 407                     break;
 408                 case 2:
 409                     ASSERT_TRUE( s.erase( v ));
 410                     ASSERT_FALSE( s.erase( v ) );
 411                     break;
 412                 case 3:
 413                     ASSERT_TRUE( s.erase_with( other_item( i.key()), other_predicate()));
 414                     ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_predicate() ) );
 415                     break;
 416                 case 4:
 417                     EXPECT_EQ( i.nEraseCount, 0 );
 418                     ASSERT_TRUE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
 419                     EXPECT_EQ( i.nEraseCount, 1 );
 420                     ASSERT_FALSE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
 421                     EXPECT_EQ( i.nEraseCount, 1 );
 422                     break;
 423                 case 5:
 424                     EXPECT_EQ( i.nEraseCount, 0 );
 425                     ASSERT_TRUE( s.erase_with( other_item( i.key() ), other_predicate(), []( value_type& val ) { ++val.nEraseCount; } ));
 426                     EXPECT_EQ( i.nEraseCount, 1 );
 427                     ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_predicate(), []( value_type& val ) { ++val.nEraseCount; } ));
 428                     EXPECT_EQ( i.nEraseCount, 1 );
 429                     break;
 430                 }
 431
 432                 ASSERT_FALSE( s.contains( i.nKey ));
 433                 ASSERT_FALSE( s.contains( i ));
 434                 ASSERT_FALSE( s.contains( other_item( i.key()), other_predicate()));
 435                 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
 436                 ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} ));
 437             }
 438             ASSERT_TRUE( s.empty() );
 439             ASSERT_CONTAINER_SIZE( s, 0 );
 440
 441             // clear
 442             for ( auto& i : data ) {
 443                 i.clear_stat();
 444                 ASSERT_TRUE( s.insert( i ));
 445             }
 446             ASSERT_FALSE( s.empty() );
 447             ASSERT_CONTAINER_SIZE( s, nSetSize );
 448
 449             s.clear();
 450
 451             ASSERT_TRUE( s.empty() );
 452             ASSERT_CONTAINER_SIZE( s, 0 );
 453             for ( auto& i : data ) {
 454                 EXPECT_EQ( i.nDisposeCount, 1 );
 455             }
 456         }
 457     };
 458
 459 } // namespace cds_test
 460
 461 #endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_SET_H