tests/test-hdr/tree/hdr_intrusive_bintree.h

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