test/stress/set/iteration/set_iteration.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 #include <cds_test/city.h>
  33
  34 namespace set {
  35
  36 // Test for set's thread-safe iterator:
  37 //   Several thread inserts/erases elemets from the set.
  38 //   Dedicated Iterator thread iterates over the set, calculates CityHash for each element
  39 //   and stores it in the element.
  40 // Test goal: no crash
  41
  42 #define TEST_CASE(TAG, X)  void X();
  43
  44     class Set_Iteration: public cds_test::stress_fixture
  45     {
  46     public:
  47         static size_t s_nSetSize;               // set size
  48         static size_t s_nInsertThreadCount;     // count of insertion thread
  49         static size_t s_nDeleteThreadCount;     // count of deletion thread
  50         static size_t s_nThreadPassCount;       // pass count for each thread
  51         static size_t s_nMaxLoadFactor;         // maximum load factor
  52
  53         static size_t s_nCuckooInitialSize;     // initial size for CuckooSet
  54         static size_t s_nCuckooProbesetSize;    // CuckooSet probeset size (only for list-based probeset)
  55         static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
  56
  57         static size_t s_nFeldmanSet_HeadBits;
  58         static size_t s_nFeldmanSet_ArrayBits;
  59
  60         static size_t s_nLoadFactor;
  61         static std::vector<std::string>  m_arrString;
  62
  63         static void SetUpTestCase();
  64         static void TearDownTestCase();
  65
  66         void on_modifier_done()
  67         {
  68             m_nModifierCount.fetch_sub( 1, atomics::memory_order_relaxed );
  69         }
  70
  71         bool all_modifiers_done() const
  72         {
  73             return m_nModifierCount.load( atomics::memory_order_relaxed ) == 0;
  74         }
  75
  76         typedef std::string key_type;
  77
  78         struct value_type
  79         {
  80             size_t   val;
  81             uint64_t hash;
  82
  83             explicit value_type( size_t v )
  84                 : val(v)
  85                 , hash(0)
  86             {}
  87         };
  88
  89     private:
  90         enum {
  91             insert_thread,
  92             delete_thread,
  93             extract_thread,
  94             iterator_thread
  95         };
  96
  97         atomics::atomic<size_t> m_nModifierCount;
  98
  99         template <class Set>
 100         class Inserter: public cds_test::thread
 101         {
 102             typedef cds_test::thread base_class;
 103
 104             Set&     m_Set;
 105             typedef typename Set::value_type keyval_type;
 106
 107         public:
 108             size_t  m_nInsertSuccess = 0;
 109             size_t  m_nInsertFailed = 0;
 110
 111         public:
 112             Inserter( cds_test::thread_pool& pool, Set& set )
 113                 : base_class( pool, insert_thread )
 114                 , m_Set( set )
 115             {}
 116
 117             Inserter( Inserter& src )
 118                 : base_class( src )
 119                 , m_Set( src.m_Set )
 120             {}
 121
 122             virtual thread * clone()
 123             {
 124                 return new Inserter( *this );
 125             }
 126
 127             virtual void test()
 128             {
 129                 Set& rSet = m_Set;
 130
 131                 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
 132                 size_t nArrSize = m_arrString.size();
 133                 size_t const nSetSize = fixture.s_nSetSize;
 134                 size_t const nPassCount = fixture.s_nThreadPassCount;
 135
 136                 if ( id() & 1 ) {
 137                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 138                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
 139                             if ( rSet.insert( keyval_type( m_arrString[nItem % nArrSize], nItem * 8 )))
 140                                 ++m_nInsertSuccess;
 141                             else
 142                                 ++m_nInsertFailed;
 143                         }
 144                     }
 145                 }
 146                 else {
 147                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 148                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
 149                             if ( rSet.insert( keyval_type( m_arrString[nItem % nArrSize], nItem * 8 )))
 150                                 ++m_nInsertSuccess;
 151                             else
 152                                 ++m_nInsertFailed;
 153                         }
 154                     }
 155                 }
 156
 157                 fixture.on_modifier_done();
 158             }
 159         };
 160
 161         template <class Set>
 162         class Deleter: public cds_test::thread
 163         {
 164             typedef cds_test::thread base_class;
 165
 166             Set&     m_Set;
 167         public:
 168             size_t  m_nDeleteSuccess = 0;
 169             size_t  m_nDeleteFailed = 0;
 170
 171         public:
 172             Deleter( cds_test::thread_pool& pool, Set& set )
 173                 : base_class( pool, delete_thread )
 174                 , m_Set( set )
 175             {}
 176
 177             Deleter( Deleter& src )
 178                 : base_class( src )
 179                 , m_Set( src.m_Set )
 180             {}
 181
 182             virtual thread * clone()
 183             {
 184                 return new Deleter( *this );
 185             }
 186
 187             virtual void test()
 188             {
 189                 Set& rSet = m_Set;
 190
 191                 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
 192                 size_t nArrSize = m_arrString.size();
 193                 size_t const nSetSize = fixture.s_nSetSize;
 194                 size_t const nPassCount = fixture.s_nThreadPassCount;
 195
 196                 if ( id() & 1 ) {
 197                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 198                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
 199                             if ( rSet.erase( m_arrString[nItem % nArrSize] ))
 200                                 ++m_nDeleteSuccess;
 201                             else
 202                                 ++m_nDeleteFailed;
 203                         }
 204                     }
 205                 }
 206                 else {
 207                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 208                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
 209                             if ( rSet.erase( m_arrString[nItem % nArrSize] ))
 210                                 ++m_nDeleteSuccess;
 211                             else
 212                                 ++m_nDeleteFailed;
 213                         }
 214                     }
 215                 }
 216
 217                 fixture.on_modifier_done();
 218             }
 219         };
 220
 221         template <typename GC, class Set>
 222         class Extractor: public cds_test::thread
 223         {
 224             typedef cds_test::thread base_class;
 225             Set&     m_Set;
 226
 227         public:
 228             size_t  m_nDeleteSuccess = 0;
 229             size_t  m_nDeleteFailed = 0;
 230
 231         public:
 232             Extractor( cds_test::thread_pool& pool, Set& set )
 233                 : base_class( pool, extract_thread )
 234                 , m_Set( set )
 235             {}
 236
 237             Extractor( Extractor& src )
 238                 : base_class( src )
 239                 , m_Set( src.m_Set )
 240             {}
 241
 242             virtual thread * clone()
 243             {
 244                 return new Extractor( *this );
 245             }
 246
 247             virtual void test()
 248             {
 249                 Set& rSet = m_Set;
 250
 251                 typename Set::guarded_ptr gp;
 252
 253                 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
 254                 size_t nArrSize = m_arrString.size();
 255                 size_t const nSetSize = fixture.s_nSetSize;
 256                 size_t const nPassCount = fixture.s_nThreadPassCount;
 257
 258                 if ( id() & 1 ) {
 259                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 260                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
 261                             gp = rSet.extract( m_arrString[nItem % nArrSize] );
 262                             if ( gp )
 263                                 ++m_nDeleteSuccess;
 264                             else
 265                                 ++m_nDeleteFailed;
 266                             gp.release();
 267                         }
 268                     }
 269                 }
 270                 else {
 271                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 272                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
 273                             gp = rSet.extract( m_arrString[nItem % nArrSize] );
 274                             if ( gp )
 275                                 ++m_nDeleteSuccess;
 276                             else
 277                                 ++m_nDeleteFailed;
 278                             gp.release();
 279                         }
 280                     }
 281                 }
 282
 283                 fixture.on_modifier_done();
 284             }
 285         };
 286
 287         template <typename RCU, class Set>
 288         class Extractor<cds::urcu::gc<RCU>, Set >: 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             Extractor( cds_test::thread_pool& pool, Set& set )
 299                 : base_class( pool, extract_thread )
 300                 , m_Set( set )
 301             {}
 302
 303             Extractor( Extractor& src )
 304                 : base_class( src )
 305                 , m_Set( src.m_Set )
 306             {}
 307
 308             virtual thread * clone()
 309             {
 310                 return new Extractor( *this );
 311             }
 312
 313             virtual void test()
 314             {
 315                 Set& rSet = m_Set;
 316
 317                 typename Set::exempt_ptr xp;
 318
 319                 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
 320                 size_t nArrSize = m_arrString.size();
 321                 size_t const nSetSize = fixture.s_nSetSize;
 322                 size_t const nPassCount = fixture.s_nThreadPassCount;
 323
 324                 if ( id() & 1 ) {
 325                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 326                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
 327                             if ( Set::c_bExtractLockExternal ) {
 328                                 typename Set::rcu_lock l;
 329                                 xp = rSet.extract( m_arrString[nItem % nArrSize] );
 330                                 if ( xp )
 331                                     ++m_nDeleteSuccess;
 332                                 else
 333                                     ++m_nDeleteFailed;
 334                             }
 335                             else {
 336                                 xp = rSet.extract( m_arrString[nItem % nArrSize] );
 337                                 if ( xp )
 338                                     ++m_nDeleteSuccess;
 339                                 else
 340                                     ++m_nDeleteFailed;
 341                             }
 342                             xp.release();
 343                         }
 344                     }
 345                 }
 346                 else {
 347                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 348                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
 349                             if ( Set::c_bExtractLockExternal ) {
 350                                 typename Set::rcu_lock l;
 351                                 xp = rSet.extract( m_arrString[nItem % nArrSize] );
 352                                 if ( xp )
 353                                     ++m_nDeleteSuccess;
 354                                 else
 355                                     ++m_nDeleteFailed;
 356                             }
 357                             else {
 358                                 xp = rSet.extract( m_arrString[nItem % nArrSize] );
 359                                 if ( xp )
 360                                     ++m_nDeleteSuccess;
 361                                 else
 362                                     ++m_nDeleteFailed;
 363                             }
 364                             xp.release();
 365                         }
 366                     }
 367                 }
 368
 369                 fixture.on_modifier_done();
 370             }
 371         };
 372
 373         template <typename GC, class Set>
 374         class Iterator: public cds_test::thread
 375         {
 376             typedef cds_test::thread base_class;
 377
 378             Set&     m_Set;
 379             typedef typename Set::value_type keyval_type;
 380
 381         public:
 382             size_t  m_nPassCount = 0;
 383             size_t  m_nVisitCount = 0; // how many items the iterator visited
 384
 385         public:
 386             Iterator( cds_test::thread_pool& pool, Set& set )
 387                 : base_class( pool, iterator_thread )
 388                 , m_Set( set )
 389             {}
 390
 391             Iterator( Iterator& src )
 392                 : base_class( src )
 393                 , m_Set( src.m_Set )
 394             {}
 395
 396             virtual thread * clone()
 397             {
 398                 return new Iterator( *this );
 399             }
 400
 401             virtual void test()
 402             {
 403                 Set& rSet = m_Set;
 404
 405                 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
 406                 while ( !fixture.all_modifiers_done() ) {
 407                     ++m_nPassCount;
 408                     typename Set::iterator it;
 409                     typename Set::iterator itEnd;
 410                     itEnd = rSet.end();
 411                     for ( it = rSet.begin(); it != itEnd; ++it ) {
 412                         it->val.hash = CityHash64( it->key.c_str(), it->key.length());
 413                         ++m_nVisitCount;
 414                     }
 415                 }
 416             }
 417         };
 418
 419         template <typename RCU, class Set>
 420         class Iterator<cds::urcu::gc<RCU>, Set>: public cds_test::thread
 421         {
 422             typedef cds_test::thread base_class;
 423
 424             Set&     m_Set;
 425             typedef typename Set::value_type keyval_type;
 426
 427         public:
 428             size_t  m_nPassCount = 0;
 429             size_t  m_nVisitCount = 0; // how many items the iterator visited
 430
 431         public:
 432             Iterator( cds_test::thread_pool& pool, Set& set )
 433                 : base_class( pool, iterator_thread )
 434                 , m_Set( set )
 435             {}
 436
 437             Iterator( Iterator& src )
 438                 : base_class( src )
 439                 , m_Set( src.m_Set )
 440             {}
 441
 442             virtual thread * clone()
 443             {
 444                 return new Iterator( *this );
 445             }
 446
 447             virtual void test()
 448             {
 449                 Set& rSet = m_Set;
 450
 451                 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
 452                 while ( !fixture.all_modifiers_done() ) {
 453                     ++m_nPassCount;
 454                     typename Set::rcu_lock l;
 455                     for ( auto it = rSet.begin(); it != rSet.end(); ++it ) {
 456                         it->val.hash = CityHash64( it->key.c_str(), it->key.length() );
 457                         ++m_nVisitCount;
 458                     }
 459                 }
 460             }
 461         };
 462
 463     protected:
 464         template <class Set>
 465         void do_test( Set& testSet )
 466         {
 467             typedef Inserter<Set> InserterThread;
 468             typedef Deleter<Set>  DeleterThread;
 469             typedef Iterator<typename Set::gc, Set> IteratorThread;
 470
 471             cds_test::thread_pool& pool = get_pool();
 472             pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
 473             pool.add( new DeleterThread( pool, testSet ), s_nDeleteThreadCount );
 474
 475             m_nModifierCount.store( pool.size(), atomics::memory_order_relaxed );
 476             pool.add( new IteratorThread( pool, testSet ), 1 );
 477
 478             propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
 479                 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
 480                 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
 481                 << std::make_pair( "set_size", s_nSetSize );
 482
 483             std::chrono::milliseconds duration = pool.run();
 484
 485             propout() << std::make_pair( "duration", duration );
 486
 487             size_t nInsertSuccess = 0;
 488             size_t nInsertFailed = 0;
 489             size_t nDeleteSuccess = 0;
 490             size_t nDeleteFailed = 0;
 491             size_t nIteratorPassCount = 0;
 492             size_t nIteratorVisitCount = 0;
 493             for ( size_t i = 0; i < pool.size(); ++i ) {
 494                 cds_test::thread& thr = pool.get( i );
 495                 switch ( thr.type() ) {
 496                 case insert_thread:
 497                     {
 498                         InserterThread& inserter = static_cast<InserterThread&>( thr );
 499                         nInsertSuccess += inserter.m_nInsertSuccess;
 500                         nInsertFailed += inserter.m_nInsertFailed;
 501                     }
 502                     break;
 503                 case delete_thread:
 504                     {
 505                         DeleterThread& deleter = static_cast<DeleterThread&>(thr);
 506                         nDeleteSuccess += deleter.m_nDeleteSuccess;
 507                         nDeleteFailed += deleter.m_nDeleteFailed;
 508                     }
 509                     break;
 510                 case iterator_thread:
 511                     {
 512                         IteratorThread& iter = static_cast<IteratorThread&>(thr);
 513                         nIteratorPassCount += iter.m_nPassCount;
 514                         nIteratorVisitCount += iter.m_nVisitCount;
 515                     }
 516                     break;
 517                 default:
 518                     assert( false ); // Forgot anything?..
 519                 }
 520             }
 521
 522             propout()
 523                 << std::make_pair( "insert_success", nInsertSuccess )
 524                 << std::make_pair( "delete_success", nDeleteSuccess )
 525                 << std::make_pair( "insert_failed", nInsertFailed )
 526                 << std::make_pair( "delete_failed", nDeleteFailed )
 527                 << std::make_pair( "iterator_pass_count", nIteratorPassCount )
 528                 << std::make_pair( "iterator_visit_count", nIteratorVisitCount )
 529                 << std::make_pair( "final_set_size", testSet.size() );
 530
 531             testSet.clear();
 532             EXPECT_TRUE( testSet.empty() );
 533
 534             additional_check( testSet );
 535             print_stat( propout(), testSet );
 536             additional_cleanup( testSet );
 537         }
 538
 539         template <class Set>
 540         void do_test_extract( Set& testSet )
 541         {
 542             typedef Inserter<Set> InserterThread;
 543             typedef Deleter<Set>  DeleterThread;
 544             typedef Extractor<typename Set::gc, Set> ExtractThread;
 545             typedef Iterator<typename Set::gc, Set> IteratorThread;
 546
 547             size_t const nDelThreadCount = s_nDeleteThreadCount / 2;
 548             size_t const nExtractThreadCount = s_nDeleteThreadCount - nDelThreadCount;
 549
 550             cds_test::thread_pool& pool = get_pool();
 551             pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
 552             pool.add( new DeleterThread( pool, testSet ), nDelThreadCount );
 553             pool.add( new ExtractThread( pool, testSet ), nExtractThreadCount );
 554
 555             m_nModifierCount.store( pool.size(), atomics::memory_order_relaxed );
 556             pool.add( new IteratorThread( pool, testSet ), 1 );
 557
 558             propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
 559                 << std::make_pair( "delete_thread_count", nDelThreadCount )
 560                 << std::make_pair( "extract_thread_count", nExtractThreadCount )
 561                 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
 562                 << std::make_pair( "set_size", s_nSetSize );
 563
 564             std::chrono::milliseconds duration = pool.run();
 565
 566             propout() << std::make_pair( "duration", duration );
 567
 568             size_t nInsertSuccess = 0;
 569             size_t nInsertFailed = 0;
 570             size_t nDeleteSuccess = 0;
 571             size_t nDeleteFailed = 0;
 572             size_t nExtractSuccess = 0;
 573             size_t nExtractFailed = 0;
 574             size_t nIteratorPassCount = 0;
 575             size_t nIteratorVisitCount = 0;
 576             for ( size_t i = 0; i < pool.size(); ++i ) {
 577                 cds_test::thread& thr = pool.get( i );
 578                 switch ( thr.type() ) {
 579                 case insert_thread:
 580                     {
 581                         InserterThread& inserter = static_cast<InserterThread&>(thr);
 582                         nInsertSuccess += inserter.m_nInsertSuccess;
 583                         nInsertFailed += inserter.m_nInsertFailed;
 584                     }
 585                     break;
 586                 case delete_thread:
 587                     {
 588                         DeleterThread& deleter = static_cast<DeleterThread&>(thr);
 589                         nDeleteSuccess += deleter.m_nDeleteSuccess;
 590                         nDeleteFailed += deleter.m_nDeleteFailed;
 591                     }
 592                     break;
 593                 case extract_thread:
 594                     {
 595                         ExtractThread& extractor = static_cast<ExtractThread&>(thr);
 596                         nExtractSuccess += extractor.m_nDeleteSuccess;
 597                         nExtractFailed += extractor.m_nDeleteFailed;
 598                     }
 599                     break;
 600                 case iterator_thread:
 601                     {
 602                         IteratorThread& iter = static_cast<IteratorThread&>(thr);
 603                         nIteratorPassCount += iter.m_nPassCount;
 604                         nIteratorVisitCount += iter.m_nVisitCount;
 605                     }
 606                     break;
 607                 default:
 608                     assert( false ); // Forgot anything?..
 609                 }
 610             }
 611
 612             propout()
 613                 << std::make_pair( "insert_success", nInsertSuccess )
 614                 << std::make_pair( "delete_success", nDeleteSuccess )
 615                 << std::make_pair( "extract_success", nExtractSuccess )
 616                 << std::make_pair( "insert_failed",  nInsertFailed )
 617                 << std::make_pair( "delete_failed",  nDeleteFailed )
 618                 << std::make_pair( "extract_failed", nExtractFailed )
 619                 << std::make_pair( "iterator_pass_count", nIteratorPassCount )
 620                 << std::make_pair( "iterator_visit_count", nIteratorVisitCount )
 621                 << std::make_pair( "final_set_size", testSet.size() );
 622
 623             testSet.clear();
 624             EXPECT_TRUE( testSet.empty() );
 625
 626             additional_check( testSet );
 627             print_stat( propout(), testSet );
 628             additional_cleanup( testSet );
 629         }
 630
 631         template <class Set>
 632         void run_test()
 633         {
 634             ASSERT_TRUE( m_arrString.size() > 0 );
 635
 636             Set s( *this );
 637             do_test( s );
 638         }
 639
 640         template <class Set>
 641         void run_test_extract()
 642         {
 643             ASSERT_TRUE( m_arrString.size() > 0 );
 644
 645             Set s( *this );
 646             do_test_extract( s );
 647         }
 648     };
 649
 650     class Set_Iteration_LF: public Set_Iteration
 651         , public ::testing::WithParamInterface<size_t>
 652     {
 653     public:
 654         template <class Set>
 655         void run_test()
 656         {
 657             s_nLoadFactor = GetParam();
 658             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 659             Set_Iteration::run_test<Set>();
 660         }
 661
 662         template <class Set>
 663         void run_test_extract()
 664         {
 665             s_nLoadFactor = GetParam();
 666             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 667             Set_Iteration::run_test_extract<Set>();
 668         }
 669
 670         static std::vector<size_t> get_load_factors();
 671     };
 672
 673 } // namespace set