tests/test-hdr/set/hdr_intrusive_striped_set.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_STRIPED_SET_H
  32 #define CDSTEST_HDR_INTRUSIVE_STRIPED_SET_H
  33
  34 #include "cppunit/cppunit_proxy.h"
  35 #include <cds/opt/hash.h>
  36
  37 #include <boost/version.hpp>
  38
  39 // boost 1.59 bug: intrusive containers require implicit conversion from value_type to key_type
  40 // Fixed in boost 1.60+
  41 #if BOOST_VERSION == 105900
  42 #   define CDSTEST_BOOST_INTRUSIVE_REQUIRES_IMPLICIT_CONVERSION_WORKAROUND
  43 #else
  44 #   define CDSTEST_BOOST_INTRUSIVE_REQUIRES_IMPLICIT_CONVERSION_WORKAROUND explicit
  45 #endif
  46
  47 // cds::intrusive namespace forward declaration
  48 namespace cds { namespace intrusive {}}
  49
  50 namespace set {
  51     namespace ci = cds::intrusive;
  52     namespace co = cds::opt;
  53
  54     template <typename T>
  55     struct get_int_key
  56     {
  57         int operator()( T const & v ) const
  58         {
  59             return v.key();
  60         }
  61     };
  62
  63     template <>
  64     struct get_int_key<int>
  65     {
  66         int operator()( int i ) const
  67         {
  68             return i;
  69         }
  70     };
  71
  72     // MichaelHashSet
  73     class IntrusiveStripedSetHdrTest: public CppUnitMini::TestCase
  74     {
  75     public:
  76         struct stat
  77         {
  78             unsigned int nDisposeCount  ;   // count of disposer calling
  79             unsigned int nFindCount     ;   // count of find-functor calling
  80             unsigned int nFindArgCount;
  81             unsigned int nInsertCount;
  82             unsigned int nUpdateNewCount;
  83             unsigned int nUpdateCount;
  84             unsigned int nEraseCount;
  85
  86             stat()
  87             {
  88                 memset( this, 0, sizeof(*this));
  89             }
  90
  91             stat& operator=( stat const& s)
  92             {
  93                 memcpy( this, &s, sizeof(*this));
  94                 return *this;
  95             }
  96         };
  97
  98         struct item
  99         {
 100             int nKey;
 101             int nVal;
 102
 103             item()
 104             {}
 105
 106             explicit item( int key )
 107                 : nKey( key )
 108                 , nVal(0)
 109             {}
 110
 111             item(int key, int val)
 112                 : nKey( key )
 113                 , nVal(val)
 114             {}
 115
 116             item(const item& v )
 117                 : nKey( v.nKey )
 118                 , nVal( v.nVal )
 119             {}
 120
 121             int key() const
 122             {
 123                 return nKey;
 124             }
 125
 126             int val() const
 127             {
 128                 return nVal;
 129             }
 130         };
 131
 132         template <typename Hook>
 133         struct base_item
 134             : public item
 135             , public Hook
 136             , public stat
 137
 138         {
 139             base_item()
 140             {}
 141
 142             CDSTEST_BOOST_INTRUSIVE_REQUIRES_IMPLICIT_CONVERSION_WORKAROUND
 143             base_item( int key )
 144                 : item( key )
 145             {}
 146
 147             base_item(int key, int val)
 148                 : item( key, val )
 149             {}
 150
 151             base_item(const base_item& v )
 152                 : item( static_cast<item const&>(v) )
 153                 , stat()
 154             {}
 155
 156             operator int() const
 157             {
 158                 return key();
 159             }
 160         };
 161
 162         template <typename Hook>
 163         struct member_item
 164             : public item
 165             , public stat
 166         {
 167             Hook hMember;
 168
 169             member_item()
 170             {}
 171
 172             CDSTEST_BOOST_INTRUSIVE_REQUIRES_IMPLICIT_CONVERSION_WORKAROUND
 173             member_item( int key )
 174                 : item( key )
 175             {}
 176
 177             member_item(int key, int val)
 178                 : item( key, val )
 179             {}
 180
 181             member_item(const member_item& v )
 182                 : item( static_cast<item const&>(v))
 183                 , stat()
 184             {}
 185
 186             operator int() const
 187             {
 188                 return key();
 189             }
 190         };
 191
 192         struct find_key {
 193             int nKey;
 194
 195             find_key( int key )
 196                 : nKey(key)
 197             {}
 198         };
 199
 200         struct hash_int {
 201             size_t operator()( int i ) const
 202             {
 203                 return co::v::hash<int>()( i );
 204             }
 205             template <typename Item>
 206             size_t operator()( const Item& i ) const
 207             {
 208                 return (*this)( i.key() );
 209             }
 210             size_t operator()( find_key const& i) const
 211             {
 212                 return co::v::hash<int>()( i.nKey );
 213             }
 214         };
 215
 216         template <typename T>
 217         struct less
 218         {
 219             bool operator ()(const T& v1, const T& v2 ) const
 220             {
 221                 return v1.key() < v2.key();
 222             }
 223
 224             template <typename Q>
 225             bool operator ()(const T& v1, const Q& v2 ) const
 226             {
 227                 return v1.key() < v2;
 228             }
 229
 230             template <typename Q>
 231             bool operator ()(const Q& v1, const T& v2 ) const
 232             {
 233                 return v1 < v2.key();
 234             }
 235
 236             bool operator()( int i1, int i2 ) const
 237             {
 238                 return i1 < i2;
 239             }
 240         };
 241
 242         template <typename T>
 243         struct cmp {
 244             int operator ()(const T& v1, const T& v2 ) const
 245             {
 246                 if ( v1.key() < v2.key() )
 247                     return -1;
 248                 return v1.key() > v2.key() ? 1 : 0;
 249             }
 250
 251             template <typename Q>
 252             int operator ()(const T& v1, const Q& v2 ) const
 253             {
 254                 if ( v1.key() < v2 )
 255                     return -1;
 256                 return v1.key() > v2 ? 1 : 0;
 257             }
 258
 259             template <typename Q>
 260             int operator ()(const Q& v1, const T& v2 ) const
 261             {
 262                 if ( v1 < v2.key() )
 263                     return -1;
 264                 return v1 > v2.key() ? 1 : 0;
 265             }
 266         };
 267
 268         struct faked_disposer
 269         {
 270             template <typename T>
 271             void operator ()( T * p )
 272             {
 273                 ++p->nDisposeCount;
 274             }
 275         };
 276
 277         struct insert_functor {
 278             template <typename Item>
 279             void operator()( Item& e)
 280             {
 281                 ++e.nInsertCount;
 282             }
 283         };
 284
 285         struct update_functor {
 286             template <typename Item>
 287             void operator()( bool bNew, Item& e, Item& arg )
 288             {
 289                 if ( bNew ) {
 290                     ++e.nUpdateNewCount;
 291                     CPPUNIT_ASSERT_CURRENT( &e == &arg );
 292                 }
 293                 else
 294                     ++e.nUpdateCount;
 295             }
 296         };
 297
 298         struct erase_functor {
 299             template< typename Item >
 300             void operator()( Item& e )
 301             {
 302                 ++e.nEraseCount;
 303             }
 304         };
 305
 306         struct find_functor {
 307             template <typename Item, typename What>
 308             void operator()( Item& e, What& )
 309             {
 310                 ++e.nFindCount;
 311             }
 312
 313             template <typename Item>
 314             void operator()( Item& e, Item& w )
 315             {
 316                 ++e.nFindCount;
 317                 ++w.nFindArgCount;
 318             }
 319         };
 320
 321         struct less2 {
 322             template <typename Item>
 323             bool operator()( Item const& e, find_key const& k ) const
 324             {
 325                 return get_int_key<Item>()(e) < k.nKey;
 326             }
 327             template <typename Item>
 328             bool operator()( find_key const& k, Item const& e ) const
 329             {
 330                 return k.nKey < get_int_key<Item>()(e);
 331             }
 332             template <typename Item1, typename Item2>
 333             bool operator()( Item1 const& e, Item2 const& k ) const
 334             {
 335                 return get_int_key<Item1>()(e) < get_int_key<Item2>()(k);
 336             }
 337         };
 338
 339         template <typename T>
 340         struct auto_dispose {
 341             T * m_pArr;
 342             auto_dispose( T * pArr ): m_pArr( pArr ) {}
 343             ~auto_dispose() { delete[] m_pArr; }
 344         };
 345
 346         template <class Set>
 347         void test_with(Set& s)
 348         {
 349             typedef typename Set::value_type    value_type;
 350
 351             int const k1 = 10;
 352             int const k2 = 25;
 353             int const k3 = 51;
 354
 355             int const v1 = 25;
 356             int const v2 = 56;
 357             int const v3 = 23;
 358
 359             value_type e1( k1, v1 );
 360             value_type e2( k2, v2 );
 361             value_type e3( k3, v3);
 362
 363             stat s1 = e1;
 364             stat s2 = e2;
 365             stat s3 = e3;
 366
 367             CPPUNIT_ASSERT( s.empty() );
 368             CPPUNIT_ASSERT( s.size() == 0 );
 369
 370             CPPUNIT_ASSERT( !s.contains(k1));
 371             CPPUNIT_ASSERT( !s.contains(k2));
 372             CPPUNIT_ASSERT( !s.contains(k3));
 373
 374             CPPUNIT_ASSERT( s.insert(e1));
 375             CPPUNIT_ASSERT( s.contains(e1));
 376             CPPUNIT_ASSERT( s.contains(k1));
 377             CPPUNIT_ASSERT( !s.contains(e2));
 378             CPPUNIT_ASSERT( !s.contains(e3));
 379
 380             CPPUNIT_ASSERT( e2.nInsertCount == 0 );
 381             CPPUNIT_ASSERT( s.insert(e2, insert_functor() ));
 382             CPPUNIT_ASSERT( e2.nInsertCount == 1 );
 383             CPPUNIT_ASSERT( s.find(e1, find_functor() ));
 384             CPPUNIT_ASSERT( e1.nFindCount == 1 );
 385             CPPUNIT_ASSERT( e1.nFindArgCount == 1 );
 386             CPPUNIT_ASSERT( s.find(k1, find_functor() ));
 387             CPPUNIT_ASSERT( e1.nFindCount == 2 );
 388             CPPUNIT_ASSERT( e1.nFindArgCount == 1 );
 389             CPPUNIT_ASSERT( s.find(k2, find_functor() ));
 390             CPPUNIT_ASSERT( e2.nFindCount == 1 );
 391             CPPUNIT_ASSERT( e2.nFindArgCount == 0 );
 392             CPPUNIT_ASSERT( s.find(e2, find_functor() ));
 393             CPPUNIT_ASSERT( e2.nFindCount == 2 );
 394             CPPUNIT_ASSERT( e2.nFindArgCount == 1 );
 395             CPPUNIT_ASSERT( !s.find(k3, find_functor()));
 396             CPPUNIT_ASSERT( e3.nFindCount == 0 );
 397             CPPUNIT_ASSERT( e3.nFindArgCount == 0 );
 398             CPPUNIT_ASSERT( !s.find(e3, find_functor()));
 399             CPPUNIT_ASSERT( e3.nFindCount == 0 );
 400             CPPUNIT_ASSERT( e3.nFindArgCount == 0 );
 401
 402             s1 = e1 ; s2 = e2 ; s3 = e3;
 403
 404             CPPUNIT_ASSERT( e3.nUpdateNewCount == 0 );
 405             CPPUNIT_ASSERT( e3.nUpdateCount == 0 );
 406             CPPUNIT_ASSERT(s.update(e3, update_functor(), false) == std::make_pair(false, false));
 407             CPPUNIT_ASSERT(e3.nUpdateNewCount == 0);
 408             CPPUNIT_ASSERT(e3.nUpdateCount == 0);
 409             CPPUNIT_ASSERT( s.update( e3, update_functor() ) == std::make_pair(true, true));
 410             CPPUNIT_ASSERT( e3.nUpdateNewCount == 1 );
 411             CPPUNIT_ASSERT( e3.nUpdateCount == 0 );
 412             CPPUNIT_ASSERT( s.find_with(find_key(k1), less2(), find_functor() ));
 413             CPPUNIT_ASSERT( e1.nFindCount == s1.nFindCount + 1 );
 414             CPPUNIT_ASSERT( e1.nFindArgCount == s1.nFindArgCount );
 415             CPPUNIT_ASSERT( s.find_with(k1, less2(), find_functor() ));
 416             CPPUNIT_ASSERT( e1.nFindCount == s1.nFindCount + 2 );
 417             CPPUNIT_ASSERT( e1.nFindArgCount == s1.nFindArgCount );
 418             CPPUNIT_ASSERT( s.find_with(k2, less2(), find_functor() ));
 419             CPPUNIT_ASSERT( e2.nFindCount == s2.nFindCount + 1 );
 420             CPPUNIT_ASSERT( e2.nFindArgCount == s2.nFindArgCount );
 421             CPPUNIT_ASSERT( s.contains(find_key(k2), less2() ));
 422             CPPUNIT_ASSERT( e2.nFindCount == s2.nFindCount + 1 )        ;   // unchanged, no find_functor
 423             CPPUNIT_ASSERT( e2.nFindArgCount == s2.nFindArgCount );
 424             CPPUNIT_ASSERT( s.contains(k3, less2() ));
 425             CPPUNIT_ASSERT( e3.nFindCount == s3.nFindCount )            ;   // unchanged, no find_functor
 426             CPPUNIT_ASSERT( e3.nFindArgCount == s3.nFindArgCount );
 427             CPPUNIT_ASSERT( s.find_with(find_key(k3), less2(), find_functor() ));
 428             CPPUNIT_ASSERT( e3.nFindCount == s3.nFindCount + 1 );
 429             CPPUNIT_ASSERT( e3.nFindArgCount == s3.nFindArgCount );
 430
 431             s1 = e1 ; s2 = e2 ; s3 = e3;
 432
 433             // insert existing elements
 434             {
 435                 value_type eu( k2, 1000 );
 436                 CPPUNIT_ASSERT( !s.insert( eu ));
 437                 CPPUNIT_ASSERT( !s.insert( eu, insert_functor() ));
 438                 CPPUNIT_ASSERT( e2.nInsertCount == s2.nInsertCount );
 439
 440                 CPPUNIT_ASSERT( s.update( eu, update_functor()) == std::make_pair(true, false));
 441                 CPPUNIT_ASSERT( e2.nInsertCount == s2.nInsertCount );
 442                 CPPUNIT_ASSERT( e2.nUpdateCount == s2.nUpdateCount + 1 );
 443                 CPPUNIT_ASSERT( e2.nUpdateNewCount == s2.nUpdateNewCount  );
 444             }
 445
 446             s1 = e1 ; s2 = e2 ; s3 = e3;
 447
 448             // unlink & erase test
 449             {
 450                 value_type eu( k2, 10 );
 451                 CPPUNIT_ASSERT( !s.unlink(eu));
 452             }
 453
 454             CPPUNIT_ASSERT( !s.empty() );
 455             CPPUNIT_ASSERT( s.size() == 3 );
 456
 457             CPPUNIT_ASSERT( s.unlink( e1 ) );
 458             CPPUNIT_ASSERT( s.erase_with( k2, less2() ) == &e2 );
 459             CPPUNIT_ASSERT( s.erase( e2 ) == nullptr );
 460             CPPUNIT_ASSERT( e3.nEraseCount == 0 );
 461             CPPUNIT_ASSERT( s.erase_with( k3, less2(), erase_functor()) == &e3 );
 462             CPPUNIT_ASSERT( e3.nEraseCount == 1 );
 463             CPPUNIT_ASSERT( s.erase( k3, erase_functor() ) == nullptr );
 464             CPPUNIT_ASSERT( e3.nEraseCount == 1 );
 465
 466             CPPUNIT_ASSERT( s.insert( e3 ) );
 467             CPPUNIT_ASSERT( s.erase( e3 ) == &e3 );
 468             CPPUNIT_ASSERT( e3.nEraseCount == 1 );
 469
 470             CPPUNIT_ASSERT( s.empty() );
 471             CPPUNIT_ASSERT( s.size() == 0 );
 472
 473             s1 = e1 ; s2 = e2 ; s3 = e3;
 474
 475             // clear & clear_and_dispose test
 476             CPPUNIT_ASSERT( s.insert(e1));
 477             CPPUNIT_ASSERT( s.insert(e2));
 478             CPPUNIT_ASSERT( s.insert(e3));
 479             CPPUNIT_ASSERT( !s.empty() );
 480             CPPUNIT_ASSERT( s.size() == 3 );
 481             s.clear();
 482             CPPUNIT_ASSERT( s.empty() );
 483             CPPUNIT_ASSERT( s.size() == 0 );
 484
 485             CPPUNIT_ASSERT( s.insert(e1));
 486             CPPUNIT_ASSERT( s.insert(e2));
 487             CPPUNIT_ASSERT( s.insert(e3));
 488             CPPUNIT_ASSERT( !s.empty() );
 489             CPPUNIT_ASSERT( s.size() == 3 );
 490
 491             CPPUNIT_ASSERT( e1.nDisposeCount == 0 );
 492             CPPUNIT_ASSERT( e2.nDisposeCount == 0 );
 493             CPPUNIT_ASSERT( e3.nDisposeCount == 0 );
 494             s.clear_and_dispose( faked_disposer() );
 495             CPPUNIT_ASSERT( e1.nDisposeCount == 1 );
 496             CPPUNIT_ASSERT( e2.nDisposeCount == 1 );
 497             CPPUNIT_ASSERT( e3.nDisposeCount == 1 );
 498             CPPUNIT_ASSERT( s.empty() );
 499             CPPUNIT_ASSERT( s.size() == 0 );
 500
 501             // resize test (up to 64K elements)
 502             size_t const nSize = 64 * 1024;
 503             value_type * arr = new value_type[nSize];
 504             auto_dispose<value_type> ad(arr);
 505             for ( size_t i = 0; i < nSize; ++i ) {
 506                 value_type * p = new (arr + i) value_type( (int) i, (int) i * 2 );
 507                 CPPUNIT_ASSERT_EX( s.insert( *p, insert_functor() ), "i=" << i );
 508                 CPPUNIT_ASSERT_EX( p->nInsertCount == 1, "i=" << i );
 509                 //for ( size_t j = 0; j <= i; ++j ) {
 510                 //    if ( !s.contains((int) j) ) {
 511                 //        CPPUNIT_MSG( "Key " << j << " is not found after inserting key " << i );
 512                 //    }
 513                 //}
 514             }
 515
 516             for ( size_t i = 0; i < nSize; ++i )
 517                 CPPUNIT_ASSERT_EX( s.contains((int) i), "Key " << i << " is not found" );
 518
 519             CPPUNIT_ASSERT( !s.empty() );
 520             CPPUNIT_ASSERT( s.size() == nSize );
 521             s.clear_and_dispose( faked_disposer() );
 522             for ( size_t i = 0; i < nSize; ++i ) {
 523                 CPPUNIT_ASSERT_EX( arr[i].nDisposeCount == 1, "i=" << i );
 524             }
 525         }
 526
 527         template <class Set>
 528         void test()
 529         {
 530             // default ctor
 531             {
 532                 Set s;
 533                 test_with(s);
 534             }
 535
 536             // ctor with explicit initial capacity
 537             {
 538                 Set s(256);
 539                 test_with(s);
 540             }
 541         }
 542
 543         template <class Set>
 544         void test_cuckoo()
 545         {
 546             unsigned int nProbesetSize = Set::node_type::probeset_size ? Set::node_type::probeset_size : 4;
 547             Set s( 256, nProbesetSize, nProbesetSize / 2 );
 548             test_with( s );
 549         }
 550
 551         // ***********************************************************
 552         // Striped set
 553
 554         void Striped_list_basehook_cmp();
 555         void Striped_list_basehook_less();
 556         void Striped_list_basehook_cmpmix();
 557         void Striped_list_basehook_bucket_threshold();
 558         void Striped_list_basehook_bucket_threshold_rt();
 559         void Striped_list_memberhook_cmp();
 560         void Striped_list_memberhook_less();
 561         void Striped_list_memberhook_cmpmix();
 562         void Striped_list_memberhook_bucket_threshold();
 563         void Striped_list_memberhook_bucket_threshold_rt();
 564
 565         void Striped_slist_basehook_cmp();
 566         void Striped_slist_basehook_less();
 567         void Striped_slist_basehook_cmpmix();
 568         void Striped_slist_basehook_bucket_threshold();
 569         void Striped_slist_basehook_bucket_threshold_rt();
 570         void Striped_slist_memberhook_cmp();
 571         void Striped_slist_memberhook_less();
 572         void Striped_slist_memberhook_cmpmix();
 573         void Striped_slist_memberhook_bucket_threshold();
 574         void Striped_slist_memberhook_bucket_threshold_rt();
 575
 576         void Striped_set_basehook();
 577         void Striped_set_basehook_bucket_threshold();
 578         void Striped_set_basehook_bucket_threshold_rt();
 579         void Striped_set_memberhook();
 580         void Striped_set_memberhook_bucket_threshold();
 581         void Striped_set_memberhook_bucket_threshold_rt();
 582
 583         void Striped_unordered_set_basehook();
 584         void Striped_unordered_set_basehook_bucket_threshold();
 585         void Striped_unordered_set_basehook_bucket_threshold_rt();
 586         void Striped_unordered_set_memberhook();
 587         void Striped_unordered_set_memberhook_bucket_threshold();
 588         void Striped_unordered_set_memberhook_bucket_threshold_rt();
 589
 590         void Striped_avl_set_basehook();
 591         void Striped_avl_set_basehook_bucket_threshold();
 592         void Striped_avl_set_basehook_bucket_threshold_rt();
 593         void Striped_avl_set_memberhook();
 594         void Striped_avl_set_memberhook_bucket_threshold();
 595         void Striped_avl_set_memberhook_bucket_threshold_rt();
 596
 597         void Striped_sg_set_basehook();
 598         void Striped_sg_set_basehook_bucket_threshold();
 599         void Striped_sg_set_basehook_bucket_threshold_rt();
 600         void Striped_sg_set_memberhook();
 601         void Striped_sg_set_memberhook_bucket_threshold();
 602         void Striped_sg_set_memberhook_bucket_threshold_rt();
 603
 604         void Striped_splay_set_basehook();
 605         void Striped_splay_set_basehook_bucket_threshold();
 606         void Striped_splay_set_basehook_bucket_threshold_rt();
 607         void Striped_splay_set_memberhook();
 608         void Striped_splay_set_memberhook_bucket_threshold();
 609         void Striped_splay_set_memberhook_bucket_threshold_rt();
 610
 611         void Striped_treap_set_basehook();
 612         void Striped_treap_set_basehook_bucket_threshold();
 613         void Striped_treap_set_basehook_bucket_threshold_rt();
 614         void Striped_treap_set_memberhook();
 615         void Striped_treap_set_memberhook_bucket_threshold();
 616         void Striped_treap_set_memberhook_bucket_threshold_rt();
 617
 618         // ***********************************************************
 619         // Refinable set
 620
 621         void Refinable_list_basehook_cmp();
 622         void Refinable_list_basehook_less();
 623         void Refinable_list_basehook_cmpmix();
 624         void Refinable_list_basehook_bucket_threshold();
 625         void Refinable_list_basehook_bucket_threshold_rt();
 626         void Refinable_list_memberhook_cmp();
 627         void Refinable_list_memberhook_less();
 628         void Refinable_list_memberhook_cmpmix();
 629         void Refinable_list_memberhook_bucket_threshold();
 630         void Refinable_list_memberhook_bucket_threshold_rt();
 631
 632         void Refinable_slist_basehook_cmp();
 633         void Refinable_slist_basehook_less();
 634         void Refinable_slist_basehook_cmpmix();
 635         void Refinable_slist_basehook_bucket_threshold();
 636         void Refinable_slist_basehook_bucket_threshold_rt();
 637         void Refinable_slist_memberhook_cmp();
 638         void Refinable_slist_memberhook_less();
 639         void Refinable_slist_memberhook_cmpmix();
 640         void Refinable_slist_memberhook_bucket_threshold();
 641         void Refinable_slist_memberhook_bucket_threshold_rt();
 642
 643         void Refinable_set_basehook();
 644         void Refinable_set_basehook_bucket_threshold();
 645         void Refinable_set_basehook_bucket_threshold_rt();
 646         void Refinable_set_memberhook();
 647         void Refinable_set_memberhook_bucket_threshold();
 648         void Refinable_set_memberhook_bucket_threshold_rt();
 649
 650         void Refinable_unordered_set_basehook();
 651         void Refinable_unordered_set_basehook_bucket_threshold();
 652         void Refinable_unordered_set_basehook_bucket_threshold_rt();
 653         void Refinable_unordered_set_memberhook();
 654         void Refinable_unordered_set_memberhook_bucket_threshold();
 655         void Refinable_unordered_set_memberhook_bucket_threshold_rt();
 656
 657         void Refinable_avl_set_basehook();
 658         void Refinable_avl_set_basehook_bucket_threshold();
 659         void Refinable_avl_set_basehook_bucket_threshold_rt();
 660         void Refinable_avl_set_memberhook();
 661         void Refinable_avl_set_memberhook_bucket_threshold();
 662         void Refinable_avl_set_memberhook_bucket_threshold_rt();
 663
 664         void Refinable_sg_set_basehook();
 665         void Refinable_sg_set_basehook_bucket_threshold();
 666         void Refinable_sg_set_basehook_bucket_threshold_rt();
 667         void Refinable_sg_set_memberhook();
 668         void Refinable_sg_set_memberhook_bucket_threshold();
 669         void Refinable_sg_set_memberhook_bucket_threshold_rt();
 670
 671         void Refinable_splay_set_basehook();
 672         void Refinable_splay_set_basehook_bucket_threshold();
 673         void Refinable_splay_set_basehook_bucket_threshold_rt();
 674         void Refinable_splay_set_memberhook();
 675         void Refinable_splay_set_memberhook_bucket_threshold();
 676         void Refinable_splay_set_memberhook_bucket_threshold_rt();
 677
 678         void Refinable_treap_set_basehook();
 679         void Refinable_treap_set_basehook_bucket_threshold();
 680         void Refinable_treap_set_basehook_bucket_threshold_rt();
 681         void Refinable_treap_set_memberhook();
 682         void Refinable_treap_set_memberhook_bucket_threshold();
 683         void Refinable_treap_set_memberhook_bucket_threshold_rt();
 684
 685         CPPUNIT_TEST_SUITE(IntrusiveStripedSetHdrTest)
 686             // ***********************************************************
 687             // Striped set
 688
 689             CPPUNIT_TEST( Striped_list_basehook_cmp)
 690             CPPUNIT_TEST( Striped_list_basehook_less)
 691             CPPUNIT_TEST( Striped_list_basehook_cmpmix)
 692             CPPUNIT_TEST( Striped_list_basehook_bucket_threshold)
 693             CPPUNIT_TEST( Striped_list_basehook_bucket_threshold_rt)
 694             CPPUNIT_TEST( Striped_list_memberhook_cmp)
 695             CPPUNIT_TEST( Striped_list_memberhook_less)
 696             CPPUNIT_TEST( Striped_list_memberhook_cmpmix)
 697             CPPUNIT_TEST( Striped_list_memberhook_bucket_threshold)
 698             CPPUNIT_TEST( Striped_list_memberhook_bucket_threshold_rt)
 699
 700             CPPUNIT_TEST( Striped_slist_basehook_cmp)
 701             CPPUNIT_TEST( Striped_slist_basehook_less)
 702             CPPUNIT_TEST( Striped_slist_basehook_cmpmix)
 703             CPPUNIT_TEST( Striped_slist_basehook_bucket_threshold)
 704             CPPUNIT_TEST( Striped_slist_basehook_bucket_threshold_rt)
 705             CPPUNIT_TEST( Striped_slist_memberhook_cmp)
 706             CPPUNIT_TEST( Striped_slist_memberhook_less)
 707             CPPUNIT_TEST( Striped_slist_memberhook_cmpmix)
 708             CPPUNIT_TEST( Striped_slist_memberhook_bucket_threshold)
 709             CPPUNIT_TEST( Striped_slist_memberhook_bucket_threshold_rt)
 710
 711             CPPUNIT_TEST( Striped_set_basehook )
 712             CPPUNIT_TEST( Striped_set_basehook_bucket_threshold )
 713             CPPUNIT_TEST( Striped_set_basehook_bucket_threshold_rt )
 714             CPPUNIT_TEST( Striped_set_memberhook)
 715             CPPUNIT_TEST( Striped_set_memberhook_bucket_threshold )
 716             CPPUNIT_TEST( Striped_set_memberhook_bucket_threshold_rt )
 717
 718             CPPUNIT_TEST( Striped_unordered_set_basehook )
 719             CPPUNIT_TEST( Striped_unordered_set_basehook_bucket_threshold )
 720             CPPUNIT_TEST( Striped_unordered_set_basehook_bucket_threshold_rt )
 721             CPPUNIT_TEST( Striped_unordered_set_memberhook)
 722             CPPUNIT_TEST( Striped_unordered_set_memberhook_bucket_threshold )
 723             CPPUNIT_TEST( Striped_unordered_set_memberhook_bucket_threshold_rt )
 724
 725             CPPUNIT_TEST( Striped_avl_set_basehook )
 726             CPPUNIT_TEST( Striped_avl_set_basehook_bucket_threshold )
 727             CPPUNIT_TEST( Striped_avl_set_basehook_bucket_threshold_rt )
 728             CPPUNIT_TEST( Striped_avl_set_memberhook)
 729             CPPUNIT_TEST( Striped_avl_set_memberhook_bucket_threshold )
 730             CPPUNIT_TEST( Striped_avl_set_memberhook_bucket_threshold_rt )
 731
 732             CPPUNIT_TEST( Striped_sg_set_basehook )
 733             CPPUNIT_TEST( Striped_sg_set_basehook_bucket_threshold )
 734             CPPUNIT_TEST( Striped_sg_set_basehook_bucket_threshold_rt )
 735             CPPUNIT_TEST( Striped_sg_set_memberhook)
 736             CPPUNIT_TEST( Striped_sg_set_memberhook_bucket_threshold )
 737             CPPUNIT_TEST( Striped_sg_set_memberhook_bucket_threshold_rt )
 738
 739             CPPUNIT_TEST( Striped_splay_set_basehook )
 740             CPPUNIT_TEST( Striped_splay_set_basehook_bucket_threshold )
 741             CPPUNIT_TEST( Striped_splay_set_basehook_bucket_threshold_rt )
 742             CPPUNIT_TEST( Striped_splay_set_memberhook)
 743             CPPUNIT_TEST( Striped_splay_set_memberhook_bucket_threshold )
 744             CPPUNIT_TEST( Striped_splay_set_memberhook_bucket_threshold_rt )
 745
 746             CPPUNIT_TEST( Striped_treap_set_basehook )
 747             CPPUNIT_TEST( Striped_treap_set_basehook_bucket_threshold )
 748             CPPUNIT_TEST( Striped_treap_set_basehook_bucket_threshold_rt )
 749             CPPUNIT_TEST( Striped_treap_set_memberhook)
 750             CPPUNIT_TEST( Striped_treap_set_memberhook_bucket_threshold )
 751             CPPUNIT_TEST( Striped_treap_set_memberhook_bucket_threshold_rt )
 752
 753             // ***********************************************************
 754             // Refinable set
 755
 756             CPPUNIT_TEST( Refinable_list_basehook_cmp)
 757             CPPUNIT_TEST( Refinable_list_basehook_less)
 758             CPPUNIT_TEST( Refinable_list_basehook_cmpmix)
 759             CPPUNIT_TEST( Refinable_list_basehook_bucket_threshold)
 760             CPPUNIT_TEST( Refinable_list_basehook_bucket_threshold_rt)
 761             CPPUNIT_TEST( Refinable_list_memberhook_cmp)
 762             CPPUNIT_TEST( Refinable_list_memberhook_less)
 763             CPPUNIT_TEST( Refinable_list_memberhook_cmpmix)
 764             CPPUNIT_TEST( Refinable_list_memberhook_bucket_threshold)
 765             CPPUNIT_TEST( Refinable_list_memberhook_bucket_threshold_rt)
 766
 767             CPPUNIT_TEST( Refinable_slist_basehook_cmp)
 768             CPPUNIT_TEST( Refinable_slist_basehook_less)
 769             CPPUNIT_TEST( Refinable_slist_basehook_cmpmix)
 770             CPPUNIT_TEST( Refinable_slist_basehook_bucket_threshold)
 771             CPPUNIT_TEST( Refinable_slist_basehook_bucket_threshold_rt)
 772             CPPUNIT_TEST( Refinable_slist_memberhook_cmp)
 773             CPPUNIT_TEST( Refinable_slist_memberhook_less)
 774             CPPUNIT_TEST( Refinable_slist_memberhook_cmpmix)
 775             CPPUNIT_TEST( Refinable_slist_memberhook_bucket_threshold)
 776             CPPUNIT_TEST( Refinable_slist_memberhook_bucket_threshold_rt)
 777
 778             CPPUNIT_TEST( Refinable_set_basehook )
 779             CPPUNIT_TEST( Refinable_set_basehook_bucket_threshold )
 780             CPPUNIT_TEST( Refinable_set_basehook_bucket_threshold_rt )
 781             CPPUNIT_TEST( Refinable_set_memberhook)
 782             CPPUNIT_TEST( Refinable_set_memberhook_bucket_threshold )
 783             CPPUNIT_TEST( Refinable_set_memberhook_bucket_threshold_rt )
 784
 785             CPPUNIT_TEST( Refinable_unordered_set_basehook )
 786             CPPUNIT_TEST( Refinable_unordered_set_basehook_bucket_threshold )
 787             CPPUNIT_TEST( Refinable_unordered_set_basehook_bucket_threshold_rt )
 788             CPPUNIT_TEST( Refinable_unordered_set_memberhook)
 789             CPPUNIT_TEST( Refinable_unordered_set_memberhook_bucket_threshold )
 790             CPPUNIT_TEST( Refinable_unordered_set_memberhook_bucket_threshold_rt )
 791
 792             CPPUNIT_TEST( Refinable_avl_set_basehook )
 793             CPPUNIT_TEST( Refinable_avl_set_basehook_bucket_threshold )
 794             CPPUNIT_TEST( Refinable_avl_set_basehook_bucket_threshold_rt )
 795             CPPUNIT_TEST( Refinable_avl_set_memberhook)
 796             CPPUNIT_TEST( Refinable_avl_set_memberhook_bucket_threshold )
 797             CPPUNIT_TEST( Refinable_avl_set_memberhook_bucket_threshold_rt )
 798
 799             CPPUNIT_TEST( Refinable_sg_set_basehook )
 800             CPPUNIT_TEST( Refinable_sg_set_basehook_bucket_threshold )
 801             CPPUNIT_TEST( Refinable_sg_set_basehook_bucket_threshold_rt )
 802             CPPUNIT_TEST( Refinable_sg_set_memberhook)
 803             CPPUNIT_TEST( Refinable_sg_set_memberhook_bucket_threshold )
 804             CPPUNIT_TEST( Refinable_sg_set_memberhook_bucket_threshold_rt )
 805
 806             CPPUNIT_TEST( Refinable_splay_set_basehook )
 807             CPPUNIT_TEST( Refinable_splay_set_basehook_bucket_threshold )
 808             CPPUNIT_TEST( Refinable_splay_set_basehook_bucket_threshold_rt )
 809             CPPUNIT_TEST( Refinable_splay_set_memberhook)
 810             CPPUNIT_TEST( Refinable_splay_set_memberhook_bucket_threshold )
 811             CPPUNIT_TEST( Refinable_splay_set_memberhook_bucket_threshold_rt )
 812
 813             CPPUNIT_TEST( Refinable_treap_set_basehook )
 814             CPPUNIT_TEST( Refinable_treap_set_basehook_bucket_threshold )
 815             CPPUNIT_TEST( Refinable_treap_set_basehook_bucket_threshold_rt )
 816             CPPUNIT_TEST( Refinable_treap_set_memberhook)
 817             CPPUNIT_TEST( Refinable_treap_set_memberhook_bucket_threshold )
 818             CPPUNIT_TEST( Refinable_treap_set_memberhook_bucket_threshold_rt )
 819         CPPUNIT_TEST_SUITE_END()
 820     };
 821 } // namespace set
 822
 823 #endif // #ifndef CDSTEST_HDR_INTRUSIVE_STRIPED_SET_H