tests/test-hdr/tree/hdr_ellenbintree_set.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSTEST_HDR_ELLENBINTREE_SET_H
   4 #define CDSTEST_HDR_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                     gp = s.extract_min();
 499                     CPPUNIT_ASSERT( gp );
 500                     CPPUNIT_ASSERT( gp->nKey == i );
 501                     ++i;
 502                 }
 503                 CPPUNIT_ASSERT( s.empty() );
 504                 CPPUNIT_ASSERT( check_size( s, 0 ));
 505
 506                 fill_set( s, arr );
 507                 i = (int) c_nItemCount - 1;
 508                 while ( !s.empty() ) {
 509                     gp = s.extract_max();
 510                     CPPUNIT_ASSERT( gp );
 511                     CPPUNIT_ASSERT( gp->nKey == i );
 512                     --i;
 513                 }
 514                 CPPUNIT_ASSERT( s.empty() );
 515                 CPPUNIT_ASSERT( check_size( s, 0 ));
 516
 517                 fill_set( s, arr );
 518                 for ( int i = 0; i < static_cast<int>( c_nItemCount ); ++i ) {
 519                     int nKey = arr[i];
 520                     gp = s.get( nKey );
 521                     CPPUNIT_ASSERT( gp );
 522                     CPPUNIT_ASSERT( !gp.empty());
 523                     CPPUNIT_CHECK( gp->nKey == nKey );
 524
 525                     gp = s.extract( nKey );
 526                     CPPUNIT_ASSERT( gp );
 527                     CPPUNIT_ASSERT( !gp.empty());
 528                     CPPUNIT_CHECK( gp->nKey == nKey );
 529
 530                     gp = s.get( nKey );
 531                     CPPUNIT_CHECK( !gp );
 532                     CPPUNIT_CHECK( gp.empty());
 533                     CPPUNIT_CHECK( !s.extract( nKey ));
 534                     CPPUNIT_CHECK( gp.empty());
 535                 }
 536                 CPPUNIT_ASSERT( s.empty() );
 537                 CPPUNIT_ASSERT( check_size( s, 0 ));
 538
 539                 fill_set( s, arr );
 540                 for ( int i = 0; i < static_cast<int>( c_nItemCount ); ++i ) {
 541                     int nKey = arr[i];
 542                     gp = s.get_with( wrapped_int( nKey ), wrapped_less() );
 543                     CPPUNIT_ASSERT( gp );
 544                     CPPUNIT_ASSERT( !gp.empty());
 545                     CPPUNIT_CHECK( gp->nKey == nKey );
 546
 547                     gp = s.extract_with( wrapped_int( nKey ), wrapped_less() );
 548                     CPPUNIT_ASSERT( gp );
 549                     CPPUNIT_ASSERT( !gp.empty());
 550                     CPPUNIT_CHECK( gp->nKey == nKey );
 551
 552                     gp = s.get_with( wrapped_int( nKey ), wrapped_less() );
 553                     CPPUNIT_CHECK( !gp );
 554                     CPPUNIT_CHECK( gp.empty());
 555                     CPPUNIT_CHECK( !s.extract_with( wrapped_int(nKey), wrapped_less() ));
 556                     CPPUNIT_CHECK( gp.empty());
 557                 }
 558                 CPPUNIT_ASSERT( s.empty() );
 559                 CPPUNIT_ASSERT( check_size( s, 0 ));
 560             }
 561
 562             PrintStat()( s );
 563         }
 564
 565         template <class Set, class PrintStat>
 566         void test_rcu()
 567         {
 568             typedef Set set_type;
 569
 570             set_type s;
 571
 572             test_with( s );
 573
 574             s.clear();
 575             CPPUNIT_ASSERT( s.empty() );
 576             CPPUNIT_ASSERT( check_size( s, 0 ));
 577
 578             // extract min/max
 579             {
 580                 typename set_type::exempt_ptr ep;
 581                 data_array arr;
 582                 fill_set( s, arr );
 583
 584                 int i = 0;
 585                 value_type v;
 586                 while ( !s.empty() ) {
 587                     ep = s.extract_min();
 588                     CPPUNIT_ASSERT( ep );
 589                     CPPUNIT_ASSERT( !ep.empty());
 590                     CPPUNIT_CHECK( ep->nKey == i );
 591                     ++i;
 592                     //ep.release();
 593                 }
 594                 ep.release();
 595                 CPPUNIT_ASSERT( s.empty() );
 596                 CPPUNIT_ASSERT( check_size( s, 0 ));
 597
 598                 fill_set( s, arr );
 599                 i = (int) c_nItemCount - 1;
 600                 while ( !s.empty() ) {
 601                     ep = s.extract_max();
 602                     CPPUNIT_ASSERT( ep );
 603                     CPPUNIT_ASSERT( !ep.empty());
 604                     CPPUNIT_CHECK( ep->nKey == i );
 605                     --i;
 606                     //ep.release();
 607                 }
 608                 ep.release();
 609                 CPPUNIT_ASSERT( s.empty() );
 610                 CPPUNIT_ASSERT( check_size( s, 0 ));
 611
 612                 fill_set( s, arr );
 613                 for ( size_t i = 0; i < c_nItemCount; ++i ) {
 614                     int nKey = arr[i];
 615                     {
 616                         typename set_type::rcu_lock l;
 617                         value_type * p = s.get( nKey );
 618                         CPPUNIT_ASSERT( p != nullptr );
 619                         CPPUNIT_CHECK( p->nKey == nKey );
 620                     }
 621                     ep = s.extract( nKey );
 622                     CPPUNIT_ASSERT( !ep.empty());
 623                     CPPUNIT_CHECK( ep->nKey == nKey);
 624                     //ep.release();
 625
 626                     {
 627                         typename set_type::rcu_lock l;
 628                         CPPUNIT_CHECK( s.get( nKey ) == nullptr );
 629                     }
 630                     ep = s.extract( nKey );
 631                     CPPUNIT_CHECK( !ep );
 632                 }
 633                 CPPUNIT_ASSERT( s.empty() );
 634                 CPPUNIT_ASSERT( check_size( s, 0 ));
 635
 636                 fill_set( s, arr );
 637                 for ( size_t i = 0; i < c_nItemCount; ++i ) {
 638                     int nKey = arr[i];
 639                     {
 640                         typename set_type::rcu_lock l;
 641                         value_type * p = s.get_with( wrapped_int(nKey), wrapped_less() );
 642                         CPPUNIT_ASSERT( p != nullptr );
 643                         CPPUNIT_CHECK( p->nKey == nKey );
 644                     }
 645                     ep = s.extract_with( wrapped_int( nKey ), wrapped_less() );
 646                     CPPUNIT_ASSERT( ep );
 647                     CPPUNIT_ASSERT( !ep.empty());
 648                     CPPUNIT_CHECK( ep->nKey == nKey);
 649                     //ep.release();
 650
 651                     {
 652                         typename set_type::rcu_lock l;
 653                         CPPUNIT_CHECK( s.get_with( wrapped_int( nKey ), wrapped_less() ) == nullptr );
 654                     }
 655                     ep = s.extract_with( wrapped_int( nKey ), wrapped_less() );
 656                     CPPUNIT_CHECK( !ep );
 657                 }
 658                 CPPUNIT_ASSERT( s.empty() );
 659                 CPPUNIT_ASSERT( check_size( s, 0 ));
 660
 661             }
 662
 663             PrintStat()( s );
 664         }
 665
 666         void EllenBinTree_hp_less();
 667         void EllenBinTree_hp_cmp();
 668         void EllenBinTree_hp_cmpless();
 669         void EllenBinTree_hp_less_ic();
 670         void EllenBinTree_hp_cmp_ic();
 671         void EllenBinTree_hp_less_stat();
 672         void EllenBinTree_hp_cmp_ic_stat();
 673         void EllenBinTree_hp_cmp_ic_stat_yield();
 674         void EllenBinTree_hp_less_pool();
 675         void EllenBinTree_hp_less_pool_ic_stat();
 676
 677         void EllenBinTree_dhp_less();
 678         void EllenBinTree_dhp_cmp();
 679         void EllenBinTree_dhp_cmpless();
 680         void EllenBinTree_dhp_less_ic();
 681         void EllenBinTree_dhp_cmp_ic();
 682         void EllenBinTree_dhp_less_stat();
 683         void EllenBinTree_dhp_cmp_ic_stat();
 684         void EllenBinTree_dhp_cmp_ic_stat_yield();
 685         void EllenBinTree_dhp_less_pool();
 686         void EllenBinTree_dhp_less_pool_ic_stat();
 687
 688         void EllenBinTree_rcu_gpi_less();
 689         void EllenBinTree_rcu_gpi_cmp();
 690         void EllenBinTree_rcu_gpi_cmpless();
 691         void EllenBinTree_rcu_gpi_less_ic();
 692         void EllenBinTree_rcu_gpi_cmp_ic();
 693         void EllenBinTree_rcu_gpi_less_stat();
 694         void EllenBinTree_rcu_gpi_cmp_ic_stat();
 695         void EllenBinTree_rcu_gpi_cmp_ic_stat_yield();
 696         void EllenBinTree_rcu_gpi_less_pool();
 697         void EllenBinTree_rcu_gpi_less_pool_ic_stat();
 698
 699         void EllenBinTree_rcu_gpb_less();
 700         void EllenBinTree_rcu_gpb_cmp();
 701         void EllenBinTree_rcu_gpb_cmpless();
 702         void EllenBinTree_rcu_gpb_less_ic();
 703         void EllenBinTree_rcu_gpb_cmp_ic();
 704         void EllenBinTree_rcu_gpb_less_stat();
 705         void EllenBinTree_rcu_gpb_cmp_ic_stat();
 706         void EllenBinTree_rcu_gpb_cmp_ic_stat_yield();
 707         void EllenBinTree_rcu_gpb_less_pool();
 708         void EllenBinTree_rcu_gpb_less_pool_ic_stat();
 709
 710         void EllenBinTree_rcu_gpt_less();
 711         void EllenBinTree_rcu_gpt_cmp();
 712         void EllenBinTree_rcu_gpt_cmpless();
 713         void EllenBinTree_rcu_gpt_less_ic();
 714         void EllenBinTree_rcu_gpt_cmp_ic();
 715         void EllenBinTree_rcu_gpt_less_stat();
 716         void EllenBinTree_rcu_gpt_cmp_ic_stat();
 717         void EllenBinTree_rcu_gpt_cmp_ic_stat_yield();
 718         void EllenBinTree_rcu_gpt_less_pool();
 719         void EllenBinTree_rcu_gpt_less_pool_ic_stat();
 720
 721         void EllenBinTree_rcu_shb_less();
 722         void EllenBinTree_rcu_shb_cmp();
 723         void EllenBinTree_rcu_shb_cmpless();
 724         void EllenBinTree_rcu_shb_less_ic();
 725         void EllenBinTree_rcu_shb_cmp_ic();
 726         void EllenBinTree_rcu_shb_less_stat();
 727         void EllenBinTree_rcu_shb_cmp_ic_stat();
 728         void EllenBinTree_rcu_shb_cmp_ic_stat_yield();
 729         void EllenBinTree_rcu_shb_less_pool();
 730         void EllenBinTree_rcu_shb_less_pool_ic_stat();
 731
 732         void EllenBinTree_rcu_sht_less();
 733         void EllenBinTree_rcu_sht_cmp();
 734         void EllenBinTree_rcu_sht_cmpless();
 735         void EllenBinTree_rcu_sht_less_ic();
 736         void EllenBinTree_rcu_sht_cmp_ic();
 737         void EllenBinTree_rcu_sht_less_stat();
 738         void EllenBinTree_rcu_sht_cmp_ic_stat();
 739         void EllenBinTree_rcu_sht_cmp_ic_stat_yield();
 740         void EllenBinTree_rcu_sht_less_pool();
 741         void EllenBinTree_rcu_sht_less_pool_ic_stat();
 742
 743         CPPUNIT_TEST_SUITE(EllenBinTreeSetHdrTest)
 744             CPPUNIT_TEST(EllenBinTree_hp_less)
 745             CPPUNIT_TEST(EllenBinTree_hp_cmp)
 746             CPPUNIT_TEST(EllenBinTree_hp_less_stat)
 747             CPPUNIT_TEST(EllenBinTree_hp_cmpless)
 748             CPPUNIT_TEST(EllenBinTree_hp_less_ic)
 749             CPPUNIT_TEST(EllenBinTree_hp_cmp_ic)
 750             CPPUNIT_TEST(EllenBinTree_hp_cmp_ic_stat)
 751             CPPUNIT_TEST( EllenBinTree_hp_cmp_ic_stat_yield )
 752             CPPUNIT_TEST( EllenBinTree_hp_less_pool )
 753             CPPUNIT_TEST(EllenBinTree_hp_less_pool_ic_stat)
 754
 755             CPPUNIT_TEST(EllenBinTree_dhp_less)
 756             CPPUNIT_TEST(EllenBinTree_dhp_cmp)
 757             CPPUNIT_TEST(EllenBinTree_dhp_less_stat)
 758             CPPUNIT_TEST(EllenBinTree_dhp_cmpless)
 759             CPPUNIT_TEST(EllenBinTree_dhp_less_ic)
 760             CPPUNIT_TEST(EllenBinTree_dhp_cmp_ic)
 761             CPPUNIT_TEST(EllenBinTree_dhp_cmp_ic_stat)
 762             CPPUNIT_TEST( EllenBinTree_dhp_cmp_ic_stat_yield )
 763             CPPUNIT_TEST( EllenBinTree_dhp_less_pool )
 764             CPPUNIT_TEST(EllenBinTree_dhp_less_pool_ic_stat)
 765
 766             CPPUNIT_TEST(EllenBinTree_rcu_gpi_less)
 767             CPPUNIT_TEST(EllenBinTree_rcu_gpi_cmp)
 768             CPPUNIT_TEST(EllenBinTree_rcu_gpi_less_stat)
 769             CPPUNIT_TEST(EllenBinTree_rcu_gpi_cmpless)
 770             CPPUNIT_TEST(EllenBinTree_rcu_gpi_less_ic)
 771             CPPUNIT_TEST(EllenBinTree_rcu_gpi_cmp_ic)
 772             CPPUNIT_TEST(EllenBinTree_rcu_gpi_cmp_ic_stat)
 773             CPPUNIT_TEST( EllenBinTree_rcu_gpi_cmp_ic_stat_yield )
 774             CPPUNIT_TEST( EllenBinTree_rcu_gpi_less_pool )
 775             CPPUNIT_TEST(EllenBinTree_rcu_gpi_less_pool_ic_stat)
 776
 777             CPPUNIT_TEST(EllenBinTree_rcu_gpb_less)
 778             CPPUNIT_TEST(EllenBinTree_rcu_gpb_cmp)
 779             CPPUNIT_TEST(EllenBinTree_rcu_gpb_less_stat)
 780             CPPUNIT_TEST(EllenBinTree_rcu_gpb_cmpless)
 781             CPPUNIT_TEST(EllenBinTree_rcu_gpb_less_ic)
 782             CPPUNIT_TEST(EllenBinTree_rcu_gpb_cmp_ic)
 783             CPPUNIT_TEST(EllenBinTree_rcu_gpb_cmp_ic_stat)
 784             CPPUNIT_TEST( EllenBinTree_rcu_gpb_cmp_ic_stat_yield )
 785             CPPUNIT_TEST( EllenBinTree_rcu_gpb_less_pool )
 786             CPPUNIT_TEST(EllenBinTree_rcu_gpb_less_pool_ic_stat)
 787
 788             CPPUNIT_TEST(EllenBinTree_rcu_gpt_less)
 789             CPPUNIT_TEST(EllenBinTree_rcu_gpt_cmp)
 790             CPPUNIT_TEST(EllenBinTree_rcu_gpt_less_stat)
 791             CPPUNIT_TEST(EllenBinTree_rcu_gpt_cmpless)
 792             CPPUNIT_TEST(EllenBinTree_rcu_gpt_less_ic)
 793             CPPUNIT_TEST(EllenBinTree_rcu_gpt_cmp_ic)
 794             CPPUNIT_TEST(EllenBinTree_rcu_gpt_cmp_ic_stat)
 795             CPPUNIT_TEST( EllenBinTree_rcu_gpt_cmp_ic_stat_yield )
 796             CPPUNIT_TEST( EllenBinTree_rcu_gpt_less_pool )
 797             CPPUNIT_TEST(EllenBinTree_rcu_gpt_less_pool_ic_stat)
 798
 799             CPPUNIT_TEST(EllenBinTree_rcu_shb_less)
 800             CPPUNIT_TEST(EllenBinTree_rcu_shb_cmp)
 801             CPPUNIT_TEST(EllenBinTree_rcu_shb_less_stat)
 802             CPPUNIT_TEST(EllenBinTree_rcu_shb_cmpless)
 803             CPPUNIT_TEST(EllenBinTree_rcu_shb_less_ic)
 804             CPPUNIT_TEST(EllenBinTree_rcu_shb_cmp_ic)
 805             CPPUNIT_TEST(EllenBinTree_rcu_shb_cmp_ic_stat)
 806             CPPUNIT_TEST( EllenBinTree_rcu_shb_cmp_ic_stat_yield )
 807             CPPUNIT_TEST( EllenBinTree_rcu_shb_less_pool )
 808             CPPUNIT_TEST(EllenBinTree_rcu_shb_less_pool_ic_stat)
 809
 810             CPPUNIT_TEST(EllenBinTree_rcu_sht_less)
 811             CPPUNIT_TEST(EllenBinTree_rcu_sht_cmp)
 812             CPPUNIT_TEST(EllenBinTree_rcu_sht_less_stat)
 813             CPPUNIT_TEST(EllenBinTree_rcu_sht_cmpless)
 814             CPPUNIT_TEST(EllenBinTree_rcu_sht_less_ic)
 815             CPPUNIT_TEST(EllenBinTree_rcu_sht_cmp_ic)
 816             CPPUNIT_TEST(EllenBinTree_rcu_sht_cmp_ic_stat)
 817             CPPUNIT_TEST( EllenBinTree_rcu_sht_cmp_ic_stat_yield )
 818             CPPUNIT_TEST( EllenBinTree_rcu_sht_less_pool )
 819             CPPUNIT_TEST(EllenBinTree_rcu_sht_less_pool_ic_stat)
 820
 821         CPPUNIT_TEST_SUITE_END()
 822     };
 823 } // namespace tree
 824
 825 #endif // #ifndef CDSTEST_HDR_ELLENBINTREE_SET_H