2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSUNIT_SET_TYPE_ELLEN_BINTREE_H
32 #define CDSUNIT_SET_TYPE_ELLEN_BINTREE_H
36 #include <cds/container/ellen_bintree_set_rcu.h>
37 #include <cds/container/ellen_bintree_set_hp.h>
38 #include <cds/container/ellen_bintree_set_dhp.h>
40 #include <cds_test/stat_ellenbintree_out.h>
41 #include "framework/ellen_bintree_update_desc_pool.h"
45 template <class GC, typename Key, typename T, typename Traits = cc::ellen_bintree::traits >
46 class EllenBinTreeSet : public cc::EllenBinTreeSet< GC, Key, T, Traits >
48 typedef cc::EllenBinTreeSet< GC, Key, T, Traits > base_class;
50 template <typename Config>
51 EllenBinTreeSet( Config const& /*cfg*/ )
55 static CDS_CONSTEXPR bool const c_bExtractSupported = true;
56 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
57 static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
60 struct tag_EllenBinTreeSet;
62 template <typename Key, typename Val>
63 struct set_type< tag_EllenBinTreeSet, Key, Val >: public set_type_base< Key, Val >
65 typedef set_type_base< Key, Val > base_class;
66 typedef typename base_class::key_type key_type;
67 typedef typename base_class::key_val key_val;
68 typedef typename base_class::compare compare;
69 typedef typename base_class::less less;
70 typedef typename base_class::key_less key_less;
72 struct ellen_bintree_props {
73 struct key_extractor {
74 void operator()( key_type& dest, key_val const& src ) const
81 bool operator()( key_val const& v1, key_val const& v2 ) const
83 return key_less()( v1.key, v2.key );
85 bool operator()( key_type const& k, key_val const& v ) const
87 return key_less()( k, v.key );
89 bool operator()( key_val const& v, key_type const& k ) const
91 return key_less()( v.key, k );
93 bool operator()( key_type const& k1, key_type const& k2 ) const
95 return key_less()( k1, k2 );
100 typedef cc::ellen_bintree::node<cds::gc::HP, key_val> leaf_node;
101 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
102 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
106 typedef cc::ellen_bintree::node<cds::gc::DHP, key_val> leaf_node;
107 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
108 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
112 typedef cc::ellen_bintree::node<rcu_gpi, key_val> leaf_node;
113 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
114 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
117 typedef cc::ellen_bintree::node<rcu_gpb, key_val> leaf_node;
118 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
119 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
122 typedef cc::ellen_bintree::node<rcu_gpt, key_val> leaf_node;
123 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
124 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
126 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
128 typedef cc::ellen_bintree::node<rcu_shb, key_val> leaf_node;
129 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
130 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
135 struct traits_EllenBinTreeSet: public cc::ellen_bintree::make_set_traits<
136 cc::ellen_bintree::key_extractor< typename ellen_bintree_props::key_extractor >
137 ,co::less< typename ellen_bintree_props::less >
138 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
139 ,co::item_counter<cds::atomicity::cache_friendly_item_counter >
143 struct traits_EllenBinTreeSet_hp : public traits_EllenBinTreeSet
145 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
147 typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_hp > EllenBinTreeSet_hp;
149 struct traits_EllenBinTreeSet_dhp : public traits_EllenBinTreeSet
151 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
153 typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_dhp > EllenBinTreeSet_dhp;
155 struct traits_EllenBinTreeSet_gpi : public traits_EllenBinTreeSet
157 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
159 typedef EllenBinTreeSet< rcu_gpi, key_type, key_val, traits_EllenBinTreeSet_gpi > EllenBinTreeSet_rcu_gpi;
161 struct traits_EllenBinTreeSet_gpb : public traits_EllenBinTreeSet
163 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
165 typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_gpb > EllenBinTreeSet_rcu_gpb;
167 struct traits_EllenBinTreeSet_gpt : public traits_EllenBinTreeSet
169 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
171 typedef EllenBinTreeSet< rcu_gpt, key_type, key_val, traits_EllenBinTreeSet_gpt > EllenBinTreeSet_rcu_gpt;
173 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
174 struct traits_EllenBinTreeSet_shb : public traits_EllenBinTreeSet
176 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
178 typedef EllenBinTreeSet< rcu_shb, key_type, key_val, traits_EllenBinTreeSet_shb > EllenBinTreeSet_rcu_shb;
182 struct traits_EllenBinTreeSet_yield : public traits_EllenBinTreeSet
184 typedef cds::backoff::yield back_off;
187 struct traits_EllenBinTreeSet_yield_hp : public traits_EllenBinTreeSet_yield
189 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
191 typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_yield_hp > EllenBinTreeSet_yield_hp;
193 struct traits_EllenBinTreeSet_yield_dhp : public traits_EllenBinTreeSet_yield
195 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
197 typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_yield_dhp > EllenBinTreeSet_yield_dhp;
200 struct traits_EllenBinTreeSet_yield_gpb : public traits_EllenBinTreeSet_yield
202 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
204 typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_yield_gpb > EllenBinTreeSet_yield_rcu_gpb;
207 struct traits_EllenBinTreeSet_stat: public cc::ellen_bintree::make_set_traits<
208 cc::ellen_bintree::key_extractor< typename ellen_bintree_props::key_extractor >
209 ,co::less< typename ellen_bintree_props::less >
210 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
211 ,co::stat< cc::ellen_bintree::stat<> >
212 ,co::item_counter<cds::atomicity::cache_friendly_item_counter >
216 struct traits_EllenBinTreeSet_stat_hp : public traits_EllenBinTreeSet_stat
218 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
220 typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_stat_hp > EllenBinTreeSet_hp_stat;
222 struct traits_EllenBinTreeSet_stat_dhp : public traits_EllenBinTreeSet_stat
224 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
226 typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_stat_dhp > EllenBinTreeSet_dhp_stat;
228 struct traits_EllenBinTreeSet_stat_gpi : public traits_EllenBinTreeSet_stat
230 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
232 typedef EllenBinTreeSet< rcu_gpi, key_type, key_val, traits_EllenBinTreeSet_stat_gpi > EllenBinTreeSet_rcu_gpi_stat;
234 struct traits_EllenBinTreeSet_stat_gpb : public traits_EllenBinTreeSet_stat
236 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
238 typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_stat_gpb > EllenBinTreeSet_rcu_gpb_stat;
240 struct traits_EllenBinTreeSet_stat_gpt : public traits_EllenBinTreeSet_stat
242 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
244 typedef EllenBinTreeSet< rcu_gpt, key_type, key_val, traits_EllenBinTreeSet_stat_gpt > EllenBinTreeSet_rcu_gpt_stat;
246 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
247 struct traits_EllenBinTreeSet_stat_shb : public traits_EllenBinTreeSet_stat
249 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
251 typedef EllenBinTreeSet< rcu_shb, key_type, key_val, traits_EllenBinTreeSet_stat_shb > EllenBinTreeSet_rcu_shb_stat;
256 template <typename GC, typename Key, typename T, typename Traits>
257 static inline void print_stat( cds_test::property_stream& o, EllenBinTreeSet<GC, Key, T, Traits> const& s )
262 namespace ellen_bintree_check {
263 static inline void check_stat( cds::intrusive::ellen_bintree::empty_stat const& /*s*/ )
265 // Not true for threaded RCU
267 EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), ellen_bintree_pool::internal_node_counter::m_nFree.get());
270 static inline void check_stat( cds::intrusive::ellen_bintree::stat<> const& stat )
272 EXPECT_EQ( stat.m_nInternalNodeCreated, stat.m_nInternalNodeDeleted );
273 EXPECT_EQ( stat.m_nUpdateDescCreated, stat.m_nUpdateDescDeleted );
274 //EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), ellen_bintree_pool::internal_node_counter::m_nFree.get());
275 EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), stat.m_nInternalNodeCreated );
276 // true if RCU is not threaded
277 //EXPECT_EQ( stat.m_nInternalNodeDeleted, ellen_bintree_pool::internal_node_counter::m_nFree.get());
279 } // namespace ellen_bintree_check
281 template <typename GC, typename Key, typename T, typename Traits>
282 static inline void additional_check( EllenBinTreeSet<GC, Key, T, Traits>& s )
284 //typedef EllenBinTreeSet<GC, Key, T, Traits> set_type;
286 ellen_bintree_check::check_stat( s.statistics());
289 template <typename GC, typename Key, typename T, typename Traits>
290 static inline void additional_cleanup( EllenBinTreeSet<GC, Key, T, Traits>& /*s*/ )
292 ellen_bintree_pool::internal_node_counter::reset();
295 template <typename GC, typename Key, typename T, typename Traits>
296 static inline void check_before_clear( cds::container::EllenBinTreeSet<GC, Key, T, Traits>& s )
298 EXPECT_TRUE( s.check_consistency());
302 #define CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, ellen_set_type, key_type, value_type ) \
303 TEST_F( fixture, ellen_set_type ) \
305 typedef set::set_type< tag_EllenBinTreeSet, key_type, value_type >::ellen_set_type set_type; \
306 test_case<set_type>(); \
309 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
310 # define CDSSTRESS_EllenBinTreeSet_SHRCU( fixture, test_case, key_type, value_type ) \
311 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_shb, key_type, value_type ) \
314 # define CDSSTRESS_EllenBinTreeSet_SHRCU( fixture, test_case, key_type, value_type )
318 #if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL > 0
319 # define CDSSTRESS_EllenBinTreeSet_HP_1( fixture, test_case, key_type, value_type ) \
320 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_yield_hp, key_type, value_type ) \
321 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_yield_dhp, key_type, value_type ) \
322 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_yield_rcu_gpb, key_type, value_type ) \
324 # define CDSSTRESS_EllenBinTreeSet_RCU_1( fixture, test_case, key_type, value_type ) \
325 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpi, key_type, value_type ) \
326 CDSSTRESS_EllenBinTreeSet_SHRCU( fixture, test_case, key_type, value_type )
329 # define CDSSTRESS_EllenBinTreeSet_HP_1( fixture, test_case, key_type, value_type )
330 # define CDSSTRESS_EllenBinTreeSet_RCU_1( fixture, test_case, key_type, value_type )
333 #define CDSSTRESS_EllenBinTreeSet_HP( fixture, test_case, key_type, value_type ) \
334 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_hp, key_type, value_type ) \
335 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_dhp, key_type, value_type ) \
336 CDSSTRESS_EllenBinTreeSet_HP_1( fixture, test_case, key_type, value_type ) \
338 #define CDSSTRESS_EllenBinTreeSet_RCU( fixture, test_case, key_type, value_type ) \
339 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpb, key_type, value_type ) \
340 CDSSTRESS_EllenBinTreeSet_RCU_1( fixture, test_case, key_type, value_type ) \
342 #define CDSSTRESS_EllenBinTreeSet( fixture, test_case, key_type, value_type ) \
343 CDSSTRESS_EllenBinTreeSet_HP( fixture, test_case, key_type, value_type ) \
344 CDSSTRESS_EllenBinTreeSet_RCU( fixture, test_case, key_type, value_type ) \
346 #endif // #ifndef CDSUNIT_SET_TYPE_ELLEN_BINTREE_H