tests/test-hdr/set/hdr_set.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSTEST_HDR_SET_H
  32 #define CDSTEST_HDR_SET_H
  33
  34 #include "cppunit/cppunit_proxy.h"
  35 #include "size_check.h"
  36
  37 #include <cds/opt/hash.h>
  38 #include <cds/os/timer.h>
  39 #include <functional>   // ref
  40
  41 // forward namespace declaration
  42 namespace cds {
  43     namespace container {}
  44     namespace opt {}
  45 }
  46
  47 namespace set {
  48     using misc::check_size;
  49
  50     namespace cc = cds::container;
  51     namespace co = cds::opt;
  52
  53
  54     class HashSetHdrTest: public CppUnitMini::TestCase
  55     {
  56     public:
  57         struct stat
  58         {
  59             unsigned int nFindCount     ;   // count of find-functor calling
  60             unsigned int nUpdateNewCount;
  61             unsigned int nUpdateCount;
  62
  63             stat()
  64             {
  65                 memset( this, 0, sizeof(*this));
  66             }
  67
  68             void copy( stat const& s )
  69             {
  70                 nFindCount = s.nFindCount;
  71                 nUpdateCount = s.nUpdateCount;
  72                 nUpdateNewCount = s.nUpdateNewCount;
  73             }
  74         };
  75
  76         struct item: public stat
  77         {
  78             int nKey;
  79             int nVal;
  80
  81             item()
  82             {}
  83
  84             item( int key )
  85                 : nKey( key )
  86                 , nVal( key )
  87             {}
  88
  89             item (int key, int val )
  90                 : nKey(key)
  91                 , nVal( val )
  92             {}
  93
  94             item( std::pair<int,int> const& p )
  95                 : nKey( p.first )
  96                 , nVal( p.second )
  97             {}
  98
  99             item( item const& i )
 100                 : nKey( i.nKey )
 101                 , nVal( i.nVal )
 102             {}
 103
 104             item& operator=(item const& i)
 105             {
 106                 nKey = i.nKey;
 107                 nVal = i.nVal;
 108                 stat::copy(i);
 109
 110                 return *this;
 111             }
 112
 113             item( item&& i )
 114                 : nKey( i.nKey )
 115                 , nVal( i.nVal )
 116             {}
 117
 118             //item& operator=(item&& i)
 119             //{
 120             //    nKey = i.nKey;
 121             //    nVal = i.nVal;
 122             //    return *this;
 123             //}
 124
 125             int key() const
 126             {
 127                 return nKey;
 128             }
 129
 130             int val() const
 131             {
 132                 return nVal;
 133             }
 134         };
 135
 136         struct hash_int {
 137             size_t operator()( int i ) const
 138             {
 139                 return co::v::hash<int>()( i );
 140             }
 141
 142             size_t operator()( std::pair<int,int> const& i ) const
 143             {
 144                 return co::v::hash<int>()( i.first );
 145             }
 146
 147             template <typename Item>
 148             size_t operator()( Item const& i ) const
 149             {
 150                 return (*this)( i.key() );
 151             }
 152         };
 153
 154         struct simple_item_counter {
 155             size_t  m_nCount;
 156
 157             simple_item_counter()
 158                 : m_nCount(0)
 159             {}
 160
 161             size_t operator ++()
 162             {
 163                 return ++m_nCount;
 164             }
 165
 166             size_t operator --()
 167             {
 168                 return --m_nCount;
 169             }
 170
 171             void reset()
 172             {
 173                 m_nCount = 0;
 174             }
 175
 176             operator size_t() const
 177             {
 178                 return m_nCount;
 179             }
 180         };
 181
 182         template <typename T>
 183         struct less
 184         {
 185             bool operator ()(const T& v1, const T& v2 ) const
 186             {
 187                 return v1.key() < v2.key();
 188             }
 189
 190             template <typename Q>
 191             bool operator ()(const T& v1, const Q& v2 ) const
 192             {
 193                 return v1.key() < v2;
 194             }
 195
 196             template <typename Q>
 197             bool operator ()(const Q& v1, const T& v2 ) const
 198             {
 199                 return v1 < v2.key();
 200             }
 201
 202             bool operator ()( std::pair<int, int> const& v1, const T& v2 ) const
 203             {
 204                 return v1.first < v2.key();
 205             }
 206
 207             bool operator ()(const T& v1, std::pair<int, int> const& v2 ) const
 208             {
 209                 return v1.key() < v2.first;
 210             }
 211         };
 212
 213         struct other_item {
 214             int nKey;
 215
 216             other_item( int key )
 217                 : nKey(key)
 218             {}
 219
 220             int key() const
 221             {
 222                 return nKey;
 223             }
 224         };
 225
 226         struct other_less
 227         {
 228             template <typename T>
 229             bool operator ()(T const& v1, other_item const& v2 ) const
 230             {
 231                 return v1.key() < v2.nKey;
 232             }
 233             template <typename T>
 234             bool operator ()(other_item const& v1, T const& v2 ) const
 235             {
 236                 return v1.nKey < v2.key();
 237             }
 238         };
 239
 240         template <typename T>
 241         struct cmp {
 242             int operator ()(const T& v1, const T& v2 ) const
 243             {
 244                 if ( v1.key() < v2.key() )
 245                     return -1;
 246                 return v1.key() > v2.key() ? 1 : 0;
 247             }
 248
 249             template <typename Q>
 250             int operator ()(const T& v1, const Q& v2 ) const
 251             {
 252                 if ( v1.key() < v2 )
 253                     return -1;
 254                 return v1.key() > v2 ? 1 : 0;
 255             }
 256
 257             template <typename Q>
 258             int operator ()(const Q& v1, const T& v2 ) const
 259             {
 260                 if ( v1 < v2.key() )
 261                     return -1;
 262                 return v1 > v2.key() ? 1 : 0;
 263             }
 264
 265             int operator()( std::pair<int,int> const& v1, T const& v2 ) const
 266             {
 267                 if ( v1.first < v2.key() )
 268                     return -1;
 269                 return v1.first > v2.key() ? 1 : 0;
 270             }
 271
 272             int operator()( T const& v1, std::pair<int,int> const& v2 ) const
 273             {
 274                 if ( v1.key() < v2.first )
 275                     return -1;
 276                 return v1.key() > v2.first ? 1 : 0;
 277             }
 278         };
 279
 280         template <typename T>
 281         struct equal
 282         {
 283             bool operator ()(const T& v1, const T& v2 ) const
 284             {
 285                 return v1.key() == v2.key();
 286             }
 287
 288             template <typename Q>
 289             bool operator ()(const T& v1, const Q& v2 ) const
 290             {
 291                 return v1.key() == v2;
 292             }
 293
 294             template <typename Q>
 295             bool operator ()(const Q& v1, const T& v2 ) const
 296             {
 297                 return v1 == v2.key();
 298             }
 299
 300             bool operator ()( std::pair<int, int> const& v1, const T& v2 ) const
 301             {
 302                 return v1.first == v2.key();
 303             }
 304
 305             bool operator ()(const T& v1, std::pair<int, int> const& v2 ) const
 306             {
 307                 return v1.key() == v2.first;
 308             }
 309         };
 310
 311         struct find_functor
 312         {
 313             template <typename Item, typename T>
 314             void operator()( Item& i, T& /*val*/ ) const
 315             {
 316                 ++i.nFindCount;
 317             }
 318             template <typename Item, typename T>
 319             void operator()( Item& i, T const& /*val*/ ) const
 320             {
 321                 ++i.nFindCount;
 322             }
 323         };
 324
 325         template <typename Item>
 326         struct copy_found
 327         {
 328             Item    m_found;
 329
 330             template <typename T>
 331             void operator()( Item& i, T& /*val*/ )
 332             {
 333                 m_found = i;
 334             }
 335
 336             void operator()( Item const& i )
 337             {
 338                 m_found = i;
 339             }
 340         };
 341
 342         struct insert_functor
 343         {
 344             template <typename Item>
 345             void operator()(Item& i )
 346             {
 347                 i.nVal = i.nKey * 100;
 348             }
 349         };
 350
 351         template <typename Item, typename Q>
 352         static void udate_func( bool bNew, Item& i, Q& /*val*/ )
 353         {
 354             if ( bNew )
 355                 ++i.nUpdateNewCount;
 356             else
 357                 ++i.nUpdateCount;
 358         }
 359
 360         struct udate_functor
 361         {
 362             template <typename Item, typename Q>
 363             void operator()( bool bNew, Item& i, Q& val )
 364             {
 365                 udate_func( bNew, i, val );
 366             }
 367         };
 368
 369         template <class Set>
 370         void test_int()
 371         {
 372             Set s( 100, 4 );
 373             test_int_with( s );
 374
 375             // extract/get test
 376             CPPUNIT_ASSERT( s.empty() );
 377             {
 378                 const int nLimit = 100;
 379                 typename Set::guarded_ptr gp;
 380                 int arrRandom[nLimit];
 381                 for ( int i = 0; i < nLimit; ++i )
 382                     arrRandom[i] = i;
 383                 shuffle( arrRandom, arrRandom + nLimit );
 384
 385                 for ( int i = 0; i < nLimit; ++i )
 386                     CPPUNIT_ASSERT( s.insert( arrRandom[i] ));
 387
 388                 for ( int i = 0; i < nLimit; ++i ) {
 389                     int nKey = arrRandom[i];
 390                     gp = s.get( nKey );
 391                     CPPUNIT_ASSERT( gp );
 392                     CPPUNIT_ASSERT( !gp.empty());
 393                     CPPUNIT_CHECK( gp->nKey == nKey );
 394                     CPPUNIT_CHECK( gp->nVal == nKey );
 395                     gp.release();
 396
 397                     gp = s.extract( nKey );
 398                     CPPUNIT_ASSERT( gp );
 399                     CPPUNIT_ASSERT( !gp.empty());
 400                     CPPUNIT_CHECK( gp->nKey == nKey );
 401                     CPPUNIT_CHECK( gp->nVal == nKey );
 402                     gp.release();
 403                     CPPUNIT_CHECK( !s.get( nKey ) );
 404
 405                     gp = s.extract( nKey );
 406                     CPPUNIT_CHECK( !gp );
 407                     CPPUNIT_CHECK( gp.empty());
 408                 }
 409                 CPPUNIT_ASSERT( s.empty() );
 410
 411
 412                 for ( int i = 0; i < nLimit; ++i )
 413                     CPPUNIT_ASSERT( s.insert( arrRandom[i] ));
 414
 415                 for ( int i = 0; i < nLimit; ++i ) {
 416                     int nKey = arrRandom[i];
 417                     gp = s.get_with( other_item( nKey ), other_less() );
 418                     CPPUNIT_ASSERT( gp );
 419                     CPPUNIT_ASSERT( !gp.empty());
 420                     CPPUNIT_CHECK( gp->nKey == nKey );
 421                     CPPUNIT_CHECK( gp->nVal == nKey );
 422                     gp.release();
 423
 424                     gp = s.extract_with( other_item( nKey ), other_less() );
 425                     CPPUNIT_ASSERT( gp );
 426                     CPPUNIT_ASSERT( !gp.empty());
 427                     CPPUNIT_CHECK( gp->nKey == nKey );
 428                     CPPUNIT_CHECK( gp->nVal == nKey );
 429                     gp.release();
 430
 431                     gp = s.get_with( other_item( nKey ), other_less() );
 432                     CPPUNIT_CHECK( !gp );
 433
 434                     CPPUNIT_CHECK( !s.extract_with(other_item(nKey), other_less() ));
 435                     CPPUNIT_CHECK( gp.empty());
 436                 }
 437                 CPPUNIT_ASSERT( s.empty() );
 438             }
 439
 440             // iterator test
 441             test_iter<Set>();
 442         }
 443
 444         template <class Set>
 445         void test_int_rcu()
 446         {
 447             Set s( 100, 4 );
 448             test_int_with( s );
 449
 450             // extract/get test
 451             {
 452                 typedef typename Set::gc    rcu;
 453                 typedef typename Set::rcu_lock rcu_lock;
 454                 typedef typename Set::value_type value_type;
 455                 typename Set::exempt_ptr ep;
 456
 457                 static size_t const nLimit = 100;
 458                 int arr[nLimit];
 459                 for ( size_t i = 0; i < nLimit; ++i )
 460                     arr[i] = (int) i;
 461                 shuffle( arr, arr + nLimit );
 462
 463                 for ( size_t i = 0; i < nLimit; ++i )
 464                     CPPUNIT_ASSERT( s.insert( arr[i] ));
 465
 466                 for ( size_t i = 0; i < nLimit; i += 2 ) {
 467                     value_type * pVal;
 468                     int nKey = arr[i];
 469                     {
 470                         rcu_lock l;
 471                         pVal = s.get( nKey );
 472                         CPPUNIT_ASSERT( pVal != nullptr );
 473                         CPPUNIT_CHECK( pVal->nKey == nKey );
 474                         CPPUNIT_CHECK( pVal->nVal == nKey );
 475
 476                         ep = s.extract( nKey );
 477                         CPPUNIT_ASSERT( ep );
 478                         CPPUNIT_ASSERT( !ep.empty() );
 479                         CPPUNIT_CHECK( pVal->nKey == ep->nKey );
 480                         CPPUNIT_CHECK( pVal->nVal == (*ep).nVal );
 481                     }
 482                     ep.release();
 483                     {
 484                         rcu_lock l;
 485                         CPPUNIT_CHECK( s.get( nKey ) == nullptr );
 486                         ep = s.extract( nKey );
 487                         CPPUNIT_CHECK( !ep );
 488                         CPPUNIT_CHECK( ep.empty() );
 489
 490                         nKey = arr[i+1];
 491                         pVal = s.get_with( other_item(nKey), other_less() );
 492                         CPPUNIT_ASSERT( pVal != nullptr );
 493                         CPPUNIT_CHECK( pVal->nKey == nKey );
 494                         CPPUNIT_CHECK( pVal->nVal == nKey );
 495
 496                         ep = s.extract_with( other_item( nKey ), other_less() );
 497                         CPPUNIT_ASSERT( ep );
 498                         CPPUNIT_ASSERT( !ep.empty() );
 499                         CPPUNIT_CHECK( pVal->nKey == ep->nKey );
 500                         CPPUNIT_CHECK( pVal->nVal == (*ep).nVal );
 501                     }
 502                     ep.release();
 503                     {
 504                         rcu_lock l;
 505                         CPPUNIT_CHECK( s.get_with( other_item( nKey ), other_less() ) == nullptr );
 506                         CPPUNIT_CHECK( !s.extract_with( other_item(nKey), other_less() ));
 507                         CPPUNIT_CHECK( ep.empty() );
 508                     }
 509                 }
 510                 CPPUNIT_CHECK( s.empty() );
 511                 CPPUNIT_CHECK( check_size( s, 0 ));
 512                 {
 513                     rcu_lock l;
 514                     CPPUNIT_CHECK( s.get( int( nLimit / 2 ) ) == nullptr );
 515                     ep = s.extract( int( nLimit / 2 ) );
 516                     CPPUNIT_CHECK( !ep );
 517                     CPPUNIT_CHECK( ep.empty() );
 518                 }
 519             }
 520
 521             // iterator test
 522             test_iter<Set>();
 523         }
 524
 525         template <class Set>
 526         void test_int_rcu_michael_list()
 527         {
 528             Set s( 100, 4 );
 529             test_int_with( s );
 530
 531             // extract/get test
 532             {
 533                 typedef typename Set::gc    rcu;
 534                 typedef typename Set::rcu_lock rcu_lock;
 535                 typedef typename Set::value_type value_type;
 536                 typename Set::exempt_ptr ep;
 537                 typename Set::raw_ptr gp;
 538
 539                 static size_t const nLimit = 100;
 540                 int arr[nLimit];
 541                 for ( size_t i = 0; i < nLimit; ++i )
 542                     arr[i] = (int) i;
 543                 shuffle( arr, arr + nLimit );
 544
 545                 for ( size_t i = 0; i < nLimit; ++i )
 546                     CPPUNIT_ASSERT( s.insert( arr[i] ));
 547
 548                 for ( size_t i = 0; i < nLimit; i += 2 ) {
 549                     int nKey = arr[i];
 550                     {
 551                         rcu_lock l;
 552                         gp = s.get( nKey );
 553                         CPPUNIT_ASSERT( gp );
 554                         CPPUNIT_CHECK( gp->nKey == nKey );
 555                         CPPUNIT_CHECK( gp->nVal == nKey );
 556                     }
 557                     gp.release();
 558
 559                     ep = s.extract( nKey );
 560                     CPPUNIT_ASSERT( ep );
 561                     CPPUNIT_ASSERT( !ep.empty() );
 562                     CPPUNIT_CHECK( nKey == ep->nKey );
 563                     CPPUNIT_CHECK( nKey == (*ep).nVal );
 564                     ep.release();
 565
 566                     {
 567                         rcu_lock l;
 568                         CPPUNIT_CHECK( !s.get( nKey ));
 569                     }
 570                     ep = s.extract( nKey );
 571                     CPPUNIT_CHECK( !ep );
 572                     CPPUNIT_CHECK( ep.empty() );
 573
 574                     {
 575                         rcu_lock l;
 576                         nKey = arr[i+1];
 577                         gp = s.get_with( other_item(nKey), other_less() );
 578                         CPPUNIT_ASSERT( gp );
 579                         CPPUNIT_CHECK( gp->nKey == nKey );
 580                         CPPUNIT_CHECK( gp->nVal == nKey );
 581                     }
 582                     gp.release();
 583
 584                     ep = s.extract_with( other_item( nKey ), other_less() );
 585                     CPPUNIT_ASSERT( ep );
 586                     CPPUNIT_ASSERT( !ep.empty() );
 587                     CPPUNIT_CHECK( nKey == ep->nKey );
 588                     CPPUNIT_CHECK( nKey == (*ep).nVal );
 589                     ep.release();
 590
 591                     {
 592                         rcu_lock l;
 593                         CPPUNIT_CHECK( !s.get_with( other_item( nKey ), other_less()));
 594                     }
 595                     CPPUNIT_CHECK( !s.extract_with( other_item(nKey), other_less() ));
 596                     CPPUNIT_CHECK( ep.empty() );
 597                 }
 598                 CPPUNIT_CHECK( s.empty() );
 599                 CPPUNIT_CHECK( check_size( s, 0 ));
 600
 601                 {
 602                     rcu_lock l;
 603                     CPPUNIT_CHECK( !s.get( int( nLimit / 2 )));
 604                 }
 605
 606                 ep = s.extract( int( nLimit / 2 ) );
 607                 CPPUNIT_CHECK( !ep );
 608                 CPPUNIT_CHECK( ep.empty() );
 609             }
 610
 611             // iterator test
 612             test_iter<Set>();
 613         }
 614
 615
 616         template <class Set>
 617         void test_int_with( Set& s)
 618         {
 619             typedef typename Set::value_type    value_type;
 620
 621             item itm;
 622             int key;
 623
 624             // insert/find test
 625             CPPUNIT_ASSERT( !s.contains( 10 ) );
 626             CPPUNIT_ASSERT( s.insert( 10 ));
 627             CPPUNIT_ASSERT( !s.empty() );
 628             CPPUNIT_ASSERT( check_size( s, 1 ));
 629             CPPUNIT_ASSERT( s.contains( 10 ) );
 630
 631             CPPUNIT_ASSERT( !s.insert( 10 ));
 632             CPPUNIT_ASSERT( !s.empty() );
 633             CPPUNIT_ASSERT( check_size( s, 1 ));
 634
 635             CPPUNIT_ASSERT( !s.contains( 20, less<value_type>() ) );
 636             CPPUNIT_ASSERT( s.insert( std::make_pair(20, 25) ));
 637             CPPUNIT_ASSERT( !s.empty() );
 638             CPPUNIT_ASSERT( check_size( s, 2 ));
 639             CPPUNIT_ASSERT( s.contains( 10, less<value_type>() ) );
 640             CPPUNIT_ASSERT( s.contains( key = 20 ) );
 641             CPPUNIT_ASSERT( s.find_with( key, less<value_type>(), find_functor() ) );
 642             {
 643                 copy_found<item> f;
 644                 key = 20;
 645                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 646                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 647                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 648                 CPPUNIT_ASSERT( f.m_found.nFindCount == 1 );
 649             }
 650             CPPUNIT_ASSERT( s.find( key, find_functor() ) );
 651             {
 652                 copy_found<item> f;
 653                 key = 20;
 654                 CPPUNIT_ASSERT( s.find_with( key, less<value_type>(), std::ref( f ) ) );
 655                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 656                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 657                 CPPUNIT_ASSERT( f.m_found.nFindCount == 2 );
 658             }
 659             CPPUNIT_ASSERT( !s.empty() );
 660             CPPUNIT_ASSERT( check_size( s, 2 ));
 661
 662             CPPUNIT_ASSERT( !s.contains( 25 ) );
 663             CPPUNIT_ASSERT( s.insert( std::make_pair(25, -1), insert_functor() ));
 664             CPPUNIT_ASSERT( !s.empty() );
 665             CPPUNIT_ASSERT( check_size( s, 3 ));
 666             {
 667                 copy_found<item> f;
 668                 key = 25;
 669                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 670                 CPPUNIT_ASSERT( f.m_found.nKey == 25 );
 671                 CPPUNIT_ASSERT( f.m_found.nVal == 2500 );
 672             }
 673
 674             // update test
 675             key = 10;
 676             {
 677                 copy_found<item> f;
 678                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 679                 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
 680                 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
 681                 CPPUNIT_ASSERT( f.m_found.nUpdateCount == 0 );
 682                 CPPUNIT_ASSERT( f.m_found.nUpdateNewCount == 0 );
 683             }
 684             std::pair<bool, bool> updateResult = s.update( key, udate_functor() );
 685             CPPUNIT_ASSERT( updateResult.first && !updateResult.second );
 686             CPPUNIT_ASSERT( !s.empty() );
 687             CPPUNIT_ASSERT( check_size( s, 3 ));
 688             {
 689                 copy_found<item> f;
 690                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 691                 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
 692                 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
 693                 CPPUNIT_ASSERT( f.m_found.nUpdateCount == 1 );
 694                 CPPUNIT_ASSERT( f.m_found.nUpdateNewCount == 0 );
 695             }
 696
 697             updateResult = s.update(std::make_pair(13, 1300), udate_functor(), false);
 698             CPPUNIT_ASSERT(!updateResult.first && !updateResult.second);
 699             CPPUNIT_ASSERT(check_size(s, 3));
 700
 701             updateResult = s.update( std::make_pair(13, 1300), udate_functor() );
 702             CPPUNIT_ASSERT( updateResult.first && updateResult.second );
 703             CPPUNIT_ASSERT( !s.empty() );
 704             CPPUNIT_ASSERT( check_size( s, 4 ));
 705             {
 706                 copy_found<item> f;
 707                 key = 13;
 708                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 709                 CPPUNIT_ASSERT( f.m_found.nKey == 13 );
 710                 CPPUNIT_ASSERT( f.m_found.nVal == 1300 );
 711                 CPPUNIT_ASSERT( f.m_found.nUpdateCount == 0 );
 712                 CPPUNIT_ASSERT( f.m_found.nUpdateNewCount == 1 );
 713             }
 714
 715             // erase test
 716             CPPUNIT_ASSERT( s.erase(13) );
 717             CPPUNIT_ASSERT( !s.contains( 13 ));
 718             CPPUNIT_ASSERT( !s.empty() );
 719             CPPUNIT_ASSERT( check_size( s, 3 ));
 720             CPPUNIT_ASSERT( !s.erase(13) );
 721             CPPUNIT_ASSERT( !s.empty() );
 722             CPPUNIT_ASSERT( check_size( s, 3 ));
 723
 724             CPPUNIT_ASSERT( s.contains( 10 ));
 725             CPPUNIT_ASSERT( s.erase_with( 10, less<value_type>() ));
 726             CPPUNIT_ASSERT( !s.contains( 10 ));
 727             CPPUNIT_ASSERT( !s.empty() );
 728             CPPUNIT_ASSERT( check_size( s, 2 ));
 729             CPPUNIT_ASSERT( !s.erase_with(10, less<value_type>()) );
 730             CPPUNIT_ASSERT( !s.empty() );
 731             CPPUNIT_ASSERT( check_size( s, 2 ));
 732
 733             CPPUNIT_ASSERT( s.contains(20) );
 734             {
 735                 copy_found<item> f;
 736                 CPPUNIT_ASSERT( s.erase( 20, std::ref( f ) ) );
 737                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 738                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 739
 740                 CPPUNIT_ASSERT( s.insert(235))
 741                     CPPUNIT_ASSERT( s.erase_with( 235, less<value_type>(), std::ref( f ) ) );
 742                 CPPUNIT_ASSERT( f.m_found.nKey == 235 );
 743                 CPPUNIT_ASSERT( f.m_found.nVal == 235 );
 744             }
 745             CPPUNIT_ASSERT( !s.contains( 20 ));
 746             CPPUNIT_ASSERT( !s.empty() );
 747             CPPUNIT_ASSERT( check_size( s, 1 ));
 748
 749             s.clear();
 750             CPPUNIT_ASSERT( s.empty() );
 751             CPPUNIT_ASSERT( check_size( s, 0 ));
 752
 753             // emplace test
 754             CPPUNIT_ASSERT( s.emplace( 151 )) ;  // key = 151,  val = 151
 755             CPPUNIT_ASSERT( s.emplace( 174, 471 )) ;    // key = 174, val = 471
 756             CPPUNIT_ASSERT( s.emplace( std::make_pair( 190, 91 ) )) ; // key == 190, val = 91
 757             CPPUNIT_ASSERT( !s.empty() );
 758             CPPUNIT_ASSERT( check_size( s, 3 ));
 759
 760             CPPUNIT_ASSERT( s.contains(151));
 761             CPPUNIT_ASSERT( s.contains(174, less<value_type>()));
 762             CPPUNIT_ASSERT( s.contains(190));
 763
 764             {
 765                 copy_found<item> f;
 766                 key = 151;
 767                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 768                 CPPUNIT_ASSERT( f.m_found.nKey == 151 );
 769                 CPPUNIT_ASSERT( f.m_found.nVal == 151 );
 770
 771                 key = 174;
 772                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 773                 CPPUNIT_ASSERT( f.m_found.nKey == 174 );
 774                 CPPUNIT_ASSERT( f.m_found.nVal == 471 );
 775
 776                 key = 190;
 777                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 778                 CPPUNIT_ASSERT( f.m_found.nKey == 190 );
 779                 CPPUNIT_ASSERT( f.m_found.nVal == 91 );
 780             }
 781
 782             s.clear();
 783             CPPUNIT_ASSERT( s.empty() );
 784             CPPUNIT_ASSERT( check_size( s, 0 ));
 785         }
 786
 787
 788         template <class Set>
 789         void test_int_nogc()
 790         {
 791             typedef typename Set::value_type        value_type;
 792             typedef typename Set::iterator          iterator;
 793             typedef typename Set::const_iterator    const_iterator;
 794
 795             {
 796                 Set s( 52, 4 );
 797                 iterator it;
 798
 799                 CPPUNIT_ASSERT( s.empty() );
 800                 CPPUNIT_ASSERT( check_size( s, 0 ));
 801
 802                 // insert
 803                 it = s.insert( 10 );
 804                 CPPUNIT_ASSERT( it != s.end() );
 805                 CPPUNIT_ASSERT( it->key() == 10 );
 806                 CPPUNIT_ASSERT( it->val() == 10 );
 807                 CPPUNIT_ASSERT( !s.empty() );
 808                 CPPUNIT_ASSERT( check_size( s, 1 ));
 809                 CPPUNIT_ASSERT( s.insert( 10 ) == s.end() );
 810
 811                 it = s.insert( std::make_pair( 50, 25 ));
 812                 CPPUNIT_ASSERT( it != s.end() );
 813                 CPPUNIT_ASSERT( it->key() == 50 );
 814                 CPPUNIT_ASSERT( it->val() == 25 );
 815                 CPPUNIT_ASSERT( !s.empty() );
 816                 CPPUNIT_ASSERT( check_size( s, 2 ));
 817                 CPPUNIT_ASSERT( s.insert( 50 ) == s.end() );
 818
 819                 // update
 820                 std::pair< iterator, bool>  updateResult;
 821                 updateResult = s.update(20, false);
 822                 CPPUNIT_ASSERT(updateResult.first == s.end());
 823                 CPPUNIT_ASSERT(!updateResult.second);
 824                 CPPUNIT_ASSERT(check_size(s, 2));
 825
 826                 updateResult = s.update( 20 );
 827                 CPPUNIT_ASSERT( updateResult.first != s.end() );
 828                 CPPUNIT_ASSERT( updateResult.second  );
 829                 CPPUNIT_ASSERT( updateResult.first->key() == 20 );
 830                 CPPUNIT_ASSERT( updateResult.first->val() == 20 );
 831                 CPPUNIT_ASSERT( !s.empty() );
 832                 CPPUNIT_ASSERT( check_size( s, 3 ));
 833
 834                 updateResult = s.update( std::make_pair( 20, 200 ));
 835                 CPPUNIT_ASSERT( updateResult.first != s.end() );
 836                 CPPUNIT_ASSERT( !updateResult.second  );
 837                 CPPUNIT_ASSERT( updateResult.first->key() == 20 );
 838                 CPPUNIT_ASSERT( updateResult.first->val() == 20 );
 839                 CPPUNIT_ASSERT( !s.empty() );
 840                 CPPUNIT_ASSERT( check_size( s, 3 ));
 841                 updateResult.first->nVal = 22;
 842
 843                 updateResult = s.update( std::make_pair( 30, 33 ));
 844                 CPPUNIT_ASSERT( updateResult.first != s.end() );
 845                 CPPUNIT_ASSERT( updateResult.second  );
 846                 CPPUNIT_ASSERT( updateResult.first->key() == 30 );
 847                 CPPUNIT_ASSERT( updateResult.first->val() == 33 );
 848                 CPPUNIT_ASSERT( !s.empty() );
 849                 CPPUNIT_ASSERT( check_size( s, 4 ));
 850
 851                 // find
 852                 it = s.contains( 10 );
 853                 CPPUNIT_ASSERT( it != s.end() );
 854                 CPPUNIT_ASSERT( it->key() == 10 );
 855                 CPPUNIT_ASSERT( it->val() == 10 );
 856
 857                 it = s.contains( 20, less<value_type>() );
 858                 CPPUNIT_ASSERT( it != s.end() );
 859                 CPPUNIT_ASSERT( it->key() == 20 );
 860                 CPPUNIT_ASSERT( it->val() == 22 );
 861
 862                 it = s.contains( 30 );
 863                 CPPUNIT_ASSERT( it != s.end() );
 864                 CPPUNIT_ASSERT( it->key() == 30 );
 865                 CPPUNIT_ASSERT( it->val() == 33 );
 866
 867                 it = s.contains( 40 );
 868                 CPPUNIT_ASSERT( it == s.end() );
 869
 870                 it = s.contains( 50 );
 871                 CPPUNIT_ASSERT( it != s.end() );
 872                 CPPUNIT_ASSERT( it->key() == 50 );
 873                 CPPUNIT_ASSERT( it->val() == 25 );
 874
 875                 // emplace test
 876                 it = s.emplace( 151 ) ;  // key = 151,  val = 151
 877                 CPPUNIT_ASSERT( it != s.end() );
 878                 CPPUNIT_ASSERT( it->key() == 151 );
 879                 CPPUNIT_ASSERT( it->val() == 151 );
 880
 881                 it = s.emplace( 174, 471 ) ; // key == 174, val = 471
 882                 CPPUNIT_ASSERT( it != s.end() );
 883                 CPPUNIT_ASSERT( it->key() == 174 );
 884                 CPPUNIT_ASSERT( it->val() == 471 );
 885
 886                 it = s.emplace( std::make_pair( 190, 91 )) ; // key == 190, val = 91
 887                 CPPUNIT_ASSERT( it != s.end() );
 888                 CPPUNIT_ASSERT( it->key() == 190 );
 889                 CPPUNIT_ASSERT( it->val() == 91 );
 890
 891                 it = s.contains( 174 );
 892                 CPPUNIT_ASSERT( it != s.end() );
 893                 CPPUNIT_ASSERT( it->key() == 174 );
 894                 CPPUNIT_ASSERT( it->val() == 471 );
 895
 896                 it = s.contains( 190, less<value_type>() );
 897                 CPPUNIT_ASSERT( it != s.end() );
 898                 CPPUNIT_ASSERT( it->key() == 190 );
 899                 CPPUNIT_ASSERT( it->val() == 91 );
 900
 901                 it = s.contains( 151 );
 902                 CPPUNIT_ASSERT( it != s.end() );
 903                 CPPUNIT_ASSERT( it->key() == 151 );
 904                 CPPUNIT_ASSERT( it->val() == 151 );
 905
 906                 //s.clear();
 907                 //CPPUNIT_ASSERT( s.empty() );
 908                 //CPPUNIT_ASSERT( check_size( s, 0 ));
 909             }
 910
 911             {
 912                 Set s( 52, 4 );
 913
 914                 // iterator test
 915                 for ( int i = 0; i < 500; ++i ) {
 916                     CPPUNIT_ASSERT( s.insert( std::make_pair( i, i * 2) ) != s.end() );
 917                 }
 918                 for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 919                     iterator it2 = it;
 920                     CPPUNIT_CHECK( it2 == it );
 921                     CPPUNIT_CHECK( it2 != itEnd );
 922                     CPPUNIT_ASSERT( (*it).nKey * 2 == it->nVal );
 923                     it->nVal = (*it).nKey;
 924                 }
 925
 926                 Set const& refSet = s;
 927                 for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
 928                     CPPUNIT_ASSERT( (*it).nKey == it->nVal );
 929                 }
 930             }
 931         }
 932
 933         template <class Set>
 934         void test_int_nogc_unordered()
 935         {
 936             typedef typename Set::value_type        value_type;
 937             typedef typename Set::iterator          iterator;
 938             typedef typename Set::const_iterator    const_iterator;
 939
 940             {
 941                 Set s( 52, 4 );
 942                 iterator it;
 943
 944                 CPPUNIT_ASSERT( s.empty() );
 945                 CPPUNIT_ASSERT( check_size( s, 0 ));
 946
 947                 // insert
 948                 it = s.insert( 10 );
 949                 CPPUNIT_ASSERT( it != s.end() );
 950                 CPPUNIT_ASSERT( it->key() == 10 );
 951                 CPPUNIT_ASSERT( it->val() == 10 );
 952                 CPPUNIT_ASSERT( !s.empty() );
 953                 CPPUNIT_ASSERT( check_size( s, 1 ));
 954                 CPPUNIT_ASSERT( s.insert( 10 ) == s.end() );
 955
 956                 it = s.insert( std::make_pair( 50, 25 ));
 957                 CPPUNIT_ASSERT( it != s.end() );
 958                 CPPUNIT_ASSERT( it->key() == 50 );
 959                 CPPUNIT_ASSERT( it->val() == 25 );
 960                 CPPUNIT_ASSERT( !s.empty() );
 961                 CPPUNIT_ASSERT( check_size( s, 2 ));
 962                 CPPUNIT_ASSERT( s.insert( 50 ) == s.end() );
 963
 964                 // update
 965                 std::pair< iterator, bool>  updateResult;
 966                 updateResult = s.update(20, false);
 967                 CPPUNIT_ASSERT(updateResult.first == s.end());
 968                 CPPUNIT_ASSERT(!updateResult.second);
 969                 CPPUNIT_ASSERT(check_size(s, 2));
 970
 971                 updateResult = s.update( 20 );
 972                 CPPUNIT_ASSERT( updateResult.first != s.end() );
 973                 CPPUNIT_ASSERT( updateResult.second  );
 974                 CPPUNIT_ASSERT( updateResult.first->key() == 20 );
 975                 CPPUNIT_ASSERT( updateResult.first->val() == 20 );
 976                 CPPUNIT_ASSERT( !s.empty() );
 977                 CPPUNIT_ASSERT( check_size( s, 3 ));
 978
 979                 updateResult = s.update( std::make_pair( 20, 200 ));
 980                 CPPUNIT_ASSERT( updateResult.first != s.end() );
 981                 CPPUNIT_ASSERT( !updateResult.second  );
 982                 CPPUNIT_ASSERT( updateResult.first->key() == 20 );
 983                 CPPUNIT_ASSERT( updateResult.first->val() == 20 );
 984                 CPPUNIT_ASSERT( !s.empty() );
 985                 CPPUNIT_ASSERT( check_size( s, 3 ));
 986                 updateResult.first->nVal = 22;
 987
 988                 updateResult = s.update( std::make_pair( 30, 33 ));
 989                 CPPUNIT_ASSERT( updateResult.first != s.end() );
 990                 CPPUNIT_ASSERT( updateResult.second  );
 991                 CPPUNIT_ASSERT( updateResult.first->key() == 30 );
 992                 CPPUNIT_ASSERT( updateResult.first->val() == 33 );
 993                 CPPUNIT_ASSERT( !s.empty() );
 994                 CPPUNIT_ASSERT( check_size( s, 4 ));
 995
 996                 // find
 997                 it = s.contains( 10 );
 998                 CPPUNIT_ASSERT( it != s.end() );
 999                 CPPUNIT_ASSERT( it->key() == 10 );
1000                 CPPUNIT_ASSERT( it->val() == 10 );
1001
1002                 it = s.contains( 20, equal<value_type>() );
1003                 CPPUNIT_ASSERT( it != s.end() );
1004                 CPPUNIT_ASSERT( it->key() == 20 );
1005                 CPPUNIT_ASSERT( it->val() == 22 );
1006
1007                 it = s.contains( 30 );
1008                 CPPUNIT_ASSERT( it != s.end() );
1009                 CPPUNIT_ASSERT( it->key() == 30 );
1010                 CPPUNIT_ASSERT( it->val() == 33 );
1011
1012                 it = s.contains( 40 );
1013                 CPPUNIT_ASSERT( it == s.end() );
1014
1015                 it = s.contains( 50 );
1016                 CPPUNIT_ASSERT( it != s.end() );
1017                 CPPUNIT_ASSERT( it->key() == 50 );
1018                 CPPUNIT_ASSERT( it->val() == 25 );
1019
1020                 // emplace test
1021                 it = s.emplace( 151 ) ;  // key = 151,  val = 151
1022                 CPPUNIT_ASSERT( it != s.end() );
1023                 CPPUNIT_ASSERT( it->key() == 151 );
1024                 CPPUNIT_ASSERT( it->val() == 151 );
1025
1026                 it = s.emplace( 174, 471 ) ; // key == 174, val = 471
1027                 CPPUNIT_ASSERT( it != s.end() );
1028                 CPPUNIT_ASSERT( it->key() == 174 );
1029                 CPPUNIT_ASSERT( it->val() == 471 );
1030
1031                 it = s.emplace( std::make_pair( 190, 91 )) ; // key == 190, val = 91
1032                 CPPUNIT_ASSERT( it != s.end() );
1033                 CPPUNIT_ASSERT( it->key() == 190 );
1034                 CPPUNIT_ASSERT( it->val() == 91 );
1035
1036                 it = s.contains( 174 );
1037                 CPPUNIT_ASSERT( it != s.end() );
1038                 CPPUNIT_ASSERT( it->key() == 174 );
1039                 CPPUNIT_ASSERT( it->val() == 471 );
1040
1041                 it = s.contains( 190, equal<value_type>() );
1042                 CPPUNIT_ASSERT( it != s.end() );
1043                 CPPUNIT_ASSERT( it->key() == 190 );
1044                 CPPUNIT_ASSERT( it->val() == 91 );
1045
1046                 it = s.contains( 151 );
1047                 CPPUNIT_ASSERT( it != s.end() );
1048                 CPPUNIT_ASSERT( it->key() == 151 );
1049                 CPPUNIT_ASSERT( it->val() == 151 );
1050
1051                 //s.clear();
1052                 //CPPUNIT_ASSERT( s.empty() );
1053                 //CPPUNIT_ASSERT( check_size( s, 0 ));
1054             }
1055
1056             {
1057                 Set s( 52, 4 );
1058
1059                 // iterator test
1060                 for ( int i = 0; i < 500; ++i ) {
1061                     CPPUNIT_ASSERT( s.insert( std::make_pair( i, i * 2) ) != s.end() );
1062                 }
1063                 for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
1064                     iterator it2 = it;
1065                     CPPUNIT_CHECK( it2 == it );
1066                     CPPUNIT_CHECK( it2 != itEnd );
1067                     CPPUNIT_ASSERT( (*it).nKey * 2 == it->nVal );
1068                     it->nVal = (*it).nKey;
1069                 }
1070
1071                 Set const& refSet = s;
1072                 for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
1073                     CPPUNIT_ASSERT( (*it).nKey == it->nVal );
1074                 }
1075             }
1076         }
1077         template <class Set>
1078         void test_iter()
1079         {
1080             typedef typename Set::value_type        value_type;
1081             typedef typename Set::iterator          iterator;
1082             typedef typename Set::const_iterator    const_iterator;
1083
1084             Set s( 100, 4 );
1085
1086             const size_t nMaxCount = 500;
1087             for ( int i = 0; size_t(i) < nMaxCount; ++i ) {
1088                 CPPUNIT_ASSERT( s.insert( std::make_pair( i, i * 2) ));
1089             }
1090
1091             {
1092                 typename Set::iterator it( s.begin() );
1093                 typename Set::const_iterator cit( s.cbegin() );
1094                 CPPUNIT_CHECK( it == cit );
1095                 CPPUNIT_CHECK( it != s.end() );
1096                 CPPUNIT_CHECK( it != s.cend() );
1097                 CPPUNIT_CHECK( cit != s.end() );
1098                 CPPUNIT_CHECK( cit != s.cend() );
1099                 ++it;
1100                 CPPUNIT_CHECK( it != cit );
1101                 CPPUNIT_CHECK( it != s.end() );
1102                 CPPUNIT_CHECK( it != s.cend() );
1103                 CPPUNIT_CHECK( cit != s.end() );
1104                 CPPUNIT_CHECK( cit != s.cend() );
1105                 ++cit;
1106                 CPPUNIT_CHECK( it == cit );
1107                 CPPUNIT_CHECK( it != s.end() );
1108                 CPPUNIT_CHECK( it != s.cend() );
1109                 CPPUNIT_CHECK( cit != s.end() );
1110                 CPPUNIT_CHECK( cit != s.cend() );
1111             }
1112
1113             size_t nCount = 0;
1114             for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
1115                 CPPUNIT_ASSERT_EX( (*it).nKey * 2 == it->nVal,
1116                     "Step " << nCount << ": Iterator key=" << it->nKey <<  ", value expected=" << it->nKey * 2 << ", value real=" << it->nVal
1117                     );
1118                 it->nVal = (*it).nKey;
1119                 ++nCount;
1120             }
1121             CPPUNIT_ASSERT( nCount == nMaxCount );
1122
1123             nCount = 0;
1124             Set const& refSet = s;
1125             for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
1126                 CPPUNIT_ASSERT_EX( (*it).nKey == it->nVal,
1127                     "Step " << nCount << ": Iterator key=" << it->nKey <<  ", value expected=" << it->nKey << ", value real=" << it->nVal
1128                     );
1129                 ++nCount;
1130             }
1131             CPPUNIT_ASSERT( nCount == nMaxCount );
1132         }
1133
1134         void Michael_HP_cmp();
1135         void Michael_HP_less();
1136         void Michael_HP_cmpmix();
1137
1138         void Michael_DHP_cmp();
1139         void Michael_DHP_less();
1140         void Michael_DHP_cmpmix();
1141
1142         void Michael_RCU_GPI_cmp();
1143         void Michael_RCU_GPI_less();
1144         void Michael_RCU_GPI_cmpmix();
1145
1146         void Michael_RCU_GPT_cmp();
1147         void Michael_RCU_GPT_less();
1148         void Michael_RCU_GPT_cmpmix();
1149
1150         void Michael_RCU_GPB_cmp();
1151         void Michael_RCU_GPB_less();
1152         void Michael_RCU_GPB_cmpmix();
1153
1154         void Michael_RCU_SHT_cmp();
1155         void Michael_RCU_SHT_less();
1156         void Michael_RCU_SHT_cmpmix();
1157
1158         void Michael_RCU_SHB_cmp();
1159         void Michael_RCU_SHB_less();
1160         void Michael_RCU_SHB_cmpmix();
1161
1162         void Michael_nogc_cmp();
1163         void Michael_nogc_less();
1164         void Michael_nogc_cmpmix();
1165
1166         void Lazy_HP_cmp();
1167         void Lazy_HP_less();
1168         void Lazy_HP_cmpmix();
1169
1170         void Lazy_DHP_cmp();
1171         void Lazy_DHP_less();
1172         void Lazy_DHP_cmpmix();
1173
1174         void Lazy_RCU_GPI_cmp();
1175         void Lazy_RCU_GPI_less();
1176         void Lazy_RCU_GPI_cmpmix();
1177
1178         void Lazy_RCU_GPB_cmp();
1179         void Lazy_RCU_GPB_less();
1180         void Lazy_RCU_GPB_cmpmix();
1181
1182         void Lazy_RCU_GPT_cmp();
1183         void Lazy_RCU_GPT_less();
1184         void Lazy_RCU_GPT_cmpmix();
1185
1186         void Lazy_RCU_SHB_cmp();
1187         void Lazy_RCU_SHB_less();
1188         void Lazy_RCU_SHB_cmpmix();
1189
1190         void Lazy_RCU_SHT_cmp();
1191         void Lazy_RCU_SHT_less();
1192         void Lazy_RCU_SHT_cmpmix();
1193
1194         void Lazy_nogc_cmp();
1195         void Lazy_nogc_less();
1196         void Lazy_nogc_equal();
1197         void Lazy_nogc_cmpmix();
1198
1199         void Split_HP_cmp();
1200         void Split_HP_less();
1201         void Split_HP_cmpmix();
1202         void Split_HP_cmpmix_stat();
1203
1204         void Split_DHP_cmp();
1205         void Split_DHP_less();
1206         void Split_DHP_cmpmix();
1207         void Split_DHP_cmpmix_stat();
1208
1209         void Split_RCU_GPI_cmp();
1210         void Split_RCU_GPI_less();
1211         void Split_RCU_GPI_cmpmix();
1212         void Split_RCU_GPI_cmpmix_stat();
1213
1214         void Split_RCU_GPB_cmp();
1215         void Split_RCU_GPB_less();
1216         void Split_RCU_GPB_cmpmix();
1217         void Split_RCU_GPB_cmpmix_stat();
1218
1219         void Split_RCU_GPT_cmp();
1220         void Split_RCU_GPT_less();
1221         void Split_RCU_GPT_cmpmix();
1222         void Split_RCU_GPT_cmpmix_stat();
1223
1224         void Split_RCU_SHB_cmp();
1225         void Split_RCU_SHB_less();
1226         void Split_RCU_SHB_cmpmix();
1227         void Split_RCU_SHB_cmpmix_stat();
1228
1229         void Split_RCU_SHT_cmp();
1230         void Split_RCU_SHT_less();
1231         void Split_RCU_SHT_cmpmix();
1232         void Split_RCU_SHT_cmpmix_stat();
1233
1234         void Split_nogc_cmp();
1235         void Split_nogc_less();
1236         void Split_nogc_cmpmix();
1237         void Split_nogc_cmpmix_stat();
1238
1239
1240         void Split_Lazy_HP_cmp();
1241         void Split_Lazy_HP_less();
1242         void Split_Lazy_HP_cmpmix();
1243         void Split_Lazy_HP_cmpmix_stat();
1244
1245         void Split_Lazy_DHP_cmp();
1246         void Split_Lazy_DHP_less();
1247         void Split_Lazy_DHP_cmpmix();
1248         void Split_Lazy_DHP_cmpmix_stat();
1249
1250         void Split_Lazy_RCU_GPI_cmp();
1251         void Split_Lazy_RCU_GPI_less();
1252         void Split_Lazy_RCU_GPI_cmpmix();
1253         void Split_Lazy_RCU_GPI_cmpmix_stat();
1254
1255         void Split_Lazy_RCU_GPB_cmp();
1256         void Split_Lazy_RCU_GPB_less();
1257         void Split_Lazy_RCU_GPB_cmpmix();
1258         void Split_Lazy_RCU_GPB_cmpmix_stat();
1259
1260         void Split_Lazy_RCU_GPT_cmp();
1261         void Split_Lazy_RCU_GPT_less();
1262         void Split_Lazy_RCU_GPT_cmpmix();
1263         void Split_Lazy_RCU_GPT_cmpmix_stat();
1264
1265         void Split_Lazy_RCU_SHB_cmp();
1266         void Split_Lazy_RCU_SHB_less();
1267         void Split_Lazy_RCU_SHB_cmpmix();
1268         void Split_Lazy_RCU_SHB_cmpmix_stat();
1269
1270         void Split_Lazy_RCU_SHT_cmp();
1271         void Split_Lazy_RCU_SHT_less();
1272         void Split_Lazy_RCU_SHT_cmpmix();
1273         void Split_Lazy_RCU_SHT_cmpmix_stat();
1274
1275         void Split_Lazy_nogc_cmp();
1276         void Split_Lazy_nogc_less();
1277         void Split_Lazy_nogc_cmpmix();
1278         void Split_Lazy_nogc_cmpmix_stat();
1279
1280         CPPUNIT_TEST_SUITE(HashSetHdrTest)
1281             CPPUNIT_TEST(Michael_HP_cmp)
1282             CPPUNIT_TEST(Michael_HP_less)
1283             CPPUNIT_TEST(Michael_HP_cmpmix)
1284
1285             CPPUNIT_TEST(Michael_DHP_cmp)
1286             CPPUNIT_TEST(Michael_DHP_less)
1287             CPPUNIT_TEST(Michael_DHP_cmpmix)
1288
1289             CPPUNIT_TEST(Michael_RCU_GPI_cmp)
1290             CPPUNIT_TEST(Michael_RCU_GPI_less)
1291             CPPUNIT_TEST(Michael_RCU_GPI_cmpmix)
1292
1293             CPPUNIT_TEST(Michael_RCU_GPB_cmp)
1294             CPPUNIT_TEST(Michael_RCU_GPB_less)
1295             CPPUNIT_TEST(Michael_RCU_GPB_cmpmix)
1296
1297             CPPUNIT_TEST(Michael_RCU_GPT_cmp)
1298             CPPUNIT_TEST(Michael_RCU_GPT_less)
1299             CPPUNIT_TEST(Michael_RCU_GPT_cmpmix)
1300
1301             CPPUNIT_TEST(Michael_RCU_SHB_cmp)
1302             CPPUNIT_TEST(Michael_RCU_SHB_less)
1303             CPPUNIT_TEST(Michael_RCU_SHB_cmpmix)
1304
1305             CPPUNIT_TEST(Michael_RCU_SHT_cmp)
1306             CPPUNIT_TEST(Michael_RCU_SHT_less)
1307             CPPUNIT_TEST(Michael_RCU_SHT_cmpmix)
1308
1309             CPPUNIT_TEST(Michael_nogc_cmp)
1310             CPPUNIT_TEST(Michael_nogc_less)
1311             CPPUNIT_TEST(Michael_nogc_cmpmix)
1312
1313             CPPUNIT_TEST(Lazy_HP_cmp)
1314             CPPUNIT_TEST(Lazy_HP_less)
1315             CPPUNIT_TEST(Lazy_HP_cmpmix)
1316
1317             CPPUNIT_TEST(Lazy_DHP_cmp)
1318             CPPUNIT_TEST(Lazy_DHP_less)
1319             CPPUNIT_TEST(Lazy_DHP_cmpmix)
1320
1321             CPPUNIT_TEST(Lazy_RCU_GPI_cmp)
1322             CPPUNIT_TEST(Lazy_RCU_GPI_less)
1323             CPPUNIT_TEST(Lazy_RCU_GPI_cmpmix)
1324
1325             CPPUNIT_TEST(Lazy_RCU_GPB_cmp)
1326             CPPUNIT_TEST(Lazy_RCU_GPB_less)
1327             CPPUNIT_TEST(Lazy_RCU_GPB_cmpmix)
1328
1329             CPPUNIT_TEST(Lazy_RCU_GPT_cmp)
1330             CPPUNIT_TEST(Lazy_RCU_GPT_less)
1331             CPPUNIT_TEST(Lazy_RCU_GPT_cmpmix)
1332
1333             CPPUNIT_TEST(Lazy_RCU_SHB_cmp)
1334             CPPUNIT_TEST(Lazy_RCU_SHB_less)
1335             CPPUNIT_TEST(Lazy_RCU_SHB_cmpmix)
1336
1337             CPPUNIT_TEST(Lazy_RCU_SHT_cmp)
1338             CPPUNIT_TEST(Lazy_RCU_SHT_less)
1339             CPPUNIT_TEST(Lazy_RCU_SHT_cmpmix)
1340
1341             CPPUNIT_TEST(Lazy_nogc_cmp)
1342             CPPUNIT_TEST(Lazy_nogc_less)
1343             CPPUNIT_TEST(Lazy_nogc_equal)
1344             CPPUNIT_TEST(Lazy_nogc_cmpmix)
1345
1346             CPPUNIT_TEST(Split_HP_cmp)
1347             CPPUNIT_TEST(Split_HP_less)
1348             CPPUNIT_TEST(Split_HP_cmpmix)
1349             CPPUNIT_TEST( Split_HP_cmpmix_stat )
1350
1351             CPPUNIT_TEST(Split_DHP_cmp)
1352             CPPUNIT_TEST(Split_DHP_less)
1353             CPPUNIT_TEST(Split_DHP_cmpmix)
1354             CPPUNIT_TEST( Split_DHP_cmpmix_stat )
1355
1356             CPPUNIT_TEST(Split_RCU_GPI_cmp)
1357             CPPUNIT_TEST(Split_RCU_GPI_less)
1358             CPPUNIT_TEST(Split_RCU_GPI_cmpmix)
1359             CPPUNIT_TEST( Split_RCU_GPI_cmpmix_stat )
1360
1361             CPPUNIT_TEST(Split_RCU_GPB_cmp)
1362             CPPUNIT_TEST(Split_RCU_GPB_less)
1363             CPPUNIT_TEST(Split_RCU_GPB_cmpmix)
1364             CPPUNIT_TEST( Split_RCU_GPB_cmpmix_stat )
1365
1366             CPPUNIT_TEST(Split_RCU_GPT_cmp)
1367             CPPUNIT_TEST(Split_RCU_GPT_less)
1368             CPPUNIT_TEST(Split_RCU_GPT_cmpmix)
1369             CPPUNIT_TEST( Split_RCU_GPT_cmpmix_stat )
1370
1371             CPPUNIT_TEST(Split_RCU_SHB_cmp)
1372             CPPUNIT_TEST(Split_RCU_SHB_less)
1373             CPPUNIT_TEST(Split_RCU_SHB_cmpmix)
1374             CPPUNIT_TEST( Split_RCU_SHB_cmpmix_stat )
1375
1376             CPPUNIT_TEST(Split_RCU_SHT_cmp)
1377             CPPUNIT_TEST(Split_RCU_SHT_less)
1378             CPPUNIT_TEST(Split_RCU_SHT_cmpmix)
1379             CPPUNIT_TEST( Split_RCU_SHT_cmpmix_stat )
1380
1381             CPPUNIT_TEST(Split_nogc_cmp)
1382             CPPUNIT_TEST(Split_nogc_less)
1383             CPPUNIT_TEST(Split_nogc_cmpmix)
1384             CPPUNIT_TEST( Split_nogc_cmpmix_stat )
1385
1386             CPPUNIT_TEST(Split_Lazy_HP_cmp)
1387             CPPUNIT_TEST(Split_Lazy_HP_less)
1388             CPPUNIT_TEST(Split_Lazy_HP_cmpmix)
1389             CPPUNIT_TEST( Split_Lazy_HP_cmpmix_stat )
1390
1391             CPPUNIT_TEST(Split_Lazy_DHP_cmp)
1392             CPPUNIT_TEST(Split_Lazy_DHP_less)
1393             CPPUNIT_TEST(Split_Lazy_DHP_cmpmix)
1394             CPPUNIT_TEST( Split_Lazy_DHP_cmpmix_stat )
1395
1396             CPPUNIT_TEST(Split_Lazy_RCU_GPI_cmp)
1397             CPPUNIT_TEST(Split_Lazy_RCU_GPI_less)
1398             CPPUNIT_TEST(Split_Lazy_RCU_GPI_cmpmix)
1399             CPPUNIT_TEST( Split_Lazy_RCU_GPI_cmpmix_stat )
1400
1401             CPPUNIT_TEST(Split_Lazy_RCU_GPB_cmp)
1402             CPPUNIT_TEST(Split_Lazy_RCU_GPB_less)
1403             CPPUNIT_TEST(Split_Lazy_RCU_GPB_cmpmix)
1404             CPPUNIT_TEST( Split_Lazy_RCU_GPB_cmpmix_stat )
1405
1406             CPPUNIT_TEST(Split_Lazy_RCU_GPT_cmp)
1407             CPPUNIT_TEST(Split_Lazy_RCU_GPT_less)
1408             CPPUNIT_TEST(Split_Lazy_RCU_GPT_cmpmix)
1409             CPPUNIT_TEST( Split_Lazy_RCU_GPT_cmpmix_stat )
1410
1411             CPPUNIT_TEST(Split_Lazy_RCU_SHB_cmp)
1412             CPPUNIT_TEST(Split_Lazy_RCU_SHB_less)
1413             CPPUNIT_TEST(Split_Lazy_RCU_SHB_cmpmix)
1414             CPPUNIT_TEST( Split_Lazy_RCU_SHB_cmpmix_stat )
1415
1416             CPPUNIT_TEST(Split_Lazy_RCU_SHT_cmp)
1417             CPPUNIT_TEST(Split_Lazy_RCU_SHT_less)
1418             CPPUNIT_TEST(Split_Lazy_RCU_SHT_cmpmix)
1419             CPPUNIT_TEST( Split_Lazy_RCU_SHT_cmpmix_stat )
1420
1421             CPPUNIT_TEST(Split_Lazy_nogc_cmp)
1422             CPPUNIT_TEST(Split_Lazy_nogc_less)
1423             CPPUNIT_TEST(Split_Lazy_nogc_cmpmix)
1424             CPPUNIT_TEST( Split_Lazy_nogc_cmpmix_stat )
1425
1426         CPPUNIT_TEST_SUITE_END()
1427
1428     };
1429
1430 } // namespace set
1431
1432 #endif // CDSTEST_HDR_SET_H