tests/unit/map2/map_type_ellen_bintree.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSUNIT_MAP_TYPE_ELLEN_BINTREE_H
   4 #define CDSUNIT_MAP_TYPE_ELLEN_BINTREE_H
   5
   6 #include "map2/map_type.h"
   7
   8 #include <cds/container/ellen_bintree_map_rcu.h>
   9 #include <cds/container/ellen_bintree_map_hp.h>
  10 #include <cds/container/ellen_bintree_map_dhp.h>
  11
  12 #include "ellen_bintree_update_desc_pool.h"
  13 #include "print_ellenbintree_stat.h"
  14
  15 namespace map2 {
  16
  17     template <class GC, typename Key, typename T, typename Traits = cc::ellen_bintree::traits >
  18     class EllenBinTreeMap : public cc::EllenBinTreeMap< GC, Key, T, Traits >
  19     {
  20         typedef cc::EllenBinTreeMap< GC, Key, T, Traits > base_class;
  21     public:
  22         template <typename Config>
  23         EllenBinTreeMap( Config const& /*cfg*/)
  24             : base_class()
  25         {}
  26
  27         // for testing
  28         static CDS_CONSTEXPR bool const c_bExtractSupported = true;
  29         static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
  30     };
  31
  32     struct tag_EllenBinTreeMap;
  33
  34     template <typename Key, typename Value>
  35     struct map_type< tag_EllenBinTreeMap, Key, Value >: public map_type_base< Key, Value >
  36     {
  37         typedef map_type_base< Key, Value > base_class;
  38         typedef typename base_class::compare    compare;
  39         typedef typename base_class::less       less;
  40
  41         struct ellen_bintree_props {
  42             struct hp_gc {
  43                 typedef cc::ellen_bintree::map_node<cds::gc::HP, Key, Value>        leaf_node;
  44                 typedef cc::ellen_bintree::internal_node< Key, leaf_node >          internal_node;
  45                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
  46             };
  47             struct dhp_gc {
  48                 typedef cc::ellen_bintree::map_node<cds::gc::DHP, Key, Value>       leaf_node;
  49                 typedef cc::ellen_bintree::internal_node< Key, leaf_node >          internal_node;
  50                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
  51             };
  52             struct gpi {
  53                 typedef cc::ellen_bintree::map_node<rcu_gpi, Key, Value>            leaf_node;
  54                 typedef cc::ellen_bintree::internal_node< Key, leaf_node >          internal_node;
  55                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
  56             };
  57             struct gpb {
  58                 typedef cc::ellen_bintree::map_node<rcu_gpb, Key, Value>            leaf_node;
  59                 typedef cc::ellen_bintree::internal_node< Key, leaf_node >          internal_node;
  60                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
  61             };
  62             struct gpt {
  63                 typedef cc::ellen_bintree::map_node<rcu_gpt, Key, Value>            leaf_node;
  64                 typedef cc::ellen_bintree::internal_node< Key, leaf_node >          internal_node;
  65                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
  66             };
  67 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
  68             struct shb {
  69                 typedef cc::ellen_bintree::map_node<rcu_shb, Key, Value>            leaf_node;
  70                 typedef cc::ellen_bintree::internal_node< Key, leaf_node >          internal_node;
  71                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
  72             };
  73             struct sht {
  74                 typedef cc::ellen_bintree::map_node<rcu_sht, Key, Value>            leaf_node;
  75                 typedef cc::ellen_bintree::internal_node< Key, leaf_node >          internal_node;
  76                 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node >  update_desc;
  77             };
  78 #endif
  79         };
  80
  81         struct traits_EllenBinTreeMap: public cc::ellen_bintree::make_set_traits<
  82                 co::less< less >
  83                 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
  84                 ,co::item_counter< cds::atomicity::item_counter >
  85             >::type
  86         {};
  87         struct traits_EllenBinTreeMap_hp : traits_EllenBinTreeMap {
  88             typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
  89         };
  90         typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_hp >EllenBinTreeMap_hp;
  91
  92         struct traits_EllenBinTreeMap_dhp : traits_EllenBinTreeMap {
  93             typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
  94         };
  95         typedef EllenBinTreeMap< cds::gc::DHP, Key, Value, traits_EllenBinTreeMap_dhp >EllenBinTreeMap_dhp;
  96
  97         struct traits_EllenBinTreeMap_gpi : traits_EllenBinTreeMap {
  98             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
  99         };
 100         typedef EllenBinTreeMap< rcu_gpi, Key, Value, traits_EllenBinTreeMap_gpi >EllenBinTreeMap_rcu_gpi;
 101
 102         struct traits_EllenBinTreeMap_gpb : traits_EllenBinTreeMap {
 103             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 104         };
 105         typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_gpb >EllenBinTreeMap_rcu_gpb;
 106
 107         struct traits_EllenBinTreeMap_gpt : traits_EllenBinTreeMap {
 108             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 109         };
 110         typedef EllenBinTreeMap< rcu_gpt, Key, Value, traits_EllenBinTreeMap_gpt >EllenBinTreeMap_rcu_gpt;
 111
 112 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 113         struct traits_EllenBinTreeMap_shb : traits_EllenBinTreeMap {
 114             typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 115         };
 116         typedef EllenBinTreeMap< rcu_shb, Key, Value, traits_EllenBinTreeMap_shb >EllenBinTreeMap_rcu_shb;
 117
 118         struct traits_EllenBinTreeMap_sht : traits_EllenBinTreeMap {
 119             typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 120         };
 121         typedef EllenBinTreeMap< rcu_sht, Key, Value, traits_EllenBinTreeMap_sht >EllenBinTreeMap_rcu_sht;
 122 #endif
 123
 124         struct traits_EllenBinTreeMap_yield : public traits_EllenBinTreeMap
 125         {
 126             typedef cds::backoff::yield back_off;
 127         };
 128         struct traits_EllenBinTreeMap_hp_yield : traits_EllenBinTreeMap_yield {
 129             typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 130         };
 131         typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_hp_yield >EllenBinTreeMap_hp_yield;
 132
 133         struct traits_EllenBinTreeMap_dhp_yield : traits_EllenBinTreeMap_yield {
 134             typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 135         };
 136         typedef EllenBinTreeMap< cds::gc::DHP, Key, Value, traits_EllenBinTreeMap_dhp_yield >EllenBinTreeMap_dhp_yield;
 137
 138         struct traits_EllenBinTreeMap_gpb_yield : traits_EllenBinTreeMap_yield {
 139             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 140         };
 141         typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_gpb_yield >EllenBinTreeMap_rcu_gpb_yield;
 142
 143
 144         struct traits_EllenBinTreeMap_stat: public cc::ellen_bintree::make_set_traits<
 145                 co::less< less >
 146                 ,cc::ellen_bintree::update_desc_allocator<
 147                     cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor >
 148                 >
 149                 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
 150                 ,co::stat< cc::ellen_bintree::stat<> >
 151                 ,co::item_counter< cds::atomicity::item_counter >
 152             >::type
 153         {};
 154
 155         struct traits_EllenBinTreeMap_stat_hp : public traits_EllenBinTreeMap_stat
 156         {
 157             typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 158         };
 159         typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_stat_hp > EllenBinTreeMap_hp_stat;
 160
 161         struct traits_EllenBinTreeMap_stat_dhp : public traits_EllenBinTreeMap_stat
 162         {
 163             typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 164         };
 165         typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_stat_dhp > EllenBinTreeMap_dhp_stat;
 166
 167         struct traits_EllenBinTreeMap_stat_gpi : public traits_EllenBinTreeMap_stat
 168         {
 169             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 170         };
 171         typedef EllenBinTreeMap< rcu_gpi, Key, Value, traits_EllenBinTreeMap_stat_gpi > EllenBinTreeMap_rcu_gpi_stat;
 172
 173         struct traits_EllenBinTreeMap_stat_gpb : public traits_EllenBinTreeMap_stat
 174         {
 175             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 176         };
 177         typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_stat_gpb > EllenBinTreeMap_rcu_gpb_stat;
 178
 179         struct traits_EllenBinTreeMap_stat_gpt : public traits_EllenBinTreeMap_stat
 180         {
 181             typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 182         };
 183         typedef EllenBinTreeMap< rcu_gpt, Key, Value, traits_EllenBinTreeMap_stat_gpt > EllenBinTreeMap_rcu_gpt_stat;
 184
 185 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 186         struct traits_EllenBinTreeMap_stat_shb : public traits_EllenBinTreeMap_stat
 187         {
 188             typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 189         };
 190         typedef EllenBinTreeMap< rcu_shb, Key, Value, traits_EllenBinTreeMap_stat_shb > EllenBinTreeMap_rcu_shb_stat;
 191
 192         struct traits_EllenBinTreeMap_stat_sht : public traits_EllenBinTreeMap_stat
 193         {
 194             typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
 195         };
 196         typedef EllenBinTreeMap< rcu_sht, Key, Value, traits_EllenBinTreeMap_stat_sht > EllenBinTreeMap_rcu_sht_stat;
 197 #endif
 198     };
 199
 200     template <typename GC, typename Key, typename T, typename Traits>
 201     static inline void print_stat( EllenBinTreeMap<GC, Key, T, Traits> const& s )
 202     {
 203         CPPUNIT_MSG( s.statistics() );
 204     }
 205     template <typename GC, typename Key, typename T, typename Traits>
 206     static inline void additional_cleanup( EllenBinTreeMap<GC, Key, T, Traits>& /*s*/ )
 207     {
 208         ellen_bintree_pool::internal_node_counter::reset();
 209     }
 210     namespace ellen_bintree_check {
 211         static inline void check_stat( cds::intrusive::ellen_bintree::empty_stat const& /*s*/ )
 212         {
 213             // This check is not valid for thread-based RCU
 214             /*
 215             CPPUNIT_CHECK_CURRENT_EX( ellen_bintree_pool::internal_node_counter::m_nAlloc.get() == ellen_bintree_pool::internal_node_counter::m_nFree.get(),
 216                 "m_nAlloc=" << ellen_bintree_pool::internal_node_counter::m_nAlloc.get()
 217                 << ", m_nFree=" << ellen_bintree_pool::internal_node_counter::m_nFree.get()
 218                 );
 219             */
 220         }
 221
 222         static inline void check_stat( cds::intrusive::ellen_bintree::stat<> const& stat )
 223         {
 224             CPPUNIT_CHECK_CURRENT_EX( stat.m_nInternalNodeCreated == stat.m_nInternalNodeDeleted,
 225                 "m_nInternalNodeCreated=" << stat.m_nInternalNodeCreated
 226                 << " m_nInternalNodeDeleted=" << stat.m_nInternalNodeDeleted );
 227             CPPUNIT_CHECK_CURRENT_EX( stat.m_nUpdateDescCreated == stat.m_nUpdateDescDeleted,
 228                 "m_nUpdateDescCreated=" << stat.m_nUpdateDescCreated
 229                 << " m_nUpdateDescDeleted=" << stat.m_nUpdateDescDeleted );
 230             CPPUNIT_CHECK_CURRENT_EX( ellen_bintree_pool::internal_node_counter::m_nAlloc.get() == stat.m_nInternalNodeCreated,
 231                 "allocated=" << ellen_bintree_pool::internal_node_counter::m_nAlloc.get()
 232                 << "m_nInternalNodeCreated=" << stat.m_nInternalNodeCreated );
 233         }
 234     }   // namespace ellen_bintree_check
 235     template <typename GC, typename Key, typename T, typename Traits>
 236     static inline void additional_check( EllenBinTreeMap<GC, Key, T, Traits>& s )
 237     {
 238         GC::force_dispose();
 239         ellen_bintree_check::check_stat( s.statistics() );
 240     }
 241
 242     template <typename GC, typename Key, typename T, typename Traits>
 243     static inline void check_before_cleanup( EllenBinTreeMap<GC, Key, T, Traits>& m )
 244     {
 245         CPPUNIT_MSG( "  Check internal consistency (single-threaded)..." );
 246         CPPUNIT_CHECK_CURRENT( m.check_consistency() );
 247     }
 248 }   // namespace map2
 249
 250 #endif // ifndef CDSUNIT_MAP_TYPE_ELLEN_BINTREE_H