tests/test-hdr/set/hdr_intrusive_skiplist_set.h

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