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