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