tests/unit/map2/map_insdel_item_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_Item_string: 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 std::string  key_type;
  61         typedef size_t  value_type;
  62
  63         const std::vector<std::string> *  m_parrString;
  64
  65         template <class Map>
  66         class Inserter: public CppUnitMini::TestThread
  67         {
  68             Map&     m_Map;
  69
  70             virtual Inserter *    clone()
  71             {
  72                 return new Inserter( *this );
  73             }
  74         public:
  75             size_t  m_nInsertSuccess;
  76             size_t  m_nInsertFailed;
  77
  78         public:
  79             Inserter( CppUnitMini::ThreadPool& pool, Map& rMap )
  80                 : CppUnitMini::TestThread( pool )
  81                 , m_Map( rMap )
  82             {}
  83             Inserter( Inserter& src )
  84                 : CppUnitMini::TestThread( src )
  85                 , m_Map( src.m_Map )
  86             {}
  87
  88             Map_InsDel_Item_string&  getTest()
  89             {
  90                 return reinterpret_cast<Map_InsDel_Item_string&>( m_Pool.m_Test );
  91             }
  92
  93             virtual void init() { cds::threading::Manager::attachThread()   ; }
  94             virtual void fini() { cds::threading::Manager::detachThread()   ; }
  95
  96             virtual void test()
  97             {
  98                 Map& rMap = m_Map;
  99
 100                 m_nInsertSuccess =
 101                     m_nInsertFailed = 0;
 102
 103                 size_t nGoalItem = getTest().c_nGoalItem;
 104                 std::string strGoal = (*getTest().m_parrString)[nGoalItem];
 105                 size_t const nAttemptCount = getTest().c_nAttemptCount;
 106
 107                 for ( size_t nAttempt = 0; nAttempt < nAttemptCount; ) {
 108                     if ( rMap.insert( strGoal, nGoalItem )) {
 109                         ++m_nInsertSuccess;
 110                         ++nAttempt;
 111                     }
 112                     else
 113                         ++m_nInsertFailed;
 114                 }
 115             }
 116         };
 117
 118         template <class Map>
 119         class Deleter: public CppUnitMini::TestThread
 120         {
 121             Map&     m_Map;
 122
 123             struct erase_cleaner {
 124                 void operator ()(std::pair<typename Map::key_type const, typename Map::mapped_type>& val )
 125                 {
 126                     val.second = 0;
 127                 }
 128                 // for boost::container::flat_map
 129                 void operator ()(std::pair< typename std::remove_const< typename Map::key_type >::type, typename Map::mapped_type>& val )
 130                 {
 131                     val.second = 0;
 132                 }
 133                 // for BronsonAVLTreeMap
 134                 void operator()( typename Map::key_type const& /*key*/, typename Map::mapped_type& val )
 135                 {
 136                     val = 0;
 137                 }
 138             };
 139
 140             virtual Deleter *    clone()
 141             {
 142                 return new Deleter( *this );
 143             }
 144         public:
 145             size_t  m_nDeleteSuccess;
 146             size_t  m_nDeleteFailed;
 147
 148         public:
 149             Deleter( CppUnitMini::ThreadPool& pool, Map& rMap )
 150                 : CppUnitMini::TestThread( pool )
 151                 , m_Map( rMap )
 152             {}
 153             Deleter( Deleter& src )
 154                 : CppUnitMini::TestThread( src )
 155                 , m_Map( src.m_Map )
 156             {}
 157
 158             Map_InsDel_Item_string&  getTest()
 159             {
 160                 return reinterpret_cast<Map_InsDel_Item_string&>( m_Pool.m_Test );
 161             }
 162
 163             virtual void init() { cds::threading::Manager::attachThread()   ; }
 164             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 165
 166             virtual void test()
 167             {
 168                 Map& rMap = m_Map;
 169
 170                 m_nDeleteSuccess =
 171                     m_nDeleteFailed = 0;
 172
 173                 size_t nGoalItem = getTest().c_nGoalItem;
 174                 std::string strGoal = (*getTest().m_parrString)[nGoalItem];
 175                 size_t const nAttemptCount = getTest().c_nAttemptCount;
 176
 177                 for ( size_t nAttempt = 0; nAttempt < nAttemptCount; ) {
 178                     if ( rMap.erase( strGoal, erase_cleaner() )) {
 179                         ++m_nDeleteSuccess;
 180                         ++nAttempt;
 181                     }
 182                     else
 183                         ++m_nDeleteFailed;
 184                 }
 185             }
 186         };
 187
 188     protected:
 189
 190         template <class Map>
 191         void do_test( Map& testMap )
 192         {
 193             typedef Inserter<Map>       InserterThread;
 194             typedef Deleter<Map>        DeleterThread;
 195             cds::OS::Timer    timer;
 196
 197             // Fill the map
 198             CPPUNIT_MSG( "  Fill map (" << c_nMapSize << " items)...");
 199             timer.reset();
 200             for ( size_t i = 0; i < c_nMapSize; ++i ) {
 201                 CPPUNIT_ASSERT_EX( testMap.insert( (*m_parrString)[i], i ), i );
 202             }
 203             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 204
 205             CPPUNIT_MSG( "  Insert/delete the key " << c_nGoalItem << " (" << c_nAttemptCount << " successful times)...");
 206             CppUnitMini::ThreadPool pool( *this );
 207             pool.add( new InserterThread( pool, testMap ), (c_nThreadCount + 1) / 2 );
 208             pool.add( new DeleterThread( pool, testMap ), (c_nThreadCount + 1) / 2 );
 209             pool.run();
 210             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 211
 212             size_t nInsertSuccess = 0;
 213             size_t nInsertFailed = 0;
 214             size_t nDeleteSuccess = 0;
 215             size_t nDeleteFailed = 0;
 216             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 217                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 218                 if ( pThread ) {
 219                     CPPUNIT_CHECK( pThread->m_nInsertSuccess == c_nAttemptCount );
 220                     nInsertSuccess += pThread->m_nInsertSuccess;
 221                     nInsertFailed += pThread->m_nInsertFailed;
 222                 }
 223                 else {
 224                     DeleterThread * p = static_cast<DeleterThread *>( *it );
 225                     CPPUNIT_CHECK( p->m_nDeleteSuccess == c_nAttemptCount );
 226                     nDeleteSuccess += p->m_nDeleteSuccess;
 227                     nDeleteFailed += p->m_nDeleteFailed;
 228                 }
 229             }
 230             CPPUNIT_CHECK_EX( nInsertSuccess == nDeleteSuccess, "nInsertSuccess=" << nInsertSuccess << ", nDeleteSuccess=" << nDeleteSuccess );
 231             CPPUNIT_MSG( "    Totals: Ins fail=" << nInsertFailed << " Del fail=" << nDeleteFailed );
 232
 233             // Check if the map contains all items
 234             CPPUNIT_MSG( "    Check if the map contains all items" );
 235             timer.reset();
 236             for ( size_t i = 0; i < c_nMapSize; ++i ) {
 237                 CPPUNIT_CHECK_EX( testMap.contains( (*m_parrString)[i] ), "Key \"" << (*m_parrString)[i] << "\" not found" );
 238             }
 239             CPPUNIT_MSG( "    Duration=" << timer.duration() );
 240
 241             check_before_cleanup( testMap );
 242
 243             testMap.clear();
 244             additional_check( testMap );
 245             print_stat( testMap );
 246             additional_cleanup( testMap );
 247         }
 248
 249         template <class Map>
 250         void run_test()
 251         {
 252             m_parrString = &CppUnitMini::TestCase::getTestStrings();
 253             if ( c_nMapSize > m_parrString->size() )
 254                 c_nMapSize = m_parrString->size();
 255             if ( c_nGoalItem > m_parrString->size() )
 256                 c_nGoalItem = m_parrString->size() / 2;
 257
 258             CPPUNIT_MSG( "Thread count= " << c_nThreadCount
 259                 << " pass count=" << c_nAttemptCount
 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 // very slow!!
 293
 294         CPPUNIT_TEST_SUITE(Map_InsDel_Item_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 // very slow!!
 305         CPPUNIT_TEST_SUITE_END();
 306
 307     };
 308 } // namespace map2