tests/test-hdr/list/hdr_lazy_kv.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSTEST_HDR_LAZY_KV_H
  32 #define CDSTEST_HDR_LAZY_KV_H
  33
  34 #include "cppunit/cppunit_proxy.h"
  35 #include <cds/container/details/lazy_list_base.h>
  36
  37 namespace ordlist {
  38     namespace cc = cds::container;
  39     namespace co = cds::container::opt;
  40
  41     class LazyKVListTestHeader: public CppUnitMini::TestCase
  42     {
  43     public:
  44         typedef int key_type;
  45         struct value_type {
  46             int m_val;
  47
  48             value_type()
  49                 : m_val(0)
  50             {}
  51
  52             value_type( int n )
  53                 : m_val( n )
  54             {}
  55         };
  56
  57         template <typename T>
  58         struct lt
  59         {
  60             bool operator ()(const T& v1, const T& v2 ) const
  61             {
  62                 return v1 < v2;
  63             }
  64         };
  65
  66         template <typename T>
  67         struct cmp {
  68             int operator ()(const T& v1, const T& v2 ) const
  69             {
  70                 if ( v1 < v2 )
  71                     return -1;
  72                 return v1 > v2 ? 1 : 0;
  73             }
  74         };
  75
  76         template <typename T>
  77         struct eq {
  78             bool operator ()(const T& v1, const T& v2 ) const
  79             {
  80                 return v1 == v2;
  81             }
  82         };
  83
  84         struct check_value {
  85             int     m_nExpected;
  86
  87             check_value( int nExpected )
  88                 : m_nExpected( nExpected )
  89             {}
  90
  91             template <typename T>
  92             void operator ()( T& pair )
  93             {
  94                 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
  95             }
  96         };
  97
  98         struct insert_functor {
  99             template <typename T>
 100             void operator()( T& pair )
 101             {
 102                 pair.second.m_val = pair.first * 10;
 103             }
 104         };
 105
 106         struct update_functor {
 107             template <typename T>
 108             void operator()( bool /*bNew*/, T& pair )
 109             {
 110                 pair.second.m_val = pair.first * 50;
 111             }
 112         };
 113
 114         struct erase_functor {
 115             int     nKey;
 116             int     nVal;
 117
 118             erase_functor()
 119                 : nKey(0)
 120                 , nVal(0)
 121             {}
 122
 123             template <typename T>
 124             void operator()( T& i )
 125             {
 126                 nKey = i.first;
 127                 nVal = i.second.m_val;
 128             }
 129         };
 130
 131         typedef float other_key;
 132         struct other_less {
 133             bool operator()( float f, int i ) const
 134             {
 135                 return int(f) < i;
 136             }
 137             bool operator()( int i, float f ) const
 138             {
 139                 return i < int(f);
 140             }
 141         };
 142
 143     protected:
 144         template <class OrdList>
 145         void test_with( OrdList& l)
 146         {
 147             typedef typename OrdList::value_type    value_type;
 148
 149             typename OrdList::iterator itTest;
 150             typename OrdList::const_iterator citTest;
 151
 152             CPPUNIT_ASSERT( l.empty() );
 153
 154             // insert / find test
 155             CPPUNIT_ASSERT( !l.contains( 100 ));
 156             CPPUNIT_ASSERT( l.insert( 100 ));
 157             CPPUNIT_ASSERT( !l.empty() );
 158             CPPUNIT_ASSERT( l.contains( 100 ));
 159
 160             check_value chk(0);
 161             CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) );
 162
 163             CPPUNIT_ASSERT( !l.contains( 50, lt<key_type>() ));
 164             CPPUNIT_ASSERT( l.insert( 50, 500 ));
 165             CPPUNIT_ASSERT( l.contains( 50, lt<key_type>() ));
 166             CPPUNIT_ASSERT( !l.insert( 50, 5 ));
 167             chk.m_nExpected = 500;
 168             CPPUNIT_ASSERT( l.find( 50, std::ref( chk ) ) );
 169             chk.m_nExpected = 0;
 170             CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) );
 171             CPPUNIT_ASSERT( !l.empty() );
 172
 173             CPPUNIT_ASSERT( !l.contains( 150 ));
 174             CPPUNIT_ASSERT( l.insert_with( 150, insert_functor() ));
 175             CPPUNIT_ASSERT( l.contains( 150 ));
 176             chk.m_nExpected = 1500;
 177             CPPUNIT_ASSERT( l.find_with( 150, lt<key_type>(), std::ref( chk ) ) );
 178             chk.m_nExpected = 0;
 179             CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) );
 180             chk.m_nExpected = 500;
 181             CPPUNIT_ASSERT( l.find( 50, std::ref( chk ) ) );
 182             CPPUNIT_ASSERT( !l.empty() );
 183
 184             // erase test
 185
 186             CPPUNIT_ASSERT( !l.erase( 500 ));
 187             CPPUNIT_ASSERT( !l.empty() );
 188
 189             CPPUNIT_ASSERT( l.contains( 50 ));
 190             {
 191                 erase_functor ef;
 192                 l.erase( 50, std::ref( ef ) );
 193                 CPPUNIT_ASSERT( ef.nKey == 50 );
 194                 CPPUNIT_ASSERT( ef.nVal == 500 );
 195             }
 196             CPPUNIT_ASSERT( !l.contains( 50 ));
 197
 198             // update test
 199             std::pair<bool, bool> bUpdateResult;
 200             bUpdateResult = l.update( 100, update_functor() );
 201             CPPUNIT_ASSERT( bUpdateResult.first );
 202             CPPUNIT_ASSERT( !bUpdateResult.second );
 203             chk.m_nExpected = 5000;
 204             CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) );
 205
 206             {
 207                 update_functor ef;
 208                 bUpdateResult = l.update( 50, std::ref( ef ) );
 209             }
 210             CPPUNIT_ASSERT( bUpdateResult.first );
 211             CPPUNIT_ASSERT( bUpdateResult.second );
 212             chk.m_nExpected = 2500;
 213             CPPUNIT_ASSERT( l.find( 50, std::ref( chk ) ) );
 214
 215             // erase test
 216             CPPUNIT_ASSERT( !l.empty() );
 217             CPPUNIT_ASSERT( l.insert_with( 200, insert_functor() ));
 218             CPPUNIT_ASSERT( l.insert( 25 ));
 219             CPPUNIT_ASSERT( l.erase( 100 ));
 220             CPPUNIT_ASSERT( l.erase( 150 ));
 221             {
 222                 erase_functor ef;
 223                 CPPUNIT_ASSERT( l.erase_with( 200, lt<key_type>(), std::ref(ef)) );
 224                 CPPUNIT_ASSERT( ef.nKey == 200 );
 225                 CPPUNIT_ASSERT( ef.nVal == 2000 );
 226             }
 227             CPPUNIT_ASSERT( l.erase_with( 25, lt<key_type>()))
 228             CPPUNIT_ASSERT( l.erase( 50 ));
 229             CPPUNIT_ASSERT( l.empty() );
 230
 231             // clear empty list
 232             l.clear();
 233             CPPUNIT_ASSERT( l.empty() );
 234
 235             // insert test
 236             CPPUNIT_ASSERT( l.emplace( 501 ) );
 237             CPPUNIT_ASSERT( l.emplace( 251, 152 ));
 238
 239             // insert failed - such key exists
 240             CPPUNIT_ASSERT( !l.emplace( 501, 2 ) );
 241             CPPUNIT_ASSERT( !l.emplace( 251, 10) );
 242
 243             check_value cv(0);
 244             CPPUNIT_ASSERT( l.find( 501, std::ref(cv) ));
 245             cv.m_nExpected = 152;
 246             CPPUNIT_ASSERT( l.find( 251, std::ref(cv) ));
 247
 248             l.clear();
 249             CPPUNIT_ASSERT( l.empty() );
 250
 251             // Iterator test
 252             {
 253                 int nCount = 100;
 254                 for ( int i = 0; i < nCount; ++i )
 255                     CPPUNIT_ASSERT( l.insert(i, i * 2 ) );
 256
 257                 {
 258                     typename OrdList::iterator it( l.begin() );
 259                     typename OrdList::const_iterator cit( l.cbegin() );
 260                     CPPUNIT_CHECK( it == cit );
 261                     CPPUNIT_CHECK( it != l.end() );
 262                     CPPUNIT_CHECK( it != l.cend() );
 263                     CPPUNIT_CHECK( cit != l.end() );
 264                     CPPUNIT_CHECK( cit != l.cend() );
 265                     ++it;
 266                     CPPUNIT_CHECK( it != cit );
 267                     CPPUNIT_CHECK( it != l.end() );
 268                     CPPUNIT_CHECK( it != l.cend() );
 269                     CPPUNIT_CHECK( cit != l.end() );
 270                     CPPUNIT_CHECK( cit != l.cend() );
 271                     ++cit;
 272                     CPPUNIT_CHECK( it == cit );
 273                     CPPUNIT_CHECK( it != l.end() );
 274                     CPPUNIT_CHECK( it != l.cend() );
 275                     CPPUNIT_CHECK( cit != l.end() );
 276                     CPPUNIT_CHECK( cit != l.cend() );
 277                 }
 278
 279                 int i = 0;
 280                 for ( typename OrdList::iterator it = l.begin(), itEnd = l.end(); it != itEnd; ++it, ++i ) {
 281                     CPPUNIT_ASSERT( it.key() == i );
 282                     CPPUNIT_ASSERT( it.val().m_val == i * 2 );
 283                     it.val().m_val = i * 3;
 284                 }
 285
 286                 // Check that we have visited all items
 287                 for ( int i = 0; i < nCount; ++i ) {
 288                     chk.m_nExpected = i * 3;
 289                     CPPUNIT_ASSERT( l.find( i, std::ref( chk ) ) );
 290                 }
 291
 292                 l.clear();
 293                 CPPUNIT_ASSERT( l.empty() );
 294
 295                 // Const iterator
 296                 for ( int i = 0; i < nCount; ++i )
 297                     CPPUNIT_ASSERT( l.insert(i, i * 7) );
 298
 299                 i = 0;
 300                 const OrdList& rl = l;
 301                 for ( typename OrdList::const_iterator it = rl.begin(), itEnd = rl.end(); it != itEnd; ++it, ++i ) {
 302                     CPPUNIT_ASSERT( it.key() == i );
 303                     CPPUNIT_ASSERT( it.val().m_val == i * 7 );
 304                 }
 305
 306                 // Check that we have visited all items
 307                 for ( int i = nCount; i > 0; --i ) {
 308                     chk.m_nExpected = (i - 1) * 7;
 309                     CPPUNIT_ASSERT( l.find_with( i - 1, lt<key_type>(), std::ref( chk ) ) );
 310                 }
 311
 312                 l.clear();
 313                 CPPUNIT_ASSERT( l.empty() );
 314             }
 315         }
 316
 317         template <class OrdList>
 318         void test()
 319         {
 320             OrdList l;
 321             test_with(l);
 322
 323             typedef typename OrdList::guarded_ptr guarded_ptr;
 324
 325             static int const nLimit = 20;
 326             int arr[nLimit];
 327             for ( int i = 0; i < nLimit; i++ )
 328                 arr[i] = i;
 329             shuffle( arr, arr + nLimit );
 330
 331             // extract/get
 332             for ( int i = 0; i < nLimit; ++i )
 333                 l.insert( arr[i], arr[i] * 2 );
 334             {
 335                 guarded_ptr gp;
 336                 for ( int i = 0; i < nLimit; ++i ) {
 337                     int nKey = arr[i];
 338
 339                     gp = l.get( nKey );
 340                     CPPUNIT_ASSERT( gp );
 341                     CPPUNIT_ASSERT( !gp.empty());
 342                     CPPUNIT_CHECK( gp->first == nKey );
 343                     CPPUNIT_CHECK( gp->second.m_val == nKey * 2 );
 344                     gp.release();
 345
 346                     gp = l.extract( nKey );
 347                     CPPUNIT_ASSERT( gp );
 348                     CPPUNIT_ASSERT( !gp.empty());
 349                     CPPUNIT_CHECK( gp->first == nKey );
 350                     CPPUNIT_CHECK( gp->second.m_val == nKey*2 );
 351                     gp.release();
 352
 353                     gp = l.get( nKey );
 354                     CPPUNIT_CHECK( !gp );
 355                     CPPUNIT_CHECK( gp.empty());
 356                     CPPUNIT_CHECK( !l.extract( nKey));
 357                     CPPUNIT_CHECK( gp.empty());
 358                 }
 359                 CPPUNIT_ASSERT( l.empty());
 360                 CPPUNIT_CHECK( !l.get(arr[0]));
 361                 CPPUNIT_CHECK( gp.empty());
 362                 CPPUNIT_CHECK( !l.extract( arr[0]));
 363                 CPPUNIT_CHECK( gp.empty());
 364             }
 365
 366             // extract_with/get_with
 367             for ( int i = 0; i < nLimit; ++i )
 368                 l.insert( arr[i], arr[i] * 2 );
 369             {
 370                 guarded_ptr gp;
 371                 for ( int i = 0; i < nLimit; ++i ) {
 372                     int nKey = arr[i];
 373                     other_key key = float(nKey + 0.3);
 374
 375                     gp = l.get_with( key, other_less() );
 376                     CPPUNIT_ASSERT( gp );
 377                     CPPUNIT_ASSERT( !gp.empty());
 378                     CPPUNIT_CHECK( gp->first == nKey );
 379                     CPPUNIT_CHECK( gp->second.m_val == nKey * 2 );
 380                     gp.release();
 381
 382                     gp = l.extract_with( key, other_less() );
 383                     CPPUNIT_ASSERT( gp );
 384                     CPPUNIT_ASSERT( !gp.empty());
 385                     CPPUNIT_CHECK( gp->first == nKey );
 386                     CPPUNIT_CHECK( gp->second.m_val == nKey*2 );
 387                     gp.release();
 388
 389                     gp = l.get_with( key, other_less() );
 390                     CPPUNIT_CHECK( !gp );
 391                     CPPUNIT_CHECK( gp.empty());
 392                     CPPUNIT_CHECK( !l.extract_with( key, other_less()));
 393                     CPPUNIT_CHECK( gp.empty());
 394                 }
 395                 CPPUNIT_ASSERT( l.empty());
 396                 CPPUNIT_CHECK( !l.get_with(3.4f, other_less()));
 397                 CPPUNIT_CHECK( gp.empty());
 398                 CPPUNIT_CHECK( !l.extract_with( 3.4f, other_less()));
 399                 CPPUNIT_CHECK( gp.empty());
 400             }
 401         }
 402
 403         template <class OrdList>
 404         void test_rcu()
 405         {
 406             OrdList l;
 407             test_with(l);
 408
 409             static int const nLimit = 20;
 410
 411             typedef typename OrdList::rcu_lock rcu_lock;
 412             typedef typename OrdList::value_type value_type;
 413             typedef typename OrdList::gc rcu_type;
 414
 415             {
 416                 int a[nLimit];
 417                 for (int i = 0; i < nLimit; ++i)
 418                     a[i]=i;
 419                 shuffle( a, a + nLimit );
 420
 421                 // extract/get
 422                 for ( int i = 0; i < nLimit; ++i )
 423                     CPPUNIT_ASSERT( l.insert( a[i], a[i]*2 ) );
 424
 425                 typename OrdList::exempt_ptr ep;
 426
 427                 for ( int i = 0; i < nLimit; ++i ) {
 428                     {
 429                         rcu_lock lock;
 430                         value_type * pGet = l.get( a[i] );
 431                         CPPUNIT_ASSERT( pGet != nullptr );
 432                         CPPUNIT_CHECK( pGet->first == a[i] );
 433                         CPPUNIT_CHECK( pGet->second.m_val == a[i] * 2 );
 434
 435                         ep = l.extract( a[i] );
 436                         CPPUNIT_ASSERT( ep );
 437                         CPPUNIT_ASSERT( !ep.empty() );
 438                         CPPUNIT_CHECK( ep->first == a[i] );
 439                         CPPUNIT_CHECK( (*ep).second.m_val == a[i] * 2 );
 440                     }
 441                     ep.release();
 442                     {
 443                         rcu_lock lock;
 444                         CPPUNIT_CHECK( l.get( a[i] ) == nullptr );
 445                         ep = l.extract( a[i] );
 446                         CPPUNIT_CHECK( !ep );
 447                         CPPUNIT_CHECK( ep.empty() );
 448                     }
 449                 }
 450                 CPPUNIT_ASSERT( l.empty() );
 451
 452                 {
 453                     rcu_lock lock;
 454                     CPPUNIT_CHECK( l.get( a[0] ) == nullptr );
 455                     CPPUNIT_CHECK( !l.extract( a[0] ) );
 456                 }
 457
 458                 // extract_with/get_with
 459                 for ( int i = 0; i < nLimit; ++i ) {
 460                     CPPUNIT_ASSERT( l.insert( a[i], a[i]*2 ) );
 461                 }
 462
 463                 for ( int i = 0; i < nLimit; ++i ) {
 464                     float itm = a[i] + 0.3f;
 465                     {
 466                         rcu_lock lock;
 467                         value_type * pGet = l.get_with( itm, other_less() );
 468                         CPPUNIT_ASSERT( pGet != nullptr );
 469                         CPPUNIT_CHECK( pGet->first == a[i] );
 470                         CPPUNIT_CHECK( pGet->second.m_val == a[i] * 2 );
 471
 472                         ep = l.extract_with( itm, other_less() );
 473                         CPPUNIT_ASSERT( ep );
 474                         CPPUNIT_ASSERT( !ep.empty() );
 475                         CPPUNIT_CHECK( ep->first == a[i] );
 476                         CPPUNIT_CHECK( ep->second.m_val == a[i] * 2 );
 477                     }
 478                     ep.release();
 479                     {
 480                         rcu_lock lock;
 481                         CPPUNIT_CHECK( l.get_with( itm, other_less()) == nullptr );
 482                         ep = l.extract_with( itm, other_less() );
 483                         CPPUNIT_CHECK( !ep );
 484                         CPPUNIT_CHECK( ep.empty() );
 485                     }
 486                 }
 487                 CPPUNIT_ASSERT( l.empty() );
 488
 489                 {
 490                     rcu_lock lock;
 491                     CPPUNIT_CHECK( l.get_with( 3.14f, other_less() ) == nullptr );
 492                     CPPUNIT_CHECK( !l.extract_with( 3.14f, other_less() ));
 493                     CPPUNIT_CHECK( ep.empty() );
 494                 }
 495             }
 496         }
 497
 498         template <class OrdList>
 499         void nogc_test()
 500         {
 501             typedef typename OrdList::value_type    value_type;
 502             typedef typename OrdList::iterator      iterator;
 503
 504             {
 505                 OrdList l;
 506                 iterator it;
 507
 508                 CPPUNIT_ASSERT( l.empty() );
 509
 510                 // insert / find test
 511                 CPPUNIT_ASSERT( l.contains( 100 ) == l.end() );
 512                 CPPUNIT_ASSERT( l.insert( 100 ) != l.end() );
 513                 CPPUNIT_ASSERT( !l.empty() );
 514                 it = l.contains( 100 );
 515                 CPPUNIT_ASSERT( it != l.end() );
 516                 CPPUNIT_ASSERT( it.key() == 100 );
 517                 CPPUNIT_ASSERT( it.val().m_val == 0 );
 518
 519                 CPPUNIT_ASSERT( l.contains( 50, lt<key_type>() ) == l.end() );
 520                 CPPUNIT_ASSERT( l.insert( 50, 500 ) != l.end());
 521                 it = l.contains( 50 );
 522                 CPPUNIT_ASSERT( it != l.end() );
 523                 CPPUNIT_ASSERT( it.key() == 50 );
 524                 CPPUNIT_ASSERT( it.val().m_val == 500 );
 525
 526                 CPPUNIT_ASSERT( l.insert( 50, 5 ) == l.end() );
 527                 it = l.contains( 50 );
 528                 CPPUNIT_ASSERT( it != l.end() );
 529                 CPPUNIT_ASSERT( it.key() == 50 );
 530                 CPPUNIT_ASSERT( it.val().m_val == 500 );
 531                 CPPUNIT_ASSERT( !l.empty() );
 532
 533                 CPPUNIT_ASSERT( l.contains( 150 ) == l.end() );
 534                 CPPUNIT_ASSERT( l.insert_with( 150, insert_functor() ) != l.end() );
 535                 it = l.contains( 150 );
 536                 CPPUNIT_ASSERT( it != l.end() );
 537                 CPPUNIT_ASSERT( it.key() == 150 );
 538                 CPPUNIT_ASSERT( it.val().m_val == 1500 );
 539                 it = l.contains( 100 );
 540                 CPPUNIT_ASSERT( it != l.end() );
 541                 CPPUNIT_ASSERT( it.key() == 100 );
 542                 CPPUNIT_ASSERT( it.val().m_val == 0 );
 543                 it = l.contains( 50 );
 544                 CPPUNIT_ASSERT( it != l.end() );
 545                 CPPUNIT_ASSERT( it.key() == 50 );
 546                 CPPUNIT_ASSERT( it.val().m_val == 500 );
 547                 it.val().m_val = 25;
 548                 it = l.contains( 50 );
 549                 CPPUNIT_ASSERT( it != l.end() );
 550                 CPPUNIT_ASSERT( it.key() == 50 );
 551                 CPPUNIT_ASSERT( it.val().m_val == 25 );
 552                 CPPUNIT_ASSERT( !l.empty() );
 553
 554                 // update existing item
 555                 std::pair<iterator, bool> updateResult;
 556                 updateResult = l.update( 100 );
 557                 CPPUNIT_ASSERT( !updateResult.second );
 558                 CPPUNIT_ASSERT( updateResult.first.key() == 100 );
 559                 CPPUNIT_ASSERT( updateResult.first.val().m_val == 0   );
 560                 updateResult.first.val().m_val = 5;
 561                 it = l.contains( 100 );
 562                 CPPUNIT_ASSERT( it != l.end() );
 563                 CPPUNIT_ASSERT( it.key() == 100 );
 564                 CPPUNIT_ASSERT( it.val().m_val == 5 );
 565
 566                 CPPUNIT_ASSERT( !l.empty() );
 567
 568                 // update new item
 569                 updateResult = l.update( 1000 );
 570                 CPPUNIT_ASSERT( updateResult.second );
 571                 CPPUNIT_ASSERT( updateResult.first.key() == 1000 );
 572                 CPPUNIT_ASSERT( updateResult.first.val().m_val == 0   );
 573                 updateResult.first.val().m_val = 33;
 574                 updateResult = l.update( 1000 );
 575                 CPPUNIT_ASSERT( !updateResult.second );
 576                 CPPUNIT_ASSERT( updateResult.first.key() == 1000 );
 577                 CPPUNIT_ASSERT( updateResult.first.val().m_val == 33   );
 578
 579                 // clear test
 580                 l.clear();
 581                 CPPUNIT_ASSERT( l.empty() );
 582
 583                 // insert test
 584                 CPPUNIT_ASSERT( l.emplace( 501 ) != l.end());
 585                 CPPUNIT_ASSERT( l.emplace( 251, 152 ) != l.end());
 586
 587                 // insert failed - such key exists
 588                 CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end());
 589                 CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end());
 590
 591                 it = l.contains(501);
 592                 CPPUNIT_ASSERT( it != l.end() );
 593                 CPPUNIT_ASSERT( it.key() == 501 );
 594                 CPPUNIT_ASSERT( it.val().m_val == 0 );
 595
 596                 it = l.contains(251);
 597                 CPPUNIT_ASSERT( it != l.end() );
 598                 CPPUNIT_ASSERT( it.key() == 251 );
 599                 CPPUNIT_ASSERT( it.val().m_val == 152 );
 600
 601                 l.clear();
 602                 CPPUNIT_ASSERT( l.empty() );
 603
 604                 // Iterator test
 605                 {
 606                     int nCount = 100;
 607                     for ( int i = 0; i < nCount; ++i )
 608                         CPPUNIT_ASSERT( l.insert(i, i * 2 ) != l.end() );
 609
 610                     {
 611                         typename OrdList::iterator it( l.begin() );
 612                         typename OrdList::const_iterator cit( l.cbegin() );
 613                         CPPUNIT_CHECK( it == cit );
 614                         CPPUNIT_CHECK( it != l.end() );
 615                         CPPUNIT_CHECK( it != l.cend() );
 616                         CPPUNIT_CHECK( cit != l.end() );
 617                         CPPUNIT_CHECK( cit != l.cend() );
 618                         ++it;
 619                         CPPUNIT_CHECK( it != cit );
 620                         CPPUNIT_CHECK( it != l.end() );
 621                         CPPUNIT_CHECK( it != l.cend() );
 622                         CPPUNIT_CHECK( cit != l.end() );
 623                         CPPUNIT_CHECK( cit != l.cend() );
 624                         ++cit;
 625                         CPPUNIT_CHECK( it == cit );
 626                         CPPUNIT_CHECK( it != l.end() );
 627                         CPPUNIT_CHECK( it != l.cend() );
 628                         CPPUNIT_CHECK( cit != l.end() );
 629                         CPPUNIT_CHECK( cit != l.cend() );
 630                     }
 631
 632                     int i = 0;
 633                     for ( typename OrdList::iterator iter = l.begin(), itEnd = l.end(); iter != itEnd; ++iter, ++i ) {
 634                         CPPUNIT_ASSERT( iter.key() == i );
 635                         CPPUNIT_ASSERT( iter->first == i );
 636                         CPPUNIT_ASSERT( (*iter).first == i );
 637
 638                         CPPUNIT_ASSERT( iter.val().m_val == i * 2 );
 639                         CPPUNIT_ASSERT( iter->second.m_val == i * 2 );
 640                         CPPUNIT_ASSERT( (*iter).second.m_val == i * 2 );
 641
 642                         iter.val().m_val = i * 3;
 643                     }
 644
 645                     // Check that we have visited all items
 646                     for ( int i = 0; i < nCount; ++i ) {
 647                         it = l.contains( i );
 648                         CPPUNIT_ASSERT( it != l.end() );
 649                         CPPUNIT_ASSERT( it.key() == i );
 650                         CPPUNIT_ASSERT( it.val().m_val == i * 3 );
 651                     }
 652
 653                     l.clear();
 654                     CPPUNIT_ASSERT( l.empty() );
 655
 656                     // Const iterator
 657                     for ( int i = 0; i < nCount; ++i )
 658                         CPPUNIT_ASSERT( l.insert(i, i * 7) != l.end() );
 659
 660                     i = 0;
 661                     const OrdList& rl = l;
 662                     for ( typename OrdList::const_iterator iter = rl.begin(), itEnd = rl.end(); iter != itEnd; ++iter, ++i ) {
 663                         CPPUNIT_ASSERT( iter.key() == i );
 664                         CPPUNIT_ASSERT( iter->first == i );
 665                         CPPUNIT_ASSERT( (*iter).first == i );
 666
 667                         CPPUNIT_ASSERT( iter.val().m_val == i * 7 );
 668                         CPPUNIT_ASSERT( iter->second.m_val == i * 7 );
 669                         CPPUNIT_ASSERT( (*iter).second.m_val == i * 7 );
 670                         // it.val().m_val = i * 3    ; // error: const-iterator
 671                     }
 672
 673                     l.clear();
 674                     CPPUNIT_ASSERT( l.empty() );
 675                 }
 676
 677             }
 678         }
 679
 680         template <class UnordList>
 681         void nogc_unord_test()
 682         {
 683             typedef typename UnordList::value_type    value_type;
 684             typedef typename UnordList::iterator      iterator;
 685
 686             {
 687                 UnordList l;
 688                 iterator it;
 689
 690                 CPPUNIT_ASSERT( l.empty() );
 691
 692                 // insert / find test
 693                 CPPUNIT_ASSERT( l.contains( 100 ) == l.end() );
 694                 CPPUNIT_ASSERT( l.insert( 100 ) != l.end() );
 695                 CPPUNIT_ASSERT( !l.empty() );
 696                 it = l.contains( 100 );
 697                 CPPUNIT_ASSERT( it != l.end() );
 698                 CPPUNIT_ASSERT( it.key() == 100 );
 699                 CPPUNIT_ASSERT( it.val().m_val == 0 );
 700
 701                 CPPUNIT_ASSERT( l.contains( 50, eq<key_type>() ) == l.end() );
 702                 CPPUNIT_ASSERT( l.insert( 50, 500 ) != l.end());
 703                 it = l.contains( 50 );
 704                 CPPUNIT_ASSERT( it != l.end() );
 705                 CPPUNIT_ASSERT( it.key() == 50 );
 706                 CPPUNIT_ASSERT( it.val().m_val == 500 );
 707
 708                 CPPUNIT_ASSERT( l.insert( 50, 5 ) == l.end() );
 709                 it = l.contains( 50 );
 710                 CPPUNIT_ASSERT( it != l.end() );
 711                 CPPUNIT_ASSERT( it.key() == 50 );
 712                 CPPUNIT_ASSERT( it.val().m_val == 500 );
 713                 CPPUNIT_ASSERT( !l.empty() );
 714
 715                 CPPUNIT_ASSERT( l.contains( 150 ) == l.end() );
 716                 CPPUNIT_ASSERT( l.insert_with( 150, insert_functor() ) != l.end() );
 717                 it = l.contains( 150 );
 718                 CPPUNIT_ASSERT( it != l.end() );
 719                 CPPUNIT_ASSERT( it.key() == 150 );
 720                 CPPUNIT_ASSERT( it.val().m_val == 1500 );
 721                 it = l.contains( 100 );
 722                 CPPUNIT_ASSERT( it != l.end() );
 723                 CPPUNIT_ASSERT( it.key() == 100 );
 724                 CPPUNIT_ASSERT( it.val().m_val == 0 );
 725                 it = l.contains( 50 );
 726                 CPPUNIT_ASSERT( it != l.end() );
 727                 CPPUNIT_ASSERT( it.key() == 50 );
 728                 CPPUNIT_ASSERT( it.val().m_val == 500 );
 729                 it.val().m_val = 25;
 730                 it = l.contains( 50 );
 731                 CPPUNIT_ASSERT( it != l.end() );
 732                 CPPUNIT_ASSERT( it.key() == 50 );
 733                 CPPUNIT_ASSERT( it.val().m_val == 25 );
 734                 CPPUNIT_ASSERT( !l.empty() );
 735
 736                 // update existing item
 737                 std::pair<iterator, bool> updateResult;
 738                 updateResult = l.update( 100 );
 739                 CPPUNIT_ASSERT( !updateResult.second );
 740                 CPPUNIT_ASSERT( updateResult.first.key() == 100 );
 741                 CPPUNIT_ASSERT( updateResult.first.val().m_val == 0   );
 742                 updateResult.first.val().m_val = 5;
 743                 it = l.contains( 100 );
 744                 CPPUNIT_ASSERT( it != l.end() );
 745                 CPPUNIT_ASSERT( it.key() == 100 );
 746                 CPPUNIT_ASSERT( it.val().m_val == 5 );
 747
 748                 CPPUNIT_ASSERT( !l.empty() );
 749
 750                 // update new item
 751                 updateResult = l.update( 1000 );
 752                 CPPUNIT_ASSERT( updateResult.second );
 753                 CPPUNIT_ASSERT( updateResult.first.key() == 1000 );
 754                 CPPUNIT_ASSERT( updateResult.first.val().m_val == 0   );
 755                 updateResult.first.val().m_val = 33;
 756                 updateResult = l.update( 1000 );
 757                 CPPUNIT_ASSERT( !updateResult.second );
 758                 CPPUNIT_ASSERT( updateResult.first.key() == 1000 );
 759                 CPPUNIT_ASSERT( updateResult.first.val().m_val == 33   );
 760
 761                 // clear test
 762                 l.clear();
 763                 CPPUNIT_ASSERT( l.empty() );
 764
 765                 // insert test
 766                 CPPUNIT_ASSERT( l.emplace( 501 ) != l.end());
 767                 CPPUNIT_ASSERT( l.emplace( 251, 152 ) != l.end());
 768
 769                 // insert failed - such key exists
 770                 CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end());
 771                 CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end());
 772
 773                 it = l.contains(501);
 774                 CPPUNIT_ASSERT( it != l.end() );
 775                 CPPUNIT_ASSERT( it.key() == 501 );
 776                 CPPUNIT_ASSERT( it.val().m_val == 0 );
 777
 778                 it = l.contains(251);
 779                 CPPUNIT_ASSERT( it != l.end() );
 780                 CPPUNIT_ASSERT( it.key() == 251 );
 781                 CPPUNIT_ASSERT( it.val().m_val == 152 );
 782
 783                 l.clear();
 784                 CPPUNIT_ASSERT( l.empty() );
 785
 786                 // Iterator test
 787                 {
 788                     int nCount = 100;
 789                     for ( int i = 0; i < nCount; ++i )
 790                         CPPUNIT_ASSERT( l.insert(i, i * 2 ) != l.end() );
 791
 792                     {
 793                         typename UnordList::iterator it( l.begin() );
 794                         typename UnordList::const_iterator cit( l.cbegin() );
 795                         CPPUNIT_CHECK( it == cit );
 796                         CPPUNIT_CHECK( it != l.end() );
 797                         CPPUNIT_CHECK( it != l.cend() );
 798                         CPPUNIT_CHECK( cit != l.end() );
 799                         CPPUNIT_CHECK( cit != l.cend() );
 800                         ++it;
 801                         CPPUNIT_CHECK( it != cit );
 802                         CPPUNIT_CHECK( it != l.end() );
 803                         CPPUNIT_CHECK( it != l.cend() );
 804                         CPPUNIT_CHECK( cit != l.end() );
 805                         CPPUNIT_CHECK( cit != l.cend() );
 806                         ++cit;
 807                         CPPUNIT_CHECK( it == cit );
 808                         CPPUNIT_CHECK( it != l.end() );
 809                         CPPUNIT_CHECK( it != l.cend() );
 810                         CPPUNIT_CHECK( cit != l.end() );
 811                         CPPUNIT_CHECK( cit != l.cend() );
 812                     }
 813
 814                     int i = 0;
 815                     for ( typename UnordList::iterator iter = l.begin(), itEnd = l.end(); iter != itEnd; ++iter, ++i ) {
 816                         CPPUNIT_ASSERT( iter.key() == i );
 817                         CPPUNIT_ASSERT( iter->first == i );
 818                         CPPUNIT_ASSERT( (*iter).first == i );
 819
 820                         CPPUNIT_ASSERT( iter.val().m_val == i * 2 );
 821                         CPPUNIT_ASSERT( iter->second.m_val == i * 2 );
 822                         CPPUNIT_ASSERT( (*iter).second.m_val == i * 2 );
 823
 824                         iter.val().m_val = i * 3;
 825                     }
 826
 827                     // Check that we have visited all items
 828                     for ( int i = 0; i < nCount; ++i ) {
 829                         it = l.contains( i );
 830                         CPPUNIT_ASSERT( it != l.end() );
 831                         CPPUNIT_ASSERT( it.key() == i );
 832                         CPPUNIT_ASSERT( it.val().m_val == i * 3 );
 833                     }
 834
 835                     l.clear();
 836                     CPPUNIT_ASSERT( l.empty() );
 837
 838                     // Const iterator
 839                     for ( int i = 0; i < nCount; ++i )
 840                         CPPUNIT_ASSERT( l.insert(i, i * 7) != l.end() );
 841
 842                     i = 0;
 843                     const UnordList& rl = l;
 844                     for ( typename UnordList::const_iterator iter = rl.begin(), itEnd = rl.end(); iter != itEnd; ++iter, ++i ) {
 845                         CPPUNIT_ASSERT( iter.key() == i );
 846                         CPPUNIT_ASSERT( iter->first == i );
 847                         CPPUNIT_ASSERT( (*iter).first == i );
 848
 849                         CPPUNIT_ASSERT( iter.val().m_val == i * 7 );
 850                         CPPUNIT_ASSERT( iter->second.m_val == i * 7 );
 851                         CPPUNIT_ASSERT( (*iter).second.m_val == i * 7 );
 852                         // it.val().m_val = i * 3    ; // error: const-iterator
 853                     }
 854
 855                     l.clear();
 856                     CPPUNIT_ASSERT( l.empty() );
 857                 }
 858
 859             }
 860         }
 861
 862
 863         void HP_cmp();
 864         void HP_less();
 865         void HP_cmpmix();
 866         void HP_ic();
 867
 868         void DHP_cmp();
 869         void DHP_less();
 870         void DHP_cmpmix();
 871         void DHP_ic();
 872
 873         void RCU_GPI_cmp();
 874         void RCU_GPI_less();
 875         void RCU_GPI_cmpmix();
 876         void RCU_GPI_ic();
 877
 878         void RCU_GPB_cmp();
 879         void RCU_GPB_less();
 880         void RCU_GPB_cmpmix();
 881         void RCU_GPB_ic();
 882
 883         void RCU_GPT_cmp();
 884         void RCU_GPT_less();
 885         void RCU_GPT_cmpmix();
 886         void RCU_GPT_ic();
 887
 888         void RCU_SHB_cmp();
 889         void RCU_SHB_less();
 890         void RCU_SHB_cmpmix();
 891         void RCU_SHB_ic();
 892
 893         void RCU_SHT_cmp();
 894         void RCU_SHT_less();
 895         void RCU_SHT_cmpmix();
 896         void RCU_SHT_ic();
 897
 898         void NOGC_cmp();
 899         void NOGC_less();
 900         void NOGC_cmpmix();
 901         void NOGC_ic();
 902
 903         void NOGC_cmp_unord();
 904         void NOGC_less_unord();
 905         void NOGC_equal_to_unord();
 906         void NOGC_cmpmix_unord();
 907         void NOGC_ic_unord();
 908
 909         CPPUNIT_TEST_SUITE(LazyKVListTestHeader)
 910             CPPUNIT_TEST(HP_cmp)
 911             CPPUNIT_TEST(HP_less)
 912             CPPUNIT_TEST(HP_cmpmix)
 913             CPPUNIT_TEST(HP_ic)
 914
 915             CPPUNIT_TEST(DHP_cmp)
 916             CPPUNIT_TEST(DHP_less)
 917             CPPUNIT_TEST(DHP_cmpmix)
 918             CPPUNIT_TEST(DHP_ic)
 919
 920             CPPUNIT_TEST(RCU_GPI_cmp)
 921             CPPUNIT_TEST(RCU_GPI_less)
 922             CPPUNIT_TEST(RCU_GPI_cmpmix)
 923             CPPUNIT_TEST(RCU_GPI_ic)
 924
 925             CPPUNIT_TEST(RCU_GPB_cmp)
 926             CPPUNIT_TEST(RCU_GPB_less)
 927             CPPUNIT_TEST(RCU_GPB_cmpmix)
 928             CPPUNIT_TEST(RCU_GPB_ic)
 929
 930             CPPUNIT_TEST(RCU_GPT_cmp)
 931             CPPUNIT_TEST(RCU_GPT_less)
 932             CPPUNIT_TEST(RCU_GPT_cmpmix)
 933             CPPUNIT_TEST(RCU_GPT_ic)
 934
 935             CPPUNIT_TEST(RCU_SHB_cmp)
 936             CPPUNIT_TEST(RCU_SHB_less)
 937             CPPUNIT_TEST(RCU_SHB_cmpmix)
 938             CPPUNIT_TEST(RCU_SHB_ic)
 939
 940             CPPUNIT_TEST(RCU_SHT_cmp)
 941             CPPUNIT_TEST(RCU_SHT_less)
 942             CPPUNIT_TEST(RCU_SHT_cmpmix)
 943             CPPUNIT_TEST(RCU_SHT_ic)
 944
 945             CPPUNIT_TEST(NOGC_cmp)
 946             CPPUNIT_TEST(NOGC_less)
 947             CPPUNIT_TEST(NOGC_cmpmix)
 948             CPPUNIT_TEST(NOGC_ic)
 949
 950             CPPUNIT_TEST(NOGC_cmp_unord)
 951             CPPUNIT_TEST(NOGC_less_unord)
 952             CPPUNIT_TEST(NOGC_equal_to_unord)
 953             CPPUNIT_TEST(NOGC_cmpmix_unord)
 954             CPPUNIT_TEST(NOGC_ic_unord)
 955
 956         CPPUNIT_TEST_SUITE_END()
 957     };
 958
 959 }   // namespace ordlist
 960
 961 #endif // #ifndef CDSTEST_HDR_LAZY_KV_H