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