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