tests/unit/map2/map_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 "map2/map_type.h"
  32 #include "cppunit/thread.h"
  33
  34 #include <vector>
  35
  36 namespace map2 {
  37
  38 #define TEST_CASE(TAG, X)  void X();
  39
  40     class Map_InsDel_string: public CppUnitMini::TestCase
  41     {
  42     public:
  43         size_t  c_nMapSize = 1000000;      // map 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
  49         size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
  50         size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
  51         size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
  52
  53         size_t c_nFeldmanMap_HeadBits = 10;
  54         size_t c_nFeldmanMap_ArrayBits = 4;
  55
  56         bool    c_bPrintGCState = true;
  57
  58         size_t  c_nLoadFactor;  // current load factor
  59
  60     private:
  61         typedef std::string key_type;
  62         typedef size_t      value_type;
  63
  64         const std::vector<std::string> *  m_parrString;
  65
  66         template <class Map>
  67         class Inserter: public CppUnitMini::TestThread
  68         {
  69             Map&     m_Map;
  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, Map& rMap )
  81                 : CppUnitMini::TestThread( pool )
  82                 , m_Map( rMap )
  83             {}
  84             Inserter( Inserter& src )
  85                 : CppUnitMini::TestThread( src )
  86                 , m_Map( src.m_Map )
  87             {}
  88
  89             Map_InsDel_string&  getTest()
  90             {
  91                 return reinterpret_cast<Map_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                 Map& rMap = m_Map;
 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 nMapSize = getTest().c_nMapSize;
 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 < nMapSize; ++nItem ) {
 112                             if ( rMap.insert( 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 = nMapSize; nItem > 0; --nItem ) {
 122                             if ( rMap.insert( arrString[nItem % nArrSize], nItem * 8 ) )
 123                                 ++m_nInsertSuccess;
 124                             else
 125                                 ++m_nInsertFailed;
 126                         }
 127                     }
 128                 }
 129             }
 130         };
 131
 132         template <class Map>
 133         class Deleter: public CppUnitMini::TestThread
 134         {
 135             Map&     m_Map;
 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, Map& rMap )
 147                 : CppUnitMini::TestThread( pool )
 148                 , m_Map( rMap )
 149             {}
 150             Deleter( Deleter& src )
 151                 : CppUnitMini::TestThread( src )
 152                 , m_Map( src.m_Map )
 153             {}
 154
 155             Map_InsDel_string&  getTest()
 156             {
 157                 return reinterpret_cast<Map_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                 Map& rMap = m_Map;
 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 nMapSize = getTest().c_nMapSize;
 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 < nMapSize; ++nItem ) {
 178                             if ( rMap.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 = nMapSize; nItem > 0; --nItem ) {
 188                             if ( rMap.erase( arrString[nItem % nArrSize] ) )
 189                                 ++m_nDeleteSuccess;
 190                             else
 191                                 ++m_nDeleteFailed;
 192                         }
 193                     }
 194                 }
 195             }
 196         };
 197
 198     protected:
 199
 200         template <class Map>
 201         void do_test( Map& testMap )
 202         {
 203             typedef Inserter<Map>       InserterThread;
 204             typedef Deleter<Map>        DeleterThread;
 205             cds::OS::Timer    timer;
 206
 207             CppUnitMini::ThreadPool pool( *this );
 208             pool.add( new InserterThread( pool, testMap ), c_nInsertThreadCount );
 209             pool.add( new DeleterThread( pool, testMap ), c_nDeleteThreadCount );
 210             pool.run();
 211             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 212
 213             size_t nInsertSuccess = 0;
 214             size_t nInsertFailed = 0;
 215             size_t nDeleteSuccess = 0;
 216             size_t nDeleteFailed = 0;
 217             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 218                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 219                 if ( pThread ) {
 220                     nInsertSuccess += pThread->m_nInsertSuccess;
 221                     nInsertFailed += pThread->m_nInsertFailed;
 222                 }
 223                 else {
 224                     DeleterThread * p = static_cast<DeleterThread *>( *it );
 225                     nDeleteSuccess += p->m_nDeleteSuccess;
 226                     nDeleteFailed += p->m_nDeleteFailed;
 227                 }
 228             }
 229
 230             CPPUNIT_MSG( "    Totals: Ins succ=" << nInsertSuccess
 231                 << " Del succ=" << nDeleteSuccess << "\n"
 232                       << "          : Ins fail=" << nInsertFailed
 233                 << " Del fail=" << nDeleteFailed
 234                 << " Map size=" << testMap.size()
 235                 );
 236
 237             check_before_cleanup( testMap );
 238
 239             CPPUNIT_MSG( "  Clear map (single-threaded)..." );
 240             timer.reset();
 241             for ( size_t i = 0; i < m_parrString->size(); ++i )
 242                 testMap.erase( (*m_parrString)[i] );
 243             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 244             CPPUNIT_CHECK( testMap.empty() );
 245             CPPUNIT_CHECK_EX( testMap.size() == 0, "size() == " << testMap.size() );
 246
 247             additional_check( testMap );
 248             print_stat( testMap );
 249             additional_cleanup( testMap );
 250         }
 251
 252         template <class Map>
 253         void run_test()
 254         {
 255             m_parrString = &CppUnitMini::TestCase::getTestStrings();
 256
 257             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 258                 << " delete=" << c_nDeleteThreadCount
 259                 << " pass count=" << c_nThreadPassCount
 260                 << " map size=" << c_nMapSize
 261                 );
 262
 263             if ( Map::c_bLoadFactorDepended ) {
 264                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 265                     CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
 266                     Map  testMap( *this );
 267                     do_test( testMap );
 268                     if ( c_bPrintGCState )
 269                         print_gc_state();
 270                 }
 271             }
 272             else {
 273                 Map testMap( *this );
 274                 do_test( testMap );
 275                 if ( c_bPrintGCState )
 276                     print_gc_state();
 277             }
 278         }
 279
 280         void setUpParams( const CppUnitMini::TestCfg& cfg );
 281
 282 #   include "map2/map_defs.h"
 283         CDSUNIT_DECLARE_MichaelMap
 284         CDSUNIT_DECLARE_SplitList
 285         CDSUNIT_DECLARE_SkipListMap
 286         CDSUNIT_DECLARE_EllenBinTreeMap
 287         CDSUNIT_DECLARE_BronsonAVLTreeMap
 288         CDSUNIT_DECLARE_FeldmanHashMap_city
 289         CDSUNIT_DECLARE_StripedMap
 290         CDSUNIT_DECLARE_RefinableMap
 291         CDSUNIT_DECLARE_CuckooMap
 292         CDSUNIT_DECLARE_StdMap
 293
 294         CPPUNIT_TEST_SUITE(Map_InsDel_string)
 295             CDSUNIT_TEST_MichaelMap
 296             CDSUNIT_TEST_SplitList
 297             CDSUNIT_TEST_SkipListMap
 298             CDSUNIT_TEST_EllenBinTreeMap
 299             CDSUNIT_TEST_BronsonAVLTreeMap
 300             CDSUNIT_TEST_FeldmanHashMap_city
 301             CDSUNIT_TEST_CuckooMap
 302             CDSUNIT_TEST_StripedMap
 303             CDSUNIT_TEST_RefinableMap
 304             CDSUNIT_TEST_StdMap
 305         CPPUNIT_TEST_SUITE_END();
 306     };
 307 } // namespace map2