tests/unit/map2/map_find_int.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 // defines concurrent access to map::nonconcurrent_iterator::Sequence::TValue::nAccess field
  32
  33 #include "map2/map_type.h"
  34 #include "cppunit/thread.h"
  35
  36 #include <vector>
  37
  38 // find int test in map<int> in mutithreaded mode
  39 namespace map2 {
  40
  41 #define TEST_CASE(TAG, X)  void X();
  42
  43     class Map_find_int: public CppUnitMini::TestCase
  44     {
  45     public:
  46         size_t c_nThreadCount = 8;     // thread count
  47         size_t c_nMapSize = 10000000;  // map size (count of searching item)
  48         size_t c_nPercentExists = 50;  // percent of existing keys in searching sequence
  49         size_t c_nPassCount = 2;
  50         size_t c_nMaxLoadFactor = 8;   // maximum load factor
  51         bool   c_bPrintGCState = true;
  52
  53         size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
  54         size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
  55         size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
  56
  57         size_t c_nFeldmanMap_HeadBits = 10;
  58         size_t c_nFeldmanMap_ArrayBits = 4;
  59
  60         size_t  c_nLoadFactor;  // current load factor
  61
  62     private:
  63         typedef size_t   key_type;
  64         struct value_type {
  65             key_type    nKey    ;   // key
  66             bool        bExists ;   // true - key in map, false - key not in map
  67         };
  68
  69         typedef std::vector<value_type> ValueVector;
  70         ValueVector             m_Arr;
  71         size_t                  m_nRealMapSize;
  72
  73         void generateSequence();
  74
  75         template <typename Iterator, typename Map>
  76         static bool check_result( Iterator const& it, Map const& map )
  77         {
  78             return it != map.end();
  79         }
  80         template <typename Map>
  81         static bool check_result( bool b, Map const& )
  82         {
  83             return b;
  84         }
  85
  86         template <class Map>
  87         class TestThread: public CppUnitMini::TestThread
  88         {
  89             Map&     m_Map;
  90
  91             virtual TestThread *    clone()
  92             {
  93                 return new TestThread( *this );
  94             }
  95         public:
  96             struct Stat {
  97                 size_t      nSuccess;
  98                 size_t      nFailed;
  99
 100                 Stat()
 101                     : nSuccess(0)
 102                     , nFailed(0)
 103                 {}
 104             };
 105
 106             Stat    m_KeyExists;
 107             Stat    m_KeyNotExists;
 108
 109         public:
 110             TestThread( CppUnitMini::ThreadPool& pool, Map& rMap )
 111                 : CppUnitMini::TestThread( pool )
 112                 , m_Map( rMap )
 113             {}
 114             TestThread( TestThread& src )
 115                 : CppUnitMini::TestThread( src )
 116                 , m_Map( src.m_Map )
 117             {}
 118
 119             Map_find_int&  getTest()
 120             {
 121                 return reinterpret_cast<Map_find_int&>( m_Pool.m_Test );
 122             }
 123
 124             virtual void init() { cds::threading::Manager::attachThread()   ; }
 125             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 126
 127             virtual void test()
 128             {
 129                 ValueVector& arr = getTest().m_Arr;
 130                 size_t const nPassCount = getTest().c_nPassCount;
 131
 132                 Map& rMap = m_Map;
 133                 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 134                     if ( m_nThreadNo & 1 ) {
 135                         ValueVector::const_iterator itEnd = arr.end();
 136                         for ( ValueVector::const_iterator it = arr.begin(); it != itEnd; ++it ) {
 137                             auto bFound = rMap.contains( it->nKey );
 138                             if ( it->bExists ) {
 139                                 if ( check_result( bFound, rMap ))
 140                                     ++m_KeyExists.nSuccess;
 141                                 else {
 142                                     //rMap.find( it->nKey );
 143                                     ++m_KeyExists.nFailed;
 144                                 }
 145                             }
 146                             else {
 147                                 if ( check_result( bFound, rMap )) {
 148                                     //rMap.find( it->nKey );
 149                                     ++m_KeyNotExists.nFailed;
 150                                 }
 151                                 else
 152                                     ++m_KeyNotExists.nSuccess;
 153                             }
 154                         }
 155                     }
 156                     else {
 157                         ValueVector::const_reverse_iterator itEnd = arr.rend();
 158                         for ( ValueVector::const_reverse_iterator it = arr.rbegin(); it != itEnd; ++it ) {
 159                             auto bFound = rMap.contains( it->nKey );
 160                             if ( it->bExists ) {
 161                                 if ( check_result( bFound, rMap ))
 162                                     ++m_KeyExists.nSuccess;
 163                                 else {
 164                                     //rMap.find( it->nKey );
 165                                     ++m_KeyExists.nFailed;
 166                                 }
 167                             }
 168                             else {
 169                                 if ( check_result( bFound, rMap )) {
 170                                     //rMap.find( it->nKey );
 171                                     ++m_KeyNotExists.nFailed;
 172                                 }
 173                                 else
 174                                     ++m_KeyNotExists.nSuccess;
 175                             }
 176                         }
 177                     }
 178                 }
 179             }
 180         };
 181
 182     protected:
 183
 184         template <class Map>
 185         void find_int_test( Map& testMap )
 186         {
 187             typedef TestThread<Map>     Thread;
 188             cds::OS::Timer    timer;
 189
 190             // Fill the map
 191             CPPUNIT_MSG( "  Fill map with " << m_Arr.size() << " items...");
 192             timer.reset();
 193             for ( size_t i = 0; i < m_Arr.size(); ++i ) {
 194                 if ( m_Arr[i].bExists ) {
 195                     CPPUNIT_ASSERT( check_result( testMap.insert( m_Arr[i].nKey, m_Arr[i] ), testMap ));
 196                 }
 197             }
 198             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 199
 200             CPPUNIT_MSG( "  Searching...");
 201             CppUnitMini::ThreadPool pool( *this );
 202             pool.add( new Thread( pool, testMap ), c_nThreadCount );
 203             pool.run();
 204             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 205
 206             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 207                 Thread * pThread = static_cast<Thread *>( *it );
 208                 CPPUNIT_CHECK( pThread->m_KeyExists.nFailed == 0 );
 209                 CPPUNIT_CHECK( pThread->m_KeyExists.nSuccess == m_nRealMapSize * c_nPassCount );
 210                 CPPUNIT_CHECK( pThread->m_KeyNotExists.nFailed == 0 );
 211                 CPPUNIT_CHECK( pThread->m_KeyNotExists.nSuccess == (m_Arr.size() - m_nRealMapSize) * c_nPassCount );
 212             }
 213
 214             check_before_cleanup( testMap );
 215
 216             testMap.clear();
 217             additional_check( testMap );
 218             print_stat( testMap );
 219             additional_cleanup( testMap );
 220         }
 221
 222         template <class Map>
 223         void run_test()
 224         {
 225             if ( Map::c_bLoadFactorDepended ) {
 226                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 227                     CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
 228                     Map  testMap( *this );
 229                     find_int_test( testMap );
 230                     if ( c_bPrintGCState )
 231                         print_gc_state();
 232                 }
 233             }
 234             else {
 235                 Map testMap( *this );
 236                 find_int_test( testMap );
 237                 if ( c_bPrintGCState )
 238                     print_gc_state();
 239             }
 240         }
 241
 242         void setUpParams( const CppUnitMini::TestCfg& cfg );
 243
 244     public:
 245         Map_find_int()
 246             : c_nLoadFactor(2)
 247         {}
 248
 249 #   include "map2/map_defs.h"
 250         CDSUNIT_DECLARE_MichaelMap
 251         CDSUNIT_DECLARE_MichaelMap_nogc
 252         CDSUNIT_DECLARE_SplitList
 253         CDSUNIT_DECLARE_SplitList_nogc
 254         CDSUNIT_DECLARE_SkipListMap
 255         CDSUNIT_DECLARE_SkipListMap_nogc
 256         CDSUNIT_DECLARE_EllenBinTreeMap
 257         CDSUNIT_DECLARE_BronsonAVLTreeMap
 258         CDSUNIT_DECLARE_FeldmanHashMap
 259         CDSUNIT_DECLARE_StripedMap
 260         CDSUNIT_DECLARE_RefinableMap
 261         CDSUNIT_DECLARE_CuckooMap
 262         CDSUNIT_DECLARE_StdMap
 263         CDSUNIT_DECLARE_StdMap_NoLock
 264
 265         CPPUNIT_TEST_SUITE_(Map_find_int, "map_find_int")
 266             CDSUNIT_TEST_MichaelMap
 267             CDSUNIT_TEST_MichaelMap_nogc
 268             CDSUNIT_TEST_SplitList
 269             CDSUNIT_TEST_SplitList_nogc
 270             CDSUNIT_TEST_SkipListMap
 271             CDSUNIT_TEST_SkipListMap_nogc
 272             CDSUNIT_TEST_EllenBinTreeMap
 273             CDSUNIT_TEST_BronsonAVLTreeMap
 274             CDSUNIT_TEST_FeldmanHashMap
 275             CDSUNIT_TEST_CuckooMap
 276             CDSUNIT_TEST_StripedMap
 277             CDSUNIT_TEST_RefinableMap
 278             CDSUNIT_TEST_StdMap
 279             CDSUNIT_TEST_StdMap_NoLock
 280         CPPUNIT_TEST_SUITE_END();
 281     };
 282 } // namespace map