tests/test-hdr/list/hdr_michael_kv.h

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