tests/test-hdr/map/hdr_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_MAP_H
  32 #define CDSTEST_HDR_MAP_H
  33 #include "size_check.h"
  34
  35 #include "cppunit/cppunit_proxy.h"
  36 #include <cds/os/timer.h>
  37 #include <cds/opt/hash.h>
  38 #include <functional>   // ref
  39
  40 namespace cds { namespace container {}}
  41
  42 namespace map {
  43     using misc::check_size;
  44
  45     namespace cc = cds::container;
  46     namespace co = cds::opt;
  47
  48     // MichaelHashSet based on MichaelList
  49     class HashMapHdrTest: public CppUnitMini::TestCase
  50     {
  51     public:
  52         typedef int key_type;
  53
  54         struct value_type {
  55             int m_val;
  56
  57             value_type()
  58                 : m_val(0)
  59             {}
  60
  61             value_type( int n )
  62                 : m_val( n )
  63             {}
  64
  65             value_type( value_type&& v )
  66                 : m_val( v.m_val )
  67             {}
  68
  69             value_type( value_type const& v )
  70                 : m_val( v.m_val )
  71             {}
  72
  73             value_type& operator=( value_type const& v )
  74             {
  75                 m_val = v.m_val;
  76                 return *this;
  77             }
  78         };
  79
  80         typedef std::pair<key_type const, value_type> pair_type;
  81
  82         struct less
  83         {
  84             bool operator ()(int v1, int v2 ) const
  85             {
  86                 return v1 < v2;
  87             }
  88         };
  89
  90         struct cmp {
  91             int operator ()(int v1, int v2 ) const
  92             {
  93                 if ( v1 < v2 )
  94                     return -1;
  95                 return v1 > v2 ? 1 : 0;
  96             }
  97         };
  98
  99         struct equal {
 100             bool operator ()(int v1, int v2 ) const
 101             {
 102                 return v1 == v2;
 103             }
 104         };
 105
 106         struct hash_int {
 107             size_t operator()( int i ) const
 108             {
 109                 return co::v::hash<int>()( i );
 110             }
 111
 112             template <typename T>
 113             size_t operator()( T const& i ) const
 114             {
 115                 return co::v::hash<int>()( i.nKey );
 116             }
 117         };
 118
 119         struct simple_item_counter {
 120             size_t  m_nCount;
 121
 122             simple_item_counter()
 123                 : m_nCount(0)
 124             {}
 125
 126             size_t operator ++()
 127             {
 128                 return ++m_nCount;
 129             }
 130
 131             size_t operator --()
 132             {
 133                 return --m_nCount;
 134             }
 135
 136             void reset()
 137             {
 138                 m_nCount = 0;
 139             }
 140
 141             operator size_t() const
 142             {
 143                 return m_nCount;
 144             }
 145         };
 146
 147         template <typename Map>
 148         struct insert_functor
 149         {
 150             typedef typename Map::value_type pair_type;
 151
 152             // insert ftor
 153             void operator()( pair_type& item )
 154             {
 155                 item.second.m_val = item.first * 3;
 156             }
 157
 158             // update ftor
 159             void operator()( bool bNew, pair_type& item )
 160             {
 161                 if ( bNew )
 162                     item.second.m_val = item.first * 2;
 163                 else
 164                     item.second.m_val = item.first * 5;
 165             }
 166         };
 167
 168         struct check_value {
 169             int     m_nExpected;
 170
 171             check_value( int nExpected )
 172                 : m_nExpected( nExpected )
 173             {}
 174
 175             template <typename T>
 176             void operator ()( T& pair )
 177             {
 178                 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
 179             }
 180             template <typename T, typename Q>
 181             void operator ()( T& pair, Q )
 182             {
 183                 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
 184             }
 185         };
 186
 187         struct extract_functor
 188         {
 189             int *   m_pVal;
 190             void operator()( pair_type const& val )
 191             {
 192                 *m_pVal = val.second.m_val;
 193             }
 194         };
 195
 196         struct other_item {
 197             int nKey;
 198
 199             other_item( int key )
 200                 : nKey(key)
 201             {}
 202         };
 203
 204         struct other_less
 205         {
 206             bool operator ()(int v1, other_item const& v2 ) const
 207             {
 208                 return v1 < v2.nKey;
 209             }
 210             bool operator ()(other_item const& v1, int v2 ) const
 211             {
 212                 return v1.nKey < v2;
 213             }
 214         };
 215
 216
 217         template <class Map>
 218         void test_int()
 219         {
 220             Map m( 100, 4 );
 221
 222             test_int_with(m);
 223
 224             // extract/get test
 225             CPPUNIT_ASSERT( m.empty() );
 226             {
 227                 const int nLimit = 100;
 228                 typename Map::guarded_ptr gp;
 229                 int arrRandom[nLimit];
 230                 for ( int i = 0; i < nLimit; ++i )
 231                     arrRandom[i] = i;
 232                 shuffle( arrRandom, arrRandom + nLimit );
 233
 234                 for ( int i = 0; i < nLimit; ++i )
 235                     CPPUNIT_ASSERT( m.insert( arrRandom[i], arrRandom[i] ));
 236
 237                 for ( int i = 0; i < nLimit; ++i ) {
 238                     int nKey = arrRandom[i];
 239                     gp = m.get( nKey );
 240                     CPPUNIT_ASSERT( gp );
 241                     CPPUNIT_ASSERT( !gp.empty());
 242                     CPPUNIT_CHECK( gp->first == nKey );
 243                     CPPUNIT_CHECK( gp->second.m_val == nKey );
 244                     gp.release();
 245
 246                     gp = m.extract( nKey );
 247                     CPPUNIT_ASSERT( gp );
 248                     CPPUNIT_ASSERT( !gp.empty());
 249                     CPPUNIT_CHECK( gp->first == nKey );
 250                     CPPUNIT_CHECK( gp->second.m_val == nKey );
 251                     gp.release();
 252
 253                     gp = m.get( nKey );
 254                     CPPUNIT_CHECK( !gp );
 255
 256                     CPPUNIT_CHECK( !m.extract(nKey));
 257                     CPPUNIT_CHECK( gp.empty());
 258                 }
 259                 CPPUNIT_ASSERT( m.empty() );
 260
 261                 for ( int i = 0; i < nLimit; ++i )
 262                     CPPUNIT_ASSERT( m.insert( arrRandom[i], arrRandom[i] ));
 263
 264                 for ( int i = 0; i < nLimit; ++i ) {
 265                     int nKey = arrRandom[i];
 266                     gp = m.get_with( other_item( nKey ), other_less() );
 267                     CPPUNIT_ASSERT( gp );
 268                     CPPUNIT_ASSERT( !gp.empty());
 269                     CPPUNIT_CHECK( gp->first == nKey );
 270                     CPPUNIT_CHECK( gp->second.m_val == nKey );
 271                     gp.release();
 272
 273                     gp = m.extract_with( other_item( nKey ), other_less() );
 274                     CPPUNIT_ASSERT( gp );
 275                     CPPUNIT_ASSERT( !gp.empty());
 276                     CPPUNIT_CHECK( gp->first == nKey );
 277                     CPPUNIT_CHECK( gp->second.m_val == nKey );
 278                     gp.release();
 279
 280                     gp = m.get_with( other_item( nKey ), other_less() );
 281                     CPPUNIT_CHECK( !gp );
 282
 283                     CPPUNIT_CHECK( !m.extract_with(other_item(nKey), other_less() ));
 284                     CPPUNIT_CHECK( gp.empty());
 285                 }
 286                 CPPUNIT_ASSERT( m.empty() );
 287             }
 288
 289             // iterator test
 290             test_iter<Map>();
 291         }
 292
 293         template <class Map>
 294         void test_rcu()
 295         {
 296             Map m( 52, 4 );
 297
 298             test_int_with(m);
 299
 300             // extract/get test
 301             {
 302                 typedef typename Map::gc    rcu;
 303                 typedef typename Map::rcu_lock rcu_lock;
 304                 typedef typename Map::value_type value_type;
 305                 typename Map::exempt_ptr ep;
 306
 307                 static size_t const nLimit = 100;
 308                 int arr[nLimit];
 309                 for ( size_t i = 0; i < nLimit; ++i )
 310                     arr[i] = (int) i;
 311                 shuffle( arr, arr + nLimit );
 312
 313                 for ( size_t i = 0; i < nLimit; ++i )
 314                     CPPUNIT_ASSERT( m.insert( arr[i], arr[i] ));
 315
 316                 for ( size_t i = 0; i < nLimit; i += 2 ) {
 317                     value_type * pVal;
 318                     int nKey = arr[i];
 319                     {
 320                         rcu_lock l;
 321                         pVal = m.get( nKey );
 322                         CPPUNIT_ASSERT( pVal != nullptr );
 323                         CPPUNIT_CHECK( pVal->first == nKey );
 324                         CPPUNIT_CHECK( pVal->second.m_val == nKey );
 325
 326                         ep = m.extract( nKey );
 327                         CPPUNIT_ASSERT( ep );
 328                         CPPUNIT_ASSERT( !ep.empty() );
 329                         CPPUNIT_CHECK( pVal->first == ep->first );
 330                         CPPUNIT_CHECK( pVal->second.m_val == ep->second.m_val );
 331                     }
 332                     ep.release();
 333                     {
 334                         rcu_lock l;
 335                         CPPUNIT_CHECK( m.get( nKey ) == nullptr );
 336                         ep = m.extract( nKey );
 337                         CPPUNIT_CHECK( !ep );
 338                         CPPUNIT_CHECK( ep.empty() );
 339
 340                         nKey = arr[i+1];
 341                         pVal = m.get_with( other_item(nKey), other_less() );
 342                         CPPUNIT_ASSERT( pVal != nullptr );
 343                         CPPUNIT_CHECK( pVal->first == nKey );
 344                         CPPUNIT_CHECK( pVal->second.m_val == nKey );
 345
 346                         ep = m.extract_with( other_item( nKey ), other_less() );
 347                         CPPUNIT_ASSERT( ep );
 348                         CPPUNIT_ASSERT( !ep.empty() );
 349                         CPPUNIT_CHECK( pVal->first == ep->first );
 350                         CPPUNIT_CHECK( pVal->second.m_val == (*ep).second.m_val );
 351                     }
 352                     ep.release();
 353                     {
 354                         rcu_lock l;
 355                         CPPUNIT_CHECK( m.get_with( other_item(nKey), other_less() ) == nullptr );
 356                         CPPUNIT_CHECK( !m.extract_with( other_item(nKey), other_less() ));
 357                         CPPUNIT_CHECK( ep.empty() );
 358                     }
 359                 }
 360                 CPPUNIT_CHECK( m.empty() );
 361                 CPPUNIT_CHECK( check_size( m, 0 ));
 362                 {
 363                     rcu_lock l;
 364                     CPPUNIT_CHECK( m.get( int(nLimit / 2) ) == nullptr );
 365                     ep = m.extract( int( nLimit / 2 ) );
 366                     CPPUNIT_CHECK( !ep );
 367                     CPPUNIT_CHECK( ep.empty() );
 368                 }
 369             }
 370
 371             // iterator test
 372             test_iter<Map>();
 373         }
 374
 375         template <class Map>
 376         void test_rcu_michael_list()
 377         {
 378             Map m( 52, 4 );
 379
 380             test_int_with(m);
 381
 382             // extract/get test
 383             {
 384                 typedef typename Map::gc    rcu;
 385                 typedef typename Map::rcu_lock rcu_lock;
 386                 typedef typename Map::value_type value_type;
 387                 typename Map::exempt_ptr ep;
 388                 typename Map::raw_ptr gp;
 389
 390                 static size_t const nLimit = 100;
 391                 int arr[nLimit];
 392                 for ( size_t i = 0; i < nLimit; ++i )
 393                     arr[i] = (int) i;
 394                 shuffle( arr, arr + nLimit );
 395
 396                 for ( size_t i = 0; i < nLimit; ++i )
 397                     CPPUNIT_ASSERT( m.insert( arr[i], arr[i] ));
 398
 399                 for ( size_t i = 0; i < nLimit; i += 2 ) {
 400                     int nKey = arr[i];
 401                     {
 402                         rcu_lock l;
 403                         gp = m.get( nKey );
 404                         CPPUNIT_ASSERT( gp );
 405                         CPPUNIT_CHECK( gp->first == nKey );
 406                         CPPUNIT_CHECK( gp->second.m_val == nKey );
 407                     }
 408                     gp.release();
 409
 410                     ep = m.extract( nKey );
 411                     CPPUNIT_ASSERT( ep );
 412                     CPPUNIT_ASSERT( !ep.empty() );
 413                     CPPUNIT_CHECK( nKey == ep->first );
 414                     CPPUNIT_CHECK( nKey == ep->second.m_val );
 415                     ep.release();
 416
 417                     {
 418                         rcu_lock l;
 419                         CPPUNIT_CHECK( !m.get( nKey ));
 420                     }
 421                     ep = m.extract( nKey );
 422                     CPPUNIT_CHECK( !ep );
 423                     CPPUNIT_CHECK( ep.empty() );
 424
 425                     {
 426                         rcu_lock l;
 427                         nKey = arr[i+1];
 428                         gp = m.get_with( other_item(nKey), other_less() );
 429                         CPPUNIT_ASSERT( gp );
 430                         CPPUNIT_CHECK( gp->first == nKey );
 431                         CPPUNIT_CHECK( gp->second.m_val == nKey );
 432                     }
 433                     gp.release();
 434
 435                     ep = m.extract_with( other_item( nKey ), other_less() );
 436                     CPPUNIT_ASSERT( ep );
 437                     CPPUNIT_ASSERT( !ep.empty() );
 438                     CPPUNIT_CHECK( nKey == ep->first );
 439                     CPPUNIT_CHECK( nKey == (*ep).second.m_val );
 440                     ep.release();
 441
 442                     {
 443                         rcu_lock l;
 444                         CPPUNIT_CHECK( !m.get_with( other_item(nKey), other_less() ));
 445                     }
 446                     CPPUNIT_CHECK( !m.extract_with( other_item(nKey), other_less() ));
 447                     CPPUNIT_CHECK( ep.empty() );
 448                 }
 449                 CPPUNIT_CHECK( m.empty() );
 450                 CPPUNIT_CHECK( check_size( m, 0 ));
 451                 {
 452                     rcu_lock l;
 453                     CPPUNIT_CHECK( !m.get( int(nLimit / 2) ));
 454                 }
 455                 ep = m.extract( int( nLimit / 2 ) );
 456                 CPPUNIT_CHECK( !ep );
 457                 CPPUNIT_CHECK( ep.empty() );
 458             }
 459
 460             // iterator test
 461             test_iter<Map>();
 462         }
 463
 464         template <class Map>
 465         void test_rcu_split_list()
 466         {
 467             test_rcu_michael_list<Map>();
 468         }
 469
 470         template <class Map>
 471         void test_int_with( Map& m )
 472         {
 473             std::pair<bool, bool> updateResult;
 474
 475             // insert
 476             CPPUNIT_ASSERT( m.empty() );
 477             CPPUNIT_ASSERT( check_size( m, 0 ));
 478             CPPUNIT_ASSERT( !m.contains(25) );
 479             CPPUNIT_ASSERT( m.insert( 25 ) )    ;   // value = 0
 480             CPPUNIT_ASSERT( m.contains(25) );
 481             CPPUNIT_ASSERT( !m.empty() );
 482             CPPUNIT_ASSERT( check_size( m, 1 ));
 483             CPPUNIT_ASSERT( m.contains(25) );
 484
 485             CPPUNIT_ASSERT( !m.insert( 25 ) );
 486             CPPUNIT_ASSERT( !m.empty() );
 487             CPPUNIT_ASSERT( check_size( m, 1 ));
 488
 489             CPPUNIT_ASSERT( !m.contains(10, less()) );
 490             CPPUNIT_ASSERT( m.insert( 10, 10 ) );
 491             CPPUNIT_ASSERT( !m.empty() );
 492             CPPUNIT_ASSERT( check_size( m, 2 ));
 493             CPPUNIT_ASSERT( m.contains(10, less()) );
 494
 495             CPPUNIT_ASSERT( !m.insert( 10, 20 ) );
 496             CPPUNIT_ASSERT( !m.empty() );
 497             CPPUNIT_ASSERT( check_size( m, 2 ));
 498
 499             CPPUNIT_ASSERT( !m.contains(30) );
 500             CPPUNIT_ASSERT( m.insert_with( 30, insert_functor<Map>() ) )    ; // value = 90
 501             CPPUNIT_ASSERT( !m.empty() );
 502             CPPUNIT_ASSERT( check_size( m, 3 ));
 503             CPPUNIT_ASSERT( m.contains(30) );
 504
 505             CPPUNIT_ASSERT( !m.insert_with( 10, insert_functor<Map>() ) );
 506             CPPUNIT_ASSERT( !m.insert_with( 25, insert_functor<Map>() ) );
 507             CPPUNIT_ASSERT( !m.insert_with( 30, insert_functor<Map>() ) );
 508
 509             // update (new key)
 510             CPPUNIT_ASSERT( !m.contains(27) );
 511             updateResult = m.update(27, insert_functor<Map>(), false);
 512             CPPUNIT_ASSERT(!updateResult.first);
 513             CPPUNIT_ASSERT(!updateResult.second);
 514             CPPUNIT_ASSERT(!m.contains(27));
 515
 516             updateResult = m.update( 27, insert_functor<Map>() ) ;   // value = 54
 517             CPPUNIT_ASSERT( updateResult.first );
 518             CPPUNIT_ASSERT( updateResult.second );
 519             CPPUNIT_ASSERT( m.contains(27) );
 520
 521             // find test
 522             check_value chk(10);
 523             CPPUNIT_ASSERT( m.find( 10, std::ref(chk) ));
 524             chk.m_nExpected = 0;
 525             CPPUNIT_ASSERT( m.find_with( 25, less(), std::ref( chk ) ) );
 526             chk.m_nExpected = 90;
 527             CPPUNIT_ASSERT( m.find( 30, std::ref( chk ) ) );
 528             chk.m_nExpected = 54;
 529             CPPUNIT_ASSERT( m.find( 27, std::ref( chk ) ) );
 530
 531             updateResult = m.update( 10, insert_functor<Map>() ) ;   // value = 50
 532             CPPUNIT_ASSERT( updateResult.first );
 533             CPPUNIT_ASSERT( !updateResult.second );
 534             chk.m_nExpected = 50;
 535             CPPUNIT_ASSERT( m.find( 10, std::ref( chk ) ) );
 536
 537             // erase test
 538             CPPUNIT_ASSERT( !m.contains(100) );
 539             CPPUNIT_ASSERT( !m.erase( 100 )) ;  // not found
 540
 541             CPPUNIT_ASSERT( m.contains(25) );
 542             CPPUNIT_ASSERT( check_size( m, 4 ));
 543             CPPUNIT_ASSERT( m.erase( 25 ));
 544             CPPUNIT_ASSERT( !m.empty() );
 545             CPPUNIT_ASSERT( check_size( m, 3 ));
 546             CPPUNIT_ASSERT( !m.contains(25) );
 547             CPPUNIT_ASSERT( !m.erase( 25 ));
 548
 549             CPPUNIT_ASSERT( !m.contains(258) );
 550             CPPUNIT_ASSERT( m.insert(258))
 551             CPPUNIT_ASSERT( check_size( m, 4 ));
 552             CPPUNIT_ASSERT( m.contains(258, less()) );
 553             CPPUNIT_ASSERT( m.erase_with( 258, less() ));
 554             CPPUNIT_ASSERT( !m.empty() );
 555             CPPUNIT_ASSERT( check_size( m, 3 ));
 556             CPPUNIT_ASSERT( !m.contains(258) );
 557             CPPUNIT_ASSERT( !m.erase_with( 258, less() ));
 558
 559             int nVal;
 560             extract_functor ext;
 561             ext.m_pVal = &nVal;
 562
 563             CPPUNIT_ASSERT( !m.contains(29) );
 564             CPPUNIT_ASSERT( m.insert(29, 290));
 565             CPPUNIT_ASSERT( check_size( m, 4 ));
 566             CPPUNIT_ASSERT( m.erase_with( 29, less(), std::ref( ext ) ) );
 567             CPPUNIT_ASSERT( !m.empty() );
 568             CPPUNIT_ASSERT( check_size( m, 3 ));
 569             CPPUNIT_ASSERT( nVal == 290 );
 570             nVal = -1;
 571             CPPUNIT_ASSERT( !m.erase_with( 29, less(), std::ref( ext ) ) );
 572             CPPUNIT_ASSERT( nVal == -1 );
 573
 574             CPPUNIT_ASSERT( m.erase( 30, std::ref( ext ) ) );
 575             CPPUNIT_ASSERT( !m.empty() );
 576             CPPUNIT_ASSERT( check_size( m, 2 ));
 577             CPPUNIT_ASSERT( nVal == 90 );
 578             nVal = -1;
 579             CPPUNIT_ASSERT( !m.erase( 30, std::ref( ext ) ) );
 580             CPPUNIT_ASSERT( nVal == -1 );
 581
 582             m.clear();
 583             CPPUNIT_ASSERT( m.empty() );
 584             CPPUNIT_ASSERT( check_size( m, 0 ));
 585
 586             // emplace test
 587             CPPUNIT_ASSERT( m.emplace(126) ) ; // key = 126, val = 0
 588             CPPUNIT_ASSERT( m.emplace(137, 731))    ;   // key = 137, val = 731
 589             CPPUNIT_ASSERT( m.emplace( 149, value_type(941) ))   ;   // key = 149, val = 941
 590
 591             CPPUNIT_ASSERT( !m.empty() );
 592             CPPUNIT_ASSERT( check_size( m, 3 ));
 593
 594             chk.m_nExpected = 0;
 595             CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
 596             chk.m_nExpected = 731;
 597             CPPUNIT_ASSERT( m.find_with( 137, less(), std::ref(chk) ));
 598             chk.m_nExpected = 941;
 599             CPPUNIT_ASSERT( m.find( 149, std::ref(chk) ));
 600
 601             CPPUNIT_ASSERT( !m.emplace(126, 621)) ; // already in map
 602             chk.m_nExpected = 0;
 603             CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
 604             CPPUNIT_ASSERT( !m.empty() );
 605             CPPUNIT_ASSERT( check_size( m, 3 ));
 606
 607             m.clear();
 608             CPPUNIT_ASSERT( m.empty() );
 609             CPPUNIT_ASSERT( check_size( m, 0 ));
 610         }
 611
 612
 613         template <class Map>
 614         void test_int_nogc()
 615         {
 616             typedef typename Map::iterator          iterator;
 617             typedef typename Map::const_iterator    const_iterator;
 618
 619             {
 620                 Map m( 52, 4 );
 621
 622                 CPPUNIT_ASSERT( m.empty() );
 623                 CPPUNIT_ASSERT( check_size( m, 0 ));
 624
 625                 CPPUNIT_ASSERT( m.contains(10) == m.end() );
 626                 iterator it = m.insert( 10 );
 627                 CPPUNIT_ASSERT( it != m.end() );
 628                 CPPUNIT_ASSERT( !m.empty() );
 629                 CPPUNIT_ASSERT( check_size( m, 1 ));
 630                 CPPUNIT_ASSERT( m.contains(10) == it );
 631                 CPPUNIT_ASSERT( it->first == 10 );
 632                 CPPUNIT_ASSERT( it->second.m_val == 0 );
 633
 634                 CPPUNIT_ASSERT( m.contains(100) == m.end() );
 635                 it = m.insert( 100, 200 );
 636                 CPPUNIT_ASSERT( it != m.end() );
 637                 CPPUNIT_ASSERT( !m.empty() );
 638                 CPPUNIT_ASSERT( check_size( m, 2 ));
 639                 CPPUNIT_ASSERT( m.contains(100, less()) == it );
 640                 CPPUNIT_ASSERT( it->first == 100 );
 641                 CPPUNIT_ASSERT( it->second.m_val == 200 );
 642
 643                 CPPUNIT_ASSERT( m.contains(55) == m.end() );
 644                 it = m.insert_with( 55, insert_functor<Map>() );
 645                 CPPUNIT_ASSERT( it != m.end() );
 646                 CPPUNIT_ASSERT( !m.empty() );
 647                 CPPUNIT_ASSERT( check_size( m, 3 ));
 648                 CPPUNIT_ASSERT( m.contains(55) == it );
 649                 CPPUNIT_ASSERT( it->first == 55 );
 650                 CPPUNIT_ASSERT( it->second.m_val == 55 * 3 );
 651
 652                 CPPUNIT_ASSERT( m.insert( 55 ) == m.end() );
 653                 CPPUNIT_ASSERT( m.insert( 55, 10 ) == m.end() );
 654                 CPPUNIT_ASSERT( m.insert_with( 55, insert_functor<Map>()) == m.end() );
 655
 656                 CPPUNIT_ASSERT( m.contains(10) != m.end() );
 657                 std::pair<iterator, bool> updateResult = m.update(10, false);
 658                 CPPUNIT_ASSERT( updateResult.first != m.end() );
 659                 CPPUNIT_ASSERT( !updateResult.second  );
 660                 CPPUNIT_ASSERT( !m.empty() );
 661                 updateResult.first->second.m_val = updateResult.first->first * 5;
 662                 CPPUNIT_ASSERT( check_size( m, 3 ));
 663                 CPPUNIT_ASSERT( m.contains(10) == updateResult.first );
 664                 it = m.contains(10);
 665                 CPPUNIT_ASSERT( it != m.end() );
 666                 CPPUNIT_ASSERT( it->second.m_val == 50 );
 667
 668                 CPPUNIT_ASSERT( m.contains(120) == m.end() );
 669                 updateResult = m.update(120, false);
 670                 CPPUNIT_ASSERT(updateResult.first == m.end());
 671                 CPPUNIT_ASSERT(!updateResult.second);
 672                 updateResult = m.update( 120 );
 673                 CPPUNIT_ASSERT( updateResult.first != m.end() );
 674                 CPPUNIT_ASSERT( updateResult.second  );
 675                 CPPUNIT_ASSERT( !m.empty() );
 676                 CPPUNIT_ASSERT( check_size( m, 4 ));
 677                 updateResult.first->second.m_val = updateResult.first->first * 5;
 678                 CPPUNIT_ASSERT( m.contains(120, less()) == updateResult.first );
 679                 it = m.contains(120, less());
 680                 CPPUNIT_ASSERT( it != m.end() );
 681                 CPPUNIT_ASSERT( it->second.m_val == 120 * 5 );
 682                 CPPUNIT_ASSERT( m.contains(120, less()) == m.contains(120) );
 683
 684                 // emplace test
 685                 it = m.emplace( 151 ) ;  // key = 151,  val = 0
 686                 CPPUNIT_ASSERT( it != m.end() );
 687                 CPPUNIT_ASSERT( it->first == 151 );
 688                 CPPUNIT_ASSERT( it->second.m_val == 0 );
 689
 690                 it = m.emplace( 174, 471 ) ; // key == 174, val = 471
 691                 CPPUNIT_ASSERT( it != m.end() );
 692                 CPPUNIT_ASSERT( it->first == 174 );
 693                 CPPUNIT_ASSERT( it->second.m_val == 471 );
 694
 695                 it = m.emplace( 190, value_type(91)) ; // key == 190, val = 19
 696                 CPPUNIT_ASSERT( it != m.end() );
 697                 CPPUNIT_ASSERT( it->first == 190 );
 698                 CPPUNIT_ASSERT( it->second.m_val == 91 );
 699
 700                 it = m.emplace( 151, 1051 );
 701                 CPPUNIT_ASSERT( it == m.end());
 702
 703                 it = m.contains( 174 );
 704                 CPPUNIT_ASSERT( it != m.end() );
 705                 CPPUNIT_ASSERT( it->first == 174 );
 706                 CPPUNIT_ASSERT( it->second.m_val == 471 );
 707
 708                 it = m.contains( 190 );
 709                 CPPUNIT_ASSERT( it != m.end() );
 710                 CPPUNIT_ASSERT( it->first == 190 );
 711                 CPPUNIT_ASSERT( it->second.m_val == 91 );
 712
 713                 it = m.contains( 151 );
 714                 CPPUNIT_ASSERT( it != m.end() );
 715                 CPPUNIT_ASSERT( it->first == 151 );
 716                 CPPUNIT_ASSERT( it->second.m_val == 0 );
 717             }
 718
 719             // iterator test
 720
 721             {
 722                 Map m( 52, 4 );
 723
 724                 for ( int i = 0; i < 500; ++i ) {
 725                     CPPUNIT_ASSERT( m.insert( i, i * 2 ) != m.end() );
 726                 }
 727                 CPPUNIT_ASSERT( check_size( m, 500 ));
 728
 729                 {
 730                     typename Map::iterator it( m.begin() );
 731                     typename Map::const_iterator cit( m.cbegin() );
 732                     CPPUNIT_CHECK( it == cit );
 733                     CPPUNIT_CHECK( it != m.end() );
 734                     CPPUNIT_CHECK( it != m.cend() );
 735                     CPPUNIT_CHECK( cit != m.end() );
 736                     CPPUNIT_CHECK( cit != m.cend() );
 737                     ++it;
 738                     CPPUNIT_CHECK( it != cit );
 739                     CPPUNIT_CHECK( it != m.end() );
 740                     CPPUNIT_CHECK( it != m.cend() );
 741                     CPPUNIT_CHECK( cit != m.end() );
 742                     CPPUNIT_CHECK( cit != m.cend() );
 743                     ++cit;
 744                     CPPUNIT_CHECK( it == cit );
 745                     CPPUNIT_CHECK( it != m.end() );
 746                     CPPUNIT_CHECK( it != m.cend() );
 747                     CPPUNIT_CHECK( cit != m.end() );
 748                     CPPUNIT_CHECK( cit != m.cend() );
 749                 }
 750
 751
 752                 for ( iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) {
 753                     iterator it2 = it;
 754                     CPPUNIT_CHECK( it2 == it );
 755                     CPPUNIT_CHECK( it2 != itEnd );
 756                     CPPUNIT_ASSERT( it->first * 2 == (*it).second.m_val );
 757                     it->second = it->first;
 758                 }
 759
 760                 Map const& refMap = m;
 761                 for ( const_iterator it = refMap.begin(), itEnd = refMap.end(); it != itEnd; ++it ) {
 762                     CPPUNIT_ASSERT( it->first == it->second.m_val );
 763                     CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
 764                 }
 765             }
 766         }
 767
 768         template <class Map>
 769         void test_int_nogc_unordered()
 770         {
 771             typedef typename Map::iterator          iterator;
 772             typedef typename Map::const_iterator    const_iterator;
 773
 774             {
 775                 Map m( 52, 4 );
 776
 777                 CPPUNIT_ASSERT( m.empty() );
 778                 CPPUNIT_ASSERT( check_size( m, 0 ));
 779
 780                 CPPUNIT_ASSERT( m.contains(10) == m.end() );
 781                 iterator it = m.insert( 10 );
 782                 CPPUNIT_ASSERT( it != m.end() );
 783                 CPPUNIT_ASSERT( !m.empty() );
 784                 CPPUNIT_ASSERT( check_size( m, 1 ));
 785                 CPPUNIT_ASSERT( m.contains(10) == it );
 786                 CPPUNIT_ASSERT( it->first == 10 );
 787                 CPPUNIT_ASSERT( it->second.m_val == 0 );
 788
 789                 CPPUNIT_ASSERT( m.contains(100) == m.end() );
 790                 it = m.insert( 100, 200 );
 791                 CPPUNIT_ASSERT( it != m.end() );
 792                 CPPUNIT_ASSERT( !m.empty() );
 793                 CPPUNIT_ASSERT( check_size( m, 2 ));
 794                 CPPUNIT_ASSERT( m.contains(100, equal()) == it );
 795                 CPPUNIT_ASSERT( it->first == 100 );
 796                 CPPUNIT_ASSERT( it->second.m_val == 200 );
 797
 798                 CPPUNIT_ASSERT( m.contains(55) == m.end() );
 799                 it = m.insert_with( 55, insert_functor<Map>() );
 800                 CPPUNIT_ASSERT( it != m.end() );
 801                 CPPUNIT_ASSERT( !m.empty() );
 802                 CPPUNIT_ASSERT( check_size( m, 3 ));
 803                 CPPUNIT_ASSERT( m.contains(55) == it );
 804                 CPPUNIT_ASSERT( it->first == 55 );
 805                 CPPUNIT_ASSERT( it->second.m_val == 55 * 3 );
 806
 807                 CPPUNIT_ASSERT( m.insert( 55 ) == m.end() );
 808                 CPPUNIT_ASSERT( m.insert( 55, 10 ) == m.end() );
 809                 CPPUNIT_ASSERT( m.insert_with( 55, insert_functor<Map>()) == m.end() );
 810
 811                 CPPUNIT_ASSERT( m.contains(10) != m.end() );
 812                 std::pair<iterator, bool> updateResult = m.update( 10 );
 813                 CPPUNIT_ASSERT( updateResult.first != m.end() );
 814                 CPPUNIT_ASSERT( !updateResult.second  );
 815                 CPPUNIT_ASSERT( !m.empty() );
 816                 updateResult.first->second.m_val = updateResult.first->first * 5;
 817                 CPPUNIT_ASSERT( check_size( m, 3 ));
 818                 CPPUNIT_ASSERT( m.contains(10) == updateResult.first );
 819                 it = m.contains(10);
 820                 CPPUNIT_ASSERT( it != m.end() );
 821                 CPPUNIT_ASSERT( it->second.m_val == 50 );
 822
 823                 CPPUNIT_ASSERT( m.contains(120) == m.end() );
 824                 updateResult = m.update(120, false);
 825                 CPPUNIT_ASSERT(updateResult.first == m.end());
 826                 CPPUNIT_ASSERT(!updateResult.second);
 827                 updateResult = m.update( 120, true );
 828                 CPPUNIT_ASSERT( updateResult.first != m.end() );
 829                 CPPUNIT_ASSERT( updateResult.second  );
 830                 CPPUNIT_ASSERT( !m.empty() );
 831                 CPPUNIT_ASSERT( check_size( m, 4 ));
 832                 updateResult.first->second.m_val = updateResult.first->first * 5;
 833                 CPPUNIT_ASSERT( m.contains(120, equal()) == updateResult.first );
 834                 it = m.contains(120, equal());
 835                 CPPUNIT_ASSERT( it != m.end() );
 836                 CPPUNIT_ASSERT( it->second.m_val == 120 * 5 );
 837                 CPPUNIT_ASSERT( m.contains(120, equal()) == m.contains(120) );
 838
 839                 // emplace test
 840                 it = m.emplace( 151 ) ;  // key = 151,  val = 0
 841                 CPPUNIT_ASSERT( it != m.end() );
 842                 CPPUNIT_ASSERT( it->first == 151 );
 843                 CPPUNIT_ASSERT( it->second.m_val == 0 );
 844
 845                 it = m.emplace( 174, 471 ) ; // key == 174, val = 471
 846                 CPPUNIT_ASSERT( it != m.end() );
 847                 CPPUNIT_ASSERT( it->first == 174 );
 848                 CPPUNIT_ASSERT( it->second.m_val == 471 );
 849
 850                 it = m.emplace( 190, value_type(91)) ; // key == 190, val = 19
 851                 CPPUNIT_ASSERT( it != m.end() );
 852                 CPPUNIT_ASSERT( it->first == 190 );
 853                 CPPUNIT_ASSERT( it->second.m_val == 91 );
 854
 855                 it = m.emplace( 151, 1051 );
 856                 CPPUNIT_ASSERT( it == m.end());
 857
 858                 it = m.contains( 174 );
 859                 CPPUNIT_ASSERT( it != m.end() );
 860                 CPPUNIT_ASSERT( it->first == 174 );
 861                 CPPUNIT_ASSERT( it->second.m_val == 471 );
 862
 863                 it = m.contains( 190 );
 864                 CPPUNIT_ASSERT( it != m.end() );
 865                 CPPUNIT_ASSERT( it->first == 190 );
 866                 CPPUNIT_ASSERT( it->second.m_val == 91 );
 867
 868                 it = m.contains( 151 );
 869                 CPPUNIT_ASSERT( it != m.end() );
 870                 CPPUNIT_ASSERT( it->first == 151 );
 871                 CPPUNIT_ASSERT( it->second.m_val == 0 );
 872             }
 873
 874             // iterator test
 875
 876             {
 877                 Map m( 52, 4 );
 878
 879                 for ( int i = 0; i < 500; ++i ) {
 880                     CPPUNIT_ASSERT( m.insert( i, i * 2 ) != m.end() );
 881                 }
 882                 CPPUNIT_ASSERT( check_size( m, 500 ));
 883
 884                 {
 885                     typename Map::iterator it( m.begin() );
 886                     typename Map::const_iterator cit( m.cbegin() );
 887                     CPPUNIT_CHECK( it == cit );
 888                     CPPUNIT_CHECK( it != m.end() );
 889                     CPPUNIT_CHECK( it != m.cend() );
 890                     CPPUNIT_CHECK( cit != m.end() );
 891                     CPPUNIT_CHECK( cit != m.cend() );
 892                     ++it;
 893                     CPPUNIT_CHECK( it != cit );
 894                     CPPUNIT_CHECK( it != m.end() );
 895                     CPPUNIT_CHECK( it != m.cend() );
 896                     CPPUNIT_CHECK( cit != m.end() );
 897                     CPPUNIT_CHECK( cit != m.cend() );
 898                     ++cit;
 899                     CPPUNIT_CHECK( it == cit );
 900                     CPPUNIT_CHECK( it != m.end() );
 901                     CPPUNIT_CHECK( it != m.cend() );
 902                     CPPUNIT_CHECK( cit != m.end() );
 903                     CPPUNIT_CHECK( cit != m.cend() );
 904                 }
 905
 906
 907                 for ( iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) {
 908                     iterator it2 = it;
 909                     CPPUNIT_CHECK( it2 == it );
 910                     CPPUNIT_CHECK( it2 != itEnd );
 911                     CPPUNIT_ASSERT( it->first * 2 == (*it).second.m_val );
 912                     it->second = it->first;
 913                 }
 914
 915                 Map const& refMap = m;
 916                 for ( const_iterator it = refMap.begin(), itEnd = refMap.end(); it != itEnd; ++it ) {
 917                     CPPUNIT_ASSERT( it->first == it->second.m_val );
 918                     CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
 919                 }
 920             }
 921         }
 922
 923         template <class Map>
 924         void test_iter()
 925         {
 926             typedef typename Map::iterator          iterator;
 927             typedef typename Map::const_iterator    const_iterator;
 928
 929             Map s( 100, 4 );
 930
 931             const int nMaxCount = 500;
 932             for ( int i = 0; i < nMaxCount; ++i ) {
 933                 CPPUNIT_ASSERT( s.insert( i, i * 2 ));
 934             }
 935
 936             {
 937                 typename Map::iterator it( s.begin() );
 938                 typename Map::const_iterator cit( s.cbegin() );
 939                 CPPUNIT_CHECK( it == cit );
 940                 CPPUNIT_CHECK( it != s.end() );
 941                 CPPUNIT_CHECK( it != s.cend() );
 942                 CPPUNIT_CHECK( cit != s.end() );
 943                 CPPUNIT_CHECK( cit != s.cend() );
 944                 ++it;
 945                 CPPUNIT_CHECK( it != cit );
 946                 CPPUNIT_CHECK( it != s.end() );
 947                 CPPUNIT_CHECK( it != s.cend() );
 948                 CPPUNIT_CHECK( cit != s.end() );
 949                 CPPUNIT_CHECK( cit != s.cend() );
 950                 ++cit;
 951                 CPPUNIT_CHECK( it == cit );
 952                 CPPUNIT_CHECK( it != s.end() );
 953                 CPPUNIT_CHECK( it != s.cend() );
 954                 CPPUNIT_CHECK( cit != s.end() );
 955                 CPPUNIT_CHECK( cit != s.cend() );
 956             }
 957
 958             int nCount = 0;
 959             for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 960                 CPPUNIT_ASSERT( it->first * 2 == it->second.m_val );
 961                 CPPUNIT_ASSERT( (*it).first * 2 == (*it).second.m_val );
 962                 it->second.m_val = it->first;
 963                 ++nCount;
 964             }
 965             CPPUNIT_ASSERT( nCount == nMaxCount );
 966
 967             Map const& refSet = s;
 968             nCount = 0;
 969             for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
 970                 CPPUNIT_ASSERT( it->first == it->second.m_val );
 971                 CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
 972                 ++nCount;
 973             }
 974             CPPUNIT_ASSERT( nCount == nMaxCount );
 975         }
 976
 977
 978         void Michael_HP_cmp();
 979         void Michael_HP_less();
 980         void Michael_HP_cmpmix();
 981
 982         void Michael_DHP_cmp();
 983         void Michael_DHP_less();
 984         void Michael_DHP_cmpmix();
 985
 986         void Michael_RCU_GPI_cmp();
 987         void Michael_RCU_GPI_less();
 988         void Michael_RCU_GPI_cmpmix();
 989
 990         void Michael_RCU_GPB_cmp();
 991         void Michael_RCU_GPB_less();
 992         void Michael_RCU_GPB_cmpmix();
 993
 994         void Michael_RCU_GPT_cmp();
 995         void Michael_RCU_GPT_less();
 996         void Michael_RCU_GPT_cmpmix();
 997
 998         void Michael_RCU_SHB_cmp();
 999         void Michael_RCU_SHB_less();
