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