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