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