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