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 <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     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_with( 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_with( 10, insert_functor<Map>() ) );
 198             CPPUNIT_ASSERT( !m.insert_with( 25, insert_functor<Map>() ) );
 199             CPPUNIT_ASSERT( !m.insert_with( 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, std::ref(chk) ));
 212             chk.m_nExpected = 0;
 213             CPPUNIT_ASSERT( m.find( 25, std::ref( chk ) ) );
 214             chk.m_nExpected = 90;
 215             CPPUNIT_ASSERT( m.find( 30, std::ref( chk ) ) );
 216             chk.m_nExpected = 54;
 217             CPPUNIT_ASSERT( m.find( 27, std::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, std::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, std::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, std::ref( ext ) ) );
 260             CPPUNIT_ASSERT( nVal == -1 );
 261
 262             CPPUNIT_ASSERT( m.erase( 30, std::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, std::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             // emplace test
 275             CPPUNIT_ASSERT( m.emplace(126) ) ; // key = 126, val = 0
 276             CPPUNIT_ASSERT( m.emplace(137, 731))    ;   // key = 137, val = 731
 277             CPPUNIT_ASSERT( m.emplace( 149, value_type(941) ))   ;   // key = 149, val = 941
 278
 279             CPPUNIT_ASSERT( !m.empty() );
 280             CPPUNIT_ASSERT( check_size( m, 3 ));
 281
 282             chk.m_nExpected = 0;
 283             CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
 284             chk.m_nExpected = 731;
 285             CPPUNIT_ASSERT( m.find( 137, std::ref(chk) ));
 286             chk.m_nExpected = 941;
 287             CPPUNIT_ASSERT( m.find( 149, std::ref(chk) ));
 288
 289             CPPUNIT_ASSERT( !m.emplace(126, 621)) ; // already in map
 290             chk.m_nExpected = 0;
 291             CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
 292             CPPUNIT_ASSERT( !m.empty() );
 293             CPPUNIT_ASSERT( check_size( m, 3 ));
 294
 295             m.clear();
 296             CPPUNIT_ASSERT( m.empty() );
 297             CPPUNIT_ASSERT( check_size( m, 0 ));
 298         }
 299
 300         template <class Map>
 301         void test_iter( Map& s)
 302         {
 303             typedef typename Map::iterator          iterator;
 304             typedef typename Map::const_iterator    const_iterator;
 305
 306             const int nMaxCount = 500;
 307             for ( int i = 0; i < nMaxCount; ++i ) {
 308                 CPPUNIT_ASSERT( s.insert( i, i * 2 ));
 309             }
 310
 311             int nCount = 0;
 312             for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 313                 CPPUNIT_ASSERT( it->first * 2 == it->second.m_val );
 314                 CPPUNIT_ASSERT( (*it).first * 2 == (*it).second.m_val );
 315                 it->second.m_val = it->first;
 316                 ++nCount;
 317             }
 318             CPPUNIT_ASSERT( nCount == nMaxCount );
 319
 320             Map const& refSet = s;
 321             nCount = 0;
 322             for ( const_iterator it = refSet.begin(), itEnd = refSet.end(); it != itEnd; ++it ) {
 323                 CPPUNIT_ASSERT( it->first == it->second.m_val );
 324                 CPPUNIT_ASSERT( (*it).first == (*it).second.m_val );
 325                 ++nCount;
 326             }
 327             CPPUNIT_ASSERT( nCount == nMaxCount );
 328         }
 329
 330         template <class Map>
 331         void test_striped()
 332         {
 333             Map m( 30 );
 334             CPPUNIT_ASSERT( m.bucket_count() == 32 );
 335             CPPUNIT_ASSERT( m.lock_count() == 32 );
 336
 337             test_striped_with(m);
 338         }
 339
 340         template <class Map>
 341         void test_striped_with(Map& m)
 342         {
 343             cds::OS::Timer    timer;
 344
 345             test_int_with( m );
 346
 347             // Iterators is not yet supported
 348             //m.clear();
 349             //CPPUNIT_ASSERT( m.empty() );
 350             //CPPUNIT_ASSERT( check_size( m, 0 ));
 351             //test_iter(m);
 352
 353             m.clear();
 354             CPPUNIT_ASSERT( m.empty() );
 355             CPPUNIT_ASSERT( check_size( m, 0 ));
 356
 357             // Resizing test
 358             for ( int i = 0; i < 40000; i++ ) {
 359                 m.insert( i );
 360             }
 361
 362             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 363         }
 364
 365         //*******************************************
 366         // If erase_with && find_with are supported
 367         template <class Map>
 368         void test_int_with2( Map& m )
 369         {
 370             std::pair<bool, bool> ensureResult;
 371
 372             // insert
 373             CPPUNIT_ASSERT( m.empty() );
 374             CPPUNIT_ASSERT( check_size( m, 0 ));
 375             CPPUNIT_ASSERT( !m.find(25) );
 376             CPPUNIT_ASSERT( m.insert( 25 ) )    ;   // value = 0
 377             CPPUNIT_ASSERT( m.find(25) );
 378             CPPUNIT_ASSERT( !m.empty() );
 379             CPPUNIT_ASSERT( check_size( m, 1 ));
 380             CPPUNIT_ASSERT( m.find(25) );
 381
 382             CPPUNIT_ASSERT( !m.insert( 25 ) );
 383             CPPUNIT_ASSERT( !m.empty() );
 384             CPPUNIT_ASSERT( check_size( m, 1 ));
 385
 386             CPPUNIT_ASSERT( !m.find_with(10, less()) );
 387             CPPUNIT_ASSERT( m.insert( 10, 10 ) );
 388             CPPUNIT_ASSERT( !m.empty() );
 389             CPPUNIT_ASSERT( check_size( m, 2 ));
 390             CPPUNIT_ASSERT( m.find_with(10, less()) );
 391
 392             CPPUNIT_ASSERT( !m.insert( 10, 20 ) );
 393             CPPUNIT_ASSERT( !m.empty() );
 394             CPPUNIT_ASSERT( check_size( m, 2 ));
 395
 396             CPPUNIT_ASSERT( !m.find(30) );
 397             CPPUNIT_ASSERT( m.insert_with( 30, insert_functor<Map>() ) )    ; // value = 90
 398             CPPUNIT_ASSERT( !m.empty() );
 399             CPPUNIT_ASSERT( check_size( m, 3 ));
 400             CPPUNIT_ASSERT( m.find(30) );
 401
 402             CPPUNIT_ASSERT( !m.insert_with( 10, insert_functor<Map>() ) );
 403             CPPUNIT_ASSERT( !m.insert_with( 25, insert_functor<Map>() ) );
 404             CPPUNIT_ASSERT( !m.insert_with( 30, insert_functor<Map>() ) );
 405
 406             // ensure (new key)
 407             CPPUNIT_ASSERT( !m.find(27) );
 408             ensureResult = m.ensure( 27, insert_functor<Map>() ) ;   // value = 54
 409             CPPUNIT_ASSERT( ensureResult.first );
 410             CPPUNIT_ASSERT( ensureResult.second );
 411             CPPUNIT_ASSERT( m.find(27) );
 412
 413             // find test
 414             check_value chk(10);
 415             CPPUNIT_ASSERT( m.find( 10, std::ref(chk) ));
 416             chk.m_nExpected = 0;
 417             CPPUNIT_ASSERT( m.find_with( 25, less(), std::ref( chk ) ) );
 418             chk.m_nExpected = 90;
 419             CPPUNIT_ASSERT( m.find( 30, std::ref( chk ) ) );
 420             chk.m_nExpected = 54;
 421             CPPUNIT_ASSERT( m.find( 27, std::ref( chk ) ) );
 422
 423             ensureResult = m.ensure( 10, insert_functor<Map>() ) ;   // value = 50
 424             CPPUNIT_ASSERT( ensureResult.first );
 425             CPPUNIT_ASSERT( !ensureResult.second );
 426             chk.m_nExpected = 50;
 427             CPPUNIT_ASSERT( m.find( 10, std::ref( chk ) ) );
 428
 429             // erase test
 430             CPPUNIT_ASSERT( !m.find(100) );
 431             CPPUNIT_ASSERT( !m.erase( 100 )) ;  // not found
 432
 433             CPPUNIT_ASSERT( m.find(25) );
 434             CPPUNIT_ASSERT( check_size( m, 4 ));
 435             CPPUNIT_ASSERT( m.erase( 25 ));
 436             CPPUNIT_ASSERT( !m.empty() );
 437             CPPUNIT_ASSERT( check_size( m, 3 ));
 438             CPPUNIT_ASSERT( !m.find(25) );
 439             CPPUNIT_ASSERT( !m.erase( 25 ));
 440
 441             CPPUNIT_ASSERT( !m.find(258) );
 442             CPPUNIT_ASSERT( m.insert(258))
 443             CPPUNIT_ASSERT( check_size( m, 4 ));
 444             CPPUNIT_ASSERT( m.find_with(258, less()) );
 445             CPPUNIT_ASSERT( m.erase_with( 258, less() ));
 446             CPPUNIT_ASSERT( !m.empty() );
 447             CPPUNIT_ASSERT( check_size( m, 3 ));
 448             CPPUNIT_ASSERT( !m.find(258) );
 449             CPPUNIT_ASSERT( !m.erase_with( 258, less() ));
 450
 451             int nVal;
 452             extract_functor ext;
 453             ext.m_pVal = &nVal;
 454
 455             CPPUNIT_ASSERT( !m.find(29) );
 456             CPPUNIT_ASSERT( m.insert(29, 290))
 457                 CPPUNIT_ASSERT( m.erase_with( 29, less(), std::ref( ext ) ) );
 458             CPPUNIT_ASSERT( !m.empty() );
 459             CPPUNIT_ASSERT( check_size( m, 3 ));
 460             CPPUNIT_ASSERT( nVal == 290 );
 461             nVal = -1;
 462             CPPUNIT_ASSERT( !m.erase_with( 29, less(), std::ref( ext ) ) );
 463             CPPUNIT_ASSERT( nVal == -1 );
 464
 465             CPPUNIT_ASSERT( m.erase( 30, std::ref( ext ) ) );
 466             CPPUNIT_ASSERT( !m.empty() );
 467             CPPUNIT_ASSERT( check_size( m, 2 ));
 468             CPPUNIT_ASSERT( nVal == 90 );
 469             nVal = -1;
 470             CPPUNIT_ASSERT( !m.erase( 30, std::ref( ext ) ) );
 471             CPPUNIT_ASSERT( nVal == -1 );
 472
 473             m.clear();
 474             CPPUNIT_ASSERT( m.empty() );
 475             CPPUNIT_ASSERT( check_size( m, 0 ));
 476
 477             // emplace test
 478             CPPUNIT_ASSERT( m.emplace(126) ) ; // key = 126, val = 0
 479             CPPUNIT_ASSERT( m.emplace(137, 731))    ;   // key = 137, val = 731
 480             CPPUNIT_ASSERT( m.emplace( 149, value_type(941) ))   ;   // key = 149, val = 941
 481
 482             CPPUNIT_ASSERT( !m.empty() );
 483             CPPUNIT_ASSERT( check_size( m, 3 ));
 484
 485             chk.m_nExpected = 0;
 486             CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
 487             chk.m_nExpected = 731;
 488             CPPUNIT_ASSERT( m.find_with( 137, less(), std::ref(chk) ));
 489             chk.m_nExpected = 941;
 490             CPPUNIT_ASSERT( m.find( 149, std::ref(chk) ));
 491
 492             CPPUNIT_ASSERT( !m.emplace(126, 621)) ; // already in map
 493             chk.m_nExpected = 0;
 494             CPPUNIT_ASSERT( m.find( 126, std::ref(chk) ));
 495             CPPUNIT_ASSERT( !m.empty() );
 496             CPPUNIT_ASSERT( check_size( m, 3 ));
 497
 498             m.clear();
 499             CPPUNIT_ASSERT( m.empty() );
 500             CPPUNIT_ASSERT( check_size( m, 0 ));
 501         }
 502
 503         template <class Map>
 504         void test_striped_with2(Map& m)
 505         {
 506             cds::OS::Timer    timer;
 507
 508             test_int_with2( m );
 509
 510             // Iterators is not yet supported
 511             //m.clear();
 512             //CPPUNIT_ASSERT( m.empty() );
 513             //CPPUNIT_ASSERT( check_size( m, 0 ));
 514             //test_iter(m);
 515
 516             m.clear();
 517             CPPUNIT_ASSERT( m.empty() );
 518             CPPUNIT_ASSERT( check_size( m, 0 ));
 519
 520             // Resizing test
 521             for ( int i = 0; i < 40000; i++ ) {
 522                 m.insert( i );
 523             }
 524
 525             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 526         }
 527
 528         template <class Map>
 529         void test_striped2()
 530         {
 531             Map m( 30 );
 532             CPPUNIT_ASSERT( m.bucket_count() == 32 );
 533             CPPUNIT_ASSERT( m.lock_count() == 32 );
 534
 535             test_striped_with2(m);
 536         }
 537
 538         void Striped_hashmap();
 539         void Striped_list();
 540         void Striped_map();
 541         void Striped_slist();
 542         void Striped_boost_list();
 543         void Striped_boost_flat_map();
 544         void Striped_boost_map();
 545         void Striped_boost_unordered_map();
 546
 547         void Refinable_hashmap();
 548         void Refinable_list();
 549         void Refinable_map();
 550         void Refinable_slist();
 551         void Refinable_boost_list();
 552         void Refinable_boost_flat_map();
 553         void Refinable_boost_map();
 554         void Refinable_boost_unordered_map();
 555
 556         CPPUNIT_TEST_SUITE(StripedMapHdrTest)
 557             CPPUNIT_TEST(Striped_hashmap)
 558             CPPUNIT_TEST(Striped_list)
 559             CPPUNIT_TEST(Striped_map)
 560             CPPUNIT_TEST(Striped_slist)
 561             CPPUNIT_TEST(Striped_boost_list)
 562             CPPUNIT_TEST(Striped_boost_flat_map)
 563             CPPUNIT_TEST(Striped_boost_map)
 564             CPPUNIT_TEST(Striped_boost_unordered_map)
 565
 566             CPPUNIT_TEST(Refinable_hashmap)
 567             CPPUNIT_TEST(Refinable_list)
 568             CPPUNIT_TEST(Refinable_map)
 569             CPPUNIT_TEST(Refinable_slist)
 570             CPPUNIT_TEST(Refinable_boost_list)
 571             CPPUNIT_TEST(Refinable_boost_flat_map)
 572             CPPUNIT_TEST(Refinable_boost_map)
 573             CPPUNIT_TEST(Refinable_boost_unordered_map)
 574         CPPUNIT_TEST_SUITE_END()
 575
 576     };
 577 }   // namespace map
 578
 579 #endif // #ifndef __CDSTEST_HDR_STRIPED_MAP_H