test/unit/set/test_skiplist_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 #ifndef CDSUNIT_SET_TEST_SKIPLIST_RCU_H
  31 #define CDSUNIT_SET_TEST_SKIPLIST_RCU_H
  32
  33 #include "test_set_rcu.h"
  34 #include <cds/container/skip_list_set_rcu.h>
  35
  36 namespace cc = cds::container;
  37
  38 template <class RCU>
  39 class SkipListSet: public cds_test::container_set_rcu
  40 {
  41     typedef cds_test::container_set_rcu base_class;
  42 public:
  43     typedef cds::urcu::gc<RCU> rcu_type;
  44
  45 protected:
  46     template <typename Set>
  47     void test( Set& s )
  48     {
  49         // Precondition: set is empty
  50         // Postcondition: set is empty
  51
  52         base_class::test( s );
  53
  54         ASSERT_TRUE( s.empty());
  55         ASSERT_CONTAINER_SIZE( s, 0 );
  56
  57         typedef typename Set::value_type value_type;
  58
  59         size_t const nSetSize = base_class::kSize;
  60         std::vector< value_type > data;
  61         std::vector< size_t> indices;
  62         data.reserve( nSetSize );
  63         indices.reserve( nSetSize );
  64         for ( size_t key = 0; key < nSetSize; ++key ) {
  65             data.push_back( value_type( static_cast<int>(key)));
  66             indices.push_back( key );
  67         }
  68         shuffle( indices.begin(), indices.end());
  69
  70         for ( auto i : indices ) {
  71             ASSERT_TRUE( s.insert( data[i] ));
  72         }
  73         ASSERT_FALSE( s.empty());
  74         ASSERT_CONTAINER_SIZE( s, nSetSize );
  75
  76         typedef typename Set::exempt_ptr exempt_ptr;
  77         exempt_ptr xp;
  78
  79         // extract_min
  80         size_t nCount = 0;
  81         int nKey = -1;
  82         while ( !s.empty()) {
  83             xp = s.extract_min();
  84             ASSERT_FALSE( !xp );
  85             EXPECT_EQ( nKey + 1, xp->key());
  86             ++nCount;
  87             nKey = xp->key();
  88         }
  89         xp.release();
  90         EXPECT_EQ( nCount, nSetSize );
  91
  92         ASSERT_TRUE( s.empty());
  93         ASSERT_CONTAINER_SIZE( s, 0 );
  94
  95         // extract_max
  96         for ( auto i : indices ) {
  97             ASSERT_TRUE( s.insert( data[i] ));
  98         }
  99         ASSERT_FALSE( s.empty());
 100         ASSERT_CONTAINER_SIZE( s, nSetSize );
 101
 102         nCount = 0;
 103         nKey = nSetSize;
 104         while ( !s.empty()) {
 105             xp = s.extract_max();
 106             ASSERT_FALSE( !xp );
 107             EXPECT_EQ( nKey - 1, xp->key());
 108             ++nCount;
 109             nKey = xp->key();
 110         }
 111         xp.release();
 112         EXPECT_EQ( nCount, nSetSize );
 113
 114         ASSERT_TRUE( s.empty());
 115         ASSERT_CONTAINER_SIZE( s, 0 );
 116     }
 117
 118     void SetUp()
 119     {
 120         RCU::Construct();
 121         cds::threading::Manager::attachThread();
 122     }
 123
 124     void TearDown()
 125     {
 126         cds::threading::Manager::detachThread();
 127         RCU::Destruct();
 128     }
 129 };
 130
 131 TYPED_TEST_CASE_P( SkipListSet );
 132
 133 //TYPED_TEST_P( SkipListSet, compare )
 134 TYPED_TEST_P( SkipListSet, compare )
 135 {
 136     typedef typename TestFixture::rcu_type rcu_type;
 137     typedef typename TestFixture::int_item int_item;
 138
 139     typedef cc::SkipListSet< rcu_type, int_item,
 140         typename cc::skip_list::make_traits<
 141             cds::opt::compare< typename TestFixture::cmp >
 142         >::type
 143     > set_type;
 144
 145     set_type s;
 146     this->test( s );
 147 }
 148
 149 TYPED_TEST_P( SkipListSet, less )
 150 {
 151     typedef typename TestFixture::rcu_type rcu_type;
 152     typedef typename TestFixture::int_item int_item;
 153
 154     typedef cc::SkipListSet< rcu_type, int_item,
 155         typename cc::skip_list::make_traits<
 156             cds::opt::less< typename TestFixture::less >
 157         >::type
 158     > set_type;
 159
 160     set_type s;
 161     this->test( s );
 162 }
 163
 164 TYPED_TEST_P( SkipListSet, cmpmix )
 165 {
 166     typedef typename TestFixture::rcu_type rcu_type;
 167     typedef typename TestFixture::int_item int_item;
 168
 169     typedef cc::SkipListSet< rcu_type, int_item,
 170         typename cc::skip_list::make_traits<
 171             cds::opt::less< typename TestFixture::less >
 172             ,cds::opt::compare< typename TestFixture::cmp >
 173         >::type
 174     > set_type;
 175
 176     set_type s;
 177     this->test( s );
 178 }
 179
 180 TYPED_TEST_P( SkipListSet, item_counting )
 181 {
 182     typedef typename TestFixture::rcu_type rcu_type;
 183     typedef typename TestFixture::int_item int_item;
 184
 185     struct set_traits: public cc::skip_list::traits
 186     {
 187         typedef typename TestFixture::cmp compare;
 188         typedef typename TestFixture::less less;
 189         typedef cds::atomicity::item_counter item_counter;
 190     };
 191     typedef cc::SkipListSet< rcu_type, int_item, set_traits >set_type;
 192
 193     set_type s;
 194     this->test( s );
 195 }
 196
 197 TYPED_TEST_P( SkipListSet, backoff )
 198 {
 199     typedef typename TestFixture::rcu_type rcu_type;
 200     typedef typename TestFixture::int_item int_item;
 201
 202     struct set_traits: public cc::skip_list::traits
 203     {
 204         typedef typename TestFixture::cmp compare;
 205         typedef typename TestFixture::less less;
 206         typedef cds::atomicity::item_counter item_counter;
 207         typedef cds::backoff::yield back_off;
 208     };
 209     typedef cc::SkipListSet< rcu_type, int_item, set_traits >set_type;
 210
 211     set_type s;
 212     this->test( s );
 213 }
 214
 215 TYPED_TEST_P( SkipListSet, stat )
 216 {
 217     typedef typename TestFixture::rcu_type rcu_type;
 218     typedef typename TestFixture::int_item int_item;
 219
 220     struct set_traits: public cc::skip_list::traits
 221     {
 222         typedef typename TestFixture::cmp compare;
 223         typedef typename TestFixture::less less;
 224         typedef cds::atomicity::item_counter item_counter;
 225         typedef cds::backoff::yield back_off;
 226         typedef cc::skip_list::stat<> stat;
 227     };
 228     typedef cc::SkipListSet< rcu_type, int_item, set_traits >set_type;
 229
 230     set_type s;
 231     this->test( s );
 232 }
 233
 234 TYPED_TEST_P( SkipListSet, xorshift32 )
 235 {
 236     typedef typename TestFixture::rcu_type rcu_type;
 237     typedef typename TestFixture::int_item int_item;
 238
 239     struct set_traits: public cc::skip_list::traits
 240     {
 241         typedef typename TestFixture::less less;
 242         typedef cds::atomicity::item_counter item_counter;
 243         typedef cc::skip_list::xorshift32 random_level_generator;
 244         typedef cds::opt::v::rcu_assert_deadlock rcu_check_deadlock;
 245     };
 246     typedef cc::SkipListSet< rcu_type, int_item, set_traits >set_type;
 247
 248     set_type s;
 249     this->test( s );
 250 }
 251
 252 TYPED_TEST_P( SkipListSet, xorshift24 )
 253 {
 254     typedef typename TestFixture::rcu_type rcu_type;
 255     typedef typename TestFixture::int_item int_item;
 256
 257     struct set_traits: public cc::skip_list::traits
 258     {
 259         typedef typename TestFixture::less less;
 260         typedef cds::atomicity::item_counter item_counter;
 261         typedef cc::skip_list::xorshift24 random_level_generator;
 262         typedef cds::opt::v::rcu_assert_deadlock rcu_check_deadlock;
 263     };
 264     typedef cc::SkipListSet< rcu_type, int_item, set_traits >set_type;
 265
 266     set_type s;
 267     this->test( s );
 268 }
 269
 270 TYPED_TEST_P( SkipListSet, xorshift16 )
 271 {
 272     typedef typename TestFixture::rcu_type rcu_type;
 273     typedef typename TestFixture::int_item int_item;
 274
 275     struct set_traits: public cc::skip_list::traits
 276     {
 277         typedef typename TestFixture::less less;
 278         typedef cds::atomicity::item_counter item_counter;
 279         typedef cc::skip_list::xorshift16 random_level_generator;
 280         typedef cds::opt::v::rcu_assert_deadlock rcu_check_deadlock;
 281     };
 282     typedef cc::SkipListSet< rcu_type, int_item, set_traits >set_type;
 283
 284     set_type s;
 285     this->test( s );
 286 }
 287
 288 TYPED_TEST_P( SkipListSet, turbo32 )
 289 {
 290     typedef typename TestFixture::rcu_type rcu_type;
 291     typedef typename TestFixture::int_item int_item;
 292
 293     struct set_traits: public cc::skip_list::traits
 294     {
 295         typedef typename TestFixture::less less;
 296         typedef cds::atomicity::item_counter item_counter;
 297         typedef cc::skip_list::turbo32 random_level_generator;
 298         typedef cds::opt::v::rcu_assert_deadlock rcu_check_deadlock;
 299     };
 300     typedef cc::SkipListSet< rcu_type, int_item, set_traits >set_type;
 301
 302     set_type s;
 303     this->test( s );
 304 }
 305
 306 TYPED_TEST_P( SkipListSet, turbo24 )
 307 {
 308     typedef typename TestFixture::rcu_type rcu_type;
 309     typedef typename TestFixture::int_item int_item;
 310
 311     struct set_traits: public cc::skip_list::traits
 312     {
 313         typedef typename TestFixture::less less;
 314         typedef cds::atomicity::item_counter item_counter;
 315         typedef cc::skip_list::turbo24 random_level_generator;
 316         typedef cds::opt::v::rcu_assert_deadlock rcu_check_deadlock;
 317     };
 318     typedef cc::SkipListSet< rcu_type, int_item, set_traits >set_type;
 319
 320     set_type s;
 321     this->test( s );
 322 }
 323
 324 TYPED_TEST_P( SkipListSet, turbo16 )
 325 {
 326     typedef typename TestFixture::rcu_type rcu_type;
 327     typedef typename TestFixture::int_item int_item;
 328
 329     struct set_traits: public cc::skip_list::traits
 330     {
 331         typedef typename TestFixture::less less;
 332         typedef cds::atomicity::item_counter item_counter;
 333         typedef cc::skip_list::turbo16 random_level_generator;
 334         typedef cds::opt::v::rcu_assert_deadlock rcu_check_deadlock;
 335     };
 336     typedef cc::SkipListSet< rcu_type, int_item, set_traits >set_type;
 337
 338     set_type s;
 339     this->test( s );
 340 }
 341
 342 // All this->test names should be written on single line, otherwise a runtime error will be encountered like as
 343 // "No this->test named <test_name> can be found in this this->test case"
 344 REGISTER_TYPED_TEST_CASE_P( SkipListSet,
 345     compare, less, cmpmix, item_counting, backoff, stat, xorshift32, xorshift24, xorshift16, turbo32, turbo24, turbo16
 346 );
 347
 348
 349 #endif // CDSUNIT_SET_TEST_SKIPLIST_RCU_H
 350