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