test/stress/sequential/sequential-set/insdel_find/set_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 "set_type.h"
  32
  33 namespace set {
  34
  35     class Set_InsDelFind: public cds_test::stress_fixture
  36     {
  37     public:
  38         static size_t s_nSetSize;           // initial set size
  39         static size_t s_nPassCount;           // initial set size
  40         static size_t s_nBronsonAVLTreeMapPassCount;
  41         static size_t s_nEllenBinTreeMapPassCount;
  42         static size_t s_nFeldmanPassCount;
  43         static size_t s_nMichaelMapPassCount;
  44         static size_t s_nSkipListMapPassCount;
  45         static size_t s_nSplitListMapPassCount;
  46
  47         static size_t s_nThreadCount;       // thread count
  48         static size_t s_nMaxLoadFactor;     // maximum load factor
  49         static unsigned int s_nInsertPercentage;
  50         static unsigned int s_nDeletePercentage;
  51         static unsigned int s_nDuration;   // test duration, seconds
  52
  53         static size_t  s_nCuckooInitialSize;        // initial size for CuckooSet
  54         static size_t  s_nCuckooProbesetSize;       // CuckooSet probeset size (only for list-based probeset)
  55         static size_t  s_nCuckooProbesetThreshold;  // CUckooSet probeset threshold (0 - use default)
  56
  57         static size_t s_nFeldmanSet_HeadBits;
  58         static size_t s_nFeldmanSet_ArrayBits;
  59
  60         static size_t s_nLoadFactor;
  61
  62         static void SetUpTestCase();
  63         //static void TearDownTestCase();
  64
  65     public:
  66         enum actions
  67         {
  68             do_find,
  69             do_insert,
  70             do_delete
  71         };
  72         static const unsigned int c_nShuffleSize = 100;
  73         static actions s_arrShuffle[c_nShuffleSize];
  74
  75     protected:
  76         typedef size_t  key_type;
  77         typedef size_t  value_type;
  78
  79         template <class Set>
  80         class Worker: public cds_test::thread
  81         {
  82             typedef cds_test::thread base_class;
  83             Set&     m_Set;
  84
  85         public:
  86             size_t  m_nInsertSuccess = 0;
  87             size_t  m_nInsertFailed = 0;
  88             size_t  m_nDeleteSuccess = 0;
  89             size_t  m_nDeleteFailed = 0;
  90             size_t  m_nFindSuccess = 0;
  91             size_t  m_nFindFailed = 0;
  92
  93         public:
  94             Worker( cds_test::thread_pool& pool, Set& set )
  95                 : base_class( pool )
  96                 , m_Set( set )
  97             {}
  98
  99             Worker( Worker& src )
 100                 : base_class( src )
 101                 , m_Set( src.m_Set )
 102             {}
 103
 104             virtual thread * clone()
 105             {
 106                 return new Worker( *this );
 107             }
 108
 109             virtual void test()
 110             {
 111                 Set& rSet = m_Set;
 112                 Set_InsDelFind& fixture = pool().template fixture<Set_InsDelFind>();
 113
 114                 unsigned int i = 0;
 115                 size_t const nNormalize = size_t(-1) / ( fixture.s_nSetSize * 2);
 116                 size_t pass_count = fixture.s_nPassCount;
 117
 118                 size_t nRand = 0;
 119                 while ( pass_count-- ) {
 120                     nRand = cds::bitop::RandXorShift(nRand);
 121                     size_t n = nRand / nNormalize;
 122                     switch ( s_arrShuffle[i] ) {
 123                     case do_find:
 124                         if ( rSet.contains( n ))
 125                             ++m_nFindSuccess;
 126                         else
 127                             ++m_nFindFailed;
 128                         break;
 129                     case do_insert:
 130                         if ( rSet.insert( n ))
 131                             ++m_nInsertSuccess;
 132                         else
 133                             ++m_nInsertFailed;
 134                         break;
 135                     case do_delete:
 136                         if ( rSet.erase( n ))
 137                             ++m_nDeleteSuccess;
 138                         else
 139                             ++m_nDeleteFailed;
 140                         break;
 141                     }
 142
 143                     if ( ++i >= c_nShuffleSize )
 144                         i = 0;
 145                 }
 146             }
 147         };
 148
 149     protected:
 150         template <class Set>
 151         void do_test( Set& testSet )
 152         {
 153             typedef Worker<Set> work_thread;
 154
 155             // fill map - only odd number
 156             {
 157                 size_t * pInitArr = new size_t[ s_nSetSize ];
 158                 size_t * pEnd = pInitArr + s_nSetSize;
 159                 for ( size_t i = 0; i < s_nSetSize; ++i )
 160                     pInitArr[i] = i * 2 + 1;
 161                 shuffle( pInitArr, pEnd );
 162                 for ( size_t * p = pInitArr; p < pEnd; ++p )
 163                     testSet.insert( typename Set::value_type( *p, *p ));
 164                 delete [] pInitArr;
 165             }
 166
 167             s_nThreadCount = 1;
 168             cds_test::thread_pool& pool = get_pool();
 169             std::unique_ptr<work_thread> worker(new work_thread(pool, testSet));
 170             worker->test();
 171
 172             propout() << std::make_pair( "thread_count", s_nThreadCount )
 173                 << std::make_pair( "set_size", s_nSetSize )
 174                 << std::make_pair( "insert_percentage", s_nInsertPercentage )
 175                 << std::make_pair( "delete_percentage", s_nDeletePercentage )
 176                 << std::make_pair( "total_duration", s_nDuration );
 177
 178             size_t nInsertSuccess = 0;
 179             size_t nInsertFailed = 0;
 180             size_t nDeleteSuccess = 0;
 181             size_t nDeleteFailed = 0;
 182             size_t nFindSuccess = 0;
 183             size_t nFindFailed = 0;
 184             work_thread &thr = *worker;
 185             nInsertSuccess += thr.m_nInsertSuccess;
 186             nInsertFailed += thr.m_nInsertFailed;
 187             nDeleteSuccess += thr.m_nDeleteSuccess;
 188             nDeleteFailed += thr.m_nDeleteFailed;
 189             nFindSuccess += thr.m_nFindSuccess;
 190             nFindFailed += thr.m_nFindFailed;
 191
 192             propout()
 193                 << std::make_pair( "insert_success", nInsertSuccess )
 194                 << std::make_pair( "insert_failed", nInsertFailed )
 195                 << std::make_pair( "delete_success", nDeleteSuccess )
 196                 << std::make_pair( "delete_failed", nDeleteFailed )
 197                 << std::make_pair( "find_success", nFindSuccess )
 198                 << std::make_pair( "find_failed", nFindFailed );
 199
 200             testSet.clear();
 201             EXPECT_TRUE( testSet.empty()) << "set size=" << testSet.size();
 202
 203             additional_check( testSet );
 204             print_stat( propout(), testSet );
 205             additional_cleanup( testSet );
 206         }
 207
 208         template <class Set>
 209         void run_test()
 210         {
 211             Set s( *this );
 212             do_test( s );
 213         }
 214
 215         template <class Set>
 216         void run_bronson_avl_tree() {
 217           Set_InsDelFind::s_nPassCount =
 218               Set_InsDelFind::s_nBronsonAVLTreeMapPassCount;
 219           run_test<Set>();
 220         }
 221
 222         template <class Set>
 223         void run_ellen_bin_tree() {
 224           Set_InsDelFind::s_nPassCount =
 225               Set_InsDelFind::s_nEllenBinTreeMapPassCount;
 226           run_test<Set>();
 227         }
 228
 229         template <class Set>
 230         void run_feldman() {
 231           Set_InsDelFind::s_nPassCount =
 232               Set_InsDelFind::s_nFeldmanPassCount;
 233           run_test<Set>();
 234         }
 235
 236         template <class Set>
 237         void run_skip_list() {
 238           Set_InsDelFind::s_nPassCount =
 239               Set_InsDelFind::s_nSkipListMapPassCount;
 240           run_test<Set>();
 241         }
 242     };
 243
 244     class Set_InsDelFind_LF: public Set_InsDelFind
 245         , public ::testing::WithParamInterface<size_t>
 246     {
 247     public:
 248         template <class Set>
 249         void run_test()
 250         {
 251             s_nLoadFactor = GetParam();
 252             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 253             Set_InsDelFind::run_test<Set>();
 254         }
 255
 256         template <class Set>
 257         void run_michael() {
 258           Set_InsDelFind::s_nPassCount =
 259               Set_InsDelFind::s_nMichaelMapPassCount;
 260           Set_InsDelFind_LF::run_test<Set>();
 261         }
 262
 263         template <class Set>
 264         void run_split_list() {
 265           Set_InsDelFind::s_nPassCount =
 266               Set_InsDelFind::s_nSplitListMapPassCount;
 267           Set_InsDelFind_LF::run_test<Set>();
 268         }
 269
 270         static std::vector<size_t> get_load_factors();
 271     };
 272
 273 } // namespace set