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