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 <functional>   // ref
  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                     gp = m.get( nKey );
 213                     CPPUNIT_ASSERT( gp );
 214                     CPPUNIT_ASSERT( !gp.empty());
 215                     CPPUNIT_CHECK( gp->first == nKey );
 216                     CPPUNIT_CHECK( gp->second.m_val == nKey );
 217                     gp.release();
 218
 219                     gp = m.extract( nKey );
 220                     CPPUNIT_ASSERT( gp );
 221                     CPPUNIT_ASSERT( !gp.empty());
 222                     CPPUNIT_CHECK( gp->first == nKey );
 223                     CPPUNIT_CHECK( gp->second.m_val == nKey );
 224                     gp.release();
 225
 226                     gp = m.get( nKey );
 227                     CPPUNIT_CHECK( !gp );
 228
 229                     CPPUNIT_CHECK( !m.extract(nKey));
 230                     CPPUNIT_CHECK( gp.empty());
 231                 }
 232                 CPPUNIT_ASSERT( m.empty() );
 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_with( other_item( nKey ), other_less() );
 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_with( other_item( nKey ), other_less() );
 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_with( other_item( nKey ), other_less() );
 254                     CPPUNIT_CHECK( !gp );
 255
 256                     CPPUNIT_CHECK( !m.extract_with(other_item(nKey), other_less() ));
 257                     CPPUNIT_CHECK( gp.empty());
 258                 }
 259                 CPPUNIT_ASSERT( m.empty() );
 260             }
 261
 262             // iterator test
 263             test_iter<Map>();
 264         }
 265
 266         template <class Map>
 267         void test_rcu()
 268         {
 269             Map m( 52, 4 );
 270
 271             test_int_with(m);
 272
 273             // extract/get test
 274             {
 275                 typedef typename Map::gc    rcu;
 276                 typedef typename Map::rcu_lock rcu_lock;
 277                 typedef typename Map::value_type value_type;
 278                 typename Map::exempt_ptr ep;
 279
 280                 static size_t const nLimit = 100;
 281                 int arr[nLimit];
 282                 for ( size_t i = 0; i < nLimit; ++i )
 283                     arr[i] = (int) i;
 284                 std::random_shuffle( arr, arr + nLimit );
 285
 286                 for ( size_t i = 0; i < nLimit; ++i )
 287                     CPPUNIT_ASSERT( m.insert( arr[i], arr[i] ));
 288
 289                 for ( size_t i = 0; i < nLimit; i += 2 ) {
 290                     value_type * pVal;
 291                     int nKey = arr[i];
 292                     {
 293                         rcu_lock l;
 294                         pVal = m.get( nKey );
 295                         CPPUNIT_ASSERT( pVal != nullptr );
 296                         CPPUNIT_CHECK( pVal->first == nKey );
 297                         CPPUNIT_CHECK( pVal->second.m_val == nKey );
 298
 299                         ep = m.extract( nKey );
 300                         CPPUNIT_ASSERT( ep );
 301                         CPPUNIT_ASSERT( !ep.empty() );
 302                         CPPUNIT_CHECK( pVal->first == ep->first );
 303                         CPPUNIT_CHECK( pVal->second.m_val == ep->second.m_val );
 304                     }
 305                     ep.release();
 306                     {
 307                         rcu_lock l;
 308                         CPPUNIT_CHECK( m.get( nKey ) == nullptr );
 309                         ep = m.extract( nKey );
 310                         CPPUNIT_CHECK( !ep );
 311                         CPPUNIT_CHECK( ep.empty() );
 312
 313                         nKey = arr[i+1];
 314                         pVal = m.get_with( other_item(nKey), other_less() );
 315                         CPPUNIT_ASSERT( pVal != nullptr );
 316                         CPPUNIT_CHECK( pVal->first == nKey );
 317                         CPPUNIT_CHECK( pVal->second.m_val == nKey );
 318
 319                         ep = m.extract_with( other_item( nKey ), other_less() );
 320                         CPPUNIT_ASSERT( ep );
 321                         CPPUNIT_ASSERT( !ep.empty() );
 322                         CPPUNIT_CHECK( pVal->first == ep->first );
 323                         CPPUNIT_CHECK( pVal->second.m_val == (*ep).second.m_val );
 324                     }
 325                     ep.release();
 326                     {
 327                         rcu_lock l;
 328                         CPPUNIT_CHECK( m.get_with( other_item(nKey), other_less() ) == nullptr );
 329                         CPPUNIT_CHECK( !m.extract_with( other_item(nKey), other_less() ));
 330                         CPPUNIT_CHECK( ep.empty() );
 331                     }
 332                 }
 333                 CPPUNIT_CHECK( m.empty() );
 334                 CPPUNIT_CHECK( check_size( m, 0 ));
 335                 {
 336                     rcu_lock l;
 337                     CPPUNIT_CHECK( m.get( int(nLimit / 2) ) == nullptr );
 338                     ep = m.extract( int( nLimit / 2 ) );
 339                     CPPUNIT_CHECK( !ep );
 340                     CPPUNIT_CHECK( ep.empty() );
 341                 }
 342             }
 343
 344             // iterator test
 345             test_iter<Map>();
 346         }
 347
 348         template <class Map>
 349         void test_int_with( Map& m )
 350         {
 351             std::pair<bool, bool> ensureResult;
 352
 353             // insert
 354             CPPUNIT_ASSERT( m.empty() );
 355             CPPUNIT_ASSERT( check_size( m, 0 ));
 356             CPPUNIT_ASSERT( !m.find(25) );
 357             CPPUNIT_ASSERT( m.insert( 25 ) )    ;   // value = 0
 358             CPPUNIT_ASSERT( m.find(25) );
 359             CPPUNIT_ASSERT( !m.empty() );
 360             CPPUNIT_ASSERT( check_size( m, 1 ));
 361             CPPUNIT_ASSERT( m.find(25) );
 362
 363             CPPUNIT_ASSERT( !m.insert( 25 ) );
 364             CPPUNIT_ASSERT( !m.empty() );
 365             CPPUNIT_ASSERT( check_size( m, 1 ));
 366
 367             CPPUNIT_ASSERT( !m.find_with(10, less()) );
 368             CPPUNIT_ASSERT( m.insert( 10, 10 ) );
 369             CPPUNIT_ASSERT( !m.empty() );
 370             CPPUNIT_ASSERT( check_size( m, 2 ));
 371             CPPUNIT_ASSERT( m.find_with(10, less()) );
 372
 373             CPPUNIT_ASSERT( !m.insert( 10, 20 ) );
 374             CPPUNIT_ASSERT( !m.empty() );
 375             CPPUNIT_ASSERT( check_size( m, 2 ));
 376
 377             CPPUNIT_ASSERT( !m.find(30) );
 378             CPPUNIT_ASSERT( m.insert_with( 30, insert_functor<Map>() ) )    ; // value = 90
 379             CPPUNIT_ASSERT( !m.empty() );
 380             CPPUNIT_ASSERT( check_size( m, 3 ));
 381             CPPUNIT_ASSERT( m.find(30) );
 382
 383             CPPUNIT_ASSERT( !m.insert_with( 10, insert_functor<Map>() ) );
 384             CPPUNIT_ASSERT( !m.insert_with( 25, insert_functor<Map>() ) );
 385             CPPUNIT_ASSERT( !m.insert_with( 30, insert_functor<Map>() ) );
 386
 387             // ensure (new key)
 388             CPPUNIT_ASSERT( !m.find(27) );
 389             ensureResult = m.ensure( 27, insert_functor<Map>() ) ;   // value = 54
 390             CPPUNIT_ASSERT( ensureResult.first );
 391             CPPUNIT_ASSERT( ensureResult.second );
 392             CPPUNIT_ASSERT( m.find(27) );
 393
 394             // find test
 395             check_value chk(10);
 396             CPPUNIT_ASSERT( m.find( 10, std::ref(chk) ));
 397             chk.m_nExpected = 0;
 398             CPPUNIT_ASSERT( m.find_with( 25, less(), std::ref( chk ) ) );
 399             chk.m_nExpected = 90;
 400             CPPUNIT_ASSERT( m.find( 30, std::ref( chk ) ) );
 401             chk.m_nExpected = 54;
 402             CPPUNIT_ASSERT( m.find( 27, std::ref( chk ) ) );
 403
 404             ensureResult = m.ensure( 10, insert_functor<Map>() ) ;   // value = 50
 405             CPPUNIT_ASSERT( ensureResult.first );
 406             CPPUNIT_ASSERT( !ensureResult.second );
 407             chk.m_nExpected = 50;
 408             CPPUNIT_ASSERT( m.find( 10, std::ref( chk ) ) );
 409
 410             // erase test
 411             CPPUNIT_ASSERT( !m.find(100) );
 412             CPPUNIT_ASSERT( !m.erase( 100 )) ;  // not found
 413
 414             CPPUNIT_ASSERT( m.find(25) );
 415             CPPUNIT_ASSERT( check_size( m, 4 ));
 416             CPPUNIT_ASSERT( m.erase( 25 ));
 417             CPPUNIT_ASSERT( !m.empty() );
 418             CPPUNIT_ASSERT( check_size( m, 3 ));
 419             CPPUNIT_ASSERT( !m.find(25) );
 420             CPPUNIT_ASSERT( !m.erase( 25 ));
 421
 422             CPPUNIT_ASSERT( !m.find(258) );
 423             CPPUNIT_ASSERT( m.insert(258))
 424             CPPUNIT_ASSERT( check_size( m, 4 ));
 425             CPPUNIT_ASSERT( m.find_with(258, less()) );
 426             CPPUNIT_ASSERT( m.erase_with( 258, less() ));
 427             CPPUNIT_ASSERT( !m.empty() );
 428             CPPUNIT_ASSERT( check_size( m, 3 ));
 429             CPPUNIT_ASSERT( !m.find(258) );
 430             CPPUNIT_ASSERT( !m.erase_with( 258, less() ));
 431
 432             int nVal;
 433             extract_functor ext;
 434             ext.m_pVal = &nVal;
 435
 436             CPPUNIT_ASSERT( !m.find(29) );
 437             CPPUNIT_ASSERT( m.insert(29, 290));
 438             CPPUNIT_ASSERT( check_size( m, 4 ));
 439             CPPUNIT_ASSERT( m.erase_with( 29, less(), std::ref( ext ) ) );
 440             CPPUNIT_ASSERT( !m.empty() );
 441             CPPUNIT_ASSERT( check_size( m, 3 ));
 442             CPPUNIT_ASSERT( nVal == 290 );
 443             nVal = -1;
 444             CPPUNIT_ASSERT( !m.erase_with( 29, less(), std::ref( ext ) ) );
 445             CPPUNIT_ASSERT( nVal == -1 );
 446
 447             CPPUNIT_ASSERT( m.erase( 30, std::ref( ext ) ) );
 448             CPPUNIT_ASSERT( !m.empty() );
 449             CPPUNIT_ASSERT( check_size( m, 2 ));
 450             CPPUNIT_ASSERT( nVal == 90 );
 451             nVal = -1;
 452             CPPUNIT_ASSERT( !m.erase( 30, std::ref( ext ) ) );
 453             CPPUNIT_ASSERT( nVal == -1 );
 454
 455             m.clear();
 456             CPPUNIT_ASSERT( m.empty() );
 457             CPPUNIT_ASSERT( check_size( m, 0 ));
 458
 459             // emplace test
 460             CPPUNIT_ASSERT( m.emplace(126) ) ; // key = 126, val = 0
 461             CPPUNIT_ASSERT( m.emplace(137, 731))    ;   // key = 137, val = 731
 462             CPPUNIT_ASSERT( m.emplace( 149, value_type(941) ))   ;   // key = 149, val = 941
 463
 464             CPPUNIT_ASSERT( !m.empty() );
 465             CPPUNIT_ASSERT( check_size( m, 3 ));
 466
 467             chk.m_nExpected = 0;
 468             CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
 469             chk.m_nExpected = 731;
 470             CPPUNIT_ASSERT( m.find_with( 137, less(), std::ref(chk) ));
 471             chk.m_nExpected = 941;
 472             CPPUNIT_ASSERT( m.find( 149, std::ref(chk) ));
 473
 474             CPPUNIT_ASSERT( !m.emplace(126, 621)) ; // already in map
 475             chk.m_nExpected = 0;
 476             CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
 477             CPPUNIT_ASSERT( !m.empty() );
 478             CPPUNIT_ASSERT( check_size( m, 3 ));
 479
 480             m.clear();
 481             CPPUNIT_ASSERT( m.empty() );
 482             CPPUNIT_ASSERT( check_size( m, 0 ));
 483         }
 484
 485
 486         template <class Map>
 487         void test_int_nogc()
 488         {
 489             typedef typename Map::iterator          iterator;
 490             typedef typename Map::const_iterator    const_iterator;
 491
 492             {
 493                 Map m( 52, 4 );
 494
 495                 CPPUNIT_ASSERT( m.empty() );
 496                 CPPUNIT_ASSERT( check_size( m, 0 ));
 497
 498                 CPPUNIT_ASSERT( m.find(10) == m.end() );
 499                 iterator it = m.insert( 10 );
 500                 CPPUNIT_ASSERT( it != m.end() );
 501                 CPPUNIT_ASSERT( !m.empty() );
 502                 CPPUNIT_ASSERT( check_size( m, 1 ));
 503                 CPPUNIT_ASSERT( m.find(10) == it );
 504                 CPPUNIT_ASSERT( it->first == 10 );
 505                 CPPUNIT_ASSERT( it->second.m_val == 0 );
 506
 507                 CPPUNIT_ASSERT( m.find(100) == m.end() );
 508                 it = m.insert( 100, 200 );
 509                 CPPUNIT_ASSERT( it != m.end() );
 510                 CPPUNIT_ASSERT( !m.empty() );
 511                 CPPUNIT_ASSERT( check_size( m, 2 ));
 512                 CPPUNIT_ASSERT( m.find_with(100, less()) == it );
 513                 CPPUNIT_ASSERT( it->first == 100 );
 514                 CPPUNIT_ASSERT( it->second.m_val == 200 );
 515
 516                 CPPUNIT_ASSERT( m.find(55) == m.end() );
 517                 it = m.insert_with( 55, insert_functor<Map>() );
 518                 CPPUNIT_ASSERT( it != m.end() );
 519                 CPPUNIT_ASSERT( !m.empty() );
 520                 CPPUNIT_ASSERT( check_size( m, 3 ));
 521                 CPPUNIT_ASSERT( m.find(55) == it );
 522                 CPPUNIT_ASSERT( it->first == 55 );
 523                 CPPUNIT_ASSERT( it->second.m_val == 55 * 3 );
 524
 525                 CPPUNIT_ASSERT( m.insert( 55 ) == m.end() );
 526                 CPPUNIT_ASSERT( m.insert( 55, 10 ) == m.end() );
 527                 CPPUNIT_ASSERT( m.insert_with( 55, insert_functor<Map>()) == m.end() );
 528
 529                 CPPUNIT_ASSERT( m.find(10) != m.end() );
 530                 std::pair<iterator, bool> ensureResult = m.ensure( 10 );
 531                 CPPUNIT_ASSERT( ensureResult.first != m.end() );
 532                 CPPUNIT_ASSERT( !ensureResult.second  );
 533                 CPPUNIT_ASSERT( !m.empty() );
 534                 ensureResult.first->second.m_val = ensureResult.first->first * 5;
 535                 CPPUNIT_ASSERT( check_size( m, 3 ));
 536                 CPPUNIT_ASSERT( m.find(10) == ensureResult.first );
 537                 it = m.find(10);
 538                 CPPUNIT_ASSERT( it != m.end() );
 539                 CPPUNIT_ASSERT( it->second.m_val == 50 );
 540
 541                 CPPUNIT_ASSERT( m.find(120) == m.end() );
 542                 ensureResult = m.ensure( 120 );
 543                 CPPUNIT_ASSERT( ensureResult.first != m.end() );
 544                 CPPUNIT_ASSERT( ensureResult.second  );
 545                 CPPUNIT_ASSERT( !m.empty() );
 546                 CPPUNIT_ASSERT( check_size( m, 4 ));
 547                 ensureResult.first->second.m_val = ensureResult.first->first * 5;
 548                 CPPUNIT_ASSERT( m.find_with(120, less()) == ensureResult.first );
 549                 it = m.find_with(120, less());
 550                 CPPUNIT_ASSERT( it != m.end() );
 551                 CPPUNIT_ASSERT( it->second.m_val == 120 * 5 );
 552                 CPPUNIT_ASSERT( m.find_with(120, less()) == m.find(120) );
 553
 554                 // emplace test
 555                 it = m.emplace( 151 ) ;  // key = 151,  val = 0
 556                 CPPUNIT_ASSERT( it != m.end() );
 557                 CPPUNIT_ASSERT( it->first == 151 );
 558                 CPPUNIT_ASSERT( it->second.m_val == 0 );
 559
 560                 it = m.emplace( 174, 471 ) ; // key == 174, val = 471
 561                 CPPUNIT_ASSERT( it != m.end() );
 562                 CPPUNIT_ASSERT( it->first == 174 );
 563                 CPPUNIT_ASSERT( it->second.m_val == 471 );
 564
 565                 it = m.emplace( 190, value_type(91)) ; // key == 190, val = 19
 566                 CPPUNIT_ASSERT( it != m.end() );
 567                 CPPUNIT_ASSERT( it->first == 190 );
 568                 CPPUNIT_ASSERT( it->second.m_val == 91 );
 569
 570                 it = m.emplace( 151, 1051 );
 571                 CPPUNIT_ASSERT( it == m.end());
 572
 573                 it = m.find( 174 );
 574                 CPPUNIT_ASSERT( it != m.end() );
 575                 CPPUNIT_ASSERT( it->first == 174 );
 576                 CPPUNIT_ASSERT( it->second.m_val == 471 );
 577
 578                 it = m.find( 190 );
 579                 CPPUNIT_ASSERT( it != m.end() );
 580                 CPPUNIT_ASSERT( it->first == 190 );
 581                 CPPUNIT_ASSERT( it->second.m_val == 91 );
 582
 583                 it = m.find( 151 );
 584                 CPPUNIT_ASSERT( it != m.end() );
 585                 CPPUNIT_ASSERT( it->first == 151 );
 586                 CPPUNIT_ASSERT( it->second.m_val == 0 );
 587             }
 588
 589             // iterator test
 590
 591             {
 592                 Map m( 52, 4 );
 593
 594                 for ( int i = 0; i < 500; ++i ) {
 595                     CPPUNIT_ASSERT( m.insert( i, i * 2 ) != m.end() );
 596                 }
 597                 CPPUNIT_ASSERT( check_size( m, 500 ));
 598
 599                 {
 600                     typename Map::iterator it( m.begin() );
 601                     typename Map::const_iterator cit( m.cbegin() );
 602                     CPPUNIT_CHECK( it == cit );
 603                     CPPUNIT_CHECK( it != m.end() );
 604                     CPPUNIT_CHECK( it != m.cend() );
 605                     CPPUNIT_CHECK( cit != m.end() );
 606                     CPPUNIT_CHECK( cit != m.cend() );
 607                     ++it;
 608                     CPPUNIT_CHECK( it != cit );
 609                     CPPUNIT_CHECK( it != m.end() );
 610                     CPPUNIT_CHECK( it != m.cend() );
 611                     CPPUNIT_CHECK( cit != m.end() );
 612                     CPPUNIT_CHECK( cit != m.cend() );
 613                     ++cit;
 614                     CPPUNIT_CHECK( it == cit );
 615                     CPPUNIT_CHECK( it != m.end() );
 616                     CPPUNIT_CHECK( it != m.cend() );
 617                     CPPUNIT_CHECK( cit != m.end() );
 618                     CPPUNIT_CHECK( cit != m.cend() );
 619                 }
 620
 621
 622                 for ( iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it ) {
 623                     iterator it2 = it;
 624                     CPPUNIT_CHECK( it2 == it );
 625                     CPPUNIT_CHECK( it2 != itEnd );
 626                     CPPUNIT_ASSERT( it->first * 2 == (*it).second.m_val );
 627                     it->second = it->first;
 628                 }
 629
 630                 Map const& refMap = m;
 631                 for ( const_iterator it = refMap.begin(), itEnd = refMap.end(); it != itEnd; ++it ) {
 632                     CPPUNIT_ASSERT( it->first == it->second.m_val );
 633                     CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
 634                 }
 635             }
 636         }
 637
 638         template <class Map>
 639         void test_iter()
 640         {
 641             typedef typename Map::iterator          iterator;
 642             typedef typename Map::const_iterator    const_iterator;
 643
 644             Map s( 100, 4 );
 645
 646             const int nMaxCount = 500;
 647             for ( int i = 0; i < nMaxCount; ++i ) {
 648                 CPPUNIT_ASSERT( s.insert( i, i * 2 ));
 649             }
 650
 651             {
 652                 typename Map::iterator it( s.begin() );
 653                 typename Map::const_iterator cit( s.cbegin() );
 654                 CPPUNIT_CHECK( it == cit );
 655                 CPPUNIT_CHECK( it != s.end() );
 656                 CPPUNIT_CHECK( it != s.cend() );
 657                 CPPUNIT_CHECK( cit != s.end() );
 658                 CPPUNIT_CHECK( cit != s.cend() );
 659                 ++it;
 660                 CPPUNIT_CHECK( it != cit );
 661                 CPPUNIT_CHECK( it != s.end() );
 662                 CPPUNIT_CHECK( it != s.cend() );
 663                 CPPUNIT_CHECK( cit != s.end() );
 664                 CPPUNIT_CHECK( cit != s.cend() );
 665                 ++cit;
 666                 CPPUNIT_CHECK( it == cit );
 667                 CPPUNIT_CHECK( it != s.end() );
 668                 CPPUNIT_CHECK( it != s.cend() );
 669                 CPPUNIT_CHECK( cit != s.end() );
 670                 CPPUNIT_CHECK( cit != s.cend() );
 671             }
 672
 673             int nCount = 0;
 674             for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 675                 CPPUNIT_ASSERT( it->first * 2 == it->second.m_val );
 676                 CPPUNIT_ASSERT( (*it).first * 2 == (*it).second.m_val );
 677                 it->second.m_val = it->first;
 678                 ++nCount;
 679             }
 680             CPPUNIT_ASSERT( nCount == nMaxCount );
 681
 682             Map const& refSet = s;
 683             nCount = 0;
 684             for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
 685                 CPPUNIT_ASSERT( it->first == it->second.m_val );
 686                 CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
 687                 ++nCount;
 688             }
 689             CPPUNIT_ASSERT( nCount == nMaxCount );
 690         }
 691
 692
 693         void Michael_HP_cmp();
 694         void Michael_HP_less();
 695         void Michael_HP_cmpmix();
 696
 697         void Michael_DHP_cmp();
 698         void Michael_DHP_less();
 699         void Michael_DHP_cmpmix();
 700
 701         void Michael_RCU_GPI_cmp();
 702         void Michael_RCU_GPI_less();
 703         void Michael_RCU_GPI_cmpmix();
 704
 705         void Michael_RCU_GPB_cmp();
 706         void Michael_RCU_GPB_less();
 707         void Michael_RCU_GPB_cmpmix();
 708
 709         void Michael_RCU_GPT_cmp();
 710         void Michael_RCU_GPT_less();
 711         void Michael_RCU_GPT_cmpmix();
 712
 713         void Michael_RCU_SHB_cmp();
 714         void Michael_RCU_SHB_less();
 715         void Michael_RCU_SHB_cmpmix();
 716
 717         void Michael_RCU_SHT_cmp();
 718         void Michael_RCU_SHT_less();
 719         void Michael_RCU_SHT_cmpmix();
 720
 721         void Michael_nogc_cmp();
 722         void Michael_nogc_less();
 723         void Michael_nogc_cmpmix();
 724
 725         void Lazy_HP_cmp();
 726         void Lazy_HP_less();
 727         void Lazy_HP_cmpmix();
 728
 729         void Lazy_DHP_cmp();
 730         void Lazy_DHP_less();
 731         void Lazy_DHP_cmpmix();
 732
 733         void Lazy_RCU_GPI_cmp();
 734         void Lazy_RCU_GPI_less();
 735         void Lazy_RCU_GPI_cmpmix();
 736
 737         void Lazy_RCU_GPB_cmp();
 738         void Lazy_RCU_GPB_less();
 739         void Lazy_RCU_GPB_cmpmix();
 740
 741         void Lazy_RCU_GPT_cmp();
 742         void Lazy_RCU_GPT_less();
 743         void Lazy_RCU_GPT_cmpmix();
 744
 745         void Lazy_RCU_SHB_cmp();
 746         void Lazy_RCU_SHB_less();
 747         void Lazy_RCU_SHB_cmpmix();
 748
 749         void Lazy_RCU_SHT_cmp();
 750         void Lazy_RCU_SHT_less();
 751         void Lazy_RCU_SHT_cmpmix();
 752
 753         void Lazy_nogc_cmp();
 754         void Lazy_nogc_less();
 755         void Lazy_nogc_cmpmix();
 756
 757         void Split_HP_cmp();
 758         void Split_HP_less();
 759         void Split_HP_cmpmix();
 760         void Split_HP_cmpmix_stat();
 761
 762         void Split_DHP_cmp();
 763         void Split_DHP_less();
 764         void Split_DHP_cmpmix();
 765         void Split_DHP_cmpmix_stat();
 766
 767         void Split_RCU_GPI_cmp();
 768         void Split_RCU_GPI_less();
 769         void Split_RCU_GPI_cmpmix();
 770         void Split_RCU_GPI_cmpmix_stat();
 771
 772         void Split_RCU_GPB_cmp();
 773         void Split_RCU_GPB_less();
 774         void Split_RCU_GPB_cmpmix();
 775         void Split_RCU_GPB_cmpmix_stat();
 776
 777         void Split_RCU_GPT_cmp();
 778         void Split_RCU_GPT_less();
 779         void Split_RCU_GPT_cmpmix();
 780         void Split_RCU_GPT_cmpmix_stat();
 781
 782         void Split_RCU_SHB_cmp();
 783         void Split_RCU_SHB_less();
 784         void Split_RCU_SHB_cmpmix();
 785         void Split_RCU_SHB_cmpmix_stat();
 786
 787         void Split_RCU_SHT_cmp();
 788         void Split_RCU_SHT_less();
 789         void Split_RCU_SHT_cmpmix();
 790         void Split_RCU_SHT_cmpmix_stat();
 791
 792         void Split_nogc_cmp();
 793         void Split_nogc_less();
 794         void Split_nogc_cmpmix();
 795         void Split_nogc_cmpmix_stat();
 796
 797         void Split_Lazy_HP_cmp();
 798         void Split_Lazy_HP_less();
 799         void Split_Lazy_HP_cmpmix();
 800         void Split_Lazy_HP_cmpmix_stat();
 801
 802         void Split_Lazy_DHP_cmp();
 803         void Split_Lazy_DHP_less();
 804         void Split_Lazy_DHP_cmpmix();
 805         void Split_Lazy_DHP_cmpmix_stat();
 806
 807         void Split_Lazy_RCU_GPI_cmp();
 808         void Split_Lazy_RCU_GPI_less();
 809         void Split_Lazy_RCU_GPI_cmpmix();
 810         void Split_Lazy_RCU_GPI_cmpmix_stat();
 811
 812         void Split_Lazy_RCU_GPB_cmp();
 813         void Split_Lazy_RCU_GPB_less();
 814         void Split_Lazy_RCU_GPB_cmpmix();
 815         void Split_Lazy_RCU_GPB_cmpmix_stat();
 816
 817         void Split_Lazy_RCU_GPT_cmp();
 818         void Split_Lazy_RCU_GPT_less();
 819         void Split_Lazy_RCU_GPT_cmpmix();
 820         void Split_Lazy_RCU_GPT_cmpmix_stat();
 821
 822         void Split_Lazy_RCU_SHB_cmp();
 823         void Split_Lazy_RCU_SHB_less();
 824         void Split_Lazy_RCU_SHB_cmpmix();
 825         void Split_Lazy_RCU_SHB_cmpmix_stat();
 826
 827         void Split_Lazy_RCU_SHT_cmp();
 828         void Split_Lazy_RCU_SHT_less();
 829         void Split_Lazy_RCU_SHT_cmpmix();
 830         void Split_Lazy_RCU_SHT_cmpmix_stat();
 831
 832         void Split_Lazy_nogc_cmp();
 833         void Split_Lazy_nogc_less();
 834         void Split_Lazy_nogc_cmpmix();
 835         void Split_Lazy_nogc_cmpmix_stat();
 836
 837         CPPUNIT_TEST_SUITE(HashMapHdrTest)
 838             CPPUNIT_TEST(Michael_HP_cmp)
 839             CPPUNIT_TEST(Michael_HP_less)
 840             CPPUNIT_TEST(Michael_HP_cmpmix)
 841
 842             CPPUNIT_TEST(Michael_DHP_cmp)
 843             CPPUNIT_TEST(Michael_DHP_less)
 844             CPPUNIT_TEST(Michael_DHP_cmpmix)
 845
 846             CPPUNIT_TEST(Michael_RCU_GPI_cmp)
 847             CPPUNIT_TEST(Michael_RCU_GPI_less)
 848             CPPUNIT_TEST(Michael_RCU_GPI_cmpmix)
 849
 850             CPPUNIT_TEST(Michael_RCU_GPB_cmp)
 851             CPPUNIT_TEST(Michael_RCU_GPB_less)
 852             CPPUNIT_TEST(Michael_RCU_GPB_cmpmix)
 853
 854             CPPUNIT_TEST(Michael_RCU_SHT_cmp)
 855             CPPUNIT_TEST(Michael_RCU_SHT_less)
 856             CPPUNIT_TEST(Michael_RCU_SHT_cmpmix)
 857
 858             CPPUNIT_TEST(Michael_RCU_SHB_cmp)
 859             CPPUNIT_TEST(Michael_RCU_SHB_less)
 860             CPPUNIT_TEST(Michael_RCU_SHB_cmpmix)
 861
 862             CPPUNIT_TEST(Michael_RCU_GPT_cmp)
 863             CPPUNIT_TEST(Michael_RCU_GPT_less)
 864             CPPUNIT_TEST(Michael_RCU_GPT_cmpmix)
 865
 866             CPPUNIT_TEST(Michael_nogc_cmp)
 867             CPPUNIT_TEST(Michael_nogc_less)
 868             CPPUNIT_TEST(Michael_nogc_cmpmix)
 869
 870             CPPUNIT_TEST(Lazy_HP_cmp)
 871             CPPUNIT_TEST(Lazy_HP_less)
 872             CPPUNIT_TEST(Lazy_HP_cmpmix)
 873
 874             CPPUNIT_TEST(Lazy_DHP_cmp)
 875             CPPUNIT_TEST(Lazy_DHP_less)
 876             CPPUNIT_TEST(Lazy_DHP_cmpmix)
 877
 878             CPPUNIT_TEST(Lazy_RCU_GPI_cmp)
 879             CPPUNIT_TEST(Lazy_RCU_GPI_less)
 880             CPPUNIT_TEST(Lazy_RCU_GPI_cmpmix)
 881
 882             CPPUNIT_TEST(Lazy_RCU_GPB_cmp)
 883             CPPUNIT_TEST(Lazy_RCU_GPB_less)
 884             CPPUNIT_TEST(Lazy_RCU_GPB_cmpmix)
 885
 886             CPPUNIT_TEST(Lazy_RCU_GPT_cmp)
 887             CPPUNIT_TEST(Lazy_RCU_GPT_less)
 888             CPPUNIT_TEST(Lazy_RCU_GPT_cmpmix)
 889
 890             CPPUNIT_TEST(Lazy_RCU_SHB_cmp)
 891             CPPUNIT_TEST(Lazy_RCU_SHB_less)
 892             CPPUNIT_TEST(Lazy_RCU_SHB_cmpmix)
 893
 894             CPPUNIT_TEST(Lazy_RCU_SHT_cmp)
 895             CPPUNIT_TEST(Lazy_RCU_SHT_less)
 896             CPPUNIT_TEST(Lazy_RCU_SHT_cmpmix)
 897
 898             CPPUNIT_TEST(Lazy_nogc_cmp)
 899             CPPUNIT_TEST(Lazy_nogc_less)
 900             CPPUNIT_TEST(Lazy_nogc_cmpmix)
 901
 902             CPPUNIT_TEST(Split_HP_cmp)
 903             CPPUNIT_TEST(Split_HP_less)
 904             CPPUNIT_TEST(Split_HP_cmpmix)
 905             CPPUNIT_TEST( Split_HP_cmpmix_stat )
 906
 907             CPPUNIT_TEST(Split_DHP_cmp)
 908             CPPUNIT_TEST(Split_DHP_less)
 909             CPPUNIT_TEST(Split_DHP_cmpmix)
 910             CPPUNIT_TEST( Split_DHP_cmpmix_stat )
 911
 912             CPPUNIT_TEST(Split_RCU_GPI_cmp)
 913             CPPUNIT_TEST(Split_RCU_GPI_less)
 914             CPPUNIT_TEST(Split_RCU_GPI_cmpmix)
 915             CPPUNIT_TEST( Split_RCU_GPI_cmpmix_stat )
 916
 917             CPPUNIT_TEST(Split_RCU_GPB_cmp)
 918             CPPUNIT_TEST(Split_RCU_GPB_less)
 919             CPPUNIT_TEST(Split_RCU_GPB_cmpmix)
 920             CPPUNIT_TEST( Split_RCU_GPB_cmpmix_stat )
 921
 922             CPPUNIT_TEST(Split_RCU_GPT_cmp)
 923             CPPUNIT_TEST(Split_RCU_GPT_less)
 924             CPPUNIT_TEST(Split_RCU_GPT_cmpmix)
 925             CPPUNIT_TEST( Split_RCU_GPT_cmpmix_stat )
 926
 927             CPPUNIT_TEST(Split_RCU_SHB_cmp)
 928             CPPUNIT_TEST(Split_RCU_SHB_less)
 929             CPPUNIT_TEST(Split_RCU_SHB_cmpmix)
 930             CPPUNIT_TEST( Split_RCU_SHB_cmpmix_stat )
 931
 932             CPPUNIT_TEST(Split_RCU_SHT_cmp)
 933             CPPUNIT_TEST(Split_RCU_SHT_less)
 934             CPPUNIT_TEST(Split_RCU_SHT_cmpmix)
 935             CPPUNIT_TEST( Split_RCU_SHT_cmpmix_stat )
 936
 937             CPPUNIT_TEST(Split_nogc_cmp)
 938             CPPUNIT_TEST(Split_nogc_less)
 939             CPPUNIT_TEST(Split_nogc_cmpmix)
 940             CPPUNIT_TEST( Split_nogc_cmpmix_stat )
 941
 942             CPPUNIT_TEST(Split_Lazy_HP_cmp)
 943             CPPUNIT_TEST(Split_Lazy_HP_less)
 944             CPPUNIT_TEST(Split_Lazy_HP_cmpmix)
 945             CPPUNIT_TEST( Split_Lazy_HP_cmpmix_stat )
 946
 947             CPPUNIT_TEST(Split_Lazy_DHP_cmp)
 948             CPPUNIT_TEST(Split_Lazy_DHP_less)
 949             CPPUNIT_TEST(Split_Lazy_DHP_cmpmix)
 950             CPPUNIT_TEST( Split_Lazy_DHP_cmpmix_stat )
 951
 952             CPPUNIT_TEST(Split_Lazy_RCU_GPI_cmp)
 953             CPPUNIT_TEST(Split_Lazy_RCU_GPI_less)
 954             CPPUNIT_TEST(Split_Lazy_RCU_GPI_cmpmix)
 955             CPPUNIT_TEST( Split_Lazy_RCU_GPI_cmpmix_stat )
 956
 957             CPPUNIT_TEST(Split_Lazy_RCU_GPB_cmp)
 958             CPPUNIT_TEST(Split_Lazy_RCU_GPB_less)
 959             CPPUNIT_TEST(Split_Lazy_RCU_GPB_cmpmix)
 960             CPPUNIT_TEST( Split_Lazy_RCU_GPB_cmpmix_stat )
 961
 962             CPPUNIT_TEST(Split_Lazy_RCU_GPT_cmp)
 963             CPPUNIT_TEST(Split_Lazy_RCU_GPT_less)
 964             CPPUNIT_TEST(Split_Lazy_RCU_GPT_cmpmix)
 965             CPPUNIT_TEST( Split_Lazy_RCU_GPT_cmpmix_stat )
 966
 967             CPPUNIT_TEST(Split_Lazy_RCU_SHB_cmp)
 968             CPPUNIT_TEST(Split_Lazy_RCU_SHB_less)
 969             CPPUNIT_TEST(Split_Lazy_RCU_SHB_cmpmix)
 970             CPPUNIT_TEST( Split_Lazy_RCU_SHB_cmpmix_stat )
 971
 972             CPPUNIT_TEST(Split_Lazy_RCU_SHT_cmp)
 973             CPPUNIT_TEST(Split_Lazy_RCU_SHT_less)
 974             CPPUNIT_TEST(Split_Lazy_RCU_SHT_cmpmix)
 975             CPPUNIT_TEST( Split_Lazy_RCU_SHT_cmpmix_stat )
 976
 977             CPPUNIT_TEST(Split_Lazy_nogc_cmp)
 978             CPPUNIT_TEST(Split_Lazy_nogc_less)
 979             CPPUNIT_TEST(Split_Lazy_nogc_cmpmix)
 980             CPPUNIT_TEST( Split_Lazy_nogc_cmpmix_stat )
 981             CPPUNIT_TEST_SUITE_END()
 982
 983     };
 984 }   // namespace map
 985
 986 #endif // #ifndef CDSTEST_HDR_MAP_H