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