3 #ifndef CDSUNIT_SET_TYPE_ELLEN_BINTREE_H
4 #define CDSUNIT_SET_TYPE_ELLEN_BINTREE_H
6 #include "set2/set_type.h"
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>
12 #include "print_ellenbintree_stat.h"
16 template <typename Key, typename Val>
17 struct set_type< cc::ellen_bintree::implementation_tag, Key, Val >: public set_type_base< Key, Val >
19 typedef set_type_base< Key, Val > base_class;
20 typedef typename base_class::key_type key_type;
21 typedef typename base_class::key_val key_val;
22 typedef typename base_class::compare compare;
23 typedef typename base_class::less less;
24 typedef typename base_class::key_less key_less;
26 struct ellen_bintree_props {
27 struct key_extractor {
28 void operator()( key_type& dest, key_val const& src ) const
35 bool operator()( key_val const& v1, key_val const& v2 ) const
37 return key_less()( v1.key, v2.key );
39 bool operator()( key_type const& k, key_val const& v ) const
41 return key_less()( k, v.key );
43 bool operator()( key_val const& v, key_type const& k ) const
45 return key_less()( v.key, k );
47 bool operator()( key_type const& k1, key_type const& k2 ) const
49 return key_less()( k1, k2 );
54 typedef cc::ellen_bintree::node<cds::gc::HP, key_val> leaf_node;
55 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
56 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
60 typedef cc::ellen_bintree::node<cds::gc::DHP, key_val> leaf_node;
61 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
62 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
66 typedef cc::ellen_bintree::node<rcu_gpi, key_val> leaf_node;
67 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
68 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
71 typedef cc::ellen_bintree::node<rcu_gpb, key_val> leaf_node;
72 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
73 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
76 typedef cc::ellen_bintree::node<rcu_gpt, 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;
80 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
82 typedef cc::ellen_bintree::node<rcu_shb, 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;
87 typedef cc::ellen_bintree::node<rcu_sht, 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;
94 struct traits_EllenBinTreeSet: public cc::ellen_bintree::make_set_traits<
95 cc::ellen_bintree::key_extractor< typename ellen_bintree_props::key_extractor >
96 ,co::less< typename ellen_bintree_props::less >
97 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
101 struct traits_EllenBinTreeSet_hp : public traits_EllenBinTreeSet
103 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
105 typedef cc::EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_hp > EllenBinTreeSet_hp;
107 struct traits_EllenBinTreeSet_dhp : public traits_EllenBinTreeSet
109 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
111 typedef cc::EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_dhp > EllenBinTreeSet_dhp;
113 struct traits_EllenBinTreeSet_gpi : public traits_EllenBinTreeSet
115 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
117 typedef cc::EllenBinTreeSet< rcu_gpi, key_type, key_val, traits_EllenBinTreeSet_gpi > EllenBinTreeSet_rcu_gpi;
119 struct traits_EllenBinTreeSet_gpb : public traits_EllenBinTreeSet
121 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
123 typedef cc::EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_gpb > EllenBinTreeSet_rcu_gpb;
125 struct traits_EllenBinTreeSet_gpt : public traits_EllenBinTreeSet
127 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
129 typedef cc::EllenBinTreeSet< rcu_gpt, key_type, key_val, traits_EllenBinTreeSet_gpt > EllenBinTreeSet_rcu_gpt;
131 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
132 struct traits_EllenBinTreeSet_shb : public traits_EllenBinTreeSet
134 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
136 typedef cc::EllenBinTreeSet< rcu_shb, key_type, key_val, traits_EllenBinTreeSet_shb > EllenBinTreeSet_rcu_shb;
138 struct traits_EllenBinTreeSet_sht : public traits_EllenBinTreeSet
140 typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
142 typedef cc::EllenBinTreeSet< rcu_sht, key_type, key_val, traits_EllenBinTreeSet_sht > EllenBinTreeSet_rcu_sht;
146 struct traits_EllenBinTreeSet_yield : public traits_EllenBinTreeSet
148 typedef cds::backoff::yield back_off;
151 struct traits_EllenBinTreeSet_yield_hp : public traits_EllenBinTreeSet_yield
153 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
155 typedef cc::EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_yield_hp > EllenBinTreeSet_yield_hp;
157 struct traits_EllenBinTreeSet_yield_dhp : public traits_EllenBinTreeSet_yield
159 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
161 typedef cc::EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_yield_dhp > EllenBinTreeSet_yield_dhp;
164 struct traits_EllenBinTreeSet_yield_gpb : public traits_EllenBinTreeSet_yield
166 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
168 typedef cc::EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_yield_gpb > EllenBinTreeSet_yield_rcu_gpb;
171 struct traits_EllenBinTreeSet_stat: public cc::ellen_bintree::make_set_traits<
172 cc::ellen_bintree::key_extractor< typename ellen_bintree_props::key_extractor >
173 ,co::less< typename ellen_bintree_props::less >
174 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
175 ,co::stat< cc::ellen_bintree::stat<> >
179 struct traits_EllenBinTreeSet_stat_hp : public traits_EllenBinTreeSet_stat
181 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
183 typedef cc::EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_stat_hp > EllenBinTreeSet_hp_stat;
185 struct traits_EllenBinTreeSet_stat_dhp : public traits_EllenBinTreeSet_stat
187 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
189 typedef cc::EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_stat_dhp > EllenBinTreeSet_dhp_stat;
191 struct traits_EllenBinTreeSet_stat_gpi : public traits_EllenBinTreeSet_stat
193 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
195 typedef cc::EllenBinTreeSet< rcu_gpi, key_type, key_val, traits_EllenBinTreeSet_stat_gpi > EllenBinTreeSet_rcu_gpi_stat;
197 struct traits_EllenBinTreeSet_stat_gpb : public traits_EllenBinTreeSet_stat
199 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
201 typedef cc::EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_stat_gpb > EllenBinTreeSet_rcu_gpb_stat;
203 struct traits_EllenBinTreeSet_stat_gpt : public traits_EllenBinTreeSet_stat
205 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
207 typedef cc::EllenBinTreeSet< rcu_gpt, key_type, key_val, traits_EllenBinTreeSet_stat_gpt > EllenBinTreeSet_rcu_gpt_stat;
209 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
210 struct traits_EllenBinTreeSet_stat_shb : public traits_EllenBinTreeSet_stat
212 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
214 typedef cc::EllenBinTreeSet< rcu_shb, key_type, key_val, traits_EllenBinTreeSet_stat_shb > EllenBinTreeSet_rcu_shb_stat;
216 struct traits_EllenBinTreeSet_stat_sht : public traits_EllenBinTreeSet_stat
218 typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
220 typedef cc::EllenBinTreeSet< rcu_sht, key_type, key_val, traits_EllenBinTreeSet_stat_sht > EllenBinTreeSet_rcu_sht_stat;
225 template <typename GC, typename Key, typename T, typename Traits>
226 static inline void print_stat( cc::EllenBinTreeSet<GC, Key, T, Traits> const& s )
228 CPPUNIT_MSG( s.statistics() );
231 namespace ellen_bintree_check {
232 static inline void check_stat( cds::intrusive::ellen_bintree::empty_stat const& /*s*/ )
234 // Not true for threaded RCU
236 CPPUNIT_CHECK_CURRENT_EX( ellen_bintree_pool::internal_node_counter::m_nAlloc.get() == ellen_bintree_pool::internal_node_counter::m_nFree.get(),
237 "m_nAlloc=" << ellen_bintree_pool::internal_node_counter::m_nAlloc.get()
238 << ", m_nFree=" << ellen_bintree_pool::internal_node_counter::m_nFree.get()
243 static inline void check_stat( cds::intrusive::ellen_bintree::stat<> const& stat )
245 CPPUNIT_CHECK_CURRENT( stat.m_nInternalNodeCreated == stat.m_nInternalNodeDeleted );
246 CPPUNIT_CHECK_CURRENT( stat.m_nUpdateDescCreated == stat.m_nUpdateDescDeleted );
247 //CPPUNIT_CHECK_CURRENT( ellen_bintree_pool::internal_node_counter::m_nAlloc.get() == ellen_bintree_pool::internal_node_counter::m_nFree.get() );
248 CPPUNIT_CHECK_CURRENT( ellen_bintree_pool::internal_node_counter::m_nAlloc.get() == stat.m_nInternalNodeCreated );
249 // true if RCU is not threaded
250 //CPPUNIT_CHECK_CURRENT( stat.m_nInternalNodeDeleted == ellen_bintree_pool::internal_node_counter::m_nFree.get() );
252 } // namespace ellen_bintree_check
254 template <typename GC, typename Key, typename T, typename Traits>
255 static inline void additional_check( cc::EllenBinTreeSet<GC, Key, T, Traits>& s )
258 ellen_bintree_check::check_stat( s.statistics() );
261 template <typename GC, typename Key, typename T, typename Traits>
262 static inline void additional_cleanup( cc::EllenBinTreeSet<GC, Key, T, Traits>& /*s*/ )
264 ellen_bintree_pool::internal_node_counter::reset();
267 template <typename GC, typename Key, typename T, typename Traits>
268 static inline void check_before_clear( cds::container::EllenBinTreeSet<GC, Key, T, Traits>& s )
270 CPPUNIT_CHECK_CURRENT( s.check_consistency() );
276 #endif // #ifndef CDSUNIT_SET_TYPE_ELLEN_BINTREE_H