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