1000         void Michael_RCU_SHB_cmpmix();
1001
1002         void Michael_RCU_SHT_cmp();
1003         void Michael_RCU_SHT_less();
1004         void Michael_RCU_SHT_cmpmix();
1005
1006         void Michael_nogc_cmp();
1007         void Michael_nogc_less();
1008         void Michael_nogc_cmpmix();
1009
1010         void Lazy_HP_cmp();
1011         void Lazy_HP_less();
1012         void Lazy_HP_cmpmix();
1013
1014         void Lazy_DHP_cmp();
1015         void Lazy_DHP_less();
1016         void Lazy_DHP_cmpmix();
1017
1018         void Lazy_RCU_GPI_cmp();
1019         void Lazy_RCU_GPI_less();
1020         void Lazy_RCU_GPI_cmpmix();
1021
1022         void Lazy_RCU_GPB_cmp();
1023         void Lazy_RCU_GPB_less();
1024         void Lazy_RCU_GPB_cmpmix();
1025
1026         void Lazy_RCU_GPT_cmp();
1027         void Lazy_RCU_GPT_less();
1028         void Lazy_RCU_GPT_cmpmix();
1029
1030         void Lazy_RCU_SHB_cmp();
1031         void Lazy_RCU_SHB_less();
1032         void Lazy_RCU_SHB_cmpmix();
1033
1034         void Lazy_RCU_SHT_cmp();
1035         void Lazy_RCU_SHT_less();
1036         void Lazy_RCU_SHT_cmpmix();
1037
1038         void Lazy_nogc_cmp();
1039         void Lazy_nogc_less();
1040         void Lazy_nogc_equal();
1041         void Lazy_nogc_cmpmix();
1042
1043         void Split_HP_cmp();
1044         void Split_HP_less();
1045         void Split_HP_cmpmix();
1046         void Split_HP_cmpmix_stat();
1047
1048         void Split_DHP_cmp();
1049         void Split_DHP_less();
1050         void Split_DHP_cmpmix();
1051         void Split_DHP_cmpmix_stat();
1052
1053         void Split_RCU_GPI_cmp();
1054         void Split_RCU_GPI_less();
1055         void Split_RCU_GPI_cmpmix();
1056         void Split_RCU_GPI_cmpmix_stat();
1057
1058         void Split_RCU_GPB_cmp();
1059         void Split_RCU_GPB_less();
1060         void Split_RCU_GPB_cmpmix();
1061         void Split_RCU_GPB_cmpmix_stat();
1062
1063         void Split_RCU_GPT_cmp();
1064         void Split_RCU_GPT_less();
1065         void Split_RCU_GPT_cmpmix();
1066         void Split_RCU_GPT_cmpmix_stat();
1067
1068         void Split_RCU_SHB_cmp();
1069         void Split_RCU_SHB_less();
1070         void Split_RCU_SHB_cmpmix();
1071         void Split_RCU_SHB_cmpmix_stat();
1072
1073         void Split_RCU_SHT_cmp();
1074         void Split_RCU_SHT_less();
1075         void Split_RCU_SHT_cmpmix();
1076         void Split_RCU_SHT_cmpmix_stat();
1077
1078         void Split_nogc_cmp();
1079         void Split_nogc_less();
1080         void Split_nogc_cmpmix();
1081         void Split_nogc_cmpmix_stat();
1082
1083         void Split_Lazy_HP_cmp();
1084         void Split_Lazy_HP_less();
1085         void Split_Lazy_HP_cmpmix();
1086         void Split_Lazy_HP_cmpmix_stat();
1087
1088         void Split_Lazy_DHP_cmp();
1089         void Split_Lazy_DHP_less();
1090         void Split_Lazy_DHP_cmpmix();
1091         void Split_Lazy_DHP_cmpmix_stat();
1092
1093         void Split_Lazy_RCU_GPI_cmp();
1094         void Split_Lazy_RCU_GPI_less();
1095         void Split_Lazy_RCU_GPI_cmpmix();
1096         void Split_Lazy_RCU_GPI_cmpmix_stat();
1097
1098         void Split_Lazy_RCU_GPB_cmp();
1099         void Split_Lazy_RCU_GPB_less();
1100         void Split_Lazy_RCU_GPB_cmpmix();
1101         void Split_Lazy_RCU_GPB_cmpmix_stat();
1102
1103         void Split_Lazy_RCU_GPT_cmp();
1104         void Split_Lazy_RCU_GPT_less();
1105         void Split_Lazy_RCU_GPT_cmpmix();
1106         void Split_Lazy_RCU_GPT_cmpmix_stat();
1107
1108         void Split_Lazy_RCU_SHB_cmp();
1109         void Split_Lazy_RCU_SHB_less();
1110         void Split_Lazy_RCU_SHB_cmpmix();
1111         void Split_Lazy_RCU_SHB_cmpmix_stat();
1112
1113         void Split_Lazy_RCU_SHT_cmp();
1114         void Split_Lazy_RCU_SHT_less();
1115         void Split_Lazy_RCU_SHT_cmpmix();
1116         void Split_Lazy_RCU_SHT_cmpmix_stat();
1117
1118         void Split_Lazy_nogc_cmp();
1119         void Split_Lazy_nogc_less();
1120         void Split_Lazy_nogc_cmpmix();
1121         void Split_Lazy_nogc_cmpmix_stat();
1122
1123         CPPUNIT_TEST_SUITE(HashMapHdrTest)
1124             CPPUNIT_TEST(Michael_HP_cmp)
1125             CPPUNIT_TEST(Michael_HP_less)
1126             CPPUNIT_TEST(Michael_HP_cmpmix)
1127
1128             CPPUNIT_TEST(Michael_DHP_cmp)
1129             CPPUNIT_TEST(Michael_DHP_less)
1130             CPPUNIT_TEST(Michael_DHP_cmpmix)
1131
1132             CPPUNIT_TEST(Michael_RCU_GPI_cmp)
1133             CPPUNIT_TEST(Michael_RCU_GPI_less)
1134             CPPUNIT_TEST(Michael_RCU_GPI_cmpmix)
1135
1136             CPPUNIT_TEST(Michael_RCU_GPB_cmp)
1137             CPPUNIT_TEST(Michael_RCU_GPB_less)
1138             CPPUNIT_TEST(Michael_RCU_GPB_cmpmix)
1139
1140             CPPUNIT_TEST(Michael_RCU_SHT_cmp)
1141             CPPUNIT_TEST(Michael_RCU_SHT_less)
1142             CPPUNIT_TEST(Michael_RCU_SHT_cmpmix)
1143
1144             CPPUNIT_TEST(Michael_RCU_SHB_cmp)
1145             CPPUNIT_TEST(Michael_RCU_SHB_less)
1146             CPPUNIT_TEST(Michael_RCU_SHB_cmpmix)
1147
1148             CPPUNIT_TEST(Michael_RCU_GPT_cmp)
1149             CPPUNIT_TEST(Michael_RCU_GPT_less)
1150             CPPUNIT_TEST(Michael_RCU_GPT_cmpmix)
1151
1152             CPPUNIT_TEST(Michael_nogc_cmp)
1153             CPPUNIT_TEST(Michael_nogc_less)
1154             CPPUNIT_TEST(Michael_nogc_cmpmix)
1155
1156             CPPUNIT_TEST(Lazy_HP_cmp)
1157             CPPUNIT_TEST(Lazy_HP_less)
1158             CPPUNIT_TEST(Lazy_HP_cmpmix)
1159
1160             CPPUNIT_TEST(Lazy_DHP_cmp)
1161             CPPUNIT_TEST(Lazy_DHP_less)
1162             CPPUNIT_TEST(Lazy_DHP_cmpmix)
1163
1164             CPPUNIT_TEST(Lazy_RCU_GPI_cmp)
1165             CPPUNIT_TEST(Lazy_RCU_GPI_less)
1166             CPPUNIT_TEST(Lazy_RCU_GPI_cmpmix)
1167
1168             CPPUNIT_TEST(Lazy_RCU_GPB_cmp)
1169             CPPUNIT_TEST(Lazy_RCU_GPB_less)
1170             CPPUNIT_TEST(Lazy_RCU_GPB_cmpmix)
1171
1172             CPPUNIT_TEST(Lazy_RCU_GPT_cmp)
1173             CPPUNIT_TEST(Lazy_RCU_GPT_less)
1174             CPPUNIT_TEST(Lazy_RCU_GPT_cmpmix)
1175
1176             CPPUNIT_TEST(Lazy_RCU_SHB_cmp)
1177             CPPUNIT_TEST(Lazy_RCU_SHB_less)
1178             CPPUNIT_TEST(Lazy_RCU_SHB_cmpmix)
1179
1180             CPPUNIT_TEST(Lazy_RCU_SHT_cmp)
1181             CPPUNIT_TEST(Lazy_RCU_SHT_less)
1182             CPPUNIT_TEST(Lazy_RCU_SHT_cmpmix)
1183
1184             CPPUNIT_TEST(Lazy_nogc_cmp)
1185             CPPUNIT_TEST(Lazy_nogc_less)
1186             CPPUNIT_TEST(Lazy_nogc_equal)
1187             CPPUNIT_TEST(Lazy_nogc_cmpmix)
1188
1189             CPPUNIT_TEST(Split_HP_cmp)
1190             CPPUNIT_TEST(Split_HP_less)
1191             CPPUNIT_TEST(Split_HP_cmpmix)
1192             CPPUNIT_TEST( Split_HP_cmpmix_stat )
1193
1194             CPPUNIT_TEST(Split_DHP_cmp)
1195             CPPUNIT_TEST(Split_DHP_less)
1196             CPPUNIT_TEST(Split_DHP_cmpmix)
1197             CPPUNIT_TEST( Split_DHP_cmpmix_stat )
1198
1199             CPPUNIT_TEST(Split_RCU_GPI_cmp)
1200             CPPUNIT_TEST(Split_RCU_GPI_less)
1201             CPPUNIT_TEST(Split_RCU_GPI_cmpmix)
1202             CPPUNIT_TEST( Split_RCU_GPI_cmpmix_stat )
1203
1204             CPPUNIT_TEST(Split_RCU_GPB_cmp)
1205             CPPUNIT_TEST(Split_RCU_GPB_less)
1206             CPPUNIT_TEST(Split_RCU_GPB_cmpmix)
1207             CPPUNIT_TEST( Split_RCU_GPB_cmpmix_stat )
1208
1209             CPPUNIT_TEST(Split_RCU_GPT_cmp)
1210             CPPUNIT_TEST(Split_RCU_GPT_less)
1211             CPPUNIT_TEST(Split_RCU_GPT_cmpmix)
1212             CPPUNIT_TEST( Split_RCU_GPT_cmpmix_stat )
1213
1214             CPPUNIT_TEST(Split_RCU_SHB_cmp)
1215             CPPUNIT_TEST(Split_RCU_SHB_less)
1216             CPPUNIT_TEST(Split_RCU_SHB_cmpmix)
1217             CPPUNIT_TEST( Split_RCU_SHB_cmpmix_stat )
1218
1219             CPPUNIT_TEST(Split_RCU_SHT_cmp)
1220             CPPUNIT_TEST(Split_RCU_SHT_less)
1221             CPPUNIT_TEST(Split_RCU_SHT_cmpmix)
1222             CPPUNIT_TEST( Split_RCU_SHT_cmpmix_stat )
1223
1224             CPPUNIT_TEST(Split_nogc_cmp)
1225             CPPUNIT_TEST(Split_nogc_less)
1226             CPPUNIT_TEST(Split_nogc_cmpmix)
1227             CPPUNIT_TEST( Split_nogc_cmpmix_stat )
1228
1229             CPPUNIT_TEST(Split_Lazy_HP_cmp)
1230             CPPUNIT_TEST(Split_Lazy_HP_less)
1231             CPPUNIT_TEST(Split_Lazy_HP_cmpmix)
1232             CPPUNIT_TEST( Split_Lazy_HP_cmpmix_stat )
1233
1234             CPPUNIT_TEST(Split_Lazy_DHP_cmp)
1235             CPPUNIT_TEST(Split_Lazy_DHP_less)
1236             CPPUNIT_TEST(Split_Lazy_DHP_cmpmix)
1237             CPPUNIT_TEST( Split_Lazy_DHP_cmpmix_stat )
1238
1239             CPPUNIT_TEST(Split_Lazy_RCU_GPI_cmp)
1240             CPPUNIT_TEST(Split_Lazy_RCU_GPI_less)
1241             CPPUNIT_TEST(Split_Lazy_RCU_GPI_cmpmix)
1242             CPPUNIT_TEST( Split_Lazy_RCU_GPI_cmpmix_stat )
1243
1244             CPPUNIT_TEST(Split_Lazy_RCU_GPB_cmp)
1245             CPPUNIT_TEST(Split_Lazy_RCU_GPB_less)
1246             CPPUNIT_TEST(Split_Lazy_RCU_GPB_cmpmix)
1247             CPPUNIT_TEST( Split_Lazy_RCU_GPB_cmpmix_stat )
1248
1249             CPPUNIT_TEST(Split_Lazy_RCU_GPT_cmp)
1250             CPPUNIT_TEST(Split_Lazy_RCU_GPT_less)
1251             CPPUNIT_TEST(Split_Lazy_RCU_GPT_cmpmix)
1252             CPPUNIT_TEST( Split_Lazy_RCU_GPT_cmpmix_stat )
1253
1254             CPPUNIT_TEST(Split_Lazy_RCU_SHB_cmp)
1255             CPPUNIT_TEST(Split_Lazy_RCU_SHB_less)
1256             CPPUNIT_TEST(Split_Lazy_RCU_SHB_cmpmix)
1257             CPPUNIT_TEST( Split_Lazy_RCU_SHB_cmpmix_stat )
1258
1259             CPPUNIT_TEST(Split_Lazy_RCU_SHT_cmp)
1260             CPPUNIT_TEST(Split_Lazy_RCU_SHT_less)
1261             CPPUNIT_TEST(Split_Lazy_RCU_SHT_cmpmix)
1262             CPPUNIT_TEST( Split_Lazy_RCU_SHT_cmpmix_stat )
1263
1264             CPPUNIT_TEST(Split_Lazy_nogc_cmp)
1265             CPPUNIT_TEST(Split_Lazy_nogc_less)
1266             CPPUNIT_TEST(Split_Lazy_nogc_cmpmix)
1267             CPPUNIT_TEST( Split_Lazy_nogc_cmpmix_stat )
1268             CPPUNIT_TEST_SUITE_END()
1269
1270     };
1271 }   // namespace map
1272
1273 #endif // #ifndef CDSTEST_HDR_MAP_H