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