tests/unit/map2/map_insdel_item_int.h

   1 //$$CDS-header$$
   2
   3 #include "map2/map_type.h"
   4 #include "cppunit/thread.h"
   5
   6 #include <vector>
   7
   8 namespace map2 {
   9
  10 #define TEST_CASE(TAG, X)  void X();
  11
  12     class Map_InsDel_Item_int: public CppUnitMini::TestCase
  13     {
  14     public:
  15         size_t  c_nMapSize = 1000000;       // map size
  16         size_t  c_nThreadCount = 4;         // thread count
  17         size_t  c_nAttemptCount = 100000;   // count of SUCCESS insert/delete for each thread
  18         size_t  c_nMaxLoadFactor = 8;       // maximum load factor
  19         bool    c_bPrintGCState = true;
  20
  21         size_t c_nCuckooInitialSize = 1024; // initial size for CuckooMap
  22         size_t c_nCuckooProbesetSize = 16;  // CuckooMap probeset size (only for list-based probeset)
  23         size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
  24
  25         size_t c_nMultiLevelMap_HeadBits = 10;
  26         size_t c_nMultiLevelMap_ArrayBits = 4;
  27
  28         size_t  c_nGoalItem;
  29         size_t  c_nLoadFactor = 2;  // current load factor
  30
  31     private:
  32         typedef size_t  key_type;
  33         typedef size_t  value_type;
  34
  35         template <class Map>
  36         class Inserter: public CppUnitMini::TestThread
  37         {
  38             Map&     m_Map;
  39
  40             virtual Inserter *    clone()
  41             {
  42                 return new Inserter( *this );
  43             }
  44
  45             struct update_func
  46             {
  47                 void operator()( bool bNew, std::pair<key_type const, value_type>& item )
  48                 {
  49                     if ( bNew )
  50                         item.second = item.first;
  51                 }
  52                 // for boost::container::flat_map
  53                 void operator()( bool bNew, std::pair<key_type, value_type>& item )
  54                 {
  55                     if ( bNew )
  56                         item.second = item.first;
  57                 }
  58
  59                 // for BronsonAVLTreeMap
  60                 void operator()( bool bNew, key_type key, value_type& val )
  61                 {
  62                     if ( bNew )
  63                         val = key;
  64                 }
  65
  66                 // for MultiLevelHashMap
  67                 void operator()( std::pair<key_type const, value_type>& item, std::pair<key_type const, value_type> * pOld )
  68                 {
  69                     if ( !pOld )
  70                         item.second = item.first;
  71                 }
  72             };
  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_int&  getTest()
  89             {
  90                 return reinterpret_cast<Map_InsDel_Item_int&>( 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                 size_t const nAttemptCount = getTest().c_nAttemptCount;
 105
 106                 for ( size_t nAttempt = 0; nAttempt < nAttemptCount; ) {
 107                     if ( nAttempt % 2  == 0 ) {
 108                         if ( rMap.insert( nGoalItem, nGoalItem )) {
 109                             ++m_nInsertSuccess;
 110                             ++nAttempt;
 111                         }
 112                         else
 113                             ++m_nInsertFailed;
 114                     }
 115                     else {
 116                         std::pair<bool, bool> updateResult = rMap.update( nGoalItem, update_func(), true );
 117                         if ( updateResult.second ) {
 118                             ++m_nInsertSuccess;
 119                             ++nAttempt;
 120                         }
 121                         else
 122                             ++m_nInsertFailed;
 123                     }
 124                 }
 125             }
 126         };
 127
 128         template <class Map>
 129         class Deleter: public CppUnitMini::TestThread
 130         {
 131             Map&     m_Map;
 132
 133             virtual Deleter *    clone()
 134             {
 135                 return new Deleter( *this );
 136             }
 137         public:
 138             size_t  m_nDeleteSuccess;
 139             size_t  m_nDeleteFailed;
 140
 141         public:
 142             Deleter( CppUnitMini::ThreadPool& pool, Map& rMap )
 143                 : CppUnitMini::TestThread( pool )
 144                 , m_Map( rMap )
 145             {}
 146             Deleter( Deleter& src )
 147                 : CppUnitMini::TestThread( src )
 148                 , m_Map( src.m_Map )
 149             {}
 150
 151             Map_InsDel_Item_int&  getTest()
 152             {
 153                 return reinterpret_cast<Map_InsDel_Item_int&>( m_Pool.m_Test );
 154             }
 155
 156             virtual void init() { cds::threading::Manager::attachThread()   ; }
 157             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 158
 159             virtual void test()
 160             {
 161                 Map& rMap = m_Map;
 162
 163                 m_nDeleteSuccess =
 164                     m_nDeleteFailed = 0;
 165
 166                 size_t nGoalItem = getTest().c_nGoalItem;
 167                 size_t const nAttemptCount = getTest().c_nAttemptCount;
 168                 for ( size_t nAttempt = 0; nAttempt < nAttemptCount; ) {
 169                     if ( rMap.erase( nGoalItem )) {
 170                         ++m_nDeleteSuccess;
 171                         ++nAttempt;
 172                     }
 173                     else
 174                         ++m_nDeleteFailed;
 175                 }
 176             }
 177         };
 178
 179     protected:
 180
 181         template <class Map>
 182         void do_test( Map& testMap )
 183         {
 184             typedef Inserter<Map>       InserterThread;
 185             typedef Deleter<Map>        DeleterThread;
 186             cds::OS::Timer    timer;
 187
 188             // Fill the map
 189             CPPUNIT_MSG( "  Fill map (" << c_nMapSize << " items)...");
 190             timer.reset();
 191             {
 192                 std::vector<key_type>   v;
 193                 v.reserve( c_nMapSize );
 194                 for ( size_t i = 0; i < c_nMapSize; ++i )
 195                     v.push_back( i );
 196                 shuffle( v.begin(), v.end() );
 197                 for ( size_t i = 0; i < v.size(); ++i ) {
 198                     CPPUNIT_ASSERT( testMap.insert( v[i], v[i] ));
 199                 }
 200             }
 201             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 202
 203             CPPUNIT_MSG( "  Insert/delete the key " << c_nGoalItem << " (" << c_nAttemptCount << " successful times)...");
 204             CppUnitMini::ThreadPool pool( *this );
 205             pool.add( new InserterThread( pool, testMap ), (c_nThreadCount + 1) / 2 );
 206             pool.add( new DeleterThread( pool, testMap ), (c_nThreadCount + 1) / 2 );
 207             pool.run();
 208             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 209
 210             size_t nInsertSuccess = 0;
 211             size_t nInsertFailed = 0;
 212             size_t nDeleteSuccess = 0;
 213             size_t nDeleteFailed = 0;
 214             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 215                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 216                 if ( pThread ) {
 217                     CPPUNIT_CHECK( pThread->m_nInsertSuccess == c_nAttemptCount );
 218                     nInsertSuccess += pThread->m_nInsertSuccess;
 219                     nInsertFailed += pThread->m_nInsertFailed;
 220                 }
 221                 else {
 222                     DeleterThread * p = static_cast<DeleterThread *>( *it );
 223                     CPPUNIT_CHECK( p->m_nDeleteSuccess == c_nAttemptCount );
 224                     nDeleteSuccess += p->m_nDeleteSuccess;
 225                     nDeleteFailed += p->m_nDeleteFailed;
 226                 }
 227             }
 228             CPPUNIT_CHECK( nInsertSuccess == nDeleteSuccess );
 229             size_t nGoalItem = c_nGoalItem;
 230             CPPUNIT_CHECK( testMap.contains( nGoalItem ));
 231
 232
 233             CPPUNIT_MSG( "    Totals: Ins fail=" << nInsertFailed << " Del fail=" << nDeleteFailed );
 234
 235             // Check if the map contains all items
 236             CPPUNIT_MSG( "    Check if the map contains all items" );
 237             timer.reset();
 238             for ( size_t i = 0; i < c_nMapSize; ++i ) {
 239                 CPPUNIT_CHECK_EX( testMap.contains( i ), "key " << i );
 240             }
 241             CPPUNIT_MSG( "    Duration=" << timer.duration() );
 242
 243             check_before_cleanup( testMap );
 244
 245             testMap.clear();
 246             additional_check( testMap );
 247             print_stat( testMap );
 248             additional_cleanup( testMap );
 249         }
 250
 251         template <class Map>
 252         void run_test()
 253         {
 254             if ( Map::c_bLoadFactorDepended ) {
 255                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 256                     CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
 257                     Map testMap( *this );
 258                     do_test( testMap );
 259                     if ( c_bPrintGCState )
 260                         print_gc_state();
 261                 }
 262             }
 263             else {
 264                 Map testMap( *this );
 265                 do_test<Map>( testMap );
 266                 if ( c_bPrintGCState )
 267                     print_gc_state();
 268             }
 269         }
 270
 271         void setUpParams( const CppUnitMini::TestCfg& cfg );
 272
 273 #   include "map2/map_defs.h"
 274         CDSUNIT_DECLARE_MichaelMap
 275         CDSUNIT_DECLARE_SplitList
 276         CDSUNIT_DECLARE_SkipListMap
 277         CDSUNIT_DECLARE_EllenBinTreeMap
 278         CDSUNIT_DECLARE_BronsonAVLTreeMap
 279         CDSUNIT_DECLARE_MultiLevelHashMap_fixed
 280         CDSUNIT_DECLARE_MultiLevelHashMap_city
 281         CDSUNIT_DECLARE_StripedMap
 282         CDSUNIT_DECLARE_RefinableMap
 283         CDSUNIT_DECLARE_CuckooMap
 284         // CDSUNIT_DECLARE_StdMap // very slow!!
 285
 286         CPPUNIT_TEST_SUITE(Map_InsDel_Item_int)
 287             CDSUNIT_TEST_MichaelMap
 288             CDSUNIT_TEST_SplitList
 289             CDSUNIT_TEST_SkipListMap
 290             CDSUNIT_TEST_EllenBinTreeMap
 291             CDSUNIT_TEST_BronsonAVLTreeMap
 292             CDSUNIT_TEST_MultiLevelHashMap_fixed
 293             CDSUNIT_TEST_MultiLevelHashMap_city
 294             CDSUNIT_TEST_CuckooMap
 295             CDSUNIT_TEST_StripedMap
 296             CDSUNIT_TEST_RefinableMap
 297             // CDSUNIT_TEST_StdMap // very slow!!
 298         CPPUNIT_TEST_SUITE_END();
 299     };
 300 } // namespace map2