test/stress/map/insdel_string/map_insdel_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 #define TEST_CASE(TAG, X)  void X();
  36
  37     class Map_InsDel_string: public cds_test::stress_fixture
  38     {
  39     public:
  40         static size_t s_nMapSize;           // map size
  41         static size_t s_nInsertThreadCount; // count of insertion thread
  42         static size_t s_nDeleteThreadCount; // count of deletion thread
  43         static size_t s_nThreadPassCount;   // pass count for each thread
  44         static size_t s_nMaxLoadFactor;     // maximum load factor
  45
  46         static size_t s_nCuckooInitialSize;         // initial size for CuckooMap
  47         static size_t s_nCuckooProbesetSize;        // CuckooMap probeset size (only for list-based probeset)
  48         static size_t s_nCuckooProbesetThreshold;   // CuckooMap probeset threshold (o - use default)
  49
  50         static size_t s_nFeldmanMap_HeadBits;
  51         static size_t s_nFeldmanMap_ArrayBits;
  52
  53         static size_t  s_nLoadFactor;  // current load factor
  54
  55         static void SetUpTestCase();
  56         static void TearDownTestCase();
  57
  58         static void setup_test_case();
  59         static std::vector<size_t> get_load_factors();
  60
  61         typedef std::string key_type;
  62         typedef size_t      value_type;
  63
  64         static std::vector<std::string> s_arrKeys;
  65
  66     protected:
  67         enum {
  68             insert_thread,
  69             delete_thread
  70         };
  71
  72         template <class Map>
  73         class Inserter: public cds_test::thread
  74         {
  75             typedef cds_test::thread base_class;
  76             Map&     m_Map;
  77
  78         public:
  79             size_t  m_nInsertSuccess = 0;
  80             size_t  m_nInsertFailed = 0;
  81
  82         public:
  83             Inserter( cds_test::thread_pool& pool, Map& map )
  84                 : base_class( pool, insert_thread )
  85                 , m_Map( map )
  86             {}
  87
  88             Inserter( Inserter& src )
  89                 : base_class( src )
  90                 , m_Map( src.m_Map )
  91             {}
  92
  93             virtual thread * clone()
  94             {
  95                 return new Inserter( *this );
  96             }
  97
  98             virtual void test()
  99             {
 100                 Map& rMap = m_Map;
 101
 102                 if ( id() & 1 ) {
 103                     for ( size_t nPass = 0; nPass < s_nThreadPassCount; ++nPass ) {
 104                         for ( auto it = s_arrKeys.cbegin(), itEnd = s_arrKeys.cend(); it != itEnd; ++it ) {
 105                             if ( rMap.insert( *it, 0 ))
 106                                 ++m_nInsertSuccess;
 107                             else
 108                                 ++m_nInsertFailed;
 109                         }
 110                     }
 111                 }
 112                 else {
 113                     for ( size_t nPass = 0; nPass < s_nThreadPassCount; ++nPass ) {
 114                         for ( auto it = s_arrKeys.crbegin(), itEnd = s_arrKeys.crend(); it != itEnd; ++it ) {
 115                             if ( rMap.insert( *it, 1 ))
 116                                 ++m_nInsertSuccess;
 117                             else
 118                                 ++m_nInsertFailed;
 119                         }
 120                     }
 121                 }
 122             }
 123         };
 124
 125         template <class Map>
 126         class Deleter: public cds_test::thread
 127         {
 128             typedef cds_test::thread base_class;
 129             Map&     m_Map;
 130
 131         public:
 132             size_t  m_nDeleteSuccess = 0;
 133             size_t  m_nDeleteFailed = 0;
 134
 135         public:
 136             Deleter( cds_test::thread_pool& pool, Map& map )
 137                 : base_class( pool, delete_thread )
 138                 , m_Map( map )
 139             {}
 140
 141             Deleter( Deleter& src )
 142                 : base_class( src )
 143                 , m_Map( src.m_Map )
 144             {}
 145
 146             virtual thread * clone()
 147             {
 148                 return new Deleter( *this );
 149             }
 150
 151             virtual void test()
 152             {
 153                 Map& rMap = m_Map;
 154
 155                 if ( id() & 1 ) {
 156                     for ( size_t nPass = 0; nPass < s_nThreadPassCount; ++nPass ) {
 157                         for ( auto it = s_arrKeys.cbegin(), itEnd = s_arrKeys.cend(); it != itEnd; ++it ) {
 158                             if ( rMap.erase( *it ))
 159                                 ++m_nDeleteSuccess;
 160                             else
 161                                 ++m_nDeleteFailed;
 162                         }
 163                     }
 164                 }
 165                 else {
 166                     for ( size_t nPass = 0; nPass < s_nThreadPassCount; ++nPass ) {
 167                         for ( auto it = s_arrKeys.crbegin(), itEnd = s_arrKeys.crend(); it != itEnd; ++it ) {
 168                             if ( rMap.erase( *it ))
 169                                 ++m_nDeleteSuccess;
 170                             else
 171                                 ++m_nDeleteFailed;
 172                         }
 173                     }
 174                 }
 175             }
 176         };
 177
 178     protected:
 179         template <typename Hash>
 180         static void fill_string_array();
 181
 182         template <class Map>
 183         void do_test( Map& testMap )
 184         {
 185             typedef Inserter<Map>       inserter;
 186             typedef Deleter<Map>        deleter;
 187
 188             cds_test::thread_pool& pool = get_pool();
 189             pool.add( new inserter( pool, testMap ), s_nInsertThreadCount );
 190             pool.add( new deleter( pool, testMap ), s_nDeleteThreadCount );
 191
 192             propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
 193                 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
 194                 << std::make_pair( "pass_count", s_nThreadPassCount )
 195                 << std::make_pair( "map_size", s_nMapSize );
 196
 197             std::chrono::milliseconds duration = pool.run();
 198
 199             propout() << std::make_pair( "duration", duration );
 200
 201             size_t nInsertSuccess = 0;
 202             size_t nInsertFailed = 0;
 203             size_t nDeleteSuccess = 0;
 204             size_t nDeleteFailed = 0;
 205
 206             for ( size_t i = 0; i < pool.size(); ++i ) {
 207                 cds_test::thread& thr = pool.get( i );
 208                 switch ( thr.type() ) {
 209                 case insert_thread:
 210                 {
 211                     inserter& t = static_cast<inserter&>(thr);
 212                     nInsertSuccess += t.m_nInsertSuccess;
 213                     nInsertFailed += t.m_nInsertFailed;
 214                 }
 215                 break;
 216                 case delete_thread:
 217                 {
 218                     deleter& t = static_cast<deleter&>(thr);
 219                     nDeleteSuccess += t.m_nDeleteSuccess;
 220                     nDeleteFailed += t.m_nDeleteFailed;
 221                 }
 222                 break;
 223                 default:
 224                     assert( false );
 225                 }
 226             }
 227
 228             propout()
 229                 << std::make_pair( "insert_success", nInsertSuccess )
 230                 << std::make_pair( "insert_failed", nInsertFailed )
 231                 << std::make_pair( "delete_success", nDeleteSuccess )
 232                 << std::make_pair( "delete_failed", nDeleteFailed )
 233                 << std::make_pair( "finish_map_size", testMap.size() );
 234
 235             check_before_cleanup( testMap );
 236
 237             testMap.clear();
 238             EXPECT_TRUE( testMap.empty() );
 239
 240             additional_check( testMap );
 241             print_stat( propout(), testMap );
 242             additional_cleanup( testMap );
 243         }
 244
 245         template <class Map>
 246         void run_test()
 247         {
 248             Map testMap( *this );
 249             do_test( testMap );
 250         }
 251     };
 252
 253     class Map_InsDel_string_stdhash: public Map_InsDel_string
 254     {
 255     public:
 256         static void SetUpTestCase();
 257
 258         template <class Map>
 259         void run_test()
 260         {
 261             Map_InsDel_string::run_test<Map>();
 262         }
 263     };
 264
 265 #if CDS_BUILD_BITS == 64
 266     class Map_InsDel_string_city32: public Map_InsDel_string
 267     {
 268     public:
 269         static void SetUpTestCase();
 270
 271         template <class Map>
 272         void run_test()
 273         {
 274             Map_InsDel_string::run_test<Map>();
 275         }
 276     };
 277
 278     class Map_InsDel_string_city64: public Map_InsDel_string
 279     {
 280     public:
 281         static void SetUpTestCase();
 282
 283         template <class Map>
 284         void run_test()
 285         {
 286             Map_InsDel_string::run_test<Map>();
 287         }
 288     };
 289
 290     class Map_InsDel_string_city128: public Map_InsDel_string
 291     {
 292     public:
 293         static void SetUpTestCase();
 294
 295         template <class Map>
 296         void run_test()
 297         {
 298             Map_InsDel_string::run_test<Map>();
 299         }
 300     };
 301
 302 #endif // #if CDS_BUILD_BITS == 64
 303
 304     class Map_InsDel_string_LF: public Map_InsDel_string
 305         , public ::testing::WithParamInterface<size_t>
 306     {
 307     public:
 308         template <class Map>
 309         void run_test()
 310         {
 311             s_nLoadFactor = GetParam();
 312             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 313             Map_InsDel_string::run_test<Map>();
 314         }
 315     };
 316
 317 } // namespace map