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 )
 288             {
 289                 ++i.nFindCount;
 290             }
 291             template <typename Item, typename T>
 292             void operator()( Item& i, T const& val )
 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                     CPPUNIT_ASSERT( s.get(gp, nKey ));
 364                     CPPUNIT_ASSERT( !gp.empty());
 365                     CPPUNIT_CHECK( gp->nKey == nKey );
 366                     CPPUNIT_CHECK( gp->nVal == nKey );
 367
 368                     CPPUNIT_ASSERT( s.extract(gp, nKey));
 369                     CPPUNIT_ASSERT( !gp.empty());
 370                     CPPUNIT_CHECK( gp->nKey == nKey );
 371                     CPPUNIT_CHECK( gp->nVal == nKey );
 372                     CPPUNIT_CHECK( !s.get(gp, nKey));
 373                     gp.release();
 374
 375                     CPPUNIT_CHECK( !s.extract(gp, nKey));
 376                     CPPUNIT_CHECK( gp.empty());
 377                 }
 378                 CPPUNIT_ASSERT( s.empty() );
 379
 380
 381                 for ( int i = 0; i < nLimit; ++i )
 382                     CPPUNIT_ASSERT( s.insert( arrRandom[i] ));
 383
 384                 for ( int i = 0; i < nLimit; ++i ) {
 385                     int nKey = arrRandom[i];
 386                     CPPUNIT_ASSERT( s.get_with(gp, other_item(nKey), other_less() ));
 387                     CPPUNIT_ASSERT( !gp.empty());
 388                     CPPUNIT_CHECK( gp->nKey == nKey );
 389                     CPPUNIT_CHECK( gp->nVal == nKey );
 390
 391                     CPPUNIT_ASSERT( s.extract_with(gp, other_item(nKey), other_less() ));
 392                     CPPUNIT_ASSERT( !gp.empty());
 393                     CPPUNIT_CHECK( gp->nKey == nKey );
 394                     CPPUNIT_CHECK( gp->nVal == nKey );
 395                     CPPUNIT_CHECK( !s.get_with(gp, other_item(nKey), other_less() ));
 396                     gp.release();
 397
 398                     CPPUNIT_CHECK( !s.extract_with(gp, other_item(nKey), other_less() ));
 399                     CPPUNIT_CHECK( gp.empty());
 400                 }
 401                 CPPUNIT_ASSERT( s.empty() );
 402             }
 403
 404             // iterator test
 405             test_iter<Set>();
 406         }
 407
 408         template <class Set>
 409         void test_int_rcu()
 410         {
 411             Set s( 100, 4 );
 412             test_int_with( s );
 413
 414             // extract/get test
 415             {
 416                 typedef typename Set::gc    rcu;
 417                 typedef typename Set::rcu_lock rcu_lock;
 418                 typedef typename Set::value_type value_type;
 419                 typename Set::exempt_ptr ep;
 420
 421                 static size_t const nLimit = 100;
 422                 int arr[nLimit];
 423                 for ( size_t i = 0; i < nLimit; ++i )
 424                     arr[i] = (int) i;
 425                 std::random_shuffle( arr, arr + nLimit );
 426
 427                 for ( size_t i = 0; i < nLimit; ++i )
 428                     CPPUNIT_ASSERT( s.insert( arr[i] ));
 429
 430                 for ( size_t i = 0; i < nLimit; i += 2 ) {
 431                     value_type * pVal;
 432                     int nKey = arr[i];
 433                     {
 434                         rcu_lock l;
 435                         pVal = s.get( nKey );
 436                         CPPUNIT_ASSERT( pVal != nullptr );
 437                         CPPUNIT_CHECK( pVal->nKey == nKey );
 438                         CPPUNIT_CHECK( pVal->nVal == nKey );
 439
 440                         CPPUNIT_ASSERT( s.extract( ep, nKey ));
 441                         CPPUNIT_ASSERT( !ep.empty() );
 442                         CPPUNIT_CHECK( pVal->nKey == ep->nKey );
 443                         CPPUNIT_CHECK( pVal->nVal == (*ep).nVal );
 444                     }
 445                     ep.release();
 446                     {
 447                         rcu_lock l;
 448                         CPPUNIT_CHECK( s.get( nKey ) == nullptr );
 449                         CPPUNIT_CHECK( !s.extract( ep, nKey ));
 450                         CPPUNIT_CHECK( ep.empty() );
 451
 452                         nKey = arr[i+1];
 453                         pVal = s.get_with( other_item(nKey), other_less() );
 454                         CPPUNIT_ASSERT( pVal != nullptr );
 455                         CPPUNIT_CHECK( pVal->nKey == nKey );
 456                         CPPUNIT_CHECK( pVal->nVal == nKey );
 457
 458                         CPPUNIT_ASSERT( s.extract_with( ep, other_item(nKey), other_less() ));
 459                         CPPUNIT_ASSERT( !ep.empty() );
 460                         CPPUNIT_CHECK( pVal->nKey == ep->nKey );
 461                         CPPUNIT_CHECK( pVal->nVal == (*ep).nVal );
 462                     }
 463                     ep.release();
 464                     {
 465                         rcu_lock l;
 466                         CPPUNIT_CHECK( s.get_with( other_item( nKey ), other_less() ) == nullptr );
 467                         CPPUNIT_CHECK( !s.extract_with( ep, other_item(nKey), other_less() ));
 468                         CPPUNIT_CHECK( ep.empty() );
 469                     }
 470                 }
 471                 CPPUNIT_CHECK( s.empty() );
 472                 CPPUNIT_CHECK( check_size( s, 0 ));
 473                 {
 474                     rcu_lock l;
 475                     CPPUNIT_CHECK( s.get( int( nLimit / 2 ) ) == nullptr );
 476                     CPPUNIT_CHECK( !s.extract( ep, int(nLimit / 2) ));
 477                     CPPUNIT_CHECK( ep.empty() );
 478                 }
 479             }
 480
 481             // iterator test
 482             test_iter<Set>();
 483         }
 484
 485         template <class Set>
 486         void test_int_with( Set& s)
 487         {
 488             typedef typename Set::value_type    value_type;
 489
 490             item itm;
 491             int key;
 492
 493             // insert/find test
 494             CPPUNIT_ASSERT( !s.find( 10 ) );
 495             CPPUNIT_ASSERT( s.insert( 10 ));
 496             CPPUNIT_ASSERT( !s.empty() );
 497             CPPUNIT_ASSERT( check_size( s, 1 ));
 498             CPPUNIT_ASSERT( s.find( 10 ) );
 499
 500             CPPUNIT_ASSERT( !s.insert( 10 ));
 501             CPPUNIT_ASSERT( !s.empty() );
 502             CPPUNIT_ASSERT( check_size( s, 1 ));
 503
 504             CPPUNIT_ASSERT( !s.find_with( 20, less<value_type>() ) );
 505             CPPUNIT_ASSERT( s.insert( std::make_pair(20, 25) ));
 506             CPPUNIT_ASSERT( !s.empty() );
 507             CPPUNIT_ASSERT( check_size( s, 2 ));
 508             CPPUNIT_ASSERT( s.find_with( 10, less<value_type>() ) );
 509             CPPUNIT_ASSERT( s.find( key = 20 ) );
 510             CPPUNIT_ASSERT( s.find_with( key, less<value_type>(), find_functor() ) );
 511             {
 512                 copy_found<item> f;
 513                 key = 20;
 514                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 515                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 516                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 517                 CPPUNIT_ASSERT( f.m_found.nFindCount == 1 );
 518             }
 519             CPPUNIT_ASSERT( s.find( key, find_functor() ) );
 520             {
 521                 copy_found<item> f;
 522                 key = 20;
 523                 CPPUNIT_ASSERT( s.find_with( key, less<value_type>(), std::ref( f ) ) );
 524                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 525                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 526                 CPPUNIT_ASSERT( f.m_found.nFindCount == 2 );
 527             }
 528             CPPUNIT_ASSERT( !s.empty() );
 529             CPPUNIT_ASSERT( check_size( s, 2 ));
 530
 531             CPPUNIT_ASSERT( !s.find( 25 ) );
 532             CPPUNIT_ASSERT( s.insert( std::make_pair(25, -1), insert_functor() ));
 533             CPPUNIT_ASSERT( !s.empty() );
 534             CPPUNIT_ASSERT( check_size( s, 3 ));
 535             {
 536                 copy_found<item> f;
 537                 key = 25;
 538                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 539                 CPPUNIT_ASSERT( f.m_found.nKey == 25 );
 540                 CPPUNIT_ASSERT( f.m_found.nVal == 2500 );
 541             }
 542
 543             // ensure test
 544             key = 10;
 545             {
 546                 copy_found<item> f;
 547                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 548                 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
 549                 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
 550                 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 0 );
 551                 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 0 );
 552             }
 553             std::pair<bool, bool> ensureResult = s.ensure( key, ensure_functor() );
 554             CPPUNIT_ASSERT( ensureResult.first && !ensureResult.second );
 555             CPPUNIT_ASSERT( !s.empty() );
 556             CPPUNIT_ASSERT( check_size( s, 3 ));
 557             {
 558                 copy_found<item> f;
 559                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 560                 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
 561                 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
 562                 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 1 );
 563                 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 0 );
 564             }
 565
 566             ensureResult = s.ensure( std::make_pair(13, 1300), ensure_functor() );
 567             CPPUNIT_ASSERT( ensureResult.first && ensureResult.second );
 568             CPPUNIT_ASSERT( !s.empty() );
 569             CPPUNIT_ASSERT( check_size( s, 4 ));
 570             {
 571                 copy_found<item> f;
 572                 key = 13;
 573                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 574                 CPPUNIT_ASSERT( f.m_found.nKey == 13 );
 575                 CPPUNIT_ASSERT( f.m_found.nVal == 1300 );
 576                 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 0 );
 577                 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 1 );
 578             }
 579
 580             // erase test
 581             CPPUNIT_ASSERT( s.erase(13) );
 582             CPPUNIT_ASSERT( !s.find( 13 ));
 583             CPPUNIT_ASSERT( !s.empty() );
 584             CPPUNIT_ASSERT( check_size( s, 3 ));
 585             CPPUNIT_ASSERT( !s.erase(13) );
 586             CPPUNIT_ASSERT( !s.empty() );
 587             CPPUNIT_ASSERT( check_size( s, 3 ));
 588
 589             CPPUNIT_ASSERT( s.find( 10 ));
 590             CPPUNIT_ASSERT( s.erase_with( 10, less<value_type>() ));
 591             CPPUNIT_ASSERT( !s.find( 10 ));
 592             CPPUNIT_ASSERT( !s.empty() );
 593             CPPUNIT_ASSERT( check_size( s, 2 ));
 594             CPPUNIT_ASSERT( !s.erase_with(10, less<value_type>()) );
 595             CPPUNIT_ASSERT( !s.empty() );
 596             CPPUNIT_ASSERT( check_size( s, 2 ));
 597
 598             CPPUNIT_ASSERT( s.find(20) );
 599             {
 600                 copy_found<item> f;
 601                 CPPUNIT_ASSERT( s.erase( 20, std::ref( f ) ) );
 602                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 603                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 604
 605                 CPPUNIT_ASSERT( s.insert(235))
 606                     CPPUNIT_ASSERT( s.erase_with( 235, less<value_type>(), std::ref( f ) ) );
 607                 CPPUNIT_ASSERT( f.m_found.nKey == 235 );
 608                 CPPUNIT_ASSERT( f.m_found.nVal == 235 );
 609             }
 610             CPPUNIT_ASSERT( !s.find( 20 ));
 611             CPPUNIT_ASSERT( !s.empty() );
 612             CPPUNIT_ASSERT( check_size( s, 1 ));
 613
 614             s.clear();
 615             CPPUNIT_ASSERT( s.empty() );
 616             CPPUNIT_ASSERT( check_size( s, 0 ));
 617
 618             // emplace test
 619             CPPUNIT_ASSERT( s.emplace( 151 )) ;  // key = 151,  val = 151
 620             CPPUNIT_ASSERT( s.emplace( 174, 471 )) ;    // key = 174, val = 471
 621             CPPUNIT_ASSERT( s.emplace( std::make_pair( 190, 91 ) )) ; // key == 190, val = 91
 622             CPPUNIT_ASSERT( !s.empty() );
 623             CPPUNIT_ASSERT( check_size( s, 3 ));
 624
 625             CPPUNIT_ASSERT( s.find(151));
 626             CPPUNIT_ASSERT( s.find_with(174, less<value_type>()));
 627             CPPUNIT_ASSERT( s.find(190));
 628
 629             {
 630                 copy_found<item> f;
 631                 key = 151;
 632                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 633                 CPPUNIT_ASSERT( f.m_found.nKey == 151 );
 634                 CPPUNIT_ASSERT( f.m_found.nVal == 151 );
 635
 636                 key = 174;
 637                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 638                 CPPUNIT_ASSERT( f.m_found.nKey == 174 );
 639                 CPPUNIT_ASSERT( f.m_found.nVal == 471 );
 640
 641                 key = 190;
 642                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 643                 CPPUNIT_ASSERT( f.m_found.nKey == 190 );
 644                 CPPUNIT_ASSERT( f.m_found.nVal == 91 );
 645             }
 646
 647             s.clear();
 648             CPPUNIT_ASSERT( s.empty() );
 649             CPPUNIT_ASSERT( check_size( s, 0 ));
 650         }
 651
 652
 653         template <class Set>
 654         void test_int_nogc()
 655         {
 656             typedef typename Set::value_type        value_type;
 657             typedef typename Set::iterator          iterator;
 658             typedef typename Set::const_iterator    const_iterator;
 659
 660             {
 661                 Set s( 52, 4 );
 662                 iterator it;
 663
 664                 CPPUNIT_ASSERT( s.empty() );
 665                 CPPUNIT_ASSERT( check_size( s, 0 ));
 666
 667                 // insert
 668                 it = s.insert( 10 );
 669                 CPPUNIT_ASSERT( it != s.end() );
 670                 CPPUNIT_ASSERT( it->key() == 10 );
 671                 CPPUNIT_ASSERT( it->val() == 10 );
 672                 CPPUNIT_ASSERT( !s.empty() );
 673                 CPPUNIT_ASSERT( check_size( s, 1 ));
 674                 CPPUNIT_ASSERT( s.insert( 10 ) == s.end() );
 675
 676                 it = s.insert( std::make_pair( 50, 25 ));
 677                 CPPUNIT_ASSERT( it != s.end() );
 678                 CPPUNIT_ASSERT( it->key() == 50 );
 679                 CPPUNIT_ASSERT( it->val() == 25 );
 680                 CPPUNIT_ASSERT( !s.empty() );
 681                 CPPUNIT_ASSERT( check_size( s, 2 ));
 682                 CPPUNIT_ASSERT( s.insert( 50 ) == s.end() );
 683
 684                 // ensure
 685                 std::pair< iterator, bool>  ensureResult;
 686                 ensureResult = s.ensure( 20 );
 687                 CPPUNIT_ASSERT( ensureResult.first != s.end() );
 688                 CPPUNIT_ASSERT( ensureResult.second  );
 689                 CPPUNIT_ASSERT( ensureResult.first->key() == 20 );
 690                 CPPUNIT_ASSERT( ensureResult.first->val() == 20 );
 691                 CPPUNIT_ASSERT( !s.empty() );
 692                 CPPUNIT_ASSERT( check_size( s, 3 ));
 693
 694                 ensureResult = s.ensure( std::make_pair( 20, 200 ));
 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                 ensureResult.first->nVal = 22;
 702
 703                 ensureResult = s.ensure( std::make_pair( 30, 33 ));
 704                 CPPUNIT_ASSERT( ensureResult.first != s.end() );
 705                 CPPUNIT_ASSERT( ensureResult.second  );
 706                 CPPUNIT_ASSERT( ensureResult.first->key() == 30 );
 707                 CPPUNIT_ASSERT( ensureResult.first->val() == 33 );
 708                 CPPUNIT_ASSERT( !s.empty() );
 709                 CPPUNIT_ASSERT( check_size( s, 4 ));
 710
 711                 // find
 712                 it = s.find( 10 );
 713                 CPPUNIT_ASSERT( it != s.end() );
 714                 CPPUNIT_ASSERT( it->key() == 10 );
 715                 CPPUNIT_ASSERT( it->val() == 10 );
 716
 717                 it = s.find_with( 20, less<value_type>() );
 718                 CPPUNIT_ASSERT( it != s.end() );
 719                 CPPUNIT_ASSERT( it->key() == 20 );
 720                 CPPUNIT_ASSERT( it->val() == 22 );
 721
 722                 it = s.find( 30 );
 723                 CPPUNIT_ASSERT( it != s.end() );
 724                 CPPUNIT_ASSERT( it->key() == 30 );
 725                 CPPUNIT_ASSERT( it->val() == 33 );
 726
 727                 it = s.find( 40 );
 728                 CPPUNIT_ASSERT( it == s.end() );
 729
 730                 it = s.find( 50 );
 731                 CPPUNIT_ASSERT( it != s.end() );
 732                 CPPUNIT_ASSERT( it->key() == 50 );
 733                 CPPUNIT_ASSERT( it->val() == 25 );
 734
 735                 // emplace test
 736                 it = s.emplace( 151 ) ;  // key = 151,  val = 151
 737                 CPPUNIT_ASSERT( it != s.end() );
 738                 CPPUNIT_ASSERT( it->key() == 151 );
 739                 CPPUNIT_ASSERT( it->val() == 151 );
 740
 741                 it = s.emplace( 174, 471 ) ; // key == 174, val = 471
 742                 CPPUNIT_ASSERT( it != s.end() );
 743                 CPPUNIT_ASSERT( it->key() == 174 );
 744                 CPPUNIT_ASSERT( it->val() == 471 );
 745
 746                 it = s.emplace( std::make_pair( 190, 91 )) ; // key == 190, val = 91
 747                 CPPUNIT_ASSERT( it != s.end() );
 748                 CPPUNIT_ASSERT( it->key() == 190 );
 749                 CPPUNIT_ASSERT( it->val() == 91 );
 750
 751                 it = s.find( 174 );
 752                 CPPUNIT_ASSERT( it != s.end() );
 753                 CPPUNIT_ASSERT( it->key() == 174 );
 754                 CPPUNIT_ASSERT( it->val() == 471 );
 755
 756                 it = s.find_with( 190, less<value_type>() );
 757                 CPPUNIT_ASSERT( it != s.end() );
 758                 CPPUNIT_ASSERT( it->key() == 190 );
 759                 CPPUNIT_ASSERT( it->val() == 91 );
 760
 761                 it = s.find( 151 );
 762                 CPPUNIT_ASSERT( it != s.end() );
 763                 CPPUNIT_ASSERT( it->key() == 151 );
 764                 CPPUNIT_ASSERT( it->val() == 151 );
 765
 766                 //s.clear();
 767                 //CPPUNIT_ASSERT( s.empty() );
 768                 //CPPUNIT_ASSERT( check_size( s, 0 ));
 769             }
 770
 771             {
 772                 Set s( 52, 4 );
 773
 774                 // iterator test
 775                 for ( int i = 0; i < 500; ++i ) {
 776                     CPPUNIT_ASSERT( s.insert( std::make_pair( i, i * 2) ) != s.end() );
 777                 }
 778                 for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 779                     CPPUNIT_ASSERT( (*it).nKey * 2 == it->nVal );
 780                     it->nVal = (*it).nKey;
 781                 }
 782
 783                 Set const& refSet = s;
 784                 for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
 785                     CPPUNIT_ASSERT( (*it).nKey == it->nVal );
 786                 }
 787             }
 788         }
 789
 790         template <class Set>
 791         void test_iter()
 792         {
 793             typedef typename Set::value_type        value_type;
 794             typedef typename Set::iterator          iterator;
 795             typedef typename Set::const_iterator    const_iterator;
 796
 797             Set s( 100, 4 );
 798
 799             const size_t nMaxCount = 500;
 800             for ( int i = 0; size_t(i) < nMaxCount; ++i ) {
 801                 CPPUNIT_ASSERT( s.insert( std::make_pair( i, i * 2) ));
 802             }
 803             size_t nCount = 0;
 804             for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 805                 CPPUNIT_ASSERT_EX( (*it).nKey * 2 == it->nVal,
 806                     "Step " << nCount << ": Iterator key=" << it->nKey <<  ", value expected=" << it->nKey * 2 << ", value real=" << it->nVal
 807                     );
 808                 it->nVal = (*it).nKey;
 809                 ++nCount;
 810             }
 811             CPPUNIT_ASSERT( nCount == nMaxCount );
 812
 813             nCount = 0;
 814             Set const& refSet = s;
 815             for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
 816                 CPPUNIT_ASSERT_EX( (*it).nKey == it->nVal,
 817                     "Step " << nCount << ": Iterator key=" << it->nKey <<  ", value expected=" << it->nKey << ", value real=" << it->nVal
 818                     );
 819                 ++nCount;
 820             }
 821             CPPUNIT_ASSERT( nCount == nMaxCount );
 822         }
 823
 824         void Michael_HP_cmp();
 825         void Michael_HP_less();
 826         void Michael_HP_cmpmix();
 827
 828         void Michael_DHP_cmp();
 829         void Michael_DHP_less();
 830         void Michael_DHP_cmpmix();
 831
 832         void Michael_RCU_GPI_cmp();
 833         void Michael_RCU_GPI_less();
 834         void Michael_RCU_GPI_cmpmix();
 835
 836         void Michael_RCU_GPT_cmp();
 837         void Michael_RCU_GPT_less();
 838         void Michael_RCU_GPT_cmpmix();
 839
 840         void Michael_RCU_GPB_cmp();
 841         void Michael_RCU_GPB_less();
 842         void Michael_RCU_GPB_cmpmix();
 843
 844         void Michael_RCU_SHT_cmp();
 845         void Michael_RCU_SHT_less();
 846         void Michael_RCU_SHT_cmpmix();
 847
 848         void Michael_RCU_SHB_cmp();
 849         void Michael_RCU_SHB_less();
 850         void Michael_RCU_SHB_cmpmix();
 851
 852         void Michael_nogc_cmp();
 853         void Michael_nogc_less();
 854         void Michael_nogc_cmpmix();
 855
 856         void Lazy_HP_cmp();
 857         void Lazy_HP_less();
 858         void Lazy_HP_cmpmix();
 859
 860         void Lazy_DHP_cmp();
 861         void Lazy_DHP_less();
 862         void Lazy_DHP_cmpmix();
 863
 864         void Lazy_RCU_GPI_cmp();
 865         void Lazy_RCU_GPI_less();
 866         void Lazy_RCU_GPI_cmpmix();
 867
 868         void Lazy_RCU_GPB_cmp();
 869         void Lazy_RCU_GPB_less();
 870         void Lazy_RCU_GPB_cmpmix();
 871
 872         void Lazy_RCU_GPT_cmp();
 873         void Lazy_RCU_GPT_less();
 874         void Lazy_RCU_GPT_cmpmix();
 875
 876         void Lazy_RCU_SHB_cmp();
 877         void Lazy_RCU_SHB_less();
 878         void Lazy_RCU_SHB_cmpmix();
 879
 880         void Lazy_RCU_SHT_cmp();
 881         void Lazy_RCU_SHT_less();
 882         void Lazy_RCU_SHT_cmpmix();
 883
 884         void Lazy_nogc_cmp();
 885         void Lazy_nogc_less();
 886         void Lazy_nogc_cmpmix();
 887
 888         void Split_HP_cmp();
 889         void Split_HP_less();
 890         void Split_HP_cmpmix();
 891         void Split_HP_cmpmix_stat();
 892
 893         void Split_DHP_cmp();
 894         void Split_DHP_less();
 895         void Split_DHP_cmpmix();
 896         void Split_DHP_cmpmix_stat();
 897
 898         void Split_RCU_GPI_cmp();
 899         void Split_RCU_GPI_less();
 900         void Split_RCU_GPI_cmpmix();
 901         void Split_RCU_GPI_cmpmix_stat();
 902
 903         void Split_RCU_GPB_cmp();
 904         void Split_RCU_GPB_less();
 905         void Split_RCU_GPB_cmpmix();
 906         void Split_RCU_GPB_cmpmix_stat();
 907
 908         void Split_RCU_GPT_cmp();
 909         void Split_RCU_GPT_less();
 910         void Split_RCU_GPT_cmpmix();
 911         void Split_RCU_GPT_cmpmix_stat();
 912
 913         void Split_RCU_SHB_cmp();
 914         void Split_RCU_SHB_less();
 915         void Split_RCU_SHB_cmpmix();
 916         void Split_RCU_SHB_cmpmix_stat();
 917
 918         void Split_RCU_SHT_cmp();
 919         void Split_RCU_SHT_less();
 920         void Split_RCU_SHT_cmpmix();
 921         void Split_RCU_SHT_cmpmix_stat();
 922
 923         void Split_nogc_cmp();
 924         void Split_nogc_less();
 925         void Split_nogc_cmpmix();
 926         void Split_nogc_cmpmix_stat();
 927
 928
 929         void Split_Lazy_HP_cmp();
 930         void Split_Lazy_HP_less();
 931         void Split_Lazy_HP_cmpmix();
 932         void Split_Lazy_HP_cmpmix_stat();
 933
 934         void Split_Lazy_DHP_cmp();
 935         void Split_Lazy_DHP_less();
 936         void Split_Lazy_DHP_cmpmix();
 937         void Split_Lazy_DHP_cmpmix_stat();
 938
 939         void Split_Lazy_RCU_GPI_cmp();
 940         void Split_Lazy_RCU_GPI_less();
 941         void Split_Lazy_RCU_GPI_cmpmix();
 942         void Split_Lazy_RCU_GPI_cmpmix_stat();
 943
 944         void Split_Lazy_RCU_GPB_cmp();
 945         void Split_Lazy_RCU_GPB_less();
 946         void Split_Lazy_RCU_GPB_cmpmix();
 947         void Split_Lazy_RCU_GPB_cmpmix_stat();
 948
 949         void Split_Lazy_RCU_GPT_cmp();
 950         void Split_Lazy_RCU_GPT_less();
 951         void Split_Lazy_RCU_GPT_cmpmix();
 952         void Split_Lazy_RCU_GPT_cmpmix_stat();
 953
 954         void Split_Lazy_RCU_SHB_cmp();
 955         void Split_Lazy_RCU_SHB_less();
 956         void Split_Lazy_RCU_SHB_cmpmix();
 957         void Split_Lazy_RCU_SHB_cmpmix_stat();
 958
 959         void Split_Lazy_RCU_SHT_cmp();
 960         void Split_Lazy_RCU_SHT_less();
 961         void Split_Lazy_RCU_SHT_cmpmix();
 962         void Split_Lazy_RCU_SHT_cmpmix_stat();
 963
 964         void Split_Lazy_nogc_cmp();
 965         void Split_Lazy_nogc_less();
 966         void Split_Lazy_nogc_cmpmix();
 967         void Split_Lazy_nogc_cmpmix_stat();
 968
 969         CPPUNIT_TEST_SUITE(HashSetHdrTest)
 970             CPPUNIT_TEST(Michael_HP_cmp)
 971             CPPUNIT_TEST(Michael_HP_less)
 972             CPPUNIT_TEST(Michael_HP_cmpmix)
 973
 974             CPPUNIT_TEST(Michael_DHP_cmp)
 975             CPPUNIT_TEST(Michael_DHP_less)
 976             CPPUNIT_TEST(Michael_DHP_cmpmix)
 977
 978             CPPUNIT_TEST(Michael_RCU_GPI_cmp)
 979             CPPUNIT_TEST(Michael_RCU_GPI_less)
 980             CPPUNIT_TEST(Michael_RCU_GPI_cmpmix)
 981
 982             CPPUNIT_TEST(Michael_RCU_GPB_cmp)
 983             CPPUNIT_TEST(Michael_RCU_GPB_less)
 984             CPPUNIT_TEST(Michael_RCU_GPB_cmpmix)
 985
 986             CPPUNIT_TEST(Michael_RCU_GPT_cmp)
 987             CPPUNIT_TEST(Michael_RCU_GPT_less)
 988             CPPUNIT_TEST(Michael_RCU_GPT_cmpmix)
 989
 990             CPPUNIT_TEST(Michael_RCU_SHB_cmp)
 991             CPPUNIT_TEST(Michael_RCU_SHB_less)
 992             CPPUNIT_TEST(Michael_RCU_SHB_cmpmix)
 993
 994             CPPUNIT_TEST(Michael_RCU_SHT_cmp)
 995             CPPUNIT_TEST(Michael_RCU_SHT_less)
 996             CPPUNIT_TEST(Michael_RCU_SHT_cmpmix)
 997
 998             CPPUNIT_TEST(Michael_nogc_cmp)
 999             CPPUNIT_TEST(Michael_nogc_less)
