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