tests/unit/set2/set_type_ellen_bintree.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSUNIT_SET_TYPE_ELLEN_BINTREE_H
   4 #define CDSUNIT_SET_TYPE_ELLEN_BINTREE_H
   5
   6 #include "set2/set_type.h"
   7
   8 #include <cds/container/ellen_bintree_set_rcu.h>
   9 #include <cds/container/ellen_bintree_set_hp.h>
  10 #include <cds/container/ellen_bintree_set_dhp.h>
  11
  12 #include "print_ellenbintree_stat.h"
  13
  14 namespace set2 {
  15
  16     template <class GC, typename Key, typename T, typename Traits = cc::ellen_bintree::traits >
  17     class EllenBinTreeSet : public cc::EllenBinTreeSet< GC, Key, T, Traits >
  18     {
  19         typedef cc::EllenBinTreeSet< GC, Key, T, Traits > base_class;
  20     public:
  21         template <typename Config>
  22         EllenBinTreeSet( Config const& /*cfg*/ )
  23         {}
  24
  25         // for testing
  26         static CDS_CONSTEXPR bool const c_bExtractSupported = true;
  27         static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
  28     };
  29
  30     struct tag_EllenBinTreeSet;
  31
  32     template <typename Key, typename Val>
  33     struct set_type< tag_EllenBinTreeSet, Key, Val >: public set_type_base< Key, Val >
  34     {
  35         typedef set_type_base< Key, Val > base_class;
  36         typedef typename base_class::key_type key_type;
  37         typedef typename base_class::key_val key_val;
  38         typedef typename base_class::compare compare;
  39         typedef typename base_class::less less;
  40         typedef typename base_class::key_less key_less;
  41
  42         struct ellen_bintree_props {
  43             struct key_extractor {
  44                 void operator()( key_type& dest, key_val const& src ) const
  45                 {
  46                     dest = src.key;
  47                 }
  48             };
  49
  50             struct less {
  51                 bool operator()( key_val const& v1, key_val const& v2 ) const
  52                 {
  53                     return key_less()( v1.key, v2.key );
  54                 }
  55                 bool operator()( key_type const& k, key_val const& v ) const
  56                 {
  57                     return key_less()( k, v.key );
  58                 }
  59                 bool operator()( key_val const& v, key_type const& k ) const
  60                 {
  61                     return key_less()( v.key, k );
  62                 }
  63                 bool operator()( key_type const& k1, key_type const& k2 ) const
  64                 {
  65                     return key_less()( k1, k2 );
  66                 }
  67             };
  68
  69             struct hp_gc {
  70                 typedef cc::ellen_bintree::node<cds::gc::HP, key_val>               leaf_node;
  71                 typedef cc::ellen_bintree::internal_node< key_type, leaf_node >     internal_node;
  72                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
  73             };
  74
  75             struct dhp_gc {
  76                 typedef cc::ellen_bintree::node<cds::gc::DHP, key_val>              leaf_node;
  77                 typedef cc::ellen_bintree::internal_node< key_type, leaf_node >     internal_node;
  78                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
  79             };
  80
  81             struct gpi {
  82                 typedef cc::ellen_bintree::node<rcu_gpi, key_val>                   leaf_node;
  83                 typedef cc::ellen_bintree::internal_node< key_type, leaf_node >     internal_node;
  84                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
  85             };
  86             struct gpb {
  87                 typedef cc::ellen_bintree::node<rcu_gpb, key_val>                   leaf_node;
  88                 typedef cc::ellen_bintree::internal_node< key_type, leaf_node >     internal_node;
  89                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
  90             };
  91             struct gpt {
  92                 typedef cc::ellen_bintree::node<rcu_gpt, key_val>                   leaf_node;
  93                 typedef cc::ellen_bintree::internal_node< key_type, leaf_node >     internal_node;
  94                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
  95             };
  96 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
  97             struct shb {
  98                 typedef cc::ellen_bintree::node<rcu_shb, key_val>                   leaf_node;
  99                 typedef cc::ellen_bintree::internal_node< key_type, leaf_node >     internal_node;
 100                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
 101             };
 102             struct sht {
 103                 typedef cc::ellen_bintree::node<rcu_sht, key_val>                   leaf_node;
 104                 typedef cc::ellen_bintree::internal_node< key_type, leaf_node >     internal_node;
 105                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
 106             };
 107 #endif
 108         };
 109
 110         struct traits_EllenBinTreeSet: public cc::ellen_bintree::make_set_traits<
 111             cc::ellen_bintree::key_extractor< typename ellen_bintree_props::key_extractor >
 112             ,co::less< typename ellen_bintree_props::less >
 113             ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
 114         >::type
 115         {};
 116
 117         struct traits_EllenBinTreeSet_hp : public traits_EllenBinTreeSet
 118         {
 119             typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 120         };
 121         typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_hp > EllenBinTreeSet_hp;
 122
 123         struct traits_EllenBinTreeSet_dhp : public traits_EllenBinTreeSet
 124         {
 125             typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 126         };
 127         typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_dhp > EllenBinTreeSet_dhp;
 128
 129         struct traits_EllenBinTreeSet_gpi : public traits_EllenBinTreeSet
 130         {
 131             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 132         };
 133         typedef EllenBinTreeSet< rcu_gpi, key_type, key_val, traits_EllenBinTreeSet_gpi > EllenBinTreeSet_rcu_gpi;
 134
 135         struct traits_EllenBinTreeSet_gpb : public traits_EllenBinTreeSet
 136         {
 137             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 138         };
 139         typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_gpb > EllenBinTreeSet_rcu_gpb;
 140
 141         struct traits_EllenBinTreeSet_gpt : public traits_EllenBinTreeSet
 142         {
 143             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 144         };
 145         typedef EllenBinTreeSet< rcu_gpt, key_type, key_val, traits_EllenBinTreeSet_gpt > EllenBinTreeSet_rcu_gpt;
 146
 147 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 148         struct traits_EllenBinTreeSet_shb : public traits_EllenBinTreeSet
 149         {
 150             typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 151         };
 152         typedef EllenBinTreeSet< rcu_shb, key_type, key_val, traits_EllenBinTreeSet_shb > EllenBinTreeSet_rcu_shb;
 153
 154         struct traits_EllenBinTreeSet_sht : public traits_EllenBinTreeSet
 155         {
 156             typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 157         };
 158         typedef EllenBinTreeSet< rcu_sht, key_type, key_val, traits_EllenBinTreeSet_sht > EllenBinTreeSet_rcu_sht;
 159 #endif
 160
 161         //
 162         struct traits_EllenBinTreeSet_yield : public traits_EllenBinTreeSet
 163         {
 164             typedef cds::backoff::yield back_off;
 165         };
 166
 167         struct traits_EllenBinTreeSet_yield_hp : public traits_EllenBinTreeSet_yield
 168         {
 169             typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 170         };
 171         typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_yield_hp > EllenBinTreeSet_yield_hp;
 172
 173         struct traits_EllenBinTreeSet_yield_dhp : public traits_EllenBinTreeSet_yield
 174         {
 175             typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 176         };
 177         typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_yield_dhp > EllenBinTreeSet_yield_dhp;
 178
 179
 180         struct traits_EllenBinTreeSet_yield_gpb : public traits_EllenBinTreeSet_yield
 181         {
 182             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 183         };
 184         typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_yield_gpb > EllenBinTreeSet_yield_rcu_gpb;
 185
 186
 187         struct traits_EllenBinTreeSet_stat: public cc::ellen_bintree::make_set_traits<
 188             cc::ellen_bintree::key_extractor< typename ellen_bintree_props::key_extractor >
 189             ,co::less< typename ellen_bintree_props::less >
 190             ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
 191             ,co::stat< cc::ellen_bintree::stat<> >
 192         >::type
 193         {};
 194
 195         struct traits_EllenBinTreeSet_stat_hp : public traits_EllenBinTreeSet_stat
 196         {
 197             typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 198         };
 199         typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_stat_hp > EllenBinTreeSet_hp_stat;
 200
 201         struct traits_EllenBinTreeSet_stat_dhp : public traits_EllenBinTreeSet_stat
 202         {
 203             typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 204         };
 205         typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_stat_dhp > EllenBinTreeSet_dhp_stat;
 206
 207         struct traits_EllenBinTreeSet_stat_gpi : public traits_EllenBinTreeSet_stat
 208         {
 209             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 210         };
 211         typedef EllenBinTreeSet< rcu_gpi, key_type, key_val, traits_EllenBinTreeSet_stat_gpi > EllenBinTreeSet_rcu_gpi_stat;
 212
 213         struct traits_EllenBinTreeSet_stat_gpb : public traits_EllenBinTreeSet_stat
 214         {
 215             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 216         };
 217         typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_stat_gpb > EllenBinTreeSet_rcu_gpb_stat;
 218
 219         struct traits_EllenBinTreeSet_stat_gpt : public traits_EllenBinTreeSet_stat
 220         {
 221             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 222         };
 223         typedef EllenBinTreeSet< rcu_gpt, key_type, key_val, traits_EllenBinTreeSet_stat_gpt > EllenBinTreeSet_rcu_gpt_stat;
 224
 225 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 226         struct traits_EllenBinTreeSet_stat_shb : public traits_EllenBinTreeSet_stat
 227         {
 228             typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 229         };
 230         typedef EllenBinTreeSet< rcu_shb, key_type, key_val, traits_EllenBinTreeSet_stat_shb > EllenBinTreeSet_rcu_shb_stat;
 231
 232         struct traits_EllenBinTreeSet_stat_sht : public traits_EllenBinTreeSet_stat
 233         {
 234             typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 235         };
 236         typedef EllenBinTreeSet< rcu_sht, key_type, key_val, traits_EllenBinTreeSet_stat_sht > EllenBinTreeSet_rcu_sht_stat;
 237 #endif
 238
 239     };
 240
 241     template <typename GC, typename Key, typename T, typename Traits>
 242     static inline void print_stat( EllenBinTreeSet<GC, Key, T, Traits> const& s )
 243     {
 244         CPPUNIT_MSG( s.statistics() );
 245     }
 246
 247     namespace ellen_bintree_check {
 248         static inline void check_stat( cds::intrusive::ellen_bintree::empty_stat const& /*s*/ )
 249         {
 250             // Not true for threaded RCU
 251             /*
 252             CPPUNIT_CHECK_CURRENT_EX( ellen_bintree_pool::internal_node_counter::m_nAlloc.get() == ellen_bintree_pool::internal_node_counter::m_nFree.get(),
 253                 "m_nAlloc=" << ellen_bintree_pool::internal_node_counter::m_nAlloc.get()
 254                 << ", m_nFree=" << ellen_bintree_pool::internal_node_counter::m_nFree.get()
 255                 );
 256             */
 257         }
 258
 259         static inline void check_stat( cds::intrusive::ellen_bintree::stat<> const& stat )
 260         {
 261             CPPUNIT_CHECK_CURRENT( stat.m_nInternalNodeCreated == stat.m_nInternalNodeDeleted );
 262             CPPUNIT_CHECK_CURRENT( stat.m_nUpdateDescCreated == stat.m_nUpdateDescDeleted );
 263             //CPPUNIT_CHECK_CURRENT( ellen_bintree_pool::internal_node_counter::m_nAlloc.get() == ellen_bintree_pool::internal_node_counter::m_nFree.get() );
 264             CPPUNIT_CHECK_CURRENT( ellen_bintree_pool::internal_node_counter::m_nAlloc.get() == stat.m_nInternalNodeCreated );
 265             // true if RCU is not threaded
 266             //CPPUNIT_CHECK_CURRENT( stat.m_nInternalNodeDeleted == ellen_bintree_pool::internal_node_counter::m_nFree.get() );
 267         }
 268     }   // namespace ellen_bintree_check
 269
 270     template <typename GC, typename Key, typename T, typename Traits>
 271     static inline void additional_check( EllenBinTreeSet<GC, Key, T, Traits>& s )
 272     {
 273         GC::force_dispose();
 274         ellen_bintree_check::check_stat( s.statistics() );
 275     }
 276
 277     template <typename GC, typename Key, typename T, typename Traits>
 278     static inline void additional_cleanup( EllenBinTreeSet<GC, Key, T, Traits>& /*s*/ )
 279     {
 280         ellen_bintree_pool::internal_node_counter::reset();
 281     }
 282
 283     template <typename GC, typename Key, typename T, typename Traits>
 284     static inline void check_before_clear( cds::container::EllenBinTreeSet<GC, Key, T, Traits>& s )
 285     {
 286         CPPUNIT_CHECK_CURRENT( s.check_consistency() );
 287     }
 288
 289
 290 } // namespace set2
 291
 292 #endif // #ifndef CDSUNIT_SET_TYPE_ELLEN_BINTREE_H