tests/test-hdr/tree/hdr_bronson_avltree_map.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSTEST_HDR_BRONSON_AVLTREE_MAP_H
   4 #define CDSTEST_HDR_BRONSON_AVLTREE_MAP_H
   5
   6 #include "cppunit/cppunit_proxy.h"
   7 #include "size_check.h"
   8 #include <functional>   // ref
   9 #include <algorithm>
  10
  11 namespace tree {
  12     using misc::check_size;
  13
  14     class BronsonAVLTreeHdrTest : public CppUnitMini::TestCase
  15     {
  16     public:
  17         typedef int     key_type;
  18
  19         struct stat_data {
  20             size_t  nInsertFuncCall;
  21             size_t  nEnsureExistFuncCall;
  22             size_t  nEnsureNewFuncCall;
  23             size_t  nEraseFuncCall;
  24             size_t  nFindFuncCall;
  25
  26             stat_data()
  27                 : nInsertFuncCall( 0 )
  28                 , nEnsureExistFuncCall( 0 )
  29                 , nEnsureNewFuncCall( 0 )
  30                 , nEraseFuncCall( 0 )
  31                 , nFindFuncCall( 0 )
  32             {}
  33         };
  34
  35         struct value_type {
  36             int         nVal;
  37             stat_data   stat;
  38
  39             value_type()
  40                 : nVal(0)
  41             {}
  42
  43             value_type( int v )
  44                 : nVal( v )
  45             {}
  46         };
  47
  48         struct compare {
  49             int operator()( key_type k1, key_type k2 )
  50             {
  51                 return k1 < k2 ? -1 : k1 > k2 ? 1 : 0;
  52             }
  53         };
  54
  55         struct wrapped_int {
  56             int  nKey;
  57
  58             wrapped_int( int n )
  59                 : nKey( n )
  60             {}
  61         };
  62
  63         struct wrapped_less
  64         {
  65             bool operator()( wrapped_int const& w, int n ) const
  66             {
  67                 return w.nKey < n;
  68             }
  69             bool operator()( int n, wrapped_int const& w ) const
  70             {
  71                 return n < w.nKey;
  72             }
  73             template <typename T>
  74             bool operator()( wrapped_int const& w, T const& v ) const
  75             {
  76                 return w.nKey < v.nKey;
  77             }
  78             template <typename T>
  79             bool operator()( T const& v, wrapped_int const& w ) const
  80             {
  81                 return v.nKey < w.nKey;
  82             }
  83         };
  84
  85     protected:
  86         static const size_t c_nItemCount = 10000;
  87
  88         struct find_functor
  89         {
  90             void operator()( key_type, value_type& v ) const
  91             {
  92                 ++v.stat.nFindFuncCall;
  93             }
  94         };
  95
  96         template <typename Item>
  97         struct copy_found
  98         {
  99             Item    m_found;
 100
 101             void operator()( key_type const&, Item& v )
 102             {
 103                 m_found = v;
 104             }
 105
 106             void operator()( Item& v )
 107             {
 108                 m_found = v;
 109             }
 110         };
 111
 112         struct insert_functor
 113         {
 114             template <typename Item>
 115             void operator()( key_type key, Item& i )
 116             {
 117                 i.nVal = key * 100;
 118                 ++i.stat.nInsertFuncCall;
 119             }
 120         };
 121
 122         template <typename Q>
 123         static void ensure_func( bool bNew, Q key, value_type& i )
 124         {
 125             i.nVal = key * 100;
 126             if ( bNew )
 127                 ++i.stat.nEnsureNewFuncCall;
 128             else
 129                 ++i.stat.nEnsureExistFuncCall;
 130         }
 131
 132         struct ensure_functor
 133         {
 134             template <typename Q>
 135             void operator()( bool bNew, Q key, value_type& i )
 136             {
 137                 ensure_func( bNew, key, i );
 138             }
 139         };
 140
 141         struct check_functor
 142         {
 143             void operator()( size_t nLevel, size_t hLeft, size_t hRight )
 144             {
 145                 CPPUNIT_MSG("Consistency violation: level=" << nLevel << ", hLeft=" << hLeft << ", hRight=" << hRight );
 146             }
 147         };
 148
 149     protected:
 150         template <class Set>
 151         void test_with( Set& s )
 152         {
 153             value_type itm;
 154             int key;
 155             typedef typename Set::exempt_ptr exempt_ptr;
 156
 157             // insert/find test
 158             CPPUNIT_ASSERT( !s.find( 10 ) );
 159             CPPUNIT_ASSERT( s.insert( 10 ) );
 160             CPPUNIT_ASSERT( !s.empty() );
 161             CPPUNIT_ASSERT( check_size( s, 1 ) );
 162             CPPUNIT_ASSERT( s.find( 10 ) );
 163
 164             CPPUNIT_ASSERT( !s.insert( 10 ) );
 165             CPPUNIT_ASSERT( !s.empty() );
 166             CPPUNIT_ASSERT( check_size( s, 1 ) );
 167
 168             CPPUNIT_ASSERT( !s.find_with( 20, std::less<key_type>() ) );
 169             CPPUNIT_ASSERT( s.insert( 20, 25 ) );
 170             CPPUNIT_ASSERT( !s.empty() );
 171             CPPUNIT_ASSERT( check_size( s, 2 ) );
 172             CPPUNIT_ASSERT( s.find_with( 10, std::less<key_type>() ) );
 173             CPPUNIT_ASSERT( s.find( key = 20 ) );
 174             CPPUNIT_ASSERT( s.find_with( key, std::less<key_type>(), find_functor() ) );
 175             {
 176                 copy_found<value_type> f;
 177                 key = 20;
 178                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 179                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 180                 CPPUNIT_ASSERT( f.m_found.stat.nFindFuncCall == 1 );
 181             }
 182             CPPUNIT_ASSERT( s.find( key, find_functor() ) );
 183             {
 184                 copy_found<value_type> f;
 185                 key = 20;
 186                 CPPUNIT_ASSERT( s.find_with( key, std::less<key_type>(), std::ref( f ) ) );
 187                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 188                 CPPUNIT_ASSERT( f.m_found.stat.nFindFuncCall == 2 );
 189             }
 190             CPPUNIT_ASSERT( s.find( 20, find_functor() ) );
 191             {
 192                 copy_found<value_type> f;
 193                 CPPUNIT_ASSERT( s.find_with( 20, std::less<key_type>(), std::ref( f ) ) );
 194                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 195                 CPPUNIT_ASSERT( f.m_found.stat.nFindFuncCall == 3 );
 196             }
 197
 198             CPPUNIT_ASSERT( !s.empty() );
 199             CPPUNIT_ASSERT( check_size( s, 2 ) );
 200
 201             CPPUNIT_ASSERT( !s.find( 25 ) );
 202             CPPUNIT_ASSERT( s.insert_with( 25, insert_functor() ) );
 203             CPPUNIT_ASSERT( !s.empty() );
 204             CPPUNIT_ASSERT( check_size( s, 3 ) );
 205             {
 206                 copy_found<value_type> f;
 207                 key = 25;
 208                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 209                 CPPUNIT_ASSERT( f.m_found.nVal == 2500 );
 210                 CPPUNIT_ASSERT( f.m_found.stat.nInsertFuncCall == 1 );
 211             }
 212
 213             // update test
 214             key = 10;
 215             {
 216                 copy_found<value_type> f;
 217                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 218                 CPPUNIT_ASSERT( f.m_found.nVal == 0 );
 219                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureExistFuncCall == 0 );
 220                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureNewFuncCall == 0 );
 221             }
 222             std::pair<bool, bool> ensureResult = s.update( key, ensure_functor() );
 223             CPPUNIT_ASSERT( ensureResult.first && !ensureResult.second );
 224             CPPUNIT_ASSERT( !s.empty() );
 225             CPPUNIT_ASSERT( check_size( s, 3 ) );
 226             {
 227                 copy_found<value_type> f;
 228                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 229                 CPPUNIT_ASSERT( f.m_found.nVal == 1000 );
 230                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureExistFuncCall == 1 );
 231                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureNewFuncCall == 0 );
 232             }
 233
 234             ensureResult = s.update( 13, []( bool /*bNew*/, key_type key, value_type& v )
 235                 {
 236                     v.nVal = key * 1000;
 237                     ++v.stat.nEnsureNewFuncCall;
 238                 });
 239             CPPUNIT_ASSERT( ensureResult.first && ensureResult.second );
 240             CPPUNIT_ASSERT( !s.empty() );
 241             CPPUNIT_ASSERT( check_size( s, 4 ) );
 242             {
 243                 copy_found<value_type> f;
 244                 key = 13;
 245                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 246                 CPPUNIT_ASSERT( f.m_found.nVal == 13000 );
 247                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureExistFuncCall == 0 );
 248                 CPPUNIT_ASSERT( f.m_found.stat.nEnsureNewFuncCall == 1 );
 249             }
 250
 251             // erase test
 252             CPPUNIT_ASSERT( s.erase( 13 ) );
 253             CPPUNIT_ASSERT( !s.find( 13 ) );
 254             CPPUNIT_ASSERT( !s.empty() );
 255             CPPUNIT_ASSERT( check_size( s, 3 ) );
 256             CPPUNIT_ASSERT( !s.erase( 13 ) );
 257             CPPUNIT_ASSERT( !s.empty() );
 258             CPPUNIT_ASSERT( check_size( s, 3 ) );
 259
 260             CPPUNIT_ASSERT( s.find( 10 ) );
 261             CPPUNIT_ASSERT( s.erase_with( 10, std::less<key_type>() ) );
 262             CPPUNIT_ASSERT( !s.find( 10 ) );
 263             CPPUNIT_ASSERT( !s.empty() );
 264             CPPUNIT_ASSERT( check_size( s, 2 ) );
 265             CPPUNIT_ASSERT( !s.erase_with( 10, std::less<key_type>() ) );
 266             CPPUNIT_ASSERT( !s.empty() );
 267             CPPUNIT_ASSERT( check_size( s, 2 ) );
 268
 269             CPPUNIT_ASSERT( s.find( 20 ) );
 270             {
 271                 copy_found<value_type> f;
 272                 CPPUNIT_ASSERT( s.erase( 20, std::ref( f ) ) );
 273                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 274
 275                 CPPUNIT_ASSERT( s.insert( 235, 2350 ) );
 276                 CPPUNIT_ASSERT( s.erase_with( 235, std::less<key_type>(), std::ref( f ) ) );
 277                 CPPUNIT_ASSERT( f.m_found.nVal == 2350 );
 278             }
 279             CPPUNIT_ASSERT( !s.find( 20 ) );
 280             CPPUNIT_ASSERT( !s.empty() );
 281             CPPUNIT_ASSERT( check_size( s, 1 ) );
 282
 283             s.clear();
 284             CPPUNIT_ASSERT( s.empty() );
 285             CPPUNIT_ASSERT( check_size( s, 0 ) );
 286
 287             // emplace test
 288             CPPUNIT_ASSERT( s.emplace( 151 ) );  // key = 151, val=0
 289             CPPUNIT_ASSERT( s.emplace( 174, 471 ) );    // key = 174, val = 471
 290             CPPUNIT_ASSERT( !s.empty() );
 291             CPPUNIT_ASSERT( check_size( s, 2 ) );
 292
 293             CPPUNIT_ASSERT( s.find( 151 ) );
 294             CPPUNIT_ASSERT( s.find_with( 174, std::less<key_type>() ) );
 295             CPPUNIT_ASSERT( !s.find( 190 ) );
 296
 297             {
 298                 copy_found<value_type> f;
 299                 key = 151;
 300                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 301                 CPPUNIT_ASSERT( f.m_found.nVal == 0 );
 302
 303                 key = 174;
 304                 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
 305                 CPPUNIT_ASSERT( f.m_found.nVal == 471 );
 306             }
 307
 308             s.clear();
 309             CPPUNIT_ASSERT( s.empty() );
 310             CPPUNIT_ASSERT( check_size( s, 0 ) );
 311
 312             const int c_nStep = 10;
 313             int keys[1000];
 314             for ( key_type i = 0; i < static_cast<key_type>(sizeof(keys) / sizeof(keys[0])); ++i )
 315                 keys[i] = i;
 316             shuffle( keys, keys + sizeof(keys) / sizeof(keys[0]));
 317
 318             size_t nCount = 1;
 319             int nPrev;
 320             key_type keyPrev;
 321             exempt_ptr xp;
 322
 323             // extract_min
 324             for ( int i = 0; i < static_cast<int>(sizeof(keys) / sizeof(keys[0])); ++i )
 325                 CPPUNIT_ASSERT( s.emplace( keys[i], keys[i] * c_nStep ));
 326             CPPUNIT_CHECK( s.check_consistency( check_functor() ));
 327
 328             xp = s.extract_min();
 329             CPPUNIT_ASSERT( xp );
 330             nPrev = xp->nVal;
 331             CPPUNIT_CHECK_EX( nPrev == 0, "Expected=0 real=" << nPrev );
 332             while ( !s.empty() ) {
 333                 xp = s.extract_min();
 334                 CPPUNIT_ASSERT( xp );
 335                 CPPUNIT_CHECK_EX( nPrev + c_nStep == xp->nVal, "Expected=" << nPrev + c_nStep << " real=" << xp->nVal );
 336                 nPrev = xp->nVal;
 337                 ++nCount;
 338             }
 339             CPPUNIT_CHECK( nCount == sizeof(keys) / sizeof(keys[0]));
 340
 341             // extract_min<Func>
 342             for ( int i = 0; i < static_cast<int>(sizeof(keys) / sizeof(keys[0])); ++i )
 343                 CPPUNIT_ASSERT( s.insert( keys[i], keys[i] * c_nStep ));
 344             CPPUNIT_CHECK( s.check_consistency( check_functor() ));
 345
 346             nCount = 1;
 347             xp = s.extract_min( [&keyPrev]( key_type k ){ keyPrev = k; });
 348             CPPUNIT_ASSERT( xp );
 349             nPrev = xp->nVal;
 350             CPPUNIT_CHECK_EX( keyPrev == 0, "Expected=0 real=" << keyPrev );
 351             CPPUNIT_CHECK_EX( nPrev == 0, "Expected=0 real=" << nPrev );
 352             while ( !s.empty() ) {
 353                 xp = s.extract_min( [&key](key_type k){ key = k; } );
 354                 CPPUNIT_ASSERT( xp );
 355                 CPPUNIT_CHECK_EX( key == keyPrev + 1, "Expected=" << keyPrev + 1 << " real=" << key );
 356                 CPPUNIT_CHECK_EX( nPrev + c_nStep == xp->nVal, "Expected=" << nPrev + c_nStep << " real=" << xp->nVal );
 357                 nPrev = xp->nVal;
 358                 ++keyPrev;
 359                 ++nCount;
 360             }
 361             CPPUNIT_CHECK( nCount == sizeof(keys) / sizeof(keys[0]));
 362
 363             // extract_min_key
 364             for ( int i = 0; i < static_cast<int>(sizeof(keys) / sizeof(keys[0])); ++i )
 365                 CPPUNIT_ASSERT( s.insert( keys[i], keys[i] * c_nStep ));
 366             CPPUNIT_CHECK( s.check_consistency( check_functor() ));
 367
 368             nCount = 1;
 369             xp = s.extract_min_key( keyPrev );
 370             CPPUNIT_ASSERT( xp );
 371             nPrev = xp->nVal;
 372             CPPUNIT_CHECK_EX( keyPrev == 0, "Expected=0 real=" << keyPrev );
 373             CPPUNIT_CHECK_EX( nPrev == 0, "Expected=0 real=" << nPrev );
 374             while ( !s.empty() ) {
 375                 xp = s.extract_min_key( key );
 376                 CPPUNIT_ASSERT( xp );
 377                 CPPUNIT_CHECK_EX( key == keyPrev + 1, "Expected=" << keyPrev + 1 << " real=" << key );
 378                 CPPUNIT_CHECK_EX( nPrev + c_nStep == xp->nVal, "Expected=" << nPrev + c_nStep << " real=" << xp->nVal );
 379                 nPrev = xp->nVal;
 380                 ++keyPrev;
 381                 ++nCount;
 382             }
 383             CPPUNIT_CHECK( nCount == sizeof(keys) / sizeof(keys[0]));
 384
 385             // extract_max
 386             for ( int i = 0; i < static_cast<int>(sizeof(keys) / sizeof(keys[0])); ++i )
 387                 CPPUNIT_ASSERT( s.emplace( keys[i], keys[i] * c_nStep ));
 388             CPPUNIT_CHECK( s.check_consistency( check_functor() ));
 389
 390             nCount = 1;
 391             xp = s.extract_max();
 392             CPPUNIT_ASSERT( xp );
 393             nPrev = xp->nVal;
 394             CPPUNIT_CHECK_EX( nPrev == c_nStep * (sizeof(keys) / sizeof(keys[0]) - 1),
 395                 "Expected=" << c_nStep * (sizeof(keys) / sizeof(keys[0]) - 1) << " real=" << nPrev );
 396             while ( !s.empty() ) {
 397                 xp = s.extract_max();
 398                 CPPUNIT_ASSERT( xp );
 399                 CPPUNIT_CHECK_EX( nPrev - c_nStep == xp->nVal, "Expected=" << nPrev - c_nStep << " real=" << xp->nVal );
 400                 nPrev = xp->nVal;
 401                 ++nCount;
 402             }
 403             CPPUNIT_CHECK( nCount == sizeof(keys) / sizeof(keys[0]));
 404
 405             // extract_max<Func>
 406             for ( int i = 0; i < static_cast<int>(sizeof(keys) / sizeof(keys[0])); ++i )
 407                 CPPUNIT_ASSERT( s.emplace( keys[i], keys[i] * c_nStep ));
 408             CPPUNIT_CHECK( s.check_consistency( check_functor() ));
 409
 410             nCount = 1;
 411             xp = s.extract_max( [&keyPrev]( key_type k ){ keyPrev = k; });
 412             CPPUNIT_ASSERT( xp );
 413             nPrev = xp->nVal;
 414             CPPUNIT_CHECK_EX( keyPrev == sizeof(keys) / sizeof(keys[0]) - 1,
 415                 "Expected=" << sizeof(keys) / sizeof(keys[0]) - 1 << " real=" << keyPrev );
 416             CPPUNIT_CHECK_EX( nPrev == c_nStep * (sizeof(keys) / sizeof(keys[0]) - 1),
 417                 "Expected=" << c_nStep * (sizeof(keys) / sizeof(keys[0]) - 1) << " real=" << nPrev );
 418             while ( !s.empty() ) {
 419                 xp = s.extract_max( [&key](key_type k){ key = k; });
 420                 CPPUNIT_ASSERT( xp );
 421                 CPPUNIT_CHECK_EX( key == keyPrev - 1, "Expected=" << keyPrev - 1 << " real=" << key );
 422                 CPPUNIT_CHECK_EX( nPrev - c_nStep == xp->nVal, "Expected=" << nPrev - c_nStep << " real=" << xp->nVal );
 423                 nPrev = xp->nVal;
 424                 --keyPrev;
 425                 ++nCount;
 426             }
 427             CPPUNIT_CHECK( nCount == sizeof(keys) / sizeof(keys[0]));
 428
 429             // extract_max_key
 430             for ( int i = 0; i < static_cast<int>(sizeof(keys) / sizeof(keys[0])); ++i )
 431                 CPPUNIT_ASSERT( s.emplace( keys[i], keys[i] * c_nStep ));
 432             CPPUNIT_CHECK( s.check_consistency( check_functor() ));
 433
 434             nCount = 1;
 435             xp = s.extract_max_key( keyPrev );
 436             CPPUNIT_ASSERT( xp );
 437             nPrev = xp->nVal;
 438             CPPUNIT_CHECK_EX( keyPrev == sizeof(keys) / sizeof(keys[0]) - 1,
 439                 "Expected=" << sizeof(keys) / sizeof(keys[0]) - 1 << " real=" << keyPrev );
 440             CPPUNIT_CHECK_EX( nPrev == c_nStep * (sizeof(keys) / sizeof(keys[0]) - 1),
 441                 "Expected=" << c_nStep * (sizeof(keys) / sizeof(keys[0]) - 1) << " real=" << nPrev );
 442             while ( !s.empty() ) {
 443                 xp = s.extract_max_key( key );
 444                 CPPUNIT_ASSERT( xp );
 445                 CPPUNIT_CHECK_EX( key == keyPrev - 1, "Expected=" << keyPrev - 1 << " real=" << key );
 446                 CPPUNIT_CHECK_EX( nPrev - c_nStep == xp->nVal, "Expected=" << nPrev - c_nStep << " real=" << xp->nVal );
 447                 nPrev = xp->nVal;
 448                 --keyPrev;
 449                 ++nCount;
 450             }
 451             CPPUNIT_CHECK( nCount == sizeof(keys) / sizeof(keys[0]));
 452
 453             // extract
 454             for ( int i = 0; i < static_cast<int>(sizeof(keys) / sizeof(keys[0])); ++i )
 455                 CPPUNIT_ASSERT( s.emplace( keys[i], keys[i] * c_nStep ));
 456             CPPUNIT_CHECK( s.check_consistency( check_functor() ));
 457
 458             for ( int i = 0; i < static_cast<int>(sizeof( keys ) / sizeof( keys[0] )); ++i ) {
 459                 xp = s.extract(keys[i]);
 460                 CPPUNIT_CHECK_EX( xp->nVal == keys[i] * c_nStep, "Expected value=" << keys[i] * c_nStep << " real=" << xp->nVal );
 461             }
 462             CPPUNIT_ASSERT(s.empty());
 463
 464
 465             // extract_with
 466             for ( int i = 0; i < static_cast<int>(sizeof(keys) / sizeof(keys[0])); ++i )
 467                 CPPUNIT_ASSERT( s.emplace( keys[i], keys[i] * c_nStep ));
 468             CPPUNIT_CHECK( s.check_consistency( check_functor() ));
 469
 470             for ( int i = 0; i < static_cast<int>(sizeof( keys ) / sizeof( keys[0] )); ++i ) {
 471                 xp = s.extract_with( wrapped_int(keys[i]), wrapped_less());
 472                 CPPUNIT_CHECK_EX( xp->nVal == keys[i] * c_nStep, "Expected value=" << keys[i] * c_nStep << " real=" << xp->nVal );
 473             }
 474             CPPUNIT_ASSERT(s.empty());
 475         }
 476
 477         template <class Set, class PrintStat>
 478         void test()
 479         {
 480             typedef Set set_type;
 481
 482             set_type s;
 483
 484             test_with( s );
 485
 486             s.clear();
 487             CPPUNIT_ASSERT( s.empty() );
 488             CPPUNIT_ASSERT( check_size( s, 0 ) );
 489
 490             PrintStat()(s);
 491         }
 492
 493         void BronsonAVLTree_rcu_gpi_less();
 494         void BronsonAVLTree_rcu_gpi_less_stat();
 495         void BronsonAVLTree_rcu_gpi_cmp();
 496         void BronsonAVLTree_rcu_gpi_cmp_stat();
 497         void BronsonAVLTree_rcu_gpi_cmpless();
 498         void BronsonAVLTree_rcu_gpi_less_ic();
 499         void BronsonAVLTree_rcu_gpi_cmp_ic();
 500         void BronsonAVLTree_rcu_gpi_cmp_ic_stat();
 501         void BronsonAVLTree_rcu_gpi_cmp_ic_stat_yield();
 502         void BronsonAVLTree_rcu_gpi_less_relaxed_insert();
 503         void BronsonAVLTree_rcu_gpi_less_relaxed_insert_stat();
 504         void BronsonAVLTree_rcu_gpi_pool_monitor_less();
 505         void BronsonAVLTree_rcu_gpi_pool_monitor_less_stat();
 506         void BronsonAVLTree_rcu_gpi_pool_monitor_cmp_ic_stat();
 507         void BronsonAVLTree_rcu_gpi_pool_monitor_cmp_ic_stat_yield();
 508         void BronsonAVLTree_rcu_gpi_pool_monitor_less_relaxed_insert();
 509         void BronsonAVLTree_rcu_gpi_pool_monitor_less_relaxed_insert_stat();
 510
 511         void BronsonAVLTree_rcu_gpb_less();
 512         void BronsonAVLTree_rcu_gpb_less_stat();
 513         void BronsonAVLTree_rcu_gpb_cmp();
 514         void BronsonAVLTree_rcu_gpb_cmp_stat();
 515         void BronsonAVLTree_rcu_gpb_cmpless();
 516         void BronsonAVLTree_rcu_gpb_less_ic();
 517         void BronsonAVLTree_rcu_gpb_cmp_ic();
 518         void BronsonAVLTree_rcu_gpb_cmp_ic_stat();
 519         void BronsonAVLTree_rcu_gpb_cmp_ic_stat_yield();
 520         void BronsonAVLTree_rcu_gpb_less_relaxed_insert();
 521         void BronsonAVLTree_rcu_gpb_less_relaxed_insert_stat();
 522         void BronsonAVLTree_rcu_gpb_pool_monitor_less();
 523         void BronsonAVLTree_rcu_gpb_pool_monitor_less_stat();
 524         void BronsonAVLTree_rcu_gpb_pool_monitor_cmp_ic_stat();
 525         void BronsonAVLTree_rcu_gpb_pool_monitor_cmp_ic_stat_yield();
 526         void BronsonAVLTree_rcu_gpb_pool_monitor_less_relaxed_insert();
 527         void BronsonAVLTree_rcu_gpb_pool_monitor_less_relaxed_insert_stat();
 528
 529         void BronsonAVLTree_rcu_gpt_less();
 530         void BronsonAVLTree_rcu_gpt_less_stat();
 531         void BronsonAVLTree_rcu_gpt_cmp();
 532         void BronsonAVLTree_rcu_gpt_cmp_stat();
 533         void BronsonAVLTree_rcu_gpt_cmpless();
 534         void BronsonAVLTree_rcu_gpt_less_ic();
 535         void BronsonAVLTree_rcu_gpt_cmp_ic();
 536         void BronsonAVLTree_rcu_gpt_cmp_ic_stat();
 537         void BronsonAVLTree_rcu_gpt_cmp_ic_stat_yield();
 538         void BronsonAVLTree_rcu_gpt_less_relaxed_insert();
 539         void BronsonAVLTree_rcu_gpt_less_relaxed_insert_stat();
 540         void BronsonAVLTree_rcu_gpt_pool_monitor_less();
 541         void BronsonAVLTree_rcu_gpt_pool_monitor_less_stat();
 542         void BronsonAVLTree_rcu_gpt_pool_monitor_cmp_ic_stat();
 543         void BronsonAVLTree_rcu_gpt_pool_monitor_cmp_ic_stat_yield();
 544         void BronsonAVLTree_rcu_gpt_pool_monitor_less_relaxed_insert();
 545         void BronsonAVLTree_rcu_gpt_pool_monitor_less_relaxed_insert_stat();
 546
 547         void BronsonAVLTree_rcu_shb_less();
 548         void BronsonAVLTree_rcu_shb_less_stat();
 549         void BronsonAVLTree_rcu_shb_cmp();
 550         void BronsonAVLTree_rcu_shb_cmp_stat();
 551         void BronsonAVLTree_rcu_shb_cmpless();
 552         void BronsonAVLTree_rcu_shb_less_ic();
 553         void BronsonAVLTree_rcu_shb_cmp_ic();
 554         void BronsonAVLTree_rcu_shb_cmp_ic_stat();
 555         void BronsonAVLTree_rcu_shb_cmp_ic_stat_yield();
 556         void BronsonAVLTree_rcu_shb_less_relaxed_insert();
 557         void BronsonAVLTree_rcu_shb_less_relaxed_insert_stat();
 558         void BronsonAVLTree_rcu_shb_pool_monitor_less();
 559         void BronsonAVLTree_rcu_shb_pool_monitor_less_stat();
 560         void BronsonAVLTree_rcu_shb_pool_monitor_cmp_ic_stat();
 561         void BronsonAVLTree_rcu_shb_pool_monitor_cmp_ic_stat_yield();
 562         void BronsonAVLTree_rcu_shb_pool_monitor_less_relaxed_insert();
 563         void BronsonAVLTree_rcu_shb_pool_monitor_less_relaxed_insert_stat();
 564
 565         void BronsonAVLTree_rcu_sht_less();
 566         void BronsonAVLTree_rcu_sht_less_stat();
 567         void BronsonAVLTree_rcu_sht_cmp();
 568         void BronsonAVLTree_rcu_sht_cmp_stat();
 569         void BronsonAVLTree_rcu_sht_cmpless();
 570         void BronsonAVLTree_rcu_sht_less_ic();
 571         void BronsonAVLTree_rcu_sht_cmp_ic();
 572         void BronsonAVLTree_rcu_sht_cmp_ic_stat();
 573         void BronsonAVLTree_rcu_sht_cmp_ic_stat_yield();
 574         void BronsonAVLTree_rcu_sht_less_relaxed_insert();
 575         void BronsonAVLTree_rcu_sht_less_relaxed_insert_stat();
 576         void BronsonAVLTree_rcu_sht_pool_monitor_less();
 577         void BronsonAVLTree_rcu_sht_pool_monitor_less_stat();
 578         void BronsonAVLTree_rcu_sht_pool_monitor_cmp_ic_stat();
 579         void BronsonAVLTree_rcu_sht_pool_monitor_cmp_ic_stat_yield();
 580         void BronsonAVLTree_rcu_sht_pool_monitor_less_relaxed_insert();
 581         void BronsonAVLTree_rcu_sht_pool_monitor_less_relaxed_insert_stat();
 582
 583         CPPUNIT_TEST_SUITE( BronsonAVLTreeHdrTest )
 584             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_less )
 585             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_less_stat )
 586             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_cmp )
 587             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_cmp_stat )
 588             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_cmpless )
 589             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_less_ic )
 590             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_cmp_ic )
 591             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_cmp_ic_stat )
 592             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_cmp_ic_stat_yield )
 593             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_less_relaxed_insert )
 594             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_less_relaxed_insert_stat )
 595             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_pool_monitor_less )
 596             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_pool_monitor_less_stat )
 597             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_pool_monitor_cmp_ic_stat )
 598             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_pool_monitor_cmp_ic_stat_yield )
 599             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_pool_monitor_less_relaxed_insert )
 600             CPPUNIT_TEST( BronsonAVLTree_rcu_gpi_pool_monitor_less_relaxed_insert_stat )
 601
 602             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_less )
 603             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_less_stat )
 604             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_cmp )
 605             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_cmp_stat )
 606             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_cmpless )
 607             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_less_ic )
 608             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_cmp_ic )
 609             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_cmp_ic_stat )
 610             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_cmp_ic_stat_yield )
 611             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_less_relaxed_insert )
 612             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_less_relaxed_insert_stat )
 613             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_pool_monitor_less )
 614             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_pool_monitor_less_stat )
 615             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_pool_monitor_cmp_ic_stat )
 616             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_pool_monitor_cmp_ic_stat_yield )
 617             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_pool_monitor_less_relaxed_insert )
 618             CPPUNIT_TEST( BronsonAVLTree_rcu_gpb_pool_monitor_less_relaxed_insert_stat )
 619
 620             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_less )
 621             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_less_stat )
 622             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_cmp )
 623             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_cmp_stat )
 624             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_cmpless )
 625             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_less_ic )
 626             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_cmp_ic )
 627             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_cmp_ic_stat )
 628             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_cmp_ic_stat_yield )
 629             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_less_relaxed_insert )
 630             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_less_relaxed_insert_stat )
 631             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_pool_monitor_less )
 632             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_pool_monitor_less_stat )
 633             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_pool_monitor_cmp_ic_stat )
 634             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_pool_monitor_cmp_ic_stat_yield )
 635             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_pool_monitor_less_relaxed_insert )
 636             CPPUNIT_TEST( BronsonAVLTree_rcu_gpt_pool_monitor_less_relaxed_insert_stat )
 637
 638             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_less )
 639             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_less_stat )
 640             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_cmp )
 641             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_cmp_stat )
 642             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_cmpless )
 643             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_less_ic )
 644             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_cmp_ic )
 645             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_cmp_ic_stat )
 646             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_cmp_ic_stat_yield )
 647             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_less_relaxed_insert )
 648             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_less_relaxed_insert_stat )
 649             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_pool_monitor_less )
 650             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_pool_monitor_less_stat )
 651             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_pool_monitor_cmp_ic_stat )
 652             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_pool_monitor_cmp_ic_stat_yield )
 653             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_pool_monitor_less_relaxed_insert )
 654             CPPUNIT_TEST( BronsonAVLTree_rcu_shb_pool_monitor_less_relaxed_insert_stat )
 655
 656             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_less )
 657             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_less_stat )
 658             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_cmp )
 659             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_cmp_stat )
 660             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_cmpless )
 661             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_less_ic )
 662             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_cmp_ic )
 663             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_cmp_ic_stat )
 664             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_cmp_ic_stat_yield )
 665             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_less_relaxed_insert )
 666             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_less_relaxed_insert_stat )
 667             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_pool_monitor_less )
 668             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_pool_monitor_less_stat )
 669             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_pool_monitor_cmp_ic_stat )
 670             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_pool_monitor_cmp_ic_stat_yield )
 671             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_pool_monitor_less_relaxed_insert )
 672             CPPUNIT_TEST( BronsonAVLTree_rcu_sht_pool_monitor_less_relaxed_insert_stat )
 673
 674         CPPUNIT_TEST_SUITE_END()
 675     };
 676 } // namespace tree
 677
 678 #endif // #ifndef CDSTEST_HDR_BRONSON_AVLTREE_MAP_H