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         template <typename Node>
  70         struct base_int_item
  71             : public Node
  72             , public stat
  73
  74         {
  75             int nKey;
  76             int nVal;
  77
  78             base_int_item()
  79             {}
  80
  81             explicit base_int_item( int key )
  82                 : nKey( key )
  83                 , nVal( key )
  84             {}
  85
  86             base_int_item(int key, int val)
  87                 : nKey( key )
  88                 , nVal(val)
  89             {}
  90
  91             base_int_item( base_int_item const& v )
  92                 : Node()
  93                 , stat()
  94                 , nKey( v.nKey )
  95                 , nVal( v.nVal )
  96             {}
  97
  98             int key() const
  99             {
 100                 return nKey;
 101             }
 102         };
 103
 104         template <typename Node>
 105         struct member_int_item: public stat
 106         {
 107             int nKey;
 108             int nVal;
 109
 110             Node hMember;
 111
 112             stat t;
 113
 114             member_int_item()
 115             {}
 116
 117             explicit member_int_item( int key )
 118                 : nKey( key )
 119                 , nVal( key )
 120             {}
 121
 122             member_int_item(int key, int val)
 123                 : nKey( key )
 124                 , nVal(val)
 125             {}
 126
 127             member_int_item(member_int_item const& v )
 128                 : stat()
 129                 , nKey( v.nKey )
 130                 , nVal( v.nVal )
 131             {}
 132
 133             int key() const
 134             {
 135                 return nKey;
 136             }
 137         };
 138
 139         struct simple_item_counter {
 140             size_t  m_nCount;
 141
 142             simple_item_counter()
 143                 : m_nCount(0)
 144             {}
 145
 146             size_t operator ++()
 147             {
 148                 return ++m_nCount;
 149             }
 150
 151             size_t operator --()
 152             {
 153                 return --m_nCount;
 154             }
 155
 156             void reset()
 157             {
 158                 m_nCount = 0;
 159             }
 160
 161             operator size_t() const
 162             {
 163                 return m_nCount;
 164             }
 165         };
 166
 167
 168         template <typename T>
 169         struct less
 170         {
 171             bool operator ()(T const& v1, T const& v2 ) const
 172             {
 173                 return v1.key() < v2.key();
 174             }
 175
 176             bool operator()( T const& lhs, int rhs ) const
 177             {
 178                 return lhs.key() < rhs;
 179             }
 180
 181             bool operator()( int lhs, T const& rhs ) const
 182             {
 183                 return lhs < rhs.key();
 184             }
 185         };
 186
 187         template <typename T>
 188         struct cmp
 189         {
 190             int operator ()(T const& v1, T const& v2 ) const
 191             {
 192                 if ( v1.key() < v2.key() )
 193                     return -1;
 194                 return v1.key() > v2.key() ? 1 : 0;
 195             }
 196
 197             bool operator()( T const& lhs, int rhs ) const
 198             {
 199                 if ( lhs.key() < rhs )
 200                     return -1;
 201                 return lhs.key() > rhs ? 1 : 0;
 202             }
 203
 204             bool operator()( int lhs, T const& rhs ) const
 205             {
 206                 if ( lhs < rhs.key() )
 207                     return -1;
 208                 return lhs > rhs.key() ? 1 : 0;
 209             }
 210         };
 211
 212         struct other_item {
 213             int nKey;
 214
 215             explicit other_item( int k )
 216                 : nKey( k )
 217             {}
 218
 219             int key() const
 220             {
 221                 return nKey;
 222             }
 223         };
 224
 225         struct other_less {
 226             template <typename Q, typename T>
 227             bool operator()( Q const& lhs, T const& rhs ) const
 228             {
 229                 return lhs.key() < rhs.key();
 230             }
 231         };
 232
 233         struct mock_disposer
 234         {
 235             template <typename T>
 236             void operator ()( T * p )
 237             {
 238                 ++p->nDisposeCount;
 239             }
 240         };
 241
 242     protected:
 243         template <class Tree>
 244         void test( Tree& t )
 245         {
 246             // Precondition: tree is empty
 247             // Postcondition: tree is empty
 248
 249             ASSERT_TRUE( t.empty() );
 250             ASSERT_CONTAINER_SIZE( t, 0 );
 251             size_t const nTreeSize = kSize;
 252
 253             typedef typename Tree::value_type value_type;
 254
 255             std::vector< value_type > data;
 256             std::vector< size_t > indices;
 257             data.reserve( kSize );
 258             indices.reserve( kSize );
 259             for ( size_t key = 0; key < kSize; ++key ) {
 260                 data.push_back( value_type( static_cast<int>( key )));
 261                 indices.push_back( key );
 262             }
 263             shuffle( indices.begin(), indices.end() );
 264
 265             // insert/find
 266             for ( auto idx : indices ) {
 267                 auto& i = data[ idx ];
 268
 269                 ASSERT_FALSE( t.contains( i.nKey ));
 270                 ASSERT_FALSE( t.contains( i ));
 271                 ASSERT_FALSE( t.contains( other_item( i.key()), other_less()));
 272                 ASSERT_FALSE( t.find( i.nKey, []( value_type&, int ) {} ));
 273                 ASSERT_FALSE( t.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
 274
 275                 std::pair<bool, bool> updResult;
 276
 277                 updResult = t.update( i, []( bool bNew, value_type&, value_type& )
 278                 {
 279                     ASSERT_TRUE( false );
 280                 }, false );
 281                 EXPECT_FALSE( updResult.first );
 282                 EXPECT_FALSE( updResult.second );
 283
 284                 switch ( i.key() % 3 ) {
 285                 case 0:
 286                     ASSERT_TRUE( t.insert( i ));
 287                     ASSERT_FALSE( t.insert( i ));
 288                     updResult = t.update( i, []( bool bNew, value_type& val, value_type& arg)
 289                         {
 290                             EXPECT_FALSE( bNew );
 291                             EXPECT_EQ( &val, &arg );
 292                         }, false );
 293                     EXPECT_TRUE( updResult.first );
 294                     EXPECT_FALSE( updResult.second );
 295                     break;
 296                 case 1:
 297                     EXPECT_EQ( i.nUpdateNewCount, 0 );
 298                     ASSERT_TRUE( t.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
 299                     EXPECT_EQ( i.nUpdateNewCount, 1 );
 300                     ASSERT_FALSE( t.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ) );
 301                     EXPECT_EQ( i.nUpdateNewCount, 1 );
 302                     i.nUpdateNewCount = 0;
 303                     break;
 304                 case 2:
 305                     updResult = t.update( i, []( bool bNew, value_type& val, value_type& arg )
 306                     {
 307                         EXPECT_TRUE( false );
 308                     }, false );
 309                     EXPECT_FALSE( updResult.first );
 310                     EXPECT_FALSE( updResult.second );
 311
 312                     EXPECT_EQ( i.nUpdateNewCount, 0 );
 313                     updResult = t.update( i, []( bool bNew, value_type& val, value_type& arg )
 314                     {
 315                         EXPECT_TRUE( bNew );
 316                         EXPECT_EQ( &val, &arg );
 317                         ++val.nUpdateNewCount;
 318                     });
 319                     EXPECT_TRUE( updResult.first );
 320                     EXPECT_TRUE( updResult.second );
 321                     EXPECT_EQ( i.nUpdateNewCount, 1 );
 322                     i.nUpdateNewCount = 0;
 323
 324                     EXPECT_EQ( i.nUpdateCount, 0 );
 325                     updResult = t.update( i, []( bool bNew, value_type& val, value_type& arg )
 326                     {
 327                         EXPECT_FALSE( bNew );
 328                         EXPECT_EQ( &val, &arg );
 329                         ++val.nUpdateCount;
 330                     }, false );
 331                     EXPECT_TRUE( updResult.first );
 332                     EXPECT_TRUE( updResult.second );
 333                     EXPECT_EQ( i.nUpdateCount, 1 );
 334                     i.nUpdateCount = 0;
 335
 336                     break;
 337                 }
 338
 339                 ASSERT_TRUE( t.contains( i.nKey ) );
 340                 ASSERT_TRUE( t.contains( i ) );
 341                 ASSERT_TRUE( t.contains( other_item( i.key() ), other_less()));
 342                 EXPECT_EQ( i.nFindCount, 0 );
 343                 ASSERT_TRUE( t.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
 344                 EXPECT_EQ( i.nFindCount, 1 );
 345                 ASSERT_TRUE( t.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
 346                 EXPECT_EQ( i.nFindCount, 2 );
 347                 ASSERT_TRUE( t.find( i, []( value_type& v, value_type& ) { ++v.nFindCount; } ) );
 348                 EXPECT_EQ( i.nFindCount, 3 );
 349             }
 350             ASSERT_FALSE( t.empty() );
 351             ASSERT_CONTAINER_SIZE( t, nTreeSize );
 352
 353             std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
 354
 355             // erase
 356             shuffle( indices.begin(), indices.end() );
 357             for ( auto idx : indices ) {
 358                 auto& i = data[ idx ];
 359
 360                 ASSERT_TRUE( t.contains( i.nKey ) );
 361                 ASSERT_TRUE( t.contains( i ) );
 362                 ASSERT_TRUE( t.contains( other_item( i.key() ), other_less() ) );
 363                 EXPECT_EQ( i.nFindCount, 0 );
 364                 ASSERT_TRUE( t.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ) );
 365                 EXPECT_EQ( i.nFindCount, 1 );
 366                 ASSERT_TRUE( t.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ) );
 367                 EXPECT_EQ( i.nFindCount, 2 );
 368
 369                 value_type v( i );
 370                 switch ( i.key() % 6 ) {
 371                 case 0:
 372                     ASSERT_FALSE( t.unlink( v ));
 373                     ASSERT_TRUE( t.unlink( i ));
 374                     ASSERT_FALSE( t.unlink( i ) );
 375                     break;
 376                 case 1:
 377                     ASSERT_TRUE( t.erase( i.key()));
 378                     ASSERT_FALSE( t.erase( i.key() ) );
 379                     break;
 380                 case 2:
 381                     ASSERT_TRUE( t.erase( v ));
 382                     ASSERT_FALSE( t.erase( v ) );
 383                     break;
 384                 case 3:
 385                     ASSERT_TRUE( t.erase_with( other_item( i.key()), other_less()));
 386                     ASSERT_FALSE( t.erase_with( other_item( i.key() ), other_less() ) );
 387                     break;
 388                 case 4:
 389                     EXPECT_EQ( i.nEraseCount, 0 );
 390                     ASSERT_TRUE( t.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
 391                     EXPECT_EQ( i.nEraseCount, 1 );
 392                     ASSERT_FALSE( t.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
 393                     EXPECT_EQ( i.nEraseCount, 1 );
 394                     break;
 395                 case 5:
 396                     EXPECT_EQ( i.nEraseCount, 0 );
 397                     ASSERT_TRUE( t.erase_with( other_item( i.key() ), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
 398                     EXPECT_EQ( i.nEraseCount, 1 );
 399                     ASSERT_FALSE( t.erase_with( other_item( i.key() ), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
 400                     EXPECT_EQ( i.nEraseCount, 1 );
 401                     break;
 402                 }
 403
 404                 ASSERT_FALSE( t.contains( i.nKey ));
 405                 ASSERT_FALSE( t.contains( i ));
 406                 ASSERT_FALSE( t.contains( other_item( i.key()), other_less()));
 407                 ASSERT_FALSE( t.find( i.nKey, []( value_type&, int ) {} ));
 408                 ASSERT_FALSE( t.find( i,      []( value_type&, value_type const& ) {} ));
 409                 ASSERT_FALSE( t.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
 410             }
 411             ASSERT_TRUE( t.empty() );
 412             ASSERT_CONTAINER_SIZE( t, 0 );
 413
 414             // Force retiring cycle
 415             Tree::gc::force_dispose();
 416             for ( auto& i : data ) {
 417                 EXPECT_EQ( i.nDisposeCount, 1 );
 418             }
 419
 420             // clear
 421             for ( auto& i : data ) {
 422                 i.clear_stat();
 423                 ASSERT_TRUE( t.insert( i ));
 424             }
 425             ASSERT_FALSE( t.empty() );
 426             ASSERT_CONTAINER_SIZE( t, nTreeSize );
 427
 428             // clear test
 429             t.clear();
 430
 431             ASSERT_TRUE( t.empty());
 432             ASSERT_CONTAINER_SIZE( t, 0 );
 433             ASSERT_TRUE( t.begin() == t.end() );
 434             ASSERT_TRUE( t.cbegin() == t.cend() );
 435
 436             // Force retiring cycle
 437             Tree::gc::force_dispose();
 438             for ( auto& i : data ) {
 439                 EXPECT_EQ( i.nDisposeCount, 1 );
 440             }
 441         }
 442     };
 443
 444 } // namespace cds_test
 445
 446 #endif // #ifndef CDSUNIT_TREE_TEST_INTRUSIVE_TREE_H