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