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