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