test/unit/intrusive-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 #include <functional>   // ref
  39
  40 // forward declaration
  41 namespace cds { namespace intrusive {}}
  42
  43 namespace cds_test {
  44
  45     namespace ci = cds::intrusive;
  46     namespace co = cds::opt;
  47
  48     class intrusive_set: public fixture
  49     {
  50     public:
  51         static size_t const kSize = 100;
  52
  53         struct stat
  54         {
  55             unsigned int nDisposeCount  ;   // count of disposer calling
  56             unsigned int nFindCount     ;   // count of find-functor calling
  57             unsigned int nUpdateNewCount;
  58             unsigned int nUpdateCount;
  59             mutable unsigned int nEraseCount;
  60
  61             stat()
  62             {
  63                 clear_stat();
  64             }
  65
  66             void clear_stat()
  67             {
  68                 memset( this, 0, sizeof( *this ) );
  69             }
  70         };
  71
  72         template <typename Node>
  73         struct base_int_item
  74             : public Node
  75             , public stat
  76
  77         {
  78             int nKey;
  79             int nVal;
  80
  81             base_int_item()
  82             {}
  83
  84             explicit base_int_item( int key )
  85                 : nKey( key )
  86                 , nVal( key )
  87             {}
  88
  89             base_int_item(int key, int val)
  90                 : nKey( key )
  91                 , nVal(val)
  92             {}
  93
  94             base_int_item( base_int_item const& v )
  95                 : Node()
  96                 , stat()
  97                 , nKey( v.nKey )
  98                 , nVal( v.nVal )
  99             {}
 100
 101             int key() const
 102             {
 103                 return nKey;
 104             }
 105         };
 106
 107         template <typename Node>
 108         struct member_int_item: public stat
 109         {
 110             int nKey;
 111             int nVal;
 112
 113             Node hMember;
 114
 115             stat s;
 116
 117             member_int_item()
 118             {}
 119
 120             explicit member_int_item( int key )
 121                 : nKey( key )
 122                 , nVal( key )
 123             {}
 124
 125             member_int_item(int key, int val)
 126                 : nKey( key )
 127                 , nVal(val)
 128             {}
 129
 130             member_int_item(member_int_item const& v )
 131                 : stat()
 132                 , nKey( v.nKey )
 133                 , nVal( v.nVal )
 134             {}
 135
 136             int key() const
 137             {
 138                 return nKey;
 139             }
 140         };
 141
 142         struct hash_int {
 143             size_t operator()( int i ) const
 144             {
 145                 return co::v::hash<int>()( i );
 146             }
 147             template <typename Item>
 148             size_t operator()( const Item& i ) const
 149             {
 150                 return (*this)( i.key() );
 151             }
 152         };
 153
 154         struct simple_item_counter {
 155             size_t  m_nCount;
 156
 157             simple_item_counter()
 158                 : m_nCount(0)
 159             {}
 160
 161             size_t operator ++()
 162             {
 163                 return ++m_nCount;
 164             }
 165
 166             size_t operator --()
 167             {
 168                 return --m_nCount;
 169             }
 170
 171             void reset()
 172             {
 173                 m_nCount = 0;
 174             }
 175
 176             operator size_t() const
 177             {
 178                 return m_nCount;
 179             }
 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         struct other_item {
 232             int nKey;
 233
 234             explicit other_item( int k )
 235                 : nKey( k )
 236             {}
 237
 238             int key() const
 239             {
 240                 return nKey;
 241             }
 242         };
 243
 244         struct other_less {
 245             template <typename Q, typename T>
 246             bool operator()( Q const& lhs, T const& rhs ) const
 247             {
 248                 return lhs.key() < rhs.key();
 249             }
 250         };
 251
 252         struct mock_disposer
 253         {
 254             template <typename T>
 255             void operator ()( T * p )
 256             {
 257                 ++p->nDisposeCount;
 258             }
 259         };
 260
 261     protected:
 262         template <class Set>
 263         void test( Set& s )
 264         {
 265             // Precondition: set is empty
 266             // Postcondition: set is empty
 267
 268             ASSERT_TRUE( s.empty() );
 269             ASSERT_CONTAINER_SIZE( s, 0 );
 270             size_t const nSetSize = kSize;
 271
 272             typedef typename Set::value_type value_type;
 273
 274             std::vector< value_type > data;
 275             std::vector< size_t> indices;
 276             data.reserve( kSize );
 277             indices.reserve( kSize );
 278             for ( size_t key = 0; key < kSize; ++key ) {
 279                 data.push_back( value_type( static_cast<int>( key )));
 280                 indices.push_back( key );
 281             }
 282             shuffle( indices.begin(), indices.end() );
 283
 284             // insert/find
 285             for ( auto idx : indices ) {
 286                 auto& i = data[ idx ];
 287
 288                 ASSERT_FALSE( s.contains( i.nKey ));
 289                 ASSERT_FALSE( s.contains( i ));
 290                 ASSERT_FALSE( s.contains( other_item( i.key()), other_less()));
 291                 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
 292                 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
 293
 294                 std::pair<bool, bool> updResult;
 295
 296                 updResult = s.update( i, []( bool, value_type&, value_type& )
 297                 {
 298                     ASSERT_TRUE( false );
 299                 }, false );
 300                 EXPECT_FALSE( updResult.first );
 301                 EXPECT_FALSE( updResult.second );
 302
 303                 switch ( i.key() % 3 ) {
 304                 case 0:
 305                     ASSERT_TRUE( s.insert( i ));
 306                     ASSERT_FALSE( s.insert( i ));
 307                     updResult = s.update( i, []( bool bNew, value_type& val, value_type& arg)
 308                         {
 309                             EXPECT_FALSE( bNew );
 310                             EXPECT_EQ( &val, &arg );
 311                         }, false );
 312                     EXPECT_TRUE( updResult.first );
 313                     EXPECT_FALSE( updResult.second );
 314                     break;
 315                 case 1:
 316                     EXPECT_EQ( i.nUpdateNewCount, 0 );
 317                     ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
 318                     EXPECT_EQ( i.nUpdateNewCount, 1 );
 319                     ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ) );
 320                     EXPECT_EQ( i.nUpdateNewCount, 1 );
 321                     i.nUpdateNewCount = 0;
 322                     break;
 323                 case 2:
 324                     updResult = s.update( i, []( bool bNew, value_type& val, value_type& arg )
 325                     {
 326                         EXPECT_TRUE( bNew );
 327                         EXPECT_EQ( &val, &arg );
 328                     });
 329                     EXPECT_TRUE( updResult.first );
 330                     EXPECT_TRUE( updResult.second );
 331                     break;
 332                 }
 333
 334                 ASSERT_TRUE( s.contains( i.nKey ) );
 335                 ASSERT_TRUE( s.contains( i ) );
 336                 ASSERT_TRUE( s.contains( other_item( i.key() ), other_less()));
 337                 EXPECT_EQ( i.nFindCount, 0 );
 338                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
 339                 EXPECT_EQ( i.nFindCount, 1 );
 340                 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
 341                 EXPECT_EQ( i.nFindCount, 2 );
 342             }
 343             ASSERT_FALSE( s.empty() );
 344             ASSERT_CONTAINER_SIZE( s, nSetSize );
 345
 346             std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
 347
 348             // erase
 349             shuffle( indices.begin(), indices.end() );
 350             for ( auto idx : indices ) {
 351                 auto& i = data[ idx ];
 352
 353                 ASSERT_TRUE( s.contains( i.nKey ) );
 354                 ASSERT_TRUE( s.contains( i ) );
 355                 ASSERT_TRUE( s.contains( other_item( i.key() ), other_less() ) );
 356                 EXPECT_EQ( i.nFindCount, 0u );
 357                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ) );
 358                 EXPECT_EQ( i.nFindCount, 1u );
 359                 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ) );
 360                 EXPECT_EQ( i.nFindCount, 2u );
 361
 362                 value_type v( i );
 363                 switch ( i.key() % 6 ) {
 364                 case 0:
 365                     ASSERT_FALSE( s.unlink( v ));
 366                     ASSERT_TRUE( s.unlink( i ));
 367                     ASSERT_FALSE( s.unlink( i ) );
 368                     break;
 369                 case 1:
 370                     ASSERT_TRUE( s.erase( i.key()));
 371                     ASSERT_FALSE( s.erase( i.key() ) );
 372                     break;
 373                 case 2:
 374                     ASSERT_TRUE( s.erase( v ));
 375                     ASSERT_FALSE( s.erase( v ) );
 376                     break;
 377                 case 3:
 378                     ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less()));
 379                     ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_less() ) );
 380                     break;
 381                 case 4:
 382                     EXPECT_EQ( i.nEraseCount, 0 );
 383                     ASSERT_TRUE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
 384                     EXPECT_EQ( i.nEraseCount, 1 );
 385                     ASSERT_FALSE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
 386                     EXPECT_EQ( i.nEraseCount, 1 );
 387                     break;
 388                 case 5:
 389                     EXPECT_EQ( i.nEraseCount, 0 );
 390                     ASSERT_TRUE( s.erase_with( other_item( i.key() ), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
 391                     EXPECT_EQ( i.nEraseCount, 1 );
 392                     ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
 393                     EXPECT_EQ( i.nEraseCount, 1 );
 394                     break;
 395                 }
 396
 397                 ASSERT_FALSE( s.contains( i.nKey ));
 398                 ASSERT_FALSE( s.contains( i ));
 399                 ASSERT_FALSE( s.contains( other_item( i.key()), other_less()));
 400                 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
 401                 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
 402             }
 403             ASSERT_TRUE( s.empty() );
 404             ASSERT_CONTAINER_SIZE( s, 0 );
 405
 406             // Force retiring cycle
 407             Set::gc::force_dispose();
 408             for ( auto& i : data ) {
 409                 EXPECT_EQ( i.nDisposeCount, 1 );
 410             }
 411
 412             // clear
 413             for ( auto& i : data ) {
 414                 i.clear_stat();
 415                 ASSERT_TRUE( s.insert( i ));
 416             }
 417             ASSERT_FALSE( s.empty() );
 418             ASSERT_CONTAINER_SIZE( s, nSetSize );
 419
 420             // Iterator test
 421             for ( auto it = s.begin(); it != s.end(); ++it ) {
 422                 ++it->nFindCount;
 423             }
 424             for ( auto it = s.cbegin(); it != s.cend(); ++it ) {
 425                 EXPECT_EQ( it->nFindCount, 1 );
 426             }
 427             for ( auto& i : data ) {
 428                 EXPECT_EQ( i.nFindCount, 1 );
 429             }
 430
 431             // clear test
 432             s.clear();
 433
 434             ASSERT_TRUE( s.empty());
 435             ASSERT_CONTAINER_SIZE( s, 0 );
 436             ASSERT_TRUE( s.begin() == s.end() );
 437             ASSERT_TRUE( s.cbegin() == s.cend() );
 438
 439             // Force retiring cycle
 440             Set::gc::force_dispose();
 441             for ( auto& i : data ) {
 442                 EXPECT_EQ( i.nDisposeCount, 1 );
 443             }
 444
 445         }
 446     };
 447
 448 } // namespace cds_test
 449
 450 #endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_SET_H