tests/test-hdr/tree/hdr_intrusive_bintree.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSHDRTEST_INTRUSIVE_BINTREE_H
   4 #define CDSHDRTEST_INTRUSIVE_BINTREE_H
   5
   6 #include "cppunit/cppunit_proxy.h"
   7 #include "size_check.h"
   8 #include <algorithm>
   9
  10 namespace tree {
  11
  12     class IntrusiveBinTreeHdrTest: public CppUnitMini::TestCase
  13     {
  14     public:
  15         typedef int     key_type;
  16
  17         struct stat_data {
  18             size_t  nDisposeCount;
  19             size_t  nWaitingDispCount;
  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                 : nDisposeCount(0)
  29                 , nWaitingDispCount(0)
  30                 , nInsertFuncCall(0)
  31                 , nEnsureExistFuncCall(0)
  32                 , nEnsureNewFuncCall(0)
  33                 , nEraseFuncCall(0)
  34                 , nFindFuncCall(0)
  35                 , nFindConstFuncCall(0)
  36             {}
  37         };
  38
  39         template <typename Hook>
  40         struct base_hook_value: public Hook
  41         {
  42             int     nKey;
  43             int     nValue;
  44             mutable stat_data   stat;
  45
  46             base_hook_value()
  47             {}
  48
  49             base_hook_value( int key )
  50                 : nKey(key)
  51                 , nValue(key * 2)
  52             {}
  53
  54             base_hook_value( int key, int val )
  55                 : nKey(key)
  56                 , nValue(val)
  57             {}
  58
  59 #   ifdef _DEBUG
  60             base_hook_value( base_hook_value&& s )
  61                 : Hook()
  62                 , nKey(s.nKey)
  63                 , nValue(s.nValue)
  64             {}
  65             base_hook_value& operator=( base_hook_value const& s )
  66             {
  67                 nKey = s.nKey;
  68                 nValue = s.nValue;
  69                 return *this;
  70             }
  71 #   endif
  72         };
  73
  74         template <typename Hook>
  75         struct member_hook_value
  76         {
  77             int     nKey;
  78             int     nValue;
  79             Hook    hook;
  80             mutable stat_data   stat;
  81
  82             member_hook_value()
  83             {}
  84
  85             member_hook_value( int key )
  86                 : nKey(key)
  87                 , nValue(key * 2)
  88             {}
  89
  90             member_hook_value( int key, int val )
  91                 : nKey(key)
  92                 , nValue(val)
  93             {}
  94 #   ifdef _DEBUG
  95             member_hook_value( member_hook_value&& s )
  96                 : nKey(s.nKey)
  97                 , nValue(s.nValue)
  98                 , hook()
  99             {}
 100             member_hook_value& operator=( member_hook_value const& s )
 101             {
 102                 nKey = s.nKey;
 103                 nValue = s.nValue;
 104                 return *this;
 105             }
 106 #   endif
 107         };
 108
 109         template <typename ValueType>
 110         struct less {
 111             typedef ValueType value_type;
 112
 113             bool operator()( int k1, int k2 ) const
 114             {
 115                 return k1 < k2;
 116             }
 117             bool operator()( value_type const& v1, value_type const& v2 ) const
 118             {
 119                 return v1.nKey < v2.nKey;
 120             }
 121             bool operator()( value_type const& v, int k ) const
 122             {
 123                 return v.nKey < k;
 124             }
 125             bool operator()( int k, value_type const& v ) const
 126             {
 127                 return k < v.nKey;
 128             }
 129         };
 130
 131         template <typename ValueType>
 132         struct compare {
 133             typedef ValueType value_type;
 134
 135             int cmp( int k1, int k2 ) const
 136             {
 137                 return k1 < k2 ? -1 : (k1 > k2 ? 1 : 0);
 138             }
 139             int operator()( int k1, int k2 ) const
 140             {
 141                 return cmp( k1, k2 );
 142             }
 143             int operator()( value_type const& v1, value_type const& v2 ) const
 144             {
 145                 return cmp( v1.nKey, v2.nKey );
 146             }
 147             int operator()( value_type const& v, int k ) const
 148             {
 149                 return cmp( v.nKey, k );
 150             }
 151             int operator()( int k, value_type const& v ) const
 152             {
 153                 return cmp( k, v.nKey );
 154             }
 155         };
 156
 157         struct wrapped_int {
 158             int  nKey;
 159
 160             wrapped_int( int n )
 161                 : nKey(n)
 162             {}
 163         };
 164
 165         template <typename T>
 166         struct wrapped_less
 167         {
 168             bool operator()( wrapped_int const& w, int n ) const
 169             {
 170                 return w.nKey < n;
 171             }
 172             bool operator()( int n, wrapped_int const& w ) const
 173             {
 174                 return n < w.nKey;
 175             }
 176             bool operator()( wrapped_int const& w, T const& v ) const
 177             {
 178                 return w.nKey < v.nKey;
 179             }
 180             bool operator()( T const& v, wrapped_int const& w ) const
 181             {
 182                 return v.nKey < w.nKey;
 183             }
 184         };
 185
 186         template <typename ValueType>
 187         struct key_extractor {
 188             void operator()( int& dest, ValueType const& src ) const
 189             {
 190                 dest = src.nKey;
 191             }
 192         };
 193
 194         template <typename ValueType>
 195         struct disposer {
 196             void operator()( ValueType * v ) const
 197             {
 198                 ++v->stat.nDisposeCount;
 199             }
 200         };
 201
 202         struct insert_functor {
 203             template <typename T>
 204             void operator()( T& v ) const
 205             {
 206                 ++v.stat.nInsertFuncCall;
 207             }
 208         };
 209
 210         struct ensure_functor {
 211             template <typename T>
 212             void operator()( bool bNew, T& dest, T& src) const
 213             {
 214                 if ( bNew )
 215                     ++dest.stat.nEnsureNewFuncCall;
 216                 else {
 217                     dest.nValue *= 2;
 218                     ++src.stat.nEnsureExistFuncCall;
 219                 }
 220             }
 221         };
 222
 223         struct erase_functor {
 224             template <typename T>
 225             void operator()( T const& v ) const
 226             {
 227                 ++v.stat.nEraseFuncCall;
 228             }
 229         };
 230
 231         struct find_functor {
 232             template <typename T, typename Q>
 233             void operator()( T const& v, Q& q ) const
 234             {
 235                 ++v.stat.nFindFuncCall;
 236             }
 237             template <typename T, typename Q>
 238             void operator()( T const& v, Q const& q ) const
 239             {
 240                 ++v.stat.nFindConstFuncCall;
 241             }
 242         };
 243
 244     protected:
 245         static const size_t c_nItemCount = 10000;
 246
 247         template <typename T>
 248         class data_array
 249         {
 250             T *     pFirst;
 251             T *     pLast;
 252
 253         public:
 254             data_array()
 255                 : pFirst( new T[c_nItemCount] )
 256                 , pLast( pFirst + c_nItemCount )
 257             {
 258                 int i = 0;
 259                 for ( T * p = pFirst; p != pLast; ++p, ++i ) {
 260                     p->nKey = i;
 261                     p->nValue = i * 2;
 262                 }
 263
 264                 std::random_shuffle( pFirst, pLast );
 265             }
 266
 267             ~data_array()
 268             {
 269                 delete [] pFirst;
 270             }
 271
 272             T * begin() { return pFirst; }
 273             T * end()   { return pLast ; }
 274         };
 275
 276     protected:
 277         template <typename Tree>
 278         void test_common( Tree& t )
 279         {
 280             typedef Tree tree_type;
 281             typedef typename tree_type::key_type     key_type;
 282             typedef typename tree_type::value_type   value_type;
 283
 284             {
 285                 value_type v1( 10, 100 );
 286                 value_type v2( 20, 200 );
 287                 value_type v3( 30, 300 );
 288                 value_type v4( 25, 250 );
 289                 value_type v5( -50, -500 );
 290
 291                 // insert/ensure
 292                 CPPUNIT_ASSERT( t.empty() );
 293                 CPPUNIT_ASSERT( misc::check_size( t, 0 ));
 294                 CPPUNIT_CHECK( !t.find( v1.nKey ));
 295                 CPPUNIT_CHECK( !t.find( v1 ));
 296                 CPPUNIT_CHECK( !t.find( v2.nKey ));
 297                 CPPUNIT_CHECK( !t.find( v2 ));
 298                 CPPUNIT_CHECK( !t.find( v3.nKey ));
 299                 CPPUNIT_CHECK( !t.find( v3 ));
 300                 CPPUNIT_CHECK( !t.find( v4.nKey ));
 301                 CPPUNIT_CHECK( !t.find( v4 ));
 302                 CPPUNIT_CHECK( !t.find( v5.nKey ));
 303                 CPPUNIT_CHECK( !t.find( v5 ));
 304
 305                 CPPUNIT_ASSERT( t.insert( v1 ));
 306                 CPPUNIT_ASSERT( t.check_consistency() );
 307                 CPPUNIT_ASSERT( !t.empty() );
 308                 CPPUNIT_ASSERT( misc::check_size( t, 1 ));
 309                 CPPUNIT_CHECK( t.find( v1.nKey ));
 310                 CPPUNIT_CHECK( t.find( v1 ));
 311                 CPPUNIT_CHECK( !t.find( v2.nKey ));
 312                 CPPUNIT_CHECK( !t.find( v2 ));
 313                 CPPUNIT_CHECK( !t.find( v3.nKey ));
 314                 CPPUNIT_CHECK( !t.find( v3 ));
 315                 CPPUNIT_CHECK( !t.find( v4.nKey ));
 316                 CPPUNIT_CHECK( !t.find( v4 ));
 317                 CPPUNIT_CHECK( !t.find( v5.nKey ));
 318                 CPPUNIT_CHECK( !t.find( v5 ));
 319
 320                 CPPUNIT_ASSERT( v2.stat.nInsertFuncCall == 0 );
 321                 CPPUNIT_ASSERT( t.insert( v2, insert_functor() ));
 322                 CPPUNIT_ASSERT( t.check_consistency() );
 323                 CPPUNIT_ASSERT( v2.stat.nInsertFuncCall == 1 );
 324                 CPPUNIT_ASSERT( t.find( v1.nKey ));
 325                 CPPUNIT_ASSERT( t.find( v1 ));
 326                 CPPUNIT_ASSERT( t.find( v2.nKey ));
 327                 CPPUNIT_ASSERT( t.find( v2 ));
 328                 CPPUNIT_ASSERT( !t.find( v3.nKey ));
 329                 CPPUNIT_ASSERT( !t.find( v3 ));
 330                 CPPUNIT_ASSERT( !t.find( v4.nKey ));
 331                 CPPUNIT_ASSERT( !t.find( v4 ));
 332                 CPPUNIT_ASSERT( !t.find( v5.nKey ));
 333                 CPPUNIT_ASSERT( !t.find( v5 ));
 334                 CPPUNIT_ASSERT( !t.empty() );
 335                 CPPUNIT_ASSERT( misc::check_size( t, 2 ));
 336
 337                 CPPUNIT_ASSERT( v3.stat.nEnsureNewFuncCall == 0 );
 338                 CPPUNIT_ASSERT( v3.stat.nEnsureExistFuncCall == 0 );
 339                 CPPUNIT_ASSERT( t.ensure( v3, ensure_functor() ).second );
 340                 CPPUNIT_ASSERT( t.check_consistency() );
 341                 CPPUNIT_ASSERT( v3.stat.nEnsureNewFuncCall == 1 );
 342                 CPPUNIT_ASSERT( v3.stat.nEnsureExistFuncCall == 0 );
 343                 CPPUNIT_ASSERT( v3.nValue == 300 );
 344                 CPPUNIT_ASSERT( !t.ensure( v3, ensure_functor() ).second );
 345                 CPPUNIT_ASSERT( v3.stat.nEnsureNewFuncCall == 1 );
 346                 CPPUNIT_ASSERT( v3.stat.nEnsureExistFuncCall == 1 );
 347                 CPPUNIT_ASSERT( v3.nValue == 600 );
 348                 CPPUNIT_ASSERT( t.find( v1.nKey ));
 349                 CPPUNIT_ASSERT( t.find( v1 ));
 350                 CPPUNIT_ASSERT( t.find( v2.nKey ));
 351                 CPPUNIT_ASSERT( t.find( v2 ));
 352                 CPPUNIT_ASSERT( t.find( v3.nKey ));
 353                 CPPUNIT_ASSERT( t.find( v3 ));
 354                 CPPUNIT_ASSERT( !t.find( v4.nKey ));
 355                 CPPUNIT_ASSERT( !t.find( v4 ));
 356                 CPPUNIT_ASSERT( !t.find( v5.nKey ));
 357                 CPPUNIT_ASSERT( !t.find( v5 ));
 358                 CPPUNIT_ASSERT( !t.empty() );
 359                 CPPUNIT_ASSERT( misc::check_size( t, 3 ));
 360
 361                 {
 362                     value_type v( v3.nKey, v3.nValue );
 363                     CPPUNIT_ASSERT( v.stat.nEnsureExistFuncCall == 0 );
 364                     CPPUNIT_ASSERT( v3.stat.nEnsureNewFuncCall == 1 );
 365                     CPPUNIT_ASSERT( v3.stat.nEnsureExistFuncCall == 1 );
 366                     CPPUNIT_ASSERT( v3.nValue == 600 );
 367                     CPPUNIT_ASSERT( !t.ensure( v, ensure_functor() ).second );
 368                     CPPUNIT_ASSERT( v3.stat.nEnsureNewFuncCall == 1 );
 369                     CPPUNIT_ASSERT( v.stat.nEnsureExistFuncCall == 1 );
 370                     CPPUNIT_ASSERT( v3.nValue == 1200 );
 371
 372                 }
 373                 v3.nValue = 300;
 374                 CPPUNIT_ASSERT( !t.insert( v3 ));
 375
 376                 CPPUNIT_ASSERT( t.insert( v4 ));
 377                 CPPUNIT_ASSERT( t.check_consistency() );
 378                 CPPUNIT_ASSERT( t.find( v1.nKey ));
 379                 CPPUNIT_ASSERT( t.find( v1 ));
 380                 CPPUNIT_ASSERT( t.find( v2.nKey ));
 381                 CPPUNIT_ASSERT( t.find( v2 ));
 382                 CPPUNIT_ASSERT( t.find( v3.nKey ));
 383                 CPPUNIT_ASSERT( t.find( v3 ));
 384                 CPPUNIT_ASSERT( t.find( v4.nKey ));
 385                 CPPUNIT_ASSERT( t.find( v4 ));
 386                 CPPUNIT_ASSERT( !t.find( v5.nKey ));
 387                 CPPUNIT_ASSERT( !t.find( v5 ));
 388                 CPPUNIT_ASSERT( !t.empty() );
 389                 CPPUNIT_ASSERT( misc::check_size( t, 4 ));
 390
 391                 CPPUNIT_ASSERT( t.insert( v5 ));
 392                 CPPUNIT_ASSERT( t.check_consistency() );
 393                 CPPUNIT_ASSERT( t.find( v1.nKey ));
 394                 CPPUNIT_ASSERT( t.find( v1 ));
 395                 CPPUNIT_ASSERT( t.find( v2.nKey ));
 396                 CPPUNIT_ASSERT( t.find( v2 ));
 397                 CPPUNIT_ASSERT( t.find( v3.nKey ));
 398                 CPPUNIT_ASSERT( t.find( v3 ));
 399                 CPPUNIT_ASSERT( t.find( v4.nKey ));
 400                 CPPUNIT_ASSERT( t.find( v4 ));
 401                 CPPUNIT_ASSERT( t.find( v5.nKey ));
 402                 CPPUNIT_ASSERT( t.find( v5 ));
 403                 CPPUNIT_ASSERT( !t.empty() );
 404                 CPPUNIT_ASSERT( misc::check_size( t, 5 ));
 405
 406                 //unlink/erase
 407                 ++v1.stat.nWaitingDispCount;
 408                 CPPUNIT_ASSERT( t.unlink(v1));
 409                 CPPUNIT_ASSERT( t.check_consistency() );
 410                 CPPUNIT_ASSERT( !t.find( v1.nKey ));
 411                 CPPUNIT_ASSERT( !t.find( v1 ));
 412                 CPPUNIT_ASSERT( !t.unlink(v1));
 413                 CPPUNIT_ASSERT( t.find( v2.nKey ));
 414                 CPPUNIT_ASSERT( t.find( v2 ));
 415                 CPPUNIT_ASSERT( t.find( v3.nKey ));
 416                 CPPUNIT_ASSERT( t.find( v3 ));
 417                 CPPUNIT_ASSERT( t.find( v4.nKey ));
 418                 CPPUNIT_ASSERT( t.find( v4 ));
 419                 CPPUNIT_ASSERT( t.find( v5.nKey ));
 420                 CPPUNIT_ASSERT( t.find( v5 ));
 421                 CPPUNIT_ASSERT( !t.empty() );
 422                 CPPUNIT_ASSERT( misc::check_size( t, 4 ));
 423
 424                 ++v2.stat.nWaitingDispCount;
 425                 CPPUNIT_ASSERT( t.erase( v2.nKey ));
 426                 CPPUNIT_ASSERT( t.check_consistency() );
 427                 CPPUNIT_ASSERT( !t.find( v1.nKey ));
 428                 CPPUNIT_ASSERT( !t.find( v1 ));
 429                 CPPUNIT_ASSERT( !t.find( v2.nKey ));
 430                 CPPUNIT_ASSERT( !t.find( v2 ));
 431                 CPPUNIT_ASSERT( !t.erase(v2));
 432                 CPPUNIT_ASSERT( t.find( v3.nKey ));
 433                 CPPUNIT_ASSERT( t.find( v3 ));
 434                 CPPUNIT_ASSERT( t.find( v4.nKey ));
 435                 CPPUNIT_ASSERT( t.find( v4 ));
 436                 CPPUNIT_ASSERT( t.find( v5.nKey ));
 437                 CPPUNIT_ASSERT( t.find( v5 ));
 438                 CPPUNIT_ASSERT( !t.empty() );
 439                 CPPUNIT_ASSERT( misc::check_size( t, 3 ));
 440
 441                 ++v3.stat.nWaitingDispCount;
 442                 CPPUNIT_ASSERT( t.erase_with( v3.nKey, less<value_type>() ));
 443                 CPPUNIT_ASSERT( t.check_consistency() );
 444                 CPPUNIT_ASSERT( !t.find( v1.nKey ));
 445                 CPPUNIT_ASSERT( !t.find( v1 ));
 446                 CPPUNIT_ASSERT( !t.find( v2.nKey ));
 447                 CPPUNIT_ASSERT( !t.find( v2 ));
 448                 CPPUNIT_ASSERT( !t.find( v3.nKey ));
 449                 CPPUNIT_ASSERT( !t.find( v3 ));
 450                 CPPUNIT_ASSERT( !t.erase_with(v3, less<value_type>() ));
 451                 CPPUNIT_ASSERT( t.find( v4.nKey ));
 452                 CPPUNIT_ASSERT( t.find( v4 ));
 453                 CPPUNIT_ASSERT( t.find( v5.nKey ));
 454                 CPPUNIT_ASSERT( t.find( v5 ));
 455                 CPPUNIT_ASSERT( !t.empty() );
 456                 CPPUNIT_ASSERT( misc::check_size( t, 2 ));
 457
 458                 ++v4.stat.nWaitingDispCount;
 459                 CPPUNIT_ASSERT( v4.stat.nEraseFuncCall == 0 );
 460                 CPPUNIT_ASSERT( t.erase( v4.nKey, erase_functor() ));
 461                 CPPUNIT_ASSERT( t.check_consistency() );
 462                 CPPUNIT_ASSERT( v4.stat.nEraseFuncCall == 1 );
 463                 CPPUNIT_ASSERT( !t.find( v1.nKey ));
 464                 CPPUNIT_ASSERT( !t.find( v1 ));
 465                 CPPUNIT_ASSERT( !t.find( v2.nKey ));
 466                 CPPUNIT_ASSERT( !t.find( v2 ));
 467                 CPPUNIT_ASSERT( !t.find( v3.nKey ));
 468                 CPPUNIT_ASSERT( !t.find( v3 ));
 469                 CPPUNIT_ASSERT( !t.find( v4.nKey ));
 470                 CPPUNIT_ASSERT( !t.find( v4 ));
 471                 CPPUNIT_ASSERT( !t.erase( v4.nKey, erase_functor() ));
 472                 CPPUNIT_ASSERT( v4.stat.nEraseFuncCall == 1 );
 473                 CPPUNIT_ASSERT( t.find( v5.nKey ));
 474                 CPPUNIT_ASSERT( t.find( v5 ));
 475                 CPPUNIT_ASSERT( !t.empty() );
 476                 CPPUNIT_ASSERT( misc::check_size( t, 1 ));
 477
 478                 ++v5.stat.nWaitingDispCount;
 479                 CPPUNIT_ASSERT( t.erase_with( v5.nKey, less<value_type>(), erase_functor() ));
 480                 CPPUNIT_ASSERT( t.check_consistency() );
 481                 CPPUNIT_ASSERT( v5.stat.nEraseFuncCall == 1 );
 482                 CPPUNIT_ASSERT( !t.find( v1.nKey ));
 483                 CPPUNIT_ASSERT( !t.find( v1 ));
 484                 CPPUNIT_ASSERT( !t.find( v2.nKey ));
 485                 CPPUNIT_ASSERT( !t.find( v2 ));
 486                 CPPUNIT_ASSERT( !t.find( v3.nKey ));
 487                 CPPUNIT_ASSERT( !t.find( v3 ));
 488                 CPPUNIT_ASSERT( !t.erase_with(v5, less<value_type>(), erase_functor() ));
 489                 CPPUNIT_ASSERT( !t.find( v4.nKey ));
 490                 CPPUNIT_ASSERT( !t.find( v4 ));
 491                 CPPUNIT_ASSERT( !t.find( v5.nKey ));
 492                 CPPUNIT_ASSERT( !t.find( v5 ));
 493                 CPPUNIT_ASSERT( t.empty() );
 494                 CPPUNIT_ASSERT( misc::check_size( t, 0 ));
 495
 496                 tree_type::gc::force_dispose();
 497
 498                 // find
 499                 CPPUNIT_ASSERT( t.insert( v1 ));
 500                 CPPUNIT_ASSERT( t.insert( v2 ));
 501                 CPPUNIT_ASSERT( t.insert( v3 ));
 502                 CPPUNIT_ASSERT( t.insert( v4 ));
 503                 CPPUNIT_ASSERT( t.insert( v5 ));
 504                 CPPUNIT_ASSERT( t.check_consistency() );
 505                 CPPUNIT_ASSERT( !t.empty() );
 506                 CPPUNIT_ASSERT( misc::check_size( t, 5 ));
 507
 508                 CPPUNIT_ASSERT( t.find( 10 ));
 509                 CPPUNIT_ASSERT( !t.find( 11 ));
 510                 CPPUNIT_ASSERT( t.find( v1 ));
 511                 CPPUNIT_ASSERT( t.find( v2.nKey ));
 512                 CPPUNIT_ASSERT( t.find( v3 ));
 513                 CPPUNIT_ASSERT( t.find( v4.nKey ));
 514                 CPPUNIT_ASSERT( t.find( v5.nKey ));
 515
 516                 // find_with
 517                 CPPUNIT_ASSERT( t.find_with( 10, less<value_type>() ));
 518                 CPPUNIT_ASSERT( !t.find_with( wrapped_int(11), wrapped_less<value_type>() ));
 519                 CPPUNIT_ASSERT( t.find_with( v1, less<value_type>() ));
 520                 CPPUNIT_ASSERT( t.find_with( wrapped_int(v2.nKey), wrapped_less<value_type>() ));
 521                 CPPUNIT_ASSERT( t.find_with( v3, less<value_type>() ));
 522                 CPPUNIT_ASSERT( t.find_with( v4.nKey, less<value_type>() ));
 523                 CPPUNIT_ASSERT( t.find_with( v5.nKey, less<value_type>() ));
 524
 525                 // find<Func>
 526                 CPPUNIT_ASSERT( v1.stat.nFindFuncCall == 0 );
 527                 CPPUNIT_ASSERT( v1.stat.nFindConstFuncCall == 0 );
 528                 CPPUNIT_ASSERT( t.find( 10, find_functor() ));
 529                 CPPUNIT_ASSERT( v1.stat.nFindFuncCall == 0 );
 530                 CPPUNIT_ASSERT( v1.stat.nFindConstFuncCall == 1 );
 531
 532                 CPPUNIT_ASSERT( !t.find( 11, find_functor() ));
 533
 534                 CPPUNIT_ASSERT( t.find( v1, find_functor() ));
 535                 CPPUNIT_ASSERT( v1.stat.nFindFuncCall == 1 );
 536                 CPPUNIT_ASSERT( v1.stat.nFindConstFuncCall == 1 );
 537
 538                 CPPUNIT_ASSERT( v2.stat.nFindFuncCall == 0 );
 539                 CPPUNIT_ASSERT( v2.stat.nFindConstFuncCall == 0 );
 540                 CPPUNIT_ASSERT( t.find( v2.nKey, find_functor() ));
 541                 CPPUNIT_ASSERT( v2.stat.nFindFuncCall == 1 );
 542                 CPPUNIT_ASSERT( v2.stat.nFindConstFuncCall == 0 );
 543
 544                 CPPUNIT_ASSERT( v3.stat.nFindFuncCall == 0 );
 545                 CPPUNIT_ASSERT( v3.stat.nFindConstFuncCall == 0 );
 546                 CPPUNIT_ASSERT( t.find( v3, find_functor() ));
 547                 CPPUNIT_ASSERT( v3.stat.nFindFuncCall == 1 );
 548                 CPPUNIT_ASSERT( v3.stat.nFindConstFuncCall == 0 );
 549
 550                 CPPUNIT_ASSERT( v4.stat.nFindFuncCall == 0 );
 551                 CPPUNIT_ASSERT( v4.stat.nFindConstFuncCall == 0 );
 552                 CPPUNIT_ASSERT( t.find( (value_type const&) v4, find_functor() ));
 553                 CPPUNIT_ASSERT( v4.stat.nFindFuncCall == 0 );
 554                 CPPUNIT_ASSERT( v4.stat.nFindConstFuncCall == 1 );
 555
 556                 CPPUNIT_ASSERT( v5.stat.nFindFuncCall == 0 );
 557                 CPPUNIT_ASSERT( v5.stat.nFindConstFuncCall == 0 );
 558                 CPPUNIT_ASSERT( t.find( v5.nKey, find_functor() ));
 559                 CPPUNIT_ASSERT( v5.stat.nFindFuncCall == 1 );
 560                 CPPUNIT_ASSERT( v5.stat.nFindConstFuncCall == 0 );
 561
 562                 // find_with<Func>
 563                 CPPUNIT_ASSERT( v1.stat.nFindFuncCall == 1 );
 564                 CPPUNIT_ASSERT( v1.stat.nFindConstFuncCall == 1 );
 565                 CPPUNIT_ASSERT( t.find_with( 10, less<value_type>(), find_functor() ));
 566                 CPPUNIT_ASSERT( v1.stat.nFindFuncCall == 1 );
 567                 CPPUNIT_ASSERT( v1.stat.nFindConstFuncCall == 2 );
 568
 569                 CPPUNIT_ASSERT( !t.find_with( 11, less<value_type>(), find_functor() ));
 570
 571                 CPPUNIT_ASSERT( t.find_with( v1, less<value_type>(), find_functor() ));
 572                 CPPUNIT_ASSERT( v1.stat.nFindFuncCall == 2 );
 573                 CPPUNIT_ASSERT( v1.stat.nFindConstFuncCall == 2 );
 574
 575                 CPPUNIT_ASSERT( v2.stat.nFindFuncCall == 1 );
 576                 CPPUNIT_ASSERT( v2.stat.nFindConstFuncCall == 0 );
 577                 CPPUNIT_ASSERT( t.find_with( v2.nKey, less<value_type>(), find_functor() ));
 578                 CPPUNIT_ASSERT( v2.stat.nFindFuncCall == 2 );
 579                 CPPUNIT_ASSERT( v2.stat.nFindConstFuncCall == 0 );
 580
 581                 CPPUNIT_ASSERT( v3.stat.nFindFuncCall == 1 );
 582                 CPPUNIT_ASSERT( v3.stat.nFindConstFuncCall == 0 );
 583                 CPPUNIT_ASSERT( t.find_with( wrapped_int(v3.nKey), wrapped_less<value_type>(), find_functor() ));
 584                 CPPUNIT_ASSERT( v3.stat.nFindFuncCall == 1 );
 585                 CPPUNIT_ASSERT( v3.stat.nFindConstFuncCall == 1 );
 586
 587                 CPPUNIT_ASSERT( v4.stat.nFindFuncCall == 0 );
 588                 CPPUNIT_ASSERT( v4.stat.nFindConstFuncCall == 1 );
 589                 CPPUNIT_ASSERT( t.find_with( (value_type const&) v4, less<value_type>(), find_functor() ));
 590                 CPPUNIT_ASSERT( v4.stat.nFindFuncCall == 0 );
 591                 CPPUNIT_ASSERT( v4.stat.nFindConstFuncCall == 2 );
 592
 593                 CPPUNIT_ASSERT( v5.stat.nFindFuncCall == 1 );
 594                 CPPUNIT_ASSERT( v5.stat.nFindConstFuncCall == 0 );
 595                 CPPUNIT_ASSERT( t.find_with( v5.nKey, less<value_type>(), find_functor() ));
 596                 CPPUNIT_ASSERT( v5.stat.nFindFuncCall == 2 );
 597                 CPPUNIT_ASSERT( v5.stat.nFindConstFuncCall == 0 );
 598
 599                 CPPUNIT_ASSERT( t.check_consistency() );
 600                 t.clear();
 601                 CPPUNIT_ASSERT( t.check_consistency() );
 602                 CPPUNIT_ASSERT( t.empty() );
 603                 CPPUNIT_ASSERT( misc::check_size( t, 0 ));
 604
 605                 tree_type::gc::force_dispose();
 606                 CPPUNIT_CHECK_EX( v1.stat.nWaitingDispCount + 1 == v1.stat.nDisposeCount,
 607                     "v1.stat.nWaitingDispCount=" << v1.stat.nWaitingDispCount << ", v1.stat.nDisposeCount=" << v1.stat.nDisposeCount );
 608                 CPPUNIT_CHECK_EX( v2.stat.nWaitingDispCount + 1 == v2.stat.nDisposeCount,
 609                     "v2.stat.nWaitingDispCount=" << v2.stat.nWaitingDispCount << ", v2.stat.nDisposeCount=" << v2.stat.nDisposeCount );
 610                 CPPUNIT_CHECK_EX( v3.stat.nWaitingDispCount + 1 == v3.stat.nDisposeCount,
 611                     "v3.stat.nWaitingDispCount=" << v3.stat.nWaitingDispCount << ", v3.stat.nDisposeCount=" << v3.stat.nDisposeCount );
 612                 CPPUNIT_CHECK_EX( v4.stat.nWaitingDispCount + 1 == v4.stat.nDisposeCount,
 613                     "v4.stat.nWaitingDispCount=" << v4.stat.nWaitingDispCount << ", v4.stat.nDisposeCount=" << v4.stat.nDisposeCount );
 614                 CPPUNIT_CHECK_EX( v5.stat.nWaitingDispCount + 1 == v5.stat.nDisposeCount,
 615                     "v5.stat.nWaitingDispCount=" << v5.stat.nWaitingDispCount << ", v5.stat.nDisposeCount=" << v5.stat.nDisposeCount );
 616             }
 617
 618             {
 619                 data_array< value_type> arr;
 620                 value_type * pFirst = arr.begin();
 621                 value_type * pLast  = arr.end();
 622
 623                 for ( value_type * p = pFirst; p != pLast; ++p ) {
 624                     CPPUNIT_ASSERT( t.insert( *p ) );
 625                     CPPUNIT_ASSERT( !t.insert( *p ));
 626                 }
 627                 CPPUNIT_ASSERT( !t.empty() );
 628                 CPPUNIT_ASSERT( misc::check_size( t, c_nItemCount ));
 629                 CPPUNIT_ASSERT( t.check_consistency() );
 630
 631                 for ( int n = 0; n < (int) c_nItemCount; ++n ) {
 632                     CPPUNIT_ASSERT_MSG( t.find( n ), n );
 633                 }
 634                 for ( value_type * p = pFirst; p != pLast; ++p ) {
 635                     CPPUNIT_ASSERT( t.find( *p ));
 636                     CPPUNIT_ASSERT( t.find( p->nKey ));
 637                     CPPUNIT_ASSERT( t.unlink( *p ) );
 638                     CPPUNIT_ASSERT( !t.unlink( *p ) );
 639                     CPPUNIT_ASSERT( !t.find( p->nKey ));
 640                 }
 641
 642                 tree_type::gc::force_dispose();
 643             }
 644         }
 645
 646         template <class Tree, class PrintStat>
 647         void test()
 648         {
 649             typedef Tree tree_type;
 650             typedef typename tree_type::key_type     key_type;
 651             typedef typename tree_type::value_type   value_type;
 652
 653             tree_type t;
 654             test_common(t);
 655
 656             {
 657                 value_type v1( 10, 100 );
 658                 value_type v2( 20, 200 );
 659                 value_type v3( 30, 300 );
 660                 value_type v4( 25, 250 );
 661                 value_type v5( -50, -500 );
 662
 663                 // extract/extract_min/extract_max
 664                 CPPUNIT_ASSERT( t.insert( v1 ));
 665                 CPPUNIT_ASSERT( t.insert( v2 ));
 666                 CPPUNIT_ASSERT( t.insert( v3 ));
 667                 CPPUNIT_ASSERT( t.insert( v4 ));
 668                 CPPUNIT_ASSERT( t.insert( v5 ));
 669                 CPPUNIT_ASSERT( t.check_consistency() );
 670                 CPPUNIT_ASSERT( !t.empty() );
 671                 CPPUNIT_ASSERT( misc::check_size( t, 5 ));
 672
 673                 {
 674                     typename tree_type::guarded_ptr gp;
 675
 676                     CPPUNIT_ASSERT( t.get( gp, v2.nKey ));
 677                     CPPUNIT_ASSERT( !gp.empty());
 678                     CPPUNIT_CHECK( gp->nKey == v2.nKey );
 679                     gp.release();
 680                     CPPUNIT_ASSERT( t.extract( gp, v2.nKey ));
 681                     CPPUNIT_ASSERT( !gp.empty());
 682                     CPPUNIT_ASSERT( t.check_consistency() );
 683                     CPPUNIT_ASSERT( !t.empty() );
 684                     CPPUNIT_ASSERT( misc::check_size( t, 4 ));
 685                     CPPUNIT_ASSERT( gp->nKey == v2.nKey );
 686                     CPPUNIT_ASSERT( !t.extract( gp, v2.nKey ));
 687                     CPPUNIT_CHECK( !t.get( gp, v2.nKey ));
 688                     CPPUNIT_ASSERT( t.check_consistency() );
 689                     CPPUNIT_ASSERT( !t.empty() );
 690                     CPPUNIT_ASSERT( misc::check_size( t, 4 ));
 691
 692                     CPPUNIT_ASSERT( t.extract_min(gp));
 693                     CPPUNIT_ASSERT( !gp.empty());
 694                     CPPUNIT_ASSERT( t.check_consistency() );
 695                     CPPUNIT_ASSERT( !t.empty() );
 696                     CPPUNIT_ASSERT( misc::check_size( t, 3 ));
 697                     CPPUNIT_ASSERT( gp->nKey == v5.nKey );
 698
 699                     CPPUNIT_ASSERT( t.extract_min(gp));
 700                     CPPUNIT_ASSERT( t.check_consistency() );
 701                     CPPUNIT_ASSERT( !t.empty() );
 702                     CPPUNIT_ASSERT( misc::check_size( t, 2 ));
 703                     CPPUNIT_ASSERT( gp->nKey == v1.nKey );
 704
 705                     CPPUNIT_ASSERT( t.extract_min(gp));
 706                     CPPUNIT_ASSERT( t.check_consistency() );
 707                     CPPUNIT_ASSERT( !t.empty() );
 708                     CPPUNIT_ASSERT( misc::check_size( t, 1 ));
 709                     CPPUNIT_ASSERT( gp->nKey == v4.nKey );
 710
 711                     CPPUNIT_ASSERT( t.extract_min(gp));
 712                     CPPUNIT_ASSERT( t.check_consistency() );
 713                     CPPUNIT_ASSERT( t.empty() );
 714                     CPPUNIT_ASSERT( misc::check_size( t, 0 ));
 715                     CPPUNIT_ASSERT( gp->nKey == v3.nKey );
 716
 717                     CPPUNIT_ASSERT( !t.extract_min(gp));
 718                     CPPUNIT_ASSERT( !t.extract_max(gp));
 719                     CPPUNIT_ASSERT( !t.extract( gp, v1.nKey ));
 720                 }
 721
 722                 tree_type::gc::force_dispose();
 723
 724                 {
 725                     typename tree_type::guarded_ptr gp;
 726
 727                     CPPUNIT_ASSERT( t.insert( v1 ));
 728                     CPPUNIT_ASSERT( t.insert( v2 ));
 729                     CPPUNIT_ASSERT( t.insert( v3 ));
 730                     CPPUNIT_ASSERT( t.insert( v4 ));
 731                     CPPUNIT_ASSERT( t.insert( v5 ));
 732                     CPPUNIT_ASSERT( t.check_consistency() );
 733                     CPPUNIT_ASSERT( !t.empty() );
 734                     CPPUNIT_ASSERT( misc::check_size( t, 5 ));
 735
 736                     CPPUNIT_ASSERT( t.get_with( gp, wrapped_int(v4.nKey), wrapped_less<value_type>() ));
 737                     CPPUNIT_ASSERT( !gp.empty());
 738                     CPPUNIT_CHECK( gp->nKey == v4.nKey );
 739                     CPPUNIT_ASSERT( t.extract_with( gp, wrapped_int(v4.nKey), wrapped_less<value_type>() ));
 740                     CPPUNIT_ASSERT( t.check_consistency() );
 741                     CPPUNIT_ASSERT( !t.empty() );
 742                     CPPUNIT_ASSERT( misc::check_size( t, 4 ));
 743                     CPPUNIT_ASSERT( gp->nKey == v4.nKey );
 744
 745                     CPPUNIT_ASSERT( !t.extract_with( gp, v4.nKey, less<value_type>() ) );
 746                     CPPUNIT_ASSERT( t.check_consistency() );
 747                     CPPUNIT_ASSERT( !t.get_with( gp, v4.nKey, less<value_type>() ) );
 748
 749                     CPPUNIT_ASSERT( t.extract_max(gp));
 750                     CPPUNIT_ASSERT( t.check_consistency() );
 751                     CPPUNIT_ASSERT( !t.empty() );
 752                     CPPUNIT_ASSERT( misc::check_size( t, 3 ));
 753                     CPPUNIT_ASSERT( gp->nKey == v3.nKey );
 754
 755                     CPPUNIT_ASSERT( t.extract_max(gp) );
 756                     CPPUNIT_ASSERT( t.check_consistency() );
 757                     CPPUNIT_ASSERT( !t.empty() );
 758                     CPPUNIT_ASSERT( misc::check_size( t, 2 ));
 759                     CPPUNIT_ASSERT( gp->nKey == v2.nKey );
 760
 761                     CPPUNIT_ASSERT( t.extract_max(gp) );
 762                     CPPUNIT_ASSERT( t.check_consistency() );
 763                     CPPUNIT_ASSERT( !t.empty() );
 764                     CPPUNIT_ASSERT( misc::check_size( t, 1 ));
 765                     CPPUNIT_ASSERT( gp->nKey == v1.nKey );
 766
 767                     CPPUNIT_ASSERT( t.extract_max(gp) );
 768                     CPPUNIT_ASSERT( t.check_consistency() );
 769                     CPPUNIT_ASSERT( t.empty() );
 770                     CPPUNIT_ASSERT( misc::check_size( t, 0 ));
 771                     CPPUNIT_ASSERT( gp->nKey == v5.nKey );
 772                 }
 773
 774                 tree_type::gc::force_dispose();
 775             }
 776
 777             {
 778                 data_array< value_type> arr;
 779                 value_type * pFirst = arr.begin();
 780                 value_type * pLast  = arr.end();
 781
 782                 for ( value_type * p = pFirst; p != pLast; ++p ) {
 783                     CPPUNIT_ASSERT( t.ensure( *p, ensure_functor()).second );
 784                 }
 785                 for ( int n = 0; n < (int) c_nItemCount; ++n ) {
 786                     typename tree_type::guarded_ptr gp;
 787                     CPPUNIT_ASSERT( t.extract_min(gp));
 788                     CPPUNIT_ASSERT( !gp.empty());
 789                     CPPUNIT_CHECK( gp->nKey == n );
 790                 }
 791
 792                 for ( value_type * p = pFirst; p != pLast; ++p ) {
 793                     CPPUNIT_ASSERT( t.insert( *p ) );
 794                 }
 795                 for ( int n = (int) c_nItemCount - 1; n >= 0; --n ) {
 796                     typename tree_type::guarded_ptr gp;
 797                     CPPUNIT_ASSERT( t.extract_max(gp));
 798                     CPPUNIT_ASSERT( !gp.empty());
 799                     CPPUNIT_CHECK( gp->nKey == n );
 800                 }
 801
 802                 tree_type::gc::force_dispose();
 803             }
 804
 805             PrintStat()( t );
 806         }
 807
 808         template <class Tree, class PrintStat>
 809         void test_rcu()
 810         {
 811             typedef Tree tree_type;
 812             typedef typename tree_type::key_type     key_type;
 813             typedef typename tree_type::value_type   value_type;
 814
 815             tree_type t;
 816             test_common(t);
 817
 818             // extract/get
 819             {
 820                 value_type v1( 10, 100 );
 821                 value_type v2( 20, 200 );
 822                 value_type v3( 30, 300 );
 823                 value_type v4( 25, 250 );
 824                 value_type v5( -50, -500 );
 825
 826                 // extract/extract_min/extract_max
 827                 CPPUNIT_ASSERT( t.insert( v1 ));
 828                 CPPUNIT_ASSERT( t.insert( v2 ));
 829                 CPPUNIT_ASSERT( t.insert( v3 ));
 830                 CPPUNIT_ASSERT( t.insert( v4 ));
 831                 CPPUNIT_ASSERT( t.insert( v5 ));
 832                 CPPUNIT_ASSERT( t.check_consistency() );
 833                 CPPUNIT_ASSERT( !t.empty() );
 834                 CPPUNIT_ASSERT( misc::check_size( t, 5 ));
 835
 836                 typename tree_type::exempt_ptr  ep;
 837                 typename tree_type::value_type * pVal;
 838                 {
 839                     typename tree_type::rcu_lock l;
 840                     pVal = t.get( v1.nKey );
 841                     CPPUNIT_ASSERT( pVal != nullptr );
 842                     CPPUNIT_CHECK( pVal == &v1 );
 843                 }
 844                 ep = t.extract( v1.nKey );
 845                 CPPUNIT_ASSERT( !ep.empty());
 846                 CPPUNIT_CHECK( ep->nKey == v1.nKey );
 847                 {
 848                     typename tree_type::rcu_lock l;
 849                     CPPUNIT_CHECK( t.get( v1.nKey ) == nullptr );
 850                 }
 851                 ep.release();
 852                 ep = t.extract( v1.nKey );
 853                 CPPUNIT_ASSERT( ep.empty());
 854
 855                 ep = t.extract_min();
 856                 CPPUNIT_ASSERT( !ep.empty() );
 857                 CPPUNIT_CHECK( ep->nKey == v5.nKey );
 858                 {
 859                     typename tree_type::rcu_lock l;
 860                     CPPUNIT_CHECK( t.get( v5.nKey ) == nullptr );
 861                 }
 862
 863                 ep = t.extract( v5.nKey );
 864                 CPPUNIT_ASSERT( ep.empty() );
 865
 866                 ep = t.extract_max();
 867                 CPPUNIT_ASSERT( ep.empty());
 868                 CPPUNIT_CHECK( ep->nKey == v3.nKey );
 869                 {
 870                     typename tree_type::rcu_lock l;
 871                     CPPUNIT_CHECK( t.get( v3.nKey ) == nullptr );
 872                 }
 873                 ep.release();
 874
 875                 {
 876                     typename tree_type::rcu_lock l;
 877                     pVal = t.get_with( wrapped_int(v2.nKey), wrapped_less<value_type>() );
 878                     CPPUNIT_ASSERT( pVal != nullptr );
 879                     CPPUNIT_CHECK( pVal == &v2 );
 880                 }
 881                 ep = t.extract_with( wrapped_int( v2.nKey ), wrapped_less<value_type>() );
 882                 CPPUNIT_ASSERT( !ep.empty() );
 883                 CPPUNIT_CHECK( ep->nKey == v2.nKey );
 884                 {
 885                     typename tree_type::rcu_lock l;
 886                     CPPUNIT_CHECK( t.get_with( wrapped_int( v2.nKey ), wrapped_less<value_type>() ) == nullptr );
 887                 }
 888                 //ep.release();
 889                 ep = t.extract_with( wrapped_int( v2.nKey ), wrapped_less<value_type>() );
 890                 CPPUNIT_CHECK( ep.empty());
 891
 892                 ep = t.extract( v4.nKey );
 893                 CPPUNIT_ASSERT( ep );
 894                 CPPUNIT_CHECK( ep->nKey == v4.nKey );
 895                 ep.release();
 896
 897                 tree_type::gc::force_dispose();
 898
 899                 CPPUNIT_CHECK( t.empty());
 900                 CPPUNIT_ASSERT( misc::check_size( t, 0 ));
 901
 902                 {
 903                     typename tree_type::rcu_lock l;
 904                     CPPUNIT_CHECK( t.get( v1.nKey ) == nullptr );
 905                     CPPUNIT_CHECK( t.get( v2.nKey ) == nullptr );
 906                     CPPUNIT_CHECK( t.get( v3.nKey ) == nullptr );
 907                     CPPUNIT_CHECK( t.get( v4.nKey ) == nullptr );
 908                     CPPUNIT_CHECK( t.get( v5.nKey ) == nullptr );
 909                 }
 910
 911                 CPPUNIT_CHECK( !t.extract(v1.nKey));
 912                 CPPUNIT_CHECK( !t.extract(v2.nKey));
 913                 CPPUNIT_CHECK( !t.extract(v3.nKey));
 914                 CPPUNIT_CHECK( !t.extract(v4.nKey));
 915                 CPPUNIT_CHECK( !t.extract(v5.nKey));
 916
 917                 tree_type::gc::force_dispose();
 918             }
 919
 920             PrintStat()( t );
 921         }
 922
 923         void EllenBinTree_hp_base_less();
 924         void EllenBinTree_hp_base_cmp();
 925         void EllenBinTree_hp_base_cmpless();
 926         void EllenBinTree_hp_base_less_ic();
 927         void EllenBinTree_hp_base_cmp_ic();
 928         void EllenBinTree_hp_base_less_stat();
 929         void EllenBinTree_hp_base_cmp_ic_stat();
 930         void EllenBinTree_hp_base_cmp_ic_stat_yield();
 931         void EllenBinTree_hp_base_less_pool();
 932         void EllenBinTree_hp_base_less_pool_ic_stat();
 933
 934         void EllenBinTree_hp_member_less();
 935         void EllenBinTree_hp_member_cmp();
 936         void EllenBinTree_hp_member_cmpless();
 937         void EllenBinTree_hp_member_less_ic();
 938         void EllenBinTree_hp_member_cmp_ic();
 939         void EllenBinTree_hp_member_less_stat();
 940         void EllenBinTree_hp_member_cmp_ic_stat();
 941         void EllenBinTree_hp_member_cmp_ic_stat_yield();
 942         void EllenBinTree_hp_member_less_pool();
 943         void EllenBinTree_hp_member_less_pool_ic_stat();
 944
 945         void EllenBinTree_dhp_base_less();
 946         void EllenBinTree_dhp_base_cmp();
 947         void EllenBinTree_dhp_base_cmpless();
 948         void EllenBinTree_dhp_base_less_ic();
 949         void EllenBinTree_dhp_base_cmp_ic();
 950         void EllenBinTree_dhp_base_less_stat();
 951         void EllenBinTree_dhp_base_cmp_ic_stat();
 952         void EllenBinTree_dhp_base_cmp_ic_stat_yield();
 953         void EllenBinTree_dhp_base_less_pool();
 954         void EllenBinTree_dhp_base_less_pool_ic_stat();
 955
 956         void EllenBinTree_dhp_member_less();
 957         void EllenBinTree_dhp_member_cmp();
 958         void EllenBinTree_dhp_member_cmpless();
 959         void EllenBinTree_dhp_member_less_ic();
 960         void EllenBinTree_dhp_member_cmp_ic();
 961         void EllenBinTree_dhp_member_less_stat();
 962         void EllenBinTree_dhp_member_cmp_ic_stat();
 963         void EllenBinTree_dhp_member_cmp_ic_stat_yield();
 964         void EllenBinTree_dhp_member_less_pool();
 965         void EllenBinTree_dhp_member_less_pool_ic_stat();
 966
 967         void EllenBinTree_rcu_gpi_base_less();
 968         void EllenBinTree_rcu_gpi_base_cmp();
 969         void EllenBinTree_rcu_gpi_base_cmpless();
 970         void EllenBinTree_rcu_gpi_base_less_ic();
 971         void EllenBinTree_rcu_gpi_base_cmp_ic();
 972         void EllenBinTree_rcu_gpi_base_less_stat();
 973         void EllenBinTree_rcu_gpi_base_cmp_ic_stat();
 974         void EllenBinTree_rcu_gpi_base_cmp_ic_stat_yield();
 975         void EllenBinTree_rcu_gpi_base_less_pool();
 976         void EllenBinTree_rcu_gpi_base_less_pool_ic_stat();
 977
 978         void EllenBinTree_rcu_gpi_member_less();
 979         void EllenBinTree_rcu_gpi_member_cmp();
 980         void EllenBinTree_rcu_gpi_member_cmpless();
 981         void EllenBinTree_rcu_gpi_member_less_ic();
 982         void EllenBinTree_rcu_gpi_member_cmp_ic();
 983         void EllenBinTree_rcu_gpi_member_less_stat();
 984         void EllenBinTree_rcu_gpi_member_cmp_ic_stat();
 985         void EllenBinTree_rcu_gpi_member_cmp_ic_stat_yield();
 986         void EllenBinTree_rcu_gpi_member_less_pool();
 987         void EllenBinTree_rcu_gpi_member_less_pool_ic_stat();
 988
 989         void EllenBinTree_rcu_gpb_base_less();
 990         void EllenBinTree_rcu_gpb_base_cmp();
 991         void EllenBinTree_rcu_gpb_base_cmpless();
 992         void EllenBinTree_rcu_gpb_base_less_ic();
 993         void EllenBinTree_rcu_gpb_base_cmp_ic();
 994         void EllenBinTree_rcu_gpb_base_less_stat();
 995         void EllenBinTree_rcu_gpb_base_cmp_ic_stat();
 996         void EllenBinTree_rcu_gpb_base_cmp_ic_stat_yield();
 997         void EllenBinTree_rcu_gpb_base_less_pool();
 998         void EllenBinTree_rcu_gpb_base_less_pool_ic_stat();
 999
1000         void EllenBinTree_rcu_gpb_member_less();
1001         void EllenBinTree_rcu_gpb_member_cmp();
1002         void EllenBinTree_rcu_gpb_member_cmpless();
1003         void EllenBinTree_rcu_gpb_member_less_ic();
1004         void EllenBinTree_rcu_gpb_member_cmp_ic();
1005         void EllenBinTree_rcu_gpb_member_less_stat();
1006         void EllenBinTree_rcu_gpb_member_cmp_ic_stat();
1007         void EllenBinTree_rcu_gpb_member_cmp_ic_stat_yield();
1008         void EllenBinTree_rcu_gpb_member_less_pool();
1009         void EllenBinTree_rcu_gpb_member_less_pool_ic_stat();
1010
1011         void EllenBinTree_rcu_gpt_base_less();
1012         void EllenBinTree_rcu_gpt_base_cmp();
1013         void EllenBinTree_rcu_gpt_base_cmpless();
1014         void EllenBinTree_rcu_gpt_base_less_ic();
1015         void EllenBinTree_rcu_gpt_base_cmp_ic();
1016         void EllenBinTree_rcu_gpt_base_less_stat();
1017         void EllenBinTree_rcu_gpt_base_cmp_ic_stat();
1018         void EllenBinTree_rcu_gpt_base_cmp_ic_stat_yield();
1019         void EllenBinTree_rcu_gpt_base_less_pool();
1020         void EllenBinTree_rcu_gpt_base_less_pool_ic_stat();
1021
1022         void EllenBinTree_rcu_gpt_member_less();
1023         void EllenBinTree_rcu_gpt_member_cmp();
1024         void EllenBinTree_rcu_gpt_member_cmpless();
1025         void EllenBinTree_rcu_gpt_member_less_ic();
1026         void EllenBinTree_rcu_gpt_member_cmp_ic();
1027         void EllenBinTree_rcu_gpt_member_less_stat();
1028         void EllenBinTree_rcu_gpt_member_cmp_ic_stat();
1029         void EllenBinTree_rcu_gpt_member_cmp_ic_stat_yield();
1030         void EllenBinTree_rcu_gpt_member_less_pool();
1031         void EllenBinTree_rcu_gpt_member_less_pool_ic_stat();
1032
1033         void EllenBinTree_rcu_shb_base_less();
1034         void EllenBinTree_rcu_shb_base_cmp();
1035         void EllenBinTree_rcu_shb_base_cmpless();
1036         void EllenBinTree_rcu_shb_base_less_ic();
1037         void EllenBinTree_rcu_shb_base_cmp_ic();
1038         void EllenBinTree_rcu_shb_base_less_stat();
1039         void EllenBinTree_rcu_shb_base_cmp_ic_stat();
1040         void EllenBinTree_rcu_shb_base_cmp_ic_stat_yield();
1041         void EllenBinTree_rcu_shb_base_less_pool();
1042         void EllenBinTree_rcu_shb_base_less_pool_ic_stat();
1043
1044         void EllenBinTree_rcu_shb_member_less();
1045         void EllenBinTree_rcu_shb_member_cmp();
1046         void EllenBinTree_rcu_shb_member_cmpless();
1047         void EllenBinTree_rcu_shb_member_less_ic();
1048         void EllenBinTree_rcu_shb_member_cmp_ic();
1049         void EllenBinTree_rcu_shb_member_less_stat();
1050         void EllenBinTree_rcu_shb_member_cmp_ic_stat();
1051         void EllenBinTree_rcu_shb_member_cmp_ic_stat_yield();
1052         void EllenBinTree_rcu_shb_member_less_pool();
1053         void EllenBinTree_rcu_shb_member_less_pool_ic_stat();
1054
1055         void EllenBinTree_rcu_sht_base_less();
1056         void EllenBinTree_rcu_sht_base_cmp();
1057         void EllenBinTree_rcu_sht_base_cmpless();
1058         void EllenBinTree_rcu_sht_base_less_ic();
1059         void EllenBinTree_rcu_sht_base_cmp_ic();
1060         void EllenBinTree_rcu_sht_base_less_stat();
1061         void EllenBinTree_rcu_sht_base_cmp_ic_stat();
1062         void EllenBinTree_rcu_sht_base_cmp_ic_stat_yield();
1063         void EllenBinTree_rcu_sht_base_less_pool();
1064         void EllenBinTree_rcu_sht_base_less_pool_ic_stat();
1065
1066         void EllenBinTree_rcu_sht_member_less();
1067         void EllenBinTree_rcu_sht_member_cmp();
1068         void EllenBinTree_rcu_sht_member_cmpless();
1069         void EllenBinTree_rcu_sht_member_less_ic();
1070         void EllenBinTree_rcu_sht_member_cmp_ic();
1071         void EllenBinTree_rcu_sht_member_less_stat();
1072         void EllenBinTree_rcu_sht_member_cmp_ic_stat();
1073         void EllenBinTree_rcu_sht_member_cmp_ic_stat_yield();
1074         void EllenBinTree_rcu_sht_member_less_pool();
1075         void EllenBinTree_rcu_sht_member_less_pool_ic_stat();
1076
1077         CPPUNIT_TEST_SUITE(IntrusiveBinTreeHdrTest)
1078             CPPUNIT_TEST(EllenBinTree_hp_base_less)
1079             CPPUNIT_TEST(EllenBinTree_hp_base_cmp)
1080             CPPUNIT_TEST(EllenBinTree_hp_base_less_stat)
1081             CPPUNIT_TEST(EllenBinTree_hp_base_cmpless)
1082             CPPUNIT_TEST(EllenBinTree_hp_base_less_ic)
1083             CPPUNIT_TEST(EllenBinTree_hp_base_cmp_ic)
1084             CPPUNIT_TEST(EllenBinTree_hp_base_cmp_ic_stat)
1085             CPPUNIT_TEST( EllenBinTree_hp_base_cmp_ic_stat_yield )
1086             CPPUNIT_TEST( EllenBinTree_hp_base_less_pool )
1087             CPPUNIT_TEST(EllenBinTree_hp_base_less_pool_ic_stat)
1088
1089             CPPUNIT_TEST(EllenBinTree_hp_member_less)
1090             CPPUNIT_TEST(EllenBinTree_hp_member_cmp)
1091             CPPUNIT_TEST(EllenBinTree_hp_member_less_stat)
1092             CPPUNIT_TEST(EllenBinTree_hp_member_cmpless)
1093             CPPUNIT_TEST(EllenBinTree_hp_member_less_ic)
1094             CPPUNIT_TEST(EllenBinTree_hp_member_cmp_ic)
1095             CPPUNIT_TEST( EllenBinTree_hp_member_cmp_ic_stat )
1096             CPPUNIT_TEST( EllenBinTree_hp_member_cmp_ic_stat_yield )
1097             CPPUNIT_TEST(EllenBinTree_hp_member_less_pool)
1098             CPPUNIT_TEST(EllenBinTree_hp_member_less_pool_ic_stat)
1099
1100             CPPUNIT_TEST(EllenBinTree_dhp_base_less)
1101             CPPUNIT_TEST(EllenBinTree_dhp_base_cmp)
1102             CPPUNIT_TEST(EllenBinTree_dhp_base_less_stat)
1103             CPPUNIT_TEST(EllenBinTree_dhp_base_cmpless)
1104             CPPUNIT_TEST(EllenBinTree_dhp_base_less_ic)
1105             CPPUNIT_TEST(EllenBinTree_dhp_base_cmp_ic)
1106             CPPUNIT_TEST(EllenBinTree_dhp_base_cmp_ic_stat)
1107             CPPUNIT_TEST( EllenBinTree_dhp_base_cmp_ic_stat_yield )
1108             CPPUNIT_TEST( EllenBinTree_dhp_base_less_pool )
1109             CPPUNIT_TEST(EllenBinTree_dhp_base_less_pool_ic_stat)
1110
1111             CPPUNIT_TEST(EllenBinTree_dhp_member_less)
1112             CPPUNIT_TEST(EllenBinTree_dhp_member_cmp)
1113             CPPUNIT_TEST(EllenBinTree_dhp_member_less_stat)
1114             CPPUNIT_TEST(EllenBinTree_dhp_member_cmpless)
1115             CPPUNIT_TEST(EllenBinTree_dhp_member_less_ic)
1116             CPPUNIT_TEST(EllenBinTree_dhp_member_cmp_ic)
1117             CPPUNIT_TEST(EllenBinTree_dhp_member_cmp_ic_stat)
1118             CPPUNIT_TEST( EllenBinTree_dhp_member_cmp_ic_stat_yield )
1119             CPPUNIT_TEST( EllenBinTree_dhp_member_less_pool )
1120             CPPUNIT_TEST(EllenBinTree_dhp_member_less_pool_ic_stat)
1121
1122             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_less)
1123             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_cmp)
1124             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_less_stat)
1125             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_cmpless)
1126             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_less_ic)
1127             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_cmp_ic)
1128             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_cmp_ic_stat)
1129             CPPUNIT_TEST( EllenBinTree_rcu_gpi_base_cmp_ic_stat_yield )
1130             CPPUNIT_TEST( EllenBinTree_rcu_gpi_base_less_pool )
1131             CPPUNIT_TEST(EllenBinTree_rcu_gpi_base_less_pool_ic_stat)
1132
1133             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_less)
1134             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_cmp)
1135             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_less_stat)
1136             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_cmpless)
1137             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_less_ic)
1138             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_cmp_ic)
1139             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_cmp_ic_stat)
1140             CPPUNIT_TEST( EllenBinTree_rcu_gpi_member_cmp_ic_stat_yield )
1141             CPPUNIT_TEST( EllenBinTree_rcu_gpi_member_less_pool )
1142             CPPUNIT_TEST(EllenBinTree_rcu_gpi_member_less_pool_ic_stat)
1143
1144             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_less)
1145             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_cmp)
1146             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_less_stat)
1147             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_cmpless)
1148             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_less_ic)
1149             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_cmp_ic)
1150             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_cmp_ic_stat)
1151             CPPUNIT_TEST( EllenBinTree_rcu_gpb_base_cmp_ic_stat_yield )
1152             CPPUNIT_TEST( EllenBinTree_rcu_gpb_base_less_pool )
1153             CPPUNIT_TEST(EllenBinTree_rcu_gpb_base_less_pool_ic_stat)
1154
1155             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_less)
1156             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_cmp)
1157             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_less_stat)
1158             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_cmpless)
1159             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_less_ic)
1160             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_cmp_ic)
1161             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_cmp_ic_stat)
1162             CPPUNIT_TEST( EllenBinTree_rcu_gpb_member_cmp_ic_stat_yield )
1163             CPPUNIT_TEST( EllenBinTree_rcu_gpb_member_less_pool )
1164             CPPUNIT_TEST(EllenBinTree_rcu_gpb_member_less_pool_ic_stat)
1165
1166             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_less)
1167             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_cmp)
1168             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_less_stat)
1169             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_cmpless)
1170             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_less_ic)
1171             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_cmp_ic)
1172             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_cmp_ic_stat)
1173             CPPUNIT_TEST( EllenBinTree_rcu_gpt_base_cmp_ic_stat_yield )
1174             CPPUNIT_TEST( EllenBinTree_rcu_gpt_base_less_pool )
1175             CPPUNIT_TEST(EllenBinTree_rcu_gpt_base_less_pool_ic_stat)
1176
1177             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_less)
1178             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_cmp)
1179             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_less_stat)
1180             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_cmpless)
1181             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_less_ic)
1182             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_cmp_ic)
1183             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_cmp_ic_stat)
1184             CPPUNIT_TEST( EllenBinTree_rcu_gpt_member_cmp_ic_stat_yield )
1185             CPPUNIT_TEST( EllenBinTree_rcu_gpt_member_less_pool )
1186             CPPUNIT_TEST(EllenBinTree_rcu_gpt_member_less_pool_ic_stat)
1187
1188             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_less)
1189             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_cmp)
1190             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_less_stat)
1191             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_cmpless)
1192             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_less_ic)
1193             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_cmp_ic)
1194             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_cmp_ic_stat)
1195             CPPUNIT_TEST( EllenBinTree_rcu_shb_base_cmp_ic_stat_yield )
1196             CPPUNIT_TEST( EllenBinTree_rcu_shb_base_less_pool )
1197             CPPUNIT_TEST(EllenBinTree_rcu_shb_base_less_pool_ic_stat)
1198
1199             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_less)
1200             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_cmp)
1201             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_less_stat)
1202             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_cmpless)
1203             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_less_ic)
1204             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_cmp_ic)
1205             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_cmp_ic_stat)
1206             CPPUNIT_TEST( EllenBinTree_rcu_shb_member_cmp_ic_stat_yield )
1207             CPPUNIT_TEST( EllenBinTree_rcu_shb_member_less_pool )
1208             CPPUNIT_TEST(EllenBinTree_rcu_shb_member_less_pool_ic_stat)
1209
1210             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_less)
1211             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_cmp)
1212             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_less_stat)
1213             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_cmpless)
1214             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_less_ic)
1215             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_cmp_ic)
1216             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_cmp_ic_stat)
1217             CPPUNIT_TEST( EllenBinTree_rcu_sht_base_cmp_ic_stat_yield )
1218             CPPUNIT_TEST( EllenBinTree_rcu_sht_base_less_pool )
1219             CPPUNIT_TEST(EllenBinTree_rcu_sht_base_less_pool_ic_stat)
1220
1221             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_less)
1222             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_cmp)
1223             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_less_stat)
1224             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_cmpless)
1225             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_less_ic)
1226             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_cmp_ic)
1227             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_cmp_ic_stat)
1228             CPPUNIT_TEST( EllenBinTree_rcu_sht_member_cmp_ic_stat_yield )
1229             CPPUNIT_TEST( EllenBinTree_rcu_sht_member_less_pool )
1230             CPPUNIT_TEST(EllenBinTree_rcu_sht_member_less_pool_ic_stat)
1231
1232         CPPUNIT_TEST_SUITE_END()
1233     };
1234 } // namespace tree
1235
1236 #endif // #ifndef CDSHDRTEST_INTRUSIVE_BINTREE_H