tests/test-hdr/ordered_list/hdr_michael.h

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