tests/test-hdr/set/hdr_set.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDSTEST_HDR_SET_H
   4 #define __CDSTEST_HDR_SET_H
   5
   6 #include "cppunit/cppunit_proxy.h"
   7 #include "size_check.h"
   8
   9 #include <cds/opt/hash.h>
  10 #include <cds/os/timer.h>
  11 #include <functional>   // ref
  12 #include <algorithm>    // random_shuffle
  13
  14 // forward namespace declaration
  15 namespace cds {
  16     namespace container {}
  17     namespace opt {}
  18 }
  19
  20 namespace set {
  21     using misc::check_size;
  22
  23     namespace cc = cds::container;
  24     namespace co = cds::opt;
  25
  26
  27     class HashSetHdrTest: public CppUnitMini::TestCase
  28     {
  29     public:
  30         struct stat
  31         {
  32             unsigned int nFindCount     ;   // count of find-functor calling
  33             unsigned int nEnsureNewCount;
  34             unsigned int nEnsureCount;
  35
  36             stat()
  37             {
  38                 memset( this, 0, sizeof(*this));
  39             }
  40
  41             void copy( stat const& s )
  42             {
  43                 nFindCount = s.nFindCount;
  44                 nEnsureCount = s.nEnsureCount;
  45                 nEnsureNewCount = s.nEnsureNewCount;
  46             }
  47         };
  48
  49         struct item: public stat
  50         {
  51             int nKey;
  52             int nVal;
  53
  54             item()
  55             {}
  56
  57             item( int key )
  58                 : nKey( key )
  59                 , nVal( key )
  60             {}
  61
  62             item (int key, int val )
  63                 : nKey(key)
  64                 , nVal( val )
  65             {}
  66
  67             item( std::pair<int,int> const& p )
  68                 : nKey( p.first )
  69                 , nVal( p.second )
  70             {}
  71
  72             item( item const& i )
  73                 : nKey( i.nKey )
  74                 , nVal( i.nVal )
  75             {}
  76
  77             item& operator=(item const& i)
  78             {
  79                 nKey = i.nKey;
  80                 nVal = i.nVal;
  81                 stat::copy(i);
  82
  83                 return *this;
  84             }
  85
  86             item( item&& i )
  87                 : nKey( i.nKey )
  88                 , nVal( i.nVal )
  89             {}
  90
  91             //item& operator=(item&& i)
  92             //{
  93             //    nKey = i.nKey;
  94             //    nVal = i.nVal;
  95             //    return *this;
  96             //}
  97
  98             int key() const
  99             {
 100                 return nKey;
 101             }
 102
 103             int val() const
 104             {
 105                 return nVal;
 106             }
 107         };
 108
 109         struct hash_int {
 110             size_t operator()( int i ) const
 111             {
 112                 return co::v::hash<int>()( i );
 113             }
 114
 115             size_t operator()( std::pair<int,int> const& i ) const
 116             {
 117                 return co::v::hash<int>()( i.first );
 118             }
 119
 120             template <typename Item>
 121             size_t operator()( Item const& i ) const
 122             {
 123                 return (*this)( i.key() );
 124             }
 125         };
 126
 127         struct simple_item_counter {
 128             size_t  m_nCount;
 129
 130             simple_item_counter()
 131                 : m_nCount(0)
 132             {}
 133
 134             size_t operator ++()
 135             {
 136                 return ++m_nCount;
 137             }
 138
 139             size_t operator --()
 140             {
 141                 return --m_nCount;
 142             }
 143
 144             void reset()
 145             {
 146                 m_nCount = 0;
 147             }
 148
 149             operator size_t() const
 150             {
 151                 return m_nCount;
 152             }
 153         };
 154
 155         template <typename T>
 156         struct less
 157         {
 158             bool operator ()(const T& v1, const T& v2 ) const
 159             {
 160                 return v1.key() < v2.key();
 161             }
 162
 163             template <typename Q>
 164             bool operator ()(const T& v1, const Q& v2 ) const
 165             {
 166                 return v1.key() < v2;
 167             }
 168
 169             template <typename Q>
 170             bool operator ()(const Q& v1, const T& v2 ) const
 171             {
 172                 return v1 < v2.key();
 173             }
 174
 175             bool operator ()( std::pair<int, int> const& v1, const T& v2 ) const
 176             {
 177                 return v1.first < v2.key();
 178             }
 179
 180             bool operator ()(const T& v1, std::pair<int, int> const& v2 ) const
 181             {
 182                 return v1.key() < v2.first;
 183             }
 184         };
 185
 186         struct other_item {
 187             int nKey;
 188
 189             other_item( int key )
 190                 : nKey(key)
 191             {}
 192
 193             int key() const
 194             {
 195                 return nKey;
 196             }
 197         };
 198
 199         struct other_less
 200         {
 201             template <typename T>
 202             bool operator ()(T const& v1, other_item const& v2 ) const
 203             {
 204                 return v1.key() < v2.nKey;
 205             }
 206             template <typename T>
 207             bool operator ()(other_item const& v1, T const& v2 ) const
 208             {
 209                 return v1.nKey < v2.key();
 210             }
 211         };
 212
 213         template <typename T>
 214         struct cmp {
 215             int operator ()(const T& v1, const T& v2 ) const
 216             {
 217                 if ( v1.key() < v2.key() )
 218                     return -1;
 219                 return v1.key() > v2.key() ? 1 : 0;
 220             }
 221
 222             template <typename Q>
 223             int operator ()(const T& v1, const Q& v2 ) const
 224             {
 225                 if ( v1.key() < v2 )
 226                     return -1;
 227                 return v1.key() > v2 ? 1 : 0;
 228             }
 229
 230             template <typename Q>
 231             int operator ()(const Q& v1, const T& v2 ) const
 232             {
 233                 if ( v1 < v2.key() )
 234                     return -1;
 235                 return v1 > v2.key() ? 1 : 0;
 236             }
 237
 238             int operator()( std::pair<int,int> const& v1, T const& v2 ) const
 239             {
 240                 if ( v1.first < v2.key() )
 241                     return -1;
 242                 return v1.first > v2.key() ? 1 : 0;
 243             }
 244
 245             int operator()( T const& v1, std::pair<int,int> const& v2 ) const
 246             {
 247                 if ( v1.key() < v2.first )
 248                     return -1;
 249                 return v1.key() > v2.first ? 1 : 0;
 250             }
 251         };
 252
 253         template <typename T>
 254         struct equal
 255         {
 256             bool operator ()(const T& v1, const T& v2 ) const
 257             {
 258                 return v1.key() == v2.key();
 259             }
 260
 261             template <typename Q>
 262             bool operator ()(const T& v1, const Q& v2 ) const
 263             {
 264                 return v1.key() == v2;
 265             }
 266
 267             template <typename Q>
 268             bool operator ()(const Q& v1, const T& v2 ) const
 269             {
 270                 return v1 == v2.key();
 271             }
 272
 273             bool operator ()( std::pair<int, int> const& v1, const T& v2 ) const
 274             {
 275                 return v1.first == v2.key();
 276             }
 277
 278             bool operator ()(const T& v1, std::pair<int, int> const& v2 ) const
 279             {
 280                 return v1.key() == v2.first;
 281             }
 282         };
 283
 284         struct find_functor
 285         {
 286             template <typename Item, typename T>
 287             void operator()( Item& i, T& /*val*/ ) const
 288             {
 289                 ++i.nFindCount;
 290             }
 291             template <typename Item, typename T>
 292             void operator()( Item& i, T const& /*val*/ ) const
 293             {
 294                 ++i.nFindCount;
 295             }
 296         };
 297
 298         template <typename Item>
 299         struct copy_found
 300         {
 301             Item    m_found;
 302
 303             template <typename T>
 304             void operator()( Item& i, T& /*val*/ )
 305             {
 306                 m_found = i;
 307             }
 308
 309             void operator()( Item const& i )
 310             {
 311                 m_found = i;
 312             }
 313         };
 314
 315         struct insert_functor
 316         {
 317             template <typename Item>
 318             void operator()(Item& i )
 319             {
 320                 i.nVal = i.nKey * 100;
 321             }
 322         };
 323
 324         template <typename Item, typename Q>
 325         static void ensure_func( bool bNew, Item& i, Q& /*val*/ )
 326         {
 327             if ( bNew )
 328                 ++i.nEnsureNewCount;
 329             else
 330                 ++i.nEnsureCount;
 331         }
 332
 333         struct ensure_functor
 334         {
 335             template <typename Item, typename Q>
 336             void operator()( bool bNew, Item& i, Q& val )
 337             {
 338                 ensure_func( bNew, i, val );
 339             }
 340         };
 341
 342         template <class Set>
 343         void test_int()
 344         {
 345             Set s( 100, 4 );
 346             test_int_with( s );
 347
 348             // extract/get test
 349             CPPUNIT_ASSERT( s.empty() );
 350             {
 351                 const int nLimit = 100;
 352                 typename Set::guarded_ptr gp;
 353                 int arrRandom[nLimit];
 354                 for ( int i = 0; i < nLimit; ++i )
 355                     arrRandom[i] = i;
 356                 std::random_shuffle( arrRandom, arrRandom + nLimit );
 357
 358                 for ( int i = 0; i < nLimit; ++i )
 359                     CPPUNIT_ASSERT( s.insert( arrRandom[i] ));
 360
 361                 for ( int i = 0; i < nLimit; ++i ) {
 362                     int nKey = arrRandom[i];
 363                     gp = s.get( nKey );
 364                     CPPUNIT_ASSERT( gp );
 365                     CPPUNIT_ASSERT( !gp.empty());
 366                     CPPUNIT_CHECK( gp->nKey == nKey );
 367                     CPPUNIT_CHECK( gp->nVal == nKey );
 368
 369                     gp = s.extract( nKey );
 370                     CPPUNIT_ASSERT( gp );
 371                     CPPUNIT_ASSERT( !gp.empty());
 372                     CPPUNIT_CHECK( gp->nKey == nKey );
 373                     CPPUNIT_CHECK( gp->nVal == nKey );
 374                     CPPUNIT_CHECK( !s.get(nKey));
 375
 376                     gp = s.extract( nKey );
 377                     CPPUNIT_CHECK( !gp );
 378                     CPPUNIT_CHECK( gp.empty());
 379                 }
 380                 CPPUNIT_ASSERT( s.empty() );
 381
 382
 383                 for ( int i = 0; i < nLimit; ++i )
 384                     CPPUNIT_ASSERT( s.insert( arrRandom[i] ));
 385
 386                 for ( int i = 0; i < nLimit; ++i ) {
 387                     int nKey = arrRandom[i];
 388                     gp = s.get_with( other_item( nKey ), other_less() );
 389                     CPPUNIT_ASSERT( gp );
 390                     CPPUNIT_ASSERT( !gp.empty());
 391                     CPPUNIT_CHECK( gp->nKey == nKey );
 392                     CPPUNIT_CHECK( gp->nVal == nKey );
 393
 394                     gp = s.extract_with( other_item( nKey ), other_less() );
 395                     CPPUNIT_ASSERT( gp );
 396                     CPPUNIT_ASSERT( !gp.empty());
 397                     CPPUNIT_CHECK( gp->nKey == nKey );
 398                     CPPUNIT_CHECK( gp->nVal == nKey );
 399                     gp = s.get_with( other_item( nKey ), other_less() );
 400                     CPPUNIT_CHECK( !gp );
 401
 402                     CPPUNIT_CHECK( !s.extract_with(other_item(nKey), other_less() ));
 403                     CPPUNIT_CHECK( gp.empty());
 404                 }
 405                 CPPUNIT_ASSERT( s.empty() );
 406             }
 407
 408             // iterator test
 409             test_iter<Set>();
 410         }
 411
 412         template <class Set>
 413         void test_int_rcu()
 414         {
 415             Set s( 100, 4 );
 416             test_int_with( s );
 417
 418             // extract/get test
 419             {
 420                 typedef typename Set::gc    rcu;
 421                 typedef typename Set::rcu_lock rcu_lock;
 422                 typedef typename Set::value_type value_type;
 423                 typename Set::exempt_ptr ep;
 424
 425                 static size_t const nLimit = 100;
 426                 int arr[nLimit];
 427                 for ( size_t i = 0; i < nLimit; ++i )
 428                     arr[i] = (int) i;
 429                 std::random_shuffle( arr, arr + nLimit );
 430
 431                 for ( size_t i = 0; i < nLimit; ++i )
 432                     CPPUNIT_ASSERT( s.insert( arr[i] ));
 433
 434                 for ( size_t i = 0; i < nLimit; i += 2 ) {
 435                     value_type * pVal;
 436                     int nKey = arr[i];
 437                     {
 438                         rcu_lock l;
 439                         pVal = s.get( nKey );
 440                         CPPUNIT_ASSERT( pVal != nullptr );
 441                         CPPUNIT_CHECK( pVal->nKey == nKey );
 442                         CPPUNIT_CHECK( pVal->nVal == nKey );
 443
 444                         ep = s.extract( nKey );
 445                         CPPUNIT_ASSERT( ep );
 446                         CPPUNIT_ASSERT( !ep.empty() );
 447                         CPPUNIT_CHECK( pVal->nKey == ep->nKey );
 448                         CPPUNIT_CHECK( pVal->nVal == (*ep).nVal );
 449                     }
 450                     ep.release();
 451                     {
 452                         rcu_lock l;
 453                         CPPUNIT_CHECK( s.get( nKey ) == nullptr );
 454                         ep = s.extract( nKey );
 455                         CPPUNIT_CHECK( !ep );
 456                         CPPUNIT_CHECK( ep.empty() );
 457
 458                         nKey = arr[i+1];
 459                         pVal = s.get_with( other_item(nKey), other_less() );
 460                         CPPUNIT_ASSERT( pVal != nullptr );
 461                         CPPUNIT_CHECK( pVal->nKey == nKey );
 462                         CPPUNIT_CHECK( pVal->nVal == nKey );
 463
 464                         ep = s.extract_with( other_item( nKey ), other_less() );
 465                         CPPUNIT_ASSERT( ep );
 466                         CPPUNIT_ASSERT( !ep.empty() );
 467                         CPPUNIT_CHECK( pVal->nKey == ep->nKey );
 468                         CPPUNIT_CHECK( pVal->nVal == (*ep).nVal );
 469                     }
 470                     ep.release();
 471                     {
 472                         rcu_lock l;
 473                         CPPUNIT_CHECK( s.get_with( other_item( nKey ), other_less() ) == nullptr );
 474                         CPPUNIT_CHECK( !s.extract_with( other_item(nKey), other_less() ));
 475                         CPPUNIT_CHECK( ep.empty() );
 476                     }
 477                 }
 478                 CPPUNIT_CHECK( s.empty() );
 479                 CPPUNIT_CHECK( check_size( s, 0 ));
 480                 {
 481                     rcu_lock l;
 482                     CPPUNIT_CHECK( s.get( int( nLimit / 2 ) ) == nullptr );
 483                     ep = s.extract( int( nLimit / 2 ) );
 484                     CPPUNIT_CHECK( !ep );
 485                     CPPUNIT_CHECK( ep.empty() );
 486                 }
 487             }
 488
 489             // iterator test
 490             test_iter<Set>();
 491         }
 492
 493         template <class Set>
 494         void test_int_with( Set& s)
 495         {
 496             typedef typename Set::value_type    value_type;
 497
 498             item itm;
 499             int key;
 500
 501             // insert/find test
 502             CPPUNIT_ASSERT( !s.find( 10 ) );
 503             CPPUNIT_ASSERT( s.insert( 10 ));
 504             CPPUNIT_ASSERT( !s.empty() );
 505             CPPUNIT_ASSERT( check_size( s, 1 ));
 506             CPPUNIT_ASSERT( s.find( 10 ) );
 507
 508             CPPUNIT_ASSERT( !s.insert( 10 ));
 509             CPPUNIT_ASSERT( !s.empty() );
 510             CPPUNIT_ASSERT( check_size( s, 1 ));
 511
 512             CPPUNIT_ASSERT( !s.find_with( 20, less<value_type>() ) );
 513             CPPUNIT_ASSERT( s.insert( std::make_pair(20, 25) ));
 514             CPPUNIT_ASSERT( !s.empty() );
 515             CPPUNIT_ASSERT( check_size( s, 2 ));
 516             CPPUNIT_ASSERT( s.find_with( 10, less<value_type>() ) );
 517             CPPUNIT_ASSERT( s.find( key = 20 ) );
 518             CPPUNIT_ASSERT( s.find_with( key, less<value_type>(), find_functor() ) );
 519             {
 520                 copy_found<item> f;
 521                 key = 20;
 522                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 523                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 524                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 525                 CPPUNIT_ASSERT( f.m_found.nFindCount == 1 );
 526             }
 527             CPPUNIT_ASSERT( s.find( key, find_functor() ) );
 528             {
 529                 copy_found<item> f;
 530                 key = 20;
 531                 CPPUNIT_ASSERT( s.find_with( key, less<value_type>(), std::ref( f ) ) );
 532                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 533                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 534                 CPPUNIT_ASSERT( f.m_found.nFindCount == 2 );
 535             }
 536             CPPUNIT_ASSERT( !s.empty() );
 537             CPPUNIT_ASSERT( check_size( s, 2 ));
 538
 539             CPPUNIT_ASSERT( !s.find( 25 ) );
 540             CPPUNIT_ASSERT( s.insert( std::make_pair(25, -1), insert_functor() ));
 541             CPPUNIT_ASSERT( !s.empty() );
 542             CPPUNIT_ASSERT( check_size( s, 3 ));
 543             {
 544                 copy_found<item> f;
 545                 key = 25;
 546                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 547                 CPPUNIT_ASSERT( f.m_found.nKey == 25 );
 548                 CPPUNIT_ASSERT( f.m_found.nVal == 2500 );
 549             }
 550
 551             // ensure test
 552             key = 10;
 553             {
 554                 copy_found<item> f;
 555                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 556                 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
 557                 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
 558                 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 0 );
 559                 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 0 );
 560             }
 561             std::pair<bool, bool> ensureResult = s.ensure( key, ensure_functor() );
 562             CPPUNIT_ASSERT( ensureResult.first && !ensureResult.second );
 563             CPPUNIT_ASSERT( !s.empty() );
 564             CPPUNIT_ASSERT( check_size( s, 3 ));
 565             {
 566                 copy_found<item> f;
 567                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 568                 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
 569                 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
 570                 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 1 );
 571                 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 0 );
 572             }
 573
 574             ensureResult = s.ensure( std::make_pair(13, 1300), ensure_functor() );
 575             CPPUNIT_ASSERT( ensureResult.first && ensureResult.second );
 576             CPPUNIT_ASSERT( !s.empty() );
 577             CPPUNIT_ASSERT( check_size( s, 4 ));
 578             {
 579                 copy_found<item> f;
 580                 key = 13;
 581                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 582                 CPPUNIT_ASSERT( f.m_found.nKey == 13 );
 583                 CPPUNIT_ASSERT( f.m_found.nVal == 1300 );
 584                 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 0 );
 585                 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 1 );
 586             }
 587
 588             // erase test
 589             CPPUNIT_ASSERT( s.erase(13) );
 590             CPPUNIT_ASSERT( !s.find( 13 ));
 591             CPPUNIT_ASSERT( !s.empty() );
 592             CPPUNIT_ASSERT( check_size( s, 3 ));
 593             CPPUNIT_ASSERT( !s.erase(13) );
 594             CPPUNIT_ASSERT( !s.empty() );
 595             CPPUNIT_ASSERT( check_size( s, 3 ));
 596
 597             CPPUNIT_ASSERT( s.find( 10 ));
 598             CPPUNIT_ASSERT( s.erase_with( 10, less<value_type>() ));
 599             CPPUNIT_ASSERT( !s.find( 10 ));
 600             CPPUNIT_ASSERT( !s.empty() );
 601             CPPUNIT_ASSERT( check_size( s, 2 ));
 602             CPPUNIT_ASSERT( !s.erase_with(10, less<value_type>()) );
 603             CPPUNIT_ASSERT( !s.empty() );
 604             CPPUNIT_ASSERT( check_size( s, 2 ));
 605
 606             CPPUNIT_ASSERT( s.find(20) );
 607             {
 608                 copy_found<item> f;
 609                 CPPUNIT_ASSERT( s.erase( 20, std::ref( f ) ) );
 610                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 611                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 612
 613                 CPPUNIT_ASSERT( s.insert(235))
 614                     CPPUNIT_ASSERT( s.erase_with( 235, less<value_type>(), std::ref( f ) ) );
 615                 CPPUNIT_ASSERT( f.m_found.nKey == 235 );
 616                 CPPUNIT_ASSERT( f.m_found.nVal == 235 );
 617             }
 618             CPPUNIT_ASSERT( !s.find( 20 ));
 619             CPPUNIT_ASSERT( !s.empty() );
 620             CPPUNIT_ASSERT( check_size( s, 1 ));
 621
 622             s.clear();
 623             CPPUNIT_ASSERT( s.empty() );
 624             CPPUNIT_ASSERT( check_size( s, 0 ));
 625
 626             // emplace test
 627             CPPUNIT_ASSERT( s.emplace( 151 )) ;  // key = 151,  val = 151
 628             CPPUNIT_ASSERT( s.emplace( 174, 471 )) ;    // key = 174, val = 471
 629             CPPUNIT_ASSERT( s.emplace( std::make_pair( 190, 91 ) )) ; // key == 190, val = 91
 630             CPPUNIT_ASSERT( !s.empty() );
 631             CPPUNIT_ASSERT( check_size( s, 3 ));
 632
 633             CPPUNIT_ASSERT( s.find(151));
 634             CPPUNIT_ASSERT( s.find_with(174, less<value_type>()));
 635             CPPUNIT_ASSERT( s.find(190));
 636
 637             {
 638                 copy_found<item> f;
 639                 key = 151;
 640                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 641                 CPPUNIT_ASSERT( f.m_found.nKey == 151 );
 642                 CPPUNIT_ASSERT( f.m_found.nVal == 151 );
 643
 644                 key = 174;
 645                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 646                 CPPUNIT_ASSERT( f.m_found.nKey == 174 );
 647                 CPPUNIT_ASSERT( f.m_found.nVal == 471 );
 648
 649                 key = 190;
 650                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 651                 CPPUNIT_ASSERT( f.m_found.nKey == 190 );
 652                 CPPUNIT_ASSERT( f.m_found.nVal == 91 );
 653             }
 654
 655             s.clear();
 656             CPPUNIT_ASSERT( s.empty() );
 657             CPPUNIT_ASSERT( check_size( s, 0 ));
 658         }
 659
 660
 661         template <class Set>
 662         void test_int_nogc()
 663         {
 664             typedef typename Set::value_type        value_type;
 665             typedef typename Set::iterator          iterator;
 666             typedef typename Set::const_iterator    const_iterator;
 667
 668             {
 669                 Set s( 52, 4 );
 670                 iterator it;
 671
 672                 CPPUNIT_ASSERT( s.empty() );
 673                 CPPUNIT_ASSERT( check_size( s, 0 ));
 674
 675                 // insert
 676                 it = s.insert( 10 );
 677                 CPPUNIT_ASSERT( it != s.end() );
 678                 CPPUNIT_ASSERT( it->key() == 10 );
 679                 CPPUNIT_ASSERT( it->val() == 10 );
 680                 CPPUNIT_ASSERT( !s.empty() );
 681                 CPPUNIT_ASSERT( check_size( s, 1 ));
 682                 CPPUNIT_ASSERT( s.insert( 10 ) == s.end() );
 683
 684                 it = s.insert( std::make_pair( 50, 25 ));
 685                 CPPUNIT_ASSERT( it != s.end() );
 686                 CPPUNIT_ASSERT( it->key() == 50 );
 687                 CPPUNIT_ASSERT( it->val() == 25 );
 688                 CPPUNIT_ASSERT( !s.empty() );
 689                 CPPUNIT_ASSERT( check_size( s, 2 ));
 690                 CPPUNIT_ASSERT( s.insert( 50 ) == s.end() );
 691
 692                 // ensure
 693                 std::pair< iterator, bool>  ensureResult;
 694                 ensureResult = s.ensure( 20 );
 695                 CPPUNIT_ASSERT( ensureResult.first != s.end() );
 696                 CPPUNIT_ASSERT( ensureResult.second  );
 697                 CPPUNIT_ASSERT( ensureResult.first->key() == 20 );
 698                 CPPUNIT_ASSERT( ensureResult.first->val() == 20 );
 699                 CPPUNIT_ASSERT( !s.empty() );
 700                 CPPUNIT_ASSERT( check_size( s, 3 ));
 701
 702                 ensureResult = s.ensure( std::make_pair( 20, 200 ));
 703                 CPPUNIT_ASSERT( ensureResult.first != s.end() );
 704                 CPPUNIT_ASSERT( !ensureResult.second  );
 705                 CPPUNIT_ASSERT( ensureResult.first->key() == 20 );
 706                 CPPUNIT_ASSERT( ensureResult.first->val() == 20 );
 707                 CPPUNIT_ASSERT( !s.empty() );
 708                 CPPUNIT_ASSERT( check_size( s, 3 ));
 709                 ensureResult.first->nVal = 22;
 710
 711                 ensureResult = s.ensure( std::make_pair( 30, 33 ));
 712                 CPPUNIT_ASSERT( ensureResult.first != s.end() );
 713                 CPPUNIT_ASSERT( ensureResult.second  );
 714                 CPPUNIT_ASSERT( ensureResult.first->key() == 30 );
 715                 CPPUNIT_ASSERT( ensureResult.first->val() == 33 );
 716                 CPPUNIT_ASSERT( !s.empty() );
 717                 CPPUNIT_ASSERT( check_size( s, 4 ));
 718
 719                 // find
 720                 it = s.find( 10 );
 721                 CPPUNIT_ASSERT( it != s.end() );
 722                 CPPUNIT_ASSERT( it->key() == 10 );
 723                 CPPUNIT_ASSERT( it->val() == 10 );
 724
 725                 it = s.find_with( 20, less<value_type>() );
 726                 CPPUNIT_ASSERT( it != s.end() );
 727                 CPPUNIT_ASSERT( it->key() == 20 );
 728                 CPPUNIT_ASSERT( it->val() == 22 );
 729
 730                 it = s.find( 30 );
 731                 CPPUNIT_ASSERT( it != s.end() );
 732                 CPPUNIT_ASSERT( it->key() == 30 );
 733                 CPPUNIT_ASSERT( it->val() == 33 );
 734
 735                 it = s.find( 40 );
 736                 CPPUNIT_ASSERT( it == s.end() );
 737
 738                 it = s.find( 50 );
 739                 CPPUNIT_ASSERT( it != s.end() );
 740                 CPPUNIT_ASSERT( it->key() == 50 );
 741                 CPPUNIT_ASSERT( it->val() == 25 );
 742
 743                 // emplace test
 744                 it = s.emplace( 151 ) ;  // key = 151,  val = 151
 745                 CPPUNIT_ASSERT( it != s.end() );
 746                 CPPUNIT_ASSERT( it->key() == 151 );
 747                 CPPUNIT_ASSERT( it->val() == 151 );
 748
 749                 it = s.emplace( 174, 471 ) ; // key == 174, val = 471
 750                 CPPUNIT_ASSERT( it != s.end() );
 751                 CPPUNIT_ASSERT( it->key() == 174 );
 752                 CPPUNIT_ASSERT( it->val() == 471 );
 753
 754                 it = s.emplace( std::make_pair( 190, 91 )) ; // key == 190, val = 91
 755                 CPPUNIT_ASSERT( it != s.end() );
 756                 CPPUNIT_ASSERT( it->key() == 190 );
 757                 CPPUNIT_ASSERT( it->val() == 91 );
 758
 759                 it = s.find( 174 );
 760                 CPPUNIT_ASSERT( it != s.end() );
 761                 CPPUNIT_ASSERT( it->key() == 174 );
 762                 CPPUNIT_ASSERT( it->val() == 471 );
 763
 764                 it = s.find_with( 190, less<value_type>() );
 765                 CPPUNIT_ASSERT( it != s.end() );
 766                 CPPUNIT_ASSERT( it->key() == 190 );
 767                 CPPUNIT_ASSERT( it->val() == 91 );
 768
 769                 it = s.find( 151 );
 770                 CPPUNIT_ASSERT( it != s.end() );
 771                 CPPUNIT_ASSERT( it->key() == 151 );
 772                 CPPUNIT_ASSERT( it->val() == 151 );
 773
 774                 //s.clear();
 775                 //CPPUNIT_ASSERT( s.empty() );
 776                 //CPPUNIT_ASSERT( check_size( s, 0 ));
 777             }
 778
 779             {
 780                 Set s( 52, 4 );
 781
 782                 // iterator test
 783                 for ( int i = 0; i < 500; ++i ) {
 784                     CPPUNIT_ASSERT( s.insert( std::make_pair( i, i * 2) ) != s.end() );
 785                 }
 786                 for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 787                     iterator it2 = it;
 788                     CPPUNIT_CHECK( it2 == it );
 789                     CPPUNIT_CHECK( it2 != itEnd );
 790                     CPPUNIT_ASSERT( (*it).nKey * 2 == it->nVal );
 791                     it->nVal = (*it).nKey;
 792                 }
 793
 794                 Set const& refSet = s;
 795                 for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
 796                     CPPUNIT_ASSERT( (*it).nKey == it->nVal );
 797                 }
 798             }
 799         }
 800
 801         template <class Set>
 802         void test_iter()
 803         {
 804             typedef typename Set::value_type        value_type;
 805             typedef typename Set::iterator          iterator;
 806             typedef typename Set::const_iterator    const_iterator;
 807
 808             Set s( 100, 4 );
 809
 810             const size_t nMaxCount = 500;
 811             for ( int i = 0; size_t(i) < nMaxCount; ++i ) {
 812                 CPPUNIT_ASSERT( s.insert( std::make_pair( i, i * 2) ));
 813             }
 814
 815             {
 816                 typename Set::iterator it( s.begin() );
 817                 typename Set::const_iterator cit( s.cbegin() );
 818                 CPPUNIT_CHECK( it == cit );
 819                 CPPUNIT_CHECK( it != s.end() );
 820                 CPPUNIT_CHECK( it != s.cend() );
 821                 CPPUNIT_CHECK( cit != s.end() );
 822                 CPPUNIT_CHECK( cit != s.cend() );
 823                 ++it;
 824                 CPPUNIT_CHECK( it != cit );
 825                 CPPUNIT_CHECK( it != s.end() );
 826                 CPPUNIT_CHECK( it != s.cend() );
 827                 CPPUNIT_CHECK( cit != s.end() );
 828                 CPPUNIT_CHECK( cit != s.cend() );
 829                 ++cit;
 830                 CPPUNIT_CHECK( it == cit );
 831                 CPPUNIT_CHECK( it != s.end() );
 832                 CPPUNIT_CHECK( it != s.cend() );
 833                 CPPUNIT_CHECK( cit != s.end() );
 834                 CPPUNIT_CHECK( cit != s.cend() );
 835             }
 836
 837             size_t nCount = 0;
 838             for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 839                 CPPUNIT_ASSERT_EX( (*it).nKey * 2 == it->nVal,
 840                     "Step " << nCount << ": Iterator key=" << it->nKey <<  ", value expected=" << it->nKey * 2 << ", value real=" << it->nVal
 841                     );
 842                 it->nVal = (*it).nKey;
 843                 ++nCount;
 844             }
 845             CPPUNIT_ASSERT( nCount == nMaxCount );
 846
 847             nCount = 0;
 848             Set const& refSet = s;
 849             for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
 850                 CPPUNIT_ASSERT_EX( (*it).nKey == it->nVal,
 851                     "Step " << nCount << ": Iterator key=" << it->nKey <<  ", value expected=" << it->nKey << ", value real=" << it->nVal
 852                     );
 853                 ++nCount;
 854             }
 855             CPPUNIT_ASSERT( nCount == nMaxCount );
 856         }
 857
 858         void Michael_HP_cmp();
 859         void Michael_HP_less();
 860         void Michael_HP_cmpmix();
 861
 862         void Michael_DHP_cmp();
 863         void Michael_DHP_less();
 864         void Michael_DHP_cmpmix();
 865
 866         void Michael_RCU_GPI_cmp();
 867         void Michael_RCU_GPI_less();
 868         void Michael_RCU_GPI_cmpmix();
 869
 870         void Michael_RCU_GPT_cmp();
 871         void Michael_RCU_GPT_less();
 872         void Michael_RCU_GPT_cmpmix();
 873
 874         void Michael_RCU_GPB_cmp();
 875         void Michael_RCU_GPB_less();
 876         void Michael_RCU_GPB_cmpmix();
 877
 878         void Michael_RCU_SHT_cmp();
 879         void Michael_RCU_SHT_less();
 880         void Michael_RCU_SHT_cmpmix();
 881
 882         void Michael_RCU_SHB_cmp();
 883         void Michael_RCU_SHB_less();
 884         void Michael_RCU_SHB_cmpmix();
 885
 886         void Michael_nogc_cmp();
 887         void Michael_nogc_less();
 888         void Michael_nogc_cmpmix();
 889
 890         void Lazy_HP_cmp();
 891         void Lazy_HP_less();
 892         void Lazy_HP_cmpmix();
 893
 894         void Lazy_DHP_cmp();
 895         void Lazy_DHP_less();
 896         void Lazy_DHP_cmpmix();
 897
 898         void Lazy_RCU_GPI_cmp();
 899         void Lazy_RCU_GPI_less();
 900         void Lazy_RCU_GPI_cmpmix();
 901
 902         void Lazy_RCU_GPB_cmp();
 903         void Lazy_RCU_GPB_less();
 904         void Lazy_RCU_GPB_cmpmix();
 905
 906         void Lazy_RCU_GPT_cmp();
 907         void Lazy_RCU_GPT_less();
 908         void Lazy_RCU_GPT_cmpmix();
 909
 910         void Lazy_RCU_SHB_cmp();
 911         void Lazy_RCU_SHB_less();
 912         void Lazy_RCU_SHB_cmpmix();
 913
 914         void Lazy_RCU_SHT_cmp();
 915         void Lazy_RCU_SHT_less();
 916         void Lazy_RCU_SHT_cmpmix();
 917
 918         void Lazy_nogc_cmp();
 919         void Lazy_nogc_less();
 920         void Lazy_nogc_cmpmix();
 921
 922         void Split_HP_cmp();
 923         void Split_HP_less();
 924         void Split_HP_cmpmix();
 925         void Split_HP_cmpmix_stat();
 926
 927         void Split_DHP_cmp();
 928         void Split_DHP_less();
 929         void Split_DHP_cmpmix();
 930         void Split_DHP_cmpmix_stat();
 931
 932         void Split_RCU_GPI_cmp();
 933         void Split_RCU_GPI_less();
 934         void Split_RCU_GPI_cmpmix();
 935         void Split_RCU_GPI_cmpmix_stat();
 936
 937         void Split_RCU_GPB_cmp();
 938         void Split_RCU_GPB_less();
 939         void Split_RCU_GPB_cmpmix();
 940         void Split_RCU_GPB_cmpmix_stat();
 941
 942         void Split_RCU_GPT_cmp();
 943         void Split_RCU_GPT_less();
 944         void Split_RCU_GPT_cmpmix();
 945         void Split_RCU_GPT_cmpmix_stat();
 946
 947         void Split_RCU_SHB_cmp();
 948         void Split_RCU_SHB_less();
 949         void Split_RCU_SHB_cmpmix();
 950         void Split_RCU_SHB_cmpmix_stat();
 951
 952         void Split_RCU_SHT_cmp();
 953         void Split_RCU_SHT_less();
 954         void Split_RCU_SHT_cmpmix();
 955         void Split_RCU_SHT_cmpmix_stat();
 956
 957         void Split_nogc_cmp();
 958         void Split_nogc_less();
 959         void Split_nogc_cmpmix();
 960         void Split_nogc_cmpmix_stat();
 961
 962
 963         void Split_Lazy_HP_cmp();
 964         void Split_Lazy_HP_less();
 965         void Split_Lazy_HP_cmpmix();
 966         void Split_Lazy_HP_cmpmix_stat();
 967
 968         void Split_Lazy_DHP_cmp();
 969         void Split_Lazy_DHP_less();
 970         void Split_Lazy_DHP_cmpmix();
 971         void Split_Lazy_DHP_cmpmix_stat();
 972
 973         void Split_Lazy_RCU_GPI_cmp();
 974         void Split_Lazy_RCU_GPI_less();
 975         void Split_Lazy_RCU_GPI_cmpmix();
 976         void Split_Lazy_RCU_GPI_cmpmix_stat();
 977
 978         void Split_Lazy_RCU_GPB_cmp();
 979         void Split_Lazy_RCU_GPB_less();
 980         void Split_Lazy_RCU_GPB_cmpmix();
 981         void Split_Lazy_RCU_GPB_cmpmix_stat();
 982
 983         void Split_Lazy_RCU_GPT_cmp();
 984         void Split_Lazy_RCU_GPT_less();
 985         void Split_Lazy_RCU_GPT_cmpmix();
 986         void Split_Lazy_RCU_GPT_cmpmix_stat();
 987
 988         void Split_Lazy_RCU_SHB_cmp();
 989         void Split_Lazy_RCU_SHB_less();
 990         void Split_Lazy_RCU_SHB_cmpmix();
 991         void Split_Lazy_RCU_SHB_cmpmix_stat();
 992
 993         void Split_Lazy_RCU_SHT_cmp();
 994         void Split_Lazy_RCU_SHT_less();
 995         void Split_Lazy_RCU_SHT_cmpmix();
 996         void Split_Lazy_RCU_SHT_cmpmix_stat();
 997
 998         void Split_Lazy_nogc_cmp();
 999         void Split_Lazy_nogc_less();
