tests/unit/map2/map_find_string.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_find_string: public CppUnitMini::TestCase
  13     {
  14     public:
  15         size_t c_nThreadCount = 8;     // thread count
  16         size_t c_nMapSize = 10000000;  // map size (count of searching item)
  17         size_t c_nPercentExists = 50;  // percent of existing keys in searching sequence
  18         size_t c_nPassCount = 2;
  19         size_t c_nMaxLoadFactor = 8;   // maximum load factor
  20         bool   c_bPrintGCState = true;
  21
  22         size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
  23         size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
  24         size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
  25
  26         size_t c_nMultiLevelMap_HeadBits = 10;
  27         size_t c_nMultiLevelMap_ArrayBits = 4;
  28
  29         size_t  c_nLoadFactor;  // current load factor
  30
  31     private:
  32         typedef CppUnitMini::TestCase Base;
  33         typedef std::string  key_type;
  34         struct value_type {
  35             std::string const * pKey;
  36             bool        bExists ;   // true - key in map, false - key not in map
  37         };
  38
  39         typedef std::vector<value_type> ValueVector;
  40         ValueVector             m_Arr;
  41
  42         template <typename Iterator, typename Map>
  43         static bool check_result( Iterator const& it, Map const& map )
  44         {
  45             return it != map.end();
  46         }
  47         template <typename Map>
  48         static bool check_result( bool b, Map const& )
  49         {
  50             return b;
  51         }
  52
  53         template <class Map>
  54         class TestThread: public CppUnitMini::TestThread
  55         {
  56             Map&     m_Map;
  57
  58             virtual TestThread *    clone()
  59             {
  60                 return new TestThread( *this );
  61             }
  62         public:
  63             struct Stat {
  64                 size_t      nSuccess;
  65                 size_t      nFailed;
  66
  67                 Stat()
  68                     : nSuccess(0)
  69                     , nFailed(0)
  70                 {}
  71             };
  72
  73             Stat    m_KeyExists;
  74             Stat    m_KeyNotExists;
  75
  76         public:
  77             TestThread( CppUnitMini::ThreadPool& pool, Map& rMap )
  78                 : CppUnitMini::TestThread( pool )
  79                 , m_Map( rMap )
  80             {}
  81             TestThread( TestThread& src )
  82                 : CppUnitMini::TestThread( src )
  83                 , m_Map( src.m_Map )
  84             {}
  85
  86             Map_find_string&  getTest()
  87             {
  88                 return reinterpret_cast<Map_find_string&>( m_Pool.m_Test );
  89             }
  90
  91             virtual void init() { cds::threading::Manager::attachThread()   ; }
  92             virtual void fini() { cds::threading::Manager::detachThread()   ; }
  93
  94             virtual void test()
  95             {
  96                 ValueVector& arr = getTest().m_Arr;
  97                 size_t const nPassCount = getTest().c_nPassCount;
  98
  99                 Map& rMap = m_Map;
 100                 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 101                     if ( m_nThreadNo & 1 ) {
 102                         ValueVector::const_iterator itEnd = arr.end();
 103                         for ( ValueVector::const_iterator it = arr.begin(); it != itEnd; ++it ) {
 104                             auto bFound = rMap.contains( *(it->pKey) );
 105                             if ( it->bExists ) {
 106                                 if ( check_result(bFound, rMap))
 107                                     ++m_KeyExists.nSuccess;
 108                                 else
 109                                     ++m_KeyExists.nFailed;
 110                             }
 111                             else {
 112                                 if ( check_result(bFound, rMap))
 113                                     ++m_KeyNotExists.nFailed;
 114                                 else
 115                                     ++m_KeyNotExists.nSuccess;
 116                             }
 117                         }
 118                     }
 119                     else {
 120                         ValueVector::const_reverse_iterator itEnd = arr.rend();
 121                         for ( ValueVector::const_reverse_iterator it = arr.rbegin(); it != itEnd; ++it ) {
 122                             auto bFound = rMap.contains( *(it->pKey) );
 123                             if ( it->bExists ) {
 124                                 if ( check_result(bFound, rMap))
 125                                     ++m_KeyExists.nSuccess;
 126                                 else
 127                                     ++m_KeyExists.nFailed;
 128                             }
 129                             else {
 130                                 if ( check_result( bFound, rMap ))
 131                                     ++m_KeyNotExists.nFailed;
 132                                 else
 133                                     ++m_KeyNotExists.nSuccess;
 134                             }
 135                         }
 136                     }
 137                 }
 138             }
 139         };
 140
 141     public:
 142         Map_find_string()
 143             : c_nLoadFactor( 2 )
 144         {}
 145
 146     protected:
 147
 148         void generateSequence();
 149
 150         template <class Map>
 151         void find_string_test( Map& testMap )
 152         {
 153             typedef TestThread<Map>     Thread;
 154             cds::OS::Timer    timer;
 155
 156             // Fill the map
 157             CPPUNIT_MSG( "  Fill map...");
 158             timer.reset();
 159             for ( size_t i = 0; i < m_Arr.size(); ++i ) {
 160                 // All keys in arrData are unique, insert() must be successful
 161                 if ( m_Arr[i].bExists )
 162                     CPPUNIT_ASSERT( check_result( testMap.insert( *(m_Arr[i].pKey), m_Arr[i] ), testMap ));
 163             }
 164             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 165
 166             CPPUNIT_MSG( "  Searching...");
 167             CppUnitMini::ThreadPool pool( *this );
 168             pool.add( new Thread( pool, testMap ), c_nThreadCount );
 169             pool.run();
 170             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 171
 172             // Postcondition: the number of success searching == the number of map item
 173             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 174                 Thread * pThread = static_cast<Thread *>( *it );
 175                 CPPUNIT_CHECK( pThread->m_KeyExists.nSuccess == c_nMapSize * c_nPassCount );
 176                 CPPUNIT_CHECK( pThread->m_KeyExists.nFailed == 0 );
 177                 CPPUNIT_CHECK( pThread->m_KeyNotExists.nSuccess == (m_Arr.size() - c_nMapSize) * c_nPassCount );
 178                 CPPUNIT_CHECK( pThread->m_KeyNotExists.nFailed == 0 );
 179             }
 180
 181             check_before_cleanup( testMap );
 182
 183             testMap.clear();
 184             additional_check( testMap );
 185             print_stat( testMap );
 186             additional_cleanup( testMap );
 187         }
 188
 189         template <class Map>
 190         void run_test()
 191         {
 192             if ( Map::c_bLoadFactorDepended ) {
 193                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 194                     CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
 195                     Map testMap( *this );
 196                     find_string_test( testMap );
 197                     if ( c_bPrintGCState )
 198                         print_gc_state();
 199                 }
 200             }
 201             else {
 202                 Map testMap( *this );
 203                 find_string_test( testMap );
 204                 if ( c_bPrintGCState )
 205                     print_gc_state();
 206             }
 207         }
 208
 209         template <class Map>
 210         void test_nolf()
 211         {
 212             initTestSequence();
 213
 214             Map testMap;
 215             find_string_test( testMap );
 216             if ( c_bPrintGCState )
 217                 print_gc_state();
 218         }
 219
 220         void setUpParams( const CppUnitMini::TestCfg& cfg );
 221
 222 #   include "map2/map_defs.h"
 223         CDSUNIT_DECLARE_MichaelMap
 224         CDSUNIT_DECLARE_MichaelMap_nogc
 225         CDSUNIT_DECLARE_SplitList
 226         CDSUNIT_DECLARE_SplitList_nogc
 227         CDSUNIT_DECLARE_SkipListMap
 228         CDSUNIT_DECLARE_SkipListMap_nogc
 229         CDSUNIT_DECLARE_EllenBinTreeMap
 230         CDSUNIT_DECLARE_BronsonAVLTreeMap
 231         CDSUNIT_DECLARE_MultiLevelHashMap
 232         CDSUNIT_DECLARE_StripedMap
 233         CDSUNIT_DECLARE_RefinableMap
 234         CDSUNIT_DECLARE_CuckooMap
 235         CDSUNIT_DECLARE_StdMap
 236         CDSUNIT_DECLARE_StdMap_NoLock
 237
 238         CPPUNIT_TEST_SUITE(Map_find_string)
 239             CDSUNIT_TEST_MichaelMap
 240             CDSUNIT_TEST_MichaelMap_nogc
 241             CDSUNIT_TEST_SplitList
 242             CDSUNIT_TEST_SplitList_nogc
 243             CDSUNIT_TEST_SkipListMap
 244             CDSUNIT_TEST_SkipListMap_nogc
 245             CDSUNIT_TEST_EllenBinTreeMap
 246             CDSUNIT_TEST_BronsonAVLTreeMap
 247             CDSUNIT_TEST_MultiLevelHashMap
 248             CDSUNIT_TEST_CuckooMap
 249             CDSUNIT_TEST_StripedMap
 250             CDSUNIT_TEST_RefinableMap
 251             CDSUNIT_TEST_StdMap
 252             CDSUNIT_TEST_StdMap_NoLock
 253         CPPUNIT_TEST_SUITE_END();
 254     };
 255 } // namespace map2