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