1000         void Split_Lazy_nogc_cmpmix();
1001         void Split_Lazy_nogc_cmpmix_stat();
1002
1003         CPPUNIT_TEST_SUITE(HashSetHdrTest)
1004             CPPUNIT_TEST(Michael_HP_cmp)
1005             CPPUNIT_TEST(Michael_HP_less)
1006             CPPUNIT_TEST(Michael_HP_cmpmix)
1007
1008             CPPUNIT_TEST(Michael_DHP_cmp)
1009             CPPUNIT_TEST(Michael_DHP_less)
1010             CPPUNIT_TEST(Michael_DHP_cmpmix)
1011
1012             CPPUNIT_TEST(Michael_RCU_GPI_cmp)
1013             CPPUNIT_TEST(Michael_RCU_GPI_less)
1014             CPPUNIT_TEST(Michael_RCU_GPI_cmpmix)
1015
1016             CPPUNIT_TEST(Michael_RCU_GPB_cmp)
1017             CPPUNIT_TEST(Michael_RCU_GPB_less)
1018             CPPUNIT_TEST(Michael_RCU_GPB_cmpmix)
1019
1020             CPPUNIT_TEST(Michael_RCU_GPT_cmp)
1021             CPPUNIT_TEST(Michael_RCU_GPT_less)
1022             CPPUNIT_TEST(Michael_RCU_GPT_cmpmix)
1023
1024             CPPUNIT_TEST(Michael_RCU_SHB_cmp)
1025             CPPUNIT_TEST(Michael_RCU_SHB_less)
1026             CPPUNIT_TEST(Michael_RCU_SHB_cmpmix)
1027
1028             CPPUNIT_TEST(Michael_RCU_SHT_cmp)
1029             CPPUNIT_TEST(Michael_RCU_SHT_less)
1030             CPPUNIT_TEST(Michael_RCU_SHT_cmpmix)
1031
1032             CPPUNIT_TEST(Michael_nogc_cmp)
1033             CPPUNIT_TEST(Michael_nogc_less)
1034             CPPUNIT_TEST(Michael_nogc_cmpmix)
1035
1036             CPPUNIT_TEST(Lazy_HP_cmp)
1037             CPPUNIT_TEST(Lazy_HP_less)
1038             CPPUNIT_TEST(Lazy_HP_cmpmix)
1039
1040             CPPUNIT_TEST(Lazy_DHP_cmp)
1041             CPPUNIT_TEST(Lazy_DHP_less)
1042             CPPUNIT_TEST(Lazy_DHP_cmpmix)
1043
1044             CPPUNIT_TEST(Lazy_RCU_GPI_cmp)
1045             CPPUNIT_TEST(Lazy_RCU_GPI_less)
1046             CPPUNIT_TEST(Lazy_RCU_GPI_cmpmix)
1047
1048             CPPUNIT_TEST(Lazy_RCU_GPB_cmp)
1049             CPPUNIT_TEST(Lazy_RCU_GPB_less)
1050             CPPUNIT_TEST(Lazy_RCU_GPB_cmpmix)
1051
1052             CPPUNIT_TEST(Lazy_RCU_GPT_cmp)
1053             CPPUNIT_TEST(Lazy_RCU_GPT_less)
1054             CPPUNIT_TEST(Lazy_RCU_GPT_cmpmix)
1055
1056             CPPUNIT_TEST(Lazy_RCU_SHB_cmp)
1057             CPPUNIT_TEST(Lazy_RCU_SHB_less)
1058             CPPUNIT_TEST(Lazy_RCU_SHB_cmpmix)
1059
1060             CPPUNIT_TEST(Lazy_RCU_SHT_cmp)
1061             CPPUNIT_TEST(Lazy_RCU_SHT_less)
1062             CPPUNIT_TEST(Lazy_RCU_SHT_cmpmix)
1063
1064             CPPUNIT_TEST(Lazy_nogc_cmp)
1065             CPPUNIT_TEST(Lazy_nogc_less)
1066             CPPUNIT_TEST(Lazy_nogc_cmpmix)
1067
1068             CPPUNIT_TEST(Split_HP_cmp)
1069             CPPUNIT_TEST(Split_HP_less)
1070             CPPUNIT_TEST(Split_HP_cmpmix)
1071             CPPUNIT_TEST( Split_HP_cmpmix_stat )
1072
1073             CPPUNIT_TEST(Split_DHP_cmp)
1074             CPPUNIT_TEST(Split_DHP_less)
1075             CPPUNIT_TEST(Split_DHP_cmpmix)
1076             CPPUNIT_TEST( Split_DHP_cmpmix_stat )
1077
1078             CPPUNIT_TEST(Split_RCU_GPI_cmp)
1079             CPPUNIT_TEST(Split_RCU_GPI_less)
1080             CPPUNIT_TEST(Split_RCU_GPI_cmpmix)
1081             CPPUNIT_TEST( Split_RCU_GPI_cmpmix_stat )
1082
1083             CPPUNIT_TEST(Split_RCU_GPB_cmp)
1084             CPPUNIT_TEST(Split_RCU_GPB_less)
1085             CPPUNIT_TEST(Split_RCU_GPB_cmpmix)
1086             CPPUNIT_TEST( Split_RCU_GPB_cmpmix_stat )
1087
1088             CPPUNIT_TEST(Split_RCU_GPT_cmp)
1089             CPPUNIT_TEST(Split_RCU_GPT_less)
1090             CPPUNIT_TEST(Split_RCU_GPT_cmpmix)
1091             CPPUNIT_TEST( Split_RCU_GPT_cmpmix_stat )
1092
1093             CPPUNIT_TEST(Split_RCU_SHB_cmp)
1094             CPPUNIT_TEST(Split_RCU_SHB_less)
1095             CPPUNIT_TEST(Split_RCU_SHB_cmpmix)
1096             CPPUNIT_TEST( Split_RCU_SHB_cmpmix_stat )
1097
1098             CPPUNIT_TEST(Split_RCU_SHT_cmp)
1099             CPPUNIT_TEST(Split_RCU_SHT_less)
1100             CPPUNIT_TEST(Split_RCU_SHT_cmpmix)
1101             CPPUNIT_TEST( Split_RCU_SHT_cmpmix_stat )
1102
1103             CPPUNIT_TEST(Split_nogc_cmp)
1104             CPPUNIT_TEST(Split_nogc_less)
1105             CPPUNIT_TEST(Split_nogc_cmpmix)
1106             CPPUNIT_TEST( Split_nogc_cmpmix_stat )
1107
1108             CPPUNIT_TEST(Split_Lazy_HP_cmp)
1109             CPPUNIT_TEST(Split_Lazy_HP_less)
1110             CPPUNIT_TEST(Split_Lazy_HP_cmpmix)
1111             CPPUNIT_TEST( Split_Lazy_HP_cmpmix_stat )
1112
1113             CPPUNIT_TEST(Split_Lazy_DHP_cmp)
1114             CPPUNIT_TEST(Split_Lazy_DHP_less)
1115             CPPUNIT_TEST(Split_Lazy_DHP_cmpmix)
1116             CPPUNIT_TEST( Split_Lazy_DHP_cmpmix_stat )
1117
1118             CPPUNIT_TEST(Split_Lazy_RCU_GPI_cmp)
1119             CPPUNIT_TEST(Split_Lazy_RCU_GPI_less)
1120             CPPUNIT_TEST(Split_Lazy_RCU_GPI_cmpmix)
1121             CPPUNIT_TEST( Split_Lazy_RCU_GPI_cmpmix_stat )
1122
1123             CPPUNIT_TEST(Split_Lazy_RCU_GPB_cmp)
1124             CPPUNIT_TEST(Split_Lazy_RCU_GPB_less)
1125             CPPUNIT_TEST(Split_Lazy_RCU_GPB_cmpmix)
1126             CPPUNIT_TEST( Split_Lazy_RCU_GPB_cmpmix_stat )
1127
1128             CPPUNIT_TEST(Split_Lazy_RCU_GPT_cmp)
1129             CPPUNIT_TEST(Split_Lazy_RCU_GPT_less)
1130             CPPUNIT_TEST(Split_Lazy_RCU_GPT_cmpmix)
1131             CPPUNIT_TEST( Split_Lazy_RCU_GPT_cmpmix_stat )
1132
1133             CPPUNIT_TEST(Split_Lazy_RCU_SHB_cmp)
1134             CPPUNIT_TEST(Split_Lazy_RCU_SHB_less)
1135             CPPUNIT_TEST(Split_Lazy_RCU_SHB_cmpmix)
1136             CPPUNIT_TEST( Split_Lazy_RCU_SHB_cmpmix_stat )
1137
1138             CPPUNIT_TEST(Split_Lazy_RCU_SHT_cmp)
1139             CPPUNIT_TEST(Split_Lazy_RCU_SHT_less)
1140             CPPUNIT_TEST(Split_Lazy_RCU_SHT_cmpmix)
1141             CPPUNIT_TEST( Split_Lazy_RCU_SHT_cmpmix_stat )
1142
1143             CPPUNIT_TEST(Split_Lazy_nogc_cmp)
1144             CPPUNIT_TEST(Split_Lazy_nogc_less)
1145             CPPUNIT_TEST(Split_Lazy_nogc_cmpmix)
1146             CPPUNIT_TEST( Split_Lazy_nogc_cmpmix_stat )
1147
1148         CPPUNIT_TEST_SUITE_END()
1149
1150     };
1151
1152 } // namespace set
1153
1154 #endif // __CDSTEST_HDR_SET_H