tests/unit/map2/map_find_string.h

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