tests/test-hdr/tree/hdr_ellenbintree_set.h

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