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