tests/test-hdr/map/hdr_striped_map.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDSTEST_HDR_STRIPED_MAP_H
   4 #define __CDSTEST_HDR_STRIPED_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     class StripedMapHdrTest: public CppUnitMini::TestCase
  22     {
  23     public:
  24         typedef int key_type;
  25
  26         struct value_type {
  27             int m_val;
  28
  29             value_type()
  30                 : m_val(0)
  31             {}
  32
  33             value_type( int n )
  34                 : m_val( n )
  35             {}
  36
  37             value_type( value_type&& v )
  38                 : m_val( v.m_val )
  39             {}
  40
  41             value_type( value_type const& v )
  42                 : m_val( v.m_val )
  43             {}
  44
  45             value_type& operator=( value_type const& v )
  46             {
  47                 m_val = v.m_val;
  48                 return *this;
  49             }
  50         };
  51
  52         typedef std::pair<key_type const, value_type> pair_type;
  53
  54         struct less
  55         {
  56             bool operator ()(int v1, int v2 ) const
  57             {
  58                 return v1 < v2;
  59             }
  60         };
  61
  62         struct cmp {
  63             int operator ()(int v1, int v2 ) const
  64             {
  65                 if ( v1 < v2 )
  66                     return -1;
  67                 return v1 > v2 ? 1 : 0;
  68             }
  69         };
  70
  71         struct equal {
  72             bool operator ()(int v1, int v2 ) const
  73             {
  74                 return v1 == v2;
  75             }
  76         };
  77
  78         struct hash_int {
  79             size_t operator()( int i ) const
  80             {
  81                 return co::v::hash<int>()( i );
  82             }
  83         };
  84
  85         struct simple_item_counter {
  86             size_t  m_nCount;
  87
  88             simple_item_counter()
  89                 : m_nCount(0)
  90             {}
  91
  92             size_t operator ++()
  93             {
  94                 return ++m_nCount;
  95             }
  96
  97             size_t operator --()
  98             {
  99                 return --m_nCount;
 100             }
 101
 102             void reset()
 103             {
 104                 m_nCount = 0;
 105             }
 106
 107             operator size_t() const
 108             {
 109                 return m_nCount;
 110             }
 111         };
 112
 113         template <typename Map>
 114         struct insert_functor
 115         {
 116             typedef typename Map::value_type pair_type;
 117
 118             // insert ftor
 119             void operator()( pair_type& item )
 120             {
 121                 item.second.m_val = item.first * 3;
 122             }
 123
 124             // ensure ftor
 125             void operator()( bool bNew, pair_type& item )
 126             {
 127                 if ( bNew )
 128                     item.second.m_val = item.first * 2;
 129                 else
 130                     item.second.m_val = item.first * 5;
 131             }
 132         };
 133
 134         struct check_value {
 135             int     m_nExpected;
 136
 137             check_value( int nExpected )
 138                 : m_nExpected( nExpected )
 139             {}
 140
 141             template <typename T>
 142             void operator ()( T& pair )
 143             {
 144                 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
 145             }
 146             template <typename T, typename Q>
 147             void operator ()( T& pair, Q )
 148             {
 149                 CPPUNIT_ASSERT_CURRENT( pair.second.m_val == m_nExpected );
 150             }
 151         };
 152
 153         struct extract_functor
 154         {
 155             int *   m_pVal;
 156             void operator()( pair_type const& val )
 157             {
 158                 *m_pVal = val.second.m_val;
 159             }
 160         };
 161
 162         template <class Map>
 163         void test_int_with( Map& m )
 164         {
 165             std::pair<bool, bool> ensureResult;
 166
 167             // insert
 168             CPPUNIT_ASSERT( m.empty() );
 169             CPPUNIT_ASSERT( check_size( m, 0 ));
 170             CPPUNIT_ASSERT( !m.find(25) );
 171             CPPUNIT_ASSERT( m.insert( 25 ) )    ;   // value = 0
 172             CPPUNIT_ASSERT( m.find(25) );
 173             CPPUNIT_ASSERT( !m.empty() );
 174             CPPUNIT_ASSERT( check_size( m, 1 ));
 175             CPPUNIT_ASSERT( m.find(25) );
 176
 177             CPPUNIT_ASSERT( !m.insert( 25 ) );
 178             CPPUNIT_ASSERT( !m.empty() );
 179             CPPUNIT_ASSERT( check_size( m, 1 ));
 180
 181             CPPUNIT_ASSERT( !m.find(10) );
 182             CPPUNIT_ASSERT( m.insert( 10, 10 ) );
 183             CPPUNIT_ASSERT( !m.empty() );
 184             CPPUNIT_ASSERT( check_size( m, 2 ));
 185             CPPUNIT_ASSERT( m.find(10) );
 186
 187             CPPUNIT_ASSERT( !m.insert( 10, 20 ) );
 188             CPPUNIT_ASSERT( !m.empty() );
 189             CPPUNIT_ASSERT( check_size( m, 2 ));
 190
 191             CPPUNIT_ASSERT( !m.find(30) );
 192             CPPUNIT_ASSERT( m.insert_key( 30, insert_functor<Map>() ) )    ; // value = 90
 193             CPPUNIT_ASSERT( !m.empty() );
 194             CPPUNIT_ASSERT( check_size( m, 3 ));
 195             CPPUNIT_ASSERT( m.find(30) );
 196
 197             CPPUNIT_ASSERT( !m.insert_key( 10, insert_functor<Map>() ) );
 198             CPPUNIT_ASSERT( !m.insert_key( 25, insert_functor<Map>() ) );
 199             CPPUNIT_ASSERT( !m.insert_key( 30, insert_functor<Map>() ) );
 200
 201             // ensure (new key)
 202             CPPUNIT_ASSERT( !m.find(27) );
 203             ensureResult = m.ensure( 27, insert_functor<Map>() ) ;   // value = 54
 204             CPPUNIT_ASSERT( ensureResult.first );
 205             CPPUNIT_ASSERT( ensureResult.second );
 206             CPPUNIT_ASSERT( check_size( m, 4 ));
 207             CPPUNIT_ASSERT( m.find(27) );
 208
 209             // find test
 210             check_value chk(10);
 211             CPPUNIT_ASSERT( m.find( 10, cds::ref(chk) ));
 212             chk.m_nExpected = 0;
 213             CPPUNIT_ASSERT( m.find( 25, boost::ref(chk) ));
 214             chk.m_nExpected = 90;
 215             CPPUNIT_ASSERT( m.find( 30, boost::ref(chk) ));
 216             chk.m_nExpected = 54;
 217             CPPUNIT_ASSERT( m.find( 27, boost::ref(chk) ));
 218
 219             ensureResult = m.ensure( 10, insert_functor<Map>() ) ;   // value = 50
 220             CPPUNIT_ASSERT( ensureResult.first );
 221             CPPUNIT_ASSERT( !ensureResult.second );
 222             chk.m_nExpected = 50;
 223             CPPUNIT_ASSERT( m.find( 10, boost::ref(chk) ));
 224
 225             // erase test
 226             CPPUNIT_ASSERT( !m.find(100) );
 227             CPPUNIT_ASSERT( !m.erase( 100 )) ;  // not found
 228
 229             CPPUNIT_ASSERT( m.find(25) );
 230             CPPUNIT_ASSERT( check_size( m, 4 ));
 231             CPPUNIT_ASSERT( m.erase( 25 ));
 232             CPPUNIT_ASSERT( !m.empty() );
 233             CPPUNIT_ASSERT( check_size( m, 3 ));
 234             CPPUNIT_ASSERT( !m.find(25) );
 235             CPPUNIT_ASSERT( !m.erase( 25 ));
 236
 237             CPPUNIT_ASSERT( !m.find(258) );
 238             CPPUNIT_ASSERT( m.insert(258))
 239             CPPUNIT_ASSERT( check_size( m, 4 ));
 240             CPPUNIT_ASSERT( m.find(258) );
 241             CPPUNIT_ASSERT( m.erase( 258 ));
 242             CPPUNIT_ASSERT( !m.empty() );
 243             CPPUNIT_ASSERT( check_size( m, 3 ));
 244             CPPUNIT_ASSERT( !m.find(258) );
 245             CPPUNIT_ASSERT( !m.erase( 258 ));
 246
 247             int nVal;
 248             extract_functor ext;
 249             ext.m_pVal = &nVal;
 250
 251             CPPUNIT_ASSERT( !m.find(29) );
 252             CPPUNIT_ASSERT( m.insert(29, 290));
 253             CPPUNIT_ASSERT( check_size( m, 4 ));
 254             CPPUNIT_ASSERT( m.erase( 29, boost::ref(ext)));
 255             CPPUNIT_ASSERT( !m.empty() );
 256             CPPUNIT_ASSERT( check_size( m, 3 ));
 257             CPPUNIT_ASSERT( nVal == 290 );
 258             nVal = -1;
 259             CPPUNIT_ASSERT( !m.erase( 29, boost::ref(ext)));
 260             CPPUNIT_ASSERT( nVal == -1 );
 261
 262             CPPUNIT_ASSERT( m.erase( 30, boost::ref(ext)));
 263             CPPUNIT_ASSERT( !m.empty() );
 264             CPPUNIT_ASSERT( check_size( m, 2 ));
 265             CPPUNIT_ASSERT( nVal == 90 );
 266             nVal = -1;
 267             CPPUNIT_ASSERT( !m.erase( 30, boost::ref(ext)));
 268             CPPUNIT_ASSERT( nVal == -1 );
 269
 270             m.clear();
 271             CPPUNIT_ASSERT( m.empty() );
 272             CPPUNIT_ASSERT( check_size( m, 0 ));
 273
 274 #       ifdef CDS_EMPLACE_SUPPORT
 275             // emplace test
 276             CPPUNIT_ASSERT( m.emplace(126) ) ; // key = 126, val = 0
 277             CPPUNIT_ASSERT( m.emplace(137, 731))    ;   // key = 137, val = 731
 278             CPPUNIT_ASSERT( m.emplace( 149, value_type(941) ))   ;   // key = 149, val = 941
 279
 280             CPPUNIT_ASSERT( !m.empty() );
 281             CPPUNIT_ASSERT( check_size( m, 3 ));
 282
 283             chk.m_nExpected = 0;
 284             CPPUNIT_ASSERT( m.find( 126, cds::ref(chk) ));
 285             chk.m_nExpected = 731;
 286             CPPUNIT_ASSERT( m.find( 137, cds::ref(chk) ));
 287             chk.m_nExpected = 941;
 288             CPPUNIT_ASSERT( m.find( 149, cds::ref(chk) ));
 289
 290             CPPUNIT_ASSERT( !m.emplace(126, 621)) ; // already in map
 291             chk.m_nExpected = 0;
 292             CPPUNIT_ASSERT( m.find( 126, cds::ref(chk) ));
 293             CPPUNIT_ASSERT( !m.empty() );
 294             CPPUNIT_ASSERT( check_size( m, 3 ));
 295
 296             m.clear();
 297             CPPUNIT_ASSERT( m.empty() );
 298             CPPUNIT_ASSERT( check_size( m, 0 ));
 299
 300 #       endif
 301         }
 302
 303         template <class Map>
 304         void test_iter( Map& s)
 305         {
 306             typedef typename Map::iterator          iterator;
 307             typedef typename Map::const_iterator    const_iterator;
 308
 309             const int nMaxCount = 500;
 310             for ( int i = 0; i < nMaxCount; ++i ) {
 311                 CPPUNIT_ASSERT( s.insert( i, i * 2 ));
 312             }
 313
 314             int nCount = 0;
 315             for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 316                 CPPUNIT_ASSERT( it->first * 2 == it->second.m_val );
 317                 CPPUNIT_ASSERT( (*it).first * 2 == (*it).second.m_val );
 318                 it->second.m_val = it->first;
 319                 ++nCount;
 320             }
 321             CPPUNIT_ASSERT( nCount == nMaxCount );
 322
 323             Map const& refSet = s;
 324             nCount = 0;
 325             for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
 326                 CPPUNIT_ASSERT( it->first == it->second.m_val );
 327                 CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
 328                 ++nCount;
 329             }
 330             CPPUNIT_ASSERT( nCount == nMaxCount );
 331         }
 332
 333         template <class Map>
 334         void test_striped()
 335         {
 336             Map m( 30 );
 337             CPPUNIT_ASSERT( m.bucket_count() == 32 );
 338             CPPUNIT_ASSERT( m.lock_count() == 32 );
 339
 340             test_striped_with(m);
 341         }
 342
 343         template <class Map>
 344         void test_striped_with(Map& m)
 345         {
 346             cds::OS::Timer    timer;
 347
 348             test_int_with( m );
 349
 350             // Iterators is not yet supported
 351             //m.clear();
 352             //CPPUNIT_ASSERT( m.empty() );
 353             //CPPUNIT_ASSERT( check_size( m, 0 ));
 354             //test_iter(m);
 355
 356             m.clear();
 357             CPPUNIT_ASSERT( m.empty() );
 358             CPPUNIT_ASSERT( check_size( m, 0 ));
 359
 360             // Resizing test
 361             for ( int i = 0; i < 40000; i++ ) {
 362                 m.insert( i );
 363             }
 364
 365             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 366         }
 367
 368         //*******************************************
 369         // If erase_with && find_with are supported
 370         template <class Map>
 371         void test_int_with2( Map& m )
 372         {
 373             std::pair<bool, bool> ensureResult;
 374
 375             // insert
 376             CPPUNIT_ASSERT( m.empty() );
 377             CPPUNIT_ASSERT( check_size( m, 0 ));
 378             CPPUNIT_ASSERT( !m.find(25) );
 379             CPPUNIT_ASSERT( m.insert( 25 ) )    ;   // value = 0
 380             CPPUNIT_ASSERT( m.find(25) );
 381             CPPUNIT_ASSERT( !m.empty() );
 382             CPPUNIT_ASSERT( check_size( m, 1 ));
 383             CPPUNIT_ASSERT( m.find(25) );
 384
 385             CPPUNIT_ASSERT( !m.insert( 25 ) );
 386             CPPUNIT_ASSERT( !m.empty() );
 387             CPPUNIT_ASSERT( check_size( m, 1 ));
 388
 389             CPPUNIT_ASSERT( !m.find_with(10, less()) );
 390             CPPUNIT_ASSERT( m.insert( 10, 10 ) );
 391             CPPUNIT_ASSERT( !m.empty() );
 392             CPPUNIT_ASSERT( check_size( m, 2 ));
 393             CPPUNIT_ASSERT( m.find_with(10, less()) );
 394
 395             CPPUNIT_ASSERT( !m.insert( 10, 20 ) );
 396             CPPUNIT_ASSERT( !m.empty() );
 397             CPPUNIT_ASSERT( check_size( m, 2 ));
 398
 399             CPPUNIT_ASSERT( !m.find(30) );
 400             CPPUNIT_ASSERT( m.insert_key( 30, insert_functor<Map>() ) )    ; // value = 90
 401             CPPUNIT_ASSERT( !m.empty() );
 402             CPPUNIT_ASSERT( check_size( m, 3 ));
 403             CPPUNIT_ASSERT( m.find(30) );
 404
 405             CPPUNIT_ASSERT( !m.insert_key( 10, insert_functor<Map>() ) );
 406             CPPUNIT_ASSERT( !m.insert_key( 25, insert_functor<Map>() ) );
 407             CPPUNIT_ASSERT( !m.insert_key( 30, insert_functor<Map>() ) );
 408
 409             // ensure (new key)
 410             CPPUNIT_ASSERT( !m.find(27) );
 411             ensureResult = m.ensure( 27, insert_functor<Map>() ) ;   // value = 54
 412             CPPUNIT_ASSERT( ensureResult.first );
 413             CPPUNIT_ASSERT( ensureResult.second );
 414             CPPUNIT_ASSERT( m.find(27) );
 415
 416             // find test
 417             check_value chk(10);
 418             CPPUNIT_ASSERT( m.find( 10, cds::ref(chk) ));
 419             chk.m_nExpected = 0;
 420             CPPUNIT_ASSERT( m.find_with( 25, less(), boost::ref(chk) ));
 421             chk.m_nExpected = 90;
 422             CPPUNIT_ASSERT( m.find( 30, boost::ref(chk) ));
 423             chk.m_nExpected = 54;
 424             CPPUNIT_ASSERT( m.find( 27, boost::ref(chk) ));
 425
 426             ensureResult = m.ensure( 10, insert_functor<Map>() ) ;   // value = 50
 427             CPPUNIT_ASSERT( ensureResult.first );
 428             CPPUNIT_ASSERT( !ensureResult.second );
 429             chk.m_nExpected = 50;
 430             CPPUNIT_ASSERT( m.find( 10, boost::ref(chk) ));
 431
 432             // erase test
 433             CPPUNIT_ASSERT( !m.find(100) );
 434             CPPUNIT_ASSERT( !m.erase( 100 )) ;  // not found
 435
 436             CPPUNIT_ASSERT( m.find(25) );
 437             CPPUNIT_ASSERT( check_size( m, 4 ));
 438             CPPUNIT_ASSERT( m.erase( 25 ));
 439             CPPUNIT_ASSERT( !m.empty() );
 440             CPPUNIT_ASSERT( check_size( m, 3 ));
 441             CPPUNIT_ASSERT( !m.find(25) );
 442             CPPUNIT_ASSERT( !m.erase( 25 ));
 443
 444             CPPUNIT_ASSERT( !m.find(258) );
 445             CPPUNIT_ASSERT( m.insert(258))
 446             CPPUNIT_ASSERT( check_size( m, 4 ));
 447             CPPUNIT_ASSERT( m.find_with(258, less()) );
 448             CPPUNIT_ASSERT( m.erase_with( 258, less() ));
 449             CPPUNIT_ASSERT( !m.empty() );
 450             CPPUNIT_ASSERT( check_size( m, 3 ));
 451             CPPUNIT_ASSERT( !m.find(258) );
 452             CPPUNIT_ASSERT( !m.erase_with( 258, less() ));
 453
 454             int nVal;
 455             extract_functor ext;
 456             ext.m_pVal = &nVal;
 457
 458             CPPUNIT_ASSERT( !m.find(29) );
 459             CPPUNIT_ASSERT( m.insert(29, 290))
 460             CPPUNIT_ASSERT( m.erase_with( 29, less(), boost::ref(ext)));
 461             CPPUNIT_ASSERT( !m.empty() );
 462             CPPUNIT_ASSERT( check_size( m, 3 ));
 463             CPPUNIT_ASSERT( nVal == 290 );
 464             nVal = -1;
 465             CPPUNIT_ASSERT( !m.erase_with( 29, less(), boost::ref(ext)));
 466             CPPUNIT_ASSERT( nVal == -1 );
 467
 468             CPPUNIT_ASSERT( m.erase( 30, boost::ref(ext)));
 469             CPPUNIT_ASSERT( !m.empty() );
 470             CPPUNIT_ASSERT( check_size( m, 2 ));
 471             CPPUNIT_ASSERT( nVal == 90 );
 472             nVal = -1;
 473             CPPUNIT_ASSERT( !m.erase( 30, boost::ref(ext)));
 474             CPPUNIT_ASSERT( nVal == -1 );
 475
 476             m.clear();
 477             CPPUNIT_ASSERT( m.empty() );
 478             CPPUNIT_ASSERT( check_size( m, 0 ));
 479
 480 #       ifdef CDS_EMPLACE_SUPPORT
 481             // emplace test
 482             CPPUNIT_ASSERT( m.emplace(126) ) ; // key = 126, val = 0
 483             CPPUNIT_ASSERT( m.emplace(137, 731))    ;   // key = 137, val = 731
 484             CPPUNIT_ASSERT( m.emplace( 149, value_type(941) ))   ;   // key = 149, val = 941
 485
 486             CPPUNIT_ASSERT( !m.empty() );
 487             CPPUNIT_ASSERT( check_size( m, 3 ));
 488
 489             chk.m_nExpected = 0;
 490             CPPUNIT_ASSERT( m.find( 126, cds::ref(chk) ));
 491             chk.m_nExpected = 731;
 492             CPPUNIT_ASSERT( m.find_with( 137, less(), cds::ref(chk) ));
 493             chk.m_nExpected = 941;
 494             CPPUNIT_ASSERT( m.find( 149, cds::ref(chk) ));
 495
 496             CPPUNIT_ASSERT( !m.emplace(126, 621)) ; // already in map
 497             chk.m_nExpected = 0;
 498             CPPUNIT_ASSERT( m.find( 126, cds::ref(chk) ));
 499             CPPUNIT_ASSERT( !m.empty() );
 500             CPPUNIT_ASSERT( check_size( m, 3 ));
 501
 502             m.clear();
 503             CPPUNIT_ASSERT( m.empty() );
 504             CPPUNIT_ASSERT( check_size( m, 0 ));
 505
 506 #       endif
 507         }
 508
 509         template <class Map>
 510         void test_striped_with2(Map& m)
 511         {
 512             cds::OS::Timer    timer;
 513
 514             test_int_with2( m );
 515
 516             // Iterators is not yet supported
 517             //m.clear();
 518             //CPPUNIT_ASSERT( m.empty() );
 519             //CPPUNIT_ASSERT( check_size( m, 0 ));
 520             //test_iter(m);
 521
 522             m.clear();
 523             CPPUNIT_ASSERT( m.empty() );
 524             CPPUNIT_ASSERT( check_size( m, 0 ));
 525
 526             // Resizing test
 527             for ( int i = 0; i < 40000; i++ ) {
 528                 m.insert( i );
 529             }
 530
 531             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 532         }
 533
 534         template <class Map>
 535         void test_striped2()
 536         {
 537             Map m( 30 );
 538             CPPUNIT_ASSERT( m.bucket_count() == 32 );
 539             CPPUNIT_ASSERT( m.lock_count() == 32 );
 540
 541             test_striped_with2(m);
 542         }
 543
 544         void Striped_hashmap();
 545         void Striped_list();
 546         void Striped_map();
 547         void Striped_slist();
 548         void Striped_boost_list();
 549         void Striped_boost_flat_map();
 550         void Striped_boost_map();
 551         void Striped_boost_unordered_map();
 552
 553         void Refinable_hashmap();
 554         void Refinable_list();
 555         void Refinable_map();
 556         void Refinable_slist();
 557         void Refinable_boost_list();
 558         void Refinable_boost_flat_map();
 559         void Refinable_boost_map();
 560         void Refinable_boost_unordered_map();
 561
 562         CPPUNIT_TEST_SUITE(StripedMapHdrTest)
 563             CPPUNIT_TEST(Striped_hashmap)
 564             CPPUNIT_TEST(Striped_list)
 565             CPPUNIT_TEST(Striped_map)
 566             CPPUNIT_TEST(Striped_slist)
 567             CPPUNIT_TEST(Striped_boost_list)
 568             CPPUNIT_TEST(Striped_boost_flat_map)
 569             CPPUNIT_TEST(Striped_boost_map)
 570             CPPUNIT_TEST(Striped_boost_unordered_map)
 571
 572             CPPUNIT_TEST(Refinable_hashmap)
 573             CPPUNIT_TEST(Refinable_list)
 574             CPPUNIT_TEST(Refinable_map)
 575             CPPUNIT_TEST(Refinable_slist)
 576             CPPUNIT_TEST(Refinable_boost_list)
 577             CPPUNIT_TEST(Refinable_boost_flat_map)
 578             CPPUNIT_TEST(Refinable_boost_map)
 579             CPPUNIT_TEST(Refinable_boost_unordered_map)
 580         CPPUNIT_TEST_SUITE_END()
 581
 582     };
 583 }   // namespace map
 584
 585 #endif // #ifndef __CDSTEST_HDR_STRIPED_MAP_H