tests/test-hdr/set/hdr_intrusive_skiplist_set.h

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