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