test/stress/map/delodd/map_delodd.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #include "map_type.h"
  32
  33 namespace map {
  34
  35     namespace {
  36         struct key_thread
  37         {
  38             uint32_t  nKey;
  39             uint16_t  nThread;
  40
  41             key_thread( size_t key, size_t threadNo )
  42                 : nKey( static_cast<uint32_t>(key))
  43                 , nThread( static_cast<uint16_t>(threadNo))
  44             {}
  45
  46             key_thread()
  47                 : nKey()
  48                 , nThread()
  49             {}
  50         };
  51
  52         static_assert(sizeof( key_thread ) % 8 == 0, "Key size mismatch!!!");
  53     } // namespace
  54
  55     template <>
  56     struct cmp<key_thread> {
  57         int operator ()(key_thread const& k1, key_thread const& k2) const
  58         {
  59             if ( k1.nKey < k2.nKey )
  60                 return -1;
  61             if ( k1.nKey > k2.nKey )
  62                 return 1;
  63             if ( k1.nThread < k2.nThread )
  64                 return -1;
  65             if ( k1.nThread > k2.nThread )
  66                 return 1;
  67             return 0;
  68         }
  69         int operator ()(key_thread const& k1, size_t k2) const
  70         {
  71             if ( k1.nKey < k2 )
  72                 return -1;
  73             if ( k1.nKey > k2 )
  74                 return 1;
  75             return 0;
  76         }
  77         int operator ()(size_t k1, key_thread const& k2) const
  78         {
  79             if ( k1 < k2.nKey )
  80                 return -1;
  81             if ( k1 > k2.nKey )
  82                 return 1;
  83             return 0;
  84         }
  85     };
  86
  87     template <>
  88     struct less<key_thread>
  89     {
  90         bool operator()( key_thread const& k1, key_thread const& k2 ) const
  91         {
  92             if ( k1.nKey <= k2.nKey )
  93                 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
  94             return false;
  95         }
  96     };
  97
  98     template <>
  99     struct hash<key_thread>
 100     {
 101         typedef size_t             result_type;
 102         typedef key_thread    argument_type;
 103
 104         size_t operator()( key_thread const& k ) const
 105         {
 106             return std::hash<size_t>()(k.nKey);
 107         }
 108         size_t operator()( size_t k ) const
 109         {
 110             return std::hash<size_t>()(k);
 111         }
 112     };
 113
 114     class Map_DelOdd: public cds_test::stress_fixture
 115     {
 116     public:
 117         static size_t s_nInsThreadCount;      // insert thread count
 118         static size_t s_nDelThreadCount;      // delete thread count
 119         static size_t s_nExtractThreadCount;  // extract thread count
 120         static size_t s_nMapSize;             // max map size
 121         static size_t s_nMaxLoadFactor;       // maximum load factor
 122         static size_t s_nInsertPassCount;
 123         static size_t s_nFindThreadCount;     // find thread count
 124
 125         static size_t s_nCuckooInitialSize;       // initial size for CuckooMap
 126         static size_t s_nCuckooProbesetSize;      // CuckooMap probeset size (only for list-based probeset)
 127         static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (0 - use default)
 128
 129         static size_t s_nFeldmanMap_HeadBits;
 130         static size_t s_nFeldmanMap_ArrayBits;
 131
 132         static size_t  s_nLoadFactor;  // current load factor
 133
 134         static std::vector<size_t> m_arrElements;
 135
 136         static void SetUpTestCase();
 137         static void TearDownTestCase();
 138
 139         template <typename Pred>
 140         static void prepare_array( std::vector<size_t>& arr, Pred pred )
 141         {
 142             arr.reserve( m_arrElements.size() );
 143             for ( auto el : m_arrElements ) {
 144                 if ( pred( el ) )
 145                     arr.push_back( el );
 146             }
 147             arr.resize( arr.size() );
 148             shuffle( arr.begin(), arr.end() );
 149         }
 150
 151     protected:
 152         typedef key_thread  key_type;
 153         typedef size_t      value_type;
 154         typedef std::pair<key_type const, value_type> pair_type;
 155
 156         atomics::atomic<size_t> m_nInsThreadCount;
 157
 158         enum {
 159             inserter_thread,
 160             deleter_thread,
 161             extractor_thread,
 162             find_thread,
 163         };
 164
 165         // Inserts keys from [0..N)
 166         template <class Map>
 167         class Inserter: public cds_test::thread
 168         {
 169             typedef cds_test::thread base_class;
 170             Map&     m_Map;
 171
 172             struct update_func
 173             {
 174                 template <typename Q>
 175                 void operator()( bool /*bNew*/, Q const& ) const
 176                 {}
 177
 178                 template <typename Q, typename V>
 179                 void operator()( bool /*bNew*/, Q const&, V& ) const
 180                 {}
 181
 182                 // FeldmanHashMap
 183                 template <typename Q>
 184                 void operator()( Q&, Q*) const
 185                 {}
 186             };
 187
 188             void init_data()
 189             {
 190                 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
 191                 for ( size_t i = 0; i < m_arr.size(); ++i ) {
 192                     if ( m_Map.insert( key_type( m_arr[i], id() ) ) )
 193                         ++m_nInsertInitSuccess;
 194                     else
 195                         ++m_nInsertInitFailed;
 196                 }
 197             }
 198
 199         public:
 200             size_t m_nInsertSuccess = 0;
 201             size_t m_nInsertFailed = 0;
 202             size_t m_nInsertInitSuccess = 0;
 203             size_t m_nInsertInitFailed = 0;
 204
 205             std::vector<size_t> m_arr;
 206
 207         public:
 208             Inserter( cds_test::thread_pool& pool, Map& map )
 209                 : base_class( pool, inserter_thread )
 210                 , m_Map( map )
 211             {
 212                 init_data();
 213             }
 214
 215             Inserter( Inserter& src )
 216                 : base_class( src )
 217                 , m_Map( src.m_Map )
 218             {
 219                 init_data();
 220             }
 221
 222             virtual thread * clone()
 223             {
 224                 return new Inserter( *this );
 225             }
 226
 227             virtual void test()
 228             {
 229                 Map& rMap = m_Map;
 230                 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
 231
 232                 update_func f;
 233
 234                 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
 235                     if ( nPass & 1 ) {
 236                         // insert pass
 237                         for ( auto el : m_arr ) {
 238                             if ( el & 1 ) {
 239                                 if ( rMap.insert( key_type( el, id() )))
 240                                     ++m_nInsertSuccess;
 241                                 else
 242                                     ++m_nInsertFailed;
 243                             }
 244                         }
 245                     }
 246                     else {
 247                         // update pass
 248                         for ( auto el : m_arr ) {
 249                             if ( el & 1 ) {
 250                                 bool success;
 251                                 bool inserted;
 252                                 std::tie( success, inserted ) = rMap.update( key_type( el, id() ), f );
 253                                 if ( success && inserted )
 254                                     ++m_nInsertSuccess;
 255                                 else
 256                                     ++m_nInsertFailed;
 257                             }
 258                         }
 259                     }
 260                 }
 261
 262                 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
 263                 m_arr.resize( 0 );
 264             }
 265         };
 266
 267         struct key_equal {
 268             bool operator()( key_type const& k1, key_type const& k2 ) const
 269             {
 270                 return k1.nKey == k2.nKey;
 271             }
 272             bool operator()( size_t k1, key_type const& k2 ) const
 273             {
 274                 return k1 == k2.nKey;
 275             }
 276             bool operator()( key_type const& k1, size_t k2 ) const
 277             {
 278                 return k1.nKey == k2;
 279             }
 280         };
 281
 282         struct key_less {
 283             bool operator()( key_type const& k1, key_type const& k2 ) const
 284             {
 285                 return k1.nKey < k2.nKey;
 286             }
 287             bool operator()( size_t k1, key_type const& k2 ) const
 288             {
 289                 return k1 < k2.nKey;
 290             }
 291             bool operator()( key_type const& k1, size_t k2 ) const
 292             {
 293                 return k1.nKey < k2;
 294             }
 295
 296             typedef key_equal equal_to;
 297         };
 298
 299         // Deletes odd keys from [0..N)
 300         template <class Map>
 301         class Deleter: public cds_test::thread
 302         {
 303             typedef cds_test::thread base_class;
 304             Map&     m_Map;
 305
 306             void init_data()
 307             {
 308                 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
 309             }
 310
 311         public:
 312             size_t  m_nDeleteSuccess = 0;
 313             size_t  m_nDeleteFailed = 0;
 314
 315             std::vector<size_t> m_arr;
 316
 317         public:
 318             Deleter( cds_test::thread_pool& pool, Map& map )
 319                 : base_class( pool, deleter_thread )
 320                 , m_Map( map )
 321             {
 322                 init_data();
 323             }
 324
 325             Deleter( Deleter& src )
 326                 : base_class( src )
 327                 , m_Map( src.m_Map )
 328             {
 329                 init_data();
 330             }
 331
 332             virtual thread * clone()
 333             {
 334                 return new Deleter( *this );
 335             }
 336
 337             virtual void test()
 338             {
 339                 Map& rMap = m_Map;
 340
 341                 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
 342                 size_t const nInsThreadCount = s_nInsThreadCount;
 343
 344                 do {
 345                     if ( id() & 1 ) {
 346                         for ( auto el: m_arr ) {
 347                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 348                                 if ( rMap.erase( key_type( el, k )))
 349                                     ++m_nDeleteSuccess;
 350                                 else
 351                                     ++m_nDeleteFailed;
 352                             }
 353                         }
 354                     }
 355                     else {
 356                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 357                             for ( auto el: m_arr ) {
 358                                 if ( rMap.erase( key_type( el, k ) ) )
 359                                     ++m_nDeleteSuccess;
 360                                 else
 361                                     ++m_nDeleteFailed;
 362                             }
 363                         }
 364                     }
 365                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
 366
 367                 m_arr.resize( 0 );
 368             }
 369         };
 370
 371         // Deletes odd keys from [0..N)
 372         template <class GC, class Map >
 373         class Extractor: public cds_test::thread
 374         {
 375             typedef cds_test::thread base_class;
 376             Map&     m_Map;
 377
 378             void init_data()
 379             {
 380                 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
 381             }
 382
 383         public:
 384             size_t  m_nDeleteSuccess = 0;
 385             size_t  m_nDeleteFailed = 0;
 386
 387             std::vector<size_t> m_arr;
 388
 389         public:
 390             Extractor( cds_test::thread_pool& pool, Map& map )
 391                 : base_class( pool, extractor_thread )
 392                 , m_Map( map )
 393             {
 394                 init_data();
 395             }
 396
 397             Extractor( Extractor& src )
 398                 : base_class( src )
 399                 , m_Map( src.m_Map )
 400             {
 401                 init_data();
 402             }
 403
 404             virtual thread * clone()
 405             {
 406                 return new Extractor( *this );
 407             }
 408
 409             virtual void test()
 410             {
 411                 Map& rMap = m_Map;
 412
 413                 typename Map::guarded_ptr gp;
 414                 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
 415                 size_t const nInsThreadCount = s_nInsThreadCount;
 416
 417                 do {
 418                     if ( id() & 1 ) {
 419                         for ( auto el : m_arr ) {
 420                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 421                                 gp = rMap.extract( key_type( el, k ));
 422                                 if ( gp )
 423                                     ++m_nDeleteSuccess;
 424                                 else
 425                                     ++m_nDeleteFailed;
 426                                 gp.release();
 427                             }
 428                         }
 429                     }
 430                     else {
 431                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 432                             for ( auto el: m_arr ) {
 433                                 gp = rMap.extract( key_type( el, k ) );
 434                                 if ( gp )
 435                                     ++m_nDeleteSuccess;
 436                                 else
 437                                     ++m_nDeleteFailed;
 438                                 gp.release();
 439                             }
 440                         }
 441                     }
 442                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
 443
 444                 m_arr.resize( 0 );
 445             }
 446         };
 447
 448         template <class RCU, class Map >
 449         class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
 450         {
 451             typedef cds_test::thread base_class;
 452             Map&     m_Map;
 453
 454             void init_data()
 455             {
 456                 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 1 ) != 0; } );
 457             }
 458
 459         public:
 460             size_t  m_nDeleteSuccess = 0;
 461             size_t  m_nDeleteFailed = 0;
 462
 463             std::vector<size_t> m_arr;
 464
 465         public:
 466             Extractor( cds_test::thread_pool& pool, Map& map )
 467                 : base_class( pool, extractor_thread )
 468                 , m_Map( map )
 469             {
 470                 init_data();
 471             }
 472
 473             Extractor( Extractor& src )
 474                 : base_class( src )
 475                 , m_Map( src.m_Map )
 476             {
 477                 init_data();
 478             }
 479
 480             virtual thread * clone()
 481             {
 482                 return new Extractor( *this );
 483             }
 484
 485             virtual void test()
 486             {
 487                 Map& rMap = m_Map;
 488                 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
 489
 490                 typename Map::exempt_ptr xp;
 491                 size_t const nInsThreadCount = s_nInsThreadCount;
 492
 493                 do {
 494                     if ( id() & 1 ) {
 495                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 496                             for ( auto el: m_arr ) {
 497                                 if ( Map::c_bExtractLockExternal ) {
 498                                     typename Map::rcu_lock l;
 499                                     xp = rMap.extract( key_type( el, k ) );
 500                                     if ( xp )
 501                                         ++m_nDeleteSuccess;
 502                                     else
 503                                         ++m_nDeleteFailed;
 504                                 }
 505                                 else {
 506                                     xp = rMap.extract( key_type( el, k ) );
 507                                     if ( xp )
 508                                         ++m_nDeleteSuccess;
 509                                     else
 510                                         ++m_nDeleteFailed;
 511                                 }
 512                                 xp.release();
 513                             }
 514                         }
 515                     }
 516                     else {
 517                         for ( auto el : m_arr ) {
 518                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 519                                 if ( Map::c_bExtractLockExternal ) {
 520                                     typename Map::rcu_lock l;
 521                                     xp = rMap.extract( key_type( el, k ) );
 522                                     if ( xp )
 523                                         ++m_nDeleteSuccess;
 524                                     else
 525                                         ++m_nDeleteFailed;
 526                                 }
 527                                 else {
 528                                     xp = rMap.extract( key_type( el, k ) );
 529                                     if ( xp )
 530                                         ++m_nDeleteSuccess;
 531                                     else
 532                                         ++m_nDeleteFailed;
 533                                 }
 534                                 xp.release();
 535                             }
 536                         }
 537                     }
 538                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
 539
 540                 m_arr.resize( 0 );
 541             }
 542         };
 543
 544         // Finds keys
 545         template <class Map>
 546         class Observer: public cds_test::thread
 547         {
 548             typedef cds_test::thread base_class;
 549             Map&                m_Map;
 550
 551         public:
 552             size_t m_nFindEvenSuccess = 0;
 553             size_t m_nFindEvenFailed  = 0;
 554             size_t m_nFindOddSuccess  = 0;
 555             size_t m_nFindOddFailed   = 0;
 556
 557         public:
 558             Observer( cds_test::thread_pool& pool, Map& map )
 559                 : base_class( pool, find_thread )
 560                 , m_Map( map )
 561             {}
 562
 563             Observer( Observer& src )
 564                 : base_class( src )
 565                 , m_Map( src.m_Map )
 566             {}
 567
 568             virtual thread * clone()
 569             {
 570                 return new Observer( *this );
 571             }
 572
 573             virtual void test()
 574             {
 575                 Map& map = m_Map;
 576                 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
 577                 std::vector<size_t> const& arr = m_arrElements;
 578                 size_t const nInsThreadCount = s_nInsThreadCount;
 579
 580                 do {
 581                     for ( size_t key : arr ) {
 582                         if ( key & 1 ) {
 583                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 584                                 if ( map.contains( key_thread( key, k )))
 585                                     ++m_nFindOddSuccess;
 586                                 else
 587                                     ++m_nFindOddFailed;
 588                             }
 589                         }
 590                         else {
 591                             // even keys MUST be in the map
 592                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 593                                 if ( map.contains( key_thread( key, k )))
 594                                     ++m_nFindEvenSuccess;
 595                                 else
 596                                     ++m_nFindEvenFailed;
 597                             }
 598                         }
 599                     }
 600                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
 601             }
 602         };
 603
 604     protected:
 605         template <class Map>
 606         void do_test( Map& testMap )
 607         {
 608             typedef Inserter<Map> insert_thread;
 609             typedef Deleter<Map>  delete_thread;
 610             typedef Observer<Map> observer_thread;
 611
 612             m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
 613
 614             cds_test::thread_pool& pool = get_pool();
 615             pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
 616             pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
 617             if ( s_nFindThreadCount )
 618                 pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
 619
 620             propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
 621                 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
 622                 << std::make_pair( "find_thread_count", s_nFindThreadCount )
 623                 << std::make_pair( "map_size", s_nMapSize )
 624                 << std::make_pair( "pass_count", s_nInsertPassCount );
 625
 626             std::chrono::milliseconds duration = pool.run();
 627
 628             propout() << std::make_pair( "duration", duration );
 629
 630             size_t nInsertInitFailed = 0;
 631             size_t nInsertInitSuccess = 0;
 632             size_t nInsertSuccess = 0;
 633             size_t nInsertFailed = 0;
 634             size_t nDeleteSuccess = 0;
 635             size_t nDeleteFailed = 0;
 636
 637             size_t nFindEvenSuccess = 0;
 638             size_t nFindEvenFailed = 0;
 639             size_t nFindOddSuccess = 0;
 640             size_t nFindOddFailed = 0;
 641
 642             for ( size_t i = 0; i < pool.size(); ++i ) {
 643                 cds_test::thread& thr = pool.get( i );
 644                 switch ( thr.type() ) {
 645                 case inserter_thread:
 646                     {
 647                         insert_thread& inserter = static_cast<insert_thread&>( thr );
 648                         nInsertSuccess += inserter.m_nInsertSuccess;
 649                         nInsertFailed += inserter.m_nInsertFailed;
 650                         nInsertInitSuccess += inserter.m_nInsertInitSuccess;
 651                         nInsertInitFailed += inserter.m_nInsertInitFailed;
 652                     }
 653                     break;
 654                 case deleter_thread:
 655                     {
 656                         delete_thread& deleter = static_cast<delete_thread&>( thr );
 657                         nDeleteSuccess += deleter.m_nDeleteSuccess;
 658                         nDeleteFailed += deleter.m_nDeleteFailed;
 659                     }
 660                     break;
 661                 case find_thread:
 662                     {
 663                         observer_thread& observer = static_cast<observer_thread&>( thr );
 664                         nFindEvenSuccess = observer.m_nFindEvenSuccess;
 665                         nFindEvenFailed = observer.m_nFindEvenFailed;
 666                         nFindOddSuccess = observer.m_nFindOddSuccess;
 667                         nFindOddFailed = observer.m_nFindOddFailed;
 668                     }
 669                     break;
 670                 }
 671             }
 672
 673             size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) / 2;
 674
 675             EXPECT_EQ( nInsertInitFailed, 0u );
 676             EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
 677             EXPECT_EQ( nFindEvenFailed, 0u );
 678             EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
 679             EXPECT_LE( nInsertSuccess, nDeleteSuccess );
 680
 681             propout()
 682                 << std::make_pair( "insert_init_success", nInsertInitSuccess )
 683                 << std::make_pair( "insert_init_failed", nInsertInitFailed )
 684                 << std::make_pair( "insert_success", nInsertSuccess )
 685                 << std::make_pair( "insert_failed", nInsertFailed )
 686                 << std::make_pair( "delete_success", nDeleteSuccess )
 687                 << std::make_pair( "delete_failed", nDeleteFailed )
 688                 << std::make_pair( "find_even_success", nFindEvenSuccess )
 689                 << std::make_pair( "find_even_failed", nFindEvenFailed )
 690                 << std::make_pair( "find_odd_success", nFindOddSuccess )
 691                 << std::make_pair( "find_odd_failed", nFindOddFailed );
 692
 693             analyze( testMap );
 694         }
 695
 696         template <class Map>
 697         void do_test_extract( Map& testMap )
 698         {
 699             typedef Inserter<Map> insert_thread;
 700             typedef Deleter<Map> delete_thread;
 701             typedef Extractor< typename Map::gc, Map > extract_thread;
 702             typedef Observer<Map> observer_thread;
 703
 704             m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
 705
 706             cds_test::thread_pool& pool = get_pool();
 707             pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
 708             if ( s_nDelThreadCount )
 709                 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount );
 710             if ( s_nExtractThreadCount )
 711                 pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
 712             if ( s_nFindThreadCount )
 713                 pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
 714
 715             propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
 716                 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
 717                 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
 718                 << std::make_pair( "find_thread_count", s_nFindThreadCount )
 719                 << std::make_pair( "map_size", s_nMapSize )
 720                 << std::make_pair( "pass_count", s_nInsertPassCount );
 721
 722             std::chrono::milliseconds duration = pool.run();
 723
 724             propout() << std::make_pair( "duration", duration );
 725
 726             size_t nInsertInitFailed = 0;
 727             size_t nInsertInitSuccess = 0;
 728             size_t nInsertSuccess = 0;
 729             size_t nInsertFailed = 0;
 730             size_t nDeleteSuccess = 0;
 731             size_t nDeleteFailed = 0;
 732             size_t nExtractSuccess = 0;
 733             size_t nExtractFailed = 0;
 734
 735             size_t nFindEvenSuccess = 0;
 736             size_t nFindEvenFailed = 0;
 737             size_t nFindOddSuccess = 0;
 738             size_t nFindOddFailed = 0;
 739
 740             for ( size_t i = 0; i < pool.size(); ++i ) {
 741                 cds_test::thread& thr = pool.get( i );
 742                 switch ( thr.type()) {
 743                 case inserter_thread:
 744                 {
 745                     insert_thread& inserter = static_cast<insert_thread&>(thr);
 746                     nInsertSuccess += inserter.m_nInsertSuccess;
 747                     nInsertFailed += inserter.m_nInsertFailed;
 748                     nInsertInitSuccess += inserter.m_nInsertInitSuccess;
 749                     nInsertInitFailed += inserter.m_nInsertInitFailed;
 750                 }
 751                 break;
 752                 case deleter_thread:
 753                 {
 754                     delete_thread& deleter = static_cast<delete_thread&>(thr);
 755                     nDeleteSuccess += deleter.m_nDeleteSuccess;
 756                     nDeleteFailed += deleter.m_nDeleteFailed;
 757                 }
 758                 break;
 759                 case extractor_thread:
 760                 {
 761                     extract_thread& extractor = static_cast<extract_thread&>(thr);
 762                     nExtractSuccess += extractor.m_nDeleteSuccess;
 763                     nExtractFailed += extractor.m_nDeleteFailed;
 764                 }
 765                 break;
 766                 case find_thread:
 767                 {
 768                     observer_thread& observer = static_cast<observer_thread&>( thr );
 769                     nFindEvenSuccess = observer.m_nFindEvenSuccess;
 770                     nFindEvenFailed = observer.m_nFindEvenFailed;
 771                     nFindOddSuccess = observer.m_nFindOddSuccess;
 772                     nFindOddFailed = observer.m_nFindOddFailed;
 773                 }
 774                 break;
 775                 default:
 776                     assert( false );
 777                 }
 778             }
 779
 780             size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) / 2;
 781
 782             EXPECT_EQ( nInsertInitFailed, 0u );
 783             EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
 784             EXPECT_EQ( nFindEvenFailed, 0u );
 785             EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
 786             EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
 787
 788             propout()
 789                 << std::make_pair( "insert_init_success", nInsertInitSuccess )
 790                 << std::make_pair( "insert_init_failed", nInsertInitFailed )
 791                 << std::make_pair( "insert_success", nInsertSuccess )
 792                 << std::make_pair( "insert_failed", nInsertFailed )
 793                 << std::make_pair( "delete_success", nDeleteSuccess )
 794                 << std::make_pair( "delete_failed", nDeleteFailed )
 795                 << std::make_pair( "extract_success", nExtractSuccess )
 796                 << std::make_pair( "extract_failed", nExtractFailed )
 797                 << std::make_pair( "find_even_success", nFindEvenSuccess )
 798                 << std::make_pair( "find_even_failed", nFindEvenFailed )
 799                 << std::make_pair( "find_odd_success", nFindOddSuccess )
 800                 << std::make_pair( "find_odd_failed", nFindOddFailed );
 801
 802             analyze( testMap );
 803         }
 804
 805         template <class Map>
 806         void analyze( Map& testMap )
 807         {
 808             // All even keys must be in the map
 809             {
 810                 for ( size_t n = 0; n < s_nMapSize; n +=2 ) {
 811                     for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
 812                         EXPECT_TRUE( testMap.contains( key_type( n, i ))) << "key=" << n << "/" << i;
 813                     }
 814                 }
 815             }
 816
 817             print_stat( propout(), testMap );
 818
 819             check_before_cleanup( testMap );
 820             testMap.clear();
 821             EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
 822
 823             additional_check( testMap );
 824             additional_cleanup( testMap );
 825         }
 826
 827         template <class Map>
 828         void run_test_extract()
 829         {
 830             static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
 831
 832             size_t nMapSize = s_nMapSize;
 833             s_nMapSize *= s_nInsThreadCount;
 834
 835             Map testMap( *this );
 836
 837             s_nMapSize = nMapSize;
 838             do_test_extract( testMap );
 839         }
 840
 841         template <class Map>
 842         void run_test()
 843         {
 844             size_t nMapSize = s_nMapSize;
 845             s_nMapSize *= s_nInsThreadCount;
 846
 847             Map testMap( *this );
 848
 849             s_nMapSize = nMapSize;
 850             do_test( testMap );
 851         }
 852
 853         template <class Map>
 854         void run_feldman();
 855     };
 856
 857     class Map_DelOdd_LF: public Map_DelOdd
 858         , public ::testing::WithParamInterface<size_t>
 859     {
 860     public:
 861         template <class Map>
 862         void run_test()
 863         {
 864             s_nLoadFactor = GetParam();
 865             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 866             Map_DelOdd::run_test<Map>();
 867         }
 868
 869         template <class Map>
 870         void run_test_extract()
 871         {
 872             s_nLoadFactor = GetParam();
 873             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 874             Map_DelOdd::run_test_extract<Map>();
 875         }
 876
 877         static std::vector<size_t> get_load_factors();
 878     };
 879
 880 } // namespace map