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