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