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