tests/test-hdr/list/hdr_lazy_kv.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSTEST_HDR_LAZY_KV_H
   4 #define CDSTEST_HDR_LAZY_KV_H
   5
   6 #include "cppunit/cppunit_proxy.h"
   7 #include <cds/container/details/lazy_list_base.h>
   8
   9 namespace ordlist {
  10     namespace cc = cds::container;
  11     namespace co = cds::container::opt;
  12
  13     class LazyKVListTestHeader: 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         template <typename T>
  49         struct eq {
  50             bool operator ()(const T& v1, const T& v2 ) const
  51             {
  52                 return v1 == v2;
  53             }
  54         };
  55
  56         struct check_value {
  57             int     m_nExpected;
  58
  59             check_value( int nExpected )
  60                 : m_nExpected( nExpected )
  61             {}
  62
  63             template <typename T>
  64             void operator ()( T& pair )
  65             {
  66                 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
  67             }
  68         };
  69
  70         struct insert_functor {
  71             template <typename T>
  72             void operator()( T& pair )
  73             {
  74                 pair.second.m_val = pair.first * 10;
  75             }
  76         };
  77
  78         struct ensure_functor {
  79             template <typename T>
  80             void operator()( bool /*bNew*/, T& pair )
  81             {
  82                 pair.second.m_val = pair.first * 50;
  83             }
  84         };
  85
  86         struct erase_functor {
  87             int     nKey;
  88             int     nVal;
  89
  90             erase_functor()
  91                 : nKey(0)
  92                 , nVal(0)
  93             {}
  94
  95             template <typename T>
  96             void operator()( T& i )
  97             {
  98                 nKey = i.first;
  99                 nVal = i.second.m_val;
 100             }
 101         };
 102
 103         typedef float other_key;
 104         struct other_less {
 105             bool operator()( float f, int i ) const
 106             {
 107                 return int(f) < i;
 108             }
 109             bool operator()( int i, float f ) const
 110             {
 111                 return i < int(f);
 112             }
 113         };
 114
 115     protected:
 116         template <class OrdList>
 117         void test_with( OrdList& l)
 118         {
 119             typedef typename OrdList::value_type    value_type;
 120
 121             typename OrdList::iterator itTest;
 122             typename OrdList::const_iterator citTest;
 123
 124             CPPUNIT_ASSERT( l.empty() );
 125
 126             // insert / find test
 127             CPPUNIT_ASSERT( !l.find( 100 ));
 128             CPPUNIT_ASSERT( l.insert( 100 ));
 129             CPPUNIT_ASSERT( !l.empty() );
 130             CPPUNIT_ASSERT( l.find( 100 ));
 131
 132             check_value chk(0);
 133             CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) );
 134
 135             CPPUNIT_ASSERT( !l.find_with( 50, lt<key_type>() ));
 136             CPPUNIT_ASSERT( l.insert( 50, 500 ));
 137             CPPUNIT_ASSERT( l.find_with( 50, lt<key_type>() ));
 138             CPPUNIT_ASSERT( !l.insert( 50, 5 ));
 139             chk.m_nExpected = 500;
 140             CPPUNIT_ASSERT( l.find( 50, std::ref( chk ) ) );
 141             chk.m_nExpected = 0;
 142             CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) );
 143             CPPUNIT_ASSERT( !l.empty() );
 144
 145             CPPUNIT_ASSERT( !l.find( 150 ));
 146             CPPUNIT_ASSERT( l.insert_with( 150, insert_functor() ));
 147             CPPUNIT_ASSERT( l.find( 150 ));
 148             chk.m_nExpected = 1500;
 149             CPPUNIT_ASSERT( l.find_with( 150, lt<key_type>(), std::ref( chk ) ) );
 150             chk.m_nExpected = 0;
 151             CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) );
 152             chk.m_nExpected = 500;
 153             CPPUNIT_ASSERT( l.find( 50, std::ref( chk ) ) );
 154             CPPUNIT_ASSERT( !l.empty() );
 155
 156             // erase test
 157
 158             CPPUNIT_ASSERT( !l.erase( 500 ));
 159             CPPUNIT_ASSERT( !l.empty() );
 160
 161             CPPUNIT_ASSERT( l.find( 50 ));
 162             {
 163                 erase_functor ef;
 164                 l.erase( 50, std::ref( ef ) );
 165                 CPPUNIT_ASSERT( ef.nKey == 50 );
 166                 CPPUNIT_ASSERT( ef.nVal == 500 );
 167             }
 168             CPPUNIT_ASSERT( !l.find( 50 ));
 169
 170             // ensure test
 171             std::pair<bool, bool> bEnsureResult;
 172             bEnsureResult = l.ensure( 100, ensure_functor() );
 173             CPPUNIT_ASSERT( bEnsureResult.first );
 174             CPPUNIT_ASSERT( !bEnsureResult.second );
 175             chk.m_nExpected = 5000;
 176             CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) );
 177
 178             {
 179                 ensure_functor ef;
 180                 bEnsureResult = l.ensure( 50, std::ref( ef ) );
 181             }
 182             CPPUNIT_ASSERT( bEnsureResult.first );
 183             CPPUNIT_ASSERT( bEnsureResult.second );
 184             chk.m_nExpected = 2500;
 185             CPPUNIT_ASSERT( l.find( 50, std::ref( chk ) ) );
 186
 187             // erase test
 188             CPPUNIT_ASSERT( !l.empty() );
 189             CPPUNIT_ASSERT( l.insert_with( 200, insert_functor() ));
 190             CPPUNIT_ASSERT( l.insert( 25 ));
 191             CPPUNIT_ASSERT( l.erase( 100 ));
 192             CPPUNIT_ASSERT( l.erase( 150 ));
 193             {
 194                 erase_functor ef;
 195                 CPPUNIT_ASSERT( l.erase_with( 200, lt<key_type>(), std::ref(ef)) );
 196                 CPPUNIT_ASSERT( ef.nKey == 200 );
 197                 CPPUNIT_ASSERT( ef.nVal == 2000 );
 198             }
 199             CPPUNIT_ASSERT( l.erase_with( 25, lt<key_type>()))
 200             CPPUNIT_ASSERT( l.erase( 50 ));
 201             CPPUNIT_ASSERT( l.empty() );
 202
 203             // clear empty list
 204             l.clear();
 205             CPPUNIT_ASSERT( l.empty() );
 206
 207             // insert test
 208             CPPUNIT_ASSERT( l.emplace( 501 ) );
 209             CPPUNIT_ASSERT( l.emplace( 251, 152 ));
 210
 211             // insert failed - such key exists
 212             CPPUNIT_ASSERT( !l.emplace( 501, 2 ) );
 213             CPPUNIT_ASSERT( !l.emplace( 251, 10) );
 214
 215             check_value cv(0);
 216             CPPUNIT_ASSERT( l.find( 501, std::ref(cv) ));
 217             cv.m_nExpected = 152;
 218             CPPUNIT_ASSERT( l.find( 251, std::ref(cv) ));
 219
 220             l.clear();
 221             CPPUNIT_ASSERT( l.empty() );
 222
 223             // Iterator test
 224             {
 225                 int nCount = 100;
 226                 for ( int i = 0; i < nCount; ++i )
 227                     CPPUNIT_ASSERT( l.insert(i, i * 2 ) );
 228
 229                 {
 230                     typename OrdList::iterator it( l.begin() );
 231                     typename OrdList::const_iterator cit( l.cbegin() );
 232                     CPPUNIT_CHECK( it == cit );
 233                     CPPUNIT_CHECK( it != l.end() );
 234                     CPPUNIT_CHECK( it != l.cend() );
 235                     CPPUNIT_CHECK( cit != l.end() );
 236                     CPPUNIT_CHECK( cit != l.cend() );
 237                     ++it;
 238                     CPPUNIT_CHECK( it != cit );
 239                     CPPUNIT_CHECK( it != l.end() );
 240                     CPPUNIT_CHECK( it != l.cend() );
 241                     CPPUNIT_CHECK( cit != l.end() );
 242                     CPPUNIT_CHECK( cit != l.cend() );
 243                     ++cit;
 244                     CPPUNIT_CHECK( it == cit );
 245                     CPPUNIT_CHECK( it != l.end() );
 246                     CPPUNIT_CHECK( it != l.cend() );
 247                     CPPUNIT_CHECK( cit != l.end() );
 248                     CPPUNIT_CHECK( cit != l.cend() );
 249                 }
 250
 251                 int i = 0;
 252                 for ( typename OrdList::iterator it = l.begin(), itEnd = l.end(); it != itEnd; ++it, ++i ) {
 253                     CPPUNIT_ASSERT( it.key() == i );
 254                     CPPUNIT_ASSERT( it.val().m_val == i * 2 );
 255                     it.val().m_val = i * 3;
 256                 }
 257
 258                 // Check that we have visited all items
 259                 for ( int i = 0; i < nCount; ++i ) {
 260                     chk.m_nExpected = i * 3;
 261                     CPPUNIT_ASSERT( l.find( i, std::ref( chk ) ) );
 262                 }
 263
 264                 l.clear();
 265                 CPPUNIT_ASSERT( l.empty() );
 266
 267                 // Const iterator
 268                 for ( int i = 0; i < nCount; ++i )
 269                     CPPUNIT_ASSERT( l.insert(i, i * 7) );
 270
 271                 i = 0;
 272                 const OrdList& rl = l;
 273                 for ( typename OrdList::const_iterator it = rl.begin(), itEnd = rl.end(); it != itEnd; ++it, ++i ) {
 274                     CPPUNIT_ASSERT( it.key() == i );
 275                     CPPUNIT_ASSERT( it.val().m_val == i * 7 );
 276                 }
 277
 278                 // Check that we have visited all items
 279                 for ( int i = nCount; i > 0; --i ) {
 280                     chk.m_nExpected = (i - 1) * 7;
 281                     CPPUNIT_ASSERT( l.find_with( i - 1, lt<key_type>(), std::ref( chk ) ) );
 282                 }
 283
 284                 l.clear();
 285                 CPPUNIT_ASSERT( l.empty() );
 286             }
 287         }
 288
 289         template <class OrdList>
 290         void test()
 291         {
 292             OrdList l;
 293             test_with(l);
 294
 295             typedef typename OrdList::guarded_ptr guarded_ptr;
 296
 297             static int const nLimit = 20;
 298             int arr[nLimit];
 299             for ( int i = 0; i < nLimit; i++ )
 300                 arr[i] = i;
 301             shuffle( arr, arr + nLimit );
 302
 303             // extract/get
 304             for ( int i = 0; i < nLimit; ++i )
 305                 l.insert( arr[i], arr[i] * 2 );
 306             {
 307                 guarded_ptr gp;
 308                 for ( int i = 0; i < nLimit; ++i ) {
 309                     int nKey = arr[i];
 310
 311                     gp = l.get( nKey );
 312                     CPPUNIT_ASSERT( gp );
 313                     CPPUNIT_ASSERT( !gp.empty());
 314                     CPPUNIT_CHECK( gp->first == nKey );
 315                     CPPUNIT_CHECK( gp->second.m_val == nKey * 2 );
 316                     gp.release();
 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                 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                 }
 429
 430                 // extract_with/get_with
 431                 for ( int i = 0; i < nLimit; ++i ) {
 432                     CPPUNIT_ASSERT( l.insert( a[i], a[i]*2 ) );
 433                 }
 434
 435                 for ( int i = 0; i < nLimit; ++i ) {
 436                     float itm = a[i] + 0.3f;
 437                     {
 438                         rcu_lock lock;
 439                         value_type * pGet = l.get_with( itm, other_less() );
 440                         CPPUNIT_ASSERT( pGet != nullptr );
 441                         CPPUNIT_CHECK( pGet->first == a[i] );
 442                         CPPUNIT_CHECK( pGet->second.m_val == a[i] * 2 );
 443
 444                         ep = l.extract_with( itm, other_less() );
 445                         CPPUNIT_ASSERT( ep );
 446                         CPPUNIT_ASSERT( !ep.empty() );
 447                         CPPUNIT_CHECK( ep->first == a[i] );
 448                         CPPUNIT_CHECK( ep->second.m_val == a[i] * 2 );
 449                     }
 450                     ep.release();
 451                     {
 452                         rcu_lock lock;
 453                         CPPUNIT_CHECK( l.get_with( itm, other_less()) == nullptr );
 454                         ep = l.extract_with( itm, other_less() );
 455                         CPPUNIT_CHECK( !ep );
 456                         CPPUNIT_CHECK( ep.empty() );
 457                     }
 458                 }
 459                 CPPUNIT_ASSERT( l.empty() );
 460
 461                 {
 462                     rcu_lock lock;
 463                     CPPUNIT_CHECK( l.get_with( 3.14f, other_less() ) == nullptr );
 464                     CPPUNIT_CHECK( !l.extract_with( 3.14f, other_less() ));
 465                     CPPUNIT_CHECK( ep.empty() );
 466                 }
 467             }
 468         }
 469
 470         template <class OrdList>
 471         void nogc_test()
 472         {
 473             typedef typename OrdList::value_type    value_type;
 474             typedef typename OrdList::iterator      iterator;
 475
 476             {
 477                 OrdList l;
 478                 iterator it;
 479
 480                 CPPUNIT_ASSERT( l.empty() );
 481
 482                 // insert / find test
 483                 CPPUNIT_ASSERT( l.find( 100 ) == l.end() );
 484                 CPPUNIT_ASSERT( l.insert( 100 ) != l.end() );
 485                 CPPUNIT_ASSERT( !l.empty() );
 486                 it = l.find( 100 );
 487                 CPPUNIT_ASSERT( it != l.end() );
 488                 CPPUNIT_ASSERT( it.key() == 100 );
 489                 CPPUNIT_ASSERT( it.val().m_val == 0 );
 490
 491                 CPPUNIT_ASSERT( l.find_with( 50, lt<key_type>() ) == l.end() );
 492                 CPPUNIT_ASSERT( l.insert( 50, 500 ) != l.end());
 493                 it = l.find( 50 );
 494                 CPPUNIT_ASSERT( it != l.end() );
 495                 CPPUNIT_ASSERT( it.key() == 50 );
 496                 CPPUNIT_ASSERT( it.val().m_val == 500 );
 497
 498                 CPPUNIT_ASSERT( l.insert( 50, 5 ) == l.end() );
 499                 it = l.find( 50 );
 500                 CPPUNIT_ASSERT( it != l.end() );
 501                 CPPUNIT_ASSERT( it.key() == 50 );
 502                 CPPUNIT_ASSERT( it.val().m_val == 500 );
 503                 CPPUNIT_ASSERT( !l.empty() );
 504
 505                 CPPUNIT_ASSERT( l.find( 150 ) == l.end() );
 506                 CPPUNIT_ASSERT( l.insert_with( 150, insert_functor() ) != l.end() );
 507                 it = l.find( 150 );
 508                 CPPUNIT_ASSERT( it != l.end() );
 509                 CPPUNIT_ASSERT( it.key() == 150 );
 510                 CPPUNIT_ASSERT( it.val().m_val == 1500 );
 511                 it = l.find( 100 );
 512                 CPPUNIT_ASSERT( it != l.end() );
 513                 CPPUNIT_ASSERT( it.key() == 100 );
 514                 CPPUNIT_ASSERT( it.val().m_val == 0 );
 515                 it = l.find( 50 );
 516                 CPPUNIT_ASSERT( it != l.end() );
 517                 CPPUNIT_ASSERT( it.key() == 50 );
 518                 CPPUNIT_ASSERT( it.val().m_val == 500 );
 519                 it.val().m_val = 25;
 520                 it = l.find( 50 );
 521                 CPPUNIT_ASSERT( it != l.end() );
 522                 CPPUNIT_ASSERT( it.key() == 50 );
 523                 CPPUNIT_ASSERT( it.val().m_val == 25 );
 524                 CPPUNIT_ASSERT( !l.empty() );
 525
 526                 // ensure existing item
 527                 std::pair<iterator, bool> ensureResult;
 528                 ensureResult = l.ensure( 100 );
 529                 CPPUNIT_ASSERT( !ensureResult.second );
 530                 CPPUNIT_ASSERT( ensureResult.first.key() == 100 );
 531                 CPPUNIT_ASSERT( ensureResult.first.val().m_val == 0   );
 532                 ensureResult.first.val().m_val = 5;
 533                 it = l.find( 100 );
 534                 CPPUNIT_ASSERT( it != l.end() );
 535                 CPPUNIT_ASSERT( it.key() == 100 );
 536                 CPPUNIT_ASSERT( it.val().m_val == 5 );
 537
 538                 CPPUNIT_ASSERT( !l.empty() );
 539
 540                 // ensure new item
 541                 ensureResult = l.ensure( 1000 );
 542                 CPPUNIT_ASSERT( ensureResult.second );
 543                 CPPUNIT_ASSERT( ensureResult.first.key() == 1000 );
 544                 CPPUNIT_ASSERT( ensureResult.first.val().m_val == 0   );
 545                 ensureResult.first.val().m_val = 33;
 546                 ensureResult = l.ensure( 1000 );
 547                 CPPUNIT_ASSERT( !ensureResult.second );
 548                 CPPUNIT_ASSERT( ensureResult.first.key() == 1000 );
 549                 CPPUNIT_ASSERT( ensureResult.first.val().m_val == 33   );
 550
 551                 // clear test
 552                 l.clear();
 553                 CPPUNIT_ASSERT( l.empty() );
 554
 555                 // insert test
 556                 CPPUNIT_ASSERT( l.emplace( 501 ) != l.end());
 557                 CPPUNIT_ASSERT( l.emplace( 251, 152 ) != l.end());
 558
 559                 // insert failed - such key exists
 560                 CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end());
 561                 CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end());
 562
 563                 it = l.find(501);
 564                 CPPUNIT_ASSERT( it != l.end() );
 565                 CPPUNIT_ASSERT( it.key() == 501 );
 566                 CPPUNIT_ASSERT( it.val().m_val == 0 );
 567
 568                 it = l.find(251);
 569                 CPPUNIT_ASSERT( it != l.end() );
 570                 CPPUNIT_ASSERT( it.key() == 251 );
 571                 CPPUNIT_ASSERT( it.val().m_val == 152 );
 572
 573                 l.clear();
 574                 CPPUNIT_ASSERT( l.empty() );
 575
 576                 // Iterator test
 577                 {
 578                     int nCount = 100;
 579                     for ( int i = 0; i < nCount; ++i )
 580                         CPPUNIT_ASSERT( l.insert(i, i * 2 ) != l.end() );
 581
 582                     {
 583                         typename OrdList::iterator it( l.begin() );
 584                         typename OrdList::const_iterator cit( l.cbegin() );
 585                         CPPUNIT_CHECK( it == cit );
 586                         CPPUNIT_CHECK( it != l.end() );
 587                         CPPUNIT_CHECK( it != l.cend() );
 588                         CPPUNIT_CHECK( cit != l.end() );
 589                         CPPUNIT_CHECK( cit != l.cend() );
 590                         ++it;
 591                         CPPUNIT_CHECK( it != cit );
 592                         CPPUNIT_CHECK( it != l.end() );
 593                         CPPUNIT_CHECK( it != l.cend() );
 594                         CPPUNIT_CHECK( cit != l.end() );
 595                         CPPUNIT_CHECK( cit != l.cend() );
 596                         ++cit;
 597                         CPPUNIT_CHECK( it == cit );
 598                         CPPUNIT_CHECK( it != l.end() );
 599                         CPPUNIT_CHECK( it != l.cend() );
 600                         CPPUNIT_CHECK( cit != l.end() );
 601                         CPPUNIT_CHECK( cit != l.cend() );
 602                     }
 603
 604                     int i = 0;
 605                     for ( typename OrdList::iterator iter = l.begin(), itEnd = l.end(); iter != itEnd; ++iter, ++i ) {
 606                         CPPUNIT_ASSERT( iter.key() == i );
 607                         CPPUNIT_ASSERT( iter->first == i );
 608                         CPPUNIT_ASSERT( (*iter).first == i );
 609
 610                         CPPUNIT_ASSERT( iter.val().m_val == i * 2 );
 611                         CPPUNIT_ASSERT( iter->second.m_val == i * 2 );
 612                         CPPUNIT_ASSERT( (*iter).second.m_val == i * 2 );
 613
 614                         iter.val().m_val = i * 3;
 615                     }
 616
 617                     // Check that we have visited all items
 618                     for ( int i = 0; i < nCount; ++i ) {
 619                         it = l.find( i );
 620                         CPPUNIT_ASSERT( it != l.end() );
 621                         CPPUNIT_ASSERT( it.key() == i );
 622                         CPPUNIT_ASSERT( it.val().m_val == i * 3 );
 623                     }
 624
 625                     l.clear();
 626                     CPPUNIT_ASSERT( l.empty() );
 627
 628                     // Const iterator
 629                     for ( int i = 0; i < nCount; ++i )
 630                         CPPUNIT_ASSERT( l.insert(i, i * 7) != l.end() );
 631
 632                     i = 0;
 633                     const OrdList& rl = l;
 634                     for ( typename OrdList::const_iterator iter = rl.begin(), itEnd = rl.end(); iter != itEnd; ++iter, ++i ) {
 635                         CPPUNIT_ASSERT( iter.key() == i );
 636                         CPPUNIT_ASSERT( iter->first == i );
 637                         CPPUNIT_ASSERT( (*iter).first == i );
 638
 639                         CPPUNIT_ASSERT( iter.val().m_val == i * 7 );
 640                         CPPUNIT_ASSERT( iter->second.m_val == i * 7 );
 641                         CPPUNIT_ASSERT( (*iter).second.m_val == i * 7 );
 642                         // it.val().m_val = i * 3    ; // error: const-iterator
 643                     }
 644
 645                     l.clear();
 646                     CPPUNIT_ASSERT( l.empty() );
 647                 }
 648
 649             }
 650         }
 651
 652         template <class UnordList>
 653         void nogc_unord_test()
 654         {
 655             typedef typename UnordList::value_type    value_type;
 656             typedef typename UnordList::iterator      iterator;
 657
 658             {
 659                 UnordList l;
 660                 iterator it;
 661
 662                 CPPUNIT_ASSERT( l.empty() );
 663
 664                 // insert / find test
 665                 CPPUNIT_ASSERT( l.find( 100 ) == l.end() );
 666                 CPPUNIT_ASSERT( l.insert( 100 ) != l.end() );
 667                 CPPUNIT_ASSERT( !l.empty() );
 668                 it = l.find( 100 );
 669                 CPPUNIT_ASSERT( it != l.end() );
 670                 CPPUNIT_ASSERT( it.key() == 100 );
 671                 CPPUNIT_ASSERT( it.val().m_val == 0 );
 672
 673                 CPPUNIT_ASSERT( l.find_with( 50, eq<key_type>() ) == l.end() );
 674                 CPPUNIT_ASSERT( l.insert( 50, 500 ) != l.end());
 675                 it = l.find( 50 );
 676                 CPPUNIT_ASSERT( it != l.end() );
 677                 CPPUNIT_ASSERT( it.key() == 50 );
 678                 CPPUNIT_ASSERT( it.val().m_val == 500 );
 679
 680                 CPPUNIT_ASSERT( l.insert( 50, 5 ) == l.end() );
 681                 it = l.find( 50 );
 682                 CPPUNIT_ASSERT( it != l.end() );
 683                 CPPUNIT_ASSERT( it.key() == 50 );
 684                 CPPUNIT_ASSERT( it.val().m_val == 500 );
 685                 CPPUNIT_ASSERT( !l.empty() );
 686
 687                 CPPUNIT_ASSERT( l.find( 150 ) == l.end() );
 688                 CPPUNIT_ASSERT( l.insert_with( 150, insert_functor() ) != l.end() );
 689                 it = l.find( 150 );
 690                 CPPUNIT_ASSERT( it != l.end() );
 691                 CPPUNIT_ASSERT( it.key() == 150 );
 692                 CPPUNIT_ASSERT( it.val().m_val == 1500 );
 693                 it = l.find( 100 );
 694                 CPPUNIT_ASSERT( it != l.end() );
 695                 CPPUNIT_ASSERT( it.key() == 100 );
 696                 CPPUNIT_ASSERT( it.val().m_val == 0 );
 697                 it = l.find( 50 );
 698                 CPPUNIT_ASSERT( it != l.end() );
 699                 CPPUNIT_ASSERT( it.key() == 50 );
 700                 CPPUNIT_ASSERT( it.val().m_val == 500 );
 701                 it.val().m_val = 25;
 702                 it = l.find( 50 );
 703                 CPPUNIT_ASSERT( it != l.end() );
 704                 CPPUNIT_ASSERT( it.key() == 50 );
 705                 CPPUNIT_ASSERT( it.val().m_val == 25 );
 706                 CPPUNIT_ASSERT( !l.empty() );
 707
 708                 // ensure existing item
 709                 std::pair<iterator, bool> ensureResult;
 710                 ensureResult = l.ensure( 100 );
 711                 CPPUNIT_ASSERT( !ensureResult.second );
 712                 CPPUNIT_ASSERT( ensureResult.first.key() == 100 );
 713                 CPPUNIT_ASSERT( ensureResult.first.val().m_val == 0   );
 714                 ensureResult.first.val().m_val = 5;
 715                 it = l.find( 100 );
 716                 CPPUNIT_ASSERT( it != l.end() );
 717                 CPPUNIT_ASSERT( it.key() == 100 );
 718                 CPPUNIT_ASSERT( it.val().m_val == 5 );
 719
 720                 CPPUNIT_ASSERT( !l.empty() );
 721
 722                 // ensure new item
 723                 ensureResult = l.ensure( 1000 );
 724                 CPPUNIT_ASSERT( ensureResult.second );
 725                 CPPUNIT_ASSERT( ensureResult.first.key() == 1000 );
 726                 CPPUNIT_ASSERT( ensureResult.first.val().m_val == 0   );
 727                 ensureResult.first.val().m_val = 33;
 728                 ensureResult = l.ensure( 1000 );
 729                 CPPUNIT_ASSERT( !ensureResult.second );
 730                 CPPUNIT_ASSERT( ensureResult.first.key() == 1000 );
 731                 CPPUNIT_ASSERT( ensureResult.first.val().m_val == 33   );
 732
 733                 // clear test
 734                 l.clear();
 735                 CPPUNIT_ASSERT( l.empty() );
 736
 737                 // insert test
 738                 CPPUNIT_ASSERT( l.emplace( 501 ) != l.end());
 739                 CPPUNIT_ASSERT( l.emplace( 251, 152 ) != l.end());
 740
 741                 // insert failed - such key exists
 742                 CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end());
 743                 CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end());
 744
 745                 it = l.find(501);
 746                 CPPUNIT_ASSERT( it != l.end() );
 747                 CPPUNIT_ASSERT( it.key() == 501 );
 748                 CPPUNIT_ASSERT( it.val().m_val == 0 );
 749
 750                 it = l.find(251);
 751                 CPPUNIT_ASSERT( it != l.end() );
 752                 CPPUNIT_ASSERT( it.key() == 251 );
 753                 CPPUNIT_ASSERT( it.val().m_val == 152 );
 754
 755                 l.clear();
 756                 CPPUNIT_ASSERT( l.empty() );
 757
 758                 // Iterator test
 759                 {
 760                     int nCount = 100;
 761                     for ( int i = 0; i < nCount; ++i )
 762                         CPPUNIT_ASSERT( l.insert(i, i * 2 ) != l.end() );
 763
 764                     {
 765                         typename UnordList::iterator it( l.begin() );
 766                         typename UnordList::const_iterator cit( l.cbegin() );
 767                         CPPUNIT_CHECK( it == cit );
 768                         CPPUNIT_CHECK( it != l.end() );
 769                         CPPUNIT_CHECK( it != l.cend() );
 770                         CPPUNIT_CHECK( cit != l.end() );
 771                         CPPUNIT_CHECK( cit != l.cend() );
 772                         ++it;
 773                         CPPUNIT_CHECK( it != cit );
 774                         CPPUNIT_CHECK( it != l.end() );
 775                         CPPUNIT_CHECK( it != l.cend() );
 776                         CPPUNIT_CHECK( cit != l.end() );
 777                         CPPUNIT_CHECK( cit != l.cend() );
 778                         ++cit;
 779                         CPPUNIT_CHECK( it == cit );
 780                         CPPUNIT_CHECK( it != l.end() );
 781                         CPPUNIT_CHECK( it != l.cend() );
 782                         CPPUNIT_CHECK( cit != l.end() );
 783                         CPPUNIT_CHECK( cit != l.cend() );
 784                     }
 785
 786                     int i = 0;
 787                     for ( typename UnordList::iterator iter = l.begin(), itEnd = l.end(); iter != itEnd; ++iter, ++i ) {
 788                         CPPUNIT_ASSERT( iter.key() == i );
 789                         CPPUNIT_ASSERT( iter->first == i );
 790                         CPPUNIT_ASSERT( (*iter).first == i );
 791
 792                         CPPUNIT_ASSERT( iter.val().m_val == i * 2 );
 793                         CPPUNIT_ASSERT( iter->second.m_val == i * 2 );
 794                         CPPUNIT_ASSERT( (*iter).second.m_val == i * 2 );
 795
 796                         iter.val().m_val = i * 3;
 797                     }
 798
 799                     // Check that we have visited all items
 800                     for ( int i = 0; i < nCount; ++i ) {
 801                         it = l.find( i );
 802                         CPPUNIT_ASSERT( it != l.end() );
 803                         CPPUNIT_ASSERT( it.key() == i );
 804                         CPPUNIT_ASSERT( it.val().m_val == i * 3 );
 805                     }
 806
 807                     l.clear();
 808                     CPPUNIT_ASSERT( l.empty() );
 809
 810                     // Const iterator
 811                     for ( int i = 0; i < nCount; ++i )
 812                         CPPUNIT_ASSERT( l.insert(i, i * 7) != l.end() );
 813
 814                     i = 0;
 815                     const UnordList& rl = l;
 816                     for ( typename UnordList::const_iterator iter = rl.begin(), itEnd = rl.end(); iter != itEnd; ++iter, ++i ) {
 817                         CPPUNIT_ASSERT( iter.key() == i );
 818                         CPPUNIT_ASSERT( iter->first == i );
 819                         CPPUNIT_ASSERT( (*iter).first == i );
 820
 821                         CPPUNIT_ASSERT( iter.val().m_val == i * 7 );
 822                         CPPUNIT_ASSERT( iter->second.m_val == i * 7 );
 823                         CPPUNIT_ASSERT( (*iter).second.m_val == i * 7 );
 824                         // it.val().m_val = i * 3    ; // error: const-iterator
 825                     }
 826
 827                     l.clear();
 828                     CPPUNIT_ASSERT( l.empty() );
 829                 }
 830
 831             }
 832         }
 833
 834
 835         void HP_cmp();
 836         void HP_less();
 837         void HP_cmpmix();
 838         void HP_ic();
 839
 840         void DHP_cmp();
 841         void DHP_less();
 842         void DHP_cmpmix();
 843         void DHP_ic();
 844
 845         void RCU_GPI_cmp();
 846         void RCU_GPI_less();
 847         void RCU_GPI_cmpmix();
 848         void RCU_GPI_ic();
 849
 850         void RCU_GPB_cmp();
 851         void RCU_GPB_less();
 852         void RCU_GPB_cmpmix();
 853         void RCU_GPB_ic();
 854
 855         void RCU_GPT_cmp();
 856         void RCU_GPT_less();
 857         void RCU_GPT_cmpmix();
 858         void RCU_GPT_ic();
 859
 860         void RCU_SHB_cmp();
 861         void RCU_SHB_less();
 862         void RCU_SHB_cmpmix();
 863         void RCU_SHB_ic();
 864
 865         void RCU_SHT_cmp();
 866         void RCU_SHT_less();
 867         void RCU_SHT_cmpmix();
 868         void RCU_SHT_ic();
 869
 870         void NOGC_cmp();
 871         void NOGC_less();
 872         void NOGC_cmpmix();
 873         void NOGC_ic();
 874
 875         void NOGC_cmp_unord();
 876         void NOGC_less_unord();
 877         void NOGC_equal_to_unord();
 878         void NOGC_cmpmix_unord();
 879         void NOGC_ic_unord();
 880
 881         CPPUNIT_TEST_SUITE(LazyKVListTestHeader)
 882             CPPUNIT_TEST(HP_cmp)
 883             CPPUNIT_TEST(HP_less)
 884             CPPUNIT_TEST(HP_cmpmix)
 885             CPPUNIT_TEST(HP_ic)
 886
 887             CPPUNIT_TEST(DHP_cmp)
 888             CPPUNIT_TEST(DHP_less)
 889             CPPUNIT_TEST(DHP_cmpmix)
 890             CPPUNIT_TEST(DHP_ic)
 891
 892             CPPUNIT_TEST(RCU_GPI_cmp)
 893             CPPUNIT_TEST(RCU_GPI_less)
 894             CPPUNIT_TEST(RCU_GPI_cmpmix)
 895             CPPUNIT_TEST(RCU_GPI_ic)
 896
 897             CPPUNIT_TEST(RCU_GPB_cmp)
 898             CPPUNIT_TEST(RCU_GPB_less)
 899             CPPUNIT_TEST(RCU_GPB_cmpmix)
 900             CPPUNIT_TEST(RCU_GPB_ic)
 901
 902             CPPUNIT_TEST(RCU_GPT_cmp)
 903             CPPUNIT_TEST(RCU_GPT_less)
 904             CPPUNIT_TEST(RCU_GPT_cmpmix)
 905             CPPUNIT_TEST(RCU_GPT_ic)
 906
 907             CPPUNIT_TEST(RCU_SHB_cmp)
 908             CPPUNIT_TEST(RCU_SHB_less)
 909             CPPUNIT_TEST(RCU_SHB_cmpmix)
 910             CPPUNIT_TEST(RCU_SHB_ic)
 911
 912             CPPUNIT_TEST(RCU_SHT_cmp)
 913             CPPUNIT_TEST(RCU_SHT_less)
 914             CPPUNIT_TEST(RCU_SHT_cmpmix)
 915             CPPUNIT_TEST(RCU_SHT_ic)
 916
 917             CPPUNIT_TEST(NOGC_cmp)
 918             CPPUNIT_TEST(NOGC_less)
 919             CPPUNIT_TEST(NOGC_cmpmix)
 920             CPPUNIT_TEST(NOGC_ic)
 921
 922             CPPUNIT_TEST(NOGC_cmp_unord)
 923             CPPUNIT_TEST(NOGC_less_unord)
 924             CPPUNIT_TEST(NOGC_equal_to_unord)
 925             CPPUNIT_TEST(NOGC_cmpmix_unord)
 926             CPPUNIT_TEST(NOGC_ic_unord)
 927
 928         CPPUNIT_TEST_SUITE_END()
 929     };
 930
 931 }   // namespace ordlist
 932
 933 #endif // #ifndef CDSTEST_HDR_LAZY_KV_H