test/unit/map/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_MAP_TEST_SKIPLIST_RCU_H
  31 #define CDSUNIT_MAP_TEST_SKIPLIST_RCU_H
  32
  33 #include "test_map_rcu.h"
  34 #include <cds/container/skip_list_map_rcu.h>
  35
  36 namespace cc = cds::container;
  37
  38 template <class RCU>
  39 class SkipListMap: public cds_test::container_map_rcu
  40 {
  41     typedef cds_test::container_map_rcu base_class;
  42 public:
  43     typedef cds::urcu::gc<RCU> rcu_type;
  44
  45 protected:
  46     template <typename Map>
  47     void test( Map& m )
  48     {
  49         // Precondition: map is empty
  50         // Postcondition: map is empty
  51
  52         base_class::test( m );
  53
  54         ASSERT_TRUE( m.empty());
  55         ASSERT_CONTAINER_SIZE( m, 0 );
  56
  57         typedef typename Map::exempt_ptr exempt_ptr;
  58         size_t const kkSize = base_class::kSize;
  59
  60         // get_min
  61         for ( int i = static_cast<int>(kkSize); i > 0; --i )
  62             ASSERT_TRUE( m.insert( i ));
  63
  64         exempt_ptr xp;
  65
  66         size_t nCount = 0;
  67         int nKey = 0;
  68         while ( !m.empty()) {
  69             xp = m.extract_min();
  70             ASSERT_FALSE( !xp );
  71             EXPECT_EQ( xp->first.nKey, nKey + 1 );
  72             nKey = xp->first.nKey;
  73             ++nCount;
  74         }
  75         xp = m.extract_min();
  76         ASSERT_TRUE( !xp );
  77         xp = m.extract_max();
  78         ASSERT_TRUE( !xp );
  79         EXPECT_EQ( kkSize, nCount );
  80         ASSERT_TRUE( m.empty());
  81         ASSERT_CONTAINER_SIZE( m, 0 );
  82
  83         // get_max
  84         for ( int i = 0; i < static_cast<int>(kkSize); ++i )
  85             ASSERT_TRUE( m.insert( i ));
  86
  87         nKey = kkSize;
  88         nCount = 0;
  89         while ( !m.empty()) {
  90             xp = m.extract_max();
  91             ASSERT_FALSE( !xp );
  92             EXPECT_EQ( xp->first.nKey, nKey - 1 );
  93             nKey = xp->first.nKey;
  94             ++nCount;
  95         }
  96         xp = m.extract_min();
  97         ASSERT_TRUE( !xp );
  98         xp = m.extract_max();
  99         ASSERT_TRUE( !xp );
 100         EXPECT_EQ( kkSize, nCount );
 101         ASSERT_TRUE( m.empty());
 102         ASSERT_CONTAINER_SIZE( m, 0 );
 103     }
 104
 105     void SetUp()
 106     {
 107         RCU::Construct();
 108         cds::threading::Manager::attachThread();
 109     }
 110
 111     void TearDown()
 112     {
 113         cds::threading::Manager::detachThread();
 114         RCU::Destruct();
 115     }
 116 };
 117
 118 TYPED_TEST_CASE_P( SkipListMap );
 119
 120 TYPED_TEST_P( SkipListMap, compare )
 121 {
 122     typedef typename TestFixture::rcu_type   rcu_type;
 123     typedef typename TestFixture::key_type   key_type;
 124     typedef typename TestFixture::value_type value_type;
 125
 126     typedef cc::SkipListMap< rcu_type, key_type, value_type,
 127         typename cc::skip_list::make_traits<
 128             cds::opt::compare< typename TestFixture::cmp >
 129         >::type
 130     > map_type;
 131
 132     map_type m;
 133     this->test( m );
 134 }
 135
 136 TYPED_TEST_P( SkipListMap, less )
 137 {
 138     typedef typename TestFixture::rcu_type   rcu_type;
 139     typedef typename TestFixture::key_type   key_type;
 140     typedef typename TestFixture::value_type value_type;
 141
 142     typedef cc::SkipListMap< rcu_type, key_type, value_type,
 143         typename cc::skip_list::make_traits<
 144             cds::opt::less< typename TestFixture::less >
 145         >::type
 146     > map_type;
 147
 148     map_type m;
 149     this->test( m );
 150 }
 151
 152 TYPED_TEST_P( SkipListMap, cmpmix )
 153 {
 154     typedef typename TestFixture::rcu_type   rcu_type;
 155     typedef typename TestFixture::key_type   key_type;
 156     typedef typename TestFixture::value_type value_type;
 157
 158     typedef cc::SkipListMap< rcu_type, key_type, value_type,
 159         typename cc::skip_list::make_traits<
 160             cds::opt::less< typename TestFixture::less >
 161             ,cds::opt::compare< typename TestFixture::cmp >
 162         >::type
 163     > map_type;
 164
 165     map_type m;
 166     this->test( m );
 167 }
 168
 169 TYPED_TEST_P( SkipListMap, item_counting )
 170 {
 171     typedef typename TestFixture::rcu_type   rcu_type;
 172     typedef typename TestFixture::key_type   key_type;
 173     typedef typename TestFixture::value_type value_type;
 174
 175     struct map_traits: public cc::skip_list::traits
 176     {
 177         typedef typename TestFixture::cmp compare;
 178         typedef typename TestFixture::less less;
 179         typedef cds::atomicity::item_counter item_counter;
 180     };
 181     typedef cc::SkipListMap< rcu_type, key_type, value_type, map_traits > map_type;
 182
 183     map_type m;
 184     this->test( m );
 185 }
 186
 187 TYPED_TEST_P( SkipListMap, backoff )
 188 {
 189     typedef typename TestFixture::rcu_type   rcu_type;
 190     typedef typename TestFixture::key_type   key_type;
 191     typedef typename TestFixture::value_type value_type;
 192
 193     struct map_traits: public cc::skip_list::traits
 194     {
 195         typedef typename TestFixture::cmp compare;
 196         typedef typename TestFixture::less less;
 197         typedef cds::atomicity::item_counter item_counter;
 198         typedef cds::backoff::yield back_off;
 199     };
 200     typedef cc::SkipListMap< rcu_type, key_type, value_type, map_traits > map_type;
 201
 202     map_type m;
 203     this->test( m );
 204 }
 205
 206 TYPED_TEST_P( SkipListMap, stat )
 207 {
 208     typedef typename TestFixture::rcu_type   rcu_type;
 209     typedef typename TestFixture::key_type   key_type;
 210     typedef typename TestFixture::value_type value_type;
 211
 212     struct map_traits: public cc::skip_list::traits
 213     {
 214         typedef typename TestFixture::cmp compare;
 215         typedef typename TestFixture::less less;
 216         typedef cds::atomicity::item_counter item_counter;
 217         typedef cds::backoff::yield back_off;
 218         typedef cc::skip_list::stat<> stat;
 219     };
 220     typedef cc::SkipListMap< rcu_type, key_type, value_type, map_traits > map_type;
 221
 222     map_type m;
 223     this->test( m );
 224 }
 225
 226 TYPED_TEST_P( SkipListMap, random_level_generator )
 227 {
 228     typedef typename TestFixture::rcu_type   rcu_type;
 229     typedef typename TestFixture::key_type   key_type;
 230     typedef typename TestFixture::value_type value_type;
 231
 232     struct map_traits: public cc::skip_list::traits
 233     {
 234         typedef typename TestFixture::cmp compare;
 235         typedef typename TestFixture::less less;
 236         typedef cds::atomicity::item_counter item_counter;
 237         typedef cc::skip_list::stat<> stat;
 238         typedef cc::skip_list::xorshift random_level_generator;
 239         typedef cds::opt::v::rcu_assert_deadlock rcu_check_deadlock;
 240     };
 241     typedef cc::SkipListMap< rcu_type, key_type, value_type, map_traits > map_type;
 242
 243     map_type m;
 244     this->test( m );
 245 }
 246
 247
 248 REGISTER_TYPED_TEST_CASE_P( SkipListMap,
 249     compare, less, cmpmix, item_counting, backoff, stat, random_level_generator
 250 );
 251
 252
 253 #endif // CDSUNIT_MAP_TEST_SKIPLIST_RCU_H
 254