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_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.upsert( i, false );
 282                         EXPECT_EQ( ret.first, false );
 283                         EXPECT_EQ( ret.second, false );
 284
 285                         ret = l.upsert( 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             // Apply retired pointer to clean links
 361             List::gc::force_dispose();
 362
 363             for ( auto& i : arr ) {
 364                 EXPECT_EQ( i.s.nUpdateExistsCall, 0 );
 365                 std::pair<bool, bool> ret = l.update( i, []( value_type& i, value_type * old ) {
 366                     EXPECT_FALSE( old == nullptr );
 367                     EXPECT_EQ( i.s.nUpdateExistsCall, 0 );
 368                     ++i.s.nUpdateExistsCall;
 369                 });
 370                 EXPECT_TRUE( ret.first );
 371                 EXPECT_FALSE( ret.second );
 372                 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
 373             }
 374
 375             // erase test
 376             for ( auto const& i : arr ) {
 377                 if ( i.nKey & 1 )
 378                     EXPECT_TRUE( l.erase( i.nKey ));
 379                 else
 380                     EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less() ));
 381
 382                 EXPECT_FALSE( l.contains( i ));
 383             }
 384             EXPECT_TRUE( l.empty() );
 385             EXPECT_CONTAINER_SIZE( l, 0 );
 386
 387             // Apply retired pointer to clean links
 388             List::gc::force_dispose();
 389
 390             for ( auto const& i : arr )
 391                 EXPECT_EQ( i.s.nDisposeCount, 2 );
 392             for ( auto const& i : arr2 )
 393                 EXPECT_EQ( i.s.nDisposeCount, 1 );
 394
 395             // erase with functor
 396             for ( auto& i : arr ) {
 397                 int const updateNewCall = i.s.nUpdateNewCall;
 398                 std::pair<bool, bool> ret = l.update( i, update_functor(), false );
 399                 EXPECT_FALSE( ret.first );
 400                 EXPECT_FALSE( ret.second );
 401                 EXPECT_EQ( i.s.nUpdateNewCall, updateNewCall );
 402
 403                 ret = l.update( i, update_functor(), true );
 404                 EXPECT_TRUE( ret.first );
 405                 EXPECT_TRUE( ret.second );
 406                 EXPECT_EQ( i.s.nUpdateNewCall, updateNewCall + 1 );
 407             }
 408             EXPECT_FALSE( l.empty() );
 409             EXPECT_CONTAINER_SIZE( l, nSize );
 410
 411             for ( auto const& i : arr ) {
 412                 EXPECT_EQ( i.s.nEraseCall, 0 );
 413                 if ( i.nKey & 1 ) {
 414                     EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less(), erase_functor()));
 415                     EXPECT_FALSE( l.erase_with( other_item( i.nKey ), other_less(), erase_functor()));
 416                 }
 417                 else {
 418                     EXPECT_TRUE( l.erase( i.nKey, []( value_type& item) { ++item.s.nEraseCall; } ));
 419                     EXPECT_FALSE( l.erase( i.nKey, []( value_type& item) { ++item.s.nEraseCall; } ));
 420                 }
 421                 EXPECT_EQ( i.s.nEraseCall, 1 );
 422                 EXPECT_FALSE( l.contains( i.nKey ));
 423             }
 424             EXPECT_TRUE( l.empty() );
 425             EXPECT_CONTAINER_SIZE( l, 0 );
 426
 427             // Apply retired pointer to clean links
 428             List::gc::force_dispose();
 429
 430             for ( auto const& i : arr )
 431                 EXPECT_EQ( i.s.nDisposeCount, 3 );
 432
 433             // clear test
 434             for ( auto& i : arr )
 435                 EXPECT_TRUE( l.insert( i ));
 436
 437             EXPECT_FALSE( l.empty() );
 438             EXPECT_CONTAINER_SIZE( l, nSize );
 439
 440             l.clear();
 441
 442             EXPECT_TRUE( l.empty() );
 443             EXPECT_CONTAINER_SIZE( l, 0 );
 444
 445             // Apply retired pointer to clean links
 446             List::gc::force_dispose();
 447             for ( auto const& i : arr ) {
 448                 EXPECT_EQ( i.s.nDisposeCount, 4 );
 449                 EXPECT_FALSE( l.contains( i ));
 450             }
 451
 452             // unlink test
 453             for ( auto& i : arr )
 454                 EXPECT_TRUE( l.insert( i ) );
 455             for ( auto& i : arr ) {
 456                 value_type val( i );
 457                 EXPECT_TRUE( l.contains( val ));
 458                 EXPECT_FALSE( l.unlink( val ));
 459                 EXPECT_TRUE( l.contains( val ) );
 460                 EXPECT_TRUE( l.unlink( i ));
 461                 EXPECT_FALSE( l.unlink( i ));
 462                 EXPECT_FALSE( l.contains( i ) );
 463             }
 464             EXPECT_TRUE( l.empty() );
 465             EXPECT_CONTAINER_SIZE( l, 0 );
 466
 467             // Apply retired pointer to clean links
 468             List::gc::force_dispose();
 469             for ( auto const& i : arr ) {
 470                 EXPECT_EQ( i.s.nDisposeCount, 5 );
 471                 EXPECT_FALSE( l.contains( i ) );
 472             }
 473
 474             // Iterators on empty list
 475             {
 476                 auto it = l.begin();
 477                 auto itEnd = l.end();
 478                 auto cit = l.cbegin();
 479                 auto citEnd = l.cend();
 480
 481                 EXPECT_TRUE( it == itEnd );
 482                 EXPECT_TRUE( it == cit );
 483                 EXPECT_TRUE( cit == citEnd );
 484
 485                 ++it;
 486                 ++cit;
 487
 488                 EXPECT_TRUE( it == itEnd );
 489                 EXPECT_TRUE( it == cit );
 490                 EXPECT_TRUE( cit == citEnd );
 491             }
 492         }
 493
 494         template <typename List>
 495         void test_ordered_iterator( List& l )
 496         {
 497             // Precondition: list is empty
 498             // Postcondition: list is empty
 499
 500             static const size_t nSize = 20;
 501             typedef typename List::value_type value_type;
 502             value_type arr[nSize];
 503
 504             for ( size_t i = 0; i < nSize; ++i ) {
 505                 arr[i].nKey = static_cast<int>(i);
 506                 arr[i].nVal = arr[i].nKey * 10;
 507             }
 508             shuffle( arr, arr + nSize );
 509
 510             ASSERT_TRUE( l.empty() );
 511             ASSERT_CONTAINER_SIZE( l, 0 );
 512
 513             for ( auto& i : arr )
 514                 EXPECT_TRUE( l.insert( i ) );
 515
 516             int key = 0;
 517             for ( auto it = l.begin(); it != l.end(); ++it ) {
 518                 EXPECT_EQ( it->nKey, key );
 519                 EXPECT_EQ( (*it).nKey, key );
 520                 ++key;
 521             }
 522
 523             key = 0;
 524             for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
 525                 EXPECT_EQ( it->nKey, key );
 526                 EXPECT_EQ( (*it).nKey, key );
 527                 ++key;
 528             }
 529
 530             l.clear();
 531             List::gc::force_dispose();
 532             for ( auto const& i : arr ) {
 533                 EXPECT_EQ( i.s.nDisposeCount, 1 );
 534                 EXPECT_FALSE( l.contains( i ) );
 535             }
 536         }
 537
 538         template <typename Iterator>
 539         void check_ordered( Iterator first, Iterator last )
 540         {
 541             while ( first != last ) {
 542                 Iterator it = first;
 543                 if ( ++it != last ) {
 544                     EXPECT_LT( first->nKey, it->nKey );
 545                 }
 546                 first = it;
 547             }
 548         }
 549
 550     };
 551
 552 } // namespace cds_test
 553
 554 #endif // CDSUNIT_LIST_TEST_INTRUSIVE_ITERABLE_LIST_H