tests/unit/map2/map_find_string.cpp

   1 //$$CDS-header$$
   2
   3 #include "map2/map_types.h"
   4 #include "cppunit/thread.h"
   5
   6 #include <vector>
   7
   8 namespace map2 {
   9
  10 #   define TEST_MAP(X)         void X() { test<MapTypes<key_type, value_type>::X >()    ; }
  11 #   define TEST_MAP_NOLF(X)    void X() { test_nolf<MapTypes<key_type, value_type>::X >()    ; }
  12 #   define TEST_MAP_EXTRACT(X)  TEST_MAP(X)
  13 #   define TEST_MAP_NOLF_EXTRACT(X) TEST_MAP_NOLF(X)
  14
  15     namespace {
  16         static size_t  c_nThreadCount = 8      ;  // thread count
  17         static size_t  c_nMapSize = 20000000   ;  // map size (count of searching item)
  18         static size_t  c_nPercentExists = 50   ;  // percent of existing keys in searching sequence
  19         static size_t  c_nPassCount = 2;
  20         static size_t  c_nMaxLoadFactor = 8    ;  // maximum load factor
  21         static bool    c_bPrintGCState = true;
  22     }
  23
  24     class Map_find_string: public CppUnitMini::TestCase
  25     {
  26         typedef std::string  key_type;
  27         struct value_type {
  28             std::string const * pKey;
  29             bool        bExists ;   // true - key in map, false - key not in map
  30         };
  31
  32         typedef std::vector<value_type> ValueVector;
  33         ValueVector             m_Arr;
  34         size_t                  m_nRealMapSize;
  35         bool                    m_bSeqInit;
  36
  37         template <typename Iterator, typename Map>
  38         static bool check_result( Iterator const& it, Map const& map )
  39         {
  40             return it != map.end();
  41         }
  42         template <typename Map>
  43         static bool check_result( bool b, Map const& )
  44         {
  45             return b;
  46         }
  47
  48         template <class MAP>
  49         class TestThread: public CppUnitMini::TestThread
  50         {
  51             MAP&     m_Map;
  52
  53             virtual TestThread *    clone()
  54             {
  55                 return new TestThread( *this );
  56             }
  57         public:
  58             struct Stat {
  59                 size_t      nSuccess;
  60                 size_t      nFailed;
  61
  62                 Stat()
  63                     : nSuccess(0)
  64                     , nFailed(0)
  65                 {}
  66             };
  67
  68             Stat    m_KeyExists;
  69             Stat    m_KeyNotExists;
  70
  71         public:
  72             TestThread( CppUnitMini::ThreadPool& pool, MAP& rMap )
  73                 : CppUnitMini::TestThread( pool )
  74                 , m_Map( rMap )
  75             {}
  76             TestThread( TestThread& src )
  77                 : CppUnitMini::TestThread( src )
  78                 , m_Map( src.m_Map )
  79             {}
  80
  81             Map_find_string&  getTest()
  82             {
  83                 return reinterpret_cast<Map_find_string&>( m_Pool.m_Test );
  84             }
  85
  86             virtual void init() { cds::threading::Manager::attachThread()   ; }
  87             virtual void fini() { cds::threading::Manager::detachThread()   ; }
  88
  89             virtual void test()
  90             {
  91                 ValueVector& arr = getTest().m_Arr;
  92                 //size_t nSize = arr.size();
  93
  94                 MAP& rMap = m_Map;
  95                 for ( size_t nPass = 0; nPass < c_nPassCount; ++nPass ) {
  96                     if ( m_nThreadNo & 1 ) {
  97                         ValueVector::const_iterator itEnd = arr.end();
  98                         for ( ValueVector::const_iterator it = arr.begin(); it != itEnd; ++it ) {
  99                             auto bFound = rMap.find( *(it->pKey) );
 100                             if ( it->bExists ) {
 101                                 if ( check_result(bFound, rMap))
 102                                     ++m_KeyExists.nSuccess;
 103                                 else
 104                                     ++m_KeyExists.nFailed;
 105                             }
 106                             else {
 107                                 if ( check_result(bFound, rMap))
 108                                     ++m_KeyNotExists.nFailed;
 109                                 else
 110                                     ++m_KeyNotExists.nSuccess;
 111                             }
 112                         }
 113                     }
 114                     else {
 115                         ValueVector::const_reverse_iterator itEnd = arr.rend();
 116                         for ( ValueVector::const_reverse_iterator it = arr.rbegin(); it != itEnd; ++it ) {
 117                             auto bFound = rMap.find( *(it->pKey) );
 118                             if ( it->bExists ) {
 119                                 if ( check_result(bFound, rMap))
 120                                     ++m_KeyExists.nSuccess;
 121                                 else
 122                                     ++m_KeyExists.nFailed;
 123                             }
 124                             else {
 125                                 if ( check_result( bFound, rMap ))
 126                                     ++m_KeyNotExists.nFailed;
 127                                 else
 128                                     ++m_KeyNotExists.nSuccess;
 129                             }
 130                         }
 131                     }
 132                 }
 133             }
 134         };
 135
 136     public:
 137         Map_find_string()
 138             : m_bSeqInit( false )
 139         {}
 140
 141     protected:
 142
 143         void generateSequence()
 144         {
 145             size_t nPercent = c_nPercentExists;
 146
 147             if ( nPercent > 100 )
 148                 nPercent = 100;
 149             else if ( nPercent < 1 )
 150                 nPercent = 1;
 151
 152             m_nRealMapSize = 0;
 153
 154             std::vector<std::string> const & arrString = CppUnitMini::TestCase::getTestStrings();
 155             size_t nSize = arrString.size();
 156             if ( nSize > c_nMapSize )
 157                 nSize = c_nMapSize;
 158             m_Arr.resize( nSize );
 159             for ( size_t i = 0; i < nSize; ++i ) {
 160                 m_Arr[i].pKey = &( arrString[i] );
 161                 m_Arr[i].bExists = CppUnitMini::Rand( 100 ) <= nPercent;
 162                 if ( m_Arr[i].bExists )
 163                     ++m_nRealMapSize;
 164             }
 165         }
 166
 167
 168         template <class MAP>
 169         void find_string_test( MAP& testMap )
 170         {
 171             typedef TestThread<MAP>     Thread;
 172             cds::OS::Timer    timer;
 173
 174             // Fill the map
 175             CPPUNIT_MSG( "  Fill map...");
 176             timer.reset();
 177             for ( size_t i = 0; i < m_Arr.size(); ++i ) {
 178                 // All keys in arrData are unique, insert() must be successful
 179                 if ( m_Arr[i].bExists )
 180                     CPPUNIT_ASSERT( check_result( testMap.insert( *(m_Arr[i].pKey), m_Arr[i] ), testMap ));
 181             }
 182             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 183
 184             CPPUNIT_MSG( "  Searching...");
 185             CppUnitMini::ThreadPool pool( *this );
 186             pool.add( new Thread( pool, testMap ), c_nThreadCount );
 187             pool.run();
 188             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 189
 190             // Postcondition: the number of success searching == the number of map item
 191             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 192                 Thread * pThread = static_cast<Thread *>( *it );
 193                 CPPUNIT_CHECK( pThread->m_KeyExists.nSuccess == m_nRealMapSize * c_nPassCount );
 194                 CPPUNIT_CHECK( pThread->m_KeyExists.nFailed == 0 );
 195                 CPPUNIT_CHECK( pThread->m_KeyNotExists.nSuccess == (m_Arr.size() - m_nRealMapSize) * c_nPassCount );
 196                 CPPUNIT_CHECK( pThread->m_KeyNotExists.nFailed == 0 );
 197             }
 198
 199             check_before_cleanup( testMap );
 200
 201             testMap.clear();
 202             additional_check( testMap );
 203             print_stat( testMap );
 204             additional_cleanup( testMap );
 205         }
 206
 207         void initTestSequence()
 208         {
 209             if ( !m_bSeqInit ) {
 210                 m_bSeqInit = true;
 211
 212                 CPPUNIT_MSG( "Generating test data...");
 213                 cds::OS::Timer    timer;
 214                 generateSequence();
 215                 CPPUNIT_MSG( "   Duration=" << timer.duration() );
 216                 CPPUNIT_MSG( "Map size=" << m_nRealMapSize << " find key loop=" << m_Arr.size() << " (" << c_nPercentExists << "% success)" );
 217                 CPPUNIT_MSG( "Thread count=" << c_nThreadCount << " Pass count=" << c_nPassCount );
 218             }
 219         }
 220
 221         template <class MAP>
 222         void test()
 223         {
 224             initTestSequence();
 225
 226             for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
 227                 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
 228                 MAP  testMap( m_Arr.size(), nLoadFactor );
 229                 find_string_test( testMap );
 230                 if ( c_bPrintGCState )
 231                     print_gc_state();
 232             }
 233         }
 234
 235         template <class MAP>
 236         void test_nolf()
 237         {
 238             initTestSequence();
 239
 240             MAP testMap;
 241             find_string_test( testMap );
 242             if ( c_bPrintGCState )
 243                 print_gc_state();
 244         }
 245
 246         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
 247             c_nThreadCount = cfg.getULong("ThreadCount", 8 )        ; // thread count
 248             c_nMapSize = cfg.getULong("MapSize", 20000000 )         ;  // map size (count of searching item)
 249             c_nPercentExists = cfg.getULong("PercentExists", 50 )   ;  // percent of existing keys in searching sequence
 250             c_nPassCount = cfg.getULong("PassCount", 2 );
 251             c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", 8 );
 252             c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true );
 253         }
 254
 255 #   include "map2/map_defs.h"
 256         CDSUNIT_DECLARE_MichaelMap
 257         CDSUNIT_DECLARE_MichaelMap_nogc
 258         CDSUNIT_DECLARE_SplitList
 259         CDSUNIT_DECLARE_SplitList_nogc
 260         CDSUNIT_DECLARE_SkipListMap
 261         CDSUNIT_DECLARE_SkipListMap_nogc
 262         CDSUNIT_DECLARE_EllenBinTreeMap
 263         CDSUNIT_DECLARE_BronsonAVLTreeMap
 264         CDSUNIT_DECLARE_StripedMap
 265         CDSUNIT_DECLARE_RefinableMap
 266         CDSUNIT_DECLARE_CuckooMap
 267         CDSUNIT_DECLARE_StdMap
 268
 269         CPPUNIT_TEST_SUITE( Map_find_string )
 270             CDSUNIT_TEST_MichaelMap
 271             CDSUNIT_TEST_MichaelMap_nogc
 272             CDSUNIT_TEST_SplitList
 273             CDSUNIT_TEST_SplitList_nogc
 274             CDSUNIT_TEST_SkipListMap
 275             CDSUNIT_TEST_SkipListMap_nogc
 276             CDSUNIT_TEST_EllenBinTreeMap
 277             CDSUNIT_TEST_BronsonAVLTreeMap
 278             CDSUNIT_TEST_StripedMap
 279             CDSUNIT_TEST_RefinableMap
 280             CDSUNIT_TEST_CuckooMap
 281             CDSUNIT_TEST_StdMap
 282         CPPUNIT_TEST_SUITE_END()
 283
 284     };
 285
 286     CPPUNIT_TEST_SUITE_REGISTRATION( Map_find_string );
 287 } // namespace map2