tests/test-hdr/ordered_list/hdr_michael.h

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