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