test/unit/map/skiplist_nogc.cpp

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