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