1000             CPPUNIT_TEST(Michael_nogc_cmpmix)
1001
1002             CPPUNIT_TEST(Lazy_HP_cmp)
1003             CPPUNIT_TEST(Lazy_HP_less)
1004             CPPUNIT_TEST(Lazy_HP_cmpmix)
1005
1006             CPPUNIT_TEST(Lazy_DHP_cmp)
1007             CPPUNIT_TEST(Lazy_DHP_less)
1008             CPPUNIT_TEST(Lazy_DHP_cmpmix)
1009
1010             CPPUNIT_TEST(Lazy_RCU_GPI_cmp)
1011             CPPUNIT_TEST(Lazy_RCU_GPI_less)
1012             CPPUNIT_TEST(Lazy_RCU_GPI_cmpmix)
1013
1014             CPPUNIT_TEST(Lazy_RCU_GPB_cmp)
1015             CPPUNIT_TEST(Lazy_RCU_GPB_less)
1016             CPPUNIT_TEST(Lazy_RCU_GPB_cmpmix)
1017
1018             CPPUNIT_TEST(Lazy_RCU_GPT_cmp)
1019             CPPUNIT_TEST(Lazy_RCU_GPT_less)
1020             CPPUNIT_TEST(Lazy_RCU_GPT_cmpmix)
1021
1022             CPPUNIT_TEST(Lazy_RCU_SHB_cmp)
1023             CPPUNIT_TEST(Lazy_RCU_SHB_less)
1024             CPPUNIT_TEST(Lazy_RCU_SHB_cmpmix)
1025
1026             CPPUNIT_TEST(Lazy_RCU_SHT_cmp)
1027             CPPUNIT_TEST(Lazy_RCU_SHT_less)
1028             CPPUNIT_TEST(Lazy_RCU_SHT_cmpmix)
1029
1030             CPPUNIT_TEST(Lazy_nogc_cmp)
1031             CPPUNIT_TEST(Lazy_nogc_less)
1032             CPPUNIT_TEST(Lazy_nogc_cmpmix)
1033
1034             CPPUNIT_TEST(Split_HP_cmp)
1035             CPPUNIT_TEST(Split_HP_less)
1036             CPPUNIT_TEST(Split_HP_cmpmix)
1037             CPPUNIT_TEST( Split_HP_cmpmix_stat )
1038
1039             CPPUNIT_TEST(Split_DHP_cmp)
1040             CPPUNIT_TEST(Split_DHP_less)
1041             CPPUNIT_TEST(Split_DHP_cmpmix)
1042             CPPUNIT_TEST( Split_DHP_cmpmix_stat )
1043
1044             CPPUNIT_TEST(Split_RCU_GPI_cmp)
1045             CPPUNIT_TEST(Split_RCU_GPI_less)
1046             CPPUNIT_TEST(Split_RCU_GPI_cmpmix)
1047             CPPUNIT_TEST( Split_RCU_GPI_cmpmix_stat )
1048
1049             CPPUNIT_TEST(Split_RCU_GPB_cmp)
1050             CPPUNIT_TEST(Split_RCU_GPB_less)
1051             CPPUNIT_TEST(Split_RCU_GPB_cmpmix)
1052             CPPUNIT_TEST( Split_RCU_GPB_cmpmix_stat )
1053
1054             CPPUNIT_TEST(Split_RCU_GPT_cmp)
1055             CPPUNIT_TEST(Split_RCU_GPT_less)
1056             CPPUNIT_TEST(Split_RCU_GPT_cmpmix)
1057             CPPUNIT_TEST( Split_RCU_GPT_cmpmix_stat )
1058
1059             CPPUNIT_TEST(Split_RCU_SHB_cmp)
1060             CPPUNIT_TEST(Split_RCU_SHB_less)
1061             CPPUNIT_TEST(Split_RCU_SHB_cmpmix)
1062             CPPUNIT_TEST( Split_RCU_SHB_cmpmix_stat )
1063
1064             CPPUNIT_TEST(Split_RCU_SHT_cmp)
1065             CPPUNIT_TEST(Split_RCU_SHT_less)
1066             CPPUNIT_TEST(Split_RCU_SHT_cmpmix)
1067             CPPUNIT_TEST( Split_RCU_SHT_cmpmix_stat )
1068
1069             CPPUNIT_TEST(Split_nogc_cmp)
1070             CPPUNIT_TEST(Split_nogc_less)
1071             CPPUNIT_TEST(Split_nogc_cmpmix)
1072             CPPUNIT_TEST( Split_nogc_cmpmix_stat )
1073
1074             CPPUNIT_TEST(Split_Lazy_HP_cmp)
1075             CPPUNIT_TEST(Split_Lazy_HP_less)
1076             CPPUNIT_TEST(Split_Lazy_HP_cmpmix)
1077             CPPUNIT_TEST( Split_Lazy_HP_cmpmix_stat )
1078
1079             CPPUNIT_TEST(Split_Lazy_DHP_cmp)
1080             CPPUNIT_TEST(Split_Lazy_DHP_less)
1081             CPPUNIT_TEST(Split_Lazy_DHP_cmpmix)
1082             CPPUNIT_TEST( Split_Lazy_DHP_cmpmix_stat )
1083
1084             CPPUNIT_TEST(Split_Lazy_RCU_GPI_cmp)
1085             CPPUNIT_TEST(Split_Lazy_RCU_GPI_less)
1086             CPPUNIT_TEST(Split_Lazy_RCU_GPI_cmpmix)
1087             CPPUNIT_TEST( Split_Lazy_RCU_GPI_cmpmix_stat )
1088
1089             CPPUNIT_TEST(Split_Lazy_RCU_GPB_cmp)
1090             CPPUNIT_TEST(Split_Lazy_RCU_GPB_less)
1091             CPPUNIT_TEST(Split_Lazy_RCU_GPB_cmpmix)
1092             CPPUNIT_TEST( Split_Lazy_RCU_GPB_cmpmix_stat )
1093
1094             CPPUNIT_TEST(Split_Lazy_RCU_GPT_cmp)
1095             CPPUNIT_TEST(Split_Lazy_RCU_GPT_less)
1096             CPPUNIT_TEST(Split_Lazy_RCU_GPT_cmpmix)
1097             CPPUNIT_TEST( Split_Lazy_RCU_GPT_cmpmix_stat )
1098
1099             CPPUNIT_TEST(Split_Lazy_RCU_SHB_cmp)
1100             CPPUNIT_TEST(Split_Lazy_RCU_SHB_less)
1101             CPPUNIT_TEST(Split_Lazy_RCU_SHB_cmpmix)
1102             CPPUNIT_TEST( Split_Lazy_RCU_SHB_cmpmix_stat )
1103
1104             CPPUNIT_TEST(Split_Lazy_RCU_SHT_cmp)
1105             CPPUNIT_TEST(Split_Lazy_RCU_SHT_less)
1106             CPPUNIT_TEST(Split_Lazy_RCU_SHT_cmpmix)
1107             CPPUNIT_TEST( Split_Lazy_RCU_SHT_cmpmix_stat )
1108
1109             CPPUNIT_TEST(Split_Lazy_nogc_cmp)
1110             CPPUNIT_TEST(Split_Lazy_nogc_less)
1111             CPPUNIT_TEST(Split_Lazy_nogc_cmpmix)
1112             CPPUNIT_TEST( Split_Lazy_nogc_cmpmix_stat )
1113
1114         CPPUNIT_TEST_SUITE_END()
1115
1116     };
1117
1118 } // namespace set
1119
1120 #endif // __CDSTEST_HDR_SET_H