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