test/stress/set/set_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_SET_TYPE_ELLEN_BINTREE_H
  32 #define CDSUNIT_SET_TYPE_ELLEN_BINTREE_H
  33
  34 #include "set_type.h"
  35
  36 #include <cds/container/ellen_bintree_set_rcu.h>
  37 #include <cds/container/ellen_bintree_set_hp.h>
  38 #include <cds/container/ellen_bintree_set_dhp.h>
  39
  40 #include <cds_test/stat_ellenbintree_out.h>
  41 #include "framework/ellen_bintree_update_desc_pool.h"
  42
  43 namespace set {
  44
  45     template <class GC, typename Key, typename T, typename Traits = cc::ellen_bintree::traits >
  46     class EllenBinTreeSet : public cc::EllenBinTreeSet< GC, Key, T, Traits >
  47     {
  48         typedef cc::EllenBinTreeSet< GC, Key, T, Traits > base_class;
  49     public:
  50         template <typename Config>
  51         EllenBinTreeSet( Config const& /*cfg*/ )
  52         {}
  53
  54         // for testing
  55         static CDS_CONSTEXPR bool const c_bExtractSupported = true;
  56         static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
  57         static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
  58     };
  59
  60     struct tag_EllenBinTreeSet;
  61
  62     template <typename Key, typename Val>
  63     struct set_type< tag_EllenBinTreeSet, Key, Val >: public set_type_base< Key, Val >
  64     {
  65         typedef set_type_base< Key, Val > base_class;
  66         typedef typename base_class::key_type key_type;
  67         typedef typename base_class::key_val key_val;
  68         typedef typename base_class::compare compare;
  69         typedef typename base_class::less less;
  70         typedef typename base_class::key_less key_less;
  71
  72         struct ellen_bintree_props {
  73             struct key_extractor {
  74                 void operator()( key_type& dest, key_val const& src ) const
  75                 {
  76                     dest = src.key;
  77                 }
  78             };
  79
  80             struct less {
  81                 bool operator()( key_val const& v1, key_val const& v2 ) const
  82                 {
  83                     return key_less()( v1.key, v2.key );
  84                 }
  85                 bool operator()( key_type const& k, key_val const& v ) const
  86                 {
  87                     return key_less()( k, v.key );
  88                 }
  89                 bool operator()( key_val const& v, key_type const& k ) const
  90                 {
  91                     return key_less()( v.key, k );
  92                 }
  93                 bool operator()( key_type const& k1, key_type const& k2 ) const
  94                 {
  95                     return key_less()( k1, k2 );
  96                 }
  97             };
  98
  99             struct hp_gc {
 100                 typedef cc::ellen_bintree::node<cds::gc::HP, key_val>               leaf_node;
 101                 typedef cc::ellen_bintree::internal_node< key_type, leaf_node >     internal_node;
 102                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
 103             };
 104
 105             struct dhp_gc {
 106                 typedef cc::ellen_bintree::node<cds::gc::DHP, key_val>              leaf_node;
 107                 typedef cc::ellen_bintree::internal_node< key_type, leaf_node >     internal_node;
 108                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
 109             };
 110
 111             struct gpi {
 112                 typedef cc::ellen_bintree::node<rcu_gpi, key_val>                   leaf_node;
 113                 typedef cc::ellen_bintree::internal_node< key_type, leaf_node >     internal_node;
 114                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
 115             };
 116             struct gpb {
 117                 typedef cc::ellen_bintree::node<rcu_gpb, key_val>                   leaf_node;
 118                 typedef cc::ellen_bintree::internal_node< key_type, leaf_node >     internal_node;
 119                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
 120             };
 121             struct gpt {
 122                 typedef cc::ellen_bintree::node<rcu_gpt, key_val>                   leaf_node;
 123                 typedef cc::ellen_bintree::internal_node< key_type, leaf_node >     internal_node;
 124                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
 125             };
 126 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 127             struct shb {
 128                 typedef cc::ellen_bintree::node<rcu_shb, key_val>                   leaf_node;
 129                 typedef cc::ellen_bintree::internal_node< key_type, leaf_node >     internal_node;
 130                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
 131             };
 132 #endif
 133         };
 134
 135         struct traits_EllenBinTreeSet: public cc::ellen_bintree::make_set_traits<
 136             cc::ellen_bintree::key_extractor< typename ellen_bintree_props::key_extractor >
 137             ,co::less< typename ellen_bintree_props::less >
 138             ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
 139             ,co::item_counter<cds::atomicity::cache_friendly_item_counter >
 140         >::type
 141         {};
 142
 143         struct traits_EllenBinTreeSet_hp : public traits_EllenBinTreeSet
 144         {
 145             typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 146         };
 147         typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_hp > EllenBinTreeSet_hp;
 148
 149         struct traits_EllenBinTreeSet_dhp : public traits_EllenBinTreeSet
 150         {
 151             typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 152         };
 153         typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_dhp > EllenBinTreeSet_dhp;
 154
 155         struct traits_EllenBinTreeSet_gpi : public traits_EllenBinTreeSet
 156         {
 157             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 158         };
 159         typedef EllenBinTreeSet< rcu_gpi, key_type, key_val, traits_EllenBinTreeSet_gpi > EllenBinTreeSet_rcu_gpi;
 160
 161         struct traits_EllenBinTreeSet_gpb : public traits_EllenBinTreeSet
 162         {
 163             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 164         };
 165         typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_gpb > EllenBinTreeSet_rcu_gpb;
 166
 167         struct traits_EllenBinTreeSet_gpt : public traits_EllenBinTreeSet
 168         {
 169             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 170         };
 171         typedef EllenBinTreeSet< rcu_gpt, key_type, key_val, traits_EllenBinTreeSet_gpt > EllenBinTreeSet_rcu_gpt;
 172
 173 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 174         struct traits_EllenBinTreeSet_shb : public traits_EllenBinTreeSet
 175         {
 176             typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 177         };
 178         typedef EllenBinTreeSet< rcu_shb, key_type, key_val, traits_EllenBinTreeSet_shb > EllenBinTreeSet_rcu_shb;
 179 #endif
 180
 181         //
 182         struct traits_EllenBinTreeSet_yield : public traits_EllenBinTreeSet
 183         {
 184             typedef cds::backoff::yield back_off;
 185         };
 186
 187         struct traits_EllenBinTreeSet_yield_hp : public traits_EllenBinTreeSet_yield
 188         {
 189             typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 190         };
 191         typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_yield_hp > EllenBinTreeSet_yield_hp;
 192
 193         struct traits_EllenBinTreeSet_yield_dhp : public traits_EllenBinTreeSet_yield
 194         {
 195             typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 196         };
 197         typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_yield_dhp > EllenBinTreeSet_yield_dhp;
 198
 199
 200         struct traits_EllenBinTreeSet_yield_gpb : public traits_EllenBinTreeSet_yield
 201         {
 202             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 203         };
 204         typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_yield_gpb > EllenBinTreeSet_yield_rcu_gpb;
 205
 206
 207         struct traits_EllenBinTreeSet_stat: public cc::ellen_bintree::make_set_traits<
 208             cc::ellen_bintree::key_extractor< typename ellen_bintree_props::key_extractor >
 209             ,co::less< typename ellen_bintree_props::less >
 210             ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
 211             ,co::stat< cc::ellen_bintree::stat<> >
 212             ,co::item_counter<cds::atomicity::cache_friendly_item_counter >
 213         >::type
 214         {};
 215
 216         struct traits_EllenBinTreeSet_stat_hp : public traits_EllenBinTreeSet_stat
 217         {
 218             typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 219         };
 220         typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_stat_hp > EllenBinTreeSet_hp_stat;
 221
 222         struct traits_EllenBinTreeSet_stat_dhp : public traits_EllenBinTreeSet_stat
 223         {
 224             typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 225         };
 226         typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_stat_dhp > EllenBinTreeSet_dhp_stat;
 227
 228         struct traits_EllenBinTreeSet_stat_gpi : public traits_EllenBinTreeSet_stat
 229         {
 230             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 231         };
 232         typedef EllenBinTreeSet< rcu_gpi, key_type, key_val, traits_EllenBinTreeSet_stat_gpi > EllenBinTreeSet_rcu_gpi_stat;
 233
 234         struct traits_EllenBinTreeSet_stat_gpb : public traits_EllenBinTreeSet_stat
 235         {
 236             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 237         };
 238         typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_stat_gpb > EllenBinTreeSet_rcu_gpb_stat;
 239
 240         struct traits_EllenBinTreeSet_stat_gpt : public traits_EllenBinTreeSet_stat
 241         {
 242             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 243         };
 244         typedef EllenBinTreeSet< rcu_gpt, key_type, key_val, traits_EllenBinTreeSet_stat_gpt > EllenBinTreeSet_rcu_gpt_stat;
 245
 246 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 247         struct traits_EllenBinTreeSet_stat_shb : public traits_EllenBinTreeSet_stat
 248         {
 249             typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 250         };
 251         typedef EllenBinTreeSet< rcu_shb, key_type, key_val, traits_EllenBinTreeSet_stat_shb > EllenBinTreeSet_rcu_shb_stat;
 252 #endif
 253
 254     };
 255
 256     template <typename GC, typename Key, typename T, typename Traits>
 257     static inline void print_stat( cds_test::property_stream& o, EllenBinTreeSet<GC, Key, T, Traits> const& s )
 258     {
 259         o << s.statistics();
 260     }
 261
 262     namespace ellen_bintree_check {
 263         static inline void check_stat( cds::intrusive::ellen_bintree::empty_stat const& /*s*/ )
 264         {
 265             // Not true for threaded RCU
 266             /*
 267             EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), ellen_bintree_pool::internal_node_counter::m_nFree.get());
 268             */
 269         }
 270         static inline void check_stat( cds::intrusive::ellen_bintree::stat<> const& stat )
 271         {
 272             EXPECT_EQ( stat.m_nInternalNodeCreated, stat.m_nInternalNodeDeleted );
 273             EXPECT_EQ( stat.m_nUpdateDescCreated, stat.m_nUpdateDescDeleted );
 274             //EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), ellen_bintree_pool::internal_node_counter::m_nFree.get());
 275             EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), stat.m_nInternalNodeCreated );
 276             // true if RCU is not threaded
 277             //EXPECT_EQ( stat.m_nInternalNodeDeleted, ellen_bintree_pool::internal_node_counter::m_nFree.get());
 278         }
 279     }   // namespace ellen_bintree_check
 280
 281     template <typename GC, typename Key, typename T, typename Traits>
 282     static inline void additional_check( EllenBinTreeSet<GC, Key, T, Traits>& s )
 283     {
 284         //typedef EllenBinTreeSet<GC, Key, T, Traits> set_type;
 285         GC::force_dispose();
 286         ellen_bintree_check::check_stat( s.statistics());
 287     }
 288
 289     template <typename GC, typename Key, typename T, typename Traits>
 290     static inline void additional_cleanup( EllenBinTreeSet<GC, Key, T, Traits>& /*s*/ )
 291     {
 292         ellen_bintree_pool::internal_node_counter::reset();
 293     }
 294
 295     template <typename GC, typename Key, typename T, typename Traits>
 296     static inline void check_before_clear( cds::container::EllenBinTreeSet<GC, Key, T, Traits>& s )
 297     {
 298         EXPECT_TRUE( s.check_consistency());
 299     }
 300 } // namespace set
 301
 302 #define CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, ellen_set_type, key_type, value_type ) \
 303     TEST_F( fixture, ellen_set_type ) \
 304     { \
 305         typedef set::set_type< tag_EllenBinTreeSet, key_type, value_type >::ellen_set_type set_type; \
 306         test_case<set_type>(); \
 307     }
 308
 309 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 310 #   define CDSSTRESS_EllenBinTreeSet_SHRCU( fixture, test_case, key_type, value_type ) \
 311         CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_shb,      key_type, value_type ) \
 312
 313 #else
 314 #   define CDSSTRESS_EllenBinTreeSet_SHRCU( fixture, test_case, key_type, value_type )
 315 #endif
 316
 317
 318 #if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL > 0
 319 #   define CDSSTRESS_EllenBinTreeSet_HP_1( fixture, test_case, key_type, value_type ) \
 320         CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_yield_hp,       key_type, value_type ) \
 321         CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_yield_dhp,      key_type, value_type ) \
 322         CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_yield_rcu_gpb,  key_type, value_type ) \
 323
 324 #   define CDSSTRESS_EllenBinTreeSet_RCU_1( fixture, test_case, key_type, value_type ) \
 325         CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpi,        key_type, value_type ) \
 326         CDSSTRESS_EllenBinTreeSet_SHRCU( fixture, test_case, key_type, value_type )
 327
 328 #else
 329 #   define CDSSTRESS_EllenBinTreeSet_HP_1( fixture, test_case, key_type, value_type )
 330 #   define CDSSTRESS_EllenBinTreeSet_RCU_1( fixture, test_case, key_type, value_type )
 331 #endif
 332
 333 #define CDSSTRESS_EllenBinTreeSet_HP( fixture, test_case, key_type, value_type ) \
 334     CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_hp,             key_type, value_type ) \
 335     CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_dhp,            key_type, value_type ) \
 336     CDSSTRESS_EllenBinTreeSet_HP_1( fixture, test_case, key_type, value_type ) \
 337
 338 #define CDSSTRESS_EllenBinTreeSet_RCU( fixture, test_case, key_type, value_type ) \
 339     CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpb,        key_type, value_type ) \
 340     CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpt,        key_type, value_type ) \
 341     CDSSTRESS_EllenBinTreeSet_RCU_1( fixture, test_case, key_type, value_type ) \
 342
 343 #define CDSSTRESS_EllenBinTreeSet( fixture, test_case, key_type, value_type ) \
 344     CDSSTRESS_EllenBinTreeSet_HP( fixture, test_case, key_type, value_type ) \
 345     CDSSTRESS_EllenBinTreeSet_RCU( fixture, test_case, key_type, value_type ) \
 346
 347 #endif // #ifndef CDSUNIT_SET_TYPE_ELLEN_BINTREE_H