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