test/stress/sequential/sequential-map/insdelfind/map_insdelfind.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
  36     class Map_InsDelFind: public cds_test::stress_fixture
  37     {
  38     public:
  39         static size_t s_nMapSize;           // initial map size
  40
  41         static size_t s_nPassCount;
  42         static size_t s_nBronsonAVLTreeMapPassCount;
  43
  44         static size_t s_nHpEllenBinTreeMapPassCount;
  45         static size_t s_nHpFeldmanPassCount;
  46         static size_t s_nHpMichaelMapPassCount;
  47         static size_t s_nHpSkipListMapPassCount;
  48         static size_t s_nHpSplitListMapPassCount;
  49
  50         static size_t s_nRcuEllenBinTreeMapPassCount;
  51         static size_t s_nRcuFeldmanPassCount;
  52         static size_t s_nRcuMichaelMapPassCount;
  53         static size_t s_nRcuSkipListMapPassCount;
  54         static size_t s_nRcuSplitListMapPassCount;
  55
  56
  57         static size_t s_nThreadCount;       // thread count
  58         static size_t s_nMaxLoadFactor;     // maximum load factor
  59         static unsigned int s_nInsertPercentage;
  60         static unsigned int s_nDeletePercentage;
  61         static unsigned int s_nDuration;    // test duration, seconds
  62
  63         static size_t s_nCuckooInitialSize;         // initial size for CuckooMap
  64         static size_t s_nCuckooProbesetSize;        // CuckooMap probeset size (only for list-based probeset)
  65         static size_t s_nCuckooProbesetThreshold;   // CuckooMap probeset threshold (o - use default)
  66
  67         static size_t s_nFeldmanMap_HeadBits;
  68         static size_t s_nFeldmanMap_ArrayBits;
  69
  70         static size_t  s_nLoadFactor;  // current load factor
  71
  72         static void SetUpTestCase();
  73         //static void TearDownTestCase();
  74
  75     public:
  76         enum actions
  77         {
  78             do_find,
  79             do_insert,
  80             do_delete
  81         };
  82         static const unsigned int c_nShuffleSize = 100;
  83         static actions s_arrShuffle[c_nShuffleSize];
  84
  85     protected:
  86         typedef size_t  key_type;
  87         typedef size_t  value_type;
  88
  89         template <class Map>
  90         class Worker: public cds_test::thread
  91         {
  92             typedef cds_test::thread base_class;
  93             Map&     m_Map;
  94
  95         public:
  96             size_t  m_nInsertSuccess = 0;
  97             size_t  m_nInsertFailed = 0;
  98             size_t  m_nDeleteSuccess = 0;
  99             size_t  m_nDeleteFailed = 0;
 100             size_t  m_nFindSuccess = 0;
 101             size_t  m_nFindFailed = 0;
 102
 103         public:
 104             Worker( cds_test::thread_pool& pool, Map& map )
 105                 : base_class( pool )
 106                 , m_Map( map )
 107             {}
 108
 109             Worker( Worker& src )
 110                 : base_class( src )
 111                 , m_Map( src.m_Map )
 112             {}
 113
 114             virtual thread * clone()
 115             {
 116                 return new Worker( *this );
 117             }
 118
 119             typedef std::pair< key_type const, value_type > map_value_type;
 120
 121             struct update_functor {
 122                 template <typename Q>
 123                 void operator()( bool /*bNew*/, map_value_type& /*cur*/, Q const& /*val*/ ) const
 124                 {}
 125
 126                 // FeldmanHashMap
 127                 void operator()( map_value_type& /*cur*/, map_value_type* /*old*/) const
 128                 {}
 129
 130                 // MichaelMap
 131                 void operator()( bool /*bNew*/, map_value_type& /*cur*/ ) const
 132                 {}
 133
 134                 // BronsonAVLTreeMap
 135                 void operator()( bool /*bNew*/, key_type /*key*/, value_type& /*val*/ ) const
 136                 {}
 137             };
 138
 139             virtual void test()
 140             {
 141                 Map& rMap = m_Map;
 142                 size_t pass_count = Map_InsDelFind::s_nPassCount;
 143
 144                 size_t nInsertedNum = 0;
 145                 size_t nUninsertedNum = 0;
 146                 for (size_t count = 0; count < pass_count; count++) {
 147                   bool shouldUpdate = true;
 148                   for (size_t i = 0; i < s_nMapSize; ++i) {
 149                     // The number to operate on the map.
 150                     size_t n = i;
 151                     // Insert
 152                     if (i % s_nInsertPercentage == 1) {
 153                       nInsertedNum++;
 154                       if (!shouldUpdate) {
 155                         if (rMap.insert(n, n))
 156                           ++m_nInsertSuccess;
 157                         else
 158                           ++m_nInsertFailed;
 159                         shouldUpdate = true;
 160                       } else {
 161                         if (rMap.update(n, update_functor(), true).first)
 162                           ++m_nInsertSuccess;
 163                         else
 164                           ++m_nInsertFailed;
 165                         shouldUpdate = false;
 166                       }
 167                     } else {
 168                       nUninsertedNum++;
 169                     }
 170                     // Find
 171                     if (rMap.contains(n))
 172                       ++m_nFindSuccess;
 173                     else
 174                       ++m_nFindFailed;
 175                     // Delete
 176                     if (i % s_nInsertPercentage == 1) {
 177
 178                       if (rMap.erase(n))
 179                         ++m_nDeleteSuccess;
 180                       else
 181                         ++m_nDeleteFailed;
 182                       break;
 183                     }
 184                   }
 185                 }
 186                 EXPECT_EQ(nInsertedNum, m_nFindSuccess);
 187                 EXPECT_EQ(nUninsertedNum, m_nFindFailed);
 188                 EXPECT_EQ(m_nDeleteSuccess, nInsertedNum);
 189                 EXPECT_EQ(m_nDeleteFailed, 0);
 190             }
 191         };
 192
 193     protected:
 194         template <class Map>
 195         void do_test( Map& testMap )
 196         {
 197             typedef Worker<Map> worker;
 198             cds_test::thread_pool& pool = get_pool();
 199             std::unique_ptr<worker> worker_thrd(new worker(pool, testMap));
 200             worker_thrd->test();
 201
 202             testMap.clear();
 203             EXPECT_TRUE( testMap.empty());
 204             additional_cleanup( testMap );
 205         }
 206
 207         template <class Map>
 208         void run_test()
 209         {
 210             Map testMap( *this );
 211             do_test( testMap );
 212         }
 213
 214         template <class Map>
 215         void run_bronson_avl_tree() {
 216           Map_InsDelFind::s_nPassCount =
 217               Map_InsDelFind::s_nBronsonAVLTreeMapPassCount;
 218           run_test<Map>();
 219         }
 220
 221         template <class Map>
 222         void run_ellen_bin_tree_hp() {
 223           Map_InsDelFind::s_nPassCount =
 224               Map_InsDelFind::s_nHpEllenBinTreeMapPassCount;
 225           run_test<Map>();
 226         }
 227
 228         template <class Map>
 229         void run_skip_list_hp() {
 230           Map_InsDelFind::s_nPassCount =
 231               Map_InsDelFind::s_nHpSkipListMapPassCount;
 232           run_test<Map>();
 233         }
 234
 235         template <class Map>
 236         void run_feldman_hp() {
 237           Map_InsDelFind::s_nPassCount =
 238               Map_InsDelFind::s_nHpFeldmanPassCount;
 239           run_test<Map>();
 240         }
 241
 242         template <class Map>
 243         void run_ellen_bin_tree_rcu() {
 244           Map_InsDelFind::s_nPassCount =
 245               Map_InsDelFind::s_nRcuEllenBinTreeMapPassCount;
 246           run_test<Map>();
 247         }
 248
 249         template <class Map>
 250         void run_skip_list_rcu() {
 251           Map_InsDelFind::s_nPassCount =
 252               Map_InsDelFind::s_nRcuSkipListMapPassCount;
 253           run_test<Map>();
 254         }
 255
 256         template <class Map>
 257         void run_feldman_rcu() {
 258           Map_InsDelFind::s_nPassCount =
 259               Map_InsDelFind::s_nRcuFeldmanPassCount;
 260           run_test<Map>();
 261         }
 262     };
 263
 264     class Map_InsDelFind_LF: public Map_InsDelFind
 265         , public ::testing::WithParamInterface<size_t>
 266     {
 267     public:
 268         template <class Map>
 269         void run_test()
 270         {
 271             s_nLoadFactor = GetParam();
 272             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 273             Map_InsDelFind::run_test<Map>();
 274         }
 275
 276                                 template <class Map>
 277         void run_michael_hp() {
 278           Map_InsDelFind::s_nPassCount =
 279               Map_InsDelFind::s_nHpMichaelMapPassCount;
 280           Map_InsDelFind_LF::run_test<Map>();
 281         }
 282
 283         template <class Map>
 284         void run_split_list_hp() {
 285           Map_InsDelFind::s_nPassCount =
 286               Map_InsDelFind::s_nHpSplitListMapPassCount;
 287           Map_InsDelFind_LF::run_test<Map>();
 288         }
 289
 290         template <class Map>
 291         void run_michael_rcu() {
 292           Map_InsDelFind::s_nPassCount =
 293               Map_InsDelFind::s_nRcuMichaelMapPassCount;
 294           Map_InsDelFind_LF::run_test<Map>();
 295         }
 296
 297         template <class Map>
 298         void run_split_list_rcu() {
 299           Map_InsDelFind::s_nPassCount =
 300               Map_InsDelFind::s_nRcuSplitListMapPassCount;
 301           Map_InsDelFind_LF::run_test<Map>();
 302         }
 303
 304         static std::vector<size_t> get_load_factors();
 305     };
 306
 307 } // namespace map