tests/test-hdr/set/hdr_intrusive_skiplist_set.h

   1 //$$CDS-header$$
   2
   3 #include "set/hdr_intrusive_set.h"
   4
   5 namespace set {
   6
   7     class IntrusiveSkipListSet: public IntrusiveHashSetHdrTest
   8     {
   9         typedef IntrusiveHashSetHdrTest base_class;
  10
  11         static size_t const c_nArrSize = 1000;
  12
  13     protected:
  14         struct other_key {
  15             int nKey;
  16
  17             other_key()
  18             {}
  19
  20             other_key( int key )
  21                 : nKey(key)
  22             {}
  23
  24             template <typename Q>
  25             other_key& operator=( Q const& src )
  26             {
  27                 nKey = src.nKey;
  28                 return *this;
  29             }
  30         };
  31
  32         template <typename StoredType>
  33         struct other_key_less
  34         {
  35             bool operator ()( StoredType const& n, other_key k ) const
  36             {
  37                 return n.nKey < k.nKey;
  38             }
  39             bool operator ()( other_key k, StoredType const& n ) const
  40             {
  41                 return k.nKey < n.nKey;
  42             }
  43         };
  44
  45         struct copy_other_key
  46         {
  47             template <typename Q>
  48             void operator()( other_key& dest, Q const& src ) const
  49             {
  50                 dest.nKey = src.nKey;
  51             }
  52         };
  53
  54     protected:
  55         template <class Set, typename PrintStat>
  56         void test_skiplist()
  57         {
  58             {
  59                 Set s;
  60                 base_class::test_int_with( s );
  61             }
  62
  63             test_skiplist_<Set, PrintStat >();
  64         }
  65
  66         template <class Set, typename PrintStat>
  67         void test_skiplist_()
  68         {
  69             Set s;
  70             s.clear();
  71             CPPUNIT_ASSERT( s.empty() );
  72             CPPUNIT_ASSERT( check_size( s, 0 ));
  73
  74             typedef typename Set::value_type        value_type;
  75             typedef typename Set::iterator          set_iterator;
  76             typedef typename Set::const_iterator    const_set_iterator;
  77             typedef typename base_class::less<value_type>   less;
  78
  79             value_type  v[c_nArrSize];
  80             int nCount = 0;
  81             int nPrevKey = 0;
  82
  83             // Test iterator - ascending order
  84             for ( int i = 0; i < (int) (sizeof(v)/sizeof(v[0])); ++i ) {
  85                 v[i].nKey = i;
  86                 v[i].nVal = i * 2;
  87
  88                 CPPUNIT_ASSERT( s.insert( v[i] ));
  89             }
  90             CPPUNIT_ASSERT( check_size( s, sizeof(v)/sizeof(v[0]) ));
  91             //CPPUNIT_MSG( PrintStat()(s, "Iterator test, ascending insert order") );
  92
  93             nCount = 0;
  94             nPrevKey = 0;
  95             for ( set_iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
  96                 CPPUNIT_ASSERT( (*it).nKey * 2 == it->nVal );
  97                 CPPUNIT_ASSERT( s.find( it->nKey ));
  98                 it->nVal = (*it).nKey;
  99                 ++nCount;
 100                 if ( it != s.begin() ) {
 101                     CPPUNIT_ASSERT( nPrevKey + 1 == it->nKey );
 102                 }
 103                 nPrevKey = it->nKey;
 104             }
 105             CPPUNIT_ASSERT( check_size( s, sizeof(v)/sizeof(v[0]) ));
 106             CPPUNIT_ASSERT( nCount == sizeof(v)/sizeof(v[0]));
 107
 108             nCount = 0;
 109             for ( const_set_iterator it = s.cbegin(), itEnd = s.cend(); it != itEnd; ++it ) {
 110                 CPPUNIT_ASSERT( (*it).nKey == it->nVal );
 111                 ++nCount;
 112                 if ( it != s.cbegin() ) {
 113                     CPPUNIT_ASSERT( nPrevKey + 1 == it->nKey );
 114                 }
 115                 nPrevKey = it->nKey;
 116             }
 117             CPPUNIT_ASSERT( check_size( s, sizeof(v)/sizeof(v[0]) ));
 118             CPPUNIT_ASSERT( nCount == sizeof(v)/sizeof(v[0]));
 119
 120             for ( size_t i = 0; i < sizeof(v)/sizeof(v[0]); ++i ) {
 121                 CPPUNIT_ASSERT( v[i].nKey == v[i].nVal );
 122                 CPPUNIT_ASSERT( s.find_with( v[i].nKey, less() ));
 123             }
 124
 125             s.clear();
 126             CPPUNIT_ASSERT( s.empty() );
 127             CPPUNIT_ASSERT( check_size( s, 0 ));
 128             Set::gc::force_dispose();
 129
 130             for ( size_t i = 0; i < (int) sizeof(v)/sizeof(v[0]); ++i ) {
 131                 CPPUNIT_ASSERT( v[i].nDisposeCount == 1 );
 132             }
 133
 134             // Test iterator - descending order
 135             for ( int i = (int) sizeof(v)/sizeof(v[0]) - 1; i >= 0; --i ) {
 136                 v[i].nKey = i;
 137                 v[i].nVal = i * 2;
 138
 139                 CPPUNIT_ASSERT( s.insert( v[i] ));
 140             }
 141             CPPUNIT_ASSERT( check_size( s, sizeof(v)/sizeof(v[0]) ));
 142
 143             //CPPUNIT_MSG( PrintStat()(s, "Iterator test, descending insert order") );
 144
 145             nCount = 0;
 146             for ( set_iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 147                 CPPUNIT_ASSERT( (*it).nKey * 2 == it->nVal );
 148                 it->nVal = (*it).nKey;
 149                 ++nCount;
 150                 if ( it != s.begin() ) {
 151                     CPPUNIT_ASSERT( nPrevKey + 1 == it->nKey );
 152                 }
 153                 nPrevKey = it->nKey;
 154             }
 155             CPPUNIT_ASSERT( check_size( s, sizeof(v)/sizeof(v[0]) ));
 156             CPPUNIT_ASSERT( nCount == sizeof(v)/sizeof(v[0]));
 157
 158             nCount = 0;
 159             for ( const_set_iterator it = s.cbegin(), itEnd = s.cend(); it != itEnd; ++it ) {
 160                 CPPUNIT_ASSERT( (*it).nKey == it->nVal );
 161                 ++nCount;
 162                 if ( it != s.cbegin() ) {
 163                     CPPUNIT_ASSERT( nPrevKey + 1 == it->nKey );
 164                 }
 165                 nPrevKey = it->nKey;
 166             }
 167             CPPUNIT_ASSERT( check_size( s, sizeof(v)/sizeof(v[0]) ));
 168             CPPUNIT_ASSERT( nCount == sizeof(v)/sizeof(v[0]));
 169
 170             for ( size_t i = 0; i < sizeof(v)/sizeof(v[0]); ++i ) {
 171                 CPPUNIT_ASSERT( v[i].nKey == v[i].nVal );
 172             }
 173
 174             s.clear();
 175             CPPUNIT_ASSERT( s.empty() );
 176             CPPUNIT_ASSERT( check_size( s, 0 ));
 177             Set::gc::force_dispose();
 178
 179             for ( size_t i = 0; i < sizeof(v)/sizeof(v[0]); ++i ) {
 180                 CPPUNIT_ASSERT( v[i].nDisposeCount == 2 );
 181             }
 182
 183             // Test iterator - random order
 184             fill_skiplist( s, v );
 185             //CPPUNIT_MSG( PrintStat()(s, "Iterator test, random insert order") );
 186
 187             nCount = 0;
 188             for ( set_iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 189                 CPPUNIT_ASSERT( (*it).nKey * 2 == it->nVal );
 190                 it->nVal = (*it).nKey;
 191                 ++nCount;
 192                 if ( it != s.begin() ) {
 193                     CPPUNIT_ASSERT( nPrevKey + 1 == it->nKey );
 194                 }
 195                 nPrevKey = it->nKey;
 196             }
 197             CPPUNIT_ASSERT( check_size( s, sizeof(v)/sizeof(v[0]) ));
 198             CPPUNIT_ASSERT( nCount == sizeof(v)/sizeof(v[0]));
 199
 200             nCount = 0;
 201             for ( const_set_iterator it = s.cbegin(), itEnd = s.cend(); it != itEnd; ++it ) {
 202                 CPPUNIT_ASSERT( (*it).nKey == it->nVal );
 203                 ++nCount;
 204                 if ( it != s.cbegin() ) {
 205                     CPPUNIT_ASSERT( nPrevKey + 1 == it->nKey );
 206                 }
 207                 nPrevKey = it->nKey;
 208             }
 209             CPPUNIT_ASSERT( check_size( s, sizeof(v)/sizeof(v[0]) ));
 210             CPPUNIT_ASSERT( nCount == sizeof(v)/sizeof(v[0]));
 211
 212             for ( size_t i = 0; i < sizeof(v)/sizeof(v[0]); ++i ) {
 213                 CPPUNIT_ASSERT( v[i].nKey == v[i].nVal );
 214             }
 215
 216             s.clear();
 217             CPPUNIT_ASSERT( s.empty() );
 218             CPPUNIT_ASSERT( check_size( s, 0 ));
 219             Set::gc::force_dispose();
 220
 221             for ( size_t i = 0; i < sizeof(v)/sizeof(v[0]); ++i ) {
 222                 CPPUNIT_ASSERT( v[i].nDisposeCount == 3 );
 223             }
 224
 225             CPPUNIT_MSG( "extract test" );
 226             // extract/get test
 227             {
 228                 typename Set::guarded_ptr gp;
 229
 230                 // extract
 231                 fill_skiplist( s, v );
 232                 for ( int i = c_nArrSize - 1; i >= 0; i -= 1 ) {
 233                     CPPUNIT_CHECK( s.get(gp, i));
 234                     CPPUNIT_CHECK( gp->nKey == i );
 235                     CPPUNIT_CHECK( gp->nVal == i * 2 );
 236                     gp->nVal *= 2;
 237                     gp.release();
 238
 239                     CPPUNIT_CHECK( s.extract( gp, i ));
 240                     CPPUNIT_CHECK_EX( gp->nKey == i, "i=" << i << ", gp->nKey=" << gp->nKey);
 241                     CPPUNIT_CHECK_EX( (*gp).nVal == i * 4, "i=" << i << ", gp->nVal=" << gp->nVal );
 242                     CPPUNIT_CHECK( !s.extract( gp, i ));
 243                     CPPUNIT_CHECK( !s.get( gp, i ));
 244                 }
 245                 gp.release();
 246                 CPPUNIT_CHECK( s.empty() );
 247                 Set::gc::force_dispose();
 248
 249                 // extract_with
 250                 fill_skiplist( s, v );
 251                 for ( int i = c_nArrSize - 1; i >= 0; i -= 1 ) {
 252                     CPPUNIT_CHECK( s.get_with( gp, other_key(i), other_key_less<typename Set::value_type>() ));
 253                     CPPUNIT_CHECK( gp->nKey == i );
 254                     CPPUNIT_CHECK( (*gp).nVal == i * 2 );
 255                     gp->nVal *= 2;
 256                     gp.release();
 257
 258                     CPPUNIT_CHECK( s.extract_with( gp, other_key(i), other_key_less<typename Set::value_type>() ));
 259                     CPPUNIT_CHECK_EX( gp->nKey == i, "i=" << i << ", gp->nKey=" << gp->nKey);
 260                     CPPUNIT_CHECK_EX( (*gp).nVal == i * 4, "i=" << i << ", gp->nVal=" << gp->nVal );
 261                     CPPUNIT_CHECK( !s.extract_with( gp, other_key(i), other_key_less<typename Set::value_type>() ));
 262                     CPPUNIT_CHECK( !s.get_with( gp, other_key(i), other_key_less<typename Set::value_type>() ));
 263                 }
 264                 gp.release();
 265                 CPPUNIT_CHECK( s.empty() );
 266                 Set::gc::force_dispose();
 267
 268                 // extract_min
 269                 {
 270                     fill_skiplist( s, v );
 271                     int nPrevKey;
 272                     CPPUNIT_ASSERT( s.extract_min( gp ));
 273                     nPrevKey = gp->nKey;
 274                     while ( !s.empty() ) {
 275                         CPPUNIT_CHECK( s.extract_min( gp ));
 276                         CPPUNIT_ASSERT( !gp.empty());
 277                         CPPUNIT_CHECK( gp->nKey == nPrevKey + 1 );
 278                         CPPUNIT_CHECK( (*gp).nVal == (nPrevKey + 1) * 2 );
 279                         nPrevKey = gp->nKey;
 280                         gp.release();
 281                     }
 282                     gp.release();
 283                     CPPUNIT_CHECK( !s.extract_min(gp));
 284                     CPPUNIT_CHECK( gp.empty());
 285                 }
 286                 Set::gc::force_dispose();
 287
 288                 // extract_max
 289                 {
 290                     fill_skiplist( s, v );
 291                     int nPrevKey;
 292                     CPPUNIT_ASSERT( s.extract_max( gp ));
 293                     nPrevKey = gp->nKey;
 294                     while ( !s.empty() ) {
 295
 296                         CPPUNIT_CHECK( s.extract_max( gp ));
 297                         CPPUNIT_ASSERT( !gp.empty() );
 298                         CPPUNIT_CHECK( gp->nKey == nPrevKey - 1 );
 299                         CPPUNIT_CHECK( (*gp).nVal == (nPrevKey - 1) * 2 );
 300                         nPrevKey = gp->nKey;
 301                         gp.release();
 302                     }
 303                     gp.release();
 304                     CPPUNIT_CHECK( !s.extract_min(gp));
 305                     CPPUNIT_CHECK( gp.empty());
 306
 307                     CPPUNIT_CHECK( !s.extract_max(gp));
 308                     CPPUNIT_CHECK( gp.empty());
 309                 }
 310                 Set::gc::force_dispose();
 311             }
 312
 313             CPPUNIT_MSG( PrintStat()( s, NULL ));
 314         }
 315
 316         template <typename Set>
 317         void fill_skiplist( Set& s, typename Set::value_type * pArr )
 318         {
 319             int nRand[c_nArrSize];
 320             for ( int i = 0; i < (int) c_nArrSize; ++i ) {
 321                 nRand[i] = i;
 322             }
 323             std::random_shuffle( nRand, nRand + c_nArrSize );
 324
 325             for ( int i = 0; i < (int) c_nArrSize; ++i ) {
 326                 pArr[i].nKey = nRand[i];
 327                 pArr[i].nVal = nRand[i] * 2;
 328                 CPPUNIT_ASSERT( s.insert( pArr[i] ));
 329             }
 330             CPPUNIT_CHECK( check_size( s, c_nArrSize ));
 331         }
 332
 333         template <class Set, typename PrintStat>
 334         void test_skiplist_nogc()
 335         {
 336             typedef typename Set::value_type    value_type;
 337             typedef typename Set::iterator set_iterator;
 338             typedef typename Set::iterator const_set_iterator;
 339             typedef typename base_class::less<value_type>   less;
 340
 341             value_type v1( 10, 50 );
 342             value_type v2( 5, 25  );
 343             value_type v3( 20, 100 );
 344             int key;
 345
 346             Set s;
 347
 348             // insert test
 349             CPPUNIT_ASSERT( s.empty() );
 350             CPPUNIT_ASSERT( check_size( s, 0 ));
 351
 352             // insert/find test
 353             CPPUNIT_ASSERT( s.find( v1.key() ) == NULL );
 354             CPPUNIT_ASSERT( s.insert( v1 ));
 355             CPPUNIT_ASSERT( s.find( v1.key() ) == &v1 );
 356             CPPUNIT_ASSERT( check_size( s, 1 ));
 357             CPPUNIT_ASSERT( !s.empty() );
 358
 359             CPPUNIT_ASSERT( s.find_with( v2.key(), less() ) == NULL );
 360             CPPUNIT_ASSERT( s.insert( v2 ));
 361             CPPUNIT_ASSERT( v2.nFindCount == 0 );
 362             CPPUNIT_ASSERT( s.find_with( key = v2.key(), less(), find_functor() ));
 363             CPPUNIT_ASSERT( v2.nFindCount == 1 );
 364             v2.nFindCount = 0;
 365             CPPUNIT_ASSERT( check_size( s, 2 ));
 366             CPPUNIT_ASSERT( !s.empty() );
 367
 368             {
 369                 find_functor    ff;
 370                 CPPUNIT_ASSERT( s.find( v3 ) == NULL );
 371                 CPPUNIT_ASSERT( s.insert( v3 ));
 372                 CPPUNIT_ASSERT( v3.nFindCount == 0 );
 373                 CPPUNIT_ASSERT( s.find( v3, cds::ref(ff) ));
 374                 CPPUNIT_ASSERT( v3.nFindCount == 1 );
 375                 v3.nFindCount = 0;
 376                 CPPUNIT_ASSERT( check_size( s, 3 ));
 377                 CPPUNIT_ASSERT( !s.empty() );
 378             }
 379
 380             CPPUNIT_ASSERT( !s.empty() );
 381             s.clear();
 382             CPPUNIT_ASSERT( s.empty() );
 383             CPPUNIT_ASSERT( check_size( s, 0 ));
 384             //CPPUNIT_MSG( PrintStat()(s, "Insert test") );
 385
 386             ensure_functor f;
 387             std::pair<bool, bool> ret = s.ensure( v1, f );
 388             CPPUNIT_ASSERT( ret.first );
 389             CPPUNIT_ASSERT( ret.second );
 390             CPPUNIT_ASSERT( v1.nEnsureNewCount == 1 );
 391             CPPUNIT_ASSERT( v1.nEnsureCount == 0 );
 392             CPPUNIT_ASSERT( check_size( s, 1 ));
 393
 394             ret = s.ensure( v2, f );
 395             CPPUNIT_ASSERT( ret.first );
 396             CPPUNIT_ASSERT( ret.second );
 397             CPPUNIT_ASSERT( v2.nEnsureNewCount == 1 );
 398             CPPUNIT_ASSERT( v2.nEnsureCount == 0 );
 399             CPPUNIT_ASSERT( check_size( s, 2 ));
 400
 401             ret = s.ensure( v3, f );
 402             CPPUNIT_ASSERT( ret.first );
 403             CPPUNIT_ASSERT( ret.second );
 404             CPPUNIT_ASSERT( v3.nEnsureNewCount == 1 );
 405             CPPUNIT_ASSERT( v3.nEnsureCount == 0 );
 406             CPPUNIT_ASSERT( check_size( s, 3 ));
 407
 408             CPPUNIT_ASSERT( s.find( v1 ) == &v1 );
 409             CPPUNIT_ASSERT( s.find_with( v2, base_class::less<value_type>() ) == &v2 );
 410             CPPUNIT_ASSERT( s.find( v3 ) == &v3 );
 411
 412             ret = s.ensure( v1, f );
 413             CPPUNIT_ASSERT( ret.first );
 414             CPPUNIT_ASSERT( !ret.second );
 415             CPPUNIT_ASSERT( v1.nEnsureNewCount == 1 );
 416             CPPUNIT_ASSERT( v1.nEnsureCount == 1 );
 417             CPPUNIT_ASSERT( check_size( s, 3 ));
 418
 419             ret = s.ensure( v2, f );
 420             CPPUNIT_ASSERT( ret.first );
 421             CPPUNIT_ASSERT( !ret.second );
 422             CPPUNIT_ASSERT( v2.nEnsureNewCount == 1 );
 423             CPPUNIT_ASSERT( v2.nEnsureCount == 1 );
 424             CPPUNIT_ASSERT( check_size( s, 3 ));
 425
 426             ret = s.ensure( v3, f );
 427             CPPUNIT_ASSERT( ret.first );
 428             CPPUNIT_ASSERT( !ret.second );
 429             CPPUNIT_ASSERT( v3.nEnsureNewCount == 1 );
 430             CPPUNIT_ASSERT( v3.nEnsureCount == 1 );
 431             CPPUNIT_ASSERT( check_size( s, 3 ));
 432
 433             CPPUNIT_ASSERT( s.find( v1 ) == &v1 );
 434             CPPUNIT_ASSERT( s.find( v2 ) == &v2 );
 435             CPPUNIT_ASSERT( s.find( v3 ) == &v3 );
 436
 437             CPPUNIT_ASSERT( !s.empty() );
 438             s.clear();
 439             CPPUNIT_ASSERT( s.empty() );
 440             CPPUNIT_ASSERT( check_size( s, 0 ));
 441
 442             //CPPUNIT_MSG( PrintStat()(s, "Ensure test") );
 443
 444             // get_min test
 445             CPPUNIT_CHECK( s.get_min() == NULL );
 446             CPPUNIT_CHECK( s.get_max() == NULL );
 447
 448             {
 449                 value_type  v[1000];
 450                 for ( int i = 999; i >= 0; --i ) {
 451                     v[i].nKey = i;
 452                     v[i].nVal = i * 2;
 453
 454                     CPPUNIT_ASSERT( s.insert( v[i] ));
 455                     value_type * pVal = s.get_min();
 456                     CPPUNIT_ASSERT( pVal != NULL );
 457                     CPPUNIT_CHECK( pVal->nKey == i );
 458                     CPPUNIT_CHECK( pVal->nVal == i * 2 );
 459                 }
 460
 461                 CPPUNIT_ASSERT( !s.empty() );
 462                 s.clear();
 463                 CPPUNIT_ASSERT( s.empty() );
 464                 CPPUNIT_ASSERT( check_size( s, 0 ));
 465             }
 466
 467             // Iterator test
 468             {
 469                 value_type  v[500];
 470
 471                 for ( int i = 0; unsigned(i) < sizeof(v)/sizeof(v[0]); ++i ) {
 472                     v[i].nKey = i;
 473                     v[i].nVal = i * 2;
 474
 475                     CPPUNIT_ASSERT( s.insert( v[i] ));
 476
 477                     value_type * pVal = s.get_max();
 478                     CPPUNIT_ASSERT( pVal != NULL );
 479                     CPPUNIT_CHECK( pVal->nKey == i );
 480                     CPPUNIT_CHECK( pVal->nVal == i * 2 );
 481                 }
 482
 483                 int nCount = 0;
 484                 for ( set_iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 485                     CPPUNIT_ASSERT( (*it).nKey * 2 == it->nVal );
 486                     it->nVal = (*it).nKey;
 487                     ++nCount;
 488                 }
 489                 CPPUNIT_ASSERT( nCount == sizeof(v)/sizeof(v[0]));
 490
 491                 nCount = 0;
 492                 for ( const_set_iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 493                     CPPUNIT_ASSERT( (*it).nKey == it->nVal );
 494                     ++nCount;
 495                 }
 496                 CPPUNIT_ASSERT( nCount == sizeof(v)/sizeof(v[0]));
 497
 498                 for ( size_t i = 0; i < sizeof(v)/sizeof(v[0]); ++i ) {
 499                     CPPUNIT_ASSERT( v[i].nKey == v[i].nVal );
 500                 }
 501
 502                 //CPPUNIT_MSG( PrintStat()(s, "Iterator test") );
 503                 s.clear();
 504             }
 505
 506             // Test empty set
 507             CPPUNIT_ASSERT( s.begin() == s.end() );
 508             CPPUNIT_ASSERT( s.cbegin() == s.cend() );
 509
 510             CPPUNIT_MSG( PrintStat()(s, NULL) );
 511         }
 512
 513     public:
 514         // Skip-list - gc::HP
 515         void skiplist_hp_base_cmp();
 516         void skiplist_hp_base_less();
 517         void skiplist_hp_base_cmpmix();
 518         void skiplist_hp_base_cmp_stat();
 519         void skiplist_hp_base_less_stat();
 520         void skiplist_hp_base_cmpmix_stat();
 521         void skiplist_hp_base_cmp_xorshift();
 522         void skiplist_hp_base_less_xorshift();
 523         void skiplist_hp_base_cmpmix_xorshift();
 524         void skiplist_hp_base_cmp_xorshift_stat();
 525         void skiplist_hp_base_less_xorshift_stat();
 526         void skiplist_hp_base_cmpmix_xorshift_stat();
 527         void skiplist_hp_base_cmp_pascal();
 528         void skiplist_hp_base_less_pascal();
 529         void skiplist_hp_base_cmpmix_pascal();
 530         void skiplist_hp_base_cmp_pascal_stat();
 531         void skiplist_hp_base_less_pascal_stat();
 532         void skiplist_hp_base_cmpmix_pascal_stat();
 533
 534         void skiplist_hp_member_cmp();
 535         void skiplist_hp_member_less();
 536         void skiplist_hp_member_cmpmix();
 537         void skiplist_hp_member_cmp_stat();
 538         void skiplist_hp_member_less_stat();
 539         void skiplist_hp_member_cmpmix_stat();
 540         void skiplist_hp_member_cmp_xorshift();
 541         void skiplist_hp_member_less_xorshift();
 542         void skiplist_hp_member_cmpmix_xorshift();
 543         void skiplist_hp_member_cmp_xorshift_stat();
 544         void skiplist_hp_member_less_xorshift_stat();
 545         void skiplist_hp_member_cmpmix_xorshift_stat();
 546         void skiplist_hp_member_cmp_pascal();
 547         void skiplist_hp_member_less_pascal();
 548         void skiplist_hp_member_cmpmix_pascal();
 549         void skiplist_hp_member_cmp_pascal_stat();
 550         void skiplist_hp_member_less_pascal_stat();
 551         void skiplist_hp_member_cmpmix_pascal_stat();
 552
 553         // Skip-list - gc::HRC
 554         void skiplist_hrc_base_cmp();
 555         void skiplist_hrc_base_less();
 556         void skiplist_hrc_base_cmpmix();
 557         void skiplist_hrc_base_cmp_stat();
 558         void skiplist_hrc_base_less_stat();
 559         void skiplist_hrc_base_cmpmix_stat();
 560         void skiplist_hrc_base_cmp_xorshift();
 561         void skiplist_hrc_base_less_xorshift();
 562         void skiplist_hrc_base_cmpmix_xorshift();
 563         void skiplist_hrc_base_cmp_xorshift_stat();
 564         void skiplist_hrc_base_less_xorshift_stat();
 565         void skiplist_hrc_base_cmpmix_xorshift_stat();
 566         void skiplist_hrc_base_cmp_pascal();
 567         void skiplist_hrc_base_less_pascal();
 568         void skiplist_hrc_base_cmpmix_pascal();
 569         void skiplist_hrc_base_cmp_pascal_stat();
 570         void skiplist_hrc_base_less_pascal_stat();
 571         void skiplist_hrc_base_cmpmix_pascal_stat();
 572
 573         // Skip-list - gc::PTB
 574         void skiplist_ptb_base_cmp();
 575         void skiplist_ptb_base_less();
 576         void skiplist_ptb_base_cmpmix();
 577         void skiplist_ptb_base_cmp_stat();
 578         void skiplist_ptb_base_less_stat();
 579         void skiplist_ptb_base_cmpmix_stat();
 580         void skiplist_ptb_base_cmp_xorshift();
 581         void skiplist_ptb_base_less_xorshift();
 582         void skiplist_ptb_base_cmpmix_xorshift();
 583         void skiplist_ptb_base_cmp_xorshift_stat();
 584         void skiplist_ptb_base_less_xorshift_stat();
 585         void skiplist_ptb_base_cmpmix_xorshift_stat();
 586         void skiplist_ptb_base_cmp_pascal();
 587         void skiplist_ptb_base_less_pascal();
 588         void skiplist_ptb_base_cmpmix_pascal();
 589         void skiplist_ptb_base_cmp_pascal_stat();
 590         void skiplist_ptb_base_less_pascal_stat();
 591         void skiplist_ptb_base_cmpmix_pascal_stat();
 592
 593         void skiplist_ptb_member_cmp();
 594         void skiplist_ptb_member_less();
 595         void skiplist_ptb_member_cmpmix();
 596         void skiplist_ptb_member_cmp_stat();
 597         void skiplist_ptb_member_less_stat();
 598         void skiplist_ptb_member_cmpmix_stat();
 599         void skiplist_ptb_member_cmp_xorshift();
 600         void skiplist_ptb_member_less_xorshift();
 601         void skiplist_ptb_member_cmpmix_xorshift();
 602         void skiplist_ptb_member_cmp_xorshift_stat();
 603         void skiplist_ptb_member_less_xorshift_stat();
 604         void skiplist_ptb_member_cmpmix_xorshift_stat();
 605         void skiplist_ptb_member_cmp_pascal();
 606         void skiplist_ptb_member_less_pascal();
 607         void skiplist_ptb_member_cmpmix_pascal();
 608         void skiplist_ptb_member_cmp_pascal_stat();
 609         void skiplist_ptb_member_less_pascal_stat();
 610         void skiplist_ptb_member_cmpmix_pascal_stat();
 611
 612         // Skip-list - gc::nogc
 613         void skiplist_nogc_base_cmp();
 614         void skiplist_nogc_base_less();
 615         void skiplist_nogc_base_cmpmix();
 616         void skiplist_nogc_base_cmp_stat();
 617         void skiplist_nogc_base_less_stat();
 618         void skiplist_nogc_base_cmpmix_stat();
 619         void skiplist_nogc_base_cmp_xorshift();
 620         void skiplist_nogc_base_less_xorshift();
 621         void skiplist_nogc_base_cmpmix_xorshift();
 622         void skiplist_nogc_base_cmp_xorshift_stat();
 623         void skiplist_nogc_base_less_xorshift_stat();
 624         void skiplist_nogc_base_cmpmix_xorshift_stat();
 625         void skiplist_nogc_base_cmp_pascal();
 626         void skiplist_nogc_base_less_pascal();
 627         void skiplist_nogc_base_cmpmix_pascal();
 628         void skiplist_nogc_base_cmp_pascal_stat();
 629         void skiplist_nogc_base_less_pascal_stat();
 630         void skiplist_nogc_base_cmpmix_pascal_stat();
 631
 632         void skiplist_nogc_member_cmp();
 633         void skiplist_nogc_member_less();
 634         void skiplist_nogc_member_cmpmix();
 635         void skiplist_nogc_member_cmp_stat();
 636         void skiplist_nogc_member_less_stat();
 637         void skiplist_nogc_member_cmpmix_stat();
 638         void skiplist_nogc_member_cmp_xorshift();
 639         void skiplist_nogc_member_less_xorshift();
 640         void skiplist_nogc_member_cmpmix_xorshift();
 641         void skiplist_nogc_member_cmp_xorshift_stat();
 642         void skiplist_nogc_member_less_xorshift_stat();
 643         void skiplist_nogc_member_cmpmix_xorshift_stat();
 644         void skiplist_nogc_member_cmp_pascal();
 645         void skiplist_nogc_member_less_pascal();
 646         void skiplist_nogc_member_cmpmix_pascal();
 647         void skiplist_nogc_member_cmp_pascal_stat();
 648         void skiplist_nogc_member_less_pascal_stat();
 649         void skiplist_nogc_member_cmpmix_pascal_stat();
 650
 651         CPPUNIT_TEST_SUITE(IntrusiveSkipListSet)
 652             CPPUNIT_TEST(skiplist_hp_base_cmp)
 653             CPPUNIT_TEST(skiplist_hp_base_less)
 654             CPPUNIT_TEST(skiplist_hp_base_cmpmix)
 655             CPPUNIT_TEST(skiplist_hp_base_cmp_stat)
 656             CPPUNIT_TEST(skiplist_hp_base_less_stat)
 657             CPPUNIT_TEST(skiplist_hp_base_cmpmix_stat)
 658             CPPUNIT_TEST(skiplist_hp_base_cmp_xorshift)
 659             CPPUNIT_TEST(skiplist_hp_base_less_xorshift)
 660             CPPUNIT_TEST(skiplist_hp_base_cmpmix_xorshift)
 661             CPPUNIT_TEST(skiplist_hp_base_cmp_xorshift_stat)
 662             CPPUNIT_TEST(skiplist_hp_base_less_xorshift_stat)
 663             CPPUNIT_TEST(skiplist_hp_base_cmpmix_xorshift_stat)
 664             CPPUNIT_TEST(skiplist_hp_base_cmp_pascal)
 665             CPPUNIT_TEST(skiplist_hp_base_less_pascal)
 666             CPPUNIT_TEST(skiplist_hp_base_cmpmix_pascal)
 667             CPPUNIT_TEST(skiplist_hp_base_cmp_pascal_stat)
 668             CPPUNIT_TEST(skiplist_hp_base_less_pascal_stat)
 669             CPPUNIT_TEST(skiplist_hp_base_cmpmix_pascal_stat)
 670
 671             CPPUNIT_TEST(skiplist_hp_member_cmp)
 672             CPPUNIT_TEST(skiplist_hp_member_less)
 673             CPPUNIT_TEST(skiplist_hp_member_cmpmix)
 674             CPPUNIT_TEST(skiplist_hp_member_cmp_stat)
 675             CPPUNIT_TEST(skiplist_hp_member_less_stat)
 676             CPPUNIT_TEST(skiplist_hp_member_cmpmix_stat)
 677             CPPUNIT_TEST(skiplist_hp_member_cmp_xorshift)
 678             CPPUNIT_TEST(skiplist_hp_member_less_xorshift)
 679             CPPUNIT_TEST(skiplist_hp_member_cmpmix_xorshift)
 680             CPPUNIT_TEST(skiplist_hp_member_cmp_xorshift_stat)
 681             CPPUNIT_TEST(skiplist_hp_member_less_xorshift_stat)
 682             CPPUNIT_TEST(skiplist_hp_member_cmpmix_xorshift_stat)
 683             CPPUNIT_TEST(skiplist_hp_member_cmp_pascal)
 684             CPPUNIT_TEST(skiplist_hp_member_less_pascal)
 685             CPPUNIT_TEST(skiplist_hp_member_cmpmix_pascal)
 686             CPPUNIT_TEST(skiplist_hp_member_cmp_pascal_stat)
 687             CPPUNIT_TEST(skiplist_hp_member_less_pascal_stat)
 688             CPPUNIT_TEST(skiplist_hp_member_cmpmix_pascal_stat)
 689
 690             CPPUNIT_TEST(skiplist_hrc_base_cmp)
 691             CPPUNIT_TEST(skiplist_hrc_base_less)
 692             CPPUNIT_TEST(skiplist_hrc_base_cmpmix)
 693             CPPUNIT_TEST(skiplist_hrc_base_cmp_stat)
 694             CPPUNIT_TEST(skiplist_hrc_base_less_stat)
 695             CPPUNIT_TEST(skiplist_hrc_base_cmpmix_stat)
 696             CPPUNIT_TEST(skiplist_hrc_base_cmp_xorshift)
 697             CPPUNIT_TEST(skiplist_hrc_base_less_xorshift)
 698             CPPUNIT_TEST(skiplist_hrc_base_cmpmix_xorshift)
 699             CPPUNIT_TEST(skiplist_hrc_base_cmp_xorshift_stat)
 700             CPPUNIT_TEST(skiplist_hrc_base_less_xorshift_stat)
 701             CPPUNIT_TEST(skiplist_hrc_base_cmpmix_xorshift_stat)
 702             CPPUNIT_TEST(skiplist_hrc_base_cmp_pascal)
 703             CPPUNIT_TEST(skiplist_hrc_base_less_pascal)
 704             CPPUNIT_TEST(skiplist_hrc_base_cmpmix_pascal)
 705             CPPUNIT_TEST(skiplist_hrc_base_cmp_pascal_stat)
 706             CPPUNIT_TEST(skiplist_hrc_base_less_pascal_stat)
 707             CPPUNIT_TEST(skiplist_hrc_base_cmpmix_pascal_stat)
 708
 709             CPPUNIT_TEST(skiplist_ptb_base_cmp)
 710             CPPUNIT_TEST(skiplist_ptb_base_less)
 711             CPPUNIT_TEST(skiplist_ptb_base_cmpmix)
 712             CPPUNIT_TEST(skiplist_ptb_base_cmp_stat)
 713             CPPUNIT_TEST(skiplist_ptb_base_less_stat)
 714             CPPUNIT_TEST(skiplist_ptb_base_cmpmix_stat)
 715             CPPUNIT_TEST(skiplist_ptb_base_cmp_xorshift)
 716             CPPUNIT_TEST(skiplist_ptb_base_less_xorshift)
 717             CPPUNIT_TEST(skiplist_ptb_base_cmpmix_xorshift)
 718             CPPUNIT_TEST(skiplist_ptb_base_cmp_xorshift_stat)
 719             CPPUNIT_TEST(skiplist_ptb_base_less_xorshift_stat)
 720             CPPUNIT_TEST(skiplist_ptb_base_cmpmix_xorshift_stat)
 721             CPPUNIT_TEST(skiplist_ptb_base_cmp_pascal)
 722             CPPUNIT_TEST(skiplist_ptb_base_less_pascal)
 723             CPPUNIT_TEST(skiplist_ptb_base_cmpmix_pascal)
 724             CPPUNIT_TEST(skiplist_ptb_base_cmp_pascal_stat)
 725             CPPUNIT_TEST(skiplist_ptb_base_less_pascal_stat)
 726             CPPUNIT_TEST(skiplist_ptb_base_cmpmix_pascal_stat)
 727
 728             CPPUNIT_TEST(skiplist_ptb_member_cmp)
 729             CPPUNIT_TEST(skiplist_ptb_member_less)
 730             CPPUNIT_TEST(skiplist_ptb_member_cmpmix)
 731             CPPUNIT_TEST(skiplist_ptb_member_cmp_stat)
 732             CPPUNIT_TEST(skiplist_ptb_member_less_stat)
 733             CPPUNIT_TEST(skiplist_ptb_member_cmpmix_stat)
 734             CPPUNIT_TEST(skiplist_ptb_member_cmp_xorshift)
 735             CPPUNIT_TEST(skiplist_ptb_member_less_xorshift)
 736             CPPUNIT_TEST(skiplist_ptb_member_cmpmix_xorshift)
 737             CPPUNIT_TEST(skiplist_ptb_member_cmp_xorshift_stat)
 738             CPPUNIT_TEST(skiplist_ptb_member_less_xorshift_stat)
 739             CPPUNIT_TEST(skiplist_ptb_member_cmpmix_xorshift_stat)
 740             CPPUNIT_TEST(skiplist_ptb_member_cmp_pascal)
 741             CPPUNIT_TEST(skiplist_ptb_member_less_pascal)
 742             CPPUNIT_TEST(skiplist_ptb_member_cmpmix_pascal)
 743             CPPUNIT_TEST(skiplist_ptb_member_cmp_pascal_stat)
 744             CPPUNIT_TEST(skiplist_ptb_member_less_pascal_stat)
 745             CPPUNIT_TEST(skiplist_ptb_member_cmpmix_pascal_stat)
 746
 747             CPPUNIT_TEST(skiplist_nogc_base_cmp)
 748             CPPUNIT_TEST(skiplist_nogc_base_less)
 749             CPPUNIT_TEST(skiplist_nogc_base_cmpmix)
 750             CPPUNIT_TEST(skiplist_nogc_base_cmp_stat)
 751             CPPUNIT_TEST(skiplist_nogc_base_less_stat)
 752             CPPUNIT_TEST(skiplist_nogc_base_cmpmix_stat)
 753             CPPUNIT_TEST(skiplist_nogc_base_cmp_xorshift)
 754             CPPUNIT_TEST(skiplist_nogc_base_less_xorshift)
 755             CPPUNIT_TEST(skiplist_nogc_base_cmpmix_xorshift)
 756             CPPUNIT_TEST(skiplist_nogc_base_cmp_xorshift_stat)
 757             CPPUNIT_TEST(skiplist_nogc_base_less_xorshift_stat)
 758             CPPUNIT_TEST(skiplist_nogc_base_cmpmix_xorshift_stat)
 759             CPPUNIT_TEST(skiplist_nogc_base_cmp_pascal)
 760             CPPUNIT_TEST(skiplist_nogc_base_less_pascal)
 761             CPPUNIT_TEST(skiplist_nogc_base_cmpmix_pascal)
 762             CPPUNIT_TEST(skiplist_nogc_base_cmp_pascal_stat)
 763             CPPUNIT_TEST(skiplist_nogc_base_less_pascal_stat)
 764             CPPUNIT_TEST(skiplist_nogc_base_cmpmix_pascal_stat)
 765
 766             CPPUNIT_TEST(skiplist_nogc_member_cmp)
 767             CPPUNIT_TEST(skiplist_nogc_member_less)
 768             CPPUNIT_TEST(skiplist_nogc_member_cmpmix)
 769             CPPUNIT_TEST(skiplist_nogc_member_cmp_stat)
 770             CPPUNIT_TEST(skiplist_nogc_member_less_stat)
 771             CPPUNIT_TEST(skiplist_nogc_member_cmpmix_stat)
 772             CPPUNIT_TEST(skiplist_nogc_member_cmp_xorshift)
 773             CPPUNIT_TEST(skiplist_nogc_member_less_xorshift)
 774             CPPUNIT_TEST(skiplist_nogc_member_cmpmix_xorshift)
 775             CPPUNIT_TEST(skiplist_nogc_member_cmp_xorshift_stat)
 776             CPPUNIT_TEST(skiplist_nogc_member_less_xorshift_stat)
 777             CPPUNIT_TEST(skiplist_nogc_member_cmpmix_xorshift_stat)
 778             CPPUNIT_TEST(skiplist_nogc_member_cmp_pascal)
 779             CPPUNIT_TEST(skiplist_nogc_member_less_pascal)
 780             CPPUNIT_TEST(skiplist_nogc_member_cmpmix_pascal)
 781             CPPUNIT_TEST(skiplist_nogc_member_cmp_pascal_stat)
 782             CPPUNIT_TEST(skiplist_nogc_member_less_pascal_stat)
 783             CPPUNIT_TEST(skiplist_nogc_member_cmpmix_pascal_stat)
 784
 785         CPPUNIT_TEST_SUITE_END()
 786     };
 787 } // namespace set