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