3 #ifndef CDSUNIT_MAP_TYPE_ELLEN_BINTREE_H
4 #define CDSUNIT_MAP_TYPE_ELLEN_BINTREE_H
6 #include "map2/map_type.h"
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>
12 #include "ellen_bintree_update_desc_pool.h"
13 #include "print_ellenbintree_stat.h"
17 template <class GC, typename Key, typename T, typename Traits = cc::ellen_bintree::traits >
18 class EllenBinTreeMap : public cc::EllenBinTreeMap< GC, Key, T, Traits >
20 typedef cc::EllenBinTreeMap< GC, Key, T, Traits > base_class;
22 template <typename Config>
23 EllenBinTreeMap( Config const& /*cfg*/)
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;
33 struct tag_EllenBinTreeMap;
35 template <typename Key, typename Value>
36 struct map_type< tag_EllenBinTreeMap, Key, Value >: public map_type_base< Key, Value >
38 typedef map_type_base< Key, Value > base_class;
39 typedef typename base_class::compare compare;
40 typedef typename base_class::less less;
42 struct ellen_bintree_props {
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;
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;
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;
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;
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;
68 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
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;
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;
82 struct traits_EllenBinTreeMap: public cc::ellen_bintree::make_set_traits<
84 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
85 ,co::item_counter< cds::atomicity::item_counter >
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;
91 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_hp >EllenBinTreeMap_hp;
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;
96 typedef EllenBinTreeMap< cds::gc::DHP, Key, Value, traits_EllenBinTreeMap_dhp >EllenBinTreeMap_dhp;
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;
101 typedef EllenBinTreeMap< rcu_gpi, Key, Value, traits_EllenBinTreeMap_gpi >EllenBinTreeMap_rcu_gpi;
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;
106 typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_gpb >EllenBinTreeMap_rcu_gpb;
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;
111 typedef EllenBinTreeMap< rcu_gpt, Key, Value, traits_EllenBinTreeMap_gpt >EllenBinTreeMap_rcu_gpt;
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;
117 typedef EllenBinTreeMap< rcu_shb, Key, Value, traits_EllenBinTreeMap_shb >EllenBinTreeMap_rcu_shb;
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;
122 typedef EllenBinTreeMap< rcu_sht, Key, Value, traits_EllenBinTreeMap_sht >EllenBinTreeMap_rcu_sht;
125 struct traits_EllenBinTreeMap_yield : public traits_EllenBinTreeMap
127 typedef cds::backoff::yield back_off;
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;
132 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_hp_yield >EllenBinTreeMap_hp_yield;
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;
137 typedef EllenBinTreeMap< cds::gc::DHP, Key, Value, traits_EllenBinTreeMap_dhp_yield >EllenBinTreeMap_dhp_yield;
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;
142 typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_gpb_yield >EllenBinTreeMap_rcu_gpb_yield;
145 struct traits_EllenBinTreeMap_stat: public cc::ellen_bintree::make_set_traits<
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 >
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 >
156 struct traits_EllenBinTreeMap_stat_hp : public traits_EllenBinTreeMap_stat
158 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
160 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_stat_hp > EllenBinTreeMap_hp_stat;
162 struct traits_EllenBinTreeMap_stat_dhp : public traits_EllenBinTreeMap_stat
164 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
166 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_stat_dhp > EllenBinTreeMap_dhp_stat;
168 struct traits_EllenBinTreeMap_stat_gpi : public traits_EllenBinTreeMap_stat
170 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
172 typedef EllenBinTreeMap< rcu_gpi, Key, Value, traits_EllenBinTreeMap_stat_gpi > EllenBinTreeMap_rcu_gpi_stat;
174 struct traits_EllenBinTreeMap_stat_gpb : public traits_EllenBinTreeMap_stat
176 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
178 typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_stat_gpb > EllenBinTreeMap_rcu_gpb_stat;
180 struct traits_EllenBinTreeMap_stat_gpt : public traits_EllenBinTreeMap_stat
182 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
184 typedef EllenBinTreeMap< rcu_gpt, Key, Value, traits_EllenBinTreeMap_stat_gpt > EllenBinTreeMap_rcu_gpt_stat;
186 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
187 struct traits_EllenBinTreeMap_stat_shb : public traits_EllenBinTreeMap_stat
189 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
191 typedef EllenBinTreeMap< rcu_shb, Key, Value, traits_EllenBinTreeMap_stat_shb > EllenBinTreeMap_rcu_shb_stat;
193 struct traits_EllenBinTreeMap_stat_sht : public traits_EllenBinTreeMap_stat
195 typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
197 typedef EllenBinTreeMap< rcu_sht, Key, Value, traits_EllenBinTreeMap_stat_sht > EllenBinTreeMap_rcu_sht_stat;
201 template <typename GC, typename Key, typename T, typename Traits>
202 static inline void print_stat( EllenBinTreeMap<GC, Key, T, Traits> const& s )
204 CPPUNIT_MSG( s.statistics() );
206 template <typename GC, typename Key, typename T, typename Traits>
207 static inline void additional_cleanup( EllenBinTreeMap<GC, Key, T, Traits>& /*s*/ )
209 ellen_bintree_pool::internal_node_counter::reset();
211 namespace ellen_bintree_check {
212 static inline void check_stat( cds::intrusive::ellen_bintree::empty_stat const& /*s*/ )
214 // This check is not valid for thread-based RCU
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()
223 static inline void check_stat( cds::intrusive::ellen_bintree::stat<> const& stat )
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 );
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 )
240 ellen_bintree_check::check_stat( s.statistics() );
243 template <typename GC, typename Key, typename T, typename Traits>
244 static inline void check_before_cleanup( EllenBinTreeMap<GC, Key, T, Traits>& m )
246 CPPUNIT_MSG( " Check internal consistency (single-threaded)..." );
247 CPPUNIT_CHECK_CURRENT( m.check_consistency() );
251 #endif // ifndef CDSUNIT_MAP_TYPE_ELLEN_BINTREE_H