tests/test-hdr/ordered_list/hdr_michael_kv.h

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