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             {}
  50         };
  51     }
  52
  53     template <>
  54     struct cmp<key_thread> {
  55         int operator ()(key_thread const& k1, key_thread const& k2) const
  56         {
  57             if ( k1.nKey < k2.nKey )
  58                 return -1;
  59             if ( k1.nKey > k2.nKey )
  60                 return 1;
  61             if ( k1.nThread < k2.nThread )
  62                 return -1;
  63             if ( k1.nThread > k2.nThread )
  64                 return 1;
  65             return 0;
  66         }
  67         int operator ()(key_thread const& k1, size_t k2) const
  68         {
  69             if ( k1.nKey < k2 )
  70                 return -1;
  71             if ( k1.nKey > k2 )
  72                 return 1;
  73             return 0;
  74         }
  75         int operator ()(size_t k1, key_thread const& k2) const
  76         {
  77             if ( k1 < k2.nKey )
  78                 return -1;
  79             if ( k1 > k2.nKey )
  80                 return 1;
  81             return 0;
  82         }
  83     };
  84
  85     template <>
  86     struct less<key_thread>
  87     {
  88         bool operator()( key_thread const& k1, key_thread const& k2 ) const
  89         {
  90             if ( k1.nKey <= k2.nKey )
  91                 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
  92             return false;
  93         }
  94     };
  95
  96     template <>
  97     struct hash<key_thread>
  98     {
  99         typedef size_t             result_type;
 100         typedef key_thread    argument_type;
 101
 102         size_t operator()( key_thread const& k ) const
 103         {
 104             return std::hash<size_t>()(k.nKey);
 105         }
 106         size_t operator()( size_t k ) const
 107         {
 108             return std::hash<size_t>()(k);
 109         }
 110     };
 111
 112     class Map_DelOdd: public cds_test::stress_fixture
 113     {
 114     public:
 115         static size_t s_nInsThreadCount;      // insert thread count
 116         static size_t s_nDelThreadCount;      // delete thread count
 117         static size_t s_nExtractThreadCount;  // extract thread count
 118         static size_t s_nMapSize;             // max map size
 119         static size_t s_nMaxLoadFactor;       // maximum load factor
 120
 121         static size_t s_nCuckooInitialSize;       // initial size for CuckooMap
 122         static size_t s_nCuckooProbesetSize;      // CuckooMap probeset size (only for list-based probeset)
 123         static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (0 - use default)
 124
 125         static size_t s_nFeldmanMap_HeadBits;
 126         static size_t s_nFeldmanMap_ArrayBits;
 127
 128         static size_t  s_nLoadFactor;  // current load factor
 129
 130         static std::vector<size_t> m_arrInsert;
 131         static std::vector<size_t> m_arrRemove;
 132
 133         static void SetUpTestCase();
 134         static void TearDownTestCase();
 135
 136     protected:
 137         typedef key_thread  key_type;
 138         typedef size_t      value_type;
 139         typedef std::pair<key_type const, value_type> pair_type;
 140
 141         atomics::atomic<size_t> m_nInsThreadCount;
 142
 143         enum {
 144             inserter_thread,
 145             deleter_thread,
 146             extractor_thread,
 147         };
 148
 149         // Inserts keys from [0..N)
 150         template <class Map>
 151         class Inserter: public cds_test::thread
 152         {
 153             typedef cds_test::thread base_class;
 154             Map&     m_Map;
 155
 156             struct ensure_func
 157             {
 158                 template <typename Q>
 159                 void operator()( bool /*bNew*/, Q const& )
 160                 {}
 161                 template <typename Q, typename V>
 162                 void operator()( bool /*bNew*/, Q const&, V& )
 163                 {}
 164
 165                 // FeldmanHashMap
 166                 template <typename Q>
 167                 void operator()( Q&, Q*)
 168                 {}
 169             };
 170         public:
 171             size_t m_nInsertSuccess = 0;
 172             size_t m_nInsertFailed = 0;
 173
 174         public:
 175             Inserter( cds_test::thread_pool& pool, Map& map )
 176                 : base_class( pool, inserter_thread )
 177                 , m_Map( map )
 178             {}
 179
 180             Inserter( Inserter& src )
 181                 : base_class( src )
 182                 , m_Map( src.m_Map )
 183             {}
 184
 185             virtual thread * clone()
 186             {
 187                 return new Inserter( *this );
 188             }
 189
 190             virtual void test()
 191             {
 192                 Map& rMap = m_Map;
 193                 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
 194
 195                 std::vector<size_t>& arrData = fixture.m_arrInsert;
 196                 for ( size_t i = 0; i < arrData.size(); ++i ) {
 197                     if ( rMap.insert( key_type( arrData[i], id() )))
 198                         ++m_nInsertSuccess;
 199                     else
 200                         ++m_nInsertFailed;
 201                 }
 202
 203                 ensure_func f;
 204                 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
 205                     if ( arrData[i] & 1 ) {
 206                         rMap.update( key_type( arrData[i], id() ), f );
 207                     }
 208                 }
 209
 210                 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_acquire );
 211             }
 212         };
 213
 214         struct key_equal {
 215             bool operator()( key_type const& k1, key_type const& k2 ) const
 216             {
 217                 return k1.nKey == k2.nKey;
 218             }
 219             bool operator()( size_t k1, key_type const& k2 ) const
 220             {
 221                 return k1 == k2.nKey;
 222             }
 223             bool operator()( key_type const& k1, size_t k2 ) const
 224             {
 225                 return k1.nKey == k2;
 226             }
 227         };
 228
 229         struct key_less {
 230             bool operator()( key_type const& k1, key_type const& k2 ) const
 231             {
 232                 return k1.nKey < k2.nKey;
 233             }
 234             bool operator()( size_t k1, key_type const& k2 ) const
 235             {
 236                 return k1 < k2.nKey;
 237             }
 238             bool operator()( key_type const& k1, size_t k2 ) const
 239             {
 240                 return k1.nKey < k2;
 241             }
 242
 243             typedef key_equal equal_to;
 244         };
 245
 246         // Deletes odd keys from [0..N)
 247         template <class Map>
 248         class Deleter: public cds_test::thread
 249         {
 250             typedef cds_test::thread base_class;
 251             Map&     m_Map;
 252
 253         public:
 254             size_t  m_nDeleteSuccess = 0;
 255             size_t  m_nDeleteFailed = 0;
 256
 257         public:
 258             Deleter( cds_test::thread_pool& pool, Map& map )
 259                 : base_class( pool, deleter_thread )
 260                 , m_Map( map )
 261             {}
 262             Deleter( Deleter& src )
 263                 : base_class( src )
 264                 , m_Map( src.m_Map )
 265             {}
 266
 267             virtual thread * clone()
 268             {
 269                 return new Deleter( *this );
 270             }
 271
 272             template <typename MapType, bool>
 273             struct eraser {
 274                 static bool erase(MapType& map, size_t key, size_t /*insThread*/)
 275                 {
 276                     return map.erase_with(key, key_less());
 277                 }
 278             };
 279
 280             template <typename MapType>
 281             struct eraser<MapType, true>
 282             {
 283                 static bool erase(MapType& map, size_t key, size_t insThread)
 284                 {
 285                     return map.erase(key_type(key, insThread));
 286                 }
 287             };
 288
 289             virtual void test()
 290             {
 291                 Map& rMap = m_Map;
 292
 293                 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
 294                 size_t const nInsThreadCount = s_nInsThreadCount;
 295
 296                 for ( size_t pass = 0; pass < 2; pass++ ) {
 297                     std::vector<size_t>& arrData = fixture.m_arrRemove;
 298                     if ( id() & 1 ) {
 299                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 300                             for ( size_t i = 0; i < arrData.size(); ++i ) {
 301                                 if ( arrData[i] & 1 ) {
 302                                     if ( Map::c_bEraseExactKey ) {
 303                                         for (size_t key = 0; key < nInsThreadCount; ++key) {
 304                                             if ( eraser<Map, Map::c_bEraseExactKey>::erase( rMap, arrData[i], key ))
 305                                                 ++m_nDeleteSuccess;
 306                                             else
 307                                                 ++m_nDeleteFailed;
 308                                         }
 309                                     }
 310                                     else {
 311                                         if ( eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], 0))
 312                                             ++m_nDeleteSuccess;
 313                                         else
 314                                             ++m_nDeleteFailed;
 315                                     }
 316                                 }
 317                             }
 318                             if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
 319                                 break;
 320                         }
 321                     }
 322                     else {
 323                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 324                             for ( size_t i = arrData.size() - 1; i > 0; --i ) {
 325                                 if ( arrData[i] & 1 ) {
 326                                     if ( Map::c_bEraseExactKey ) {
 327                                         for (size_t key = 0; key < nInsThreadCount; ++key) {
 328                                             if (eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], key))
 329                                                 ++m_nDeleteSuccess;
 330                                             else
 331                                                 ++m_nDeleteFailed;
 332                                         }
 333                                     }
 334                                     else {
 335                                         if (eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], 0))
 336                                             ++m_nDeleteSuccess;
 337                                         else
 338                                             ++m_nDeleteFailed;
 339                                     }
 340                                 }
 341                             }
 342                             if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
 343                                 break;
 344                         }
 345                     }
 346                 }
 347             }
 348         };
 349
 350         // Deletes odd keys from [0..N)
 351         template <class GC, class Map >
 352         class Extractor: public cds_test::thread
 353         {
 354             typedef cds_test::thread base_class;
 355             Map&     m_Map;
 356
 357         public:
 358             size_t  m_nDeleteSuccess = 0;
 359             size_t  m_nDeleteFailed = 0;
 360
 361         public:
 362             Extractor( cds_test::thread_pool& pool, Map& map )
 363                 : base_class( pool, extractor_thread )
 364                 , m_Map( map )
 365             {}
 366
 367             Extractor( Extractor& src )
 368                 : base_class( src )
 369                 , m_Map( src.m_Map )
 370             {}
 371
 372             virtual thread * clone()
 373             {
 374                 return new Extractor( *this );
 375             }
 376
 377             template <typename MapType, bool>
 378             struct extractor {
 379                 static typename Map::guarded_ptr extract(MapType& map, size_t key, size_t /*insThread*/)
 380                 {
 381                     return map.extract_with(key, key_less());
 382                 }
 383             };
 384
 385             template <typename MapType>
 386             struct extractor<MapType, true>
 387             {
 388                 static typename Map::guarded_ptr extract(MapType& map, size_t key, size_t insThread)
 389                 {
 390                     return map.extract(key_type(key, insThread));
 391                 }
 392             };
 393
 394             virtual void test()
 395             {
 396                 Map& rMap = m_Map;
 397
 398                 m_nDeleteSuccess =
 399                     m_nDeleteFailed = 0;
 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, 0 );
 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, 0 );
 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