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