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 > >
142 struct traits_EllenBinTreeSet_hp : public traits_EllenBinTreeSet
144 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
146 typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_hp > EllenBinTreeSet_hp;
148 struct traits_EllenBinTreeSet_dhp : public traits_EllenBinTreeSet
150 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
152 typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_dhp > EllenBinTreeSet_dhp;
154 struct traits_EllenBinTreeSet_gpi : public traits_EllenBinTreeSet
156 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
158 typedef EllenBinTreeSet< rcu_gpi, key_type, key_val, traits_EllenBinTreeSet_gpi > EllenBinTreeSet_rcu_gpi;
160 struct traits_EllenBinTreeSet_gpb : public traits_EllenBinTreeSet
162 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
164 typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_gpb > EllenBinTreeSet_rcu_gpb;
166 struct traits_EllenBinTreeSet_gpt : public traits_EllenBinTreeSet
168 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
170 typedef EllenBinTreeSet< rcu_gpt, key_type, key_val, traits_EllenBinTreeSet_gpt > EllenBinTreeSet_rcu_gpt;
172 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
173 struct traits_EllenBinTreeSet_shb : public traits_EllenBinTreeSet
175 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
177 typedef EllenBinTreeSet< rcu_shb, key_type, key_val, traits_EllenBinTreeSet_shb > EllenBinTreeSet_rcu_shb;
181 struct traits_EllenBinTreeSet_yield : public traits_EllenBinTreeSet
183 typedef cds::backoff::yield back_off;
186 struct traits_EllenBinTreeSet_yield_hp : public traits_EllenBinTreeSet_yield
188 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
190 typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_yield_hp > EllenBinTreeSet_yield_hp;
192 struct traits_EllenBinTreeSet_yield_dhp : public traits_EllenBinTreeSet_yield
194 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
196 typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_yield_dhp > EllenBinTreeSet_yield_dhp;
199 struct traits_EllenBinTreeSet_yield_gpb : public traits_EllenBinTreeSet_yield
201 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
203 typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_yield_gpb > EllenBinTreeSet_yield_rcu_gpb;
206 struct traits_EllenBinTreeSet_stat: public cc::ellen_bintree::make_set_traits<
207 cc::ellen_bintree::key_extractor< typename ellen_bintree_props::key_extractor >
208 ,co::less< typename ellen_bintree_props::less >
209 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
210 ,co::stat< cc::ellen_bintree::stat<> >
214 struct traits_EllenBinTreeSet_stat_hp : public traits_EllenBinTreeSet_stat
216 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
218 typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_stat_hp > EllenBinTreeSet_hp_stat;
220 struct traits_EllenBinTreeSet_stat_dhp : public traits_EllenBinTreeSet_stat
222 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
224 typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_stat_dhp > EllenBinTreeSet_dhp_stat;
226 struct traits_EllenBinTreeSet_stat_gpi : public traits_EllenBinTreeSet_stat
228 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
230 typedef EllenBinTreeSet< rcu_gpi, key_type, key_val, traits_EllenBinTreeSet_stat_gpi > EllenBinTreeSet_rcu_gpi_stat;
232 struct traits_EllenBinTreeSet_stat_gpb : public traits_EllenBinTreeSet_stat
234 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
236 typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_stat_gpb > EllenBinTreeSet_rcu_gpb_stat;
238 struct traits_EllenBinTreeSet_stat_gpt : public traits_EllenBinTreeSet_stat
240 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
242 typedef EllenBinTreeSet< rcu_gpt, key_type, key_val, traits_EllenBinTreeSet_stat_gpt > EllenBinTreeSet_rcu_gpt_stat;
244 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
245 struct traits_EllenBinTreeSet_stat_shb : public traits_EllenBinTreeSet_stat
247 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
249 typedef EllenBinTreeSet< rcu_shb, key_type, key_val, traits_EllenBinTreeSet_stat_shb > EllenBinTreeSet_rcu_shb_stat;
254 template <typename GC, typename Key, typename T, typename Traits>
255 static inline void print_stat( cds_test::property_stream& o, EllenBinTreeSet<GC, Key, T, Traits> const& s )
260 namespace ellen_bintree_check {
261 static inline void check_stat( cds::intrusive::ellen_bintree::empty_stat const& /*s*/ )
263 // Not true for threaded RCU
265 EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), ellen_bintree_pool::internal_node_counter::m_nFree.get());
268 static inline void check_stat( cds::intrusive::ellen_bintree::stat<> const& stat )
270 EXPECT_EQ( stat.m_nInternalNodeCreated, stat.m_nInternalNodeDeleted );
271 EXPECT_EQ( stat.m_nUpdateDescCreated, stat.m_nUpdateDescDeleted );
272 //EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), ellen_bintree_pool::internal_node_counter::m_nFree.get());
273 EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), stat.m_nInternalNodeCreated );
274 // true if RCU is not threaded
275 //EXPECT_EQ( stat.m_nInternalNodeDeleted, ellen_bintree_pool::internal_node_counter::m_nFree.get());
277 } // namespace ellen_bintree_check
279 template <typename GC, typename Key, typename T, typename Traits>
280 static inline void additional_check( EllenBinTreeSet<GC, Key, T, Traits>& s )
282 //typedef EllenBinTreeSet<GC, Key, T, Traits> set_type;
284 ellen_bintree_check::check_stat( s.statistics());
287 template <typename GC, typename Key, typename T, typename Traits>
288 static inline void additional_cleanup( EllenBinTreeSet<GC, Key, T, Traits>& /*s*/ )
290 ellen_bintree_pool::internal_node_counter::reset();
293 template <typename GC, typename Key, typename T, typename Traits>
294 static inline void check_before_clear( cds::container::EllenBinTreeSet<GC, Key, T, Traits>& s )
296 EXPECT_TRUE( s.check_consistency());
300 #define CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, ellen_set_type, key_type, value_type ) \
301 TEST_F( fixture, ellen_set_type ) \
303 typedef set::set_type< tag_EllenBinTreeSet, key_type, value_type >::ellen_set_type set_type; \
304 test_case<set_type>(); \
307 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
308 # define CDSSTRESS_EllenBinTreeSet_SHRCU( fixture, test_case, key_type, value_type ) \
309 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_shb, key_type, value_type ) \
310 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_shb_stat, key_type, value_type ) \
313 # define CDSSTRESS_EllenBinTreeSet_SHRCU( fixture, test_case, key_type, value_type )
317 #if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL > 0
318 # define CDSSTRESS_EllenBinTreeSet_HP_1( fixture, test_case, key_type, value_type ) \
319 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_yield_hp, key_type, value_type ) \
320 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_yield_dhp, key_type, value_type ) \
321 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_yield_rcu_gpb, key_type, value_type ) \
323 # define CDSSTRESS_EllenBinTreeSet_RCU_1( fixture, test_case, key_type, value_type ) \
324 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpi, key_type, value_type ) \
325 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpi_stat, 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_case( fixture, test_case, EllenBinTreeSet_hp_stat, key_type, value_type ) \
337 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_dhp_stat, key_type, value_type ) \
338 CDSSTRESS_EllenBinTreeSet_HP_1( fixture, test_case, key_type, value_type ) \
340 #define CDSSTRESS_EllenBinTreeSet_RCU( fixture, test_case, key_type, value_type ) \
341 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpb, key_type, value_type ) \
342 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpt, key_type, value_type ) \
343 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpb_stat, key_type, value_type ) \
344 CDSSTRESS_EllenBinTreeSet_case( fixture, test_case, EllenBinTreeSet_rcu_gpt_stat, key_type, value_type ) \
345 CDSSTRESS_EllenBinTreeSet_RCU_1( fixture, test_case, key_type, value_type ) \
347 #define CDSSTRESS_EllenBinTreeSet( fixture, test_case, key_type, value_type ) \
348 CDSSTRESS_EllenBinTreeSet_HP( fixture, test_case, key_type, value_type ) \
349 CDSSTRESS_EllenBinTreeSet_RCU( fixture, test_case, key_type, value_type ) \
351 #endif // #ifndef CDSUNIT_SET_TYPE_ELLEN_BINTREE_H