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 <cds/ref.h>
   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, boost::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(), boost::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(), boost::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, boost::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, boost::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, boost::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, boost::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, boost::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(), boost::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 #       ifdef CDS_EMPLACE_SUPPORT
 430             // emplace test
 431             CPPUNIT_ASSERT( s.emplace( 151 )) ;  // key = 151,  val = 1510
 432             CPPUNIT_ASSERT( s.emplace( 174, 471 )) ;    // key = 174, val = 471
 433             CPPUNIT_ASSERT( s.emplace( std::make_pair( 190, 91 ) )) ; // key == 190, val = 91
 434             CPPUNIT_ASSERT( !s.empty() );
 435             CPPUNIT_ASSERT( check_size( s, 3 ));
 436
 437             CPPUNIT_ASSERT( s.find(151));
 438             CPPUNIT_ASSERT( s.find_with(174, less()));
 439             CPPUNIT_ASSERT( s.find(190));
 440
 441             {
 442                 copy_found<value_type> f;
 443                 f.m_found.nKey = 0;
 444                 key = 151;
 445                 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
 446                 CPPUNIT_ASSERT( f.m_found.nKey == 151 );
 447                 CPPUNIT_ASSERT( f.m_found.nVal == 1510 );
 448
 449                 key = 174;
 450                 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
 451                 CPPUNIT_ASSERT( f.m_found.nKey == 174 );
 452                 CPPUNIT_ASSERT( f.m_found.nVal == 471 );
 453
 454                 key = 190;
 455                 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
 456                 CPPUNIT_ASSERT( f.m_found.nKey == 190 );
 457                 CPPUNIT_ASSERT( f.m_found.nVal == 91 );
 458             }
 459
 460             s.clear();
 461             CPPUNIT_ASSERT( s.empty() );
 462             CPPUNIT_ASSERT( check_size( s, 0 ));
 463 #       endif
 464         }
 465
 466         template <typename Set>
 467         void fill_set( Set& s, data_array& a )
 468         {
 469             CPPUNIT_ASSERT( s.empty() );
 470             for ( size_t i = 0; i < c_nItemCount; ++i ) {
 471                 CPPUNIT_ASSERT( s.insert( a[i] ));
 472             }
 473             CPPUNIT_ASSERT( !s.empty() );
 474             CPPUNIT_ASSERT( check_size( s, c_nItemCount ));
 475
 476         }
 477
 478         template <class Set, class PrintStat>
 479         void test()
 480         {
 481             typedef Set set_type;
 482
 483             set_type s;
 484
 485             test_with( s );
 486
 487             s.clear();
 488             CPPUNIT_ASSERT( s.empty() );
 489             CPPUNIT_ASSERT( check_size( s, 0 ));
 490
 491             // extract min/max
 492             {
 493                 typename Set::guarded_ptr gp;
 494
 495                 data_array arr;
 496                 fill_set( s, arr );
 497
 498                 int i = 0;
 499                 while ( !s.empty() ) {
 500                     CPPUNIT_ASSERT( s.extract_min( gp ) );
 501                     CPPUNIT_ASSERT( gp->nKey == i );
 502                     ++i;
 503                 }
 504                 CPPUNIT_ASSERT( s.empty() );
 505                 CPPUNIT_ASSERT( check_size( s, 0 ));
 506
 507                 fill_set( s, arr );
 508                 i = (int) c_nItemCount - 1;
 509                 while ( !s.empty() ) {
 510                     CPPUNIT_ASSERT( s.extract_max( 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                     CPPUNIT_ASSERT( s.get( gp, nKey ));
 521                     CPPUNIT_ASSERT( !gp.empty());
 522                     CPPUNIT_CHECK( gp->nKey == nKey );
 523
 524                     gp.release();
 525                     CPPUNIT_ASSERT( s.extract( gp, nKey ));
 526                     CPPUNIT_ASSERT( !gp.empty());
 527                     CPPUNIT_CHECK( gp->nKey == nKey );
 528
 529                     gp.release();
 530                     CPPUNIT_CHECK( !s.get( gp, nKey ));
 531                     CPPUNIT_CHECK( gp.empty());
 532                     CPPUNIT_CHECK( !s.extract( gp, nKey ));
 533                     CPPUNIT_CHECK( gp.empty());
 534                 }
 535                 CPPUNIT_ASSERT( s.empty() );
 536                 CPPUNIT_ASSERT( check_size( s, 0 ));
 537
 538                 fill_set( s, arr );
 539                 for ( int i = 0; i < static_cast<int>( c_nItemCount ); ++i ) {
 540                     int nKey = arr[i];
 541                     CPPUNIT_ASSERT( s.get_with( gp, wrapped_int(nKey), wrapped_less() ));
 542                     CPPUNIT_ASSERT( !gp.empty());
 543                     CPPUNIT_CHECK( gp->nKey == nKey );
 544
 545                     gp.release();
 546                     CPPUNIT_ASSERT( s.extract_with( gp, wrapped_int(nKey), wrapped_less() ));
 547                     CPPUNIT_ASSERT( !gp.empty());
 548                     CPPUNIT_CHECK( gp->nKey == nKey );
 549
 550                     gp.release();
 551                     CPPUNIT_CHECK( !s.get_with( gp, wrapped_int(nKey), wrapped_less() ));
 552                     CPPUNIT_CHECK( gp.empty());
 553                     CPPUNIT_CHECK( !s.extract_with( gp, wrapped_int(nKey), wrapped_less() ));
 554                     CPPUNIT_CHECK( gp.empty());
 555                 }
 556                 CPPUNIT_ASSERT( s.empty() );
 557                 CPPUNIT_ASSERT( check_size( s, 0 ));
 558             }
 559
 560             PrintStat()( s );
 561         }
 562
 563         template <class Set, class PrintStat>
 564         void test_rcu()
 565         {
 566             typedef Set set_type;
 567
 568             set_type s;
 569
 570             test_with( s );
 571
 572             s.clear();
 573             CPPUNIT_ASSERT( s.empty() );
 574             CPPUNIT_ASSERT( check_size( s, 0 ));
 575
 576             // extract min/max
 577             {
 578                 typename set_type::exempt_ptr ep;
 579                 data_array arr;
 580                 fill_set( s, arr );
 581
 582                 int i = 0;
 583                 value_type v;
 584                 while ( !s.empty() ) {
 585                     CPPUNIT_ASSERT( s.extract_min( ep ) );
 586                     CPPUNIT_ASSERT( !ep.empty());
 587                     CPPUNIT_CHECK( ep->nKey == i );
 588                     ++i;
 589                     ep.release();
 590                 }
 591                 CPPUNIT_ASSERT( s.empty() );
 592                 CPPUNIT_ASSERT( check_size( s, 0 ));
 593
 594                 fill_set( s, arr );
 595                 i = (int) c_nItemCount - 1;
 596                 while ( !s.empty() ) {
 597                     CPPUNIT_ASSERT( s.extract_max( ep ) );
 598                     CPPUNIT_ASSERT( !ep.empty());
 599                     CPPUNIT_CHECK( ep->nKey == i );
 600                     --i;
 601                     ep.release();
 602                 }
 603                 CPPUNIT_ASSERT( s.empty() );
 604                 CPPUNIT_ASSERT( check_size( s, 0 ));
 605
 606                 fill_set( s, arr );
 607                 for ( size_t i = 0; i < c_nItemCount; ++i ) {
 608                     int nKey = arr[i];
 609                     {
 610                         typename set_type::rcu_lock l;
 611                         value_type * p = s.get( nKey );
 612                         CPPUNIT_ASSERT( p != nullptr );
 613                         CPPUNIT_CHECK( p->nKey == nKey );
 614                     }
 615                     CPPUNIT_ASSERT( s.extract( ep, nKey ));
 616                     CPPUNIT_ASSERT( !ep.empty());
 617                     CPPUNIT_CHECK( ep->nKey == nKey);
 618                     ep.release();
 619
 620                     {
 621                         typename set_type::rcu_lock l;
 622                         CPPUNIT_CHECK( s.get( nKey ) == nullptr );
 623                     }
 624                     CPPUNIT_CHECK( !s.extract( ep, nKey ));
 625                 }
 626                 CPPUNIT_ASSERT( s.empty() );
 627                 CPPUNIT_ASSERT( check_size( s, 0 ));
 628
 629                 fill_set( s, arr );
 630                 for ( size_t i = 0; i < c_nItemCount; ++i ) {
 631                     int nKey = arr[i];
 632                     {
 633                         typename set_type::rcu_lock l;
 634                         value_type * p = s.get_with( wrapped_int(nKey), wrapped_less() );
 635                         CPPUNIT_ASSERT( p != nullptr );
 636                         CPPUNIT_CHECK( p->nKey == nKey );
 637                     }
 638                     CPPUNIT_ASSERT( s.extract_with( ep, wrapped_int(nKey), wrapped_less() ));
 639                     CPPUNIT_ASSERT( !ep.empty());
 640                     CPPUNIT_CHECK( ep->nKey == nKey);
 641                     ep.release();
 642
 643                     {
 644                         typename set_type::rcu_lock l;
 645                         CPPUNIT_CHECK( s.get_with( wrapped_int( nKey ), wrapped_less() ) == nullptr );
 646                     }
 647                     CPPUNIT_CHECK( !s.extract_with( ep, wrapped_int(nKey), wrapped_less() ));
 648                 }
 649                 CPPUNIT_ASSERT( s.empty() );
 650                 CPPUNIT_ASSERT( check_size( s, 0 ));
 651
 652             }
 653
 654             PrintStat()( s );
 655         }
 656
 657         void EllenBinTree_hp_less();
 658         void EllenBinTree_hp_cmp();
 659         void EllenBinTree_hp_cmpless();
 660         void EllenBinTree_hp_less_ic();
 661         void EllenBinTree_hp_cmp_ic();
 662         void EllenBinTree_hp_less_stat();
 663         void EllenBinTree_hp_cmp_ic_stat();
 664         void EllenBinTree_hp_less_pool();
 665         void EllenBinTree_hp_less_pool_ic_stat();
 666
 667         void EllenBinTree_ptb_less();
 668         void EllenBinTree_ptb_cmp();
 669         void EllenBinTree_ptb_cmpless();
 670         void EllenBinTree_ptb_less_ic();
 671         void EllenBinTree_ptb_cmp_ic();
 672         void EllenBinTree_ptb_less_stat();
 673         void EllenBinTree_ptb_cmp_ic_stat();
 674         void EllenBinTree_ptb_less_pool();
 675         void EllenBinTree_ptb_less_pool_ic_stat();
 676
 677         void EllenBinTree_rcu_gpi_less();
 678         void EllenBinTree_rcu_gpi_cmp();
 679         void EllenBinTree_rcu_gpi_cmpless();
 680         void EllenBinTree_rcu_gpi_less_ic();
 681         void EllenBinTree_rcu_gpi_cmp_ic();
 682         void EllenBinTree_rcu_gpi_less_stat();
 683         void EllenBinTree_rcu_gpi_cmp_ic_stat();
 684         void EllenBinTree_rcu_gpi_less_pool();
 685         void EllenBinTree_rcu_gpi_less_pool_ic_stat();
 686
 687         void EllenBinTree_rcu_gpb_less();
 688         void EllenBinTree_rcu_gpb_cmp();
 689         void EllenBinTree_rcu_gpb_cmpless();
 690         void EllenBinTree_rcu_gpb_less_ic();
 691         void EllenBinTree_rcu_gpb_cmp_ic();
 692         void EllenBinTree_rcu_gpb_less_stat();
 693         void EllenBinTree_rcu_gpb_cmp_ic_stat();
 694         void EllenBinTree_rcu_gpb_less_pool();
 695         void EllenBinTree_rcu_gpb_less_pool_ic_stat();
 696
 697         void EllenBinTree_rcu_gpt_less();
 698         void EllenBinTree_rcu_gpt_cmp();
 699         void EllenBinTree_rcu_gpt_cmpless();
 700         void EllenBinTree_rcu_gpt_less_ic();
 701         void EllenBinTree_rcu_gpt_cmp_ic();
 702         void EllenBinTree_rcu_gpt_less_stat();
 703         void EllenBinTree_rcu_gpt_cmp_ic_stat();
 704         void EllenBinTree_rcu_gpt_less_pool();
 705         void EllenBinTree_rcu_gpt_less_pool_ic_stat();
 706
 707         void EllenBinTree_rcu_shb_less();
 708         void EllenBinTree_rcu_shb_cmp();
 709         void EllenBinTree_rcu_shb_cmpless();
 710         void EllenBinTree_rcu_shb_less_ic();
 711         void EllenBinTree_rcu_shb_cmp_ic();
 712         void EllenBinTree_rcu_shb_less_stat();
 713         void EllenBinTree_rcu_shb_cmp_ic_stat();
 714         void EllenBinTree_rcu_shb_less_pool();
 715         void EllenBinTree_rcu_shb_less_pool_ic_stat();
 716
 717         void EllenBinTree_rcu_sht_less();
 718         void EllenBinTree_rcu_sht_cmp();
 719         void EllenBinTree_rcu_sht_cmpless();
 720         void EllenBinTree_rcu_sht_less_ic();
 721         void EllenBinTree_rcu_sht_cmp_ic();
 722         void EllenBinTree_rcu_sht_less_stat();
 723         void EllenBinTree_rcu_sht_cmp_ic_stat();
 724         void EllenBinTree_rcu_sht_less_pool();
 725         void EllenBinTree_rcu_sht_less_pool_ic_stat();
 726
 727         CPPUNIT_TEST_SUITE(EllenBinTreeSetHdrTest)
 728             CPPUNIT_TEST(EllenBinTree_hp_less)
 729             CPPUNIT_TEST(EllenBinTree_hp_cmp)
 730             CPPUNIT_TEST(EllenBinTree_hp_less_stat)
 731             CPPUNIT_TEST(EllenBinTree_hp_cmpless)
 732             CPPUNIT_TEST(EllenBinTree_hp_less_ic)
 733             CPPUNIT_TEST(EllenBinTree_hp_cmp_ic)
 734             CPPUNIT_TEST(EllenBinTree_hp_cmp_ic_stat)
 735             CPPUNIT_TEST(EllenBinTree_hp_less_pool)
 736             CPPUNIT_TEST(EllenBinTree_hp_less_pool_ic_stat)
 737
 738             CPPUNIT_TEST(EllenBinTree_ptb_less)
 739             CPPUNIT_TEST(EllenBinTree_ptb_cmp)
 740             CPPUNIT_TEST(EllenBinTree_ptb_less_stat)
 741             CPPUNIT_TEST(EllenBinTree_ptb_cmpless)
 742             CPPUNIT_TEST(EllenBinTree_ptb_less_ic)
 743             CPPUNIT_TEST(EllenBinTree_ptb_cmp_ic)
 744             CPPUNIT_TEST(EllenBinTree_ptb_cmp_ic_stat)
 745             CPPUNIT_TEST(EllenBinTree_ptb_less_pool)
 746             CPPUNIT_TEST(EllenBinTree_ptb_less_pool_ic_stat)
 747
 748             CPPUNIT_TEST(EllenBinTree_rcu_gpi_less)
 749             CPPUNIT_TEST(EllenBinTree_rcu_gpi_cmp)
 750             CPPUNIT_TEST(EllenBinTree_rcu_gpi_less_stat)
 751             CPPUNIT_TEST(EllenBinTree_rcu_gpi_cmpless)
 752             CPPUNIT_TEST(EllenBinTree_rcu_gpi_less_ic)
 753             CPPUNIT_TEST(EllenBinTree_rcu_gpi_cmp_ic)
 754             CPPUNIT_TEST(EllenBinTree_rcu_gpi_cmp_ic_stat)
 755             CPPUNIT_TEST(EllenBinTree_rcu_gpi_less_pool)
 756             CPPUNIT_TEST(EllenBinTree_rcu_gpi_less_pool_ic_stat)
 757
 758             CPPUNIT_TEST(EllenBinTree_rcu_gpb_less)
 759             CPPUNIT_TEST(EllenBinTree_rcu_gpb_cmp)
 760             CPPUNIT_TEST(EllenBinTree_rcu_gpb_less_stat)
 761             CPPUNIT_TEST(EllenBinTree_rcu_gpb_cmpless)
 762             CPPUNIT_TEST(EllenBinTree_rcu_gpb_less_ic)
 763             CPPUNIT_TEST(EllenBinTree_rcu_gpb_cmp_ic)
 764             CPPUNIT_TEST(EllenBinTree_rcu_gpb_cmp_ic_stat)
 765             CPPUNIT_TEST(EllenBinTree_rcu_gpb_less_pool)
 766             CPPUNIT_TEST(EllenBinTree_rcu_gpb_less_pool_ic_stat)
 767
 768             CPPUNIT_TEST(EllenBinTree_rcu_gpt_less)
 769             CPPUNIT_TEST(EllenBinTree_rcu_gpt_cmp)
 770             CPPUNIT_TEST(EllenBinTree_rcu_gpt_less_stat)
 771             CPPUNIT_TEST(EllenBinTree_rcu_gpt_cmpless)
 772             CPPUNIT_TEST(EllenBinTree_rcu_gpt_less_ic)
 773             CPPUNIT_TEST(EllenBinTree_rcu_gpt_cmp_ic)
 774             CPPUNIT_TEST(EllenBinTree_rcu_gpt_cmp_ic_stat)
 775             CPPUNIT_TEST(EllenBinTree_rcu_gpt_less_pool)
 776             CPPUNIT_TEST(EllenBinTree_rcu_gpt_less_pool_ic_stat)
 777
 778             CPPUNIT_TEST(EllenBinTree_rcu_shb_less)
 779             CPPUNIT_TEST(EllenBinTree_rcu_shb_cmp)
 780             CPPUNIT_TEST(EllenBinTree_rcu_shb_less_stat)
 781             CPPUNIT_TEST(EllenBinTree_rcu_shb_cmpless)
 782             CPPUNIT_TEST(EllenBinTree_rcu_shb_less_ic)
 783             CPPUNIT_TEST(EllenBinTree_rcu_shb_cmp_ic)
 784             CPPUNIT_TEST(EllenBinTree_rcu_shb_cmp_ic_stat)
 785             CPPUNIT_TEST(EllenBinTree_rcu_shb_less_pool)
 786             CPPUNIT_TEST(EllenBinTree_rcu_shb_less_pool_ic_stat)
 787
 788             CPPUNIT_TEST(EllenBinTree_rcu_sht_less)
 789             CPPUNIT_TEST(EllenBinTree_rcu_sht_cmp)
 790             CPPUNIT_TEST(EllenBinTree_rcu_sht_less_stat)
 791             CPPUNIT_TEST(EllenBinTree_rcu_sht_cmpless)
 792             CPPUNIT_TEST(EllenBinTree_rcu_sht_less_ic)
 793             CPPUNIT_TEST(EllenBinTree_rcu_sht_cmp_ic)
 794             CPPUNIT_TEST(EllenBinTree_rcu_sht_cmp_ic_stat)
 795             CPPUNIT_TEST(EllenBinTree_rcu_sht_less_pool)
 796             CPPUNIT_TEST(EllenBinTree_rcu_sht_less_pool_ic_stat)
 797
 798         CPPUNIT_TEST_SUITE_END()
 799     };
 800 } // namespace tree
 801
 802 #endif // #ifndef CDSHDRTEST_ELLENBINTREE_SET_H