tests/test-hdr/map/hdr_skiplist_map.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_SKIPLIST_MAP_H
  32 #define CDSTEST_HDR_SKIPLIST_MAP_H
  33
  34 #include "map/hdr_map.h"
  35
  36 namespace map {
  37
  38     class SkipListMapHdrTest: public HashMapHdrTest
  39     {
  40         typedef HashMapHdrTest base_class;
  41         typedef base_class::other_item  wrapped_item;
  42         typedef base_class::other_less  wrapped_less;
  43
  44         template <class Map, typename PrintStat >
  45         void test()
  46         {
  47             Map m;
  48             test_int_with( m );
  49
  50             static int const nLimit = 10000;
  51             typedef typename Map::iterator          set_iterator;
  52             typedef typename Map::const_iterator    const_set_iterator;
  53
  54             int nCount = 0;
  55             int nPrevKey = 0;
  56
  57             // Test iterator - ascending order
  58             m.clear();
  59             CPPUNIT_ASSERT( m.empty() );
  60
  61             for ( int i = 0; i < nLimit; ++i ) {
  62                 CPPUNIT_ASSERT( m.insert(i, i) );
  63             }
  64             CPPUNIT_MSG( PrintStat()(m, "Iterator test, ascending insert order") );
  65
  66             nCount = 0;
  67             nPrevKey = 0;
  68             for ( set_iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) {
  69                 CPPUNIT_ASSERT( (*it).first == it->second.m_val );
  70                 CPPUNIT_ASSERT( m.contains( it->first ));
  71                 it->second.m_val = (*it).first * 2;
  72                 ++nCount;
  73                 if ( it != m.begin() ) {
  74                     CPPUNIT_ASSERT( nPrevKey + 1 == it->first );
  75                 }
  76                 nPrevKey = it->first;
  77             }
  78             CPPUNIT_ASSERT( nCount == nLimit );
  79
  80             nCount = 0;
  81             for ( const_set_iterator it = m.cbegin(), itEnd = m.cend(); it != itEnd; ++it ) {
  82                 CPPUNIT_ASSERT( (*it).first * 2 == it->second.m_val );
  83                 ++nCount;
  84                 if ( it != m.cbegin() ) {
  85                     CPPUNIT_ASSERT( nPrevKey + 1 == it->first );
  86                 }
  87                 nPrevKey = it->first;
  88             }
  89             CPPUNIT_ASSERT( nCount == nLimit );
  90
  91             // Test iterator - descending order
  92             m.clear();
  93             CPPUNIT_ASSERT( m.empty() );
  94
  95             for ( int i = nLimit; i > 0; --i ) {
  96                 CPPUNIT_ASSERT( m.insert( i - 1, (i-1) * 2) );
  97             }
  98             CPPUNIT_MSG( PrintStat()(m, "Iterator test, descending insert order") );
  99
 100             nCount = 0;
 101             nPrevKey = 0;
 102             for ( set_iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) {
 103                 CPPUNIT_ASSERT( (*it).first * 2 == it->second.m_val );
 104                 CPPUNIT_ASSERT( m.contains( it->first ));
 105                 it->second.m_val = (*it).first;
 106                 ++nCount;
 107                 if ( it != m.begin() ) {
 108                     CPPUNIT_ASSERT( nPrevKey + 1 == it->first );
 109                 }
 110                 nPrevKey = it->first;
 111             }
 112             CPPUNIT_ASSERT( nCount == nLimit );
 113
 114             nCount = 0;
 115             for ( const_set_iterator it = m.cbegin(), itEnd = m.cend(); it != itEnd; ++it ) {
 116                 CPPUNIT_ASSERT( (*it).first == it->second.m_val );
 117                 ++nCount;
 118                 if ( it != m.cbegin() ) {
 119                     CPPUNIT_ASSERT( nPrevKey + 1 == it->first );
 120                 }
 121                 nPrevKey = it->first;
 122             }
 123             CPPUNIT_ASSERT( nCount == nLimit );
 124
 125             // Test iterator - random order
 126             m.clear();
 127             CPPUNIT_ASSERT( m.empty() );
 128             {
 129                 int nRand[nLimit];
 130                 for ( int i = 0; i < nLimit; ++i ) {
 131                     nRand[i] = i;
 132                 }
 133                 shuffle( nRand, nRand + nLimit );
 134
 135                 for ( int i = 0; i < nLimit; ++i ) {
 136                     CPPUNIT_ASSERT( m.insert( nRand[i], nRand[i]) );
 137                 }
 138                 CPPUNIT_MSG( PrintStat()(m, "Iterator test, random insert order") );
 139             }
 140
 141             nCount = 0;
 142             nPrevKey = 0;
 143             for ( set_iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) {
 144                 CPPUNIT_ASSERT( (*it).first == it->second.m_val );
 145                 CPPUNIT_ASSERT( m.contains( it->first ));
 146                 it->second.m_val = (*it).first * 2;
 147                 ++nCount;
 148                 if ( it != m.begin() ) {
 149                     CPPUNIT_ASSERT( nPrevKey + 1 == it->first );
 150                 }
 151                 nPrevKey = it->first;
 152             }
 153             CPPUNIT_ASSERT( nCount == nLimit );
 154
 155             nCount = 0;
 156             for ( const_set_iterator it = m.cbegin(), itEnd = m.cend(); it != itEnd; ++it ) {
 157                 CPPUNIT_ASSERT( (*it).first * 2 == it->second.m_val );
 158                 ++nCount;
 159                 if ( it != m.cbegin() ) {
 160                     CPPUNIT_ASSERT( nPrevKey + 1 == it->first );
 161                 }
 162                 nPrevKey = it->first;
 163             }
 164             CPPUNIT_ASSERT( nCount == nLimit );
 165
 166             {
 167                 typename Map::guarded_ptr gp;
 168                 int arrItem[nLimit];
 169                 for ( int i = 0; i < nLimit; ++i )
 170                     arrItem[i] = i;
 171                 shuffle( arrItem, arrItem + nLimit );
 172
 173                 typedef base_class::less less;
 174
 175                 // extract/get
 176                 for ( int i = 0; i < nLimit; ++i ) {
 177                     int nKey = arrItem[i];
 178                     gp = m.get( nKey );
 179                     CPPUNIT_ASSERT( gp );
 180                     CPPUNIT_ASSERT( !gp.empty());
 181                     CPPUNIT_CHECK( gp->first == nKey );
 182                     CPPUNIT_CHECK( gp->second.m_val == nKey * 2 );
 183                     gp.release();
 184
 185                     gp = m.extract( nKey );
 186                     CPPUNIT_ASSERT( gp );
 187                     CPPUNIT_ASSERT( !gp.empty());
 188                     CPPUNIT_CHECK( gp->first == nKey );
 189                     CPPUNIT_CHECK( gp->second.m_val == nKey * 2 );
 190                     gp.release();
 191
 192                     gp = m.get( nKey );
 193                     CPPUNIT_CHECK( !gp );
 194                     CPPUNIT_CHECK( !m.extract(nKey));
 195                     CPPUNIT_CHECK( gp.empty());
 196                 }
 197                 CPPUNIT_ASSERT( m.empty());
 198
 199                 for ( int i = 0; i < nLimit; ++i )
 200                     CPPUNIT_ASSERT( m.insert(arrItem[i], arrItem[i]*2) );
 201
 202                 // extract_with/get_with
 203                 for ( int i = 0; i < nLimit; ++i ) {
 204                     int nKey = arrItem[i];
 205                     gp = m.get_with( wrapped_item( nKey ), wrapped_less());
 206                     CPPUNIT_ASSERT( gp );
 207                     CPPUNIT_ASSERT( !gp.empty());
 208                     CPPUNIT_CHECK( gp->first == nKey );
 209                     CPPUNIT_CHECK( gp->second.m_val == nKey * 2 );
 210                     gp.release();
 211
 212                     gp = m.extract_with( wrapped_item( nKey ), wrapped_less());
 213                     CPPUNIT_ASSERT( gp );
 214                     CPPUNIT_ASSERT( !gp.empty());
 215                     CPPUNIT_CHECK( gp->first == nKey );
 216                     CPPUNIT_CHECK( gp->second.m_val == nKey * 2 );
 217                     gp.release();
 218
 219                     gp = m.get_with( wrapped_item( nKey ), wrapped_less() );
 220                     CPPUNIT_CHECK( !gp );
 221                     CPPUNIT_CHECK( !m.extract_with( wrapped_item(nKey), wrapped_less()));
 222                     CPPUNIT_CHECK( gp.empty());
 223                 }
 224                 CPPUNIT_ASSERT( m.empty());
 225
 226                 //extract_min
 227                 for ( int i = 0; i < nLimit; ++i )
 228                     CPPUNIT_ASSERT( m.insert(arrItem[i], arrItem[i]*2) );
 229
 230                 for ( int i = 0; i < nLimit; ++i ) {
 231                     gp = m.extract_min();
 232                     CPPUNIT_ASSERT( gp );
 233                     CPPUNIT_ASSERT( !gp.empty());
 234                     CPPUNIT_CHECK( gp->first == i );
 235                     CPPUNIT_CHECK( gp->second.m_val == i * 2 );
 236                     gp.release();
 237                     CPPUNIT_CHECK( gp.empty());
 238                 }
 239                 CPPUNIT_CHECK( !m.extract_min());
 240
 241                 // extract_max
 242                 for ( int i = 0; i < nLimit; ++i )
 243                     CPPUNIT_ASSERT( m.insert(arrItem[i], arrItem[i]*2) );
 244
 245                 for ( int i = nLimit - 1; i >= 0; --i ) {
 246                     gp = m.extract_max();
 247                     CPPUNIT_ASSERT( gp );
 248                     CPPUNIT_ASSERT( !gp.empty());
 249                     CPPUNIT_CHECK( gp->first == i );
 250                     CPPUNIT_CHECK( gp->second.m_val == i * 2 );
 251                     gp.release();
 252                     CPPUNIT_CHECK( gp.empty());
 253                 }
 254                 CPPUNIT_CHECK( !m.extract_max());
 255                 CPPUNIT_CHECK( gp.empty());
 256                 CPPUNIT_ASSERT( m.empty());
 257             }
 258
 259             CPPUNIT_MSG( PrintStat()(m, nullptr) );
 260         }
 261
 262         template <class Map, typename PrintStat >
 263         void test_nogc()
 264         {
 265             typedef typename Map::iterator          iterator;
 266             typedef typename Map::const_iterator    const_iterator;
 267
 268             Map m;
 269
 270             CPPUNIT_ASSERT( m.empty() );
 271             CPPUNIT_ASSERT( check_size( m, 0 ));
 272
 273             CPPUNIT_ASSERT( m.contains(10) == m.end() );
 274             iterator it = m.insert( 10 );
 275             CPPUNIT_ASSERT( it != m.end() );
 276             CPPUNIT_ASSERT( it->first == 10 );
 277             CPPUNIT_ASSERT( it->second.m_val == 0 );
 278             CPPUNIT_ASSERT( !m.empty() );
 279             CPPUNIT_ASSERT( check_size( m, 1 ));
 280             CPPUNIT_ASSERT( m.contains(10) == it );
 281             CPPUNIT_ASSERT( it->first == 10 );
 282             CPPUNIT_ASSERT( it->second.m_val == 0 );
 283
 284             CPPUNIT_ASSERT( m.contains(100) == m.end() );
 285             it = m.insert( 100, 200 );
 286             CPPUNIT_ASSERT( it != m.end() );
 287             CPPUNIT_ASSERT( !m.empty() );
 288             CPPUNIT_ASSERT( check_size( m, 2 ));
 289             CPPUNIT_ASSERT( m.contains(100) == it );
 290             CPPUNIT_ASSERT( it->first == 100 );
 291             CPPUNIT_ASSERT( it->second.m_val == 200 );
 292
 293             CPPUNIT_ASSERT( m.contains(55) == m.end() );
 294             it = m.insert_with( 55, insert_functor<Map>() );
 295             CPPUNIT_ASSERT( it != m.end() );
 296             CPPUNIT_ASSERT( !m.empty() );
 297             CPPUNIT_ASSERT( check_size( m, 3 ));
 298             CPPUNIT_ASSERT( m.contains(55) == it );
 299             CPPUNIT_ASSERT( it->first == 55 );
 300             CPPUNIT_ASSERT( it->second.m_val == 55 * 3 );
 301
 302             CPPUNIT_ASSERT( m.insert( 55 ) == m.end() );
 303             CPPUNIT_ASSERT( m.insert( 55, 10 ) == m.end() );
 304             CPPUNIT_ASSERT( m.insert_with( 55, insert_functor<Map>()) == m.end() );
 305
 306             CPPUNIT_ASSERT( m.contains(10) != m.end() );
 307             std::pair<iterator, bool> updateResult = m.update( 10, false );
 308             CPPUNIT_ASSERT( updateResult.first != m.end() );
 309             CPPUNIT_ASSERT( !updateResult.second  );
 310             CPPUNIT_ASSERT( !m.empty() );
 311             updateResult.first->second.m_val = updateResult.first->first * 5;
 312             CPPUNIT_ASSERT( check_size( m, 3 ));
 313             CPPUNIT_ASSERT( m.contains(10) == updateResult.first );
 314             it = m.contains( 10, typename base_class::less() );
 315             CPPUNIT_ASSERT( it != m.end() );
 316             CPPUNIT_ASSERT( it->second.m_val == 50 );
 317
 318             CPPUNIT_ASSERT( m.contains(120, base_class::less()) == m.end() );
 319             updateResult = m.update(120, false);
 320             CPPUNIT_ASSERT(updateResult.first == m.end());
 321             CPPUNIT_ASSERT(!updateResult.second);
 322             updateResult = m.update( 120 );
 323             CPPUNIT_ASSERT( updateResult.first != m.end() );
 324             CPPUNIT_ASSERT( updateResult.second  );
 325             CPPUNIT_ASSERT( !m.empty() );
 326             CPPUNIT_ASSERT( check_size( m, 4 ));
 327             updateResult.first->second.m_val = updateResult.first->first * 5;
 328             CPPUNIT_ASSERT( m.contains(120, base_class::less()) == updateResult.first );
 329             it = m.contains(120, base_class::less());
 330             CPPUNIT_ASSERT( it != m.end() );
 331             CPPUNIT_ASSERT( it->second.m_val == 120 * 5 );
 332
 333             // emplace test
 334             it = m.emplace( 151 ) ;  // key = 151,  val = 0
 335             CPPUNIT_ASSERT( it != m.end() );
 336             CPPUNIT_ASSERT( it->first == 151 );
 337             CPPUNIT_ASSERT( it->second.m_val == 0 );
 338
 339             it = m.emplace( 174, 471 ) ; // key == 174, val = 471
 340             CPPUNIT_ASSERT( it != m.end() );
 341             CPPUNIT_ASSERT( it->first == 174 );
 342             CPPUNIT_ASSERT( it->second.m_val == 471 );
 343
 344             it = m.emplace( 190, value_type(91)) ; // key == 190, val = 19
 345             CPPUNIT_ASSERT( it != m.end() );
 346             CPPUNIT_ASSERT( it->first == 190 );
 347             CPPUNIT_ASSERT( it->second.m_val == 91 );
 348
 349             it = m.emplace( 151, 1051 );
 350             CPPUNIT_ASSERT( it == m.end());
 351
 352             it = m.contains( 174 );
 353             CPPUNIT_ASSERT( it != m.end() );
 354             CPPUNIT_ASSERT( it->first == 174 );
 355             CPPUNIT_ASSERT( it->second.m_val == 471 );
 356
 357             it = m.contains( 190 );
 358             CPPUNIT_ASSERT( it != m.end() );
 359             CPPUNIT_ASSERT( it->first == 190 );
 360             CPPUNIT_ASSERT( it->second.m_val == 91 );
 361
 362             it = m.contains( 151 );
 363             CPPUNIT_ASSERT( it != m.end() );
 364             CPPUNIT_ASSERT( it->first == 151 );
 365             CPPUNIT_ASSERT( it->second.m_val == 0 );
 366
 367             m.clear();
 368             CPPUNIT_ASSERT( m.empty() );
 369             CPPUNIT_ASSERT( check_size( m, 0 ));
 370
 371             // get_min test
 372             for ( int i = 500; i > 0; --i ) {
 373                 CPPUNIT_ASSERT( m.insert( i, i * 2 ) != m.end() );
 374
 375                 typename Map::value_type * pVal = m.get_min();
 376                 CPPUNIT_ASSERT( pVal != nullptr );
 377                 CPPUNIT_CHECK( pVal->first == i );
 378                 CPPUNIT_CHECK( pVal->second.m_val == i * 2 );
 379             }
 380             m.clear();
 381             CPPUNIT_ASSERT( m.empty() );
 382             CPPUNIT_ASSERT( check_size( m, 0 ));
 383             CPPUNIT_CHECK( m.get_min() == nullptr );
 384             CPPUNIT_CHECK( m.get_max() == nullptr );
 385
 386             // iterator test
 387
 388             for ( int i = 0; i < 500; ++i ) {
 389                 CPPUNIT_ASSERT( m.insert( i, i * 2 ) != m.end() );
 390
 391                 typename Map::value_type * pVal = m.get_max();
 392                 CPPUNIT_ASSERT( pVal != nullptr );
 393                 CPPUNIT_CHECK( pVal->first == i );
 394                 CPPUNIT_CHECK( pVal->second.m_val == i * 2 );
 395             }
 396             CPPUNIT_ASSERT( check_size( m, 500 ));
 397
 398             for ( iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) {
 399                 CPPUNIT_ASSERT( it->first * 2 == (*it).second.m_val );
 400                 it->second = it->first;
 401             }
 402
 403             Map const& refMap = m;
 404             for ( const_iterator it = refMap.begin(), itEnd = refMap.end(); it != itEnd; ++it ) {
 405                 CPPUNIT_ASSERT( it->first == it->second.m_val );
 406                 CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
 407             }
 408
 409             CPPUNIT_MSG( PrintStat()(m, "SkipListMap statistics") );
 410         }
 411
 412     public:
 413         void SkipList_HP_less();
 414         void SkipList_HP_cmp();
 415         void SkipList_HP_cmpless();
 416         void SkipList_HP_less_stat();
 417         void SkipList_HP_cmp_stat();
 418         void SkipList_HP_cmpless_stat();
 419         void SkipList_HP_xorshift_less();
 420         void SkipList_HP_xorshift_cmp();
 421         void SkipList_HP_xorshift_cmpless();
 422         void SkipList_HP_xorshift_less_stat();
 423         void SkipList_HP_xorshift_cmp_stat();
 424         void SkipList_HP_xorshift_cmpless_stat();
 425         void SkipList_HP_turbopas_less();
 426         void SkipList_HP_turbopas_cmp();
 427         void SkipList_HP_turbopas_cmpless();
 428         void SkipList_HP_turbopas_less_stat();
 429         void SkipList_HP_turbopas_cmp_stat();
 430         void SkipList_HP_turbopas_cmpless_stat();
 431         void SkipList_HP_michaelalloc_less();
 432         void SkipList_HP_michaelalloc_cmp();
 433         void SkipList_HP_michaelalloc_cmpless();
 434         void SkipList_HP_michaelalloc_less_stat();
 435         void SkipList_HP_michaelalloc_cmp_stat();
 436         void SkipList_HP_michaelalloc_cmpless_stat();
 437
 438         void SkipList_DHP_less();
 439         void SkipList_DHP_cmp();
 440         void SkipList_DHP_cmpless();
 441         void SkipList_DHP_less_stat();
 442         void SkipList_DHP_cmp_stat();
 443         void SkipList_DHP_cmpless_stat();
 444         void SkipList_DHP_xorshift_less();
 445         void SkipList_DHP_xorshift_cmp();
 446         void SkipList_DHP_xorshift_cmpless();
 447         void SkipList_DHP_xorshift_less_stat();
 448         void SkipList_DHP_xorshift_cmp_stat();
 449         void SkipList_DHP_xorshift_cmpless_stat();
 450         void SkipList_DHP_turbopas_less();
 451         void SkipList_DHP_turbopas_cmp();
 452         void SkipList_DHP_turbopas_cmpless();
 453         void SkipList_DHP_turbopas_less_stat();
 454         void SkipList_DHP_turbopas_cmp_stat();
 455         void SkipList_DHP_turbopas_cmpless_stat();
 456         void SkipList_DHP_michaelalloc_less();
 457         void SkipList_DHP_michaelalloc_cmp();
 458         void SkipList_DHP_michaelalloc_cmpless();
 459         void SkipList_DHP_michaelalloc_less_stat();
 460         void SkipList_DHP_michaelalloc_cmp_stat();
 461         void SkipList_DHP_michaelalloc_cmpless_stat();
 462
 463         void SkipList_NOGC_less();
 464         void SkipList_NOGC_cmp();
 465         void SkipList_NOGC_cmpless();
 466         void SkipList_NOGC_less_stat();
 467         void SkipList_NOGC_cmp_stat();
 468         void SkipList_NOGC_cmpless_stat();
 469         void SkipList_NOGC_xorshift_less();
 470         void SkipList_NOGC_xorshift_cmp();
 471         void SkipList_NOGC_xorshift_cmpless();
 472         void SkipList_NOGC_xorshift_less_stat();
 473         void SkipList_NOGC_xorshift_cmp_stat();
 474         void SkipList_NOGC_xorshift_cmpless_stat();
 475         void SkipList_NOGC_turbopas_less();
 476         void SkipList_NOGC_turbopas_cmp();
 477         void SkipList_NOGC_turbopas_cmpless();
 478         void SkipList_NOGC_turbopas_less_stat();
 479         void SkipList_NOGC_turbopas_cmp_stat();
 480         void SkipList_NOGC_turbopas_cmpless_stat();
 481         void SkipList_NOGC_michaelalloc_less();
 482         void SkipList_NOGC_michaelalloc_cmp();
 483         void SkipList_NOGC_michaelalloc_cmpless();
 484         void SkipList_NOGC_michaelalloc_less_stat();
 485         void SkipList_NOGC_michaelalloc_cmp_stat();
 486         void SkipList_NOGC_michaelalloc_cmpless_stat();
 487
 488         CPPUNIT_TEST_SUITE(SkipListMapHdrTest)
 489             CPPUNIT_TEST(SkipList_HP_less)
 490             CPPUNIT_TEST(SkipList_HP_cmp)
 491             CPPUNIT_TEST(SkipList_HP_cmpless)
 492             CPPUNIT_TEST(SkipList_HP_less_stat)
 493             CPPUNIT_TEST(SkipList_HP_cmp_stat)
 494             CPPUNIT_TEST(SkipList_HP_cmpless_stat)
 495             CPPUNIT_TEST(SkipList_HP_xorshift_less)
 496             CPPUNIT_TEST(SkipList_HP_xorshift_cmp)
 497             CPPUNIT_TEST(SkipList_HP_xorshift_cmpless)
 498             CPPUNIT_TEST(SkipList_HP_xorshift_less_stat)
 499             CPPUNIT_TEST(SkipList_HP_xorshift_cmp_stat)
 500             CPPUNIT_TEST(SkipList_HP_xorshift_cmpless_stat)
 501             CPPUNIT_TEST(SkipList_HP_turbopas_less)
 502             CPPUNIT_TEST(SkipList_HP_turbopas_cmp)
 503             CPPUNIT_TEST(SkipList_HP_turbopas_cmpless)
 504             CPPUNIT_TEST(SkipList_HP_turbopas_less_stat)
 505             CPPUNIT_TEST(SkipList_HP_turbopas_cmp_stat)
 506             CPPUNIT_TEST(SkipList_HP_turbopas_cmpless_stat)
 507             CPPUNIT_TEST(SkipList_HP_michaelalloc_less)
 508             CPPUNIT_TEST(SkipList_HP_michaelalloc_cmp)
 509             CPPUNIT_TEST(SkipList_HP_michaelalloc_cmpless)
 510             CPPUNIT_TEST(SkipList_HP_michaelalloc_less_stat)
 511             CPPUNIT_TEST(SkipList_HP_michaelalloc_cmp_stat)
 512             CPPUNIT_TEST(SkipList_HP_michaelalloc_cmpless_stat)
 513
 514             CPPUNIT_TEST(SkipList_DHP_less)
 515             CPPUNIT_TEST(SkipList_DHP_cmp)
 516             CPPUNIT_TEST(SkipList_DHP_cmpless)
 517             CPPUNIT_TEST(SkipList_DHP_less_stat)
 518             CPPUNIT_TEST(SkipList_DHP_cmp_stat)
 519             CPPUNIT_TEST(SkipList_DHP_cmpless_stat)
 520             CPPUNIT_TEST(SkipList_DHP_xorshift_less)
 521             CPPUNIT_TEST(SkipList_DHP_xorshift_cmp)
 522             CPPUNIT_TEST(SkipList_DHP_xorshift_cmpless)
 523             CPPUNIT_TEST(SkipList_DHP_xorshift_less_stat)
 524             CPPUNIT_TEST(SkipList_DHP_xorshift_cmp_stat)
 525             CPPUNIT_TEST(SkipList_DHP_xorshift_cmpless_stat)
 526             CPPUNIT_TEST(SkipList_DHP_turbopas_less)
 527             CPPUNIT_TEST(SkipList_DHP_turbopas_cmp)
 528             CPPUNIT_TEST(SkipList_DHP_turbopas_cmpless)
 529             CPPUNIT_TEST(SkipList_DHP_turbopas_less_stat)
 530             CPPUNIT_TEST(SkipList_DHP_turbopas_cmp_stat)
 531             CPPUNIT_TEST(SkipList_DHP_turbopas_cmpless_stat)
 532             CPPUNIT_TEST(SkipList_DHP_michaelalloc_less)
 533             CPPUNIT_TEST(SkipList_DHP_michaelalloc_cmp)
 534             CPPUNIT_TEST(SkipList_DHP_michaelalloc_cmpless)
 535             CPPUNIT_TEST(SkipList_DHP_michaelalloc_less_stat)
 536             CPPUNIT_TEST(SkipList_DHP_michaelalloc_cmp_stat)
 537             CPPUNIT_TEST(SkipList_DHP_michaelalloc_cmpless_stat)
 538
 539             CPPUNIT_TEST(SkipList_NOGC_less)
 540             CPPUNIT_TEST(SkipList_NOGC_cmp)
 541             CPPUNIT_TEST(SkipList_NOGC_cmpless)
 542             CPPUNIT_TEST(SkipList_NOGC_less_stat)
 543             CPPUNIT_TEST(SkipList_NOGC_cmp_stat)
 544             CPPUNIT_TEST(SkipList_NOGC_cmpless_stat)
 545             CPPUNIT_TEST(SkipList_NOGC_xorshift_less)
 546             CPPUNIT_TEST(SkipList_NOGC_xorshift_cmp)
 547             CPPUNIT_TEST(SkipList_NOGC_xorshift_cmpless)
 548             CPPUNIT_TEST(SkipList_NOGC_xorshift_less_stat)
 549             CPPUNIT_TEST(SkipList_NOGC_xorshift_cmp_stat)
 550             CPPUNIT_TEST(SkipList_NOGC_xorshift_cmpless_stat)
 551             CPPUNIT_TEST(SkipList_NOGC_turbopas_less)
 552             CPPUNIT_TEST(SkipList_NOGC_turbopas_cmp)
 553             CPPUNIT_TEST(SkipList_NOGC_turbopas_cmpless)
 554             CPPUNIT_TEST(SkipList_NOGC_turbopas_less_stat)
 555             CPPUNIT_TEST(SkipList_NOGC_turbopas_cmp_stat)
 556             CPPUNIT_TEST(SkipList_NOGC_turbopas_cmpless_stat)
 557             CPPUNIT_TEST(SkipList_NOGC_michaelalloc_less)
 558             CPPUNIT_TEST(SkipList_NOGC_michaelalloc_cmp)
 559             CPPUNIT_TEST(SkipList_NOGC_michaelalloc_cmpless)
 560             CPPUNIT_TEST(SkipList_NOGC_michaelalloc_less_stat)
 561             CPPUNIT_TEST(SkipList_NOGC_michaelalloc_cmp_stat)
 562             CPPUNIT_TEST(SkipList_NOGC_michaelalloc_cmpless_stat)
 563
 564         CPPUNIT_TEST_SUITE_END()
 565
 566     };
 567
 568 } // namespace map
 569
 570 #endif // #ifndef CDSTEST_HDR_SKIPLIST_MAP_H