test/stress/map/find_string/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 "map_type.h"
  32
  33 namespace map {
  34
  35     class Map_find_string: public cds_test::stress_fixture
  36     {
  37     public:
  38         static size_t s_nThreadCount;       // thread count
  39         static size_t s_nMapSize;           // map size (count of searching item)
  40         static size_t s_nPercentExists;     // percent of existing keys in searching sequence
  41         static size_t s_nPassCount;
  42         static size_t s_nMaxLoadFactor;     // maximum load factor
  43
  44         static size_t s_nCuckooInitialSize;         // initial size for CuckooMap
  45         static size_t s_nCuckooProbesetSize;        // CuckooMap probeset size (only for list-based probeset)
  46         static size_t s_nCuckooProbesetThreshold;   // CUckooMap probeset threshold (o - use default)
  47
  48         static size_t s_nFeldmanMap_HeadBits;
  49         static size_t s_nFeldmanMap_ArrayBits;
  50
  51         static size_t s_nLoadFactor;  // current load factor
  52
  53         typedef std::string  key_type;
  54         struct value_type {
  55             std::string const* pKey;
  56             bool        bExists ;   // true - key in map, false - key not in map
  57         };
  58
  59         typedef std::vector<value_type> value_vector;
  60         static std::vector<std::string> s_arrString;
  61         static value_vector s_Data;
  62
  63         static void SetUpTestCase();
  64         static void TearDownTestCase();
  65
  66         static void setup_test_case();
  67         static std::vector<size_t> get_load_factors();
  68
  69     private:
  70         template <typename Iterator, typename Map>
  71         static bool check_result( Iterator const& it, Map const& map )
  72         {
  73             return it != map.end();
  74         }
  75         template <typename Map>
  76         static bool check_result( bool b, Map const& )
  77         {
  78             return b;
  79         }
  80
  81         template <class Map>
  82         class Worker: public cds_test::thread
  83         {
  84             typedef cds_test::thread base_class;
  85             Map&     m_Map;
  86
  87         public:
  88             struct Stat {
  89                 size_t      nSuccess = 0;
  90                 size_t      nFailed = 0;
  91             };
  92
  93             Stat    m_KeyExists;
  94             Stat    m_KeyNotExists;
  95
  96         public:
  97             Worker( cds_test::thread_pool& pool, Map& map )
  98                 : base_class( pool )
  99                 , m_Map( map )
 100             {}
 101
 102             Worker( Worker& src )
 103                 : base_class( src )
 104                 , m_Map( src.m_Map )
 105             {}
 106
 107             virtual thread * clone()
 108             {
 109                 return new Worker( *this );
 110             }
 111             virtual void test()
 112             {
 113                 size_t const nPassCount = s_nPassCount;
 114
 115                 Map& rMap = m_Map;
 116                 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 117                     if ( id() & 1 ) {
 118                         auto itEnd = s_Data.cend();
 119                         for ( auto it = s_Data.cbegin(); it != itEnd; ++it ) {
 120                             auto bFound = rMap.contains( *(it->pKey) );
 121                             if ( it->bExists ) {
 122                                 if ( check_result(bFound, rMap))
 123                                     ++m_KeyExists.nSuccess;
 124                                 else
 125                                     ++m_KeyExists.nFailed;
 126                             }
 127                             else {
 128                                 if ( check_result(bFound, rMap))
 129                                     ++m_KeyNotExists.nFailed;
 130                                 else
 131                                     ++m_KeyNotExists.nSuccess;
 132                             }
 133                         }
 134                     }
 135                     else {
 136                         auto itEnd = s_Data.crend();
 137                         for ( auto it = s_Data.crbegin(); it != itEnd; ++it ) {
 138                             auto bFound = rMap.contains( *(it->pKey) );
 139                             if ( it->bExists ) {
 140                                 if ( check_result(bFound, rMap))
 141                                     ++m_KeyExists.nSuccess;
 142                                 else
 143                                     ++m_KeyExists.nFailed;
 144                             }
 145                             else {
 146                                 if ( check_result( bFound, rMap ))
 147                                     ++m_KeyNotExists.nFailed;
 148                                 else
 149                                     ++m_KeyNotExists.nSuccess;
 150                             }
 151                         }
 152                     }
 153                 }
 154             }
 155         };
 156
 157     protected:
 158         template <typename Hash>
 159         static void fill_string_array();
 160
 161         template <class Map>
 162         void test( Map& testMap )
 163         {
 164             typedef Worker<Map> worker;
 165
 166             // Fill the map
 167             for ( size_t i = 0; i < s_Data.size(); ++i ) {
 168                 // All keys in arrData are unique, insert() must be successful
 169                 if ( s_Data[i].bExists )
 170                     EXPECT_TRUE( check_result( testMap.insert( *(s_Data[i].pKey), s_Data[i] ), testMap ));
 171             }
 172
 173             propout() << std::make_pair( "thread_count", s_nThreadCount )
 174                 << std::make_pair( "map_size", s_nMapSize )
 175                 << std::make_pair( "percent_exist", s_nPercentExists )
 176                 << std::make_pair( "pass_count", s_nPassCount );
 177
 178             cds_test::thread_pool& pool = get_pool();
 179             pool.add( new worker( pool, testMap ), s_nThreadCount );
 180
 181             std::chrono::milliseconds duration = pool.run();
 182
 183             propout() << std::make_pair( "duration", duration );
 184
 185             size_t nExistSuccess = 0;
 186             size_t nExistFailed = 0;
 187             size_t nMissingSuccess = 0;
 188             size_t nMissingFailed = 0;
 189
 190             // Postcondition: the number of success searching == the number of map item
 191             for ( size_t i = 0; i < pool.size(); ++i ) {
 192                 worker& w = static_cast<worker&>(pool.get( i ));
 193                 nExistSuccess += w.m_KeyExists.nSuccess;
 194                 nExistFailed += w.m_KeyExists.nFailed;
 195                 nMissingSuccess += w.m_KeyNotExists.nSuccess;
 196                 nMissingFailed += w.m_KeyNotExists.nFailed;
 197
 198                 EXPECT_EQ( w.m_KeyExists.nSuccess, s_nMapSize * s_nPassCount ) << "thread " << i;
 199                 EXPECT_EQ( w.m_KeyExists.nFailed, 0 ) << "thread " << i;
 200                 EXPECT_EQ( w.m_KeyNotExists.nSuccess, (s_Data.size() - s_nMapSize) * s_nPassCount ) << "thread " << i;
 201                 EXPECT_EQ( w.m_KeyNotExists.nFailed, 0 ) << "thread " << i;
 202             }
 203
 204             check_before_cleanup( testMap );
 205
 206             testMap.clear();
 207             additional_check( testMap );
 208             print_stat( propout(), testMap );
 209             additional_cleanup( testMap );
 210         }
 211
 212         template <class Map>
 213         void run_test()
 214         {
 215             ASSERT_GT( s_Data.size(), 0 );
 216
 217             Map testMap( *this );
 218             test( testMap );
 219         }
 220     };
 221
 222     class Map_find_string_stdhash: public Map_find_string
 223     {
 224     public:
 225         static void SetUpTestCase();
 226
 227         template <class Map>
 228         void run_test()
 229         {
 230             Map_find_string::run_test<Map>();
 231         }
 232     };
 233
 234 #if CDS_BUILD_BITS == 64
 235     class Map_find_string_city32: public Map_find_string
 236     {
 237     public:
 238         static void SetUpTestCase();
 239
 240         template <class Map>
 241         void run_test()
 242         {
 243             Map_find_string::run_test<Map>();
 244         }
 245     };
 246
 247     class Map_find_string_city64: public Map_find_string
 248     {
 249     public:
 250         static void SetUpTestCase();
 251
 252         template <class Map>
 253         void run_test()
 254         {
 255             Map_find_string::run_test<Map>();
 256         }
 257     };
 258
 259     class Map_find_string_city128: public Map_find_string
 260     {
 261     public:
 262         static void SetUpTestCase();
 263
 264         template <class Map>
 265         void run_test()
 266         {
 267             Map_find_string::run_test<Map>();
 268         }
 269     };
 270
 271 #endif // #if CDS_BUILD_BITS == 64
 272
 273     class Map_find_string_LF: public Map_find_string
 274         , public ::testing::WithParamInterface<size_t>
 275     {
 276     public:
 277         template <class Map>
 278         void run_test()
 279         {
 280             s_nLoadFactor = GetParam();
 281             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 282             Map_find_string::run_test<Map>();
 283         }
 284     };
 285
 286 } // namespace map