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;
133 typedef cc::ellen_bintree::node<rcu_sht, key_val> leaf_node;
134 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
135 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
140 struct traits_EllenBinTreeSet: public cc::ellen_bintree::make_set_traits<
141 cc::ellen_bintree::key_extractor< typename ellen_bintree_props::key_extractor >
142 ,co::less< typename ellen_bintree_props::less >
143 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
147 struct traits_EllenBinTreeSet_hp : public traits_EllenBinTreeSet
149 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
151 typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_hp > EllenBinTreeSet_hp;
153 struct traits_EllenBinTreeSet_dhp : public traits_EllenBinTreeSet
155 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
157 typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_dhp > EllenBinTreeSet_dhp;
159 struct traits_EllenBinTreeSet_gpi : public traits_EllenBinTreeSet
161 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
163 typedef EllenBinTreeSet< rcu_gpi, key_type, key_val, traits_EllenBinTreeSet_gpi > EllenBinTreeSet_rcu_gpi;
165 struct traits_EllenBinTreeSet_gpb : public traits_EllenBinTreeSet
167 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
169 typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_gpb > EllenBinTreeSet_rcu_gpb;
171 struct traits_EllenBinTreeSet_gpt : public traits_EllenBinTreeSet
173 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
175 typedef EllenBinTreeSet< rcu_gpt, key_type, key_val, traits_EllenBinTreeSet_gpt > EllenBinTreeSet_rcu_gpt;
177 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
178 struct traits_EllenBinTreeSet_shb : public traits_EllenBinTreeSet
180 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
182 typedef EllenBinTreeSet< rcu_shb, key_type, key_val, traits_EllenBinTreeSet_shb > EllenBinTreeSet_rcu_shb;
184 struct traits_EllenBinTreeSet_sht : public traits_EllenBinTreeSet
186 typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
188 typedef EllenBinTreeSet< rcu_sht, key_type, key_val, traits_EllenBinTreeSet_sht > EllenBinTreeSet_rcu_sht;
192 struct traits_EllenBinTreeSet_yield : public traits_EllenBinTreeSet
194 typedef cds::backoff::yield back_off;
197 struct traits_EllenBinTreeSet_yield_hp : public traits_EllenBinTreeSet_yield
199 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
201 typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_yield_hp > EllenBinTreeSet_yield_hp;
203 struct traits_EllenBinTreeSet_yield_dhp : public traits_EllenBinTreeSet_yield
205 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
207 typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_yield_dhp > EllenBinTreeSet_yield_dhp;
210 struct traits_EllenBinTreeSet_yield_gpb : public traits_EllenBinTreeSet_yield
212 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
214 typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_yield_gpb > EllenBinTreeSet_yield_rcu_gpb;
217 struct traits_EllenBinTreeSet_stat: public cc::ellen_bintree::make_set_traits<
218 cc::ellen_bintree::key_extractor< typename ellen_bintree_props::key_extractor >
219 ,co::less< typename ellen_bintree_props::less >
220 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
221 ,co::stat< cc::ellen_bintree::stat<> >
225 struct traits_EllenBinTreeSet_stat_hp : public traits_EllenBinTreeSet_stat
227 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
229 typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_stat_hp > EllenBinTreeSet_hp_stat;
231 struct traits_EllenBinTreeSet_stat_dhp : public traits_EllenBinTreeSet_stat
233 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
235 typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_stat_dhp > EllenBinTreeSet_dhp_stat;
237 struct traits_EllenBinTreeSet_stat_gpi : public traits_EllenBinTreeSet_stat
239 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
241 typedef EllenBinTreeSet< rcu_gpi, key_type, key_val, traits_EllenBinTreeSet_stat_gpi > EllenBinTreeSet_rcu_gpi_stat;
243 struct traits_EllenBinTreeSet_stat_gpb : public traits_EllenBinTreeSet_stat
245 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
247 typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_stat_gpb > EllenBinTreeSet_rcu_gpb_stat;
249 struct traits_EllenBinTreeSet_stat_gpt : public traits_EllenBinTreeSet_stat
251 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
253 typedef EllenBinTreeSet< rcu_gpt, key_type, key_val, traits_EllenBinTreeSet_stat_gpt > EllenBinTreeSet_rcu_gpt_stat;
255 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
256 struct traits_EllenBinTreeSet_stat_shb : public traits_EllenBinTreeSet_stat
258 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
260 typedef EllenBinTreeSet< rcu_shb, key_type, key_val, traits_EllenBinTreeSet_stat_shb > EllenBinTreeSet_rcu_shb_stat;
262 struct traits_EllenBinTreeSet_stat_sht : public traits_EllenBinTreeSet_stat
264 typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
266 typedef EllenBinTreeSet< rcu_sht, key_type, key_val, traits_EllenBinTreeSet_stat_sht > EllenBinTreeSet_rcu_sht_stat;
271 template <typename GC, typename Key, typename T, typename Traits>
272 static inline void print_stat( cds_test::property_stream& o, EllenBinTreeSet<GC, Key, T, Traits> const& s )
277 namespace ellen_bintree_check {
278 static inline void check_stat( cds::intrusive::ellen_bintree::empty_stat const& /*s*/ )
280 // Not true for threaded RCU
282 EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), ellen_bintree_pool::internal_node_counter::m_nFree.get());
285 static inline void check_stat( cds::intrusive::ellen_bintree::stat<> const& stat )
287 EXPECT_EQ( stat.m_nInternalNodeCreated, stat.m_nInternalNodeDeleted );
288 EXPECT_EQ( stat.m_nUpdateDescCreated, stat.m_nUpdateDescDeleted );
289 //EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), ellen_bintree_pool::internal_node_counter::m_nFree.get());
290 EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), stat.m_nInternalNodeCreated );
291 // true if RCU is not threaded
292 //EXPECT_EQ( stat.m_nInternalNodeDeleted, ellen_bintree_pool::internal_node_counter::m_nFree.get());
294 } // namespace ellen_bintree_check
296 template <typename GC, typename Key, typename T, typename Traits>
297 static inline void additional_check( EllenBinTreeSet<GC, Key, T, Traits>& s )
299 //typedef EllenBinTreeSet<GC, Key, T, Traits> set_type;
301 ellen_bintree_check::check_stat( s.statistics());
303 bool const threaded_rcu = std::is_same<typename set_type::rcu_tag, cds::urcu::general_threaded_tag >::value
304 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
305 || std::is_same<typename set_type::rcu_tag, signal_threaded_tag >::value
308 if ( !threaded_rcu ) {
309 EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), ellen_bintree_pool::internal_node_counter::m_nFree.get());
314 template <typename GC, typename Key, typename T, typename Traits>
315 static inline void additional_cleanup( EllenBinTreeSet<GC, Key, T, Traits>& /*s*/ )
317 ellen_bintree_pool::internal_node_counter::reset();
320 template <typename GC, typename Key, typename T, typename Traits>
321 static inline void check_before_clear( cds::container::EllenBinTreeSet<GC, Key, T, Traits>& s )
323 EXPECT_TRUE( s.check_consistency());
327 #define CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, ellen_set_type, key_type, value_type ) \
328 TEST_F( fixture, ellen_set_type ) \
330 typedef set::set_type< tag_EllenBinTreeSet, key_type, value_type >::ellen_set_type set_type; \
331 test_case<set_type>(); \
334 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
335 # define CDSSTRESS_EllenBinTreeSet_SHRCU( fixture, test_case, key_type, value_type ) \
336 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_shb, key_type, value_type ) \
337 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_sht, key_type, value_type ) \
338 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_shb_stat, key_type, value_type ) \
339 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_sht_stat, key_type, value_type )
341 # define CDSSTRESS_EllenBinTreeSet_SHRCU( fixture, test_case, key_type, value_type )
345 #if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL > 0
346 # define CDSSTRESS_EllenBinTreeSet_HP_1( fixture, test_case, key_type, value_type ) \
347 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_yield_hp, key_type, value_type ) \
348 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_yield_dhp, key_type, value_type ) \
349 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_yield_rcu_gpb, key_type, value_type ) \
351 # define CDSSTRESS_EllenBinTreeSet_RCU_1( fixture, test_case, key_type, value_type ) \
352 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpi, key_type, value_type ) \
353 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpi_stat, key_type, value_type ) \
354 CDSSTRESS_EllenBinTreeSet_SHRCU( fixture, test_case, key_type, value_type )
357 # define CDSSTRESS_EllenBinTreeSet_HP_1( fixture, test_case, key_type, value_type )
358 # define CDSSTRESS_EllenBinTreeSet_RCU_1( fixture, test_case, key_type, value_type )
361 #define CDSSTRESS_EllenBinTreeSet_HP( fixture, test_case, key_type, value_type ) \
362 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_hp, key_type, value_type ) \
363 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_dhp, key_type, value_type ) \
364 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_hp_stat, key_type, value_type ) \
365 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_dhp_stat, key_type, value_type ) \
366 CDSSTRESS_EllenBinTreeSet_HP_1( fixture, test_case, key_type, value_type ) \
368 #define CDSSTRESS_EllenBinTreeSet_RCU( fixture, test_case, key_type, value_type ) \
369 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpb, key_type, value_type ) \
370 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpt, key_type, value_type ) \
371 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpb_stat, key_type, value_type ) \
372 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpt_stat, key_type, value_type ) \
373 CDSSTRESS_EllenBinTreeSet_RCU_1( fixture, test_case, key_type, value_type ) \
375 #define CDSSTRESS_EllenBinTreeSet( fixture, test_case, key_type, value_type ) \
376 CDSSTRESS_EllenBinTreeSet_HP( fixture, test_case, key_type, value_type ) \
377 CDSSTRESS_EllenBinTreeSet_RCU( fixture, test_case, key_type, value_type ) \
379 #endif // #ifndef CDSUNIT_SET_TYPE_ELLEN_BINTREE_H