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_types.h"
   6 #include "cppunit/thread.h"
   7
   8 #include <vector>
   9 #include <algorithm> // random_shuffle
  10
  11 // find int test in map<int> in mutithreaded mode
  12 namespace map2 {
  13
  14 #   define TEST_MAP(X)         void X() { test<MapTypes<key_type, value_type>::X >()    ; }
  15 #   define TEST_MAP_NOLF(X)    void X() { test_nolf<MapTypes<key_type, value_type>::X >()    ; }
  16 #   define TEST_MAP_EXTRACT(X)  TEST_MAP(X)
  17 #   define TEST_MAP_NOLF_EXTRACT(X) TEST_MAP_NOLF(X)
  18
  19     class Map_find_int: public CppUnitMini::TestCase
  20     {
  21         static size_t c_nThreadCount;   // thread count
  22         static size_t c_nMapSize;       // map size (count of searching item)
  23         static size_t c_nPercentExists; // percent of existing keys in searching sequence
  24         static size_t c_nPassCount;
  25         static size_t c_nMaxLoadFactor; // maximum load factor
  26         static bool   c_bPrintGCState;
  27
  28         typedef CppUnitMini::TestCase Base;
  29         typedef size_t   key_type;
  30         struct value_type {
  31             key_type    nKey    ;   // key
  32             bool        bExists ;   // true - key in map, false - key not in map
  33         };
  34
  35         typedef std::vector<value_type> ValueVector;
  36         ValueVector             m_Arr;
  37         size_t                  m_nRealMapSize;
  38         bool                    m_bSequenceInitialized;
  39
  40         void generateSequence();
  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_int&  getTest()
  87             {
  88                 return reinterpret_cast<Map_find_int&>( 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 nSize = arr.size();
  98
  99                 Map& rMap = m_Map;
 100                 for ( size_t nPass = 0; nPass < c_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.find( it->nKey );
 105                             if ( it->bExists ) {
 106                                 if ( check_result( bFound, rMap ))
 107                                     ++m_KeyExists.nSuccess;
 108                                 else {
 109                                     //rMap.find( it->nKey );
 110                                     ++m_KeyExists.nFailed;
 111                                 }
 112                             }
 113                             else {
 114                                 if ( check_result( bFound, rMap )) {
 115                                     //rMap.find( it->nKey );
 116                                     ++m_KeyNotExists.nFailed;
 117                                 }
 118                                 else
 119                                     ++m_KeyNotExists.nSuccess;
 120                             }
 121                         }
 122                     }
 123                     else {
 124                         ValueVector::const_reverse_iterator itEnd = arr.rend();
 125                         for ( ValueVector::const_reverse_iterator it = arr.rbegin(); it != itEnd; ++it ) {
 126                             auto bFound = rMap.find( it->nKey );
 127                             if ( it->bExists ) {
 128                                 if ( check_result( bFound, rMap ))
 129                                     ++m_KeyExists.nSuccess;
 130                                 else {
 131                                     //rMap.find( it->nKey );
 132                                     ++m_KeyExists.nFailed;
 133                                 }
 134                             }
 135                             else {
 136                                 if ( check_result( bFound, rMap )) {
 137                                     //rMap.find( it->nKey );
 138                                     ++m_KeyNotExists.nFailed;
 139                                 }
 140                                 else
 141                                     ++m_KeyNotExists.nSuccess;
 142                             }
 143                         }
 144                     }
 145                 }
 146             }
 147         };
 148
 149     protected:
 150
 151         template <class Map>
 152         void find_int_test( Map& testMap )
 153         {
 154             typedef TestThread<Map>     Thread;
 155             cds::OS::Timer    timer;
 156
 157             // Fill the map
 158             CPPUNIT_MSG( "  Fill map with " << m_Arr.size() << " items...");
 159             timer.reset();
 160             for ( size_t i = 0; i < m_Arr.size(); ++i ) {
 161                 if ( m_Arr[i].bExists ) {
 162                     CPPUNIT_ASSERT( check_result( testMap.insert( m_Arr[i].nKey, m_Arr[i] ), testMap ));
 163                 }
 164             }
 165             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 166
 167             CPPUNIT_MSG( "  Searching...");
 168             CppUnitMini::ThreadPool pool( *this );
 169             pool.add( new Thread( pool, testMap ), c_nThreadCount );
 170             pool.run();
 171             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 172
 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.nFailed == 0 );
 176                 CPPUNIT_CHECK( pThread->m_KeyExists.nSuccess == m_nRealMapSize * c_nPassCount );
 177                 CPPUNIT_CHECK( pThread->m_KeyNotExists.nFailed == 0 );
 178                 CPPUNIT_CHECK( pThread->m_KeyNotExists.nSuccess == (m_Arr.size() - m_nRealMapSize) * c_nPassCount );
 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         void initTestSequence();
 190
 191         template <class Map>
 192         void test()
 193         {
 194             if ( !m_bSequenceInitialized )
 195                 initTestSequence();
 196
 197             for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
 198                 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
 199                 Map  testMap( c_nMapSize, nLoadFactor );
 200                 find_int_test( testMap );
 201                 if ( c_bPrintGCState )
 202                     print_gc_state();
 203             }
 204         }
 205
 206         template <class Map>
 207         void test_nolf()
 208         {
 209             if ( !m_bSequenceInitialized )
 210                 initTestSequence();
 211
 212             Map testMap;
 213             find_int_test( testMap );
 214             if ( c_bPrintGCState )
 215                 print_gc_state();
 216         }
 217
 218         void setUpParams( const CppUnitMini::TestCfg& cfg );
 219
 220         void run_MichaelMap(const char *in_name, bool invert = false);
 221         void run_SplitList(const char *in_name, bool invert = false);
 222         void run_StripedMap(const char *in_name, bool invert = false);
 223         void run_RefinableMap(const char *in_name, bool invert = false);
 224         void run_CuckooMap(const char *in_name, bool invert = false);
 225         void run_SkipListMap(const char *in_name, bool invert = false);
 226         void run_EllenBinTreeMap(const char *in_name, bool invert = false);
 227         void run_BronsonAVLTreeMap(const char *in_name, bool invert = false);
 228         void run_StdMap(const char *in_name, bool invert = false);
 229
 230         virtual void myRun(const char *in_name, bool invert = false);
 231
 232     public:
 233         Map_find_int()
 234             : m_bSequenceInitialized( false )
 235         {}
 236
 237 #   include "map2/map_defs.h"
 238         CDSUNIT_DECLARE_MichaelMap
 239         CDSUNIT_DECLARE_MichaelMap_nogc
 240         CDSUNIT_DECLARE_SplitList
 241         CDSUNIT_DECLARE_SplitList_nogc
 242         CDSUNIT_DECLARE_SkipListMap
 243         CDSUNIT_DECLARE_SkipListMap_nogc
 244         CDSUNIT_DECLARE_EllenBinTreeMap
 245         CDSUNIT_DECLARE_BronsonAVLTreeMap
 246         CDSUNIT_DECLARE_StripedMap
 247         CDSUNIT_DECLARE_RefinableMap
 248         CDSUNIT_DECLARE_CuckooMap
 249         CDSUNIT_DECLARE_StdMap
 250     };
 251 } // namespace map