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