test/stress/map/map_type_ellen_bintree.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
  31 #ifndef CDSUNIT_MAP_TYPE_ELLEN_BINTREE_H
  32 #define CDSUNIT_MAP_TYPE_ELLEN_BINTREE_H
  33
  34 #include "map_type.h"
  35
  36 #include <cds/container/ellen_bintree_map_rcu.h>
  37 #include <cds/container/ellen_bintree_map_hp.h>
  38 #include <cds/container/ellen_bintree_map_dhp.h>
  39
  40 #include <cds_test/stat_ellenbintree_out.h>
  41 #include "framework/ellen_bintree_update_desc_pool.h"
  42
  43 namespace map {
  44
  45     template <class GC, typename Key, typename T, typename Traits = cc::ellen_bintree::traits >
  46     class EllenBinTreeMap : public cc::EllenBinTreeMap< GC, Key, T, Traits >
  47     {
  48         typedef cc::EllenBinTreeMap< GC, Key, T, Traits > base_class;
  49     public:
  50         template <typename Config>
  51         EllenBinTreeMap( Config const& /*cfg*/)
  52             : base_class()
  53         {}
  54
  55         std::pair<Key, bool> extract_min_key()
  56         {
  57             auto xp = base_class::extract_min();
  58             if ( xp )
  59                 return std::make_pair( xp->first, true );
  60             return std::make_pair( Key(), false );
  61         }
  62
  63         std::pair<Key, bool> extract_max_key()
  64         {
  65             auto xp = base_class::extract_max();
  66             if ( xp )
  67                 return std::make_pair( xp->first, true );
  68             return std::make_pair( Key(), false );
  69         }
  70
  71         // for testing
  72         static CDS_CONSTEXPR bool const c_bExtractSupported = true;
  73         static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
  74         static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
  75     };
  76
  77     struct tag_EllenBinTreeMap;
  78
  79     template <typename Key, typename Value>
  80     struct map_type< tag_EllenBinTreeMap, Key, Value >: public map_type_base< Key, Value >
  81     {
  82         typedef map_type_base< Key, Value >      base_class;
  83         typedef typename base_class::key_compare compare;
  84         typedef typename base_class::key_less    less;
  85
  86         struct ellen_bintree_props {
  87             struct hp_gc {
  88                 typedef cc::ellen_bintree::map_node<cds::gc::HP, Key, Value>        leaf_node;
  89                 typedef cc::ellen_bintree::internal_node< Key, leaf_node >          internal_node;
  90                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
  91             };
  92             struct dhp_gc {
  93                 typedef cc::ellen_bintree::map_node<cds::gc::DHP, Key, Value>       leaf_node;
  94                 typedef cc::ellen_bintree::internal_node< Key, leaf_node >          internal_node;
  95                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
  96             };
  97             struct gpi {
  98                 typedef cc::ellen_bintree::map_node<rcu_gpi, Key, Value>            leaf_node;
  99                 typedef cc::ellen_bintree::internal_node< Key, leaf_node >          internal_node;
 100                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
 101             };
 102             struct gpb {
 103                 typedef cc::ellen_bintree::map_node<rcu_gpb, Key, Value>            leaf_node;
 104                 typedef cc::ellen_bintree::internal_node< Key, leaf_node >          internal_node;
 105                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
 106             };
 107             struct gpt {
 108                 typedef cc::ellen_bintree::map_node<rcu_gpt, Key, Value>            leaf_node;
 109                 typedef cc::ellen_bintree::internal_node< Key, leaf_node >          internal_node;
 110                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
 111             };
 112 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 113             struct shb {
 114                 typedef cc::ellen_bintree::map_node<rcu_shb, Key, Value>            leaf_node;
 115                 typedef cc::ellen_bintree::internal_node< Key, leaf_node >          internal_node;
 116                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
 117             };
 118             struct sht {
 119                 typedef cc::ellen_bintree::map_node<rcu_sht, Key, Value>            leaf_node;
 120                 typedef cc::ellen_bintree::internal_node< Key, leaf_node >          internal_node;
 121                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
 122             };
 123 #endif
 124         };
 125
 126         struct traits_EllenBinTreeMap: public cc::ellen_bintree::make_set_traits<
 127                 co::less< less >
 128                 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
 129                 ,co::item_counter< cds::atomicity::item_counter >
 130             >::type
 131         {};
 132         struct traits_EllenBinTreeMap_hp : traits_EllenBinTreeMap {
 133             typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 134         };
 135         typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_hp > EllenBinTreeMap_hp;
 136
 137         struct traits_EllenBinTreeMap_dhp : traits_EllenBinTreeMap {
 138             typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 139         };
 140         typedef EllenBinTreeMap< cds::gc::DHP, Key, Value, traits_EllenBinTreeMap_dhp > EllenBinTreeMap_dhp;
 141
 142         struct traits_EllenBinTreeMap_gpi : traits_EllenBinTreeMap {
 143             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 144         };
 145         typedef EllenBinTreeMap< rcu_gpi, Key, Value, traits_EllenBinTreeMap_gpi > EllenBinTreeMap_rcu_gpi;
 146
 147         struct traits_EllenBinTreeMap_gpb : traits_EllenBinTreeMap {
 148             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 149         };
 150         typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_gpb > EllenBinTreeMap_rcu_gpb;
 151
 152         struct traits_EllenBinTreeMap_gpt : traits_EllenBinTreeMap {
 153             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 154         };
 155         typedef EllenBinTreeMap< rcu_gpt, Key, Value, traits_EllenBinTreeMap_gpt > EllenBinTreeMap_rcu_gpt;
 156
 157 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 158         struct traits_EllenBinTreeMap_shb : traits_EllenBinTreeMap {
 159             typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 160         };
 161         typedef EllenBinTreeMap< rcu_shb, Key, Value, traits_EllenBinTreeMap_shb > EllenBinTreeMap_rcu_shb;
 162
 163         struct traits_EllenBinTreeMap_sht : traits_EllenBinTreeMap {
 164             typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 165         };
 166         typedef EllenBinTreeMap< rcu_sht, Key, Value, traits_EllenBinTreeMap_sht > EllenBinTreeMap_rcu_sht;
 167 #endif
 168
 169         struct traits_EllenBinTreeMap_yield : public traits_EllenBinTreeMap
 170         {
 171             typedef cds::backoff::yield back_off;
 172         };
 173         struct traits_EllenBinTreeMap_hp_yield : traits_EllenBinTreeMap_yield {
 174             typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 175         };
 176         typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_hp_yield > EllenBinTreeMap_hp_yield;
 177
 178         struct traits_EllenBinTreeMap_dhp_yield : traits_EllenBinTreeMap_yield {
 179             typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 180         };
 181         typedef EllenBinTreeMap< cds::gc::DHP, Key, Value, traits_EllenBinTreeMap_dhp_yield > EllenBinTreeMap_dhp_yield;
 182
 183         struct traits_EllenBinTreeMap_gpb_yield : traits_EllenBinTreeMap_yield {
 184             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 185         };
 186         typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_gpb_yield > EllenBinTreeMap_rcu_gpb_yield;
 187
 188
 189         struct traits_EllenBinTreeMap_stat: public cc::ellen_bintree::make_set_traits<
 190                 co::less< less >
 191                 ,cc::ellen_bintree::update_desc_allocator<
 192                     cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor >
 193                 >
 194                 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
 195                 ,co::stat< cc::ellen_bintree::stat<> >
 196                 ,co::item_counter< cds::atomicity::item_counter >
 197             >::type
 198         {};
 199
 200         struct traits_EllenBinTreeMap_stat_hp : public traits_EllenBinTreeMap_stat
 201         {
 202             typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 203         };
 204         typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_stat_hp > EllenBinTreeMap_hp_stat;
 205
 206         struct traits_EllenBinTreeMap_stat_dhp : public traits_EllenBinTreeMap_stat
 207         {
 208             typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 209         };
 210         typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_stat_dhp > EllenBinTreeMap_dhp_stat;
 211
 212         struct traits_EllenBinTreeMap_stat_gpi : public traits_EllenBinTreeMap_stat
 213         {
 214             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 215         };
 216         typedef EllenBinTreeMap< rcu_gpi, Key, Value, traits_EllenBinTreeMap_stat_gpi > EllenBinTreeMap_rcu_gpi_stat;
 217
 218         struct traits_EllenBinTreeMap_stat_gpb : public traits_EllenBinTreeMap_stat
 219         {
 220             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 221         };
 222         typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_stat_gpb > EllenBinTreeMap_rcu_gpb_stat;
 223
 224         struct traits_EllenBinTreeMap_stat_gpt : public traits_EllenBinTreeMap_stat
 225         {
 226             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 227         };
 228         typedef EllenBinTreeMap< rcu_gpt, Key, Value, traits_EllenBinTreeMap_stat_gpt > EllenBinTreeMap_rcu_gpt_stat;
 229
 230 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 231         struct traits_EllenBinTreeMap_stat_shb : public traits_EllenBinTreeMap_stat
 232         {
 233             typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 234         };
 235         typedef EllenBinTreeMap< rcu_shb, Key, Value, traits_EllenBinTreeMap_stat_shb > EllenBinTreeMap_rcu_shb_stat;
 236
 237         struct traits_EllenBinTreeMap_stat_sht : public traits_EllenBinTreeMap_stat
 238         {
 239             typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 240         };
 241         typedef EllenBinTreeMap< rcu_sht, Key, Value, traits_EllenBinTreeMap_stat_sht > EllenBinTreeMap_rcu_sht_stat;
 242 #endif
 243     };
 244
 245     template <typename GC, typename Key, typename T, typename Traits>
 246     static inline void print_stat( cds_test::property_stream& o, EllenBinTreeMap<GC, Key, T, Traits> const& s )
 247     {
 248         o << s.statistics();
 249     }
 250     template <typename GC, typename Key, typename T, typename Traits>
 251     static inline void additional_cleanup( EllenBinTreeMap<GC, Key, T, Traits>& /*s*/ )
 252     {
 253         ellen_bintree_pool::internal_node_counter::reset();
 254     }
 255     namespace ellen_bintree_check {
 256         static inline void check_stat( cds::intrusive::ellen_bintree::empty_stat const& /*s*/ )
 257         {
 258             // This check is not valid for thread-based RCU
 259             /*
 260             CPPUNIT_CHECK_CURRENT_EX( ellen_bintree_pool::internal_node_counter::m_nAlloc.get() == ellen_bintree_pool::internal_node_counter::m_nFree.get(),
 261                 "m_nAlloc=" << ellen_bintree_pool::internal_node_counter::m_nAlloc.get()
 262                 << ", m_nFree=" << ellen_bintree_pool::internal_node_counter::m_nFree.get()
 263                 );
 264             */
 265         }
 266
 267         static inline void check_stat( cds::intrusive::ellen_bintree::stat<> const& stat )
 268         {
 269             EXPECT_EQ( stat.m_nInternalNodeCreated, stat.m_nInternalNodeDeleted );
 270             EXPECT_EQ( stat.m_nUpdateDescCreated, stat.m_nUpdateDescDeleted );
 271             EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), stat.m_nInternalNodeCreated );
 272         }
 273     }   // namespace ellen_bintree_check
 274     template <typename GC, typename Key, typename T, typename Traits>
 275     static inline void additional_check( EllenBinTreeMap<GC, Key, T, Traits>& m )
 276     {
 277         GC::force_dispose();
 278         ellen_bintree_check::check_stat( m.statistics());
 279     }
 280
 281     template <typename GC, typename Key, typename T, typename Traits>
 282     static inline void check_before_cleanup( EllenBinTreeMap<GC, Key, T, Traits>& m )
 283     {
 284         EXPECT_TRUE( m.check_consistency());
 285     }
 286 }   // namespace map
 287
 288
 289 #define CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, ellen_map_type, key_type, value_type ) \
 290     TEST_F( fixture, ellen_map_type ) \
 291     { \
 292         typedef map::map_type< tag_EllenBinTreeMap, key_type, value_type >::ellen_map_type map_type; \
 293         test_case<map_type>(); \
 294     }
 295
 296 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 297 #   define CDSSTRESS_EllenBinTreeMap_SHRCU( fixture, test_case, key_type, value_type ) \
 298         CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_shb,        key_type, value_type ) \
 299         CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_sht,        key_type, value_type ) \
 300         CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_shb_stat,   key_type, value_type ) \
 301         CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_sht_stat,   key_type, value_type ) \
 302
 303 #else
 304 #   define CDSSTRESS_EllenBinTreeMap_SHRCU( fixture, test_case, key_type, value_type )
 305 #endif
 306
 307 #if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL > 0
 308 #   define CDSSTRESS_EllenBinTreeMap_HP_1( fixture, test_case, key_type, value_type ) \
 309         CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_hp_yield,       key_type, value_type ) \
 310         CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_dhp_yield,      key_type, value_type ) \
 311
 312
 313 #   define CDSSTRESS_EllenBinTreeMap_RCU_1( fixture, test_case, key_type, value_type ) \
 314         CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpi,        key_type, value_type ) \
 315         CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpb_yield,  key_type, value_type ) \
 316         CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpi_stat,   key_type, value_type ) \
 317
 318 #else
 319 #   define CDSSTRESS_EllenBinTreeMap_HP_1( fixture, test_case, key_type, value_type )
 320 #   define CDSSTRESS_EllenBinTreeMap_RCU_1( fixture, test_case, key_type, value_type )
 321 #endif
 322
 323 #define CDSSTRESS_EllenBinTreeMap_HP( fixture, test_case, key_type, value_type ) \
 324     CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_hp,             key_type, value_type ) \
 325     CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_dhp,            key_type, value_type ) \
 326     CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_hp_stat,        key_type, value_type ) \
 327     CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_dhp_stat,       key_type, value_type ) \
 328     CDSSTRESS_EllenBinTreeMap_HP_1( fixture, test_case, key_type, value_type ) \
 329
 330 #define CDSSTRESS_EllenBinTreeMap_RCU( fixture, test_case, key_type, value_type ) \
 331     CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpb,        key_type, value_type ) \
 332     CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpt,        key_type, value_type ) \
 333     CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpb_stat,   key_type, value_type ) \
 334     CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpt_stat,   key_type, value_type ) \
 335     CDSSTRESS_EllenBinTreeMap_RCU_1( fixture, test_case, key_type, value_type ) \
 336     CDSSTRESS_EllenBinTreeMap_SHRCU( fixture, test_case, key_type, value_type ) \
 337
 338 #define CDSSTRESS_EllenBinTreeMap( fixture, test_case, key_type, value_type ) \
 339     CDSSTRESS_EllenBinTreeMap_HP( fixture, test_case, key_type, value_type ) \
 340     CDSSTRESS_EllenBinTreeMap_RCU( fixture, test_case, key_type, value_type ) \
 341
 342 #endif // ifndef CDSUNIT_MAP_TYPE_ELLEN_BINTREE_H