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                 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
 366
 367                 do {
 368                     auto itEnd = rSet.template get_end<Iterator>();
 369                     for ( auto it = rSet.template get_begin<Iterator>(); it != itEnd; ++it ) {
 370                         if ( it->key.nKey & 3 ) {
 371                             if ( rSet.erase_at( it ))
 372                                 ++m_nDeleteSuccess;
 373                             else
 374                                 ++m_nDeleteFailed;
 375                         }
 376                     }
 377                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
 378             }
 379         };
 380
 381         // Extracts keys from [0..N)
 382         template <typename GC, class Set>
 383         class Extractor: public cds_test::thread
 384         {
 385             typedef cds_test::thread base_class;
 386             Set&     m_Set;
 387
 388             std::vector<size_t> m_arr;
 389
 390             void init_data()
 391             {
 392                 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
 393             }
 394
 395         public:
 396             size_t  m_nExtractSuccess = 0;
 397             size_t  m_nExtractFailed = 0;
 398
 399         public:
 400             Extractor( cds_test::thread_pool& pool, Set& set )
 401                 : base_class( pool, extractor_thread )
 402                 , m_Set( set )
 403             {
 404                 init_data();
 405             }
 406
 407             Extractor( Extractor& src )
 408                 : base_class( src )
 409                 , m_Set( src.m_Set )
 410             {
 411                 init_data();
 412             }
 413
 414             virtual thread * clone()
 415             {
 416                 return new Extractor( *this );
 417             }
 418
 419             virtual void test()
 420             {
 421                 Set& rSet = m_Set;
 422                 typename Set::guarded_ptr gp;
 423
 424                 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
 425                 size_t const nInsThreadCount = s_nInsThreadCount;
 426
 427                 do {
 428                     if ( id() & 1 ) {
 429                         for ( auto el : m_arr ) {
 430                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 431                                 gp = rSet.extract( key_type( el, k ));
 432                                 if ( gp )
 433                                     ++m_nExtractSuccess;
 434                                 else
 435                                     ++m_nExtractFailed;
 436                                 gp.release();
 437                             }
 438                         }
 439                     }
 440                     else {
 441                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 442                             for ( auto el : m_arr ) {
 443                                 gp = rSet.extract( key_type( el, k ));
 444                                 if ( gp )
 445                                     ++m_nExtractSuccess;
 446                                 else
 447                                     ++m_nExtractFailed;
 448                                 gp.release();
 449                             }
 450                         }
 451                     }
 452                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
 453
 454                 m_arr.resize( 0 );
 455             }
 456         };
 457
 458         template <typename RCU, class Set>
 459         class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
 460         {
 461             typedef cds_test::thread base_class;
 462             Set&     m_Set;
 463             std::vector<size_t> m_arr;
 464
 465             void init_data()
 466             {
 467                 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
 468             }
 469
 470         public:
 471             size_t  m_nExtractSuccess = 0;
 472             size_t  m_nExtractFailed = 0;
 473
 474         public:
 475             Extractor( cds_test::thread_pool& pool, Set& set )
 476                 : base_class( pool, extractor_thread )
 477                 , m_Set( set )
 478             {
 479                 init_data();
 480             }
 481
 482             Extractor( Extractor& src )
 483                 : base_class( src )
 484                 , m_Set( src.m_Set )
 485             {
 486                 init_data();
 487             }
 488
 489             virtual thread * clone()
 490             {
 491                 return new Extractor( *this );
 492             }
 493
 494             virtual void test()
 495             {
 496                 Set& rSet = m_Set;
 497                 typename Set::exempt_ptr xp;
 498
 499                 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
 500                 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
 501
 502                 do {
 503                     if ( id() & 1 ) {
 504                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 505                             for ( auto el : m_arr ) {
 506                                 if ( Set::c_bExtractLockExternal ) {
 507                                     typename Set::rcu_lock l;
 508                                     xp = rSet.extract( key_type( el, k ));
 509                                     if ( xp )
 510                                         ++m_nExtractSuccess;
 511                                     else
 512                                         ++m_nExtractFailed;
 513                                 }
 514                                 else {
 515                                     xp = rSet.extract( key_type( el, k ));
 516                                     if ( xp )
 517                                         ++m_nExtractSuccess;
 518                                     else
 519                                         ++m_nExtractFailed;
 520                                 }
 521                                 xp.release();
 522                             }
 523                         }
 524                     }
 525                     else {
 526                         for ( auto el : m_arr ) {
 527                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 528                                 if ( Set::c_bExtractLockExternal ) {
 529                                     typename Set::rcu_lock l;
 530                                     xp = rSet.extract( key_type( el, k ));
 531                                     if ( xp )
 532                                         ++m_nExtractSuccess;
 533                                     else
 534                                         ++m_nExtractFailed;
 535                                 }
 536                                 else {
 537                                     xp = rSet.extract( key_type( el, k ));
 538                                     if ( xp )
 539                                         ++m_nExtractSuccess;
 540                                     else
 541                                         ++m_nExtractFailed;
 542                                 }
 543                                 xp.release();
 544                             }
 545                         }
 546                     }
 547                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
 548
 549                 m_arr.resize( 0 );
 550             }
 551         };
 552
 553         // Finds keys
 554         template <class Set>
 555         class Observer: public cds_test::thread
 556         {
 557             typedef cds_test::thread base_class;
 558             Set&                m_Set;
 559
 560         public:
 561             size_t m_nFindEvenSuccess = 0;
 562             size_t m_nFindEvenFailed = 0;
 563             size_t m_nFindOddSuccess = 0;
 564             size_t m_nFindOddFailed = 0;
 565
 566         public:
 567             Observer( cds_test::thread_pool& pool, Set& set )
 568                 : base_class( pool, find_thread )
 569                 , m_Set( set )
 570             {}
 571
 572             Observer( Observer& src )
 573                 : base_class( src )
 574                 , m_Set( src.m_Set )
 575             {}
 576
 577             virtual thread * clone()
 578             {
 579                 return new Observer( *this );
 580             }
 581
 582             virtual void test()
 583             {
 584                 Set& set = m_Set;
 585                 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
 586                 std::vector<size_t> const& arr = m_arrData;
 587                 size_t const nInsThreadCount = s_nInsThreadCount;
 588
 589                 do {
 590                     for ( size_t key : arr ) {
 591                         if ( key & 3 ) {
 592                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 593                                 if ( set.contains( key_thread( key, k )))
 594                                     ++m_nFindOddSuccess;
 595                                 else
 596                                     ++m_nFindOddFailed;
 597                             }
 598                         }
 599                         else {
 600                             // that keys MUST be in the map
 601                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 602                                 if ( set.contains( key_thread( key, k )))
 603                                     ++m_nFindEvenSuccess;
 604                                 else
 605                                     ++m_nFindEvenFailed;
 606                             }
 607                         }
 608                     }
 609                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
 610             }
 611         };
 612
 613     protected:
 614         template <typename Iterator, class Set>
 615         void do_test_with( Set& testSet )
 616         {
 617             typedef Inserter<Set> insert_thread;
 618             typedef Deleter<Set, Iterator> delete_thread;
 619             typedef Observer<Set> observer_thread;
 620
 621             m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
 622
 623             cds_test::thread_pool& pool = get_pool();
 624             pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
 625             pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
 626             if ( s_nFindThreadCount )
 627                 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
 628
 629             propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
 630                 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
 631                 << std::make_pair( "find_thread_count", s_nFindThreadCount )
 632                 << std::make_pair( "set_size", s_nSetSize )
 633                 << std::make_pair( "pass_count", s_nInsertPassCount );
 634
 635             std::chrono::milliseconds duration = pool.run();
 636
 637             propout() << std::make_pair( "duration", duration );
 638
 639             size_t nInsertInitFailed = 0;
 640             size_t nInsertInitSuccess = 0;
 641             size_t nInsertSuccess = 0;
 642             size_t nInsertFailed = 0;
 643             size_t nDeleteSuccess = 0;
 644             size_t nDeleteFailed = 0;
 645
 646             size_t nFindEvenSuccess = 0;
 647             size_t nFindEvenFailed = 0;
 648             size_t nFindOddSuccess = 0;
 649             size_t nFindOddFailed = 0;
 650
 651             for ( size_t i = 0; i < pool.size(); ++i ) {
 652                 cds_test::thread& thr = pool.get( i );
 653                 switch ( thr.type()) {
 654                 case inserter_thread:
 655                     {
 656                         insert_thread& inserter = static_cast<insert_thread&>(thr);
 657                         nInsertSuccess += inserter.m_nInsertSuccess;
 658                         nInsertFailed += inserter.m_nInsertFailed;
 659                         nInsertInitSuccess += inserter.m_nInsertInitSuccess;
 660                         nInsertInitFailed += inserter.m_nInsertInitFailed;
 661                     }
 662                     break;
 663                 case deleter_thread:
 664                     {
 665                         delete_thread& deleter = static_cast<delete_thread&>(thr);
 666                         nDeleteSuccess += deleter.m_nDeleteSuccess;
 667                         nDeleteFailed += deleter.m_nDeleteFailed;
 668                     }
 669                     break;
 670                 case find_thread:
 671                     {
 672                         observer_thread& observer = static_cast<observer_thread&>( thr );
 673                         nFindEvenSuccess = observer.m_nFindEvenSuccess;
 674                         nFindEvenFailed = observer.m_nFindEvenFailed;
 675                         nFindOddSuccess = observer.m_nFindOddSuccess;
 676                         nFindOddFailed = observer.m_nFindOddFailed;
 677                     }
 678                     break;
 679                 default:
 680                     assert( false );
 681                 }
 682             }
 683
 684             size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
 685
 686             EXPECT_EQ( nInsertInitFailed, 0u );
 687             EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
 688             EXPECT_EQ( nFindEvenFailed, 0u );
 689             EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
 690             EXPECT_LE( nInsertSuccess, nDeleteSuccess );
 691
 692             propout()
 693                 << std::make_pair( "insert_init_success", nInsertInitSuccess )
 694                 << std::make_pair( "insert_init_failed", nInsertInitFailed )
 695                 << std::make_pair( "insert_success", nInsertSuccess )
 696                 << std::make_pair( "insert_failed", nInsertFailed )
 697                 << std::make_pair( "delete_success", nDeleteSuccess )
 698                 << std::make_pair( "delete_failed", nDeleteFailed )
 699                 << std::make_pair( "find_even_success", nFindEvenSuccess )
 700                 << std::make_pair( "find_even_failed", nFindEvenFailed )
 701                 << std::make_pair( "find_odd_success", nFindOddSuccess )
 702                 << std::make_pair( "find_odd_failed", nFindOddFailed );
 703         }
 704
 705         template <typename Iterator, class Set>
 706         void do_test_extract_with( Set& testSet )
 707         {
 708             typedef Inserter<Set> insert_thread;
 709             typedef Deleter<Set, Iterator> delete_thread;
 710             typedef Extractor< typename Set::gc, Set > extract_thread;
 711             typedef Observer<Set> observer_thread;
 712
 713             m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
 714
 715             cds_test::thread_pool& pool = get_pool();
 716             pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
 717             if ( s_nDelThreadCount )
 718                 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
 719             if ( s_nExtractThreadCount )
 720                 pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
 721             if ( s_nFindThreadCount )
 722                 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
 723
 724             propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
 725                 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
 726                 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
 727                 << std::make_pair( "find_thread_count", s_nFindThreadCount )
 728                 << std::make_pair( "set_size", s_nSetSize )
 729                 << std::make_pair( "pass_count", s_nInsertPassCount );
 730
 731             std::chrono::milliseconds duration = pool.run();
 732
 733             propout() << std::make_pair( "duration", duration );
 734
 735             size_t nInsertInitFailed = 0;
 736             size_t nInsertInitSuccess = 0;
 737             size_t nInsertSuccess = 0;
 738             size_t nInsertFailed = 0;
 739             size_t nDeleteSuccess = 0;
 740             size_t nDeleteFailed = 0;
 741             size_t nExtractSuccess = 0;
 742             size_t nExtractFailed = 0;
 743
 744             size_t nFindEvenSuccess = 0;
 745             size_t nFindEvenFailed = 0;
 746             size_t nFindOddSuccess = 0;
 747             size_t nFindOddFailed = 0;
 748
 749             for ( size_t i = 0; i < pool.size(); ++i ) {
 750                 cds_test::thread& thr = pool.get( i );
 751                 switch ( thr.type()) {
 752                 case inserter_thread:
 753                     {
 754                         insert_thread& inserter = static_cast<insert_thread&>( thr );
 755                         nInsertSuccess += inserter.m_nInsertSuccess;
 756                         nInsertFailed += inserter.m_nInsertFailed;
 757                         nInsertInitSuccess += inserter.m_nInsertInitSuccess;
 758                         nInsertInitFailed += inserter.m_nInsertInitFailed;
 759                     }
 760                     break;
 761                 case deleter_thread:
 762                     {
 763                         delete_thread& deleter = static_cast<delete_thread&>(thr);
 764                         nDeleteSuccess += deleter.m_nDeleteSuccess;
 765                         nDeleteFailed += deleter.m_nDeleteFailed;
 766                     }
 767                     break;
 768                 case extractor_thread:
 769                     {
 770                         extract_thread& extractor = static_cast<extract_thread&>(thr);
 771                         nExtractSuccess += extractor.m_nExtractSuccess;
 772                         nExtractFailed += extractor.m_nExtractFailed;
 773                     }
 774                     break;
 775                 case find_thread:
 776                     {
 777                         observer_thread& observer = static_cast<observer_thread&>( thr );
 778                         nFindEvenSuccess = observer.m_nFindEvenSuccess;
 779                         nFindEvenFailed = observer.m_nFindEvenFailed;
 780                         nFindOddSuccess = observer.m_nFindOddSuccess;
 781                         nFindOddFailed = observer.m_nFindOddFailed;
 782                     }
 783                     break;
 784                 default:
 785                     assert( false );
 786                 }
 787             }
 788
 789             size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
 790
 791             EXPECT_EQ( nInsertInitFailed, 0u );
 792             EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
 793             EXPECT_EQ( nFindEvenFailed, 0u );
 794             EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
 795             EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
 796
 797             propout()
 798                 << std::make_pair( "insert_init_success", nInsertInitSuccess )
 799                 << std::make_pair( "insert_init_failed", nInsertInitFailed )
 800                 << std::make_pair( "insert_success", nInsertSuccess )
 801                 << std::make_pair( "insert_failed", nInsertFailed )
 802                 << std::make_pair( "delete_success", nDeleteSuccess )
 803                 << std::make_pair( "delete_failed", nDeleteFailed )
 804                 << std::make_pair( "extract_success", nExtractSuccess )
 805                 << std::make_pair( "extract_failed", nExtractFailed )
 806                 << std::make_pair( "find_even_success", nFindEvenSuccess )
 807                 << std::make_pair( "find_even_failed", nFindEvenFailed )
 808                 << std::make_pair( "find_odd_success", nFindOddSuccess )
 809                 << std::make_pair( "find_odd_failed", nFindOddFailed );
 810         }
 811
 812         template <typename Set>
 813         void analyze( Set& testSet )
 814         {
 815             // All even keys must be in the set
 816             {
 817                 for ( size_t n = 0; n < s_nSetSize; n +=4 ) {
 818                     for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
 819                         EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
 820                     }
 821                 }
 822             }
 823
 824             check_before_clear( testSet );
 825
 826             testSet.clear();
 827             EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
 828
 829             additional_check( testSet );
 830             print_stat( propout(), testSet );
 831             additional_cleanup( testSet );
 832         }
 833
 834         template <class Set, typename Iterator=typename Set::iterator>
 835         void run_test()
 836         {
 837             static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
 838
 839             Set  testSet( *this );
 840             do_test_with<Iterator>( testSet );
 841             analyze( testSet );
 842         }
 843
 844         template <class Set, typename Iterator=typename Set::iterator>
 845         void run_test_extract()
 846         {
 847             static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
 848
 849             Set  testSet( *this );
 850             do_test_extract_with<Iterator>( testSet );
 851             analyze( testSet );
 852         }
 853
 854         template <class Set>
 855         void run_feldman();
 856
 857         template <class Set>
 858         void run_feldman_reverse();
 859     };
 860
 861     class Set_Iter_Del3_reverse: public Set_Iter_Del3
 862     {
 863     public:
 864         template <class Set>
 865         void run_feldman();
 866     };
 867
 868
 869     class Set_Iter_Del3_LF: public Set_Iter_Del3
 870         , public ::testing::WithParamInterface<size_t>
 871     {
 872     public:
 873         template <class Set>
 874         void run_test()
 875         {
 876             s_nLoadFactor = GetParam();
 877             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 878             Set_Iter_Del3::run_test<Set>();
 879         }
 880
 881         template <class Set>
 882         void run_test_extract()
 883         {
 884             s_nLoadFactor = GetParam();
 885             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 886             Set_Iter_Del3::run_test_extract<Set>();
 887         }
 888
 889         static std::vector<size_t> get_load_factors();
 890     };
 891
 892 } // namespace set