tests/unit/map2/map_insdel_item_int.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_Item_int: public CppUnitMini::TestCase
  41     {
  42     public:
  43         size_t  c_nMapSize = 1000000;       // map size
  44         size_t  c_nThreadCount = 4;         // thread count
  45         size_t  c_nAttemptCount = 100000;   // count of SUCCESS insert/delete for each thread
  46         size_t  c_nMaxLoadFactor = 8;       // maximum load factor
  47         bool    c_bPrintGCState = true;
  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         size_t  c_nGoalItem;
  57         size_t  c_nLoadFactor = 2;  // current load factor
  58
  59     private:
  60         typedef size_t  key_type;
  61         typedef size_t  value_type;
  62
  63         template <class Map>
  64         class Inserter: public CppUnitMini::TestThread
  65         {
  66             Map&     m_Map;
  67
  68             virtual Inserter *    clone()
  69             {
  70                 return new Inserter( *this );
  71             }
  72
  73             struct update_func
  74             {
  75                 void operator()( bool bNew, std::pair<key_type const, value_type>& item )
  76                 {
  77                     if ( bNew )
  78                         item.second = item.first;
  79                 }
  80                 // for boost::container::flat_map
  81                 void operator()( bool bNew, std::pair<key_type, value_type>& item )
  82                 {
  83                     if ( bNew )
  84                         item.second = item.first;
  85                 }
  86
  87                 // for BronsonAVLTreeMap
  88                 void operator()( bool bNew, key_type key, value_type& val )
  89                 {
  90                     if ( bNew )
  91                         val = key;
  92                 }
  93
  94                 // for FeldmanHashMap
  95                 void operator()( std::pair<key_type const, value_type>& item, std::pair<key_type const, value_type> * pOld )
  96                 {
  97                     if ( !pOld )
  98                         item.second = item.first;
  99                 }
 100             };
 101
 102         public:
 103             size_t  m_nInsertSuccess;
 104             size_t  m_nInsertFailed;
 105
 106         public:
 107             Inserter( CppUnitMini::ThreadPool& pool, Map& rMap )
 108                 : CppUnitMini::TestThread( pool )
 109                 , m_Map( rMap )
 110             {}
 111             Inserter( Inserter& src )
 112                 : CppUnitMini::TestThread( src )
 113                 , m_Map( src.m_Map )
 114             {}
 115
 116             Map_InsDel_Item_int&  getTest()
 117             {
 118                 return reinterpret_cast<Map_InsDel_Item_int&>( m_Pool.m_Test );
 119             }
 120
 121             virtual void init() { cds::threading::Manager::attachThread()   ; }
 122             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 123
 124             virtual void test()
 125             {
 126                 Map& rMap = m_Map;
 127
 128                 m_nInsertSuccess =
 129                     m_nInsertFailed = 0;
 130
 131                 size_t nGoalItem = getTest().c_nGoalItem;
 132                 size_t const nAttemptCount = getTest().c_nAttemptCount;
 133
 134                 for ( size_t nAttempt = 0; nAttempt < nAttemptCount; ) {
 135                     if ( nAttempt % 2  == 0 ) {
 136                         if ( rMap.insert( nGoalItem, nGoalItem )) {
 137                             ++m_nInsertSuccess;
 138                             ++nAttempt;
 139                         }
 140                         else
 141                             ++m_nInsertFailed;
 142                     }
 143                     else {
 144                         std::pair<bool, bool> updateResult = rMap.update( nGoalItem, update_func(), true );
 145                         if ( updateResult.second ) {
 146                             ++m_nInsertSuccess;
 147                             ++nAttempt;
 148                         }
 149                         else
 150                             ++m_nInsertFailed;
 151                     }
 152                 }
 153             }
 154         };
 155
 156         template <class Map>
 157         class Deleter: public CppUnitMini::TestThread
 158         {
 159             Map&     m_Map;
 160
 161             virtual Deleter *    clone()
 162             {
 163                 return new Deleter( *this );
 164             }
 165         public:
 166             size_t  m_nDeleteSuccess;
 167             size_t  m_nDeleteFailed;
 168
 169         public:
 170             Deleter( CppUnitMini::ThreadPool& pool, Map& rMap )
 171                 : CppUnitMini::TestThread( pool )
 172                 , m_Map( rMap )
 173             {}
 174             Deleter( Deleter& src )
 175                 : CppUnitMini::TestThread( src )
 176                 , m_Map( src.m_Map )
 177             {}
 178
 179             Map_InsDel_Item_int&  getTest()
 180             {
 181                 return reinterpret_cast<Map_InsDel_Item_int&>( m_Pool.m_Test );
 182             }
 183
 184             virtual void init() { cds::threading::Manager::attachThread()   ; }
 185             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 186
 187             virtual void test()
 188             {
 189                 Map& rMap = m_Map;
 190
 191                 m_nDeleteSuccess =
 192                     m_nDeleteFailed = 0;
 193
 194                 size_t nGoalItem = getTest().c_nGoalItem;
 195                 size_t const nAttemptCount = getTest().c_nAttemptCount;
 196                 for ( size_t nAttempt = 0; nAttempt < nAttemptCount; ) {
 197                     if ( rMap.erase( nGoalItem )) {
 198                         ++m_nDeleteSuccess;
 199                         ++nAttempt;
 200                     }
 201                     else
 202                         ++m_nDeleteFailed;
 203                 }
 204             }
 205         };
 206
 207     protected:
 208
 209         template <class Map>
 210         void do_test( Map& testMap )
 211         {
 212             typedef Inserter<Map>       InserterThread;
 213             typedef Deleter<Map>        DeleterThread;
 214             cds::OS::Timer    timer;
 215
 216             // Fill the map
 217             CPPUNIT_MSG( "  Fill map (" << c_nMapSize << " items)...");
 218             timer.reset();
 219             {
 220                 std::vector<key_type>   v;
 221                 v.reserve( c_nMapSize );
 222                 for ( size_t i = 0; i < c_nMapSize; ++i )
 223                     v.push_back( i );
 224                 shuffle( v.begin(), v.end() );
 225                 for ( size_t i = 0; i < v.size(); ++i ) {
 226                     CPPUNIT_ASSERT( testMap.insert( v[i], v[i] ));
 227                 }
 228             }
 229             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 230
 231             CPPUNIT_MSG( "  Insert/delete the key " << c_nGoalItem << " (" << c_nAttemptCount << " successful times)...");
 232             CppUnitMini::ThreadPool pool( *this );
 233             pool.add( new InserterThread( pool, testMap ), (c_nThreadCount + 1) / 2 );
 234             pool.add( new DeleterThread( pool, testMap ), (c_nThreadCount + 1) / 2 );
 235             pool.run();
 236             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 237
 238             size_t nInsertSuccess = 0;
 239             size_t nInsertFailed = 0;
 240             size_t nDeleteSuccess = 0;
 241             size_t nDeleteFailed = 0;
 242             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 243                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 244                 if ( pThread ) {
 245                     CPPUNIT_CHECK( pThread->m_nInsertSuccess == c_nAttemptCount );
 246                     nInsertSuccess += pThread->m_nInsertSuccess;
 247                     nInsertFailed += pThread->m_nInsertFailed;
 248                 }
 249                 else {
 250                     DeleterThread * p = static_cast<DeleterThread *>( *it );
 251                     CPPUNIT_CHECK( p->m_nDeleteSuccess == c_nAttemptCount );
 252                     nDeleteSuccess += p->m_nDeleteSuccess;
 253                     nDeleteFailed += p->m_nDeleteFailed;
 254                 }
 255             }
 256             CPPUNIT_CHECK( nInsertSuccess == nDeleteSuccess );
 257             size_t nGoalItem = c_nGoalItem;
 258             CPPUNIT_CHECK( testMap.contains( nGoalItem ));
 259
 260
 261             CPPUNIT_MSG( "    Totals: Ins fail=" << nInsertFailed << " Del fail=" << nDeleteFailed );
 262
 263             // Check if the map contains all items
 264             CPPUNIT_MSG( "    Check if the map contains all items" );
 265             timer.reset();
 266             for ( size_t i = 0; i < c_nMapSize; ++i ) {
 267                 CPPUNIT_CHECK_EX( testMap.contains( i ), "key " << i );
 268             }
 269             CPPUNIT_MSG( "    Duration=" << timer.duration() );
 270
 271             check_before_cleanup( testMap );
 272
 273             testMap.clear();
 274             additional_check( testMap );
 275             print_stat( testMap );
 276             additional_cleanup( testMap );
 277         }
 278
 279         template <class Map>
 280         void run_test()
 281         {
 282             if ( Map::c_bLoadFactorDepended ) {
 283                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 284                     CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
 285                     Map testMap( *this );
 286                     do_test( testMap );
 287                     if ( c_bPrintGCState )
 288                         print_gc_state();
 289                 }
 290             }
 291             else {
 292                 Map testMap( *this );
 293                 do_test<Map>( testMap );
 294                 if ( c_bPrintGCState )
 295                     print_gc_state();
 296             }
 297         }
 298
 299         void setUpParams( const CppUnitMini::TestCfg& cfg );
 300
 301 #   include "map2/map_defs.h"
 302         CDSUNIT_DECLARE_MichaelMap
 303         CDSUNIT_DECLARE_SplitList
 304         CDSUNIT_DECLARE_SkipListMap
 305         CDSUNIT_DECLARE_EllenBinTreeMap
 306         CDSUNIT_DECLARE_BronsonAVLTreeMap
 307         CDSUNIT_DECLARE_FeldmanHashMap_fixed
 308         CDSUNIT_DECLARE_FeldmanHashMap_city
 309         CDSUNIT_DECLARE_StripedMap
 310         CDSUNIT_DECLARE_RefinableMap
 311         CDSUNIT_DECLARE_CuckooMap
 312         // CDSUNIT_DECLARE_StdMap // very slow!!
 313
 314         CPPUNIT_TEST_SUITE(Map_InsDel_Item_int)
 315             CDSUNIT_TEST_MichaelMap
 316             CDSUNIT_TEST_SplitList
 317             CDSUNIT_TEST_SkipListMap
 318             CDSUNIT_TEST_EllenBinTreeMap
 319             CDSUNIT_TEST_BronsonAVLTreeMap
 320             CDSUNIT_TEST_FeldmanHashMap_fixed
 321             CDSUNIT_TEST_FeldmanHashMap_city
 322             //CDSUNIT_TEST_CuckooMap
 323             //CDSUNIT_TEST_StripedMap
 324             //CDSUNIT_TEST_RefinableMap
 325             // CDSUNIT_TEST_StdMap // very slow!!
 326         CPPUNIT_TEST_SUITE_END();
 327     };
 328 } // namespace map2