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                     gp = s.get( i );
 234                     CPPUNIT_CHECK( gp );
 235                     CPPUNIT_CHECK( gp->nKey == i );
 236                     CPPUNIT_CHECK( gp->nVal == i * 2 );
 237                     gp->nVal *= 2;
 238
 239                     gp = s.extract( i );
 240                     CPPUNIT_CHECK( gp );
 241                     CPPUNIT_CHECK_EX( gp->nKey == i, "i=" << i << ", gp->nKey=" << gp->nKey);
 242                     CPPUNIT_CHECK_EX( (*gp).nVal == i * 4, "i=" << i << ", gp->nVal=" << gp->nVal );
 243                     gp = s.extract( i );
 244                     CPPUNIT_CHECK( !gp );
 245                     CPPUNIT_CHECK( !s.get( i ));
 246                 }
 247                 CPPUNIT_CHECK( s.empty() );
 248                 Set::gc::force_dispose();
 249
 250                 // extract_with
 251                 fill_skiplist( s, v );
 252                 for ( int i = c_nArrSize - 1; i >= 0; i -= 1 ) {
 253                     gp = s.get_with( other_key( i ), other_key_less<typename Set::value_type>() );
 254                     CPPUNIT_CHECK( gp );
 255                     CPPUNIT_CHECK( gp->nKey == i );
 256                     CPPUNIT_CHECK( (*gp).nVal == i * 2 );
 257                     gp->nVal *= 2;
 258
 259                     gp = s.extract_with( other_key( i ), other_key_less<typename Set::value_type>() );
 260                     CPPUNIT_CHECK( gp );
 261                     CPPUNIT_CHECK_EX( gp->nKey == i, "i=" << i << ", gp->nKey=" << gp->nKey);
 262                     CPPUNIT_CHECK_EX( (*gp).nVal == i * 4, "i=" << i << ", gp->nVal=" << gp->nVal );
 263                     gp = s.extract_with( other_key( i ), other_key_less<typename Set::value_type>() );
 264                     CPPUNIT_CHECK( !gp );
 265                     CPPUNIT_CHECK( !s.get_with( other_key(i), other_key_less<typename Set::value_type>() ));
 266                 }
 267                 CPPUNIT_CHECK( s.empty() );
 268                 Set::gc::force_dispose();
 269
 270                 // extract_min
 271                 {
 272                     fill_skiplist( s, v );
 273                     int nPrevKey;
 274                     gp = s.extract_min();
 275                     CPPUNIT_ASSERT( gp );
 276                     nPrevKey = gp->nKey;
 277                     while ( !s.empty() ) {
 278                         gp = s.extract_min();
 279                         CPPUNIT_CHECK( gp );
 280                         CPPUNIT_ASSERT( !gp.empty());
 281                         CPPUNIT_CHECK( gp->nKey == nPrevKey + 1 );
 282                         CPPUNIT_CHECK( (*gp).nVal == (nPrevKey + 1) * 2 );
 283                         nPrevKey = gp->nKey;
 284                     }
 285                     gp.release();
 286                     CPPUNIT_CHECK( !s.extract_min());
 287                     CPPUNIT_CHECK( gp.empty());
 288                 }
 289                 Set::gc::force_dispose();
 290
 291                 // extract_max
 292                 {
 293                     fill_skiplist( s, v );
 294                     int nPrevKey;
 295                     gp = s.extract_max();
 296                     CPPUNIT_ASSERT( gp );
 297                     nPrevKey = gp->nKey;
 298                     while ( !s.empty() ) {
 299                         gp = s.extract_max();
 300                         CPPUNIT_CHECK( gp );
 301                         CPPUNIT_ASSERT( !gp.empty() );
 302                         CPPUNIT_CHECK( gp->nKey == nPrevKey - 1 );
 303                         CPPUNIT_CHECK( (*gp).nVal == (nPrevKey - 1) * 2 );
 304                         nPrevKey = gp->nKey;
 305                     }
 306                     gp.release();
 307                     CPPUNIT_CHECK( !s.extract_min());
 308                     CPPUNIT_CHECK( gp.empty());
 309
 310                     CPPUNIT_CHECK( !s.extract_max());
 311                 }
 312                 Set::gc::force_dispose();
 313             }
 314
 315             CPPUNIT_MSG( PrintStat()(s, nullptr) );
 316         }
 317
 318         template <typename Set>
 319         void fill_skiplist( Set& s, typename Set::value_type * pArr )
 320         {
 321             int nRand[c_nArrSize];
 322             for ( int i = 0; i < (int) c_nArrSize; ++i ) {
 323                 nRand[i] = i;
 324             }
 325             std::random_shuffle( nRand, nRand + c_nArrSize );
 326
 327             for ( int i = 0; i < (int) c_nArrSize; ++i ) {
 328                 pArr[i].nKey = nRand[i];
 329                 pArr[i].nVal = nRand[i] * 2;
 330                 CPPUNIT_ASSERT( s.insert( pArr[i] ));
 331             }
 332             CPPUNIT_CHECK( check_size( s, c_nArrSize ));
 333         }
 334
 335         template <class Set, typename PrintStat>
 336         void test_skiplist_nogc()
 337         {
 338             typedef typename Set::value_type    value_type;
 339             typedef typename Set::iterator set_iterator;
 340             typedef typename Set::iterator const_set_iterator;
 341             typedef typename base_class::less<value_type>   less;
 342
 343             value_type v1( 10, 50 );
 344             value_type v2( 5, 25  );
 345             value_type v3( 20, 100 );
 346             int key;
 347
 348             Set s;
 349
 350             // insert test
 351             CPPUNIT_ASSERT( s.empty() );
 352             CPPUNIT_ASSERT( check_size( s, 0 ));
 353
 354             // insert/find test
 355             CPPUNIT_ASSERT( s.find( v1.key() ) == nullptr );
 356             CPPUNIT_ASSERT( s.insert( v1 ));
 357             CPPUNIT_ASSERT( s.find( v1.key() ) == &v1 );
 358             CPPUNIT_ASSERT( check_size( s, 1 ));
 359             CPPUNIT_ASSERT( !s.empty() );
 360
 361             CPPUNIT_ASSERT( s.find_with( v2.key(), less() ) == nullptr );
 362             CPPUNIT_ASSERT( s.insert( v2 ));
 363             CPPUNIT_ASSERT( v2.nFindCount == 0 );
 364             CPPUNIT_ASSERT( s.find_with( key = v2.key(), less(), find_functor() ));
 365             CPPUNIT_ASSERT( v2.nFindCount == 1 );
 366             v2.nFindCount = 0;
 367             CPPUNIT_ASSERT( check_size( s, 2 ));
 368             CPPUNIT_ASSERT( !s.empty() );
 369
 370             {
 371                 find_functor    ff;
 372                 CPPUNIT_ASSERT( s.find( v3 ) == nullptr );
 373                 CPPUNIT_ASSERT( s.insert( v3 ));
 374                 CPPUNIT_ASSERT( v3.nFindCount == 0 );
 375                 CPPUNIT_ASSERT( s.find( v3, std::ref(ff) ));
 376                 CPPUNIT_ASSERT( v3.nFindCount == 1 );
 377                 v3.nFindCount = 0;
 378                 CPPUNIT_ASSERT( check_size( s, 3 ));
 379                 CPPUNIT_ASSERT( !s.empty() );
 380             }
 381
 382             CPPUNIT_ASSERT( !s.empty() );
 383             s.clear();
 384             CPPUNIT_ASSERT( s.empty() );
 385             CPPUNIT_ASSERT( check_size( s, 0 ));
 386             //CPPUNIT_MSG( PrintStat()(s, "Insert test") );
 387
 388             ensure_functor f;
 389             std::pair<bool, bool> ret = s.ensure( v1, f );
 390             CPPUNIT_ASSERT( ret.first );
 391             CPPUNIT_ASSERT( ret.second );
 392             CPPUNIT_ASSERT( v1.nEnsureNewCount == 1 );
 393             CPPUNIT_ASSERT( v1.nEnsureCount == 0 );
 394             CPPUNIT_ASSERT( check_size( s, 1 ));
 395
 396             ret = s.ensure( v2, f );
 397             CPPUNIT_ASSERT( ret.first );
 398             CPPUNIT_ASSERT( ret.second );
 399             CPPUNIT_ASSERT( v2.nEnsureNewCount == 1 );
 400             CPPUNIT_ASSERT( v2.nEnsureCount == 0 );
 401             CPPUNIT_ASSERT( check_size( s, 2 ));
 402
 403             ret = s.ensure( v3, f );
 404             CPPUNIT_ASSERT( ret.first );
 405             CPPUNIT_ASSERT( ret.second );
 406             CPPUNIT_ASSERT( v3.nEnsureNewCount == 1 );
 407             CPPUNIT_ASSERT( v3.nEnsureCount == 0 );
 408             CPPUNIT_ASSERT( check_size( s, 3 ));
 409
 410             CPPUNIT_ASSERT( s.find( v1 ) == &v1 );
 411             CPPUNIT_ASSERT( s.find_with( v2, base_class::less<value_type>() ) == &v2 );
 412             CPPUNIT_ASSERT( s.find( v3 ) == &v3 );
 413
 414             ret = s.ensure( v1, f );
 415             CPPUNIT_ASSERT( ret.first );
 416             CPPUNIT_ASSERT( !ret.second );
 417             CPPUNIT_ASSERT( v1.nEnsureNewCount == 1 );
 418             CPPUNIT_ASSERT( v1.nEnsureCount == 1 );
 419             CPPUNIT_ASSERT( check_size( s, 3 ));
 420
 421             ret = s.ensure( v2, f );
 422             CPPUNIT_ASSERT( ret.first );
 423             CPPUNIT_ASSERT( !ret.second );
 424             CPPUNIT_ASSERT( v2.nEnsureNewCount == 1 );
 425             CPPUNIT_ASSERT( v2.nEnsureCount == 1 );
 426             CPPUNIT_ASSERT( check_size( s, 3 ));
 427
 428             ret = s.ensure( v3, f );
 429             CPPUNIT_ASSERT( ret.first );
 430             CPPUNIT_ASSERT( !ret.second );
 431             CPPUNIT_ASSERT( v3.nEnsureNewCount == 1 );
 432             CPPUNIT_ASSERT( v3.nEnsureCount == 1 );
 433             CPPUNIT_ASSERT( check_size( s, 3 ));
 434
 435             CPPUNIT_ASSERT( s.find( v1 ) == &v1 );
 436             CPPUNIT_ASSERT( s.find( v2 ) == &v2 );
 437             CPPUNIT_ASSERT( s.find( v3 ) == &v3 );
 438
 439             CPPUNIT_ASSERT( !s.empty() );
 440             s.clear();
 441             CPPUNIT_ASSERT( s.empty() );
 442             CPPUNIT_ASSERT( check_size( s, 0 ));
 443
 444             //CPPUNIT_MSG( PrintStat()(s, "Ensure test") );
 445
 446             // get_min test
 447             CPPUNIT_CHECK( s.get_min() == nullptr );
 448             CPPUNIT_CHECK( s.get_max() == nullptr );
 449
 450             {
 451                 value_type  v[1000];
 452                 for ( int i = 999; i >= 0; --i ) {
 453                     v[i].nKey = i;
 454                     v[i].nVal = i * 2;
 455
 456                     CPPUNIT_ASSERT( s.insert( v[i] ));
 457                     value_type * pVal = s.get_min();
 458                     CPPUNIT_ASSERT( pVal != nullptr );
 459                     CPPUNIT_CHECK( pVal->nKey == i );
 460                     CPPUNIT_CHECK( pVal->nVal == i * 2 );
 461                 }
 462
 463                 CPPUNIT_ASSERT( !s.empty() );
 464                 s.clear();
 465                 CPPUNIT_ASSERT( s.empty() );
 466                 CPPUNIT_ASSERT( check_size( s, 0 ));
 467             }
 468
 469             // Iterator test
 470             {
 471                 value_type  v[500];
 472
 473                 for ( int i = 0; unsigned(i) < sizeof(v)/sizeof(v[0]); ++i ) {
 474                     v[i].nKey = i;
 475                     v[i].nVal = i * 2;
 476
 477                     CPPUNIT_ASSERT( s.insert( v[i] ));
 478
 479                     value_type * pVal = s.get_max();
 480                     CPPUNIT_ASSERT( pVal != nullptr );
 481                     CPPUNIT_CHECK( pVal->nKey == i );
 482                     CPPUNIT_CHECK( pVal->nVal == i * 2 );
 483                 }
 484
 485                 int nCount = 0;
 486                 for ( set_iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 487                     CPPUNIT_ASSERT( (*it).nKey * 2 == it->nVal );
 488                     it->nVal = (*it).nKey;
 489                     ++nCount;
 490                 }
 491                 CPPUNIT_ASSERT( nCount == sizeof(v)/sizeof(v[0]));
 492
 493                 nCount = 0;
 494                 for ( const_set_iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 495                     CPPUNIT_ASSERT( (*it).nKey == it->nVal );
 496                     ++nCount;
 497                 }
 498                 CPPUNIT_ASSERT( nCount == sizeof(v)/sizeof(v[0]));
 499
 500                 for ( size_t i = 0; i < sizeof(v)/sizeof(v[0]); ++i ) {
 501                     CPPUNIT_ASSERT( v[i].nKey == v[i].nVal );
 502                 }
 503
 504                 //CPPUNIT_MSG( PrintStat()(s, "Iterator test") );
 505                 s.clear();
 506             }
 507
 508             // Test empty set
 509             CPPUNIT_ASSERT( s.begin() == s.end() );
 510             CPPUNIT_ASSERT( s.cbegin() == s.cend() );
 511
 512             CPPUNIT_MSG( PrintStat()(s, nullptr) );
 513         }
 514
 515     public:
 516         // Skip-list - gc::HP
 517         void skiplist_hp_base_cmp();
 518         void skiplist_hp_base_less();
 519         void skiplist_hp_base_cmpmix();
 520         void skiplist_hp_base_cmp_stat();
 521         void skiplist_hp_base_less_stat();
 522         void skiplist_hp_base_cmpmix_stat();
 523         void skiplist_hp_base_cmp_xorshift();
 524         void skiplist_hp_base_less_xorshift();
 525         void skiplist_hp_base_cmpmix_xorshift();
 526         void skiplist_hp_base_cmp_xorshift_stat();
 527         void skiplist_hp_base_less_xorshift_stat();
 528         void skiplist_hp_base_cmpmix_xorshift_stat();
 529         void skiplist_hp_base_cmp_pascal();
 530         void skiplist_hp_base_less_pascal();
 531         void skiplist_hp_base_cmpmix_pascal();
 532         void skiplist_hp_base_cmp_pascal_stat();
 533         void skiplist_hp_base_less_pascal_stat();
 534         void skiplist_hp_base_cmpmix_pascal_stat();
 535
 536         void skiplist_hp_member_cmp();
 537         void skiplist_hp_member_less();
 538         void skiplist_hp_member_cmpmix();
 539         void skiplist_hp_member_cmp_stat();
 540         void skiplist_hp_member_less_stat();
 541         void skiplist_hp_member_cmpmix_stat();
 542         void skiplist_hp_member_cmp_xorshift();
 543         void skiplist_hp_member_less_xorshift();
 544         void skiplist_hp_member_cmpmix_xorshift();
 545         void skiplist_hp_member_cmp_xorshift_stat();
 546         void skiplist_hp_member_less_xorshift_stat();
 547         void skiplist_hp_member_cmpmix_xorshift_stat();
 548         void skiplist_hp_member_cmp_pascal();
 549         void skiplist_hp_member_less_pascal();
 550         void skiplist_hp_member_cmpmix_pascal();
 551         void skiplist_hp_member_cmp_pascal_stat();
 552         void skiplist_hp_member_less_pascal_stat();
 553         void skiplist_hp_member_cmpmix_pascal_stat();
 554
 555         // Skip-list - gc::DHP
 556         void skiplist_dhp_base_cmp();
 557         void skiplist_dhp_base_less();
 558         void skiplist_dhp_base_cmpmix();
 559         void skiplist_dhp_base_cmp_stat();
 560         void skiplist_dhp_base_less_stat();
 561         void skiplist_dhp_base_cmpmix_stat();
 562         void skiplist_dhp_base_cmp_xorshift();
 563         void skiplist_dhp_base_less_xorshift();
 564         void skiplist_dhp_base_cmpmix_xorshift();
 565         void skiplist_dhp_base_cmp_xorshift_stat();
 566         void skiplist_dhp_base_less_xorshift_stat();
 567         void skiplist_dhp_base_cmpmix_xorshift_stat();
 568         void skiplist_dhp_base_cmp_pascal();
 569         void skiplist_dhp_base_less_pascal();
 570         void skiplist_dhp_base_cmpmix_pascal();
 571         void skiplist_dhp_base_cmp_pascal_stat();
 572         void skiplist_dhp_base_less_pascal_stat();
 573         void skiplist_dhp_base_cmpmix_pascal_stat();
 574
 575         void skiplist_dhp_member_cmp();
 576         void skiplist_dhp_member_less();
 577         void skiplist_dhp_member_cmpmix();
 578         void skiplist_dhp_member_cmp_stat();
 579         void skiplist_dhp_member_less_stat();
 580         void skiplist_dhp_member_cmpmix_stat();
 581         void skiplist_dhp_member_cmp_xorshift();
 582         void skiplist_dhp_member_less_xorshift();
 583         void skiplist_dhp_member_cmpmix_xorshift();
 584         void skiplist_dhp_member_cmp_xorshift_stat();
 585         void skiplist_dhp_member_less_xorshift_stat();
 586         void skiplist_dhp_member_cmpmix_xorshift_stat();
 587         void skiplist_dhp_member_cmp_pascal();
 588         void skiplist_dhp_member_less_pascal();
 589         void skiplist_dhp_member_cmpmix_pascal();
 590         void skiplist_dhp_member_cmp_pascal_stat();
 591         void skiplist_dhp_member_less_pascal_stat();
 592         void skiplist_dhp_member_cmpmix_pascal_stat();
 593
 594         // Skip-list - gc::nogc
 595         void skiplist_nogc_base_cmp();
 596         void skiplist_nogc_base_less();
 597         void skiplist_nogc_base_cmpmix();
 598         void skiplist_nogc_base_cmp_stat();
 599         void skiplist_nogc_base_less_stat();
 600         void skiplist_nogc_base_cmpmix_stat();
 601         void skiplist_nogc_base_cmp_xorshift();
 602         void skiplist_nogc_base_less_xorshift();
 603         void skiplist_nogc_base_cmpmix_xorshift();
 604         void skiplist_nogc_base_cmp_xorshift_stat();
 605         void skiplist_nogc_base_less_xorshift_stat();
 606         void skiplist_nogc_base_cmpmix_xorshift_stat();
 607         void skiplist_nogc_base_cmp_pascal();
 608         void skiplist_nogc_base_less_pascal();
 609         void skiplist_nogc_base_cmpmix_pascal();
 610         void skiplist_nogc_base_cmp_pascal_stat();
 611         void skiplist_nogc_base_less_pascal_stat();
 612         void skiplist_nogc_base_cmpmix_pascal_stat();
 613
 614         void skiplist_nogc_member_cmp();
 615         void skiplist_nogc_member_less();
 616         void skiplist_nogc_member_cmpmix();
 617         void skiplist_nogc_member_cmp_stat();
 618         void skiplist_nogc_member_less_stat();
 619         void skiplist_nogc_member_cmpmix_stat();
 620         void skiplist_nogc_member_cmp_xorshift();
 621         void skiplist_nogc_member_less_xorshift();
 622         void skiplist_nogc_member_cmpmix_xorshift();
 623         void skiplist_nogc_member_cmp_xorshift_stat();
 624         void skiplist_nogc_member_less_xorshift_stat();
 625         void skiplist_nogc_member_cmpmix_xorshift_stat();
 626         void skiplist_nogc_member_cmp_pascal();
 627         void skiplist_nogc_member_less_pascal();
 628         void skiplist_nogc_member_cmpmix_pascal();
 629         void skiplist_nogc_member_cmp_pascal_stat();
 630         void skiplist_nogc_member_less_pascal_stat();
 631         void skiplist_nogc_member_cmpmix_pascal_stat();
 632
 633         CPPUNIT_TEST_SUITE(IntrusiveSkipListSet)
 634             CPPUNIT_TEST(skiplist_hp_base_cmp)
 635             CPPUNIT_TEST(skiplist_hp_base_less)
 636             CPPUNIT_TEST(skiplist_hp_base_cmpmix)
 637             CPPUNIT_TEST(skiplist_hp_base_cmp_stat)
 638             CPPUNIT_TEST(skiplist_hp_base_less_stat)
 639             CPPUNIT_TEST(skiplist_hp_base_cmpmix_stat)
 640             CPPUNIT_TEST(skiplist_hp_base_cmp_xorshift)
 641             CPPUNIT_TEST(skiplist_hp_base_less_xorshift)
 642             CPPUNIT_TEST(skiplist_hp_base_cmpmix_xorshift)
 643             CPPUNIT_TEST(skiplist_hp_base_cmp_xorshift_stat)
 644             CPPUNIT_TEST(skiplist_hp_base_less_xorshift_stat)
 645             CPPUNIT_TEST(skiplist_hp_base_cmpmix_xorshift_stat)
 646             CPPUNIT_TEST(skiplist_hp_base_cmp_pascal)
 647             CPPUNIT_TEST(skiplist_hp_base_less_pascal)
 648             CPPUNIT_TEST(skiplist_hp_base_cmpmix_pascal)
 649             CPPUNIT_TEST(skiplist_hp_base_cmp_pascal_stat)
 650             CPPUNIT_TEST(skiplist_hp_base_less_pascal_stat)
 651             CPPUNIT_TEST(skiplist_hp_base_cmpmix_pascal_stat)
 652
 653             CPPUNIT_TEST(skiplist_hp_member_cmp)
 654             CPPUNIT_TEST(skiplist_hp_member_less)
 655             CPPUNIT_TEST(skiplist_hp_member_cmpmix)
 656             CPPUNIT_TEST(skiplist_hp_member_cmp_stat)
 657             CPPUNIT_TEST(skiplist_hp_member_less_stat)
 658             CPPUNIT_TEST(skiplist_hp_member_cmpmix_stat)
 659             CPPUNIT_TEST(skiplist_hp_member_cmp_xorshift)
 660             CPPUNIT_TEST(skiplist_hp_member_less_xorshift)
 661             CPPUNIT_TEST(skiplist_hp_member_cmpmix_xorshift)
 662             CPPUNIT_TEST(skiplist_hp_member_cmp_xorshift_stat)
 663             CPPUNIT_TEST(skiplist_hp_member_less_xorshift_stat)
 664             CPPUNIT_TEST(skiplist_hp_member_cmpmix_xorshift_stat)
 665             CPPUNIT_TEST(skiplist_hp_member_cmp_pascal)
 666             CPPUNIT_TEST(skiplist_hp_member_less_pascal)
 667             CPPUNIT_TEST(skiplist_hp_member_cmpmix_pascal)
 668             CPPUNIT_TEST(skiplist_hp_member_cmp_pascal_stat)
 669             CPPUNIT_TEST(skiplist_hp_member_less_pascal_stat)
 670             CPPUNIT_TEST(skiplist_hp_member_cmpmix_pascal_stat)
 671
 672             CPPUNIT_TEST(skiplist_dhp_base_cmp)
 673             CPPUNIT_TEST(skiplist_dhp_base_less)
 674             CPPUNIT_TEST(skiplist_dhp_base_cmpmix)
 675             CPPUNIT_TEST(skiplist_dhp_base_cmp_stat)
 676             CPPUNIT_TEST(skiplist_dhp_base_less_stat)
 677             CPPUNIT_TEST(skiplist_dhp_base_cmpmix_stat)
 678             CPPUNIT_TEST(skiplist_dhp_base_cmp_xorshift)
 679             CPPUNIT_TEST(skiplist_dhp_base_less_xorshift)
 680             CPPUNIT_TEST(skiplist_dhp_base_cmpmix_xorshift)
 681             CPPUNIT_TEST(skiplist_dhp_base_cmp_xorshift_stat)
 682             CPPUNIT_TEST(skiplist_dhp_base_less_xorshift_stat)
 683             CPPUNIT_TEST(skiplist_dhp_base_cmpmix_xorshift_stat)
 684             CPPUNIT_TEST(skiplist_dhp_base_cmp_pascal)
 685             CPPUNIT_TEST(skiplist_dhp_base_less_pascal)
 686             CPPUNIT_TEST(skiplist_dhp_base_cmpmix_pascal)
 687             CPPUNIT_TEST(skiplist_dhp_base_cmp_pascal_stat)
 688             CPPUNIT_TEST(skiplist_dhp_base_less_pascal_stat)
 689             CPPUNIT_TEST(skiplist_dhp_base_cmpmix_pascal_stat)
 690
 691             CPPUNIT_TEST(skiplist_dhp_member_cmp)
 692             CPPUNIT_TEST(skiplist_dhp_member_less)
 693             CPPUNIT_TEST(skiplist_dhp_member_cmpmix)
 694             CPPUNIT_TEST(skiplist_dhp_member_cmp_stat)
 695             CPPUNIT_TEST(skiplist_dhp_member_less_stat)
 696             CPPUNIT_TEST(skiplist_dhp_member_cmpmix_stat)
 697             CPPUNIT_TEST(skiplist_dhp_member_cmp_xorshift)
 698             CPPUNIT_TEST(skiplist_dhp_member_less_xorshift)
 699             CPPUNIT_TEST(skiplist_dhp_member_cmpmix_xorshift)
 700             CPPUNIT_TEST(skiplist_dhp_member_cmp_xorshift_stat)
 701             CPPUNIT_TEST(skiplist_dhp_member_less_xorshift_stat)
 702             CPPUNIT_TEST(skiplist_dhp_member_cmpmix_xorshift_stat)
 703             CPPUNIT_TEST(skiplist_dhp_member_cmp_pascal)
 704             CPPUNIT_TEST(skiplist_dhp_member_less_pascal)
 705             CPPUNIT_TEST(skiplist_dhp_member_cmpmix_pascal)
 706             CPPUNIT_TEST(skiplist_dhp_member_cmp_pascal_stat)
 707             CPPUNIT_TEST(skiplist_dhp_member_less_pascal_stat)
 708             CPPUNIT_TEST(skiplist_dhp_member_cmpmix_pascal_stat)
 709
 710             CPPUNIT_TEST(skiplist_nogc_base_cmp)
 711             CPPUNIT_TEST(skiplist_nogc_base_less)
 712             CPPUNIT_TEST(skiplist_nogc_base_cmpmix)
 713             CPPUNIT_TEST(skiplist_nogc_base_cmp_stat)
 714             CPPUNIT_TEST(skiplist_nogc_base_less_stat)
 715             CPPUNIT_TEST(skiplist_nogc_base_cmpmix_stat)
 716             CPPUNIT_TEST(skiplist_nogc_base_cmp_xorshift)
 717             CPPUNIT_TEST(skiplist_nogc_base_less_xorshift)
 718             CPPUNIT_TEST(skiplist_nogc_base_cmpmix_xorshift)
 719             CPPUNIT_TEST(skiplist_nogc_base_cmp_xorshift_stat)
 720             CPPUNIT_TEST(skiplist_nogc_base_less_xorshift_stat)
 721             CPPUNIT_TEST(skiplist_nogc_base_cmpmix_xorshift_stat)
 722             CPPUNIT_TEST(skiplist_nogc_base_cmp_pascal)
 723             CPPUNIT_TEST(skiplist_nogc_base_less_pascal)
 724             CPPUNIT_TEST(skiplist_nogc_base_cmpmix_pascal)
 725             CPPUNIT_TEST(skiplist_nogc_base_cmp_pascal_stat)
 726             CPPUNIT_TEST(skiplist_nogc_base_less_pascal_stat)
 727             CPPUNIT_TEST(skiplist_nogc_base_cmpmix_pascal_stat)
 728
 729             CPPUNIT_TEST(skiplist_nogc_member_cmp)
 730             CPPUNIT_TEST(skiplist_nogc_member_less)
 731             CPPUNIT_TEST(skiplist_nogc_member_cmpmix)
 732             CPPUNIT_TEST(skiplist_nogc_member_cmp_stat)
 733             CPPUNIT_TEST(skiplist_nogc_member_less_stat)
 734             CPPUNIT_TEST(skiplist_nogc_member_cmpmix_stat)
 735             CPPUNIT_TEST(skiplist_nogc_member_cmp_xorshift)
 736             CPPUNIT_TEST(skiplist_nogc_member_less_xorshift)
 737             CPPUNIT_TEST(skiplist_nogc_member_cmpmix_xorshift)
 738             CPPUNIT_TEST(skiplist_nogc_member_cmp_xorshift_stat)
 739             CPPUNIT_TEST(skiplist_nogc_member_less_xorshift_stat)
 740             CPPUNIT_TEST(skiplist_nogc_member_cmpmix_xorshift_stat)
 741             CPPUNIT_TEST(skiplist_nogc_member_cmp_pascal)
 742             CPPUNIT_TEST(skiplist_nogc_member_less_pascal)
 743             CPPUNIT_TEST(skiplist_nogc_member_cmpmix_pascal)
 744             CPPUNIT_TEST(skiplist_nogc_member_cmp_pascal_stat)
 745             CPPUNIT_TEST(skiplist_nogc_member_less_pascal_stat)
 746             CPPUNIT_TEST(skiplist_nogc_member_cmpmix_pascal_stat)
 747
 748         CPPUNIT_TEST_SUITE_END()
 749     };
 750 } // namespace set