tests/unit/map2/map_insdel_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_int: 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 size_t  key_type;
  62         typedef size_t  value_type;
  63
  64         typedef std::vector<key_type>   key_array;
  65         key_array                       m_arrValues;
  66
  67         template <class Map>
  68         class Inserter: public CppUnitMini::TestThread
  69         {
  70             Map&     m_Map;
  71
  72             virtual Inserter *    clone()
  73             {
  74                 return new Inserter( *this );
  75             }
  76         public:
  77             size_t  m_nInsertSuccess;
  78             size_t  m_nInsertFailed;
  79
  80         public:
  81             Inserter( CppUnitMini::ThreadPool& pool, Map& rMap )
  82                 : CppUnitMini::TestThread( pool )
  83                 , m_Map( rMap )
  84             {}
  85             Inserter( Inserter& src )
  86                 : CppUnitMini::TestThread( src )
  87                 , m_Map( src.m_Map )
  88             {}
  89
  90             Map_InsDel_int&  getTest()
  91             {
  92                 return reinterpret_cast<Map_InsDel_int&>( m_Pool.m_Test );
  93             }
  94
  95             virtual void init() { cds::threading::Manager::attachThread()   ; }
  96             virtual void fini() { cds::threading::Manager::detachThread()   ; }
  97
  98             virtual void test()
  99             {
 100                 Map& rMap = m_Map;
 101
 102                 m_nInsertSuccess =
 103                     m_nInsertFailed = 0;
 104                 key_array const& arr = getTest().m_arrValues;
 105
 106                 size_t const nPassCount = getTest().c_nThreadPassCount;
 107
 108                 if ( m_nThreadNo & 1 ) {
 109                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 110                         for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) {
 111                             if ( rMap.insert( *it, *it * 8 ) )
 112                                 ++m_nInsertSuccess;
 113                             else
 114                                 ++m_nInsertFailed;
 115                         }
 116                     }
 117                 }
 118                 else {
 119                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 120                         for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) {
 121                             if ( rMap.insert( *it, *it * 8 ) )
 122                                 ++m_nInsertSuccess;
 123                             else
 124                                 ++m_nInsertFailed;
 125                         }
 126                     }
 127                 }
 128             }
 129         };
 130
 131         template <class Map>
 132         class Deleter: public CppUnitMini::TestThread
 133         {
 134             Map&     m_Map;
 135
 136             virtual Deleter *    clone()
 137             {
 138                 return new Deleter( *this );
 139             }
 140         public:
 141             size_t  m_nDeleteSuccess;
 142             size_t  m_nDeleteFailed;
 143
 144         public:
 145             Deleter( CppUnitMini::ThreadPool& pool, Map& rMap )
 146                 : CppUnitMini::TestThread( pool )
 147                 , m_Map( rMap )
 148             {}
 149             Deleter( Deleter& src )
 150                 : CppUnitMini::TestThread( src )
 151                 , m_Map( src.m_Map )
 152             {}
 153
 154             Map_InsDel_int&  getTest()
 155             {
 156                 return reinterpret_cast<Map_InsDel_int&>( m_Pool.m_Test );
 157             }
 158
 159             virtual void init() { cds::threading::Manager::attachThread()   ; }
 160             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 161
 162             virtual void test()
 163             {
 164                 Map& rMap = m_Map;
 165
 166                 m_nDeleteSuccess =
 167                     m_nDeleteFailed = 0;
 168                 key_array const& arr = getTest().m_arrValues;
 169
 170                 size_t const nPassCount = getTest().c_nThreadPassCount;
 171
 172                 if ( m_nThreadNo & 1 ) {
 173                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 174                         for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) {
 175                             if ( rMap.erase( *it ) )
 176                                 ++m_nDeleteSuccess;
 177                             else
 178                                 ++m_nDeleteFailed;
 179                         }
 180                     }
 181                 }
 182                 else {
 183                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 184                         for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) {
 185                             if ( rMap.erase( *it ) )
 186                                 ++m_nDeleteSuccess;
 187                             else
 188                                 ++m_nDeleteFailed;
 189                         }
 190                     }
 191                 }
 192             }
 193         };
 194
 195     protected:
 196         template <class Map>
 197         void do_test( Map& testMap )
 198         {
 199             typedef Inserter<Map>       InserterThread;
 200             typedef Deleter<Map>        DeleterThread;
 201             cds::OS::Timer    timer;
 202
 203             CppUnitMini::ThreadPool pool( *this );
 204             pool.add( new InserterThread( pool, testMap ), c_nInsertThreadCount );
 205             pool.add( new DeleterThread( pool, testMap ), c_nDeleteThreadCount );
 206             pool.run();
 207             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 208
 209             size_t nInsertSuccess = 0;
 210             size_t nInsertFailed = 0;
 211             size_t nDeleteSuccess = 0;
 212             size_t nDeleteFailed = 0;
 213             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 214                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 215                 if ( pThread ) {
 216                     nInsertSuccess += pThread->m_nInsertSuccess;
 217                     nInsertFailed += pThread->m_nInsertFailed;
 218                 }
 219                 else {
 220                     DeleterThread * p = static_cast<DeleterThread *>( *it );
 221                     nDeleteSuccess += p->m_nDeleteSuccess;
 222                     nDeleteFailed += p->m_nDeleteFailed;
 223                 }
 224             }
 225
 226             CPPUNIT_MSG( "    Totals: Ins succ=" << nInsertSuccess
 227                 << " Del succ=" << nDeleteSuccess << "\n"
 228                 << "          : Ins fail=" << nInsertFailed
 229                 << " Del fail=" << nDeleteFailed
 230                 << " Map size=" << testMap.size()
 231                 );
 232
 233             check_before_cleanup( testMap );
 234
 235             CPPUNIT_MSG( "  Clear map (single-threaded)..." );
 236             timer.reset();
 237             for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) {
 238                 testMap.erase( nItem );
 239             }
 240             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 241             CPPUNIT_CHECK( testMap.empty());
 242             CPPUNIT_CHECK_EX( testMap.size() == 0, "size() == " << testMap.size() );
 243
 244             additional_check( testMap );
 245             print_stat( testMap );
 246             additional_cleanup( testMap );
 247         }
 248
 249         template <class Map>
 250         void run_test()
 251         {
 252             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 253                 << " delete=" << c_nDeleteThreadCount
 254                 << " pass count=" << c_nThreadPassCount
 255                 << " map size=" << c_nMapSize
 256                 );
 257
 258             if ( Map::c_bLoadFactorDepended ) {
 259                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 260                     CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
 261                     Map  testMap( *this );
 262                     do_test( testMap );
 263                     if ( c_bPrintGCState )
 264                         print_gc_state();
 265                 }
 266             }
 267             else {
 268                 Map testMap( *this );
 269                 do_test( testMap );
 270                 if ( c_bPrintGCState )
 271                     print_gc_state();
 272             }
 273         }
 274
 275         void setUpParams( const CppUnitMini::TestCfg& cfg );
 276
 277 #   include "map2/map_defs.h"
 278         CDSUNIT_DECLARE_MichaelMap
 279         CDSUNIT_DECLARE_SplitList
 280         CDSUNIT_DECLARE_SkipListMap
 281         CDSUNIT_DECLARE_EllenBinTreeMap
 282         CDSUNIT_DECLARE_BronsonAVLTreeMap
 283         CDSUNIT_DECLARE_FeldmanHashMap_fixed
 284         CDSUNIT_DECLARE_FeldmanHashMap_city
 285         CDSUNIT_DECLARE_StripedMap
 286         CDSUNIT_DECLARE_RefinableMap
 287         CDSUNIT_DECLARE_CuckooMap
 288         CDSUNIT_DECLARE_StdMap
 289
 290         CPPUNIT_TEST_SUITE(Map_InsDel_int)
 291             CDSUNIT_TEST_MichaelMap
 292             CDSUNIT_TEST_SplitList
 293             CDSUNIT_TEST_SkipListMap
 294             CDSUNIT_TEST_EllenBinTreeMap
 295             CDSUNIT_TEST_BronsonAVLTreeMap
 296             CDSUNIT_TEST_FeldmanHashMap_fixed
 297             CDSUNIT_TEST_FeldmanHashMap_city
 298             CDSUNIT_TEST_CuckooMap
 299             CDSUNIT_TEST_StripedMap
 300             CDSUNIT_TEST_RefinableMap
 301             CDSUNIT_TEST_StdMap
 302         CPPUNIT_TEST_SUITE_END();
 303     };
 304 } // namespace map2