test/unit/map/test_feldman_hashmap_rcu.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 #ifndef CDSUNIT_MAP_TEST_FELDMAN_HASHMAP_RCU_H
  32 #define CDSUNIT_MAP_TEST_FELDMAN_HASHMAP_RCU_H
  33
  34 #include "test_feldman_hashmap.h"
  35 #include <cds/container/feldman_hashmap_rcu.h>
  36
  37 namespace {
  38
  39     template <typename RCU>
  40     class FeldmanHashMap: public cds_test::feldman_hashmap
  41     {
  42         typedef cds_test::feldman_hashmap base_class;
  43
  44     protected:
  45         typedef cds::urcu::gc<RCU> rcu_type;
  46
  47         template <class Map>
  48         void test( Map& m )
  49         {
  50             // Precondition: map is empty
  51             // Postcondition: map is empty
  52
  53             base_class::test( m );
  54
  55             ASSERT_TRUE( m.empty());
  56             ASSERT_CONTAINER_SIZE( m, 0 );
  57
  58             typedef typename Map::value_type map_pair;
  59             typedef typename Map::rcu_lock   rcu_lock;
  60             typedef typename Map::exempt_ptr exempt_ptr;
  61
  62             size_t const kkSize = base_class::kSize;
  63
  64             std::vector<key_type> arrKeys;
  65             for ( int i = 0; i < static_cast<int>(kkSize); ++i )
  66                 arrKeys.push_back( key_type( i ));
  67             shuffle( arrKeys.begin(), arrKeys.end());
  68
  69             std::vector< value_type > arrVals;
  70             for ( size_t i = 0; i < kkSize; ++i ) {
  71                 value_type val;
  72                 val.nVal = static_cast<int>( i );
  73                 val.strVal = std::to_string( i );
  74                 arrVals.push_back( val );
  75             }
  76
  77             for ( auto const& i : arrKeys )
  78                 ASSERT_TRUE( m.insert( i ) );
  79             ASSERT_FALSE( m.empty() );
  80             ASSERT_CONTAINER_SIZE( m, kkSize );
  81
  82             // iterators
  83             {
  84                 rcu_lock l;
  85                 size_t nCount = 0;
  86                 for ( auto it = m.begin(); it != m.end(); ++it ) {
  87                     EXPECT_EQ( it->second.nVal, 0 );
  88                     it->second.nVal = it->first.nKey * 2;
  89                     ++nCount;
  90                 }
  91                 EXPECT_EQ( nCount, kkSize );
  92
  93                 nCount = 0;
  94                 for ( auto it = m.cbegin(); it != m.cend(); ++it ) {
  95                     EXPECT_EQ( it->second.nVal, it->first.nKey * 2 );
  96                     ++nCount;
  97                 }
  98                 EXPECT_EQ( nCount, kkSize );
  99
 100                 nCount = 0;
 101                 for ( auto it = m.rbegin(); it != m.rend(); ++it ) {
 102                     EXPECT_EQ( it->second.nVal, it->first.nKey * 2 );
 103                     it->second.nVal = it->first.nKey * 4;
 104                     ++nCount;
 105                 }
 106                 EXPECT_EQ( nCount, kkSize );
 107
 108                 nCount = 0;
 109                 for ( auto it = m.crbegin(); it != m.crend(); ++it ) {
 110                     EXPECT_EQ( it->second.nVal, it->first.nKey * 4 );
 111                     ++nCount;
 112                 }
 113                 EXPECT_EQ( nCount, kkSize );
 114             }
 115
 116             // get/extract
 117             exempt_ptr xp;
 118
 119             for ( auto const& i : arrKeys ) {
 120                 value_type const& val = arrVals.at( i.nKey );
 121
 122                 {
 123                     rcu_lock l;
 124                     map_pair * p = m.get( i.nKey );
 125                     ASSERT_FALSE( p == nullptr );
 126                     EXPECT_EQ( p->first.nKey, i.nKey );
 127
 128                     p = m.get( i );
 129                     ASSERT_FALSE( p == nullptr );
 130                     EXPECT_EQ( p->first.nKey, i.nKey );
 131
 132                     p = m.get( val.strVal );
 133                     ASSERT_FALSE( p == nullptr );
 134                     EXPECT_EQ( p->first.nKey, i.nKey );
 135                 }
 136
 137                 switch ( i.nKey % 3 ) {
 138                 case 0:
 139                     xp = m.extract( i.nKey );
 140                     break;
 141                 case 1:
 142                     xp = m.extract( i );
 143                     break;
 144                 case 2:
 145                     xp = m.extract( val.strVal );
 146                     break;
 147                 }
 148                 ASSERT_FALSE( !xp );
 149                 ASSERT_EQ( xp->first.nKey, i.nKey );
 150
 151                 {
 152                     rcu_lock l;
 153
 154                     map_pair * p = m.get( i.nKey );
 155                     EXPECT_TRUE( p == nullptr );
 156                     p = m.get( i );
 157                     EXPECT_TRUE( p == nullptr );
 158                 }
 159             }
 160             ASSERT_TRUE( m.empty() );
 161             ASSERT_CONTAINER_SIZE( m, 0 );
 162         }
 163
 164         void SetUp()
 165         {
 166             RCU::Construct();
 167             cds::threading::Manager::attachThread();
 168         }
 169
 170         void TearDown()
 171         {
 172             cds::threading::Manager::detachThread();
 173             RCU::Destruct();
 174         }
 175     };
 176
 177     TYPED_TEST_CASE_P( FeldmanHashMap );
 178
 179     TYPED_TEST_P( FeldmanHashMap, defaulted )
 180     {
 181         typedef typename TestFixture::rcu_type   rcu_type;
 182         typedef typename TestFixture::key_type   key_type;
 183         typedef typename TestFixture::value_type value_type;
 184
 185         typedef cc::FeldmanHashMap< rcu_type, key_type, value_type > map_type;
 186
 187         map_type m;
 188         this->test( m );
 189     }
 190
 191     TYPED_TEST_P( FeldmanHashMap, compare )
 192     {
 193         typedef typename TestFixture::rcu_type   rcu_type;
 194         typedef typename TestFixture::key_type   key_type;
 195         typedef typename TestFixture::value_type value_type;
 196
 197         typedef cc::FeldmanHashMap< rcu_type, key_type, value_type,
 198             typename cc::feldman_hashmap::make_traits<
 199                 cds::opt::compare< typename TestFixture::cmp >
 200             >::type
 201         > map_type;
 202
 203         map_type m( 4, 5 );
 204         this->test( m );
 205     }
 206
 207     TYPED_TEST_P( FeldmanHashMap, less )
 208     {
 209         typedef typename TestFixture::rcu_type   rcu_type;
 210         typedef typename TestFixture::key_type   key_type;
 211         typedef typename TestFixture::value_type value_type;
 212
 213         typedef cc::FeldmanHashMap< rcu_type, key_type, value_type,
 214             typename cc::feldman_hashmap::make_traits<
 215                 cds::opt::less< typename TestFixture::less >
 216             >::type
 217         > map_type;
 218
 219         map_type m( 3, 2 );
 220         this->test( m );
 221     }
 222
 223     TYPED_TEST_P( FeldmanHashMap, cmpmix )
 224     {
 225         typedef typename TestFixture::rcu_type   rcu_type;
 226         typedef typename TestFixture::key_type   key_type;
 227         typedef typename TestFixture::value_type value_type;
 228
 229         typedef cc::FeldmanHashMap< rcu_type, key_type, value_type,
 230             typename cc::feldman_hashmap::make_traits<
 231                 cds::opt::less< typename TestFixture::less >
 232                 , cds::opt::compare<  typename TestFixture::cmp >
 233             >::type
 234         > map_type;
 235
 236         map_type m( 4, 4 );
 237         this->test( m );
 238     }
 239
 240     TYPED_TEST_P( FeldmanHashMap, backoff )
 241     {
 242         typedef typename TestFixture::rcu_type   rcu_type;
 243         typedef typename TestFixture::key_type   key_type;
 244         typedef typename TestFixture::value_type value_type;
 245
 246         struct map_traits: public cc::feldman_hashmap::traits
 247         {
 248             typedef typename TestFixture::cmp compare;
 249             typedef cds::atomicity::item_counter item_counter;
 250             typedef cds::backoff::yield back_off;
 251         };
 252         typedef cc::FeldmanHashMap< rcu_type, key_type, value_type, map_traits > map_type;
 253
 254         map_type m( 8, 2 );
 255         this->test( m );
 256     }
 257
 258     TYPED_TEST_P( FeldmanHashMap, stat )
 259     {
 260         typedef typename TestFixture::rcu_type   rcu_type;
 261         typedef typename TestFixture::key_type   key_type;
 262         typedef typename TestFixture::value_type value_type;
 263
 264         struct map_traits: public cc::feldman_hashmap::traits
 265         {
 266             typedef cds::backoff::yield back_off;
 267             typedef cc::feldman_hashmap::stat<> stat;
 268         };
 269         typedef cc::FeldmanHashMap< rcu_type, key_type, value_type, map_traits > map_type;
 270
 271         map_type m( 1, 1 );
 272         this->test( m );
 273     }
 274
 275     // GCC 5: All test names should be written on single line, otherwise a runtime error will be encountered like as
 276     // "No test named <test_name> can be found in this test case"
 277     REGISTER_TYPED_TEST_CASE_P( FeldmanHashMap,
 278         defaulted, compare, less, cmpmix, backoff, stat
 279         );
 280 } // namespace
 281
 282 #endif // #ifndef CDSUNIT_MAP_TEST_FELDMAN_HASHMAP_RCU_H