tests/test-hdr/tree/hdr_ellenbintree_set.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSHDRTEST_ELLENBINTREE_SET_H
   4 #define CDSHDRTEST_ELLENBINTREE_SET_H
   5
   6 #include "cppunit/cppunit_proxy.h"
   7 #include "size_check.h"
   8 #include <functional>   // ref
   9 #include <algorithm>
  10
  11 namespace tree {
  12     using misc::check_size;
  13
  14     class EllenBinTreeSetHdrTest: public CppUnitMini::TestCase
  15     {
  16     public:
  17         typedef int     key_type;
  18
  19         struct stat_data {
  20             size_t  nInsertFuncCall;
  21             size_t  nEnsureExistFuncCall;
  22             size_t  nEnsureNewFuncCall;
  23             size_t  nEraseFuncCall;
  24             size_t  nFindFuncCall;
  25             size_t  nFindConstFuncCall;
  26
  27             stat_data()
  28                 : nInsertFuncCall(0)
  29                 , nEnsureExistFuncCall(0)
  30                 , nEnsureNewFuncCall(0)
  31                 , nEraseFuncCall(0)
  32                 , nFindFuncCall(0)
  33                 , nFindConstFuncCall(0)
  34             {}
  35         };
  36
  37         struct value_type {
  38             key_type    nKey;
  39             int         nVal;
  40
  41             stat_data   stat;
  42
  43             value_type()
  44             {}
  45
  46             value_type( int key )
  47                 : nKey( key )
  48                 , nVal( key * 10 )
  49             {}
  50
  51             value_type( int key, int v )
  52                 : nKey( key )
  53                 , nVal( v )
  54             {}
  55
  56             value_type( std::pair<int,int> const& p )
  57                 : nKey( p.first )
  58                 , nVal( p.second )
  59             {}
  60         };
  61
  62         struct key_extractor {
  63             void operator()( key_type& dest, value_type const& src ) const
  64             {
  65                 dest = src.nKey;
  66             }
  67         };
  68
  69         struct less {
  70             bool operator()( int k1, int k2 ) const
  71             {
  72                 return k1 < k2;
  73             }
  74             bool operator()( value_type const& v1, value_type const& v2 ) const
  75             {
  76                 return v1.nKey < v2.nKey;
  77             }
  78             bool operator()( value_type const& v, int k ) const
  79             {
  80                 return v.nKey < k;
  81             }
  82             bool operator()( int k, value_type const& v ) const
  83             {
  84                 return k < v.nKey;
  85             }
  86             bool operator()( std::pair<int,int> const& p, value_type& v ) const
  87             {
  88                 return p.first < v.nKey;
  89             }
  90             bool operator()( value_type& v, std::pair<int,int> const& p ) const
  91             {
  92                 return v.nKey < p.first;
  93             }
  94             bool operator()( std::pair<int,int> const& p, int v ) const
  95             {
  96                 return p.first < v;
  97             }
  98             bool operator()( int v, std::pair<int,int> const& p ) const
  99             {
 100                 return v < p.first;
 101             }
 102         };
 103
 104         struct compare {
 105             int cmp( int k1, int k2 ) const
 106             {
 107                 return k1 < k2 ? -1 : (k1 > k2 ? 1 : 0);
 108             }
 109             int operator()( int k1, int k2 ) const
 110             {
 111                 return cmp( k1, k2 );
 112             }
 113             int operator()( value_type const& v1, value_type const& v2 ) const
 114             {
 115                 return cmp( v1.nKey, v2.nKey );
 116             }
 117             int operator()( value_type const& v, int k ) const
 118             {
 119                 return cmp( v.nKey, k );
 120             }
 121             int operator()( int k, value_type const& v ) const
 122             {
 123                 return cmp( k, v.nKey );
 124             }
 125             int operator()( std::pair<int,int> const& p, value_type& v ) const
 126             {
 127                 return cmp( p.first, v.nKey );
 128             }
 129             int operator()( value_type& v, std::pair<int,int> const& p ) const
 130             {
 131                 return cmp( v.nKey, p.first );
 132             }
 133             int operator()( std::pair<int,int> const& p, int v ) const
 134             {
 135                 return cmp( p.first, v );
 136             }
 137             int operator()( int v, std::pair<int,int> const& p ) const
 138             {
 139                 return cmp( v, p.first );
 140             }
 141         };
 142
 143         struct wrapped_int {
 144             int  nKey;
 145
 146             wrapped_int( int n )
 147                 : nKey(n)
 148             {}
 149         };
 150
 151         struct wrapped_less
 152         {
 153             bool operator()( wrapped_int const& w, int n ) const
 154             {
 155                 return w.nKey < n;
 156             }
 157             bool operator()( int n, wrapped_int const& w ) const
 158             {
 159                 return n < w.nKey;
 160             }
 161             template <typename T>
 162             bool operator()( wrapped_int const& w, T const& v ) const
 163             {
 164                 return w.nKey < v.nKey;
 165             }
 166             template <typename T>
 167             bool operator()( T const& v, wrapped_int const& w ) const
 168             {
 169                 return v.nKey < w.nKey;
 170             }
 171         };
 172
 173     protected:
 174         static const size_t c_nItemCount = 10000;
 175
 176         class data_array
 177         {
 178             int *     pFirst;
 179             int *     pLast;
 180
 181         public:
 182             data_array()
 183                 : pFirst( new int[c_nItemCount] )
 184                 , pLast( pFirst + c_nItemCount )
 185             {
 186                 int i = 0;
 187                 for ( int * p = pFirst; p != pLast; ++p, ++i )
 188                     *p = i;
 189
 190                 std::random_shuffle( pFirst, pLast );
 191             }
 192
 193             ~data_array()
 194             {
 195                 delete [] pFirst;
 196             }
 197
 198             int operator[]( size_t i ) const
 199             {
 200                 assert( i < size_t(pLast - pFirst) );
 201                 return pFirst[i];
 202             }
 203         };
 204
 205         struct find_functor
 206         {
 207             template <typename T>
 208             void operator()( value_type& i, T& val )
 209             {
 210                 ++i.stat.nFindFuncCall;
 211             }
 212             template <typename T>
 213             void operator()( value_type& i, T const& val )
 214             {
 215                 ++i.stat.nFindConstFuncCall;
 216             }
 217         };
 218
 219         template <typename Item>
 220         struct copy_found
 221         {
 222             Item    m_found;
 223
 224             template <typename T>
 225             void operator()( Item& i, T& /*val*/ )
 226             {
 227                 m_found = i;
 228             }
 229
 230             void operator()( Item const& i )
 231             {
 232                 m_found = i;
 233             }
 234         };
 235
 236         struct insert_functor
 237         {
 238             template <typename Item>
 239             void operator()(Item& i )
 240             {
 241                 i.nVal = i.nKey * 100;
 242                 ++i.stat.nInsertFuncCall;
 243             }
 244         };
 245
 246         template <typename Q>
 247         static void ensure_func( bool bNew, value_type& i, Q& /*val*/ )
 248         {
 249             if ( bNew )
 250                 ++i.stat.nEnsureNewFuncCall;
 251             else
 252                 ++i.stat.nEnsureExistFuncCall;
 253         }
 254
 255         struct ensure_functor
 256         {
 257             template <typename Q>
 258             void operator()( bool bNew, value_type& i, Q& val )
 259             {
 260                 ensure_func( bNew, i, val );
 261             }
 262         };
 263
 264         struct extract_functor
 265         {
 266             int nKey;
 267
 268             template <typename Q>
 269             void operator()( Q&, value_type& v )
 270             {
 271                 nKey = v.nKey;
 272             }
 273         };
 274
 275
 276     protected:
 277         template <class Set>
 278         void test_with( Set& s)
 279         {
 280             value_type itm;
 281             int key;
 282
 283             // insert/find test
 284             CPPUNIT_ASSERT( !s.find( 10 ) );
 285             CPPUNIT_ASSERT( s.insert( 10 ));
 286             CPPUNIT_ASSERT( !s.empty() );
 287             CPPUNIT_ASSERT( check_size( s, 1 ));
 288             CPPUNIT_ASSERT( s.find( 10 ) );
 289
 290             CPPUNIT_ASSERT( !s.insert( 10 ));
 291             CPPUNIT_ASSERT( !s.empty() );
 292             CPPUNIT_ASSERT( check_size( s, 1 ));
 293
 294             CPPUNIT_ASSERT( !s.find_with( 20, less() ) );
 295             CPPUNIT_ASSERT( s.insert( std::make_pair(20, 25) ));
 296             CPPUNIT_ASSERT( !s.empty() );
 297             CPPUNIT_ASSERT( check_size( s, 2 ));
 298             CPPUNIT_ASSERT( s.find_with( 10, less() ) );
 299             CPPUNIT_ASSERT( s.find( key = 20 ) );
 300             CPPUNIT_ASSERT( s.find_with( key, less(), find_functor() ) );
 301             {
 302                 copy_found<value_type> f;
 303                 f.m_found.nKey = 0;
 304                 key = 20;
 305                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 306                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 307                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 308                 CPPUNIT_ASSERT( f.m_found.stat.nFindFuncCall == 1 );
 309                 CPPUNIT_ASSERT( f.m_found.stat.nFindConstFuncCall == 0 );
 310             }
 311             CPPUNIT_ASSERT( s.find( key, find_functor() ) );
 312             {
 313                 copy_found<value_type> f;
 314                 f.m_found.nKey = 0;
 315                 key = 20;
 316                 CPPUNIT_ASSERT( s.find_with( key, less(), std::ref( f ) ) );
 317                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 318                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 319                 CPPUNIT_ASSERT( f.m_found.stat.nFindFuncCall == 2 );
 320                 CPPUNIT_ASSERT( f.m_found.stat.nFindConstFuncCall == 0 );
 321             }
 322             CPPUNIT_ASSERT( s.find( 20, find_functor() ) );
 323             {
 324                 copy_found<value_type> f;
 325                 f.m_found.nKey = 0;
 326                 CPPUNIT_ASSERT( s.find_with( 20, less(), std::ref( f ) ) );
 327                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 328                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 329                 CPPUNIT_ASSERT( f.m_found.stat.nFindFuncCall == 2 );
 330                 CPPUNIT_ASSERT( f.m_found.stat.nFindConstFuncCall == 1 );
 331             }
 332
 333             CPPUNIT_ASSERT( !s.empty() );
 334             CPPUNIT_ASSERT( check_size( s, 2 ));
 335
 336             CPPUNIT_ASSERT( !s.find( 25 ) );
 337             CPPUNIT_ASSERT( s.insert( std::make_pair(25, -1), insert_functor() ));
 338             CPPUNIT_ASSERT( !s.empty() );
 339             CPPUNIT_ASSERT( check_size( s, 3 ));
 340             {
 341                 copy_found<value_type> f;
 342                 f.m_found.nKey = 0;
 343                 key = 25;
 344                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 345                 CPPUNIT_ASSERT( f.m_found.nKey == 25 );
 346                 CPPUNIT_ASSERT( f.m_found.nVal == 2500 );
 347                 CPPUNIT_ASSERT( f.m_found.stat.nInsertFuncCall == 1 );
 348             }
 349
 350             // ensure test
 351             key = 10;
 352             {
 353                 copy_found<value_type> f;
 354                 f.m_found.nKey = 0;
 355                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 356                 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
 357                 CPPUNIT_ASSERT( f.m_found.nVal == 100 );
 358                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureExistFuncCall == 0 );
 359                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureNewFuncCall == 0 );
 360             }
 361             std::pair<bool, bool> ensureResult = s.ensure( key, ensure_functor() );
 362             CPPUNIT_ASSERT( ensureResult.first && !ensureResult.second );
 363             CPPUNIT_ASSERT( !s.empty() );
 364             CPPUNIT_ASSERT( check_size( s, 3 ));
 365             {
 366                 copy_found<value_type> f;
 367                 f.m_found.nKey = 0;
 368                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 369                 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
 370                 CPPUNIT_ASSERT( f.m_found.nVal == 100 );
 371                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureExistFuncCall == 1 );
 372                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureNewFuncCall == 0 );
 373             }
 374
 375             ensureResult = s.ensure( std::make_pair(13, 1300), ensure_functor() );
 376             CPPUNIT_ASSERT( ensureResult.first && ensureResult.second );
 377             CPPUNIT_ASSERT( !s.empty() );
 378             CPPUNIT_ASSERT( check_size( s, 4 ));
 379             {
 380                 copy_found<value_type> f;
 381                 f.m_found.nKey = 0;
 382                 key = 13;
 383                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 384                 CPPUNIT_ASSERT( f.m_found.nKey == 13 );
 385                 CPPUNIT_ASSERT( f.m_found.nVal == 1300 );
 386                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureExistFuncCall == 0 );
 387                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureNewFuncCall == 1 );
 388             }
 389
 390             // erase test
 391             CPPUNIT_ASSERT( s.erase(13) );
 392             CPPUNIT_ASSERT( !s.find( 13 ));
 393             CPPUNIT_ASSERT( !s.empty() );
 394             CPPUNIT_ASSERT( check_size( s, 3 ));
 395             CPPUNIT_ASSERT( !s.erase(13) );
 396             CPPUNIT_ASSERT( !s.empty() );
 397             CPPUNIT_ASSERT( check_size( s, 3 ));
 398
 399             CPPUNIT_ASSERT( s.find( 10 ));
 400             CPPUNIT_ASSERT( s.erase_with( 10, less() ));
 401             CPPUNIT_ASSERT( !s.find( 10 ));
 402             CPPUNIT_ASSERT( !s.empty() );
 403             CPPUNIT_ASSERT( check_size( s, 2 ));
 404             CPPUNIT_ASSERT( !s.erase_with(10, less()) );
 405             CPPUNIT_ASSERT( !s.empty() );
 406             CPPUNIT_ASSERT( check_size( s, 2 ));
 407
 408             CPPUNIT_ASSERT( s.find(20) );
 409             {
 410                 copy_found<value_type> f;
 411                 f.m_found.nKey = 0;
 412                 CPPUNIT_ASSERT( s.erase( 20, std::ref( f ) ) );
 413                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 414                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 415
 416                 CPPUNIT_ASSERT( s.insert(235))
 417                 CPPUNIT_ASSERT( s.erase_with( 235, less(), std::ref( f ) ) );
 418                 CPPUNIT_ASSERT( f.m_found.nKey == 235 );
 419                 CPPUNIT_ASSERT( f.m_found.nVal == 2350 );
 420             }
 421             CPPUNIT_ASSERT( !s.find( 20 ));
 422             CPPUNIT_ASSERT( !s.empty() );
 423             CPPUNIT_ASSERT( check_size( s, 1 ));
 424
 425             s.clear();
 426             CPPUNIT_ASSERT( s.empty() );
 427             CPPUNIT_ASSERT( check_size( s, 0 ));
 428
 429             // emplace test
 430             CPPUNIT_ASSERT( s.emplace( 151 )) ;  // key = 151,  val = 1510
 431             CPPUNIT_ASSERT( s.emplace( 174, 471 )) ;    // key = 174, val = 471
 432             CPPUNIT_ASSERT( s.emplace( std::make_pair( 190, 91 ) )) ; // key == 190, val = 91
 433             CPPUNIT_ASSERT( !s.empty() );
 434             CPPUNIT_ASSERT( check_size( s, 3 ));
 435
 436             CPPUNIT_ASSERT( s.find(151));
 437             CPPUNIT_ASSERT( s.find_with(174, less()));
 438             CPPUNIT_ASSERT( s.find(190));
 439
 440             {
 441                 copy_found<value_type> f;
 442                 f.m_found.nKey = 0;
 443                 key = 151;
 444                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 445                 CPPUNIT_ASSERT( f.m_found.nKey == 151 );
 446                 CPPUNIT_ASSERT( f.m_found.nVal == 1510 );
 447
 448                 key = 174;
 449                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 450                 CPPUNIT_ASSERT( f.m_found.nKey == 174 );
 451                 CPPUNIT_ASSERT( f.m_found.nVal == 471 );
 452
 453                 key = 190;
 454                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 455                 CPPUNIT_ASSERT( f.m_found.nKey == 190 );
 456                 CPPUNIT_ASSERT( f.m_found.nVal == 91 );
 457             }
 458
 459             s.clear();
 460             CPPUNIT_ASSERT( s.empty() );
 461             CPPUNIT_ASSERT( check_size( s, 0 ));
 462         }
 463
 464         template <typename Set>
 465         void fill_set( Set& s, data_array& a )
 466         {
 467             CPPUNIT_ASSERT( s.empty() );
 468             for ( size_t i = 0; i < c_nItemCount; ++i ) {
 469                 CPPUNIT_ASSERT( s.insert( a[i] ));
 470             }
 471             CPPUNIT_ASSERT( !s.empty() );
 472             CPPUNIT_ASSERT( check_size( s, c_nItemCount ));
 473
 474         }
 475
 476         template <class Set, class PrintStat>
 477         void test()
 478         {
 479             typedef Set set_type;
 480
 481             set_type s;
 482
 483             test_with( s );
 484
 485             s.clear();
 486             CPPUNIT_ASSERT( s.empty() );
 487             CPPUNIT_ASSERT( check_size( s, 0 ));
 488
 489             // extract min/max
 490             {
 491                 typename Set::guarded_ptr gp;
 492
 493                 data_array arr;
 494                 fill_set( s, arr );
 495
 496                 int i = 0;
 497                 while ( !s.empty() ) {
 498                     CPPUNIT_ASSERT( s.extract_min( gp ) );
 499                     CPPUNIT_ASSERT( gp->nKey == i );
 500                     ++i;
 501                 }
 502                 CPPUNIT_ASSERT( s.empty() );
 503                 CPPUNIT_ASSERT( check_size( s, 0 ));
 504
 505                 fill_set( s, arr );
 506                 i = (int) c_nItemCount - 1;
 507                 while ( !s.empty() ) {
 508                     CPPUNIT_ASSERT( s.extract_max( gp ) );
 509                     CPPUNIT_ASSERT( gp->nKey == i );
 510                     --i;
 511                 }
 512                 CPPUNIT_ASSERT( s.empty() );
 513                 CPPUNIT_ASSERT( check_size( s, 0 ));
 514
 515                 fill_set( s, arr );
 516                 for ( int i = 0; i < static_cast<int>( c_nItemCount ); ++i ) {
 517                     int nKey = arr[i];
 518                     CPPUNIT_ASSERT( s.get( gp, nKey ));
 519                     CPPUNIT_ASSERT( !gp.empty());
 520                     CPPUNIT_CHECK( gp->nKey == nKey );
 521
 522                     gp.release();
 523                     CPPUNIT_ASSERT( s.extract( gp, nKey ));
 524                     CPPUNIT_ASSERT( !gp.empty());
 525                     CPPUNIT_CHECK( gp->nKey == nKey );
 526
 527                     gp.release();
 528                     CPPUNIT_CHECK( !s.get( gp, nKey ));
 529                     CPPUNIT_CHECK( gp.empty());
 530                     CPPUNIT_CHECK( !s.extract( gp, nKey ));
 531                     CPPUNIT_CHECK( gp.empty());
 532                 }
 533                 CPPUNIT_ASSERT( s.empty() );
 534                 CPPUNIT_ASSERT( check_size( s, 0 ));
 535
 536                 fill_set( s, arr );
 537                 for ( int i = 0; i < static_cast<int>( c_nItemCount ); ++i ) {
 538                     int nKey = arr[i];
 539                     CPPUNIT_ASSERT( s.get_with( gp, wrapped_int(nKey), wrapped_less() ));
 540                     CPPUNIT_ASSERT( !gp.empty());
 541                     CPPUNIT_CHECK( gp->nKey == nKey );
 542
 543                     gp.release();
 544                     CPPUNIT_ASSERT( s.extract_with( gp, wrapped_int(nKey), wrapped_less() ));
 545                     CPPUNIT_ASSERT( !gp.empty());
 546                     CPPUNIT_CHECK( gp->nKey == nKey );
 547
 548                     gp.release();
 549                     CPPUNIT_CHECK( !s.get_with( gp, wrapped_int(nKey), wrapped_less() ));
 550                     CPPUNIT_CHECK( gp.empty());
 551                     CPPUNIT_CHECK( !s.extract_with( gp, wrapped_int(nKey), wrapped_less() ));
 552                     CPPUNIT_CHECK( gp.empty());
 553                 }
 554                 CPPUNIT_ASSERT( s.empty() );
 555                 CPPUNIT_ASSERT( check_size( s, 0 ));
 556             }
 557
 558             PrintStat()( s );
 559         }
 560
 561         template <class Set, class PrintStat>
 562         void test_rcu()
 563         {
 564             typedef Set set_type;
 565
 566             set_type s;
 567
 568             test_with( s );
 569
 570             s.clear();
 571             CPPUNIT_ASSERT( s.empty() );
 572             CPPUNIT_ASSERT( check_size( s, 0 ));
 573
 574             // extract min/max
 575             {
 576                 typename set_type::exempt_ptr ep;
 577                 data_array arr;
 578                 fill_set( s, arr );
 579
 580                 int i = 0;
 581                 value_type v;
 582                 while ( !s.empty() ) {
 583                     CPPUNIT_ASSERT( s.extract_min( ep ) );
 584                     CPPUNIT_ASSERT( !ep.empty());
 585                     CPPUNIT_CHECK( ep->nKey == i );
 586                     ++i;
 587                     ep.release();
 588                 }
 589                 CPPUNIT_ASSERT( s.empty() );
 590                 CPPUNIT_ASSERT( check_size( s, 0 ));
 591
 592                 fill_set( s, arr );
 593                 i = (int) c_nItemCount - 1;
 594                 while ( !s.empty() ) {
 595                     CPPUNIT_ASSERT( s.extract_max( ep ) );
 596                     CPPUNIT_ASSERT( !ep.empty());
 597                     CPPUNIT_CHECK( ep->nKey == i );
 598                     --i;
 599                     ep.release();
 600                 }
 601                 CPPUNIT_ASSERT( s.empty() );
 602                 CPPUNIT_ASSERT( check_size( s, 0 ));
 603
 604                 fill_set( s, arr );
 605                 for ( size_t i = 0; i < c_nItemCount; ++i ) {
 606                     int nKey = arr[i];
 607                     {
 608                         typename set_type::rcu_lock l;
 609                         value_type * p = s.get( nKey );
 610                         CPPUNIT_ASSERT( p != nullptr );
 611                         CPPUNIT_CHECK( p->nKey == nKey );
 612                     }
 613                     CPPUNIT_ASSERT( s.extract( ep, nKey ));
 614                     CPPUNIT_ASSERT( !ep.empty());
 615                     CPPUNIT_CHECK( ep->nKey == nKey);
 616                     ep.release();
 617
 618                     {
 619                         typename set_type::rcu_lock l;
 620                         CPPUNIT_CHECK( s.get( nKey ) == nullptr );
 621                     }
 622                     CPPUNIT_CHECK( !s.extract( ep, nKey ));
 623                 }
 624                 CPPUNIT_ASSERT( s.empty() );
 625                 CPPUNIT_ASSERT( check_size( s, 0 ));
 626
 627                 fill_set( s, arr );
 628                 for ( size_t i = 0; i < c_nItemCount; ++i ) {
 629                     int nKey = arr[i];
 630                     {
 631                         typename set_type::rcu_lock l;
 632                         value_type * p = s.get_with( wrapped_int(nKey), wrapped_less() );
 633                         CPPUNIT_ASSERT( p != nullptr );
 634                         CPPUNIT_CHECK( p->nKey == nKey );
 635                     }
 636                     CPPUNIT_ASSERT( s.extract_with( ep, wrapped_int(nKey), wrapped_less() ));
 637                     CPPUNIT_ASSERT( !ep.empty());
 638                     CPPUNIT_CHECK( ep->nKey == nKey);
 639                     ep.release();
 640
 641                     {
 642                         typename set_type::rcu_lock l;
 643                         CPPUNIT_CHECK( s.get_with( wrapped_int( nKey ), wrapped_less() ) == nullptr );
 644                     }
 645                     CPPUNIT_CHECK( !s.extract_with( ep, wrapped_int(nKey), wrapped_less() ));
 646                 }
 647                 CPPUNIT_ASSERT( s.empty() );
 648                 CPPUNIT_ASSERT( check_size( s, 0 ));
 649
 650             }
 651
 652             PrintStat()( s );
 653         }
 654
 655         void EllenBinTree_hp_less();
 656         void EllenBinTree_hp_cmp();
 657         void EllenBinTree_hp_cmpless();
 658         void EllenBinTree_hp_less_ic();
 659         void EllenBinTree_hp_cmp_ic();
 660         void EllenBinTree_hp_less_stat();
 661         void EllenBinTree_hp_cmp_ic_stat();
 662         void EllenBinTree_hp_less_pool();
 663         void EllenBinTree_hp_less_pool_ic_stat();
 664
 665         void EllenBinTree_ptb_less();
 666         void EllenBinTree_ptb_cmp();
 667         void EllenBinTree_ptb_cmpless();
 668         void EllenBinTree_ptb_less_ic();
 669         void EllenBinTree_ptb_cmp_ic();
 670         void EllenBinTree_ptb_less_stat();
 671         void EllenBinTree_ptb_cmp_ic_stat();
 672         void EllenBinTree_ptb_less_pool();
 673         void EllenBinTree_ptb_less_pool_ic_stat();
 674
 675         void EllenBinTree_rcu_gpi_less();
 676         void EllenBinTree_rcu_gpi_cmp();
 677         void EllenBinTree_rcu_gpi_cmpless();
 678         void EllenBinTree_rcu_gpi_less_ic();
 679         void EllenBinTree_rcu_gpi_cmp_ic();
 680         void EllenBinTree_rcu_gpi_less_stat();
 681         void EllenBinTree_rcu_gpi_cmp_ic_stat();
 682         void EllenBinTree_rcu_gpi_less_pool();
 683         void EllenBinTree_rcu_gpi_less_pool_ic_stat();
 684
 685         void EllenBinTree_rcu_gpb_less();
 686         void EllenBinTree_rcu_gpb_cmp();
 687         void EllenBinTree_rcu_gpb_cmpless();
 688         void EllenBinTree_rcu_gpb_less_ic();
 689         void EllenBinTree_rcu_gpb_cmp_ic();
 690         void EllenBinTree_rcu_gpb_less_stat();
 691         void EllenBinTree_rcu_gpb_cmp_ic_stat();
 692         void EllenBinTree_rcu_gpb_less_pool();
 693         void EllenBinTree_rcu_gpb_less_pool_ic_stat();
 694
 695         void EllenBinTree_rcu_gpt_less();
 696         void EllenBinTree_rcu_gpt_cmp();
 697         void EllenBinTree_rcu_gpt_cmpless();
 698         void EllenBinTree_rcu_gpt_less_ic();
 699         void EllenBinTree_rcu_gpt_cmp_ic();
 700         void EllenBinTree_rcu_gpt_less_stat();
 701         void EllenBinTree_rcu_gpt_cmp_ic_stat();
 702         void EllenBinTree_rcu_gpt_less_pool();
 703         void EllenBinTree_rcu_gpt_less_pool_ic_stat();
 704
 705         void EllenBinTree_rcu_shb_less();
 706         void EllenBinTree_rcu_shb_cmp();
 707         void EllenBinTree_rcu_shb_cmpless();
 708         void EllenBinTree_rcu_shb_less_ic();
 709         void EllenBinTree_rcu_shb_cmp_ic();
 710         void EllenBinTree_rcu_shb_less_stat();
 711         void EllenBinTree_rcu_shb_cmp_ic_stat();
 712         void EllenBinTree_rcu_shb_less_pool();
 713         void EllenBinTree_rcu_shb_less_pool_ic_stat();
 714
 715         void EllenBinTree_rcu_sht_less();
 716         void EllenBinTree_rcu_sht_cmp();
 717         void EllenBinTree_rcu_sht_cmpless();
 718         void EllenBinTree_rcu_sht_less_ic();
 719         void EllenBinTree_rcu_sht_cmp_ic();
 720         void EllenBinTree_rcu_sht_less_stat();
 721         void EllenBinTree_rcu_sht_cmp_ic_stat();
 722         void EllenBinTree_rcu_sht_less_pool();
 723         void EllenBinTree_rcu_sht_less_pool_ic_stat();
 724
 725         CPPUNIT_TEST_SUITE(EllenBinTreeSetHdrTest)
 726             CPPUNIT_TEST(EllenBinTree_hp_less)
 727             CPPUNIT_TEST(EllenBinTree_hp_cmp)
 728             CPPUNIT_TEST(EllenBinTree_hp_less_stat)
 729             CPPUNIT_TEST(EllenBinTree_hp_cmpless)
 730             CPPUNIT_TEST(EllenBinTree_hp_less_ic)
 731             CPPUNIT_TEST(EllenBinTree_hp_cmp_ic)
 732             CPPUNIT_TEST(EllenBinTree_hp_cmp_ic_stat)
 733             CPPUNIT_TEST(EllenBinTree_hp_less_pool)
 734             CPPUNIT_TEST(EllenBinTree_hp_less_pool_ic_stat)
 735
 736             CPPUNIT_TEST(EllenBinTree_ptb_less)
 737             CPPUNIT_TEST(EllenBinTree_ptb_cmp)
 738             CPPUNIT_TEST(EllenBinTree_ptb_less_stat)
 739             CPPUNIT_TEST(EllenBinTree_ptb_cmpless)
 740             CPPUNIT_TEST(EllenBinTree_ptb_less_ic)
 741             CPPUNIT_TEST(EllenBinTree_ptb_cmp_ic)
 742             CPPUNIT_TEST(EllenBinTree_ptb_cmp_ic_stat)
 743             CPPUNIT_TEST(EllenBinTree_ptb_less_pool)
 744             CPPUNIT_TEST(EllenBinTree_ptb_less_pool_ic_stat)
 745
 746             CPPUNIT_TEST(EllenBinTree_rcu_gpi_less)
 747             CPPUNIT_TEST(EllenBinTree_rcu_gpi_cmp)
 748             CPPUNIT_TEST(EllenBinTree_rcu_gpi_less_stat)
 749             CPPUNIT_TEST(EllenBinTree_rcu_gpi_cmpless)
 750             CPPUNIT_TEST(EllenBinTree_rcu_gpi_less_ic)
 751             CPPUNIT_TEST(EllenBinTree_rcu_gpi_cmp_ic)
 752             CPPUNIT_TEST(EllenBinTree_rcu_gpi_cmp_ic_stat)
 753             CPPUNIT_TEST(EllenBinTree_rcu_gpi_less_pool)
 754             CPPUNIT_TEST(EllenBinTree_rcu_gpi_less_pool_ic_stat)
 755
 756             CPPUNIT_TEST(EllenBinTree_rcu_gpb_less)
 757             CPPUNIT_TEST(EllenBinTree_rcu_gpb_cmp)
 758             CPPUNIT_TEST(EllenBinTree_rcu_gpb_less_stat)
 759             CPPUNIT_TEST(EllenBinTree_rcu_gpb_cmpless)
 760             CPPUNIT_TEST(EllenBinTree_rcu_gpb_less_ic)
 761             CPPUNIT_TEST(EllenBinTree_rcu_gpb_cmp_ic)
 762             CPPUNIT_TEST(EllenBinTree_rcu_gpb_cmp_ic_stat)
 763             CPPUNIT_TEST(EllenBinTree_rcu_gpb_less_pool)
 764             CPPUNIT_TEST(EllenBinTree_rcu_gpb_less_pool_ic_stat)
 765
 766             CPPUNIT_TEST(EllenBinTree_rcu_gpt_less)
 767             CPPUNIT_TEST(EllenBinTree_rcu_gpt_cmp)
 768             CPPUNIT_TEST(EllenBinTree_rcu_gpt_less_stat)
 769             CPPUNIT_TEST(EllenBinTree_rcu_gpt_cmpless)
 770             CPPUNIT_TEST(EllenBinTree_rcu_gpt_less_ic)
 771             CPPUNIT_TEST(EllenBinTree_rcu_gpt_cmp_ic)
 772             CPPUNIT_TEST(EllenBinTree_rcu_gpt_cmp_ic_stat)
 773             CPPUNIT_TEST(EllenBinTree_rcu_gpt_less_pool)
 774             CPPUNIT_TEST(EllenBinTree_rcu_gpt_less_pool_ic_stat)
 775
 776             CPPUNIT_TEST(EllenBinTree_rcu_shb_less)
 777             CPPUNIT_TEST(EllenBinTree_rcu_shb_cmp)
 778             CPPUNIT_TEST(EllenBinTree_rcu_shb_less_stat)
 779             CPPUNIT_TEST(EllenBinTree_rcu_shb_cmpless)
 780             CPPUNIT_TEST(EllenBinTree_rcu_shb_less_ic)
 781             CPPUNIT_TEST(EllenBinTree_rcu_shb_cmp_ic)
 782             CPPUNIT_TEST(EllenBinTree_rcu_shb_cmp_ic_stat)
 783             CPPUNIT_TEST(EllenBinTree_rcu_shb_less_pool)
 784             CPPUNIT_TEST(EllenBinTree_rcu_shb_less_pool_ic_stat)
 785
 786             CPPUNIT_TEST(EllenBinTree_rcu_sht_less)
 787             CPPUNIT_TEST(EllenBinTree_rcu_sht_cmp)
 788             CPPUNIT_TEST(EllenBinTree_rcu_sht_less_stat)
 789             CPPUNIT_TEST(EllenBinTree_rcu_sht_cmpless)
 790             CPPUNIT_TEST(EllenBinTree_rcu_sht_less_ic)
 791             CPPUNIT_TEST(EllenBinTree_rcu_sht_cmp_ic)
 792             CPPUNIT_TEST(EllenBinTree_rcu_sht_cmp_ic_stat)
 793             CPPUNIT_TEST(EllenBinTree_rcu_sht_less_pool)
 794             CPPUNIT_TEST(EllenBinTree_rcu_sht_less_pool_ic_stat)
 795
 796         CPPUNIT_TEST_SUITE_END()
 797     };
 798 } // namespace tree
 799
 800 #endif // #ifndef CDSHDRTEST_ELLENBINTREE_SET_H