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