test/unit/tree/test_intrusive_tree.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_TREE_TEST_INTRUSIVE_TREE_H
  32 #define CDSUNIT_TREE_TEST_INTRUSIVE_TREE_H
  33
  34 #include <cds_test/check_size.h>
  35 #include <cds_test/fixture.h>
  36
  37 #include <cds/opt/hash.h>
  38 // forward declaration
  39 namespace cds { namespace intrusive {}}
  40
  41 namespace cds_test {
  42
  43     namespace ci = cds::intrusive;
  44
  45     class intrusive_tree: public fixture
  46     {
  47     public:
  48         static size_t const kSize = 1000;
  49
  50         struct stat
  51         {
  52             unsigned int nDisposeCount  ;   // count of disposer calling
  53             unsigned int nFindCount     ;   // count of find-functor calling
  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         typedef int key_type;
  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             int nKey;
 110             int nVal;
 111
 112             Node hMember;
 113
 114             stat t;
 115
 116             member_int_item()
 117             {}
 118
 119             explicit member_int_item( int key )
 120                 : nKey( key )
 121                 , nVal( key )
 122             {}
 123
 124             member_int_item(int key, int val)
 125                 : nKey( key )
 126                 , nVal(val)
 127             {}
 128
 129             member_int_item(member_int_item const& v )
 130                 : stat()
 131                 , nKey( v.nKey )
 132                 , nVal( v.nVal )
 133             {}
 134
 135             int key() const
 136             {
 137                 return nKey;
 138             }
 139         };
 140
 141         struct key_extractor
 142         {
 143             template <typename T>
 144             void operator()( key_type& key, T const& val ) const
 145             {
 146                 key = val.key();
 147             }
 148         };
 149
 150         struct simple_item_counter {
 151             size_t  m_nCount;
 152
 153             simple_item_counter()
 154                 : m_nCount(0)
 155             {}
 156
 157             size_t operator ++()
 158             {
 159                 return ++m_nCount;
 160             }
 161
 162             size_t operator --()
 163             {
 164                 return --m_nCount;
 165             }
 166
 167             void reset()
 168             {
 169                 m_nCount = 0;
 170             }
 171
 172             operator size_t() const
 173             {
 174                 return m_nCount;
 175             }
 176         };
 177
 178
 179         template <typename T>
 180         struct less
 181         {
 182             bool operator ()(T const& v1, T const& v2 ) const
 183             {
 184                 return v1.key() < v2.key();
 185             }
 186
 187             bool operator()( T const& lhs, int rhs ) const
 188             {
 189                 return lhs.key() < rhs;
 190             }
 191
 192             bool operator()( int lhs, T const& rhs ) const
 193             {
 194                 return lhs < rhs.key();
 195             }
 196
 197             bool operator()( int lhs, int rhs ) const
 198             {
 199                 return lhs < rhs;
 200             }
 201         };
 202
 203         template <typename T>
 204         struct cmp
 205         {
 206             int operator ()(T const& v1, T const& v2 ) const
 207             {
 208                 if ( v1.key() < v2.key() )
 209                     return -1;
 210                 return v1.key() > v2.key() ? 1 : 0;
 211             }
 212
 213             int operator()( T const& lhs, int rhs ) const
 214             {
 215                 if ( lhs.key() < rhs )
 216                     return -1;
 217                 return lhs.key() > rhs ? 1 : 0;
 218             }
 219
 220             int operator()( int lhs, T const& rhs ) const
 221             {
 222                 if ( lhs < rhs.key() )
 223                     return -1;
 224                 return lhs > rhs.key() ? 1 : 0;
 225             }
 226
 227             int operator()( int lhs, int rhs ) const
 228             {
 229                 if ( lhs < rhs )
 230                     return -1;
 231                 return lhs > rhs ? 1 : 0;
 232             }
 233         };
 234
 235         struct other_item {
 236             int nKey;
 237
 238             explicit other_item( int k )
 239                 : nKey( k )
 240             {}
 241
 242             int key() const
 243             {
 244                 return nKey;
 245             }
 246         };
 247
 248         struct other_less {
 249             template <typename Q, typename T>
 250             bool operator()( Q const& lhs, T const& rhs ) const
 251             {
 252                 return lhs.key() < rhs.key();
 253             }
 254
 255             template <typename Q>
 256             bool operator()( Q const& lhs, int rhs ) const
 257             {
 258                 return lhs.key() < rhs;
 259             }
 260
 261             template <typename T>
 262             bool operator()( int lhs, T const& rhs ) const
 263             {
 264                 return lhs < rhs.key();
 265             }
 266         };
 267
 268         struct mock_disposer
 269         {
 270             template <typename T>
 271             void operator ()( T * p )
 272             {
 273                 ++p->nDisposeCount;
 274             }
 275         };
 276
 277     protected:
 278         template <class Tree>
 279         void test( Tree& t )
 280         {
 281             // Precondition: tree is empty
 282             // Postcondition: tree is empty
 283
 284             ASSERT_TRUE( t.empty() );
 285             ASSERT_CONTAINER_SIZE( t, 0 );
 286             size_t const nTreeSize = kSize;
 287
 288             typedef typename Tree::value_type value_type;
 289
 290             std::vector< value_type > data;
 291             std::vector< size_t > indices;
 292             data.reserve( kSize );
 293             indices.reserve( kSize );
 294             for ( size_t key = 0; key < kSize; ++key ) {
 295                 data.push_back( value_type( static_cast<int>( key )));
 296                 indices.push_back( key );
 297             }
 298             shuffle( indices.begin(), indices.end() );
 299
 300             // insert/find
 301             for ( auto idx : indices ) {
 302                 auto& i = data[ idx ];
 303
 304                 ASSERT_FALSE( t.contains( i.nKey ));
 305                 ASSERT_FALSE( t.contains( i ));
 306                 ASSERT_FALSE( t.contains( other_item( i.key()), other_less()));
 307                 ASSERT_FALSE( t.find( i.nKey, []( value_type&, int ) {} ));
 308                 ASSERT_FALSE( t.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
 309
 310                 std::pair<bool, bool> updResult;
 311
 312                 updResult = t.update( i, []( bool bNew, value_type&, value_type& )
 313                 {
 314                     ASSERT_TRUE( false );
 315                 }, false );
 316                 EXPECT_FALSE( updResult.first );
 317                 EXPECT_FALSE( updResult.second );
 318
 319                 switch ( i.key() % 3 ) {
 320                 case 0:
 321                     ASSERT_TRUE( t.insert( i ));
 322                     ASSERT_FALSE( t.insert( i ));
 323                     updResult = t.update( i, []( bool bNew, value_type& val, value_type& arg)
 324                         {
 325                             EXPECT_FALSE( bNew );
 326                             EXPECT_EQ( &val, &arg );
 327                         }, false );
 328                     EXPECT_TRUE( updResult.first );
 329                     EXPECT_FALSE( updResult.second );
 330                     break;
 331                 case 1:
 332                     EXPECT_EQ( i.nUpdateNewCount, 0 );
 333                     ASSERT_TRUE( t.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
 334                     EXPECT_EQ( i.nUpdateNewCount, 1 );
 335                     ASSERT_FALSE( t.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ) );
 336                     EXPECT_EQ( i.nUpdateNewCount, 1 );
 337                     i.nUpdateNewCount = 0;
 338                     break;
 339                 case 2:
 340                     updResult = t.update( i, []( bool bNew, value_type& val, value_type& arg )
 341                     {
 342                         EXPECT_TRUE( false );
 343                     }, false );
 344                     EXPECT_FALSE( updResult.first );
 345                     EXPECT_FALSE( updResult.second );
 346
 347                     EXPECT_EQ( i.nUpdateNewCount, 0 );
 348                     updResult = t.update( i, []( bool bNew, value_type& val, value_type& arg )
 349                     {
 350                         EXPECT_TRUE( bNew );
 351                         EXPECT_EQ( &val, &arg );
 352                         ++val.nUpdateNewCount;
 353                     });
 354                     EXPECT_TRUE( updResult.first );
 355                     EXPECT_TRUE( updResult.second );
 356                     EXPECT_EQ( i.nUpdateNewCount, 1 );
 357                     i.nUpdateNewCount = 0;
 358
 359                     EXPECT_EQ( i.nUpdateCount, 0 );
 360                     updResult = t.update( i, []( bool bNew, value_type& val, value_type& arg )
 361                     {
 362                         EXPECT_FALSE( bNew );
 363                         EXPECT_EQ( &val, &arg );
 364                         ++val.nUpdateCount;
 365                     }, false );
 366                     EXPECT_TRUE( updResult.first );
 367                     EXPECT_FALSE( updResult.second );
 368                     EXPECT_EQ( i.nUpdateCount, 1 );
 369                     i.nUpdateCount = 0;
 370
 371                     break;
 372                 }
 373
 374                 ASSERT_TRUE( t.contains( i.nKey ) );
 375                 ASSERT_TRUE( t.contains( i ) );
 376                 ASSERT_TRUE( t.contains( other_item( i.key() ), other_less()));
 377                 EXPECT_EQ( i.nFindCount, 0 );
 378                 ASSERT_TRUE( t.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
 379                 EXPECT_EQ( i.nFindCount, 1 );
 380                 ASSERT_TRUE( t.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
 381                 EXPECT_EQ( i.nFindCount, 2 );
 382                 ASSERT_TRUE( t.find( i, []( value_type& v, value_type& ) { ++v.nFindCount; } ) );
 383                 EXPECT_EQ( i.nFindCount, 3 );
 384             }
 385             ASSERT_FALSE( t.empty() );
 386             ASSERT_CONTAINER_SIZE( t, nTreeSize );
 387
 388             std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
 389
 390             // erase
 391             shuffle( indices.begin(), indices.end() );
 392             for ( auto idx : indices ) {
 393                 auto& i = data[ idx ];
 394
 395                 ASSERT_TRUE( t.contains( i.nKey ) );
 396                 ASSERT_TRUE( t.contains( i ) );
 397                 ASSERT_TRUE( t.contains( other_item( i.key() ), other_less() ) );
 398                 EXPECT_EQ( i.nFindCount, 0 );
 399                 ASSERT_TRUE( t.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ) );
 400                 EXPECT_EQ( i.nFindCount, 1 );
 401                 ASSERT_TRUE( t.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ) );
 402                 EXPECT_EQ( i.nFindCount, 2 );
 403
 404                 value_type v( i );
 405                 switch ( i.key() % 6 ) {
 406                 case 0:
 407                     ASSERT_FALSE( t.unlink( v ));
 408                     ASSERT_TRUE( t.unlink( i ));
 409                     ASSERT_FALSE( t.unlink( i ) );
 410                     break;
 411                 case 1:
 412                     ASSERT_TRUE( t.erase( i.key()));
 413                     ASSERT_FALSE( t.erase( i.key() ) );
 414                     break;
 415                 case 2:
 416                     ASSERT_TRUE( t.erase( v ));
 417                     ASSERT_FALSE( t.erase( v ) );
 418                     break;
 419                 case 3:
 420                     ASSERT_TRUE( t.erase_with( other_item( i.key()), other_less()));
 421                     ASSERT_FALSE( t.erase_with( other_item( i.key() ), other_less() ) );
 422                     break;
 423                 case 4:
 424                     EXPECT_EQ( i.nEraseCount, 0 );
 425                     ASSERT_TRUE( t.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
 426                     EXPECT_EQ( i.nEraseCount, 1 );
 427                     ASSERT_FALSE( t.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
 428                     EXPECT_EQ( i.nEraseCount, 1 );
 429                     break;
 430                 case 5:
 431                     EXPECT_EQ( i.nEraseCount, 0 );
 432                     ASSERT_TRUE( t.erase_with( other_item( i.key() ), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
 433                     EXPECT_EQ( i.nEraseCount, 1 );
 434                     ASSERT_FALSE( t.erase_with( other_item( i.key() ), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
 435                     EXPECT_EQ( i.nEraseCount, 1 );
 436                     break;
 437                 }
 438
 439                 ASSERT_FALSE( t.contains( i.nKey ));
 440                 ASSERT_FALSE( t.contains( i ));
 441                 ASSERT_FALSE( t.contains( other_item( i.key()), other_less()));
 442                 ASSERT_FALSE( t.find( i.nKey, []( value_type&, int ) {} ));
 443                 ASSERT_FALSE( t.find( i,      []( value_type&, value_type const& ) {} ));
 444                 ASSERT_FALSE( t.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
 445             }
 446             ASSERT_TRUE( t.empty() );
 447             ASSERT_CONTAINER_SIZE( t, 0 );
 448
 449             // Force retiring cycle
 450             Tree::gc::force_dispose();
 451             for ( auto& i : data ) {
 452                 EXPECT_EQ( i.nDisposeCount, 1 );
 453             }
 454
 455             // clear
 456             for ( auto idx : indices ) {
 457                 auto& i = data[idx];
 458                 i.clear_stat();
 459                 ASSERT_TRUE( t.insert( i ));
 460             }
 461             ASSERT_FALSE( t.empty() );
 462             ASSERT_CONTAINER_SIZE( t, nTreeSize );
 463
 464             // clear test
 465             t.clear();
 466
 467             ASSERT_TRUE( t.empty());
 468             ASSERT_CONTAINER_SIZE( t, 0 );
 469
 470             // Force retiring cycle
 471             Tree::gc::force_dispose();
 472             for ( auto& i : data ) {
 473                 EXPECT_EQ( i.nDisposeCount, 1 );
 474             }
 475         }
 476     };
 477
 478 } // namespace cds_test
 479
 480 #endif // #ifndef CDSUNIT_TREE_TEST_INTRUSIVE_TREE_H