tests/unit/map2/map_find_int.h

   1 //$$CDS-header$$
   2
   3 // defines concurrent access to map::nonconcurrent_iterator::Sequence::TValue::nAccess field
   4
   5 #include "map2/map_type.h"
   6 #include "cppunit/thread.h"
   7
   8 #include <vector>
   9
  10 // find int test in map<int> in mutithreaded mode
  11 namespace map2 {
  12
  13 #define TEST_CASE(TAG, X)  void X();
  14
  15     class Map_find_int: public CppUnitMini::TestCase
  16     {
  17     public:
  18         size_t c_nThreadCount = 8;     // thread count
  19         size_t c_nMapSize = 10000000;  // map size (count of searching item)
  20         size_t c_nPercentExists = 50;  // percent of existing keys in searching sequence
  21         size_t c_nPassCount = 2;
  22         size_t c_nMaxLoadFactor = 8;   // maximum load factor
  23         bool   c_bPrintGCState = true;
  24
  25         size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
  26         size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
  27         size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
  28
  29         size_t c_nMultiLevelMap_HeadBits = 10;
  30         size_t c_nMultiLevelMap_ArrayBits = 4;
  31
  32         size_t  c_nLoadFactor;  // current load factor
  33
  34     private:
  35         typedef CppUnitMini::TestCase Base;
  36         typedef size_t   key_type;
  37         struct value_type {
  38             key_type    nKey    ;   // key
  39             bool        bExists ;   // true - key in map, false - key not in map
  40         };
  41
  42         typedef std::vector<value_type> ValueVector;
  43         ValueVector             m_Arr;
  44         size_t                  m_nRealMapSize;
  45
  46         void generateSequence();
  47
  48         template <typename Iterator, typename Map>
  49         static bool check_result( Iterator const& it, Map const& map )
  50         {
  51             return it != map.end();
  52         }
  53         template <typename Map>
  54         static bool check_result( bool b, Map const& )
  55         {
  56             return b;
  57         }
  58
  59         template <class Map>
  60         class TestThread: public CppUnitMini::TestThread
  61         {
  62             Map&     m_Map;
  63
  64             virtual TestThread *    clone()
  65             {
  66                 return new TestThread( *this );
  67             }
  68         public:
  69             struct Stat {
  70                 size_t      nSuccess;
  71                 size_t      nFailed;
  72
  73                 Stat()
  74                     : nSuccess(0)
  75                     , nFailed(0)
  76                 {}
  77             };
  78
  79             Stat    m_KeyExists;
  80             Stat    m_KeyNotExists;
  81
  82         public:
  83             TestThread( CppUnitMini::ThreadPool& pool, Map& rMap )
  84                 : CppUnitMini::TestThread( pool )
  85                 , m_Map( rMap )
  86             {}
  87             TestThread( TestThread& src )
  88                 : CppUnitMini::TestThread( src )
  89                 , m_Map( src.m_Map )
  90             {}
  91
  92             Map_find_int&  getTest()
  93             {
  94                 return reinterpret_cast<Map_find_int&>( m_Pool.m_Test );
  95             }
  96
  97             virtual void init() { cds::threading::Manager::attachThread()   ; }
  98             virtual void fini() { cds::threading::Manager::detachThread()   ; }
  99
 100             virtual void test()
 101             {
 102                 ValueVector& arr = getTest().m_Arr;
 103                 size_t const nPassCount = getTest().c_nPassCount;
 104
 105                 Map& rMap = m_Map;
 106                 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 107                     if ( m_nThreadNo & 1 ) {
 108                         ValueVector::const_iterator itEnd = arr.end();
 109                         for ( ValueVector::const_iterator it = arr.begin(); it != itEnd; ++it ) {
 110                             auto bFound = rMap.contains( it->nKey );
 111                             if ( it->bExists ) {
 112                                 if ( check_result( bFound, rMap ))
 113                                     ++m_KeyExists.nSuccess;
 114                                 else {
 115                                     //rMap.find( it->nKey );
 116                                     ++m_KeyExists.nFailed;
 117                                 }
 118                             }
 119                             else {
 120                                 if ( check_result( bFound, rMap )) {
 121                                     //rMap.find( it->nKey );
 122                                     ++m_KeyNotExists.nFailed;
 123                                 }
 124                                 else
 125                                     ++m_KeyNotExists.nSuccess;
 126                             }
 127                         }
 128                     }
 129                     else {
 130                         ValueVector::const_reverse_iterator itEnd = arr.rend();
 131                         for ( ValueVector::const_reverse_iterator it = arr.rbegin(); it != itEnd; ++it ) {
 132                             auto bFound = rMap.contains( it->nKey );
 133                             if ( it->bExists ) {
 134                                 if ( check_result( bFound, rMap ))
 135                                     ++m_KeyExists.nSuccess;
 136                                 else {
 137                                     //rMap.find( it->nKey );
 138                                     ++m_KeyExists.nFailed;
 139                                 }
 140                             }
 141                             else {
 142                                 if ( check_result( bFound, rMap )) {
 143                                     //rMap.find( it->nKey );
 144                                     ++m_KeyNotExists.nFailed;
 145                                 }
 146                                 else
 147                                     ++m_KeyNotExists.nSuccess;
 148                             }
 149                         }
 150                     }
 151                 }
 152             }
 153         };
 154
 155     protected:
 156
 157         template <class Map>
 158         void find_int_test( Map& testMap )
 159         {
 160             typedef TestThread<Map>     Thread;
 161             cds::OS::Timer    timer;
 162
 163             // Fill the map
 164             CPPUNIT_MSG( "  Fill map with " << m_Arr.size() << " items...");
 165             timer.reset();
 166             for ( size_t i = 0; i < m_Arr.size(); ++i ) {
 167                 if ( m_Arr[i].bExists ) {
 168                     CPPUNIT_ASSERT( check_result( testMap.insert( m_Arr[i].nKey, m_Arr[i] ), testMap ));
 169                 }
 170             }
 171             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 172
 173             CPPUNIT_MSG( "  Searching...");
 174             CppUnitMini::ThreadPool pool( *this );
 175             pool.add( new Thread( pool, testMap ), c_nThreadCount );
 176             pool.run();
 177             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 178
 179             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 180                 Thread * pThread = static_cast<Thread *>( *it );
 181                 CPPUNIT_CHECK( pThread->m_KeyExists.nFailed == 0 );
 182                 CPPUNIT_CHECK( pThread->m_KeyExists.nSuccess == m_nRealMapSize * c_nPassCount );
 183                 CPPUNIT_CHECK( pThread->m_KeyNotExists.nFailed == 0 );
 184                 CPPUNIT_CHECK( pThread->m_KeyNotExists.nSuccess == (m_Arr.size() - m_nRealMapSize) * c_nPassCount );
 185             }
 186
 187             check_before_cleanup( testMap );
 188
 189             testMap.clear();
 190             additional_check( testMap );
 191             print_stat( testMap );
 192             additional_cleanup( testMap );
 193         }
 194
 195         template <class Map>
 196         void run_test()
 197         {
 198             if ( Map::c_bLoadFactorDepended ) {
 199                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 200                     CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
 201                     Map  testMap( *this );
 202                     find_int_test( testMap );
 203                     if ( c_bPrintGCState )
 204                         print_gc_state();
 205                 }
 206             }
 207             else {
 208                 Map testMap( *this );
 209                 find_int_test( testMap );
 210                 if ( c_bPrintGCState )
 211                     print_gc_state();
 212             }
 213         }
 214
 215         void setUpParams( const CppUnitMini::TestCfg& cfg );
 216
 217     public:
 218         Map_find_int()
 219             : c_nLoadFactor(2)
 220         {}
 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_int)
 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 map