test/unit/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_EQ( i.s.nFindCall, 0 );
 246                 EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } ));
 247                 EXPECT_EQ( i.s.nFindCall, 0 );
 248
 249                 switch ( i.nKey % 4 ) {
 250                 case 0:
 251                     EXPECT_TRUE( l.insert( i ));
 252                     break;
 253                 case 1:
 254                     EXPECT_EQ( i.s.nInsertCall, 0 );
 255                     EXPECT_TRUE( l.insert( i, []( value_type& i ) { ++i.s.nInsertCall; } ));
 256                     EXPECT_EQ( i.s.nInsertCall, 1 );
 257                     break;
 258                 case 2:
 259                     {
 260                         std::pair<bool, bool> ret = l.update( i, []( value_type& i, value_type * old ) {
 261                             EXPECT_TRUE( old == nullptr );
 262                             EXPECT_EQ( i.s.nUpdateNewCall, 0 );
 263                             ++i.s.nUpdateNewCall;
 264                         }, false );
 265                         EXPECT_EQ( i.s.nUpdateNewCall, 0 );
 266                         EXPECT_EQ( ret.first, false );
 267                         EXPECT_EQ( ret.second, false );
 268
 269                         ret = l.update( i, []( value_type& i, value_type * old ) {
 270                             EXPECT_TRUE( old == nullptr );
 271                             EXPECT_EQ( i.s.nUpdateNewCall, 0 );
 272                             ++i.s.nUpdateNewCall;
 273                         }, true );
 274                         EXPECT_EQ( i.s.nUpdateNewCall, 1 );
 275                         EXPECT_EQ( ret.first, true );
 276                         EXPECT_EQ( ret.second, true );
 277                     }
 278                     break;
 279                 case 3:
 280                     {
 281                         std::pair<bool, bool> ret = l.update( i, false );
 282                         EXPECT_EQ( ret.first, false );
 283                         EXPECT_EQ( ret.second, false );
 284
 285                         ret = l.update( i );
 286                         EXPECT_EQ( ret.first, true );
 287                         EXPECT_EQ( ret.second, true );
 288                     }
 289                     break;
 290                 }
 291
 292                 EXPECT_TRUE( l.contains( i.nKey ));
 293                 EXPECT_TRUE( l.contains( i ));
 294                 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()));
 295                 EXPECT_TRUE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } ));
 296                 EXPECT_EQ( i.s.nFindCall, 1 );
 297                 EXPECT_TRUE( l.find( i, []( value_type& item, value_type const& ) { ++item.s.nFindCall; } ));
 298                 EXPECT_EQ( i.s.nFindCall, 2 );
 299                 EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } ));
 300                 EXPECT_EQ( i.s.nFindCall, 3 );
 301
 302                 EXPECT_FALSE( l.insert( i ) );
 303                 ASSERT_FALSE( l.empty() );
 304
 305                 int const ckey = i.nKey;
 306                 iterator it = l.find( ckey );
 307                 ASSERT_FALSE( it == l.end() );
 308                 EXPECT_EQ( it->nKey, i.nKey );
 309                 EXPECT_EQ( (*it).nVal, i.nVal );
 310                 check_ordered( it, l.end() );
 311
 312                 it = l.find( i.nKey );
 313                 ASSERT_FALSE( it == l.end() );
 314                 EXPECT_EQ( it->nKey, i.nKey );
 315                 EXPECT_EQ( (*it).nVal, i.nVal );
 316                 check_ordered( it, l.end() );
 317
 318                 it = l.find_with( other_item( i.nKey ), other_less() );
 319                 ASSERT_FALSE( it == l.end() );
 320                 EXPECT_EQ( it->nKey, i.nKey );
 321                 EXPECT_EQ( it->nVal, i.nVal );
 322                 check_ordered( it, l.end() );
 323
 324             }
 325             ASSERT_CONTAINER_SIZE( l, nSize );
 326
 327             // check all items
 328             for ( auto const& i : arr ) {
 329                 EXPECT_TRUE( l.contains( i.nKey ));
 330                 EXPECT_TRUE( l.contains( i ));
 331                 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()));
 332                 EXPECT_TRUE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } ));
 333                 EXPECT_EQ( i.s.nFindCall, 4 );
 334                 EXPECT_TRUE( l.find( i, []( value_type& item, value_type const& ) { ++item.s.nFindCall; } ));
 335                 EXPECT_EQ( i.s.nFindCall, 5 );
 336                 EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } ));
 337                 EXPECT_EQ( i.s.nFindCall, 6 );
 338             }
 339             ASSERT_FALSE( l.empty() );
 340             ASSERT_CONTAINER_SIZE( l, nSize );
 341
 342             // update existing test
 343             for ( auto& i : arr2 ) {
 344                 EXPECT_EQ( i.s.nUpdateExistsCall, 0 );
 345                 std::pair<bool, bool> ret = l.update( i, update_functor() );
 346                 EXPECT_TRUE( ret.first );
 347                 EXPECT_FALSE( ret.second );
 348                 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
 349             }
 350
 351             // update with the same value must be empty - no functor is called
 352             for ( auto& i : arr2 ) {
 353                 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
 354                 std::pair<bool, bool> ret = l.update( i, update_functor() );
 355                 EXPECT_TRUE( ret.first );
 356                 EXPECT_FALSE( ret.second );
 357                 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
 358             }
 359
 360             for ( auto& i : arr ) {
 361                 EXPECT_EQ( i.s.nUpdateExistsCall, 0 );
 362                 std::pair<bool, bool> ret = l.update( i, []( value_type& i, value_type * old ) {
 363                     EXPECT_FALSE( old == nullptr );
 364                     EXPECT_EQ( i.s.nUpdateExistsCall, 0 );
 365                     ++i.s.nUpdateExistsCall;
 366                 });
 367                 EXPECT_TRUE( ret.first );
 368                 EXPECT_FALSE( ret.second );
 369                 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
 370             }
 371
 372             // erase test
 373             for ( auto const& i : arr ) {
 374                 if ( i.nKey & 1 )
 375                     EXPECT_TRUE( l.erase( i.nKey ));
 376                 else
 377                     EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less() ));
 378
 379                 EXPECT_FALSE( l.contains( i ));
 380             }
 381             EXPECT_TRUE( l.empty() );
 382             EXPECT_CONTAINER_SIZE( l, 0 );
 383
 384             // Apply retired pointer to clean links
 385             List::gc::force_dispose();
 386
 387             for ( auto const& i : arr )
 388                 EXPECT_EQ( i.s.nDisposeCount, 2 );
 389             for ( auto const& i : arr2 )
 390                 EXPECT_EQ( i.s.nDisposeCount, 1 );
 391
 392             // erase with functor
 393             for ( auto& i : arr ) {
 394                 int const updateNewCall = i.s.nUpdateNewCall;
 395                 std::pair<bool, bool> ret = l.update( i, update_functor(), false );
 396                 EXPECT_FALSE( ret.first );
 397                 EXPECT_FALSE( ret.second );
 398                 EXPECT_EQ( i.s.nUpdateNewCall, updateNewCall );
 399
 400                 ret = l.update( i, update_functor(), true );
 401                 EXPECT_TRUE( ret.first );
 402                 EXPECT_TRUE( ret.second );
 403                 EXPECT_EQ( i.s.nUpdateNewCall, updateNewCall + 1 );
 404             }
 405             EXPECT_FALSE( l.empty() );
 406             EXPECT_CONTAINER_SIZE( l, nSize );
 407
 408             for ( auto const& i : arr ) {
 409                 EXPECT_EQ( i.s.nEraseCall, 0 );
 410                 if ( i.nKey & 1 ) {
 411                     EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less(), erase_functor()));
 412                     EXPECT_FALSE( l.erase_with( other_item( i.nKey ), other_less(), erase_functor()));
 413                 }
 414                 else {
 415                     EXPECT_TRUE( l.erase( i.nKey, []( value_type& item) { ++item.s.nEraseCall; } ));
 416                     EXPECT_FALSE( l.erase( i.nKey, []( value_type& item) { ++item.s.nEraseCall; } ));
 417                 }
 418                 EXPECT_EQ( i.s.nEraseCall, 1 );
 419                 EXPECT_FALSE( l.contains( i.nKey ));
 420             }
 421             EXPECT_TRUE( l.empty() );
 422             EXPECT_CONTAINER_SIZE( l, 0 );
 423
 424             // Apply retired pointer to clean links
 425             List::gc::force_dispose();
 426
 427             for ( auto const& i : arr )
 428                 EXPECT_EQ( i.s.nDisposeCount, 3 );
 429
 430             // clear test
 431             for ( auto& i : arr )
 432                 EXPECT_TRUE( l.insert( i ));
 433
 434             EXPECT_FALSE( l.empty() );
 435             EXPECT_CONTAINER_SIZE( l, nSize );
 436
 437             l.clear();
 438
 439             EXPECT_TRUE( l.empty() );
 440             EXPECT_CONTAINER_SIZE( l, 0 );
 441
 442             // Apply retired pointer to clean links
 443             List::gc::force_dispose();
 444             for ( auto const& i : arr ) {
 445                 EXPECT_EQ( i.s.nDisposeCount, 4 );
 446                 EXPECT_FALSE( l.contains( i ));
 447             }
 448
 449             // unlink test
 450             for ( auto& i : arr )
 451                 EXPECT_TRUE( l.insert( i ) );
 452             for ( auto& i : arr ) {
 453                 value_type val( i );
 454                 EXPECT_TRUE( l.contains( val ));
 455                 EXPECT_FALSE( l.unlink( val ));
 456                 EXPECT_TRUE( l.contains( val ) );
 457                 EXPECT_TRUE( l.unlink( i ));
 458                 EXPECT_FALSE( l.unlink( i ));
 459                 EXPECT_FALSE( l.contains( i ) );
 460             }
 461             EXPECT_TRUE( l.empty() );
 462             EXPECT_CONTAINER_SIZE( l, 0 );
 463
 464             // Apply retired pointer to clean links
 465             List::gc::force_dispose();
 466             for ( auto const& i : arr ) {
 467                 EXPECT_EQ( i.s.nDisposeCount, 5 );
 468                 EXPECT_FALSE( l.contains( i ) );
 469             }
 470
 471             // Iterators on empty list
 472             {
 473                 auto it = l.begin();
 474                 auto itEnd = l.end();
 475                 auto cit = l.cbegin();
 476                 auto citEnd = l.cend();
 477
 478                 EXPECT_TRUE( it == itEnd );
 479                 EXPECT_TRUE( it == cit );
 480                 EXPECT_TRUE( cit == citEnd );
 481
 482                 ++it;
 483                 ++cit;
 484
 485                 EXPECT_TRUE( it == itEnd );
 486                 EXPECT_TRUE( it == cit );
 487                 EXPECT_TRUE( cit == citEnd );
 488             }
 489         }
 490
 491         template <typename List>
 492         void test_ordered_iterator( List& l )
 493         {
 494             // Precondition: list is empty
 495             // Postcondition: list is empty
 496
 497             static const size_t nSize = 20;
 498             typedef typename List::value_type value_type;
 499             value_type arr[nSize];
 500
 501             for ( size_t i = 0; i < nSize; ++i ) {
 502                 arr[i].nKey = static_cast<int>(i);
 503                 arr[i].nVal = arr[i].nKey * 10;
 504             }
 505             shuffle( arr, arr + nSize );
 506
 507             ASSERT_TRUE( l.empty() );
 508             ASSERT_CONTAINER_SIZE( l, 0 );
 509
 510             for ( auto& i : arr )
 511                 EXPECT_TRUE( l.insert( i ) );
 512
 513             int key = 0;
 514             for ( auto it = l.begin(); it != l.end(); ++it ) {
 515                 EXPECT_EQ( it->nKey, key );
 516                 EXPECT_EQ( (*it).nKey, key );
 517                 ++key;
 518             }
 519
 520             key = 0;
 521             for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
 522                 EXPECT_EQ( it->nKey, key );
 523                 EXPECT_EQ( (*it).nKey, key );
 524                 ++key;
 525             }
 526
 527             l.clear();
 528             List::gc::force_dispose();
 529             for ( auto const& i : arr ) {
 530                 EXPECT_EQ( i.s.nDisposeCount, 1 );
 531                 EXPECT_FALSE( l.contains( i ) );
 532             }
 533         }
 534
 535         template <typename Iterator>
 536         void check_ordered( Iterator first, Iterator last )
 537         {
 538             while ( first != last ) {
 539                 Iterator it = first;
 540                 if ( ++it != last ) {
 541                     EXPECT_LT( first->nKey, it->nKey );
 542                 }
 543                 first = it;
 544             }
 545         }
 546
 547     };
 548
 549 } // namespace cds_test
 550
 551 #endif // CDSUNIT_LIST_TEST_INTRUSIVE_ITERABLE_LIST_H