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