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