tests/test-hdr/ordered_list/hdr_michael_kv.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 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, std::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>(), std::ref( chk ) ) );
 130             chk.m_nExpected = 0;
 131             CPPUNIT_ASSERT( l.find_with( 100, lt<key_type>(), std::ref( chk ) ) );
 132             CPPUNIT_ASSERT( !l.empty() );
 133
 134             CPPUNIT_ASSERT( !l.find( 150 ));
 135             CPPUNIT_ASSERT( l.insert_with( 150, insert_functor() ));
 136             CPPUNIT_ASSERT( l.find( 150 ));
 137             chk.m_nExpected = 1500;
 138             CPPUNIT_ASSERT( l.find( 150, std::ref( chk ) ) );
 139             chk.m_nExpected = 0;
 140             CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) );
 141             chk.m_nExpected = 500;
 142             CPPUNIT_ASSERT( l.find( 50, std::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, std::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, std::ref( chk ) ) );
 166
 167             {
 168                 ensure_functor ef;
 169                 bEnsureResult = l.ensure( 50, std::ref( ef ) );
 170             }
 171             CPPUNIT_ASSERT( bEnsureResult.first );
 172             CPPUNIT_ASSERT( bEnsureResult.second );
 173             chk.m_nExpected = 2500;
 174             CPPUNIT_ASSERT( l.find( 50, std::ref( chk ) ) );
 175
 176             // erase test
 177             CPPUNIT_ASSERT( !l.empty() );
 178             CPPUNIT_ASSERT( l.insert_with( 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>(), std::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             // insert test
 197             CPPUNIT_ASSERT( l.emplace( 501 ) );
 198             CPPUNIT_ASSERT( l.emplace( 251, 152 ));
 199
 200             // insert failed - such key exists
 201             CPPUNIT_ASSERT( !l.emplace( 501, 2 ) );
 202             CPPUNIT_ASSERT( !l.emplace( 251, 10) );
 203
 204             check_value cv(0);
 205             CPPUNIT_ASSERT( l.find( 501, std::ref(cv) ));
 206             cv.m_nExpected = 152;
 207             CPPUNIT_ASSERT( l.find( 251, std::ref(cv) ));
 208
 209             l.clear();
 210             CPPUNIT_ASSERT( l.empty() );
 211
 212             // Iterator test
 213             {
 214                 int nCount = 100;
 215                 for ( int i = 0; i < nCount; ++i )
 216                     CPPUNIT_ASSERT( l.insert(i, i * 2 ) );
 217
 218                 {
 219                     typename OrdList::iterator it( l.begin() );
 220                     typename OrdList::const_iterator cit( l.cbegin() );
 221                     CPPUNIT_CHECK( it == cit );
 222                     CPPUNIT_CHECK( it != l.end() );
 223                     CPPUNIT_CHECK( it != l.cend() );
 224                     CPPUNIT_CHECK( cit != l.end() );
 225                     CPPUNIT_CHECK( cit != l.cend() );
 226                     ++it;
 227                     CPPUNIT_CHECK( it != cit );
 228                     CPPUNIT_CHECK( it != l.end() );
 229                     CPPUNIT_CHECK( it != l.cend() );
 230                     CPPUNIT_CHECK( cit != l.end() );
 231                     CPPUNIT_CHECK( cit != l.cend() );
 232                     ++cit;
 233                     CPPUNIT_CHECK( it == cit );
 234                     CPPUNIT_CHECK( it != l.end() );
 235                     CPPUNIT_CHECK( it != l.cend() );
 236                     CPPUNIT_CHECK( cit != l.end() );
 237                     CPPUNIT_CHECK( cit != l.cend() );
 238                 }
 239
 240                 int i = 0;
 241                 for ( typename OrdList::iterator it = l.begin(), itEnd = l.end(); it != itEnd; ++it, ++i ) {
 242                     CPPUNIT_ASSERT( it.key() == i );
 243                     CPPUNIT_ASSERT( it->first == i );
 244                     CPPUNIT_ASSERT( (*it).first == i );
 245
 246                     CPPUNIT_ASSERT( it.val().m_val == i * 2 );
 247                     CPPUNIT_ASSERT( it->second.m_val == i * 2 );
 248                     CPPUNIT_ASSERT( (*it).second.m_val == i * 2 );
 249                     it.val().m_val = i * 3;
 250                 }
 251
 252                 // Check that we have visited all items
 253                 for ( int i = 0; i < nCount; ++i ) {
 254                     chk.m_nExpected = i * 3;
 255                     CPPUNIT_ASSERT( l.find( i, std::ref( chk ) ) );
 256                 }
 257
 258                 l.clear();
 259                 CPPUNIT_ASSERT( l.empty() );
 260
 261                 // Const iterator
 262                 for ( int i = 0; i < nCount; ++i )
 263                     CPPUNIT_ASSERT( l.insert(i, i * 7) );
 264
 265                 i = 0;
 266                 const OrdList& rl = l;
 267                 for ( typename OrdList::const_iterator it = rl.begin(), itEnd = rl.end(); it != itEnd; ++it, ++i ) {
 268                     CPPUNIT_ASSERT( it.key() == i );
 269                     CPPUNIT_ASSERT( it->first == i );
 270                     CPPUNIT_ASSERT( (*it).first == i );
 271
 272                     CPPUNIT_ASSERT( it.val().m_val == i * 7 );
 273                     CPPUNIT_ASSERT( it->second.m_val == i * 7 );
 274                     CPPUNIT_ASSERT( (*it).second.m_val == i * 7 );
 275                 }
 276
 277                 // Check that we have visited all items
 278                 for ( int i = 0; i < nCount; ++i ) {
 279                     chk.m_nExpected = i * 7;
 280                     CPPUNIT_ASSERT( l.find_with( i, lt<key_type>(), std::ref( chk ) ) );
 281                 }
 282
 283                 l.clear();
 284                 CPPUNIT_ASSERT( l.empty() );
 285             }
 286         }
 287
 288         template <class OrdList>
 289         void test()
 290         {
 291             OrdList l;
 292             test_with(l);
 293
 294             typedef typename OrdList::guarded_ptr guarded_ptr;
 295
 296             static int const nLimit = 20;
 297             int arr[nLimit];
 298             for ( int i = 0; i < nLimit; i++ )
 299                 arr[i] = i;
 300             std::random_shuffle( arr, arr + nLimit );
 301
 302             // extract/get
 303             for ( int i = 0; i < nLimit; ++i )
 304                 l.insert( arr[i], arr[i] * 2 );
 305             {
 306                 guarded_ptr gp;
 307                 for ( int i = 0; i < nLimit; ++i ) {
 308                     int nKey = arr[i];
 309
 310                     gp = l.get( nKey );
 311                     CPPUNIT_ASSERT( gp );
 312                     CPPUNIT_ASSERT( !gp.empty());
 313                     CPPUNIT_CHECK( gp->first == nKey );
 314                     CPPUNIT_CHECK( gp->second.m_val == nKey * 2 );
 315                     gp.release();
 316                     CPPUNIT_CHECK( gp.empty() );
 317
 318                     gp = l.extract( nKey );
 319                     CPPUNIT_ASSERT( gp );
 320                     CPPUNIT_ASSERT( !gp.empty());
 321                     CPPUNIT_CHECK( gp->first == nKey );
 322                     CPPUNIT_CHECK( gp->second.m_val == nKey*2 );
 323                     gp.release();
 324
 325                     gp = l.get( nKey );
 326                     CPPUNIT_CHECK( !gp );
 327                     CPPUNIT_CHECK( gp.empty());
 328                     CPPUNIT_CHECK( !l.extract( nKey));
 329                     CPPUNIT_CHECK( gp.empty());
 330                 }
 331                 CPPUNIT_ASSERT( l.empty());
 332                 CPPUNIT_CHECK( !l.get(arr[0]));
 333                 CPPUNIT_CHECK( gp.empty());
 334                 CPPUNIT_CHECK( !l.extract( arr[0]));
 335                 CPPUNIT_CHECK( gp.empty());
 336             }
 337
 338             // extract_with/get_with
 339             for ( int i = 0; i < nLimit; ++i )
 340                 l.insert( arr[i], arr[i] * 2 );
 341             {
 342                 guarded_ptr gp;
 343                 for ( int i = 0; i < nLimit; ++i ) {
 344                     int nKey = arr[i];
 345                     other_key key = float(nKey + 0.3);
 346
 347                     gp = l.get_with( key, other_less() );
 348                     CPPUNIT_ASSERT( gp );
 349                     CPPUNIT_ASSERT( !gp.empty());
 350                     CPPUNIT_CHECK( gp->first == nKey );
 351                     CPPUNIT_CHECK( gp->second.m_val == nKey * 2 );
 352                     gp.release();
 353
 354                     gp = l.extract_with( key, other_less() );
 355                     CPPUNIT_ASSERT( gp );
 356                     CPPUNIT_ASSERT( !gp.empty());
 357                     CPPUNIT_CHECK( gp->first == nKey );
 358                     CPPUNIT_CHECK( gp->second.m_val == nKey*2 );
 359                     gp.release();
 360
 361                     gp = l.get_with( key, other_less() );
 362                     CPPUNIT_CHECK( !gp );
 363                     CPPUNIT_CHECK( gp.empty());
 364                     CPPUNIT_CHECK( !l.extract_with( key, other_less()));
 365                     CPPUNIT_CHECK( gp.empty());
 366                 }
 367                 CPPUNIT_ASSERT( l.empty());
 368                 CPPUNIT_CHECK( !l.get_with( 3.4f, other_less()));
 369                 CPPUNIT_CHECK( gp.empty());
 370                 CPPUNIT_CHECK( !l.extract_with( 3.4f, other_less()));
 371                 CPPUNIT_CHECK( gp.empty());
 372             }
 373         }
 374
 375         template <class OrdList>
 376         void test_rcu()
 377         {
 378             OrdList l;
 379             test_with(l);
 380
 381             static int const nLimit = 20;
 382
 383             typedef typename OrdList::rcu_lock rcu_lock;
 384             typedef typename OrdList::value_type value_type;
 385             typedef typename OrdList::gc rcu_type;
 386
 387             {
 388                 int a[nLimit];
 389                 for (int i = 0; i < nLimit; ++i)
 390                     a[i]=i;
 391                 std::random_shuffle( a, a + nLimit );
 392
 393                 // extract/get
 394                 for ( int i = 0; i < nLimit; ++i )
 395                     CPPUNIT_ASSERT( l.insert( a[i], a[i]*2 ) );
 396
 397                 typename OrdList::exempt_ptr ep;
 398
 399                 for ( int i = 0; i < nLimit; ++i ) {
 400                     {
 401                         rcu_lock lock;
 402                         value_type * pGet = l.get( a[i] );
 403                         CPPUNIT_ASSERT( pGet != nullptr );
 404                         CPPUNIT_CHECK( pGet->first == a[i] );
 405                         CPPUNIT_CHECK( pGet->second.m_val == a[i] * 2 );
 406
 407                         ep = l.extract( a[i] );
 408                         CPPUNIT_ASSERT( ep );
 409                         CPPUNIT_ASSERT( !ep.empty() );
 410                         CPPUNIT_CHECK( ep->first == a[i] );
 411                         CPPUNIT_CHECK( (*ep).second.m_val == a[i] * 2 );
 412                     }
 413                     ep.release();
 414                     {
 415                         rcu_lock lock;
 416                         CPPUNIT_CHECK( l.get( a[i] ) == nullptr );
 417                         ep = l.extract( a[i] );
 418                         CPPUNIT_CHECK( !ep );
 419                         CPPUNIT_CHECK( ep.empty() );
 420                     }
 421                 }
 422                 CPPUNIT_ASSERT( l.empty() );
 423
 424                 {
 425                     rcu_lock lock;
 426                     CPPUNIT_CHECK( l.get( a[0] ) == nullptr );
 427                     CPPUNIT_CHECK( !l.extract( a[0] ) );
 428                     CPPUNIT_CHECK( ep.empty() );
 429                 }
 430
 431                 // extract_with/get_with
 432                 for ( int i = 0; i < nLimit; ++i ) {
 433                     CPPUNIT_ASSERT( l.insert( a[i], a[i]*2 ) );
 434                 }
 435
 436                 for ( int i = 0; i < nLimit; ++i ) {
 437                     float itm = a[i] + 0.3f;
 438                     {
 439                         rcu_lock lock;
 440                         value_type * pGet = l.get_with( itm, other_less() );
 441                         CPPUNIT_ASSERT( pGet != nullptr );
 442                         CPPUNIT_CHECK( pGet->first == a[i] );
 443                         CPPUNIT_CHECK( pGet->second.m_val == a[i] * 2 );
 444
 445                         ep = l.extract_with( itm, other_less() );
 446                         CPPUNIT_ASSERT( ep );
 447                         CPPUNIT_ASSERT( !ep.empty() );
 448                         CPPUNIT_CHECK( ep->first == a[i] );
 449                         CPPUNIT_CHECK( ep->second.m_val == a[i] * 2 );
 450                     }
 451                     ep.release();
 452                     {
 453                         rcu_lock lock;
 454                         CPPUNIT_CHECK( l.get_with( itm, other_less() ) == nullptr );
 455                         ep = l.extract_with( itm, other_less() );
 456                         CPPUNIT_CHECK( !ep );
 457                         CPPUNIT_CHECK( ep.empty() );
 458                     }
 459                 }
 460                 CPPUNIT_ASSERT( l.empty() );
 461
 462                 {
 463                     rcu_lock lock;
 464                     CPPUNIT_CHECK( l.get_with( 3.14f, other_less() ) == nullptr );
 465                     CPPUNIT_CHECK( !l.extract_with( 3.14f, other_less() ));
 466                     CPPUNIT_CHECK( ep.empty() );
 467                 }
 468             }
 469
 470         }
 471
 472         template <class OrdList>
 473         void nogc_test()
 474         {
 475             typedef typename OrdList::value_type    value_type;
 476             typedef typename OrdList::iterator      iterator;
 477
 478             {
 479                 OrdList l;
 480                 iterator it;
 481
 482                 CPPUNIT_ASSERT( l.empty() );
 483
 484                 // insert / find test
 485                 CPPUNIT_ASSERT( l.find( 100 ) == l.end() );
 486                 CPPUNIT_ASSERT( l.insert( 100 ) != l.end() );
 487                 CPPUNIT_ASSERT( !l.empty() );
 488                 it = l.find_with( 100, lt<key_type>() );
 489                 CPPUNIT_ASSERT( it != l.end() );
 490                 CPPUNIT_ASSERT( it.key() == 100 );
 491                 CPPUNIT_ASSERT( it.val().m_val == 0 );
 492
 493                 CPPUNIT_ASSERT( l.find_with( 50, lt<key_type>() ) == l.end() );
 494                 CPPUNIT_ASSERT( l.insert( 50, 500 ) != l.end());
 495                 it = l.find( 50 );
 496                 CPPUNIT_ASSERT( it != l.end() );
 497                 CPPUNIT_ASSERT( it.key() == 50 );
 498                 CPPUNIT_ASSERT( it.val().m_val == 500 );
 499
 500                 CPPUNIT_ASSERT( l.insert( 50, 5 ) == l.end() );
 501                 it = l.find( 50 );
 502                 CPPUNIT_ASSERT( it != l.end() );
 503                 CPPUNIT_ASSERT( it.key() == 50 );
 504                 CPPUNIT_ASSERT( it.val().m_val == 500 );
 505                 CPPUNIT_ASSERT( !l.empty() );
 506
 507                 CPPUNIT_ASSERT( l.find( 150 ) == l.end() );
 508                 CPPUNIT_ASSERT( l.insert_with( 150, insert_functor() ) != l.end() );
 509                 it = l.find( 150 );
 510                 CPPUNIT_ASSERT( it != l.end() );
 511                 CPPUNIT_ASSERT( it.key() == 150 );
 512                 CPPUNIT_ASSERT( it.val().m_val == 1500 );
 513                 it = l.find( 100 );
 514                 CPPUNIT_ASSERT( it != l.end() );
 515                 CPPUNIT_ASSERT( it.key() == 100 );
 516                 CPPUNIT_ASSERT( it.val().m_val == 0 );
 517                 it = l.find( 50 );
 518                 CPPUNIT_ASSERT( it != l.end() );
 519                 CPPUNIT_ASSERT( it.key() == 50 );
 520                 CPPUNIT_ASSERT( it.val().m_val == 500 );
 521                 it.val().m_val = 25;
 522                 it = l.find( 50 );
 523                 CPPUNIT_ASSERT( it != l.end() );
 524                 CPPUNIT_ASSERT( it.key() == 50 );
 525                 CPPUNIT_ASSERT( it.val().m_val == 25 );
 526                 CPPUNIT_ASSERT( !l.empty() );
 527
 528                 // ensure existing item
 529                 std::pair<iterator, bool> ensureResult;
 530                 ensureResult = l.ensure( 100 );
 531                 CPPUNIT_ASSERT( !ensureResult.second );
 532                 CPPUNIT_ASSERT( ensureResult.first.key() == 100 );
 533                 CPPUNIT_ASSERT( ensureResult.first.val().m_val == 0   );
 534                 ensureResult.first.val().m_val = 5;
 535                 it = l.find( 100 );
 536                 CPPUNIT_ASSERT( it != l.end() );
 537                 CPPUNIT_ASSERT( it.key() == 100 );
 538                 CPPUNIT_ASSERT( it.val().m_val == 5 );
 539
 540                 CPPUNIT_ASSERT( !l.empty() );
 541
 542                 // ensure new item
 543                 ensureResult = l.ensure( 1000 );
 544                 CPPUNIT_ASSERT( ensureResult.second );
 545                 CPPUNIT_ASSERT( ensureResult.first.key() == 1000 );
 546                 CPPUNIT_ASSERT( ensureResult.first.val().m_val == 0   );
 547                 ensureResult.first.val().m_val = 33;
 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 == 33   );
 552
 553                 // clear test
 554                 l.clear();
 555                 CPPUNIT_ASSERT( l.empty() );
 556
 557                 // insert test
 558                 CPPUNIT_ASSERT( l.emplace( 501 ) != l.end());
 559                 CPPUNIT_ASSERT( l.emplace( 251, 152 ) != l.end());
 560
 561                 // insert failed - such key exists
 562                 CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end());
 563                 CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end());
 564
 565                 it = l.find( 501 );
 566                 CPPUNIT_ASSERT( it != l.end());
 567                 CPPUNIT_ASSERT( it.key() == 501 );
 568                 CPPUNIT_ASSERT( it.val().m_val == 0 );
 569
 570                 it = l.find( 251 );
 571                 CPPUNIT_ASSERT( it != l.end());
 572                 CPPUNIT_ASSERT( it.key() == 251 );
 573                 CPPUNIT_ASSERT( it.val().m_val == 152 );
 574
 575                 l.clear();
 576                 CPPUNIT_ASSERT( l.empty() );
 577
 578                 // Iterator test
 579                 {
 580                     int nCount = 100;
 581                     for ( int i = 0; i < nCount; ++i )
 582                         CPPUNIT_ASSERT( l.insert(i, i * 2 ) != l.end() );
 583
 584                     {
 585                         typename OrdList::iterator it( l.begin() );
 586                         typename OrdList::const_iterator cit( l.cbegin() );
 587                         CPPUNIT_CHECK( it == cit );
 588                         CPPUNIT_CHECK( it != l.end() );
 589                         CPPUNIT_CHECK( it != l.cend() );
 590                         CPPUNIT_CHECK( cit != l.end() );
 591                         CPPUNIT_CHECK( cit != l.cend() );
 592                         ++it;
 593                         CPPUNIT_CHECK( it != cit );
 594                         CPPUNIT_CHECK( it != l.end() );
 595                         CPPUNIT_CHECK( it != l.cend() );
 596                         CPPUNIT_CHECK( cit != l.end() );
 597                         CPPUNIT_CHECK( cit != l.cend() );
 598                         ++cit;
 599                         CPPUNIT_CHECK( it == cit );
 600                         CPPUNIT_CHECK( it != l.end() );
 601                         CPPUNIT_CHECK( it != l.cend() );
 602                         CPPUNIT_CHECK( cit != l.end() );
 603                         CPPUNIT_CHECK( cit != l.cend() );
 604                     }
 605
 606                     int i = 0;
 607                     for ( typename OrdList::iterator iter = l.begin(), itEnd = l.end(); iter != itEnd; ++iter, ++i ) {
 608                         CPPUNIT_ASSERT( iter.key() == i );
 609                         CPPUNIT_ASSERT( iter->first == i );
 610                         CPPUNIT_ASSERT( (*iter).first == i );
 611
 612                         CPPUNIT_ASSERT( iter.val().m_val == i * 2 );
 613                         CPPUNIT_ASSERT( iter->second.m_val == i * 2 );
 614                         CPPUNIT_ASSERT( (*iter).second.m_val == i * 2 );
 615
 616                         iter.val().m_val = i * 3;
 617                     }
 618
 619                     // Check that we have visited all items
 620                     for ( int i = 0; i < nCount; ++i ) {
 621                         it = l.find( i );
 622                         CPPUNIT_ASSERT( it != l.end() );
 623                         CPPUNIT_ASSERT( it.key() == i );
 624                         CPPUNIT_ASSERT( it.val().m_val == i * 3 );
 625                     }
 626
 627                     l.clear();
 628                     CPPUNIT_ASSERT( l.empty() );
 629
 630                     // Const iterator
 631                     for ( int i = 0; i < nCount; ++i )
 632                         CPPUNIT_ASSERT( l.insert(i, i * 7) != l.end() );
 633
 634                     i = 0;
 635                     const OrdList& rl = l;
 636                     for ( typename OrdList::const_iterator iter = rl.begin(), itEnd = rl.end(); iter != itEnd; ++iter, ++i ) {
 637                         CPPUNIT_ASSERT( iter.key() == i );
 638                         CPPUNIT_ASSERT( iter->first == i );
 639                         CPPUNIT_ASSERT( (*iter).first == i );
 640
 641                         CPPUNIT_ASSERT( iter.val().m_val == i * 7 );
 642                         CPPUNIT_ASSERT( iter->second.m_val == i * 7 );
 643                         CPPUNIT_ASSERT( (*iter).second.m_val == i * 7 );
 644
 645                         // it.val().m_val = i * 3    ; // error: const-iterator
 646                     }
 647
 648                     l.clear();
 649                     CPPUNIT_ASSERT( l.empty() );
 650                 }
 651
 652             }
 653         }
 654
 655         void HP_cmp();
 656         void HP_less();
 657         void HP_cmpmix();
 658         void HP_ic();
 659
 660         void DHP_cmp();
 661         void DHP_less();
 662         void DHP_cmpmix();
 663         void DHP_ic();
 664
 665         void RCU_GPI_cmp();
 666         void RCU_GPI_less();
 667         void RCU_GPI_cmpmix();
 668         void RCU_GPI_ic();
 669
 670         void RCU_GPB_cmp();
 671         void RCU_GPB_less();
 672         void RCU_GPB_cmpmix();
 673         void RCU_GPB_ic();
 674
 675         void RCU_GPT_cmp();
 676         void RCU_GPT_less();
 677         void RCU_GPT_cmpmix();
 678         void RCU_GPT_ic();
 679
 680         void RCU_SHB_cmp();
 681         void RCU_SHB_less();
 682         void RCU_SHB_cmpmix();
 683         void RCU_SHB_ic();
 684
 685         void RCU_SHT_cmp();
 686         void RCU_SHT_less();
 687         void RCU_SHT_cmpmix();
 688         void RCU_SHT_ic();
 689
 690         void NOGC_cmp();
 691         void NOGC_less();
 692         void NOGC_cmpmix();
 693         void NOGC_ic();
 694
 695         CPPUNIT_TEST_SUITE(MichaelKVListTestHeader)
 696             CPPUNIT_TEST(HP_cmp)
 697             CPPUNIT_TEST(HP_less)
 698             CPPUNIT_TEST(HP_cmpmix)
 699             CPPUNIT_TEST(HP_ic)
 700
 701             CPPUNIT_TEST(DHP_cmp)
 702             CPPUNIT_TEST(DHP_less)
 703             CPPUNIT_TEST(DHP_cmpmix)
 704             CPPUNIT_TEST(DHP_ic)
 705
 706             CPPUNIT_TEST(RCU_GPI_cmp)
 707             CPPUNIT_TEST(RCU_GPI_less)
 708             CPPUNIT_TEST(RCU_GPI_cmpmix)
 709             CPPUNIT_TEST(RCU_GPI_ic)
 710
 711             CPPUNIT_TEST(RCU_GPB_cmp)
 712             CPPUNIT_TEST(RCU_GPB_less)
 713             CPPUNIT_TEST(RCU_GPB_cmpmix)
 714             CPPUNIT_TEST(RCU_GPB_ic)
 715
 716             CPPUNIT_TEST(RCU_GPT_cmp)
 717             CPPUNIT_TEST(RCU_GPT_less)
 718             CPPUNIT_TEST(RCU_GPT_cmpmix)
 719             CPPUNIT_TEST(RCU_GPT_ic)
 720
 721             CPPUNIT_TEST(RCU_SHB_cmp)
 722             CPPUNIT_TEST(RCU_SHB_less)
 723             CPPUNIT_TEST(RCU_SHB_cmpmix)
 724             CPPUNIT_TEST(RCU_SHB_ic)
 725
 726             CPPUNIT_TEST(RCU_SHT_cmp)
 727             CPPUNIT_TEST(RCU_SHT_less)
 728             CPPUNIT_TEST(RCU_SHT_cmpmix)
 729             CPPUNIT_TEST(RCU_SHT_ic)
 730
 731             CPPUNIT_TEST(NOGC_cmp)
 732             CPPUNIT_TEST(NOGC_less)
 733             CPPUNIT_TEST(NOGC_cmpmix)
 734             CPPUNIT_TEST(NOGC_ic)
 735         CPPUNIT_TEST_SUITE_END()
 736     };
 737
 738 }   // namespace ordlist