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