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