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-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 #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, random_level_generator )
 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::cmp compare;
 242         typedef typename TestFixture::less less;
 243         typedef cds::atomicity::item_counter item_counter;
 244         typedef cc::skip_list::stat<> stat;
 245         typedef cc::skip_list::xorshift random_level_generator;
 246         typedef cds::opt::v::rcu_assert_deadlock rcu_check_deadlock;
 247     };
 248     typedef cc::SkipListSet< rcu_type, int_item, set_traits >set_type;
 249
 250     set_type s;
 251     this->test( s );
 252 }
 253
 254
 255 // GCC 5: All this->test names should be written on single line, otherwise a runtime error will be encountered like as
 256 // "No this->test named <test_name> can be found in this this->test case"
 257 REGISTER_TYPED_TEST_CASE_P( SkipListSet,
 258     compare, less, cmpmix, item_counting, backoff, stat, random_level_generator
 259 );
 260
 261
 262 #endif // CDSUNIT_SET_TEST_SKIPLIST_RCU_H
 263