tests/test-hdr/list/hdr_lazy.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
  31 #ifndef CDSTEST_HDR_LAZY_H
  32 #define CDSTEST_HDR_LAZY_H
  33
  34 #include "cppunit/cppunit_proxy.h"
  35 #include <cds/container/details/lazy_list_base.h>
  36
  37 namespace ordlist {
  38     namespace cc = cds::container;
  39     namespace co = cds::container::opt;
  40
  41     class LazyListTestHeader: public CppUnitMini::TestCase
  42     {
  43     public:
  44         struct stat {
  45             int nUpdateExistsCall;
  46             int nUpdateNewCall;
  47
  48             stat()
  49             {
  50                 nUpdateExistsCall
  51                     = nUpdateNewCall
  52                     = 0;
  53             }
  54         };
  55
  56         struct item {
  57             int     nKey;
  58             int     nVal;
  59
  60             stat    s;
  61
  62             item(int key)
  63                 : nKey( key )
  64                 , nVal( key * 2 )
  65                 , s()
  66             {}
  67
  68             item(int key, int val)
  69                 : nKey( key )
  70                 , nVal(val)
  71                 , s()
  72             {}
  73
  74             item( item const& v )
  75                 : nKey( v.nKey )
  76                 , nVal( v.nVal )
  77                 , s()
  78             {}
  79
  80             int key() const
  81             {
  82                 return nKey;
  83             }
  84         };
  85
  86         template <typename T>
  87         struct lt
  88         {
  89             bool operator ()(const T& v1, const T& v2 ) const
  90             {
  91                 return v1.key() < v2.key();
  92             }
  93
  94             template <typename Q>
  95             bool operator ()(const T& v1, const Q& v2 ) const
  96             {
  97                 return v1.key() < v2;
  98             }
  99
 100             template <typename Q>
 101             bool operator ()(const Q& v1, const T& v2 ) const
 102             {
 103                 return v1 < v2.key();
 104             }
 105         };
 106
 107         template <typename T>
 108         struct equal_to
 109         {
 110             bool operator ()(const T& v1, const T& v2 ) const
 111             {
 112                 return v1.key() == v2.key();
 113             }
 114
 115             template <typename Q>
 116             bool operator ()(const T& v1, const Q& v2 ) const
 117             {
 118                 return v1.key() == v2;
 119             }
 120
 121             template <typename Q>
 122             bool operator ()(const Q& v1, const T& v2 ) const
 123             {
 124                 return v1 == v2.key();
 125             }
 126         };
 127
 128         template <typename T>
 129         struct cmp {
 130             int operator ()(const T& v1, const T& v2 ) const
 131             {
 132                 if ( v1.key() < v2.key() )
 133                     return -1;
 134                 return v1.key() > v2.key() ? 1 : 0;
 135             }
 136
 137             template <typename Q>
 138             int operator ()(const T& v1, const Q& v2 ) const
 139             {
 140                 if ( v1.key() < v2 )
 141                     return -1;
 142                 return v1.key() > v2 ? 1 : 0;
 143             }
 144
 145             template <typename Q>
 146             int operator ()(const Q& v1, const T& v2 ) const
 147             {
 148                 if ( v1 < v2.key() )
 149                     return -1;
 150                 return v1 > v2.key() ? 1 : 0;
 151             }
 152         };
 153
 154         struct insert_functor {
 155             void operator ()( item& i )
 156             {
 157                 i.nVal = i.nKey * 1033;
 158             }
 159         };
 160         struct dummy_insert_functor {
 161             void operator ()( item& /*i*/ )
 162             {
 163                 // This functor should not be called
 164                 TestCase::current_test()->error( "CPPUNIT_ASSERT", "dummy_insert_functor should not be called", __FILE__, __LINE__ );
 165             }
 166         };
 167
 168         static void insert_function( item& i )
 169         {
 170             i.nVal = i.nKey * 1024;
 171         }
 172         static void dummy_insert_function( item& /*i*/ )
 173         {
 174             // This function should not be called
 175             TestCase::current_test()->error( "CPPUNIT_ASSERT", "dummy_insert_function should not be called", __FILE__, __LINE__ );
 176         }
 177
 178         struct erase_functor {
 179             unsigned int nEraseCall;
 180
 181             erase_functor()
 182                 : nEraseCall(0)
 183             {}
 184
 185             void operator()( item const& /*i*/)
 186             {
 187                 ++nEraseCall;
 188             }
 189         };
 190
 191         struct check_value {
 192             unsigned int m_nMultiplier;
 193
 194             check_value( unsigned int nMultiplier )
 195                 : m_nMultiplier( nMultiplier )
 196             {}
 197
 198             check_value( const check_value& s )
 199                 : m_nMultiplier( s.m_nMultiplier )
 200             {}
 201
 202             void operator()( item& i, int )
 203             {
 204                 CPPUNIT_ASSERT_CURRENT( int(i.nKey * m_nMultiplier) == i.nVal );
 205             }
 206         };
 207
 208         struct check_exact_value {
 209             int m_nExpected;
 210
 211             check_exact_value( int nExpected )
 212                 : m_nExpected( nExpected )
 213             {}
 214
 215             check_exact_value( check_exact_value const& s)
 216                 : m_nExpected( s.m_nExpected )
 217             {}
 218
 219             void operator()( item& i, int )
 220             {
 221                 CPPUNIT_ASSERT_CURRENT( i.nVal == m_nExpected );
 222             }
 223         };
 224
 225         struct dummy_check_value {
 226             void operator()( item& /*i*/, int )
 227             {
 228                 // This functor should not be called
 229                 TestCase::current_test()->error( "CPPUNIT_ASSERT", "dummy_check_value should not be called", __FILE__, __LINE__ );
 230             }
 231         };
 232
 233         struct update_functor {
 234             void operator()( bool /*bNew*/, item& i, int /*n*/ )
 235             {
 236                 i.nVal = i.nKey * 1024;
 237             }
 238         };
 239
 240         static void update_func( bool /*bNew*/, item& i, int n )
 241         {
 242             i.nVal = n * 1033;
 243         }
 244
 245         struct other_item
 246         {
 247             int nKey;
 248
 249             other_item()
 250             {}
 251
 252             other_item(int n)
 253                 : nKey(n)
 254             {}
 255         };
 256
 257         struct other_less
 258         {
 259             template <typename T1, typename T2>
 260             bool operator()( T1 const& t1, T2 const& t2 ) const
 261             {
 262                 return t1.nKey < t2.nKey;
 263             }
 264         };
 265
 266     protected:
 267         template <class OrdList>
 268         void test_with( OrdList& l )
 269         {
 270             typedef typename OrdList::value_type    value_type;
 271
 272             // The list should be empty
 273             CPPUNIT_ASSERT( l.empty() );
 274
 275             // insert test
 276             CPPUNIT_ASSERT( l.insert( 50 ) );
 277             CPPUNIT_ASSERT( l.insert( item( 25 )) );
 278             CPPUNIT_ASSERT( l.insert( item( 100 )) );
 279
 280             // insert failed - such key exists
 281             CPPUNIT_ASSERT( !l.insert( 50 ) );
 282             CPPUNIT_ASSERT( !l.insert( item( 100 )) );
 283
 284             // clear test
 285
 286             // The list should not be empty
 287             CPPUNIT_ASSERT( !l.empty() );
 288             l.clear();
 289             // and now the list is empty
 290             CPPUNIT_ASSERT( l.empty() );
 291
 292             // Test insert with functor
 293
 294             CPPUNIT_ASSERT( l.insert( 100, insert_functor() ) );
 295             // passed by ref
 296             {
 297                 insert_functor f;
 298                 CPPUNIT_ASSERT( l.insert( item( 25 ), std::ref( f ) ) );
 299                 CPPUNIT_ASSERT( !l.insert( item( 100 ), std::ref( f ) ) );
 300             }
 301             // Test insert with function
 302             CPPUNIT_ASSERT( l.insert( 50, insert_function ));
 303             CPPUNIT_ASSERT( !l.insert( 25, dummy_insert_function ));
 304             CPPUNIT_ASSERT( !l.insert( 100, dummy_insert_functor() ));
 305
 306             // The list should not be empty
 307             CPPUNIT_ASSERT( !l.empty() );
 308
 309             // Check inserted values
 310             {
 311                 int i;
 312                 i = 100;
 313
 314                 CPPUNIT_ASSERT( l.contains( 100 ));
 315                 CPPUNIT_ASSERT( l.find( i, check_value(1033) ));
 316                 {
 317                     check_value f(1033);
 318                     i = 25;
 319                     CPPUNIT_ASSERT( l.contains( 25, lt<value_type>() ));
 320                     CPPUNIT_ASSERT( l.find_with( i, lt<value_type>(), std::ref( f ) ) );
 321                 }
 322                 i = 50;
 323                 CPPUNIT_ASSERT( l.contains( 50 ));
 324                 CPPUNIT_ASSERT( l.find( i, check_value(1024) ));
 325
 326                 i = 10;
 327                 CPPUNIT_ASSERT( !l.contains( 10, lt<value_type>() ));
 328                 CPPUNIT_ASSERT( !l.find_with( i, lt<value_type>(), dummy_check_value() ));
 329                 i = 75;
 330                 CPPUNIT_ASSERT( !l.contains( 75 ));
 331                 CPPUNIT_ASSERT( !l.find( i, dummy_check_value() ));
 332                 i = 150;
 333                 CPPUNIT_ASSERT( !l.contains( 150 ));
 334                 CPPUNIT_ASSERT( !l.find( i, dummy_check_value() ));
 335             }
 336
 337             // The list should not be empty
 338             CPPUNIT_ASSERT( !l.empty() );
 339             l.clear();
 340             // and now the list is empty
 341             CPPUNIT_ASSERT( l.empty() );
 342
 343             // Update test
 344             {
 345                 std::pair<bool, bool>   updateResult;
 346                 update_functor f;
 347                 updateResult = l.update( 100, update_functor() );
 348                 CPPUNIT_ASSERT( updateResult.first );
 349                 CPPUNIT_ASSERT( updateResult.second );
 350
 351                 updateResult = l.update( 200, std::ref( f ) );
 352                 CPPUNIT_ASSERT( updateResult.first );
 353                 CPPUNIT_ASSERT( updateResult.second );
 354
 355                 updateResult = l.update( 50, update_func );
 356                 CPPUNIT_ASSERT( updateResult.first );
 357                 CPPUNIT_ASSERT( updateResult.second );
 358
 359                 int i;
 360                 i = 100;
 361                 CPPUNIT_ASSERT( l.find( i, check_value(1024) ));
 362                 i = 50;
 363                 CPPUNIT_ASSERT( l.find( i, check_value(1033) ));
 364                 i = 200;
 365                 CPPUNIT_ASSERT( l.find( i, check_value(1024) ));
 366
 367                 // update existing key
 368                 updateResult = l.update( 200, update_func );
 369                 CPPUNIT_ASSERT( updateResult.first );
 370                 CPPUNIT_ASSERT( !updateResult.second );
 371                 i = 200;
 372                 CPPUNIT_ASSERT( l.find( i, check_value(1033) ));
 373
 374                 updateResult = l.update( 50, update_functor() );
 375                 CPPUNIT_ASSERT( updateResult.first );
 376                 CPPUNIT_ASSERT( !updateResult.second );
 377                 i = 50;
 378                 CPPUNIT_ASSERT( l.find( i, check_value(1024) ));
 379             }
 380
 381             // erase test (list: 50, 100, 200)
 382             CPPUNIT_ASSERT( !l.empty() );
 383             CPPUNIT_ASSERT( l.insert(160));
 384             CPPUNIT_ASSERT( l.insert(250));
 385             CPPUNIT_ASSERT( !l.empty() );
 386
 387             CPPUNIT_ASSERT( !l.erase( 150 ));
 388
 389             CPPUNIT_ASSERT( l.erase( 100 ));
 390             CPPUNIT_ASSERT( !l.erase( 100 ));
 391
 392             CPPUNIT_ASSERT( l.erase_with( 200, lt<value_type>() ));
 393             CPPUNIT_ASSERT( !l.erase_with( 200, lt<value_type>() ));
 394
 395             {
 396                 erase_functor ef;
 397                 CPPUNIT_ASSERT( ef.nEraseCall == 0 );
 398                 CPPUNIT_ASSERT( l.erase_with( 160, lt<value_type>(), std::ref(ef) ));
 399                 CPPUNIT_ASSERT( ef.nEraseCall == 1 );
 400                 CPPUNIT_ASSERT( !l.erase_with( 160, lt<value_type>(), std::ref(ef) ));
 401                 CPPUNIT_ASSERT( ef.nEraseCall == 1 );
 402
 403                 CPPUNIT_ASSERT( l.erase( 250, std::ref(ef) ));
 404                 CPPUNIT_ASSERT( ef.nEraseCall == 2 );
 405                 CPPUNIT_ASSERT( !l.erase( 250, std::ref(ef) ));
 406                 CPPUNIT_ASSERT( ef.nEraseCall == 2 );
 407             }
 408
 409             CPPUNIT_ASSERT( l.erase( 50 ));
 410             CPPUNIT_ASSERT( !l.erase( 50 ));
 411
 412             CPPUNIT_ASSERT( l.empty() );
 413
 414             // clear empty list
 415             l.clear();
 416             CPPUNIT_ASSERT( l.empty() );
 417
 418             {
 419                 int i;
 420                 // insert test
 421                 CPPUNIT_ASSERT( l.emplace( 501 ) );
 422                 CPPUNIT_ASSERT( l.emplace( 251, 152 ));
 423                 CPPUNIT_ASSERT( l.emplace( item( 1001 )) );
 424
 425                 // insert failed - such key exists
 426                 CPPUNIT_ASSERT( !l.emplace( 501, 2 ) );
 427                 CPPUNIT_ASSERT( !l.emplace( 251, 10) );
 428
 429                 i = 501;
 430                 CPPUNIT_ASSERT( l.find( i, check_exact_value(501*2) ));
 431                 i = 251;
 432                 CPPUNIT_ASSERT( l.find( i, check_exact_value(152) ));
 433                 i = 1001;
 434                 CPPUNIT_ASSERT( l.find( i, check_exact_value(1001*2) ));
 435
 436                 l.clear();
 437                 CPPUNIT_ASSERT( l.empty() );
 438             }
 439
 440             // Iterator test
 441             {
 442                 int nCount = 100;
 443                 for ( int i = 0; i < nCount; ++i )
 444                     CPPUNIT_ASSERT( l.insert( i ) );
 445
 446                 {
 447                     typename OrdList::iterator it( l.begin() );
 448                     typename OrdList::const_iterator cit( l.cbegin() );
 449                     CPPUNIT_CHECK( it == cit );
 450                     CPPUNIT_CHECK( it != l.end() );
 451                     CPPUNIT_CHECK( it != l.cend() );
 452                     CPPUNIT_CHECK( cit != l.end() );
 453                     CPPUNIT_CHECK( cit != l.cend() );
 454                     ++it;
 455                     CPPUNIT_CHECK( it != cit );
 456                     CPPUNIT_CHECK( it != l.end() );
 457                     CPPUNIT_CHECK( it != l.cend() );
 458                     CPPUNIT_CHECK( cit != l.end() );
 459                     CPPUNIT_CHECK( cit != l.cend() );
 460                     ++cit;
 461                     CPPUNIT_CHECK( it == cit );
 462                     CPPUNIT_CHECK( it != l.end() );
 463                     CPPUNIT_CHECK( it != l.cend() );
 464                     CPPUNIT_CHECK( cit != l.end() );
 465                     CPPUNIT_CHECK( cit != l.cend() );
 466                 }
 467
 468                 int i = 0;
 469                 for ( typename OrdList::iterator it = l.begin(), itEnd = l.end(); it != itEnd; ++it, ++i ) {
 470                     it->nVal = i * 2;
 471                     CPPUNIT_ASSERT( it->nKey == i );
 472                 }
 473
 474                 // Check that we have visited all items
 475                 for ( int i = 0; i < nCount; ++i )
 476                     CPPUNIT_ASSERT( l.find( i, check_value(2) ));
 477
 478                 l.clear();
 479                 CPPUNIT_ASSERT( l.empty() );
 480
 481                 // Const iterator
 482                 for ( int i = 0; i < nCount; ++i )
 483                     CPPUNIT_ASSERT( l.insert(i) );
 484
 485                 i = 0;
 486                 const OrdList& rl = l;
 487                 for ( typename OrdList::const_iterator it = rl.begin(), itEnd = rl.end(); it != itEnd; ++it, ++i ) {
 488                     // it->nVal = i * 2    ;    // not!
 489                     CPPUNIT_ASSERT( it->nKey == i );
 490                 }
 491
 492                 // Check that we have visited all items
 493                 for ( int i = 0; i < nCount; ++i )
 494                     CPPUNIT_ASSERT( l.find_with( i, lt<value_type>(), check_value(2) ));
 495
 496                 l.clear();
 497                 CPPUNIT_ASSERT( l.empty() );
 498             }
 499         }
 500
 501         template <class OrdList>
 502         void test()
 503         {
 504             typedef typename OrdList::guarded_ptr guarded_ptr;
 505             typedef typename OrdList::value_type value_type;
 506
 507             OrdList l;
 508             test_with( l );
 509
 510             static int const nLimit = 20;
 511             int arr[nLimit];
 512             for ( int i = 0; i < nLimit; i++ )
 513                 arr[i] = i;
 514             shuffle( arr, arr + nLimit );
 515
 516             // extract/get
 517             for ( int i = 0; i < nLimit; ++i )
 518                 l.insert( arr[i] );
 519             {
 520                 guarded_ptr gp;
 521                 for ( int i = 0; i < nLimit; ++i ) {
 522                     int nKey = arr[i];
 523
 524                     gp = l.get( nKey );
 525                     CPPUNIT_ASSERT( gp );
 526                     CPPUNIT_ASSERT( !gp.empty());
 527                     CPPUNIT_CHECK( gp->nKey == nKey );
 528                     CPPUNIT_CHECK( gp->nVal == nKey * 2 );
 529                     gp.release();
 530
 531                     gp = l.extract( nKey );
 532                     CPPUNIT_ASSERT( gp );
 533                     CPPUNIT_ASSERT( !gp.empty());
 534                     CPPUNIT_CHECK( gp->nKey == nKey );
 535                     CPPUNIT_CHECK( gp->nVal == nKey*2 );
 536                     gp.release();
 537
 538                     gp = l.get( nKey );
 539                     CPPUNIT_CHECK( !gp );
 540                     CPPUNIT_CHECK( gp.empty());
 541                     CPPUNIT_CHECK( !l.extract( nKey));
 542                     CPPUNIT_CHECK( gp.empty());
 543                 }
 544                 CPPUNIT_ASSERT( l.empty());
 545                 CPPUNIT_CHECK( !l.get(arr[0]));
 546                 CPPUNIT_CHECK( gp.empty());
 547                 CPPUNIT_CHECK( !l.extract( arr[0]));
 548                 CPPUNIT_CHECK( gp.empty());
 549             }
 550
 551             // extract_with/get_with
 552             for ( int i = 0; i < nLimit; ++i )
 553                 l.insert( arr[i] );
 554             {
 555                 guarded_ptr gp;
 556                 for ( int i = 0; i < nLimit; ++i ) {
 557                     int nKey = arr[i];
 558                     other_item key( nKey );
 559
 560                     gp = l.get_with( key, other_less() );
 561                     CPPUNIT_ASSERT( gp );
 562                     CPPUNIT_ASSERT( !gp.empty());
 563                     CPPUNIT_CHECK( gp->nKey == nKey );
 564                     CPPUNIT_CHECK( gp->nVal == nKey * 2 );
 565                     gp.release();
 566
 567                     gp = l.extract_with( key, other_less() );
 568                     CPPUNIT_ASSERT( gp );
 569                     CPPUNIT_ASSERT( !gp.empty());
 570                     CPPUNIT_CHECK( gp->nKey == nKey );
 571                     CPPUNIT_CHECK( gp->nVal == nKey*2 );
 572                     gp.release();
 573
 574                     gp = l.get_with( key, other_less() );
 575                     CPPUNIT_CHECK( !gp );
 576                     CPPUNIT_CHECK( gp.empty());
 577                     CPPUNIT_CHECK( !l.extract_with( key, other_less()));
 578                     CPPUNIT_CHECK( gp.empty());
 579                 }
 580                 CPPUNIT_ASSERT( l.empty());
 581                 CPPUNIT_CHECK( !l.get_with(other_item(arr[0]), other_less()));
 582                 CPPUNIT_CHECK( gp.empty());
 583                 CPPUNIT_CHECK( !l.extract_with( other_item(arr[0]), other_less()));
 584                 CPPUNIT_CHECK( gp.empty());
 585             }
 586
 587         }
 588
 589         template <class OrdList>
 590         void test_rcu()
 591         {
 592             OrdList l;
 593             test_with( l );
 594
 595             static int const nLimit = 20;
 596
 597             typedef typename OrdList::rcu_lock rcu_lock;
 598             typedef typename OrdList::value_type value_type;
 599             typedef typename OrdList::gc rcu_type;
 600
 601             {
 602                 int a[nLimit];
 603                 for (int i = 0; i < nLimit; ++i)
 604                     a[i]=i;
 605                 shuffle( a, a + nLimit );
 606
 607                 // extract/get
 608                 for ( int i = 0; i < nLimit; ++i )
 609                     CPPUNIT_ASSERT( l.insert( a[i] ) );
 610
 611                 typename OrdList::exempt_ptr ep;
 612
 613                 for ( int i = 0; i < nLimit; ++i ) {
 614                     {
 615                         rcu_lock lock;
 616                         value_type * pGet = l.get( a[i] );
 617                         CPPUNIT_ASSERT( pGet != nullptr );
 618                         CPPUNIT_CHECK( pGet->nKey == a[i] );
 619                         CPPUNIT_CHECK( pGet->nVal == a[i] * 2 );
 620
 621                         ep = l.extract( a[i] );
 622                         CPPUNIT_ASSERT( ep );
 623                         CPPUNIT_ASSERT( !ep.empty() );
 624                         CPPUNIT_CHECK( ep->nKey == a[i] );
 625                         CPPUNIT_CHECK( (*ep).nVal == a[i] * 2 );
 626                     }
 627                     ep.release();
 628                     {
 629                         rcu_lock lock;
 630                         CPPUNIT_CHECK( l.get( a[i] ) == nullptr );
 631                         CPPUNIT_CHECK( !l.extract( a[i] ));
 632                     }
 633                 }
 634                 CPPUNIT_ASSERT( l.empty() );
 635
 636                 {
 637                     rcu_lock lock;
 638                     CPPUNIT_CHECK( l.get( a[0] ) == nullptr );
 639                     ep = l.extract( a[0] );
 640                     CPPUNIT_CHECK( !ep );
 641                     CPPUNIT_CHECK( ep.empty() );
 642                 }
 643
 644                 // extract_with/get_with
 645                 for ( int i = 0; i < nLimit; ++i ) {
 646                     CPPUNIT_ASSERT( l.insert( a[i] ) );
 647                 }
 648
 649                 for ( int i = 0; i < nLimit; ++i ) {
 650                     other_item itm( a[i] );
 651                     {
 652                         rcu_lock lock;
 653                         value_type * pGet = l.get_with( itm, other_less() );
 654                         CPPUNIT_ASSERT( pGet != nullptr );
 655                         CPPUNIT_CHECK( pGet->nKey == a[i] );
 656                         CPPUNIT_CHECK( pGet->nVal == a[i] * 2 );
 657
 658                         ep = l.extract_with( itm, other_less() );
 659                         CPPUNIT_ASSERT( ep );
 660                         CPPUNIT_ASSERT( !ep.empty() );
 661                         CPPUNIT_CHECK( ep->nKey == a[i] );
 662                         CPPUNIT_CHECK( ep->nVal == a[i] * 2 );
 663                     }
 664                     ep.release();
 665                     {
 666                         rcu_lock lock;
 667                         CPPUNIT_CHECK( l.get_with( itm, other_less() ) == nullptr );
 668                         ep = l.extract_with( itm, other_less() );
 669                         CPPUNIT_CHECK( !ep );
 670                         CPPUNIT_CHECK( ep.empty() );
 671                     }
 672                 }
 673                 CPPUNIT_ASSERT( l.empty() );
 674
 675                 {
 676                     rcu_lock lock;
 677                     CPPUNIT_CHECK( l.get_with( other_item( 0 ), other_less() ) == nullptr );
 678                     CPPUNIT_CHECK( !l.extract_with( other_item(0), other_less() ));
 679                     CPPUNIT_CHECK( ep.empty() );
 680                 }
 681             }
 682         }
 683
 684         template <class OrdList>
 685         void nogc_test()
 686         {
 687             typedef OrdList list;
 688             typedef typename list::value_type    value_type;
 689             typedef std::pair<typename list::iterator, bool> update_result;
 690
 691             typename list::iterator it;
 692
 693             list l;
 694             CPPUNIT_ASSERT( l.empty() );
 695             CPPUNIT_ASSERT( l.insert(50) != l.end() );
 696             CPPUNIT_ASSERT( !l.empty() );
 697
 698             update_result eres = l.update( item(100, 33) );
 699             CPPUNIT_ASSERT( eres.second );
 700             CPPUNIT_ASSERT( eres.first != l.end() );
 701             CPPUNIT_ASSERT( l.insert( item(150) ) != l.end() );
 702
 703             CPPUNIT_ASSERT( l.insert(100) == l.end() );
 704             eres = l.update( item(50, 33) );
 705             CPPUNIT_ASSERT( !eres.second );
 706             CPPUNIT_ASSERT( eres.first->nVal == eres.first->nKey * 2 );
 707             eres.first->nVal = 63;
 708
 709             it = l.contains( 33 );
 710             CPPUNIT_ASSERT( it == l.end() );
 711
 712             it = l.contains( 50 );
 713             CPPUNIT_ASSERT( it != l.end() );
 714             CPPUNIT_ASSERT( it->nKey == 50 );
 715             CPPUNIT_ASSERT( it->nVal == 63 );
 716
 717             it = l.contains( 100 );
 718             CPPUNIT_ASSERT( it != l.end() );
 719             CPPUNIT_ASSERT( it->nKey == 100 );
 720             CPPUNIT_ASSERT( it->nVal == 33 );
 721
 722             it = l.contains( 150, lt<value_type>() );
 723             CPPUNIT_ASSERT( it != l.end() );
 724             CPPUNIT_ASSERT( it->nKey == 150 );
 725             CPPUNIT_ASSERT( it->nVal == it->nKey * 2 );
 726
 727             CPPUNIT_ASSERT( !l.empty() );
 728             l.clear();
 729             CPPUNIT_ASSERT( l.empty() );
 730
 731             // insert test
 732             CPPUNIT_ASSERT( l.emplace( 501 ) != l.end());
 733             CPPUNIT_ASSERT( l.emplace( 251, 152 ) != l.end());
 734             CPPUNIT_ASSERT( l.emplace( item( 1001 )) != l.end());
 735
 736             // insert failed - such key exists
 737             CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end());
 738             CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end());
 739
 740             it = l.contains( 501 );
 741             CPPUNIT_ASSERT( it != l.end() );
 742             CPPUNIT_ASSERT( it->nKey == 501 );
 743             CPPUNIT_ASSERT( it->nVal == 501 * 2 );
 744
 745             it = l.contains( 251, lt<value_type>() );
 746             CPPUNIT_ASSERT( it != l.end() );
 747             CPPUNIT_ASSERT( it->nKey == 251 );
 748             CPPUNIT_ASSERT( it->nVal == 152 );
 749
 750             it = l.contains( 1001 );
 751             CPPUNIT_ASSERT( it != l.end() );
 752             CPPUNIT_ASSERT( it->nKey == 1001 );
 753             CPPUNIT_ASSERT( it->nVal == 1001 * 2 );
 754
 755             {
 756                 typename OrdList::iterator it( l.begin() );
 757                 typename OrdList::const_iterator cit( l.cbegin() );
 758                 CPPUNIT_CHECK( it == cit );
 759                 CPPUNIT_CHECK( it != l.end() );
 760                 CPPUNIT_CHECK( it != l.cend() );
 761                 CPPUNIT_CHECK( cit != l.end() );
 762                 CPPUNIT_CHECK( cit != l.cend() );
 763                 ++it;
 764                 CPPUNIT_CHECK( it != cit );
 765                 CPPUNIT_CHECK( it != l.end() );
 766                 CPPUNIT_CHECK( it != l.cend() );
 767                 CPPUNIT_CHECK( cit != l.end() );
 768                 CPPUNIT_CHECK( cit != l.cend() );
 769                 ++cit;
 770                 CPPUNIT_CHECK( it == cit );
 771                 CPPUNIT_CHECK( it != l.end() );
 772                 CPPUNIT_CHECK( it != l.cend() );
 773                 CPPUNIT_CHECK( cit != l.end() );
 774                 CPPUNIT_CHECK( cit != l.cend() );
 775             }
 776
 777
 778             l.clear();
 779             CPPUNIT_ASSERT( l.empty() );
 780         }
 781
 782         template <class UnordList>
 783         void nogc_unord_test()
 784         {
 785             typedef UnordList list;
 786             typedef typename list::value_type    value_type;
 787             typedef std::pair<typename list::iterator, bool> update_result;
 788
 789             typename list::iterator it;
 790
 791             list l;
 792             CPPUNIT_ASSERT( l.empty() );
 793             CPPUNIT_ASSERT( l.insert(50) != l.end() );
 794             CPPUNIT_ASSERT( !l.empty() );
 795
 796             update_result eres = l.update( item(100, 33) );
 797             CPPUNIT_ASSERT( eres.second );
 798             CPPUNIT_ASSERT( eres.first != l.end() );
 799             CPPUNIT_ASSERT( l.insert( item(150) ) != l.end() );
 800
 801             CPPUNIT_ASSERT( l.insert(100) == l.end() );
 802             eres = l.update( item(50, 33) );
 803             CPPUNIT_ASSERT( !eres.second );
 804             CPPUNIT_ASSERT( eres.first->nVal == eres.first->nKey * 2 );
 805             eres.first->nVal = 63;
 806
 807             it = l.contains( 33 );
 808             CPPUNIT_ASSERT( it == l.end() );
 809
 810             it = l.contains( 50 );
 811             CPPUNIT_ASSERT( it != l.end() );
 812             CPPUNIT_ASSERT( it->nKey == 50 );
 813             CPPUNIT_ASSERT( it->nVal == 63 );
 814
 815             it = l.contains( 100 );
 816             CPPUNIT_ASSERT( it != l.end() );
 817             CPPUNIT_ASSERT( it->nKey == 100 );
 818             CPPUNIT_ASSERT( it->nVal == 33 );
 819
 820             it = l.contains( 150, equal_to<value_type>() );
 821             CPPUNIT_ASSERT( it != l.end() );
 822             CPPUNIT_ASSERT( it->nKey == 150 );
 823             CPPUNIT_ASSERT( it->nVal == it->nKey * 2 );
 824
 825             CPPUNIT_ASSERT( !l.empty() );
 826             l.clear();
 827             CPPUNIT_ASSERT( l.empty() );
 828
 829             // insert test
 830             CPPUNIT_ASSERT( l.emplace( 501 ) != l.end());
 831             CPPUNIT_ASSERT( l.emplace( 251, 152 ) != l.end());
 832             CPPUNIT_ASSERT( l.emplace( item( 1001 )) != l.end());
 833
 834             // insert failed - such key exists
 835             CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end());
 836             CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end());
 837
 838             it = l.contains( 501 );
 839             CPPUNIT_ASSERT( it != l.end() );
 840             CPPUNIT_ASSERT( it->nKey == 501 );
 841             CPPUNIT_ASSERT( it->nVal == 501 * 2 );
 842
 843             it = l.contains( 1001 );
 844             CPPUNIT_ASSERT( it != l.end() );
 845             CPPUNIT_ASSERT( it->nKey == 1001 );
 846             CPPUNIT_ASSERT( it->nVal == 1001 * 2 );
 847
 848             {
 849                 typename UnordList::iterator it( l.begin() );
 850                 typename UnordList::const_iterator cit( l.cbegin() );
 851                 CPPUNIT_CHECK( it == cit );
 852                 CPPUNIT_CHECK( it != l.end() );
 853                 CPPUNIT_CHECK( it != l.cend() );
 854                 CPPUNIT_CHECK( cit != l.end() );
 855                 CPPUNIT_CHECK( cit != l.cend() );
 856                 ++it;
 857                 CPPUNIT_CHECK( it != cit );
 858                 CPPUNIT_CHECK( it != l.end() );
 859                 CPPUNIT_CHECK( it != l.cend() );
 860                 CPPUNIT_CHECK( cit != l.end() );
 861                 CPPUNIT_CHECK( cit != l.cend() );
 862                 ++cit;
 863                 CPPUNIT_CHECK( it == cit );
 864                 CPPUNIT_CHECK( it != l.end() );
 865                 CPPUNIT_CHECK( it != l.cend() );
 866                 CPPUNIT_CHECK( cit != l.end() );
 867                 CPPUNIT_CHECK( cit != l.cend() );
 868             }
 869
 870
 871             l.clear();
 872             CPPUNIT_ASSERT( l.empty() );
 873         }
 874
 875         void HP_cmp();
 876         void HP_less();
 877         void HP_cmpmix();
 878         void HP_ic();
 879
 880         void DHP_cmp();
 881         void DHP_less();
 882         void DHP_cmpmix();
 883         void DHP_ic();
 884
 885         void RCU_GPI_cmp();
 886         void RCU_GPI_less();
 887         void RCU_GPI_cmpmix();
 888         void RCU_GPI_ic();
 889
 890         void RCU_GPB_cmp();
 891         void RCU_GPB_less();
 892         void RCU_GPB_cmpmix();
 893         void RCU_GPB_ic();
 894
 895         void RCU_GPT_cmp();
 896         void RCU_GPT_less();
 897         void RCU_GPT_cmpmix();
 898         void RCU_GPT_ic();
 899
 900         void RCU_SHB_cmp();
 901         void RCU_SHB_less();
 902         void RCU_SHB_cmpmix();
 903         void RCU_SHB_ic();
 904
 905         void RCU_SHT_cmp();
 906         void RCU_SHT_less();
 907         void RCU_SHT_cmpmix();
 908         void RCU_SHT_ic();
 909
 910         void NOGC_cmp();
 911         void NOGC_less();
 912         void NOGC_cmpmix();
 913         void NOGC_ic();
 914
 915         void NOGC_cmp_unord();
 916         void NOGC_less_unord();
 917         void NOGC_equal_to_unord();
 918         void NOGC_cmpmix_unord();
 919         void NOGC_equal_to_mix_unord();
 920         void NOGC_ic_unord();
 921
 922
 923         CPPUNIT_TEST_SUITE(LazyListTestHeader)
 924             CPPUNIT_TEST(HP_cmp)
 925             CPPUNIT_TEST(HP_less)
 926             CPPUNIT_TEST(HP_cmpmix)
 927             CPPUNIT_TEST(HP_ic)
 928
 929             CPPUNIT_TEST(DHP_cmp)
 930             CPPUNIT_TEST(DHP_less)
 931             CPPUNIT_TEST(DHP_cmpmix)
 932             CPPUNIT_TEST(DHP_ic)
 933
 934             CPPUNIT_TEST(RCU_GPI_cmp)
 935             CPPUNIT_TEST(RCU_GPI_less)
 936             CPPUNIT_TEST(RCU_GPI_cmpmix)
 937             CPPUNIT_TEST(RCU_GPI_ic)
 938
 939             CPPUNIT_TEST(RCU_GPB_cmp)
 940             CPPUNIT_TEST(RCU_GPB_less)
 941             CPPUNIT_TEST(RCU_GPB_cmpmix)
 942             CPPUNIT_TEST(RCU_GPB_ic)
 943
 944             CPPUNIT_TEST(RCU_GPT_cmp)
 945             CPPUNIT_TEST(RCU_GPT_less)
 946             CPPUNIT_TEST(RCU_GPT_cmpmix)
 947             CPPUNIT_TEST(RCU_GPT_ic)
 948
 949             CPPUNIT_TEST(RCU_SHB_cmp)
 950             CPPUNIT_TEST(RCU_SHB_less)
 951             CPPUNIT_TEST(RCU_SHB_cmpmix)
 952             CPPUNIT_TEST(RCU_SHB_ic)
 953
 954             CPPUNIT_TEST(RCU_SHT_cmp)
 955             CPPUNIT_TEST(RCU_SHT_less)
 956             CPPUNIT_TEST(RCU_SHT_cmpmix)
 957             CPPUNIT_TEST(RCU_SHT_ic)
 958
 959             CPPUNIT_TEST(NOGC_cmp)
 960             CPPUNIT_TEST(NOGC_less)
 961             CPPUNIT_TEST(NOGC_cmpmix)
 962             CPPUNIT_TEST(NOGC_ic)
 963
 964             CPPUNIT_TEST(NOGC_cmp_unord)
 965             CPPUNIT_TEST(NOGC_less_unord)
 966             CPPUNIT_TEST(NOGC_equal_to_unord)
 967             CPPUNIT_TEST(NOGC_cmpmix_unord)
 968             CPPUNIT_TEST(NOGC_equal_to_mix_unord)
 969             CPPUNIT_TEST(NOGC_ic_unord)
 970
 971         CPPUNIT_TEST_SUITE_END()
 972     };
 973
 974 }   // namespace ordlist
 975
 976 #endif // #ifndef CDSTEST_HDR_LAZY_H