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