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