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