tests/test-hdr/list/hdr_lazy.h

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