tests/unit/map2/map_delodd.h

   1 //$$CDS-header$$
   2
   3 #include "cppunit/thread.h"
   4 #include "map2/map_type.h"
   5 #include <cds/os/topology.h>
   6
   7 namespace map2 {
   8
   9 #   define TEST_CASE(TAG, X)  void X();
  10
  11     namespace {
  12         struct key_thread
  13         {
  14             size_t  nKey;
  15             size_t  nThread;
  16
  17             key_thread( size_t key, size_t threadNo )
  18                 : nKey( key )
  19                 , nThread( threadNo )
  20             {}
  21
  22             key_thread()
  23             {}
  24         };
  25     }
  26
  27     template <>
  28     struct cmp<key_thread> {
  29         int operator ()(key_thread const& k1, key_thread const& k2) const
  30         {
  31             if ( k1.nKey < k2.nKey )
  32                 return -1;
  33             if ( k1.nKey > k2.nKey )
  34                 return 1;
  35             if ( k1.nThread < k2.nThread )
  36                 return -1;
  37             if ( k1.nThread > k2.nThread )
  38                 return 1;
  39             return 0;
  40         }
  41         int operator ()(key_thread const& k1, size_t k2) const
  42         {
  43             if ( k1.nKey < k2 )
  44                 return -1;
  45             if ( k1.nKey > k2 )
  46                 return 1;
  47             return 0;
  48         }
  49         int operator ()(size_t k1, key_thread const& k2) const
  50         {
  51             if ( k1 < k2.nKey )
  52                 return -1;
  53             if ( k1 > k2.nKey )
  54                 return 1;
  55             return 0;
  56         }
  57     };
  58
  59 } // namespace map2
  60
  61 namespace std {
  62     template <>
  63     struct less<map2::key_thread>
  64     {
  65         bool operator()(map2::key_thread const& k1, map2::key_thread const& k2) const
  66         {
  67             if ( k1.nKey <= k2.nKey )
  68                 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
  69             return false;
  70         }
  71     };
  72
  73     template <>
  74     struct hash<map2::key_thread>
  75     {
  76         typedef size_t              result_type;
  77         typedef map2::key_thread    argument_type;
  78
  79         size_t operator()( map2::key_thread const& k ) const
  80         {
  81             return std::hash<size_t>()(k.nKey);
  82         }
  83         size_t operator()( size_t k ) const
  84         {
  85             return std::hash<size_t>()(k);
  86         }
  87     };
  88 } // namespace std
  89
  90 namespace boost {
  91     inline size_t hash_value( map2::key_thread const& k )
  92     {
  93         return std::hash<size_t>()( k.nKey );
  94     }
  95
  96     template <>
  97     struct hash<map2::key_thread>
  98     {
  99         typedef size_t              result_type;
 100         typedef map2::key_thread    argument_type;
 101
 102         size_t operator()(map2::key_thread const& k) const
 103         {
 104             return boost::hash<size_t>()( k.nKey );
 105         }
 106         size_t operator()(size_t k) const
 107         {
 108             return boost::hash<size_t>()( k );
 109         }
 110     };
 111 } // namespace boost
 112
 113 namespace map2 {
 114
 115     class Map_DelOdd: public CppUnitMini::TestCase
 116     {
 117     public:
 118         size_t  c_nInsThreadCount = 4;      // insert thread count
 119         size_t  c_nDelThreadCount = 4;      // delete thread count
 120         size_t  c_nExtractThreadCount = 4;  // extract thread count
 121         size_t  c_nMapSize = 1000000;       // max map size
 122         size_t  c_nMaxLoadFactor = 8;       // maximum load factor
 123
 124         size_t  c_nCuckooInitialSize = 1024;// initial size for CuckooMap
 125         size_t  c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
 126         size_t  c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (0 - use default)
 127
 128         size_t c_nFeldmanMap_HeadBits = 10;
 129         size_t c_nFeldmanMap_ArrayBits = 4;
 130
 131         bool    c_bPrintGCState = true;
 132
 133         size_t  c_nLoadFactor;  // current load factor
 134
 135     private:
 136         std::vector<size_t>     m_arrInsert;
 137         std::vector<size_t>     m_arrRemove;
 138
 139     protected:
 140         typedef key_thread  key_type;
 141         typedef size_t      value_type;
 142         typedef std::pair<key_type const, value_type> pair_type;
 143
 144         atomics::atomic<size_t>      m_nInsThreadCount;
 145
 146         // Inserts keys from [0..N)
 147         template <class Map>
 148         class InsertThread: public CppUnitMini::TestThread
 149         {
 150             Map&     m_Map;
 151
 152             virtual InsertThread *    clone()
 153             {
 154                 return new InsertThread( *this );
 155             }
 156
 157             struct ensure_func
 158             {
 159                 template <typename Q>
 160                 void operator()( bool /*bNew*/, Q const& )
 161                 {}
 162                 template <typename Q, typename V>
 163                 void operator()( bool /*bNew*/, Q const&, V& )
 164                 {}
 165
 166                 // FeldmanHashMap
 167                 template <typename Q>
 168                 void operator()( Q&, Q*)
 169                 {}
 170             };
 171         public:
 172             size_t  m_nInsertSuccess;
 173             size_t  m_nInsertFailed;
 174
 175         public:
 176             InsertThread( CppUnitMini::ThreadPool& pool, Map& rMap )
 177                 : CppUnitMini::TestThread( pool )
 178                 , m_Map( rMap )
 179             {}
 180             InsertThread( InsertThread& src )
 181                 : CppUnitMini::TestThread( src )
 182                 , m_Map( src.m_Map )
 183             {}
 184
 185             Map_DelOdd&  getTest()
 186             {
 187                 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
 188             }
 189
 190             virtual void init() { cds::threading::Manager::attachThread()   ; }
 191             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 192
 193             virtual void test()
 194             {
 195                 Map& rMap = m_Map;
 196
 197                 m_nInsertSuccess =
 198                     m_nInsertFailed = 0;
 199
 200                 std::vector<size_t>& arrData = getTest().m_arrInsert;
 201                 for ( size_t i = 0; i < arrData.size(); ++i ) {
 202                     if ( rMap.insert( key_type( arrData[i], m_nThreadNo )))
 203                         ++m_nInsertSuccess;
 204                     else
 205                         ++m_nInsertFailed;
 206                 }
 207
 208                 ensure_func f;
 209                 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
 210                     if ( arrData[i] & 1 ) {
 211                         rMap.update( key_type( arrData[i], m_nThreadNo ), f );
 212                     }
 213                 }
 214
 215                 getTest().m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_acquire );
 216             }
 217         };
 218
 219         struct key_equal {
 220             bool operator()( key_type const& k1, key_type const& k2 ) const
 221             {
 222                 return k1.nKey == k2.nKey;
 223             }
 224             bool operator()( size_t k1, key_type const& k2 ) const
 225             {
 226                 return k1 == k2.nKey;
 227             }
 228             bool operator()( key_type const& k1, size_t k2 ) const
 229             {
 230                 return k1.nKey == k2;
 231             }
 232         };
 233
 234         struct key_less {
 235             bool operator()( key_type const& k1, key_type const& k2 ) const
 236             {
 237                 return k1.nKey < k2.nKey;
 238             }
 239             bool operator()( size_t k1, key_type const& k2 ) const
 240             {
 241                 return k1 < k2.nKey;
 242             }
 243             bool operator()( key_type const& k1, size_t k2 ) const
 244             {
 245                 return k1.nKey < k2;
 246             }
 247
 248             typedef key_equal equal_to;
 249         };
 250
 251         // Deletes odd keys from [0..N)
 252         template <class Map>
 253         class DeleteThread: public CppUnitMini::TestThread
 254         {
 255             Map&     m_Map;
 256
 257             virtual DeleteThread *    clone()
 258             {
 259                 return new DeleteThread( *this );
 260             }
 261         public:
 262             size_t  m_nDeleteSuccess;
 263             size_t  m_nDeleteFailed;
 264
 265         public:
 266             DeleteThread( CppUnitMini::ThreadPool& pool, Map& rMap )
 267                 : CppUnitMini::TestThread( pool )
 268                 , m_Map( rMap )
 269             {}
 270             DeleteThread( DeleteThread& src )
 271                 : CppUnitMini::TestThread( src )
 272                 , m_Map( src.m_Map )
 273             {}
 274
 275             Map_DelOdd&  getTest()
 276             {
 277                 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
 278             }
 279
 280             virtual void init() { cds::threading::Manager::attachThread()   ; }
 281             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 282
 283             template <typename MapType, bool>
 284             struct eraser {
 285                 static bool erase(MapType& map, size_t key, size_t /*insThread*/)
 286                 {
 287                     return map.erase_with(key, key_less());
 288                 }
 289             };
 290
 291             template <typename MapType>
 292             struct eraser<MapType, true>
 293             {
 294                 static bool erase(MapType& map, size_t key, size_t insThread)
 295                 {
 296                     return map.erase(key_type(key, insThread));
 297                 }
 298             };
 299
 300             virtual void test()
 301             {
 302                 Map& rMap = m_Map;
 303
 304                 m_nDeleteSuccess =
 305                     m_nDeleteFailed = 0;
 306
 307                 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
 308
 309                 for ( size_t pass = 0; pass < 2; pass++ ) {
 310                     std::vector<size_t>& arrData = getTest().m_arrRemove;
 311                     if ( m_nThreadNo & 1 ) {
 312                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 313                             for ( size_t i = 0; i < arrData.size(); ++i ) {
 314                                 if ( arrData[i] & 1 ) {
 315                                     if ( Map::c_bEraseExactKey ) {
 316                                         for (size_t key = 0; key < nInsThreadCount; ++key) {
 317                                             if ( eraser<Map, Map::c_bEraseExactKey>::erase( rMap, arrData[i], key ))
 318                                                 ++m_nDeleteSuccess;
 319                                             else
 320                                                 ++m_nDeleteFailed;
 321                                         }
 322                                     }
 323                                     else {
 324                                         if ( eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], 0) )
 325                                             ++m_nDeleteSuccess;
 326                                         else
 327                                             ++m_nDeleteFailed;
 328                                     }
 329                                 }
 330                             }
 331                             if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
 332                                 break;
 333                         }
 334                     }
 335                     else {
 336                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 337                             for ( size_t i = arrData.size() - 1; i > 0; --i ) {
 338                                 if ( arrData[i] & 1 ) {
 339                                     if ( Map::c_bEraseExactKey ) {
 340                                         for (size_t key = 0; key < nInsThreadCount; ++key) {
 341                                             if (eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], key))
 342                                                 ++m_nDeleteSuccess;
 343                                             else
 344                                                 ++m_nDeleteFailed;
 345                                         }
 346                                     }
 347                                     else {
 348                                         if (eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], 0))
 349                                             ++m_nDeleteSuccess;
 350                                         else
 351                                             ++m_nDeleteFailed;
 352                                     }
 353                                 }
 354                             }
 355                             if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
 356                                 break;
 357                         }
 358                     }
 359                 }
 360             }
 361         };
 362
 363         // Deletes odd keys from [0..N)
 364         template <class GC, class Map >
 365         class ExtractThread: public CppUnitMini::TestThread
 366         {
 367             Map&     m_Map;
 368
 369             virtual ExtractThread *    clone()
 370             {
 371                 return new ExtractThread( *this );
 372             }
 373         public:
 374             size_t  m_nDeleteSuccess;
 375             size_t  m_nDeleteFailed;
 376
 377         public:
 378             ExtractThread( CppUnitMini::ThreadPool& pool, Map& rMap )
 379                 : CppUnitMini::TestThread( pool )
 380                 , m_Map( rMap )
 381             {}
 382             ExtractThread( ExtractThread& src )
 383                 : CppUnitMini::TestThread( src )
 384                 , m_Map( src.m_Map )
 385             {}
 386
 387             Map_DelOdd&  getTest()
 388             {
 389                 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
 390             }
 391
 392             virtual void init() { cds::threading::Manager::attachThread()   ; }
 393             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 394
 395             template <typename MapType, bool>
 396             struct extractor {
 397                 static typename Map::guarded_ptr extract(MapType& map, size_t key, size_t /*insThread*/)
 398                 {
 399                     return map.extract_with(key, key_less());
 400                 }
 401             };
 402
 403             template <typename MapType>
 404             struct extractor<MapType, true>
 405             {
 406                 static typename Map::guarded_ptr extract(MapType& map, size_t key, size_t insThread)
 407                 {
 408                     return map.extract(key_type(key, insThread));
 409                 }
 410             };
 411
 412             virtual void test()
 413             {
 414                 Map& rMap = m_Map;
 415
 416                 m_nDeleteSuccess =
 417                     m_nDeleteFailed = 0;
 418
 419                 typename Map::guarded_ptr gp;
 420                 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
 421
 422                 for ( size_t pass = 0; pass < 2; ++pass ) {
 423                     std::vector<size_t>& arrData = getTest().m_arrRemove;
 424                     if ( m_nThreadNo & 1 ) {
 425                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 426                             for ( size_t i = 0; i < arrData.size(); ++i ) {
 427                                 if ( arrData[i] & 1 ) {
 428                                     gp = extractor< Map, Map::c_bEraseExactKey >::extract( rMap, arrData[i], k );
 429                                     if ( gp )
 430                                         ++m_nDeleteSuccess;
 431                                     else
 432                                         ++m_nDeleteFailed;
 433                                     gp.release();
 434                                 }
 435                             }
 436                             if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
 437                                 break;
 438                         }
 439                     }
 440                     else {
 441                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 442                             for ( size_t i = arrData.size() - 1; i > 0; --i ) {
 443                                 if ( arrData[i] & 1 ) {
 444                                     gp = extractor< Map, Map::c_bEraseExactKey >::extract( rMap, arrData[i], k);
 445                                     if ( gp )
 446                                         ++m_nDeleteSuccess;
 447                                     else
 448                                         ++m_nDeleteFailed;
 449                                     gp.release();
 450                                 }
 451                             }
 452                             if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
 453                                 break;
 454                         }
 455                     }
 456                 }
 457             }
 458         };
 459
 460         template <class RCU, class Map >
 461         class ExtractThread< cds::urcu::gc<RCU>, Map > : public CppUnitMini::TestThread
 462         {
 463             Map&     m_Map;
 464
 465             virtual ExtractThread *    clone()
 466             {
 467                 return new ExtractThread( *this );
 468             }
 469         public:
 470             size_t  m_nDeleteSuccess;
 471             size_t  m_nDeleteFailed;
 472
 473         public:
 474             ExtractThread( CppUnitMini::ThreadPool& pool, Map& rMap )
 475                 : CppUnitMini::TestThread( pool )
 476                 , m_Map( rMap )
 477             {}
 478             ExtractThread( ExtractThread& src )
 479                 : CppUnitMini::TestThread( src )
 480                 , m_Map( src.m_Map )
 481             {}
 482
 483             Map_DelOdd&  getTest()
 484             {
 485                 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
 486             }
 487
 488             virtual void init() { cds::threading::Manager::attachThread()   ; }
 489             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 490
 491             template <typename MapType, bool>
 492             struct extractor {
 493                 static typename Map::exempt_ptr extract( MapType& map, size_t key, size_t /*insThread*/ )
 494                 {
 495                     return map.extract_with( key, key_less());
 496                 }
 497             };
 498
 499             template <typename MapType>
 500             struct extractor<MapType, true>
 501             {
 502                 static typename Map::exempt_ptr extract(MapType& map, size_t key, size_t insThread)
 503                 {
 504                     return map.extract( key_type(key, insThread));
 505                 }
 506             };
 507
 508             virtual void test()
 509             {
 510                 Map& rMap = m_Map;
 511
 512                 m_nDeleteSuccess =
 513                     m_nDeleteFailed = 0;
 514
 515                 typename Map::exempt_ptr xp;
 516                 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
 517
 518                 std::vector<size_t>& arrData = getTest().m_arrRemove;
 519                 if ( m_nThreadNo & 1 ) {
 520                     for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 521                         for ( size_t i = 0; i < arrData.size(); ++i ) {
 522                             if ( arrData[i] & 1 ) {
 523                                 if ( Map::c_bExtractLockExternal ) {
 524                                     {
 525                                         typename Map::rcu_lock l;
 526                                         xp = extractor<Map, Map::c_bEraseExactKey>::extract( rMap, arrData[i], k );
 527                                         if ( xp )
 528                                             ++m_nDeleteSuccess;
 529                                         else
 530                                             ++m_nDeleteFailed;
 531                                     }
 532                                 }
 533                                 else {
 534                                     xp = extractor<Map, Map::c_bEraseExactKey>::extract( rMap, arrData[i], k);
 535                                     if ( xp )
 536                                         ++m_nDeleteSuccess;
 537                                     else
 538                                         ++m_nDeleteFailed;
 539                                 }
 540                                 xp.release();
 541                             }
 542                         }
 543                         if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
 544                             break;
 545                     }
 546                 }
 547                 else {
 548                     for ( size_t k = 0; k < nInsThreadCount; ++k ) {
 549                         for ( size_t i = arrData.size() - 1; i > 0; --i ) {
 550                             if ( arrData[i] & 1 ) {
 551                                 if ( Map::c_bExtractLockExternal ) {
 552                                     {
 553                                         typename Map::rcu_lock l;
 554                                         xp = extractor<Map, Map::c_bEraseExactKey>::extract(rMap, arrData[i], k);
 555                                         if ( xp )
 556                                             ++m_nDeleteSuccess;
 557                                         else
 558                                             ++m_nDeleteFailed;
 559                                     }
 560                                 }
 561                                 else {
 562                                     xp = extractor<Map, Map::c_bEraseExactKey>::extract(rMap, arrData[i], k);
 563                                     if ( xp )
 564                                         ++m_nDeleteSuccess;
 565                                     else
 566                                         ++m_nDeleteFailed;
 567                                 }
 568                                 xp.release();
 569                             }
 570                         }
 571                         if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
 572                             break;
 573                     }
 574                 }
 575             }
 576         };
 577
 578     protected:
 579         template <class Map>
 580         void do_test()
 581         {
 582             Map  testMap( *this );
 583             do_test_with( testMap );
 584         }
 585
 586         template <class Map>
 587         void do_test_extract()
 588         {
 589             Map  testMap( *this );
 590             do_test_extract_with( testMap );
 591         }
 592
 593         template <class Map>
 594         void do_test_with( Map& testMap )
 595         {
 596             typedef InsertThread<Map> insert_thread;
 597             typedef DeleteThread<Map> delete_thread;
 598
 599             m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
 600
 601             CppUnitMini::ThreadPool pool( *this );
 602             pool.add( new insert_thread( pool, testMap ), c_nInsThreadCount );
 603             pool.add( new delete_thread( pool, testMap ), c_nDelThreadCount ? c_nDelThreadCount : cds::OS::topology::processor_count());
 604             pool.run();
 605             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 606
 607             size_t nInsertSuccess = 0;
 608             size_t nInsertFailed = 0;
 609             size_t nDeleteSuccess = 0;
 610             size_t nDeleteFailed = 0;
 611             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 612                 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
 613                 if ( pThread ) {
 614                     nInsertSuccess += pThread->m_nInsertSuccess;
 615                     nInsertFailed += pThread->m_nInsertFailed;
 616                 }
 617                 else {
 618                     delete_thread * p = static_cast<delete_thread *>( *it );
 619                     nDeleteSuccess += p->m_nDeleteSuccess;
 620                     nDeleteFailed += p->m_nDeleteFailed;
 621                 }
 622             }
 623
 624             CPPUNIT_MSG( "  Totals (success/failed): \n\t"
 625                 << "      Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
 626                 << "      Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
 627                 );
 628             CPPUNIT_CHECK( nInsertSuccess == c_nMapSize * c_nInsThreadCount );
 629             CPPUNIT_CHECK( nInsertFailed == 0 );
 630
 631             analyze( testMap );
 632         }
 633
 634         template <class Map>
 635         void do_test_extract_with( Map& testMap )
 636         {
 637             typedef InsertThread<Map> insert_thread;
 638             typedef DeleteThread<Map> delete_thread;
 639             typedef ExtractThread< typename Map::gc, Map > extract_thread;
 640
 641             m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
 642
 643             CppUnitMini::ThreadPool pool( *this );
 644             pool.add( new insert_thread( pool, testMap ), c_nInsThreadCount );
 645             if ( c_nDelThreadCount )
 646                 pool.add( new delete_thread( pool, testMap ), c_nDelThreadCount );
 647             if ( c_nExtractThreadCount )
 648                 pool.add( new extract_thread( pool, testMap ), c_nExtractThreadCount );
 649             pool.run();
 650             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 651
 652             size_t nInsertSuccess = 0;
 653             size_t nInsertFailed = 0;
 654             size_t nDeleteSuccess = 0;
 655             size_t nDeleteFailed = 0;
 656             size_t nExtractSuccess = 0;
 657             size_t nExtractFailed = 0;
 658             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 659                 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
 660                 if ( pThread ) {
 661                     nInsertSuccess += pThread->m_nInsertSuccess;
 662                     nInsertFailed += pThread->m_nInsertFailed;
 663                 }
 664                 else {
 665                     delete_thread * p = dynamic_cast<delete_thread *>( *it );
 666                     if ( p ) {
 667                         nDeleteSuccess += p->m_nDeleteSuccess;
 668                         nDeleteFailed += p->m_nDeleteFailed;
 669                     }
 670                     else {
 671                         extract_thread * pExtract = dynamic_cast<extract_thread *>( *it );
 672                         assert( pExtract );
 673                         nExtractSuccess += pExtract->m_nDeleteSuccess;
 674                         nExtractFailed += pExtract->m_nDeleteFailed;
 675                     }
 676                 }
 677             }
 678
 679             CPPUNIT_MSG( "  Totals (success/failed): \n\t"
 680                 << "      Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
 681                 << "      Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
 682                 << "      Extract=" << nExtractSuccess << '/' << nExtractFailed << "\n\t"
 683                 );
 684             CPPUNIT_CHECK( nInsertSuccess == c_nMapSize * c_nInsThreadCount );
 685             CPPUNIT_CHECK( nInsertFailed == 0 );
 686
 687             analyze( testMap );
 688         }
 689
 690         template <class Map>
 691         void analyze( Map& testMap )
 692         {
 693             cds::OS::Timer    timer;
 694
 695             // All even keys must be in the map
 696             {
 697                 size_t nErrorCount = 0;
 698                 CPPUNIT_MSG( "  Check even keys..." );
 699                 for ( size_t n = 0; n < c_nMapSize; n +=2 ) {
 700                     for ( size_t i = 0; i < c_nInsThreadCount; ++i ) {
 701                         if ( !testMap.contains( key_type(n, i) ) ) {
 702                             if ( ++nErrorCount < 10 ) {
 703                                 CPPUNIT_MSG( "key " << n << "-" << i << " is not found!");
 704                             }
 705                         }
 706                     }
 707                 }
 708                 CPPUNIT_CHECK_EX( nErrorCount == 0, "Totals: " << nErrorCount << " keys is not found");
 709             }
 710
 711             check_before_cleanup( testMap );
 712
 713             CPPUNIT_MSG( "  Clear map (single-threaded)..." );
 714             timer.reset();
 715             testMap.clear();
 716             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 717             CPPUNIT_CHECK_EX( testMap.empty(), ((long long) testMap.size()) );
 718
 719             additional_check( testMap );
 720             print_stat( testMap );
 721
 722             additional_cleanup( testMap );
 723         }
 724
 725         template <class Map>
 726         void run_test()
 727         {
 728             static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
 729
 730             CPPUNIT_MSG( "Thread count: insert=" << c_nInsThreadCount
 731                 << ", delete=" << c_nDelThreadCount
 732                 << ", extract=" << c_nExtractThreadCount
 733                 << "; set size=" << c_nMapSize
 734                 );
 735             if ( Map::c_bLoadFactorDepended ) {
 736                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 737                     CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
 738                     do_test_extract<Map>();
 739                     if ( c_bPrintGCState )
 740                         print_gc_state();
 741                 }
 742             }
 743             else
 744                 do_test_extract<Map>();
 745         }
 746
 747         template <class Map>
 748         void run_test_no_extract()
 749         {
 750             static_assert( !Map::c_bExtractSupported, "Map class must not support extract() method" );
 751
 752             CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
 753                 << " delete thread count=" << c_nDelThreadCount
 754                 << " set size=" << c_nMapSize
 755                 );
 756             if ( Map::c_bLoadFactorDepended ) {
 757                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 758                     CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
 759                     do_test<Map>();
 760                     if ( c_bPrintGCState )
 761                         print_gc_state();
 762                 }
 763             }
 764             else
 765                 do_test<Map>();
 766         }
 767
 768         void setUpParams( const CppUnitMini::TestCfg& cfg );
 769
 770 #   include "map2/map_defs.h"
 771         CDSUNIT_DECLARE_MichaelMap
 772         CDSUNIT_DECLARE_SplitList
 773         CDSUNIT_DECLARE_SkipListMap
 774         CDSUNIT_DECLARE_EllenBinTreeMap
 775         CDSUNIT_DECLARE_BronsonAVLTreeMap
 776         CDSUNIT_DECLARE_FeldmanHashMap_fixed
 777         CDSUNIT_DECLARE_FeldmanHashMap_city
 778         CDSUNIT_DECLARE_CuckooMap
 779
 780         CPPUNIT_TEST_SUITE(Map_DelOdd)
 781             CDSUNIT_TEST_MichaelMap
 782             CDSUNIT_TEST_SplitList
 783             CDSUNIT_TEST_SkipListMap
 784             CDSUNIT_TEST_EllenBinTreeMap
 785             CDSUNIT_TEST_BronsonAVLTreeMap
 786             CDSUNIT_TEST_FeldmanHashMap_fixed
 787             CDSUNIT_TEST_FeldmanHashMap_city
 788             CDSUNIT_TEST_CuckooMap
 789         CPPUNIT_TEST_SUITE_END();
 790
 791         // Not implemented yet
 792         ////CDSUNIT_DECLARE_StripedMap
 793         ////CDSUNIT_DECLARE_RefinableMap
 794         ////CDSUNIT_DECLARE_StdMap
 795     };
 796 } // namespace map2