tests/unit/map2/map_insdel_item_int.h

   1 //$$CDS-header$$
   2
   3 #include "map2/map_types.h"
   4 #include "cppunit/thread.h"
   5
   6 #include <vector>
   7 #include <algorithm>    // random_shuffle
   8
   9 namespace map2 {
  10
  11 #   define TEST_MAP(X)         void X() { test<MapTypes<key_type, value_type>::X >()    ; }
  12 #   define TEST_MAP_NOLF(X)    void X() { test_nolf<MapTypes<key_type, value_type>::X >()    ; }
  13 #   define TEST_MAP_EXTRACT(X)  TEST_MAP(X)
  14 #   define TEST_MAP_NOLF_EXTRACT(X) TEST_MAP_NOLF(X)
  15
  16     class Map_InsDel_Item_int: public CppUnitMini::TestCase
  17     {
  18         static size_t  c_nMapSize;        // map size
  19         static size_t  c_nThreadCount;    // thread count
  20         static size_t  c_nGoalItem;
  21         static size_t  c_nAttemptCount;   // count of SUCCESS insert/delete for each thread
  22         static size_t  c_nMaxLoadFactor;  // maximum load factor
  23         static bool    c_bPrintGCState;
  24
  25         typedef CppUnitMini::TestCase Base;
  26         typedef size_t  key_type;
  27         typedef size_t  value_type;
  28
  29         template <class MAP>
  30         class Inserter: public CppUnitMini::TestThread
  31         {
  32             MAP&     m_Map;
  33
  34             virtual Inserter *    clone()
  35             {
  36                 return new Inserter( *this );
  37             }
  38
  39             struct ensure_func
  40             {
  41                 void operator()( bool bNew, std::pair<key_type const, value_type>& item )
  42                 {
  43                     if ( bNew )
  44                         item.second = item.first;
  45                 }
  46                 // for boost::container::flat_map
  47                 void operator()( bool bNew, std::pair<key_type, value_type>& item )
  48                 {
  49                     if ( bNew )
  50                         item.second = item.first;
  51                 }
  52
  53                 // for BronsonAVLTreeMap
  54                 void operator()( bool bNew, key_type key, value_type& val )
  55                 {
  56                     if ( bNew )
  57                         val = key;
  58                 }
  59             };
  60
  61         public:
  62             size_t  m_nInsertSuccess;
  63             size_t  m_nInsertFailed;
  64
  65         public:
  66             Inserter( CppUnitMini::ThreadPool& pool, MAP& rMap )
  67                 : CppUnitMini::TestThread( pool )
  68                 , m_Map( rMap )
  69             {}
  70             Inserter( Inserter& src )
  71                 : CppUnitMini::TestThread( src )
  72                 , m_Map( src.m_Map )
  73             {}
  74
  75             Map_InsDel_Item_int&  getTest()
  76             {
  77                 return reinterpret_cast<Map_InsDel_Item_int&>( m_Pool.m_Test );
  78             }
  79
  80             virtual void init() { cds::threading::Manager::attachThread()   ; }
  81             virtual void fini() { cds::threading::Manager::detachThread()   ; }
  82
  83             virtual void test()
  84             {
  85                 MAP& rMap = m_Map;
  86
  87                 m_nInsertSuccess =
  88                     m_nInsertFailed = 0;
  89
  90                 size_t nGoalItem = c_nGoalItem;
  91                 for ( size_t nAttempt = 0; nAttempt < c_nAttemptCount; ) {
  92                     if ( nAttempt % 2  == 0 ) {
  93                         if ( rMap.insert( nGoalItem, nGoalItem )) {
  94                             ++m_nInsertSuccess;
  95                             ++nAttempt;
  96                         }
  97                         else
  98                             ++m_nInsertFailed;
  99                     }
 100                     else {
 101                         std::pair<bool, bool> ensureResult = rMap.ensure( nGoalItem, ensure_func() );
 102                         if ( ensureResult.second ) {
 103                             ++m_nInsertSuccess;
 104                             ++nAttempt;
 105                         }
 106                         else
 107                             ++m_nInsertFailed;
 108                     }
 109                 }
 110             }
 111         };
 112
 113         template <class MAP>
 114         class Deleter: public CppUnitMini::TestThread
 115         {
 116             MAP&     m_Map;
 117
 118             virtual Deleter *    clone()
 119             {
 120                 return new Deleter( *this );
 121             }
 122         public:
 123             size_t  m_nDeleteSuccess;
 124             size_t  m_nDeleteFailed;
 125
 126         public:
 127             Deleter( CppUnitMini::ThreadPool& pool, MAP& rMap )
 128                 : CppUnitMini::TestThread( pool )
 129                 , m_Map( rMap )
 130             {}
 131             Deleter( Deleter& src )
 132                 : CppUnitMini::TestThread( src )
 133                 , m_Map( src.m_Map )
 134             {}
 135
 136             Map_InsDel_Item_int&  getTest()
 137             {
 138                 return reinterpret_cast<Map_InsDel_Item_int&>( m_Pool.m_Test );
 139             }
 140
 141             virtual void init() { cds::threading::Manager::attachThread()   ; }
 142             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 143
 144             virtual void test()
 145             {
 146                 MAP& rMap = m_Map;
 147
 148                 m_nDeleteSuccess =
 149                     m_nDeleteFailed = 0;
 150
 151                 size_t nGoalItem = c_nGoalItem;
 152                 for ( size_t nAttempt = 0; nAttempt < c_nAttemptCount; ) {
 153                     if ( rMap.erase( nGoalItem )) {
 154                         ++m_nDeleteSuccess;
 155                         ++nAttempt;
 156                     }
 157                     else
 158                         ++m_nDeleteFailed;
 159                 }
 160             }
 161         };
 162
 163     protected:
 164
 165         template <class MAP>
 166         void do_test( MAP& testMap )
 167         {
 168             typedef Inserter<MAP>       InserterThread;
 169             typedef Deleter<MAP>        DeleterThread;
 170             cds::OS::Timer    timer;
 171
 172             // Fill the map
 173             CPPUNIT_MSG( "  Fill map (" << c_nMapSize << " items)...");
 174             timer.reset();
 175             {
 176                 std::vector<key_type>   v;
 177                 v.reserve( c_nMapSize );
 178                 for ( size_t i = 0; i < c_nMapSize; ++i )
 179                     v.push_back( i );
 180                 std::random_shuffle( v.begin(), v.end() );
 181                 for ( size_t i = 0; i < v.size(); ++i ) {
 182                     CPPUNIT_ASSERT( testMap.insert( v[i], v[i] ));
 183                 }
 184             }
 185             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 186
 187             CPPUNIT_MSG( "  Insert/delete the key " << c_nGoalItem << " (" << c_nAttemptCount << " successful times)...");
 188             CppUnitMini::ThreadPool pool( *this );
 189             pool.add( new InserterThread( pool, testMap ), (c_nThreadCount + 1) / 2 );
 190             pool.add( new DeleterThread( pool, testMap ), (c_nThreadCount + 1) / 2 );
 191             pool.run();
 192             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 193
 194             size_t nInsertSuccess = 0;
 195             size_t nInsertFailed = 0;
 196             size_t nDeleteSuccess = 0;
 197             size_t nDeleteFailed = 0;
 198             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 199                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 200                 if ( pThread ) {
 201                     CPPUNIT_CHECK( pThread->m_nInsertSuccess == c_nAttemptCount );
 202                     nInsertSuccess += pThread->m_nInsertSuccess;
 203                     nInsertFailed += pThread->m_nInsertFailed;
 204                 }
 205                 else {
 206                     DeleterThread * p = static_cast<DeleterThread *>( *it );
 207                     CPPUNIT_CHECK( p->m_nDeleteSuccess == c_nAttemptCount );
 208                     nDeleteSuccess += p->m_nDeleteSuccess;
 209                     nDeleteFailed += p->m_nDeleteFailed;
 210                 }
 211             }
 212             CPPUNIT_CHECK( nInsertSuccess == nDeleteSuccess );
 213             size_t nGoalItem = c_nGoalItem;
 214             CPPUNIT_CHECK( testMap.find( nGoalItem ));
 215
 216
 217             CPPUNIT_MSG( "    Totals: Ins fail=" << nInsertFailed << " Del fail=" << nDeleteFailed );
 218
 219             // Check if the map contains all items
 220             CPPUNIT_MSG( "    Check if the map contains all items" );
 221             timer.reset();
 222             for ( size_t i = 0; i < c_nMapSize; ++i ) {
 223                 CPPUNIT_CHECK_EX( testMap.find( i ), "key " << i );
 224             }
 225             CPPUNIT_MSG( "    Duration=" << timer.duration() );
 226
 227             check_before_cleanup( testMap );
 228
 229             testMap.clear();
 230             additional_check( testMap );
 231             print_stat( testMap );
 232             additional_cleanup( testMap );
 233         }
 234
 235         template <class MAP>
 236         void test()
 237         {
 238             for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
 239                 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
 240                 MAP testMap( c_nMapSize, nLoadFactor );
 241                 do_test( testMap );
 242                 if ( c_bPrintGCState )
 243                     print_gc_state();
 244             }
 245         }
 246
 247         template <class MAP>
 248         void test_nolf()
 249         {
 250             MAP testMap;
 251             do_test<MAP>( testMap );
 252             if ( c_bPrintGCState )
 253                 print_gc_state();
 254         }
 255
 256         void setUpParams( const CppUnitMini::TestCfg& cfg );
 257
 258         void run_MichaelMap(const char *in_name, bool invert = false);
 259         void run_SplitList(const char *in_name, bool invert = false);
 260         void run_SkipListMap(const char *in_name, bool invert = false);
 261         void run_StripedMap(const char *in_name, bool invert = false);
 262         void run_RefinableMap(const char *in_name, bool invert = false);
 263         void run_CuckooMap(const char *in_name, bool invert = false);
 264         void run_EllenBinTreeMap(const char *in_name, bool invert = false);
 265         void run_BronsonAVLTreeMap(const char *in_name, bool invert = false);
 266
 267         virtual void myRun(const char *in_name, bool invert = false);
 268
 269
 270 #   include "map2/map_defs.h"
 271         CDSUNIT_DECLARE_MichaelMap
 272         CDSUNIT_DECLARE_SplitList
 273         CDSUNIT_DECLARE_SkipListMap
 274         CDSUNIT_DECLARE_EllenBinTreeMap
 275         CDSUNIT_DECLARE_BronsonAVLTreeMap
 276         CDSUNIT_DECLARE_StripedMap
 277         CDSUNIT_DECLARE_RefinableMap
 278         CDSUNIT_DECLARE_CuckooMap
 279         //CDSUNIT_DECLARE_StdMap    // very slow!
 280     };
 281 } // namespace map2