tests/test-hdr/map/hdr_map.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDSTEST_HDR_MAP_H
   4 #define __CDSTEST_HDR_MAP_H
   5 #include "size_check.h"
   6
   7 #include "cppunit/cppunit_proxy.h"
   8 #include <cds/os/timer.h>
   9 #include <cds/opt/hash.h>
  10 #include <cds/ref.h>
  11 #include <algorithm>    // random_shuffle
  12
  13 namespace cds { namespace container {}}
  14
  15 namespace map {
  16     using misc::check_size;
  17
  18     namespace cc = cds::container;
  19     namespace co = cds::opt;
  20
  21     // MichaelHashSet based on MichaelList
  22     class HashMapHdrTest: public CppUnitMini::TestCase
  23     {
  24     public:
  25         typedef int key_type;
  26
  27         struct value_type {
  28             int m_val;
  29
  30             value_type()
  31                 : m_val(0)
  32             {}
  33
  34             value_type( int n )
  35                 : m_val( n )
  36             {}
  37
  38             value_type( value_type&& v )
  39                 : m_val( v.m_val )
  40             {}
  41
  42             value_type( value_type const& v )
  43                 : m_val( v.m_val )
  44             {}
  45
  46             value_type& operator=( value_type const& v )
  47             {
  48                 m_val = v.m_val;
  49                 return *this;
  50             }
  51         };
  52
  53         typedef std::pair<key_type const, value_type> pair_type;
  54
  55         struct less
  56         {
  57             bool operator ()(int v1, int v2 ) const
  58             {
  59                 return v1 < v2;
  60             }
  61         };
  62
  63         struct cmp {
  64             int operator ()(int v1, int v2 ) const
  65             {
  66                 if ( v1 < v2 )
  67                     return -1;
  68                 return v1 > v2 ? 1 : 0;
  69             }
  70         };
  71
  72         struct equal {
  73             bool operator ()(int v1, int v2 ) const
  74             {
  75                 return v1 == v2;
  76             }
  77         };
  78
  79         struct hash_int {
  80             size_t operator()( int i ) const
  81             {
  82                 return co::v::hash<int>()( i );
  83             }
  84
  85             template <typename T>
  86             size_t operator()( T const& i ) const
  87             {
  88                 return co::v::hash<int>()( i.nKey );
  89             }
  90         };
  91
  92         struct simple_item_counter {
  93             size_t  m_nCount;
  94
  95             simple_item_counter()
  96                 : m_nCount(0)
  97             {}
  98
  99             size_t operator ++()
 100             {
 101                 return ++m_nCount;
 102             }
 103
 104             size_t operator --()
 105             {
 106                 return --m_nCount;
 107             }
 108
 109             void reset()
 110             {
 111                 m_nCount = 0;
 112             }
 113
 114             operator size_t() const
 115             {
 116                 return m_nCount;
 117             }
 118         };
 119
 120         template <typename Map>
 121         struct insert_functor
 122         {
 123             typedef typename Map::value_type pair_type;
 124
 125             // insert ftor
 126             void operator()( pair_type& item )
 127             {
 128                 item.second.m_val = item.first * 3;
 129             }
 130
 131             // ensure ftor
 132             void operator()( bool bNew, pair_type& item )
 133             {
 134                 if ( bNew )
 135                     item.second.m_val = item.first * 2;
 136                 else
 137                     item.second.m_val = item.first * 5;
 138             }
 139         };
 140
 141         struct check_value {
 142             int     m_nExpected;
 143
 144             check_value( int nExpected )
 145                 : m_nExpected( nExpected )
 146             {}
 147
 148             template <typename T>
 149             void operator ()( T& pair )
 150             {
 151                 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
 152             }
 153             template <typename T, typename Q>
 154             void operator ()( T& pair, Q )
 155             {
 156                 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
 157             }
 158         };
 159
 160         struct extract_functor
 161         {
 162             int *   m_pVal;
 163             void operator()( pair_type const& val )
 164             {
 165                 *m_pVal = val.second.m_val;
 166             }
 167         };
 168
 169         struct other_item {
 170             int nKey;
 171
 172             other_item( int key )
 173                 : nKey(key)
 174             {}
 175         };
 176
 177         struct other_less
 178         {
 179             bool operator ()(int v1, other_item const& v2 ) const
 180             {
 181                 return v1 < v2.nKey;
 182             }
 183             bool operator ()(other_item const& v1, int v2 ) const
 184             {
 185                 return v1.nKey < v2;
 186             }
 187         };
 188
 189
 190         template <class Map>
 191         void test_int()
 192         {
 193             Map m( 100, 4 );
 194
 195             test_int_with(m);
 196
 197             // extract/get test
 198             CPPUNIT_ASSERT( m.empty() );
 199             {
 200                 const int nLimit = 100;
 201                 typename Map::guarded_ptr gp;
 202                 int arrRandom[nLimit];
 203                 for ( int i = 0; i < nLimit; ++i )
 204                     arrRandom[i] = i;
 205                 std::random_shuffle( arrRandom, arrRandom + nLimit );
 206
 207                 for ( int i = 0; i < nLimit; ++i )
 208                     CPPUNIT_ASSERT( m.insert( arrRandom[i], arrRandom[i] ));
 209
 210                 for ( int i = 0; i < nLimit; ++i ) {
 211                     int nKey = arrRandom[i];
 212                     CPPUNIT_ASSERT( m.get(gp, nKey ));
 213                     CPPUNIT_ASSERT( !gp.empty());
 214                     CPPUNIT_CHECK( gp->first == nKey );
 215                     CPPUNIT_CHECK( gp->second.m_val == nKey );
 216
 217                     CPPUNIT_ASSERT( m.extract(gp, nKey));
 218                     CPPUNIT_ASSERT( !gp.empty());
 219                     CPPUNIT_CHECK( gp->first == nKey );
 220                     CPPUNIT_CHECK( gp->second.m_val == nKey );
 221                     CPPUNIT_CHECK( !m.get(gp, nKey));
 222                     gp.release();
 223
 224                     CPPUNIT_CHECK( !m.extract(gp, nKey));
 225                     CPPUNIT_CHECK( gp.empty());
 226                 }
 227                 CPPUNIT_ASSERT( m.empty() );
 228
 229                 for ( int i = 0; i < nLimit; ++i )
 230                     CPPUNIT_ASSERT( m.insert( arrRandom[i], arrRandom[i] ));
 231
 232                 for ( int i = 0; i < nLimit; ++i ) {
 233                     int nKey = arrRandom[i];
 234                     CPPUNIT_ASSERT( m.get_with(gp, other_item(nKey), other_less() ));
 235                     CPPUNIT_ASSERT( !gp.empty());
 236                     CPPUNIT_CHECK( gp->first == nKey );
 237                     CPPUNIT_CHECK( gp->second.m_val == nKey );
 238
 239                     CPPUNIT_ASSERT( m.extract_with(gp, other_item(nKey), other_less() ));
 240                     CPPUNIT_ASSERT( !gp.empty());
 241                     CPPUNIT_CHECK( gp->first == nKey );
 242                     CPPUNIT_CHECK( gp->second.m_val == nKey );
 243                     CPPUNIT_CHECK( !m.get_with(gp, other_item(nKey), other_less() ));
 244                     gp.release();
 245
 246                     CPPUNIT_CHECK( !m.extract_with(gp, other_item(nKey), other_less() ));
 247                     CPPUNIT_CHECK( gp.empty());
 248                 }
 249                 CPPUNIT_ASSERT( m.empty() );
 250             }
 251
 252             // iterator test
 253             test_iter<Map>();
 254         }
 255
 256         template <class Map>
 257         void test_rcu()
 258         {
 259             Map m( 52, 4 );
 260
 261             test_int_with(m);
 262
 263             // extract/get test
 264             {
 265                 typedef typename Map::gc    rcu;
 266                 typedef typename Map::rcu_lock rcu_lock;
 267                 typedef typename Map::value_type value_type;
 268                 typename Map::exempt_ptr ep;
 269
 270                 static size_t const nLimit = 100;
 271                 int arr[nLimit];
 272                 for ( size_t i = 0; i < nLimit; ++i )
 273                     arr[i] = (int) i;
 274                 std::random_shuffle( arr, arr + nLimit );
 275
 276                 for ( size_t i = 0; i < nLimit; ++i )
 277                     CPPUNIT_ASSERT( m.insert( arr[i], arr[i] ));
 278
 279                 for ( size_t i = 0; i < nLimit; i += 2 ) {
 280                     value_type * pVal;
 281                     int nKey = arr[i];
 282                     {
 283                         rcu_lock l;
 284                         pVal = m.get( nKey );
 285                         CPPUNIT_ASSERT( pVal != nullptr );
 286                         CPPUNIT_CHECK( pVal->first == nKey );
 287                         CPPUNIT_CHECK( pVal->second.m_val == nKey );
 288
 289                         CPPUNIT_ASSERT( m.extract( ep, nKey ));
 290                         CPPUNIT_ASSERT( !ep.empty() );
 291                         CPPUNIT_CHECK( pVal->first == ep->first );
 292                         CPPUNIT_CHECK( pVal->second.m_val == ep->second.m_val );
 293                     }
 294                     ep.release();
 295                     {
 296                         rcu_lock l;
 297                         CPPUNIT_CHECK( m.get( nKey ) == nullptr );
 298                         CPPUNIT_CHECK( !m.extract( ep, nKey ));
 299                         CPPUNIT_CHECK( ep.empty() );
 300
 301                         nKey = arr[i+1];
 302                         pVal = m.get_with( other_item(nKey), other_less() );
 303                         CPPUNIT_ASSERT( pVal != nullptr );
 304                         CPPUNIT_CHECK( pVal->first == nKey );
 305                         CPPUNIT_CHECK( pVal->second.m_val == nKey );
 306
 307                         CPPUNIT_ASSERT( m.extract_with( ep, other_item(nKey), other_less() ));
 308                         CPPUNIT_ASSERT( !ep.empty() );
 309                         CPPUNIT_CHECK( pVal->first == ep->first );
 310                         CPPUNIT_CHECK( pVal->second.m_val == (*ep).second.m_val );
 311                     }
 312                     ep.release();
 313                     {
 314                         rcu_lock l;
 315                         CPPUNIT_CHECK( m.get_with( other_item(nKey), other_less() ) == nullptr );
 316                         CPPUNIT_CHECK( !m.extract_with( ep, other_item(nKey), other_less() ));
 317                         CPPUNIT_CHECK( ep.empty() );
 318                     }
 319                 }
 320                 CPPUNIT_CHECK( m.empty() );
 321                 CPPUNIT_CHECK( check_size( m, 0 ));
 322                 {
 323                     rcu_lock l;
 324                     CPPUNIT_CHECK( m.get( int(nLimit / 2) ) == nullptr );
 325                     CPPUNIT_CHECK( !m.extract( ep, int(nLimit / 2) ));
 326                     CPPUNIT_CHECK( ep.empty() );
 327                 }
 328             }
 329
 330             // iterator test
 331             test_iter<Map>();
 332         }
 333
 334         template <class Map>
 335         void test_int_with( Map& m )
 336         {
 337             std::pair<bool, bool> ensureResult;
 338
 339             // insert
 340             CPPUNIT_ASSERT( m.empty() );
 341             CPPUNIT_ASSERT( check_size( m, 0 ));
 342             CPPUNIT_ASSERT( !m.find(25) );
 343             CPPUNIT_ASSERT( m.insert( 25 ) )    ;   // value = 0
 344             CPPUNIT_ASSERT( m.find(25) );
 345             CPPUNIT_ASSERT( !m.empty() );
 346             CPPUNIT_ASSERT( check_size( m, 1 ));
 347             CPPUNIT_ASSERT( m.find(25) );
 348
 349             CPPUNIT_ASSERT( !m.insert( 25 ) );
 350             CPPUNIT_ASSERT( !m.empty() );
 351             CPPUNIT_ASSERT( check_size( m, 1 ));
 352
 353             CPPUNIT_ASSERT( !m.find_with(10, less()) );
 354             CPPUNIT_ASSERT( m.insert( 10, 10 ) );
 355             CPPUNIT_ASSERT( !m.empty() );
 356             CPPUNIT_ASSERT( check_size( m, 2 ));
 357             CPPUNIT_ASSERT( m.find_with(10, less()) );
 358
 359             CPPUNIT_ASSERT( !m.insert( 10, 20 ) );
 360             CPPUNIT_ASSERT( !m.empty() );
 361             CPPUNIT_ASSERT( check_size( m, 2 ));
 362
 363             CPPUNIT_ASSERT( !m.find(30) );
 364             CPPUNIT_ASSERT( m.insert_key( 30, insert_functor<Map>() ) )    ; // value = 90
 365             CPPUNIT_ASSERT( !m.empty() );
 366             CPPUNIT_ASSERT( check_size( m, 3 ));
 367             CPPUNIT_ASSERT( m.find(30) );
 368
 369             CPPUNIT_ASSERT( !m.insert_key( 10, insert_functor<Map>() ) );
 370             CPPUNIT_ASSERT( !m.insert_key( 25, insert_functor<Map>() ) );
 371             CPPUNIT_ASSERT( !m.insert_key( 30, insert_functor<Map>() ) );
 372
 373             // ensure (new key)
 374             CPPUNIT_ASSERT( !m.find(27) );
 375             ensureResult = m.ensure( 27, insert_functor<Map>() ) ;   // value = 54
 376             CPPUNIT_ASSERT( ensureResult.first );
 377             CPPUNIT_ASSERT( ensureResult.second );
 378             CPPUNIT_ASSERT( m.find(27) );
 379
 380             // find test
 381             check_value chk(10);
 382             CPPUNIT_ASSERT( m.find( 10, cds::ref(chk) ));
 383             chk.m_nExpected = 0;
 384             CPPUNIT_ASSERT( m.find_with( 25, less(), boost::ref(chk) ));
 385             chk.m_nExpected = 90;
 386             CPPUNIT_ASSERT( m.find( 30, boost::ref(chk) ));
 387             chk.m_nExpected = 54;
 388             CPPUNIT_ASSERT( m.find( 27, boost::ref(chk) ));
 389
 390             ensureResult = m.ensure( 10, insert_functor<Map>() ) ;   // value = 50
 391             CPPUNIT_ASSERT( ensureResult.first );
 392             CPPUNIT_ASSERT( !ensureResult.second );
 393             chk.m_nExpected = 50;
 394             CPPUNIT_ASSERT( m.find( 10, boost::ref(chk) ));
 395
 396             // erase test
 397             CPPUNIT_ASSERT( !m.find(100) );
 398             CPPUNIT_ASSERT( !m.erase( 100 )) ;  // not found
 399
 400             CPPUNIT_ASSERT( m.find(25) );
 401             CPPUNIT_ASSERT( check_size( m, 4 ));
 402             CPPUNIT_ASSERT( m.erase( 25 ));
 403             CPPUNIT_ASSERT( !m.empty() );
 404             CPPUNIT_ASSERT( check_size( m, 3 ));
 405             CPPUNIT_ASSERT( !m.find(25) );
 406             CPPUNIT_ASSERT( !m.erase( 25 ));
 407
 408             CPPUNIT_ASSERT( !m.find(258) );
 409             CPPUNIT_ASSERT( m.insert(258))
 410             CPPUNIT_ASSERT( check_size( m, 4 ));
 411             CPPUNIT_ASSERT( m.find_with(258, less()) );
 412             CPPUNIT_ASSERT( m.erase_with( 258, less() ));
 413             CPPUNIT_ASSERT( !m.empty() );
 414             CPPUNIT_ASSERT( check_size( m, 3 ));
 415             CPPUNIT_ASSERT( !m.find(258) );
 416             CPPUNIT_ASSERT( !m.erase_with( 258, less() ));
 417
 418             int nVal;
 419             extract_functor ext;
 420             ext.m_pVal = &nVal;
 421
 422             CPPUNIT_ASSERT( !m.find(29) );
 423             CPPUNIT_ASSERT( m.insert(29, 290));
 424             CPPUNIT_ASSERT( check_size( m, 4 ));
 425             CPPUNIT_ASSERT( m.erase_with( 29, less(), boost::ref(ext)));
 426             CPPUNIT_ASSERT( !m.empty() );
 427             CPPUNIT_ASSERT( check_size( m, 3 ));
 428             CPPUNIT_ASSERT( nVal == 290 );
 429             nVal = -1;
 430             CPPUNIT_ASSERT( !m.erase_with( 29, less(), boost::ref(ext)));
 431             CPPUNIT_ASSERT( nVal == -1 );
 432
 433             CPPUNIT_ASSERT( m.erase( 30, boost::ref(ext)));
 434             CPPUNIT_ASSERT( !m.empty() );
 435             CPPUNIT_ASSERT( check_size( m, 2 ));
 436             CPPUNIT_ASSERT( nVal == 90 );
 437             nVal = -1;
 438             CPPUNIT_ASSERT( !m.erase( 30, boost::ref(ext)));
 439             CPPUNIT_ASSERT( nVal == -1 );
 440
 441             m.clear();
 442             CPPUNIT_ASSERT( m.empty() );
 443             CPPUNIT_ASSERT( check_size( m, 0 ));
 444
 445 #       ifdef CDS_EMPLACE_SUPPORT
 446             // emplace test
 447             CPPUNIT_ASSERT( m.emplace(126) ) ; // key = 126, val = 0
 448             CPPUNIT_ASSERT( m.emplace(137, 731))    ;   // key = 137, val = 731
 449             CPPUNIT_ASSERT( m.emplace( 149, value_type(941) ))   ;   // key = 149, val = 941
 450
 451             CPPUNIT_ASSERT( !m.empty() );
 452             CPPUNIT_ASSERT( check_size( m, 3 ));
 453
 454             chk.m_nExpected = 0;
 455             CPPUNIT_ASSERT( m.find( 126, cds::ref(chk) ));
 456             chk.m_nExpected = 731;
 457             CPPUNIT_ASSERT( m.find_with( 137, less(), cds::ref(chk) ));
 458             chk.m_nExpected = 941;
 459             CPPUNIT_ASSERT( m.find( 149, cds::ref(chk) ));
 460
 461             CPPUNIT_ASSERT( !m.emplace(126, 621)) ; // already in map
 462             chk.m_nExpected = 0;
 463             CPPUNIT_ASSERT( m.find( 126, cds::ref(chk) ));
 464             CPPUNIT_ASSERT( !m.empty() );
 465             CPPUNIT_ASSERT( check_size( m, 3 ));
 466
 467             m.clear();
 468             CPPUNIT_ASSERT( m.empty() );
 469             CPPUNIT_ASSERT( check_size( m, 0 ));
 470
 471 #       endif
 472         }
 473
 474
 475         template <class Map>
 476         void test_int_nogc()
 477         {
 478             typedef typename Map::iterator          iterator;
 479             typedef typename Map::const_iterator    const_iterator;
 480
 481             {
 482                 Map m( 52, 4 );
 483
 484                 CPPUNIT_ASSERT( m.empty() );
 485                 CPPUNIT_ASSERT( check_size( m, 0 ));
 486
 487                 CPPUNIT_ASSERT( m.find(10) == m.end() );
 488                 iterator it = m.insert( 10 );
 489                 CPPUNIT_ASSERT( it != m.end() );
 490                 CPPUNIT_ASSERT( !m.empty() );
 491                 CPPUNIT_ASSERT( check_size( m, 1 ));
 492                 CPPUNIT_ASSERT( m.find(10) == it );
 493                 CPPUNIT_ASSERT( it->first == 10 );
 494                 CPPUNIT_ASSERT( it->second.m_val == 0 );
 495
 496                 CPPUNIT_ASSERT( m.find(100) == m.end() );
 497                 it = m.insert( 100, 200 );
 498                 CPPUNIT_ASSERT( it != m.end() );
 499                 CPPUNIT_ASSERT( !m.empty() );
 500                 CPPUNIT_ASSERT( check_size( m, 2 ));
 501                 CPPUNIT_ASSERT( m.find_with(100, less()) == it );
 502                 CPPUNIT_ASSERT( it->first == 100 );
 503                 CPPUNIT_ASSERT( it->second.m_val == 200 );
 504
 505                 CPPUNIT_ASSERT( m.find(55) == m.end() );
 506                 it = m.insert_key( 55, insert_functor<Map>() );
 507                 CPPUNIT_ASSERT( it != m.end() );
 508                 CPPUNIT_ASSERT( !m.empty() );
 509                 CPPUNIT_ASSERT( check_size( m, 3 ));
 510                 CPPUNIT_ASSERT( m.find(55) == it );
 511                 CPPUNIT_ASSERT( it->first == 55 );
 512                 CPPUNIT_ASSERT( it->second.m_val == 55 * 3 );
 513
 514                 CPPUNIT_ASSERT( m.insert( 55 ) == m.end() );
 515                 CPPUNIT_ASSERT( m.insert( 55, 10 ) == m.end() );
 516                 CPPUNIT_ASSERT( m.insert_key( 55, insert_functor<Map>()) == m.end() );
 517
 518                 CPPUNIT_ASSERT( m.find(10) != m.end() );
 519                 std::pair<iterator, bool> ensureResult = m.ensure( 10 );
 520                 CPPUNIT_ASSERT( ensureResult.first != m.end() );
 521                 CPPUNIT_ASSERT( !ensureResult.second  );
 522                 CPPUNIT_ASSERT( !m.empty() );
 523                 ensureResult.first->second.m_val = ensureResult.first->first * 5;
 524                 CPPUNIT_ASSERT( check_size( m, 3 ));
 525                 CPPUNIT_ASSERT( m.find(10) == ensureResult.first );
 526                 it = m.find(10);
 527                 CPPUNIT_ASSERT( it != m.end() );
 528                 CPPUNIT_ASSERT( it->second.m_val == 50 );
 529
 530                 CPPUNIT_ASSERT( m.find(120) == m.end() );
 531                 ensureResult = m.ensure( 120 );
 532                 CPPUNIT_ASSERT( ensureResult.first != m.end() );
 533                 CPPUNIT_ASSERT( ensureResult.second  );
 534                 CPPUNIT_ASSERT( !m.empty() );
 535                 CPPUNIT_ASSERT( check_size( m, 4 ));
 536                 ensureResult.first->second.m_val = ensureResult.first->first * 5;
 537                 CPPUNIT_ASSERT( m.find_with(120, less()) == ensureResult.first );
 538                 it = m.find_with(120, less());
 539                 CPPUNIT_ASSERT( it != m.end() );
 540                 CPPUNIT_ASSERT( it->second.m_val == 120 * 5 );
 541                 CPPUNIT_ASSERT( m.find_with(120, less()) == m.find(120) );
 542
 543 #           ifdef CDS_EMPLACE_SUPPORT
 544                 // emplace test
 545                 it = m.emplace( 151 ) ;  // key = 151,  val = 0
 546                 CPPUNIT_ASSERT( it != m.end() );
 547                 CPPUNIT_ASSERT( it->first == 151 );
 548                 CPPUNIT_ASSERT( it->second.m_val == 0 );
 549
 550                 it = m.emplace( 174, 471 ) ; // key == 174, val = 471
 551                 CPPUNIT_ASSERT( it != m.end() );
 552                 CPPUNIT_ASSERT( it->first == 174 );
 553                 CPPUNIT_ASSERT( it->second.m_val == 471 );
 554
 555                 it = m.emplace( 190, value_type(91)) ; // key == 190, val = 19
 556                 CPPUNIT_ASSERT( it != m.end() );
 557                 CPPUNIT_ASSERT( it->first == 190 );
 558                 CPPUNIT_ASSERT( it->second.m_val == 91 );
 559
 560                 it = m.emplace( 151, 1051 );
 561                 CPPUNIT_ASSERT( it == m.end());
 562
 563                 it = m.find( 174 );
 564                 CPPUNIT_ASSERT( it != m.end() );
 565                 CPPUNIT_ASSERT( it->first == 174 );
 566                 CPPUNIT_ASSERT( it->second.m_val == 471 );
 567
 568                 it = m.find( 190 );
 569                 CPPUNIT_ASSERT( it != m.end() );
 570                 CPPUNIT_ASSERT( it->first == 190 );
 571                 CPPUNIT_ASSERT( it->second.m_val == 91 );
 572
 573                 it = m.find( 151 );
 574                 CPPUNIT_ASSERT( it != m.end() );
 575                 CPPUNIT_ASSERT( it->first == 151 );
 576                 CPPUNIT_ASSERT( it->second.m_val == 0 );
 577 #           endif
 578             }
 579
 580             // iterator test
 581
 582             {
 583                 Map m( 52, 4 );
 584
 585                 for ( int i = 0; i < 500; ++i ) {
 586                     CPPUNIT_ASSERT( m.insert( i, i * 2 ) != m.end() );
 587                 }
 588                 CPPUNIT_ASSERT( check_size( m, 500 ));
 589
 590                 for ( iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) {
 591                     CPPUNIT_ASSERT( it->first * 2 == (*it).second.m_val );
 592                     it->second = it->first;
 593                 }
 594
 595                 Map const& refMap = m;
 596                 for ( const_iterator it = refMap.begin(), itEnd = refMap.end(); it != itEnd; ++it ) {
 597                     CPPUNIT_ASSERT( it->first == it->second.m_val );
 598                     CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
 599                 }
 600             }
 601         }
 602
 603         template <class Map>
 604         void test_iter()
 605         {
 606             typedef typename Map::iterator          iterator;
 607             typedef typename Map::const_iterator    const_iterator;
 608
 609             Map s( 100, 4 );
 610
 611             const int nMaxCount = 500;
 612             for ( int i = 0; i < nMaxCount; ++i ) {
 613                 CPPUNIT_ASSERT( s.insert( i, i * 2 ));
 614             }
 615
 616             int nCount = 0;
 617             for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 618                 CPPUNIT_ASSERT( it->first * 2 == it->second.m_val );
 619                 CPPUNIT_ASSERT( (*it).first * 2 == (*it).second.m_val );
 620                 it->second.m_val = it->first;
 621                 ++nCount;
 622             }
 623             CPPUNIT_ASSERT( nCount == nMaxCount );
 624
 625             Map const& refSet = s;
 626             nCount = 0;
 627             for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
 628                 CPPUNIT_ASSERT( it->first == it->second.m_val );
 629                 CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
 630                 ++nCount;
 631             }
 632             CPPUNIT_ASSERT( nCount == nMaxCount );
 633         }
 634
 635
 636         void Michael_HP_cmp();
 637         void Michael_HP_less();
 638         void Michael_HP_cmpmix();
 639
 640         void Michael_PTB_cmp();
 641         void Michael_PTB_less();
 642         void Michael_PTB_cmpmix();
 643
 644         void Michael_HRC_cmp();
 645         void Michael_HRC_less();
 646         void Michael_HRC_cmpmix();
 647
 648         void Michael_RCU_GPI_cmp();
 649         void Michael_RCU_GPI_less();
 650         void Michael_RCU_GPI_cmpmix();
 651
 652         void Michael_RCU_GPB_cmp();
 653         void Michael_RCU_GPB_less();
 654         void Michael_RCU_GPB_cmpmix();
 655
 656         void Michael_RCU_GPT_cmp();
 657         void Michael_RCU_GPT_less();
 658         void Michael_RCU_GPT_cmpmix();
 659
 660         void Michael_RCU_SHB_cmp();
 661         void Michael_RCU_SHB_less();
 662         void Michael_RCU_SHB_cmpmix();
 663
 664         void Michael_RCU_SHT_cmp();
 665         void Michael_RCU_SHT_less();
 666         void Michael_RCU_SHT_cmpmix();
 667
 668         void Michael_nogc_cmp();
 669         void Michael_nogc_less();
 670         void Michael_nogc_cmpmix();
 671
 672         void Lazy_HP_cmp();
 673         void Lazy_HP_less();
 674         void Lazy_HP_cmpmix();
 675
 676         void Lazy_PTB_cmp();
 677         void Lazy_PTB_less();
 678         void Lazy_PTB_cmpmix();
 679
 680         void Lazy_HRC_cmp();
 681         void Lazy_HRC_less();
 682         void Lazy_HRC_cmpmix();
 683
 684         void Lazy_RCU_GPI_cmp();
 685         void Lazy_RCU_GPI_less();
 686         void Lazy_RCU_GPI_cmpmix();
 687
 688         void Lazy_RCU_GPB_cmp();
 689         void Lazy_RCU_GPB_less();
 690         void Lazy_RCU_GPB_cmpmix();
 691
 692         void Lazy_RCU_GPT_cmp();
 693         void Lazy_RCU_GPT_less();
 694         void Lazy_RCU_GPT_cmpmix();
 695
 696         void Lazy_RCU_SHB_cmp();
 697         void Lazy_RCU_SHB_less();
 698         void Lazy_RCU_SHB_cmpmix();
 699
 700         void Lazy_RCU_SHT_cmp();
 701         void Lazy_RCU_SHT_less();
 702         void Lazy_RCU_SHT_cmpmix();
 703
 704         void Lazy_nogc_cmp();
 705         void Lazy_nogc_less();
 706         void Lazy_nogc_cmpmix();
 707
 708         void Split_HP_cmp();
 709         void Split_HP_less();
 710         void Split_HP_cmpmix();
 711
 712         void Split_PTB_cmp();
 713         void Split_PTB_less();
 714         void Split_PTB_cmpmix();
 715
 716         void Split_HRC_cmp();
 717         void Split_HRC_less();
 718         void Split_HRC_cmpmix();
 719
 720         void Split_RCU_GPI_cmp();
 721         void Split_RCU_GPI_less();
 722         void Split_RCU_GPI_cmpmix();
 723
 724         void Split_RCU_GPB_cmp();
 725         void Split_RCU_GPB_less();
 726         void Split_RCU_GPB_cmpmix();
 727
 728         void Split_RCU_GPT_cmp();
 729         void Split_RCU_GPT_less();
 730         void Split_RCU_GPT_cmpmix();
 731
 732         void Split_RCU_SHB_cmp();
 733         void Split_RCU_SHB_less();
 734         void Split_RCU_SHB_cmpmix();
 735
 736         void Split_RCU_SHT_cmp();
 737         void Split_RCU_SHT_less();
 738         void Split_RCU_SHT_cmpmix();
 739
 740         void Split_nogc_cmp();
 741         void Split_nogc_less();
 742         void Split_nogc_cmpmix();
 743
 744         void Split_Lazy_HP_cmp();
 745         void Split_Lazy_HP_less();
 746         void Split_Lazy_HP_cmpmix();
 747
 748         void Split_Lazy_PTB_cmp();
 749         void Split_Lazy_PTB_less();
 750         void Split_Lazy_PTB_cmpmix();
 751
 752         void Split_Lazy_HRC_cmp();
 753         void Split_Lazy_HRC_less();
 754         void Split_Lazy_HRC_cmpmix();
 755
 756         void Split_Lazy_RCU_GPI_cmp();
 757         void Split_Lazy_RCU_GPI_less();
 758         void Split_Lazy_RCU_GPI_cmpmix();
 759
 760         void Split_Lazy_RCU_GPB_cmp();
 761         void Split_Lazy_RCU_GPB_less();
 762         void Split_Lazy_RCU_GPB_cmpmix();
 763
 764         void Split_Lazy_RCU_GPT_cmp();
 765         void Split_Lazy_RCU_GPT_less();
 766         void Split_Lazy_RCU_GPT_cmpmix();
 767
 768         void Split_Lazy_RCU_SHB_cmp();
 769         void Split_Lazy_RCU_SHB_less();
 770         void Split_Lazy_RCU_SHB_cmpmix();
 771
 772         void Split_Lazy_RCU_SHT_cmp();
 773         void Split_Lazy_RCU_SHT_less();
 774         void Split_Lazy_RCU_SHT_cmpmix();
 775
 776         void Split_Lazy_nogc_cmp();
 777         void Split_Lazy_nogc_less();
 778         void Split_Lazy_nogc_cmpmix();
 779
 780         CPPUNIT_TEST_SUITE(HashMapHdrTest)
 781             CPPUNIT_TEST(Michael_HP_cmp)
 782             CPPUNIT_TEST(Michael_HP_less)
 783             CPPUNIT_TEST(Michael_HP_cmpmix)
 784
 785             CPPUNIT_TEST(Michael_PTB_cmp)
 786             CPPUNIT_TEST(Michael_PTB_less)
 787             CPPUNIT_TEST(Michael_PTB_cmpmix)
 788
 789             CPPUNIT_TEST(Michael_HRC_cmp)
 790             CPPUNIT_TEST(Michael_HRC_less)
 791             CPPUNIT_TEST(Michael_HRC_cmpmix)
 792
 793             CPPUNIT_TEST(Michael_RCU_GPI_cmp)
 794             CPPUNIT_TEST(Michael_RCU_GPI_less)
 795             CPPUNIT_TEST(Michael_RCU_GPI_cmpmix)
 796
 797             CPPUNIT_TEST(Michael_RCU_GPB_cmp)
 798             CPPUNIT_TEST(Michael_RCU_GPB_less)
 799             CPPUNIT_TEST(Michael_RCU_GPB_cmpmix)
 800
 801             CPPUNIT_TEST(Michael_RCU_SHT_cmp)
 802             CPPUNIT_TEST(Michael_RCU_SHT_less)
 803             CPPUNIT_TEST(Michael_RCU_SHT_cmpmix)
 804
 805             CPPUNIT_TEST(Michael_RCU_SHB_cmp)
 806             CPPUNIT_TEST(Michael_RCU_SHB_less)
 807             CPPUNIT_TEST(Michael_RCU_SHB_cmpmix)
 808
 809             CPPUNIT_TEST(Michael_RCU_GPT_cmp)
 810             CPPUNIT_TEST(Michael_RCU_GPT_less)
 811             CPPUNIT_TEST(Michael_RCU_GPT_cmpmix)
 812
 813             CPPUNIT_TEST(Michael_nogc_cmp)
 814             CPPUNIT_TEST(Michael_nogc_less)
 815             CPPUNIT_TEST(Michael_nogc_cmpmix)
 816
 817             CPPUNIT_TEST(Lazy_HP_cmp)
 818             CPPUNIT_TEST(Lazy_HP_less)
 819             CPPUNIT_TEST(Lazy_HP_cmpmix)
 820
 821             CPPUNIT_TEST(Lazy_PTB_cmp)
 822             CPPUNIT_TEST(Lazy_PTB_less)
 823             CPPUNIT_TEST(Lazy_PTB_cmpmix)
 824
 825             CPPUNIT_TEST(Lazy_HRC_cmp)
 826             CPPUNIT_TEST(Lazy_HRC_less)
 827             CPPUNIT_TEST(Lazy_HRC_cmpmix)
 828
 829             CPPUNIT_TEST(Lazy_RCU_GPI_cmp)
 830             CPPUNIT_TEST(Lazy_RCU_GPI_less)
 831             CPPUNIT_TEST(Lazy_RCU_GPI_cmpmix)
 832
 833             CPPUNIT_TEST(Lazy_RCU_GPB_cmp)
 834             CPPUNIT_TEST(Lazy_RCU_GPB_less)
 835             CPPUNIT_TEST(Lazy_RCU_GPB_cmpmix)
 836
 837             CPPUNIT_TEST(Lazy_RCU_GPT_cmp)
 838             CPPUNIT_TEST(Lazy_RCU_GPT_less)
 839             CPPUNIT_TEST(Lazy_RCU_GPT_cmpmix)
 840
 841             CPPUNIT_TEST(Lazy_RCU_SHB_cmp)
 842             CPPUNIT_TEST(Lazy_RCU_SHB_less)
 843             CPPUNIT_TEST(Lazy_RCU_SHB_cmpmix)
 844
 845             CPPUNIT_TEST(Lazy_RCU_SHT_cmp)
 846             CPPUNIT_TEST(Lazy_RCU_SHT_less)
 847             CPPUNIT_TEST(Lazy_RCU_SHT_cmpmix)
 848
 849             CPPUNIT_TEST(Lazy_nogc_cmp)
 850             CPPUNIT_TEST(Lazy_nogc_less)
 851             CPPUNIT_TEST(Lazy_nogc_cmpmix)
 852
 853             CPPUNIT_TEST(Split_HP_cmp)
 854             CPPUNIT_TEST(Split_HP_less)
 855             CPPUNIT_TEST(Split_HP_cmpmix)
 856
 857             CPPUNIT_TEST(Split_PTB_cmp)
 858             CPPUNIT_TEST(Split_PTB_less)
 859             CPPUNIT_TEST(Split_PTB_cmpmix)
 860
 861             CPPUNIT_TEST(Split_HRC_cmp)
 862             CPPUNIT_TEST(Split_HRC_less)
 863             CPPUNIT_TEST(Split_HRC_cmpmix)
 864
 865             CPPUNIT_TEST(Split_RCU_GPI_cmp)
 866             CPPUNIT_TEST(Split_RCU_GPI_less)
 867             CPPUNIT_TEST(Split_RCU_GPI_cmpmix)
 868
 869             CPPUNIT_TEST(Split_RCU_GPB_cmp)
 870             CPPUNIT_TEST(Split_RCU_GPB_less)
 871             CPPUNIT_TEST(Split_RCU_GPB_cmpmix)
 872
 873             CPPUNIT_TEST(Split_RCU_GPT_cmp)
 874             CPPUNIT_TEST(Split_RCU_GPT_less)
 875             CPPUNIT_TEST(Split_RCU_GPT_cmpmix)
 876
 877             CPPUNIT_TEST(Split_RCU_SHB_cmp)
 878             CPPUNIT_TEST(Split_RCU_SHB_less)
 879             CPPUNIT_TEST(Split_RCU_SHB_cmpmix)
 880
 881             CPPUNIT_TEST(Split_RCU_SHT_cmp)
 882             CPPUNIT_TEST(Split_RCU_SHT_less)
 883             CPPUNIT_TEST(Split_RCU_SHT_cmpmix)
 884
 885             CPPUNIT_TEST(Split_nogc_cmp)
 886             CPPUNIT_TEST(Split_nogc_less)
 887             CPPUNIT_TEST(Split_nogc_cmpmix)
 888
 889             CPPUNIT_TEST(Split_Lazy_HP_cmp)
 890             CPPUNIT_TEST(Split_Lazy_HP_less)
 891             CPPUNIT_TEST(Split_Lazy_HP_cmpmix)
 892
 893             CPPUNIT_TEST(Split_Lazy_PTB_cmp)
 894             CPPUNIT_TEST(Split_Lazy_PTB_less)
 895             CPPUNIT_TEST(Split_Lazy_PTB_cmpmix)
 896
 897             CPPUNIT_TEST(Split_Lazy_HRC_cmp)
 898             CPPUNIT_TEST(Split_Lazy_HRC_less)
 899             CPPUNIT_TEST(Split_Lazy_HRC_cmpmix)
 900
 901             CPPUNIT_TEST(Split_Lazy_RCU_GPI_cmp)
 902             CPPUNIT_TEST(Split_Lazy_RCU_GPI_less)
 903             CPPUNIT_TEST(Split_Lazy_RCU_GPI_cmpmix)
 904
 905             CPPUNIT_TEST(Split_Lazy_RCU_GPB_cmp)
 906             CPPUNIT_TEST(Split_Lazy_RCU_GPB_less)
 907             CPPUNIT_TEST(Split_Lazy_RCU_GPB_cmpmix)
 908
 909             CPPUNIT_TEST(Split_Lazy_RCU_GPT_cmp)
 910             CPPUNIT_TEST(Split_Lazy_RCU_GPT_less)
 911             CPPUNIT_TEST(Split_Lazy_RCU_GPT_cmpmix)
 912
 913             CPPUNIT_TEST(Split_Lazy_RCU_SHB_cmp)
 914             CPPUNIT_TEST(Split_Lazy_RCU_SHB_less)
 915             CPPUNIT_TEST(Split_Lazy_RCU_SHB_cmpmix)
 916
 917             CPPUNIT_TEST(Split_Lazy_RCU_SHT_cmp)
 918             CPPUNIT_TEST(Split_Lazy_RCU_SHT_less)
 919             CPPUNIT_TEST(Split_Lazy_RCU_SHT_cmpmix)
 920
 921             CPPUNIT_TEST(Split_Lazy_nogc_cmp)
 922             CPPUNIT_TEST(Split_Lazy_nogc_less)
 923             CPPUNIT_TEST(Split_Lazy_nogc_cmpmix)
 924         CPPUNIT_TEST_SUITE_END()
 925
 926     };
 927 }   // namespace map
 928
 929 #endif // #ifndef __CDSTEST_HDR_MAP_H