tests/unit/map2/map_insfind_int.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-2016
   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 "map2/map_type.h"
  32 #include "cppunit/thread.h"
  33
  34 #include <cds/os/topology.h>
  35 #include <vector>
  36
  37 namespace map2 {
  38
  39 #define TEST_CASE(TAG, X)  void X();
  40
  41     class Map_InsFind_int: public CppUnitMini::TestCase
  42     {
  43     public:
  44         size_t c_nThreadCount = 8;     // thread count
  45         size_t c_nMapSize = 5000;      // map size (count of searching item)
  46         size_t c_nMaxLoadFactor = 8;   // maximum load factor
  47         bool   c_bPrintGCState = true;
  48
  49         size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
  50         size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
  51         size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
  52
  53         size_t c_nFeldmanMap_HeadBits = 10;
  54         size_t c_nFeldmanMap_ArrayBits = 4;
  55
  56         size_t  c_nLoadFactor = 2;  // current load factor
  57
  58     private:
  59         typedef size_t  key_type;
  60         typedef size_t  value_type;
  61
  62         template <typename Iterator, typename Map>
  63         static bool check_result( Iterator const& it, Map const& map )
  64         {
  65             return it != map.end();
  66         }
  67         template <typename Map>
  68         static bool check_result( bool b, Map const& )
  69         {
  70             return b;
  71         }
  72
  73         template <class Map>
  74         class Inserter: public CppUnitMini::TestThread
  75         {
  76             Map&     m_Map;
  77             std::vector<size_t> m_arrVal;
  78
  79             virtual Inserter *    clone()
  80             {
  81                 return new Inserter( *this );
  82             }
  83
  84             void make_array()
  85             {
  86                 size_t const nThreadCount = getTest().c_nThreadCount;
  87                 size_t const nSize = getTest().c_nMapSize / nThreadCount + 1;
  88                 m_arrVal.resize( nSize );
  89                 size_t nItem = m_nThreadNo;
  90                 for ( size_t i = 0; i < nSize; nItem += nThreadCount, ++i )
  91                     m_arrVal[i] = nItem;
  92                 shuffle( m_arrVal.begin(), m_arrVal.end() );
  93             }
  94         public:
  95             size_t  m_nInsertSuccess;
  96             size_t  m_nInsertFailed;
  97             size_t  m_nFindSuccess;
  98             size_t  m_nFindFail;
  99
 100         public:
 101             Inserter( CppUnitMini::ThreadPool& pool, Map& rMap )
 102                 : CppUnitMini::TestThread( pool )
 103                 , m_Map( rMap )
 104             {}
 105             Inserter( Inserter& src )
 106                 : CppUnitMini::TestThread( src )
 107                 , m_Map( src.m_Map )
 108             {}
 109
 110             Map_InsFind_int&  getTest()
 111             {
 112                 return reinterpret_cast<Map_InsFind_int&>( m_Pool.m_Test );
 113             }
 114
 115             virtual void init()
 116             {
 117                 cds::threading::Manager::attachThread();
 118                 make_array();
 119             }
 120             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 121
 122             virtual void test()
 123             {
 124                 Map& rMap = m_Map;
 125
 126                 m_nInsertSuccess =
 127                     m_nInsertFailed =
 128                     m_nFindSuccess =
 129                     m_nFindFail = 0;
 130
 131                 size_t const nArrSize = m_arrVal.size();
 132                 for ( size_t i = 0; i < nArrSize; ++i ) {
 133                     size_t const nItem = m_arrVal[i];
 134                     if ( check_result( rMap.insert( nItem, nItem * 8 ), rMap ))
 135                         ++m_nInsertSuccess;
 136                     else
 137                         ++m_nInsertFailed;
 138
 139                     for ( size_t k = 0; k <= i; ++k ) {
 140                         if ( check_result( rMap.contains( m_arrVal[k] ), rMap ))
 141                             ++m_nFindSuccess;
 142                         else
 143                             ++m_nFindFail;
 144                     }
 145                 }
 146             }
 147         };
 148
 149     protected:
 150
 151         template <class Map>
 152         void do_test( Map& testMap )
 153         {
 154             typedef Inserter<Map>       InserterThread;
 155             cds::OS::Timer    timer;
 156
 157             CppUnitMini::ThreadPool pool( *this );
 158             pool.add( new InserterThread( pool, testMap ), c_nThreadCount );
 159             pool.run();
 160             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 161
 162             size_t nInsertSuccess = 0;
 163             size_t nInsertFailed = 0;
 164             size_t nFindSuccess = 0;
 165             size_t nFindFailed = 0;
 166             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 167                 InserterThread * pThread = static_cast<InserterThread *>( *it );
 168
 169                 nInsertSuccess += pThread->m_nInsertSuccess;
 170                 nInsertFailed += pThread->m_nInsertFailed;
 171                 nFindSuccess += pThread->m_nFindSuccess;
 172                 nFindFailed += pThread->m_nFindFail;
 173             }
 174
 175             CPPUNIT_MSG( "    Totals: Ins succ=" << nInsertSuccess << " fail=" << nInsertFailed << "\n"
 176                       << "           Find succ=" << nFindSuccess << " fail=" << nFindFailed
 177             );
 178
 179             CPPUNIT_CHECK( nInsertFailed == 0 );
 180             CPPUNIT_CHECK( nFindFailed == 0 );
 181
 182             check_before_cleanup( testMap );
 183
 184             testMap.clear();
 185             additional_check( testMap );
 186             print_stat( testMap );
 187             additional_cleanup( testMap );
 188         }
 189
 190         template <class Map>
 191         void run_test()
 192         {
 193             static_assert( (!std::is_same< typename Map::item_counter, cds::atomicity::empty_item_counter >::value),
 194                 "Empty item counter is not suitable for this test");
 195
 196             CPPUNIT_MSG( "Thread count: " << c_nThreadCount
 197                 << " map size=" << c_nMapSize
 198                 );
 199
 200             if ( Map::c_bLoadFactorDepended ) {
 201                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 202                     CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
 203                     Map  testMap( *this );
 204                     do_test( testMap );
 205                     if ( c_bPrintGCState )
 206                         print_gc_state();
 207                 }
 208             }
 209             else {
 210                 Map testMap( *this );
 211                 do_test( testMap );
 212                 if ( c_bPrintGCState )
 213                     print_gc_state();
 214             }
 215         }
 216
 217         void setUpParams( const CppUnitMini::TestCfg& cfg );
 218
 219 #   include "map2/map_defs.h"
 220         CDSUNIT_DECLARE_MichaelMap
 221         CDSUNIT_DECLARE_MichaelMap_nogc
 222         CDSUNIT_DECLARE_SplitList
 223         CDSUNIT_DECLARE_SplitList_nogc
 224         CDSUNIT_DECLARE_SkipListMap
 225         CDSUNIT_DECLARE_SkipListMap_nogc
 226         CDSUNIT_DECLARE_EllenBinTreeMap
 227         CDSUNIT_DECLARE_BronsonAVLTreeMap
 228         CDSUNIT_DECLARE_FeldmanHashMap_fixed
 229         CDSUNIT_DECLARE_FeldmanHashMap_city
 230         CDSUNIT_DECLARE_StripedMap
 231         CDSUNIT_DECLARE_RefinableMap
 232         CDSUNIT_DECLARE_CuckooMap
 233         CDSUNIT_DECLARE_StdMap
 234
 235         CPPUNIT_TEST_SUITE(Map_InsFind_int)
 236             CDSUNIT_TEST_MichaelMap
 237             CDSUNIT_TEST_MichaelMap_nogc
 238             CDSUNIT_TEST_SplitList
 239             CDSUNIT_TEST_SplitList_nogc
 240             CDSUNIT_TEST_SkipListMap
 241             CDSUNIT_TEST_SkipListMap_nogc
 242             CDSUNIT_TEST_EllenBinTreeMap
 243             CDSUNIT_TEST_BronsonAVLTreeMap
 244             CDSUNIT_TEST_FeldmanHashMap_fixed
 245             CDSUNIT_TEST_FeldmanHashMap_city
 246             CDSUNIT_TEST_CuckooMap
 247             CDSUNIT_TEST_StripedMap
 248             CDSUNIT_TEST_RefinableMap
 249             CDSUNIT_TEST_StdMap
 250         CPPUNIT_TEST_SUITE_END();
 251     };
 252 } // namespace map2