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