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