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