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                 typename Map::guarded_ptr gp;
 399                 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
 400                 size_t const nInsThreadCount = s_nInsThreadCount;
 401
 402                 for ( size_t pass = 0; pass < 2; ++pass ) {
 403                     std::vector<size_t>& arrData = fixture.m_arrRemove;
 404                     if ( id() & 1 ) {
 405                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 406                             for ( size_t i = 0; i < arrData.size(); ++i ) {
 407                                 if ( arrData[i] & 1 ) {
 408                                     gp = extractor< Map, Map::c_bEraseExactKey >::extract( rMap, arrData[i], k );
 409                                     if ( gp )
 410                                         ++m_nDeleteSuccess;
 411                                     else
 412                                         ++m_nDeleteFailed;
 413                                     gp.release();
 414                                 }
 415                             }
 416                             if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
 417                                 break;
 418                         }
 419                     }
 420                     else {
 421                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 422                             for ( size_t i = arrData.size() - 1; i > 0; --i ) {
 423                                 if ( arrData[i] & 1 ) {
 424                                     gp = extractor< Map, Map::c_bEraseExactKey >::extract( rMap, arrData[i], k);
 425                                     if ( gp )
 426                                         ++m_nDeleteSuccess;
 427                                     else
 428                                         ++m_nDeleteFailed;
 429                                     gp.release();
 430                                 }
 431                             }
 432                             if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
 433                                 break;
 434                         }
 435                     }
 436                 }
 437             }
 438         };
 439
 440         template <class RCU, class Map >
 441         class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
 442         {
 443             typedef cds_test::thread base_class;
 444             Map&     m_Map;
 445
 446         public:
 447             size_t  m_nDeleteSuccess = 0;
 448             size_t  m_nDeleteFailed = 0;
 449
 450         public:
 451             Extractor( cds_test::thread_pool& pool, Map& map )
 452                 : base_class( pool, extractor_thread )
 453                 , m_Map( map )
 454             {}
 455
 456             Extractor( Extractor& src )
 457                 : base_class( src )
 458                 , m_Map( src.m_Map )
 459             {}
 460
 461             virtual thread * clone()
 462             {
 463                 return new Extractor( *this );
 464             }
 465
 466             template <typename MapType, bool>
 467             struct extractor {
 468                 static typename Map::exempt_ptr extract( MapType& map, size_t key, size_t /*insThread*/ )
 469                 {
 470                     return map.extract_with( key, key_less());
 471                 }
 472             };
 473
 474             template <typename MapType>
 475             struct extractor<MapType, true>
 476             {
 477                 static typename Map::exempt_ptr extract(MapType& map, size_t key, size_t insThread)
 478                 {
 479                     return map.extract( key_type(key, insThread));
 480                 }
 481             };
 482
 483             virtual void test()
 484             {
 485                 Map& rMap = m_Map;
 486                 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
 487
 488                 typename Map::exempt_ptr xp;
 489                 size_t const nInsThreadCount = s_nInsThreadCount;
 490
 491                 std::vector<size_t>& arrData = fixture.m_arrRemove;
 492                 if ( id() & 1 ) {
 493                     for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 494                         for ( size_t i = 0; i < arrData.size(); ++i ) {
 495                             if ( arrData[i] & 1 ) {
 496                                 if ( Map::c_bExtractLockExternal ) {
 497                                     {
 498                                         typename Map::rcu_lock l;
 499                                         xp = extractor<Map, Map::c_bEraseExactKey>::extract( rMap, arrData[i], k );
 500                                         if ( xp )
 501                                             ++m_nDeleteSuccess;
 502                                         else
 503                                             ++m_nDeleteFailed;
 504                                     }
 505                                 }
 506                                 else {
 507                                     xp = extractor<Map, Map::c_bEraseExactKey>::extract( rMap, arrData[i], k);
 508                                     if ( xp )
 509                                         ++m_nDeleteSuccess;
 510                                     else
 511                                         ++m_nDeleteFailed;
 512                                 }
 513                                 xp.release();
 514                             }
 515                         }
 516                         if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
 517                             break;
 518                     }
 519                 }
 520                 else {
 521                     for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 522                         for ( size_t i = arrData.size() - 1; i > 0; --i ) {
 523                             if ( arrData[i] & 1 ) {
 524                                 if ( Map::c_bExtractLockExternal ) {
 525                                     {
 526                                         typename Map::rcu_lock l;
 527                                         xp = extractor<Map, Map::c_bEraseExactKey>::extract(rMap, arrData[i], k);
 528                                         if ( xp )
 529                                             ++m_nDeleteSuccess;
 530                                         else
 531                                             ++m_nDeleteFailed;
 532                                     }
 533                                 }
 534                                 else {
 535                                     xp = extractor<Map, Map::c_bEraseExactKey>::extract(rMap, arrData[i], k);
 536                                     if ( xp )
 537                                         ++m_nDeleteSuccess;
 538                                     else
 539                                         ++m_nDeleteFailed;
 540                                 }
 541                                 xp.release();
 542                             }
 543                         }
 544                         if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
 545                             break;
 546                     }
 547                 }
 548             }
 549         };
 550
 551     protected:
 552         template <class Map>
 553         void do_test( Map& testMap )
 554         {
 555             typedef Inserter<Map> insert_thread;
 556             typedef Deleter<Map>  delete_thread;
 557
 558             m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
 559
 560             cds_test::thread_pool& pool = get_pool();
 561             pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
 562             pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count() );
 563
 564             propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
 565                 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
 566                 << std::make_pair( "map_size", s_nMapSize );
 567
 568             std::chrono::milliseconds duration = pool.run();
 569
 570             propout() << std::make_pair( "duration", duration );
 571
 572             size_t nInsertSuccess = 0;
 573             size_t nInsertFailed = 0;
 574             size_t nDeleteSuccess = 0;
 575             size_t nDeleteFailed = 0;
 576
 577             for ( size_t i = 0; i < pool.size(); ++i ) {
 578                 cds_test::thread& thr = pool.get( i );
 579                 if ( thr.type() == inserter_thread ) {
 580                     insert_thread& inserter = static_cast<insert_thread&>(thr);
 581                     nInsertSuccess += inserter.m_nInsertSuccess;
 582                     nInsertFailed += inserter.m_nInsertFailed;
 583                 }
 584                 else {
 585                     assert( thr.type() == deleter_thread );
 586                     delete_thread& deleter = static_cast<delete_thread&>(thr);
 587                     nDeleteSuccess += deleter.m_nDeleteSuccess;
 588                     nDeleteFailed += deleter.m_nDeleteFailed;
 589                 }
 590             }
 591
 592             EXPECT_EQ( nInsertSuccess, s_nMapSize * s_nInsThreadCount );
 593             EXPECT_EQ( nInsertFailed, 0 );
 594
 595             propout()
 596                 << std::make_pair( "insert_success", nInsertSuccess )
 597                 << std::make_pair( "insert_failed",  nInsertFailed )
 598                 << std::make_pair( "delete_success", nDeleteSuccess )
 599                 << std::make_pair( "delete_failed",  nDeleteFailed );
 600
 601             analyze( testMap );
 602         }
 603
 604         template <class Map>
 605         void do_test_extract( Map& testMap )
 606         {
 607             typedef Inserter<Map> insert_thread;
 608             typedef Deleter<Map> delete_thread;
 609             typedef Extractor< typename Map::gc, Map > extract_thread;
 610
 611             m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
 612
 613             cds_test::thread_pool& pool = get_pool();
 614             pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
 615             if ( s_nDelThreadCount )
 616                 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount );
 617             if ( s_nExtractThreadCount )
 618                 pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
 619
 620             propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
 621                 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
 622                 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
 623                 << std::make_pair( "map_size", s_nMapSize );
 624
 625             std::chrono::milliseconds duration = pool.run();
 626
 627             propout() << std::make_pair( "duration", duration );
 628
 629             size_t nInsertSuccess = 0;
 630             size_t nInsertFailed = 0;
 631             size_t nDeleteSuccess = 0;
 632             size_t nDeleteFailed = 0;
 633             size_t nExtractSuccess = 0;
 634             size_t nExtractFailed = 0;
 635             for ( size_t i = 0; i < pool.size(); ++i ) {
 636                 cds_test::thread& thr = pool.get( i );
 637                 switch ( thr.type() ) {
 638                 case inserter_thread:
 639                 {
 640                     insert_thread& inserter = static_cast<insert_thread&>(thr);
 641                     nInsertSuccess += inserter.m_nInsertSuccess;
 642                     nInsertFailed += inserter.m_nInsertFailed;
 643                 }
 644                 break;
 645                 case deleter_thread:
 646                 {
 647                     delete_thread& deleter = static_cast<delete_thread&>(thr);
 648                     nDeleteSuccess += deleter.m_nDeleteSuccess;
 649                     nDeleteFailed += deleter.m_nDeleteFailed;
 650                 }
 651                 break;
 652                 case extractor_thread:
 653                 {
 654                     extract_thread& extractor = static_cast<extract_thread&>(thr);
 655                     nExtractSuccess += extractor.m_nDeleteSuccess;
 656                     nExtractFailed += extractor.m_nDeleteFailed;
 657                 }
 658                 break;
 659                 default:
 660                     assert( false );
 661                 }
 662             }
 663
 664             EXPECT_EQ( nInsertSuccess, s_nMapSize * s_nInsThreadCount );
 665             EXPECT_EQ( nInsertFailed, 0 );
 666
 667             propout()
 668                 << std::make_pair( "insert_success", nInsertSuccess )
 669                 << std::make_pair( "insert_failed", nInsertFailed )
 670                 << std::make_pair( "delete_success", nDeleteSuccess )
 671                 << std::make_pair( "delete_failed", nDeleteFailed )
 672                 << std::make_pair( "extract_success", nExtractSuccess )
 673                 << std::make_pair( "extract_failed", nExtractFailed );
 674
 675             analyze( testMap );
 676         }
 677
 678         template <class Map>
 679         void analyze( Map& testMap )
 680         {
 681             // All even keys must be in the map
 682             {
 683                 for ( size_t n = 0; n < s_nMapSize; n +=2 ) {
 684                     for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
 685                         EXPECT_TRUE( testMap.contains( key_type( n, i ) ) ) << "key=" << n << "/" << i;
 686                     }
 687                 }
 688             }
 689
 690             print_stat( propout(), testMap );
 691
 692             check_before_cleanup( testMap );
 693             testMap.clear();
 694             EXPECT_TRUE( testMap.empty() ) << "map.size=" << testMap.size();
 695
 696             additional_check( testMap );
 697             additional_cleanup( testMap );
 698         }
 699
 700         template <class Map>
 701         void run_test_extract()
 702         {
 703             static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
 704
 705             Map testMap( *this );
 706             do_test_extract( testMap );
 707         }
 708
 709         template <class Map>
 710         void run_test()
 711         {
 712             Map testMap( *this );
 713             do_test( testMap );
 714         }
 715     };
 716
 717     class Map_DelOdd_LF: public Map_DelOdd
 718         , public ::testing::WithParamInterface<size_t>
 719     {
 720     public:
 721         template <class Map>
 722         void run_test()
 723         {
 724             s_nLoadFactor = GetParam();
 725             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 726             Map_DelOdd::run_test<Map>();
 727         }
 728
 729         template <class Map>
 730         void run_test_extract()
 731         {
 732             s_nLoadFactor = GetParam();
 733             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 734             Map_DelOdd::run_test_extract<Map>();
 735         }
 736
 737         static std::vector<size_t> get_load_factors();
 738     };
 739
 740 } // namespace map