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