test/stress/parallel/parallel-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-2017
   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_nBronsonAVLTreeMapPassCount;
  45         static size_t s_nEllenBinTreeMapPassCount;
  46         static size_t s_nFeldmanPassCount;
  47         static size_t s_nMichaelMapPassCount;
  48         static size_t s_nSkipListMapPassCount;
  49         static size_t s_nSplitListMapPassCount;
  50
  51         static size_t s_nMaxLoadFactor;     // maximum load factor
  52
  53         static size_t s_nCuckooInitialSize;         // initial size for CuckooMap
  54         static size_t s_nCuckooProbesetSize;        // CuckooMap probeset size (only for list-based probeset)
  55         static size_t s_nCuckooProbesetThreshold;   // CuckooMap probeset threshold (o - use default)
  56
  57         static size_t s_nFeldmanMap_HeadBits;
  58         static size_t s_nFeldmanMap_ArrayBits;
  59
  60         static size_t  s_nLoadFactor;  // current load factor
  61
  62         static void SetUpTestCase();
  63         static void TearDownTestCase();
  64
  65         static void setup_test_case();
  66         static std::vector<size_t> get_load_factors();
  67
  68         typedef std::string key_type;
  69         typedef size_t      value_type;
  70
  71         static std::vector<std::string> s_arrKeys;
  72
  73     protected:
  74         enum {
  75             insert_thread,
  76             delete_thread
  77         };
  78
  79         template <class Map>
  80         class Inserter: public cds_test::thread
  81         {
  82             typedef cds_test::thread base_class;
  83             Map&     m_Map;
  84
  85         public:
  86             size_t  m_nInsertSuccess = 0;
  87             size_t  m_nInsertFailed = 0;
  88
  89         public:
  90             Inserter( cds_test::thread_pool& pool, Map& map )
  91                 : base_class( pool, insert_thread )
  92                 , m_Map( map )
  93             {}
  94
  95             Inserter( Inserter& src )
  96                 : base_class( src )
  97                 , m_Map( src.m_Map )
  98             {}
  99
 100             virtual thread * clone()
 101             {
 102                 return new Inserter( *this );
 103             }
 104
 105             virtual void test()
 106             {
 107                 Map& rMap = m_Map;
 108
 109                 for (auto it = s_arrKeys.cbegin(), itEnd = s_arrKeys.cend();
 110                      it != itEnd; ++it) {
 111                   if (rMap.insert(*it, 0))
 112                     ++m_nInsertSuccess;
 113                   else
 114                     ++m_nInsertFailed;
 115                 }
 116             }
 117         };
 118
 119         template <class Map>
 120         class Deleter: public cds_test::thread
 121         {
 122             typedef cds_test::thread base_class;
 123             Map&     m_Map;
 124
 125         public:
 126             size_t  m_nDeleteSuccess = 0;
 127             size_t  m_nDeleteFailed = 0;
 128
 129         public:
 130             Deleter( cds_test::thread_pool& pool, Map& map )
 131                 : base_class( pool, delete_thread )
 132                 , m_Map( map )
 133             {}
 134
 135             Deleter( Deleter& src )
 136                 : base_class( src )
 137                 , m_Map( src.m_Map )
 138             {}
 139
 140             virtual thread * clone()
 141             {
 142                 return new Deleter( *this );
 143             }
 144
 145             virtual void test()
 146             {
 147                 Map& rMap = m_Map;
 148
 149                 for (auto it = s_arrKeys.cbegin(), itEnd = s_arrKeys.cend();
 150                      it != itEnd; ++it) {
 151                   if (rMap.erase(*it))
 152                     ++m_nDeleteSuccess;
 153                   else
 154                     ++m_nDeleteFailed;
 155                 }
 156             }
 157         };
 158
 159     protected:
 160         template <typename Hash>
 161         static void fill_string_array();
 162
 163         template <class Map>
 164         void do_test( Map& testMap )
 165         {
 166             typedef Inserter<Map>       inserter;
 167             typedef Deleter<Map>        deleter;
 168
 169             cds_test::thread_pool& pool = get_pool();
 170             std::unique_ptr<inserter> inserter_thrd(
 171                 new inserter(pool, testMap));
 172             std::unique_ptr<deleter> deleter_thrd(
 173                 new deleter(pool, testMap));
 174             for (size_t nPass = 0; nPass < s_nThreadPassCount; ++nPass) {
 175               inserter_thrd->test();
 176               deleter_thrd->test();
 177             }
 178
 179             // testMap.clear();
 180             for ( auto const& str: s_arrKeys )
 181                 testMap.erase( str );
 182             EXPECT_TRUE( testMap.empty());
 183             EXPECT_EQ( testMap.size(), 0u );
 184             additional_cleanup( testMap );
 185         }
 186
 187         template <class Map>
 188         void run_test()
 189         {
 190             Map testMap( *this );
 191             do_test( testMap );
 192         }
 193
 194                                 template <class Map>
 195         void run_bronson_avl_tree() {
 196           Map_InsDel_string::s_nThreadPassCount =
 197               Map_InsDel_string::s_nBronsonAVLTreeMapPassCount;
 198           run_test<Map>();
 199         }
 200
 201         template <class Map>
 202         void run_ellen_bin_tree() {
 203           Map_InsDel_string::s_nThreadPassCount =
 204               Map_InsDel_string::s_nEllenBinTreeMapPassCount;
 205           run_test<Map>();
 206         }
 207
 208                                 template <class Map>
 209         void run_feldman() {
 210           Map_InsDel_string::s_nThreadPassCount =
 211               Map_InsDel_string::s_nFeldmanPassCount;
 212           run_test<Map>();
 213         }
 214
 215         template <class Map>
 216         void run_michael() {
 217           Map_InsDel_string::s_nThreadPassCount =
 218               Map_InsDel_string::s_nMichaelMapPassCount;
 219           run_test<Map>();
 220         }
 221
 222         template <class Map>
 223         void run_skip_list() {
 224           Map_InsDel_string::s_nThreadPassCount =
 225               Map_InsDel_string::s_nSkipListMapPassCount;
 226           run_test<Map>();
 227         }
 228
 229         template <class Map>
 230         void run_split_list() {
 231           Map_InsDel_string::s_nThreadPassCount =
 232               Map_InsDel_string::s_nSplitListMapPassCount;
 233           run_test<Map>();
 234         }
 235     };
 236
 237     class Map_InsDel_string_stdhash: public Map_InsDel_string
 238     {
 239     public:
 240         static void SetUpTestCase();
 241
 242         template <class Map>
 243         void run_test()
 244         {
 245             Map_InsDel_string::run_test<Map>();
 246         }
 247     };
 248
 249 #if CDS_BUILD_BITS == 64
 250     class Map_InsDel_string_city32: public Map_InsDel_string
 251     {
 252     public:
 253         static void SetUpTestCase();
 254
 255         template <class Map>
 256         void run_test()
 257         {
 258             Map_InsDel_string::run_test<Map>();
 259         }
 260     };
 261
 262     class Map_InsDel_string_city64: public Map_InsDel_string
 263     {
 264     public:
 265         static void SetUpTestCase();
 266
 267         template <class Map>
 268         void run_test()
 269         {
 270             Map_InsDel_string::run_test<Map>();
 271         }
 272     };
 273
 274     class Map_InsDel_string_city128: public Map_InsDel_string
 275     {
 276     public:
 277         static void SetUpTestCase();
 278
 279         template <class Map>
 280         void run_test()
 281         {
 282             Map_InsDel_string::run_test<Map>();
 283         }
 284     };
 285
 286 #endif // #if CDS_BUILD_BITS == 64
 287
 288     class Map_InsDel_string_LF: public Map_InsDel_string
 289         , public ::testing::WithParamInterface<size_t>
 290     {
 291     public:
 292         template <class Map>
 293         void run_test()
 294         {
 295             s_nLoadFactor = GetParam();
 296             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 297             Map_InsDel_string::run_test<Map>();
 298         }
 299     };
 300
 301 } // namespace map