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, xorshift32 )
 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::less less;
 235         typedef cc::skip_list::xorshift32 random_level_generator;
 236     };
 237     typedef cc::SkipListMap< rcu_type, key_type, value_type, map_traits > map_type;
 238
 239     map_type m;
 240     this->test( m );
 241 }
 242
 243 TYPED_TEST_P( SkipListMap, xorshift24 )
 244 {
 245     typedef typename TestFixture::rcu_type   rcu_type;
 246     typedef typename TestFixture::key_type   key_type;
 247     typedef typename TestFixture::value_type value_type;
 248
 249     struct map_traits: public cc::skip_list::traits
 250     {
 251         typedef typename TestFixture::less less;
 252         typedef cc::skip_list::xorshift24 random_level_generator;
 253     };
 254     typedef cc::SkipListMap< rcu_type, key_type, value_type, map_traits > map_type;
 255
 256     map_type m;
 257     this->test( m );
 258 }
 259
 260 TYPED_TEST_P( SkipListMap, xorshift16 )
 261 {
 262     typedef typename TestFixture::rcu_type   rcu_type;
 263     typedef typename TestFixture::key_type   key_type;
 264     typedef typename TestFixture::value_type value_type;
 265
 266     struct map_traits: public cc::skip_list::traits
 267     {
 268         typedef typename TestFixture::less less;
 269         typedef cc::skip_list::xorshift16 random_level_generator;
 270     };
 271     typedef cc::SkipListMap< rcu_type, key_type, value_type, map_traits > map_type;
 272
 273     map_type m;
 274     this->test( m );
 275 }
 276
 277 TYPED_TEST_P( SkipListMap, turbo32 )
 278 {
 279     typedef typename TestFixture::rcu_type   rcu_type;
 280     typedef typename TestFixture::key_type   key_type;
 281     typedef typename TestFixture::value_type value_type;
 282
 283     struct map_traits: public cc::skip_list::traits
 284     {
 285         typedef typename TestFixture::less less;
 286         typedef cc::skip_list::turbo32 random_level_generator;
 287     };
 288     typedef cc::SkipListMap< rcu_type, key_type, value_type, map_traits > map_type;
 289
 290     map_type m;
 291     this->test( m );
 292 }
 293
 294 TYPED_TEST_P( SkipListMap, turbo24 )
 295 {
 296     typedef typename TestFixture::rcu_type   rcu_type;
 297     typedef typename TestFixture::key_type   key_type;
 298     typedef typename TestFixture::value_type value_type;
 299
 300     struct map_traits: public cc::skip_list::traits
 301     {
 302         typedef typename TestFixture::less less;
 303         typedef cc::skip_list::turbo24 random_level_generator;
 304     };
 305     typedef cc::SkipListMap< rcu_type, key_type, value_type, map_traits > map_type;
 306
 307     map_type m;
 308     this->test( m );
 309 }
 310
 311 TYPED_TEST_P( SkipListMap, turbo16 )
 312 {
 313     typedef typename TestFixture::rcu_type   rcu_type;
 314     typedef typename TestFixture::key_type   key_type;
 315     typedef typename TestFixture::value_type value_type;
 316
 317     struct map_traits: public cc::skip_list::traits
 318     {
 319         typedef typename TestFixture::less less;
 320         typedef cc::skip_list::turbo16 random_level_generator;
 321     };
 322     typedef cc::SkipListMap< rcu_type, key_type, value_type, map_traits > map_type;
 323
 324     map_type m;
 325     this->test( m );
 326 }
 327
 328 REGISTER_TYPED_TEST_CASE_P( SkipListMap,
 329     compare, less, cmpmix, item_counting, backoff, stat, xorshift32, xorshift24, xorshift16, turbo32, turbo24, turbo16
 330 );
 331
 332
 333 #endif // CDSUNIT_MAP_TEST_SKIPLIST_RCU_H
 334