tests/unit/set2/set_insdel_string.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 "set2/set_type.h"
  32 #include "cppunit/thread.h"
  33
  34 #include <vector>
  35
  36 namespace set2 {
  37
  38 #define TEST_CASE(TAG, X)  void X();
  39
  40     class Set_InsDel_string: public CppUnitMini::TestCase
  41     {
  42     public:
  43         size_t c_nSetSize = 1000000;            // set size
  44         size_t c_nInsertThreadCount = 4;  // count of insertion thread
  45         size_t c_nDeleteThreadCount = 4;  // count of deletion thread
  46         size_t c_nThreadPassCount = 4;    // pass count for each thread
  47         size_t c_nMaxLoadFactor = 8;      // maximum load factor
  48         bool   c_bPrintGCState = true;
  49
  50         size_t  c_nCuckooInitialSize = 1024;// initial size for CuckooSet
  51         size_t  c_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
  52         size_t  c_nCuckooProbesetThreshold = 0; // CUckooSet probeset threshold (0 - use default)
  53
  54         size_t c_nFeldmanSet_HeadBits = 10;
  55         size_t c_nFeldmanSet_ArrayBits = 4;
  56
  57         size_t c_nLoadFactor = 2;
  58
  59     private:
  60         typedef std::string key_type;
  61         typedef size_t      value_type;
  62
  63         const std::vector<std::string> *  m_parrString;
  64
  65         template <class Set>
  66         class Inserter: public CppUnitMini::TestThread
  67         {
  68             Set&     m_Set;
  69             typedef typename Set::value_type    keyval_type;
  70
  71             virtual Inserter *    clone()
  72             {
  73                 return new Inserter( *this );
  74             }
  75         public:
  76             size_t  m_nInsertSuccess;
  77             size_t  m_nInsertFailed;
  78
  79         public:
  80             Inserter( CppUnitMini::ThreadPool& pool, Set& rSet )
  81                 : CppUnitMini::TestThread( pool )
  82                 , m_Set( rSet )
  83             {}
  84             Inserter( Inserter& src )
  85                 : CppUnitMini::TestThread( src )
  86                 , m_Set( src.m_Set )
  87             {}
  88
  89             Set_InsDel_string&  getTest()
  90             {
  91                 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
  92             }
  93
  94             virtual void init() { cds::threading::Manager::attachThread()   ; }
  95             virtual void fini() { cds::threading::Manager::detachThread()   ; }
  96
  97             virtual void test()
  98             {
  99                 Set& rSet = m_Set;
 100
 101                 m_nInsertSuccess =
 102                     m_nInsertFailed = 0;
 103
 104                 const std::vector<std::string>& arrString = *getTest().m_parrString;
 105                 size_t nArrSize = arrString.size();
 106                 size_t const nSetSize = getTest().c_nSetSize;
 107                 size_t const nPassCount = getTest().c_nThreadPassCount;
 108
 109                 if ( m_nThreadNo & 1 ) {
 110                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 111                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
 112                             if ( rSet.insert( keyval_type(arrString[nItem % nArrSize], nItem * 8) ) )
 113                                 ++m_nInsertSuccess;
 114                             else
 115                                 ++m_nInsertFailed;
 116                         }
 117                     }
 118                 }
 119                 else {
 120                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 121                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
 122                             if ( rSet.insert( keyval_type( arrString[nItem % nArrSize], nItem * 8) ) )
 123                                 ++m_nInsertSuccess;
 124                             else
 125                                 ++m_nInsertFailed;
 126                         }
 127                     }
 128                 }
 129             }
 130         };
 131
 132         template <class Set>
 133         class Deleter: public CppUnitMini::TestThread
 134         {
 135             Set&     m_Set;
 136
 137             virtual Deleter *    clone()
 138             {
 139                 return new Deleter( *this );
 140             }
 141         public:
 142             size_t  m_nDeleteSuccess;
 143             size_t  m_nDeleteFailed;
 144
 145         public:
 146             Deleter( CppUnitMini::ThreadPool& pool, Set& rSet )
 147                 : CppUnitMini::TestThread( pool )
 148                 , m_Set( rSet )
 149             {}
 150             Deleter( Deleter& src )
 151                 : CppUnitMini::TestThread( src )
 152                 , m_Set( src.m_Set )
 153             {}
 154
 155             Set_InsDel_string&  getTest()
 156             {
 157                 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
 158             }
 159
 160             virtual void init() { cds::threading::Manager::attachThread()   ; }
 161             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 162
 163             virtual void test()
 164             {
 165                 Set& rSet = m_Set;
 166
 167                 m_nDeleteSuccess =
 168                     m_nDeleteFailed = 0;
 169
 170                 const std::vector<std::string>& arrString = *getTest().m_parrString;
 171                 size_t nArrSize = arrString.size();
 172                 size_t const nSetSize = getTest().c_nSetSize;
 173                 size_t const nPassCount = getTest().c_nThreadPassCount;
 174
 175                 if ( m_nThreadNo & 1 ) {
 176                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 177                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
 178                             if ( rSet.erase( arrString[nItem % nArrSize] ) )
 179                                 ++m_nDeleteSuccess;
 180                             else
 181                                 ++m_nDeleteFailed;
 182                         }
 183                     }
 184                 }
 185                 else {
 186                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 187                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
 188                             if ( rSet.erase( arrString[nItem % nArrSize] ) )
 189                                 ++m_nDeleteSuccess;
 190                             else
 191                                 ++m_nDeleteFailed;
 192                         }
 193                     }
 194                 }
 195             }
 196         };
 197
 198         template <typename GC, class Set>
 199         class Extractor: public CppUnitMini::TestThread
 200         {
 201             Set&     m_Set;
 202
 203             virtual Extractor *    clone()
 204             {
 205                 return new Extractor( *this );
 206             }
 207         public:
 208             size_t  m_nDeleteSuccess;
 209             size_t  m_nDeleteFailed;
 210
 211         public:
 212             Extractor( CppUnitMini::ThreadPool& pool, Set& rSet )
 213                 : CppUnitMini::TestThread( pool )
 214                 , m_Set( rSet )
 215             {}
 216             Extractor( Extractor& src )
 217                 : CppUnitMini::TestThread( src )
 218                 , m_Set( src.m_Set )
 219             {}
 220
 221             Set_InsDel_string&  getTest()
 222             {
 223                 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
 224             }
 225
 226             virtual void init() { cds::threading::Manager::attachThread()   ; }
 227             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 228
 229             virtual void test()
 230             {
 231                 Set& rSet = m_Set;
 232
 233                 m_nDeleteSuccess =
 234                     m_nDeleteFailed = 0;
 235
 236                 typename Set::guarded_ptr gp;
 237
 238                 const std::vector<std::string>& arrString = *getTest().m_parrString;
 239                 size_t nArrSize = arrString.size();
 240                 size_t const nSetSize = getTest().c_nSetSize;
 241                 size_t const nPassCount = getTest().c_nThreadPassCount;
 242
 243                 if ( m_nThreadNo & 1 ) {
 244                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 245                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
 246                             gp = rSet.extract( arrString[nItem % nArrSize]);
 247                             if (  gp )
 248                                 ++m_nDeleteSuccess;
 249                             else
 250                                 ++m_nDeleteFailed;
 251                             gp.release();
 252                         }
 253                     }
 254                 }
 255                 else {
 256                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 257                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
 258                             gp = rSet.extract( arrString[nItem % nArrSize]);
 259                             if ( gp )
 260                                 ++m_nDeleteSuccess;
 261                             else
 262                                 ++m_nDeleteFailed;
 263                             gp.release();
 264                         }
 265                     }
 266                 }
 267             }
 268         };
 269
 270         template <typename RCU, class Set>
 271         class Extractor<cds::urcu::gc<RCU>, Set >: public CppUnitMini::TestThread
 272         {
 273             Set&     m_Set;
 274
 275             virtual Extractor *    clone()
 276             {
 277                 return new Extractor( *this );
 278             }
 279         public:
 280             size_t  m_nDeleteSuccess;
 281             size_t  m_nDeleteFailed;
 282
 283         public:
 284             Extractor( CppUnitMini::ThreadPool& pool, Set& rSet )
 285                 : CppUnitMini::TestThread( pool )
 286                 , m_Set( rSet )
 287             {}
 288             Extractor( Extractor& src )
 289                 : CppUnitMini::TestThread( src )
 290                 , m_Set( src.m_Set )
 291             {}
 292
 293             Set_InsDel_string&  getTest()
 294             {
 295                 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
 296             }
 297
 298             virtual void init() { cds::threading::Manager::attachThread()   ; }
 299             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 300
 301             virtual void test()
 302             {
 303                 Set& rSet = m_Set;
 304
 305                 m_nDeleteSuccess =
 306                     m_nDeleteFailed = 0;
 307
 308                 typename Set::exempt_ptr xp;
 309
 310                 const std::vector<std::string>& arrString = *getTest().m_parrString;
 311                 size_t nArrSize = arrString.size();
 312                 size_t const nSetSize = getTest().c_nSetSize;
 313                 size_t const nPassCount = getTest().c_nThreadPassCount;
 314
 315                 if ( m_nThreadNo & 1 ) {
 316                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 317                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
 318                             if ( Set::c_bExtractLockExternal ) {
 319                                 {
 320                                     typename Set::rcu_lock l;
 321                                     xp = rSet.extract( arrString[nItem % nArrSize] );
 322                                     if ( xp )
 323                                         ++m_nDeleteSuccess;
 324                                     else
 325                                         ++m_nDeleteFailed;
 326                                 }
 327                             }
 328                             else {
 329                                 xp = rSet.extract( arrString[nItem % nArrSize] );
 330                                 if ( xp )
 331                                     ++m_nDeleteSuccess;
 332                                 else
 333                                     ++m_nDeleteFailed;
 334                             }
 335                             xp.release();
 336                         }
 337                     }
 338                 }
 339                 else {
 340                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 341                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
 342                             if ( Set::c_bExtractLockExternal ) {
 343                                 {
 344                                     typename Set::rcu_lock l;
 345                                     xp = rSet.extract( arrString[nItem % nArrSize] );
 346                                     if ( xp )
 347                                         ++m_nDeleteSuccess;
 348                                     else
 349                                         ++m_nDeleteFailed;
 350                                 }
 351                             }
 352                             else {
 353                                 xp = rSet.extract( arrString[nItem % nArrSize] );
 354                                 if ( xp )
 355                                     ++m_nDeleteSuccess;
 356                                 else
 357                                     ++m_nDeleteFailed;
 358                             }
 359                             xp.release();
 360                         }
 361                     }
 362                 }
 363             }
 364         };
 365
 366     protected:
 367         template <class Set>
 368         void do_test( Set& testSet )
 369         {
 370             typedef Inserter<Set>       InserterThread;
 371             typedef Deleter<Set>        DeleterThread;
 372             cds::OS::Timer    timer;
 373
 374             CppUnitMini::ThreadPool pool( *this );
 375             pool.add( new InserterThread( pool, testSet ), c_nInsertThreadCount );
 376             pool.add( new DeleterThread( pool, testSet ), c_nDeleteThreadCount );
 377             pool.run();
 378             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 379
 380             size_t nInsertSuccess = 0;
 381             size_t nInsertFailed = 0;
 382             size_t nDeleteSuccess = 0;
 383             size_t nDeleteFailed = 0;
 384             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 385                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 386                 if ( pThread ) {
 387                     nInsertSuccess += pThread->m_nInsertSuccess;
 388                     nInsertFailed += pThread->m_nInsertFailed;
 389                 }
 390                 else {
 391                     DeleterThread * p = static_cast<DeleterThread *>( *it );
 392                     nDeleteSuccess += p->m_nDeleteSuccess;
 393                     nDeleteFailed += p->m_nDeleteFailed;
 394                 }
 395             }
 396
 397             CPPUNIT_MSG( "    Totals: Ins succ=" << nInsertSuccess
 398                 << " Del succ=" << nDeleteSuccess << "\n"
 399                       << "          : Ins fail=" << nInsertFailed
 400                 << " Del fail=" << nDeleteFailed
 401                 << " Set size=" << testSet.size()
 402                 );
 403
 404
 405             CPPUNIT_MSG( "  Clear set (single-threaded)..." );
 406             timer.reset();
 407             for ( size_t i = 0; i < m_parrString->size(); ++i )
 408                 testSet.erase( (*m_parrString)[i] );
 409             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 410             CPPUNIT_ASSERT( testSet.empty() );
 411
 412             additional_check( testSet );
 413             print_stat(  testSet  );
 414             additional_cleanup( testSet );
 415         }
 416
 417         template <class Set>
 418         void do_test_extract( Set& testSet )
 419         {
 420             typedef Inserter<Set>       InserterThread;
 421             typedef Deleter<Set>        DeleterThread;
 422             typedef Extractor<typename Set::gc, Set> ExtractThread;
 423
 424             size_t nDelThreadCount = c_nDeleteThreadCount / 2;
 425
 426             CppUnitMini::ThreadPool pool( *this );
 427             pool.add( new InserterThread( pool, testSet ), c_nInsertThreadCount );
 428             pool.add( new DeleterThread( pool, testSet ), nDelThreadCount );
 429             pool.add( new ExtractThread( pool, testSet ), c_nDeleteThreadCount - nDelThreadCount );
 430             pool.run();
 431             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 432
 433             size_t nInsertSuccess = 0;
 434             size_t nInsertFailed = 0;
 435             size_t nDeleteSuccess = 0;
 436             size_t nDeleteFailed = 0;
 437             size_t nExtractSuccess = 0;
 438             size_t nExtractFailed = 0;
 439             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 440                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 441                 if ( pThread ) {
 442                     nInsertSuccess += pThread->m_nInsertSuccess;
 443                     nInsertFailed += pThread->m_nInsertFailed;
 444                 }
 445                 else {
 446                     DeleterThread * p = dynamic_cast<DeleterThread *>( *it );
 447                     if ( p ) {
 448                         nDeleteSuccess += p->m_nDeleteSuccess;
 449                         nDeleteFailed += p->m_nDeleteFailed;
 450                     }
 451                     else {
 452                         ExtractThread * pExtract = dynamic_cast<ExtractThread *>( *it );
 453                         assert( pExtract );
 454                         nExtractSuccess += pExtract->m_nDeleteSuccess;
 455                         nExtractFailed += pExtract->m_nDeleteFailed;
 456                     }
 457                 }
 458             }
 459
 460             CPPUNIT_MSG( "    Totals: Ins succ=" << nInsertSuccess
 461                 << " Del succ=" << nDeleteSuccess
 462                 << " Extract succ= " << nExtractSuccess << "\n"
 463                 << "          : Ins fail=" << nInsertFailed
 464                 << " Del fail=" << nDeleteFailed
 465                 << " Extract fail=" << nExtractFailed
 466                 << " Set size=" << testSet.size()
 467                 );
 468
 469
 470             CPPUNIT_MSG( "  Clear set (single-threaded)..." );
 471             cds::OS::Timer    timer;
 472             for ( size_t i = 0; i < m_parrString->size(); ++i )
 473                 testSet.erase( (*m_parrString)[i] );
 474             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 475             CPPUNIT_ASSERT( testSet.empty() );
 476
 477             additional_check( testSet );
 478             print_stat(  testSet  );
 479             additional_cleanup( testSet );
 480         }
 481
 482         template <class Set>
 483         void run_test()
 484         {
 485             m_parrString = &CppUnitMini::TestCase::getTestStrings();
 486
 487             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 488                 << " delete=" << c_nDeleteThreadCount
 489                 << " pass count=" << c_nThreadPassCount
 490                 << " set size=" << c_nSetSize
 491                 );
 492
 493             if ( Set::c_bLoadFactorDepended ) {
 494                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 495                     CPPUNIT_MSG("  LoadFactor = " << c_nLoadFactor );
 496                     Set s( *this );
 497                     do_test( s );
 498                     if ( c_bPrintGCState )
 499                         print_gc_state();
 500                 }
 501             }
 502             else {
 503                 Set s( *this );
 504                 do_test( s );
 505                 if ( c_bPrintGCState )
 506                     print_gc_state();
 507             }
 508         }
 509
 510         template <class Set>
 511         void run_test_extract()
 512         {
 513             m_parrString = &CppUnitMini::TestCase::getTestStrings();
 514
 515             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 516                 << " delete=" << c_nDeleteThreadCount
 517                 << " pass count=" << c_nThreadPassCount
 518                 << " set size=" << c_nSetSize
 519                 );
 520
 521             if ( Set::c_bLoadFactorDepended ) {
 522                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 523                     CPPUNIT_MSG("  LoadFactor = " << c_nLoadFactor );
 524                     Set s( *this );
 525                     do_test_extract( s );
 526                     if ( c_bPrintGCState )
 527                         print_gc_state();
 528                 }
 529             }
 530             else {
 531                 Set s( *this );
 532                 do_test_extract( s );
 533                 if ( c_bPrintGCState )
 534                     print_gc_state();
 535             }
 536         }
 537
 538         void setUpParams( const CppUnitMini::TestCfg& cfg );
 539
 540 #   include "set2/set_defs.h"
 541         CDSUNIT_DECLARE_MichaelSet
 542         CDSUNIT_DECLARE_SplitList
 543         CDSUNIT_DECLARE_StripedSet
 544         CDSUNIT_DECLARE_RefinableSet
 545         CDSUNIT_DECLARE_CuckooSet
 546         CDSUNIT_DECLARE_SkipListSet
 547         CDSUNIT_DECLARE_EllenBinTreeSet
 548         CDSUNIT_DECLARE_FeldmanHashSet_stdhash
 549         CDSUNIT_DECLARE_FeldmanHashSet_city
 550         CDSUNIT_DECLARE_StdSet
 551
 552         CPPUNIT_TEST_SUITE_(Set_InsDel_string, "Map_InsDel_func")
 553             CDSUNIT_TEST_MichaelSet
 554             CDSUNIT_TEST_SplitList
 555             CDSUNIT_TEST_SkipListSet
 556             CDSUNIT_TEST_FeldmanHashSet_stdhash
 557             CDSUNIT_TEST_FeldmanHashSet_city
 558             CDSUNIT_TEST_EllenBinTreeSet
 559             CDSUNIT_TEST_StripedSet
 560             CDSUNIT_TEST_RefinableSet
 561             CDSUNIT_TEST_CuckooSet
 562             CDSUNIT_TEST_StdSet
 563         CPPUNIT_TEST_SUITE_END();
 564     };
 565 } // namespace set2