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_MAP_TYPE_ELLEN_BINTREE_H
32 #define CDSUNIT_MAP_TYPE_ELLEN_BINTREE_H
36 #include <cds/container/ellen_bintree_map_rcu.h>
37 #include <cds/container/ellen_bintree_map_hp.h>
38 #include <cds/container/ellen_bintree_map_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 EllenBinTreeMap : public cc::EllenBinTreeMap< GC, Key, T, Traits >
48 typedef cc::EllenBinTreeMap< GC, Key, T, Traits > base_class;
50 template <typename Config>
51 EllenBinTreeMap( Config const& /*cfg*/)
55 std::pair<Key, bool> extract_min_key()
57 auto xp = base_class::extract_min();
59 return std::make_pair( xp->first, true );
60 return std::make_pair( Key(), false );
63 std::pair<Key, bool> extract_max_key()
65 auto xp = base_class::extract_max();
67 return std::make_pair( xp->first, true );
68 return std::make_pair( Key(), false );
72 static CDS_CONSTEXPR bool const c_bExtractSupported = true;
73 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
74 static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
77 struct tag_EllenBinTreeMap;
79 template <typename Key, typename Value>
80 struct map_type< tag_EllenBinTreeMap, Key, Value >: public map_type_base< Key, Value >
82 typedef map_type_base< Key, Value > base_class;
83 typedef typename base_class::key_compare compare;
84 typedef typename base_class::key_less less;
86 struct ellen_bintree_props {
88 typedef cc::ellen_bintree::map_node<cds::gc::HP, Key, Value> leaf_node;
89 typedef cc::ellen_bintree::internal_node< Key, leaf_node > internal_node;
90 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
93 typedef cc::ellen_bintree::map_node<cds::gc::DHP, Key, Value> leaf_node;
94 typedef cc::ellen_bintree::internal_node< Key, leaf_node > internal_node;
95 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
98 typedef cc::ellen_bintree::map_node<rcu_gpi, Key, Value> leaf_node;
99 typedef cc::ellen_bintree::internal_node< Key, leaf_node > internal_node;
100 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
103 typedef cc::ellen_bintree::map_node<rcu_gpb, Key, Value> leaf_node;
104 typedef cc::ellen_bintree::internal_node< Key, leaf_node > internal_node;
105 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
108 typedef cc::ellen_bintree::map_node<rcu_gpt, Key, Value> leaf_node;
109 typedef cc::ellen_bintree::internal_node< Key, leaf_node > internal_node;
110 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
112 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
114 typedef cc::ellen_bintree::map_node<rcu_shb, Key, Value> leaf_node;
115 typedef cc::ellen_bintree::internal_node< Key, leaf_node > internal_node;
116 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
121 struct traits_EllenBinTreeMap: public cc::ellen_bintree::make_set_traits<
123 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
124 ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
127 struct traits_EllenBinTreeMap_hp : traits_EllenBinTreeMap {
128 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
130 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_hp > EllenBinTreeMap_hp;
132 struct traits_EllenBinTreeMap_dhp : traits_EllenBinTreeMap {
133 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
135 typedef EllenBinTreeMap< cds::gc::DHP, Key, Value, traits_EllenBinTreeMap_dhp > EllenBinTreeMap_dhp;
137 struct traits_EllenBinTreeMap_gpi : traits_EllenBinTreeMap {
138 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
140 typedef EllenBinTreeMap< rcu_gpi, Key, Value, traits_EllenBinTreeMap_gpi > EllenBinTreeMap_rcu_gpi;
142 struct traits_EllenBinTreeMap_gpb : traits_EllenBinTreeMap {
143 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
145 typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_gpb > EllenBinTreeMap_rcu_gpb;
147 struct traits_EllenBinTreeMap_gpt : traits_EllenBinTreeMap {
148 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
150 typedef EllenBinTreeMap< rcu_gpt, Key, Value, traits_EllenBinTreeMap_gpt > EllenBinTreeMap_rcu_gpt;
152 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
153 struct traits_EllenBinTreeMap_shb : traits_EllenBinTreeMap {
154 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
156 typedef EllenBinTreeMap< rcu_shb, Key, Value, traits_EllenBinTreeMap_shb > EllenBinTreeMap_rcu_shb;
159 struct traits_EllenBinTreeMap_yield : public traits_EllenBinTreeMap
161 typedef cds::backoff::yield back_off;
163 struct traits_EllenBinTreeMap_hp_yield : traits_EllenBinTreeMap_yield {
164 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
166 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_hp_yield > EllenBinTreeMap_hp_yield;
168 struct traits_EllenBinTreeMap_dhp_yield : traits_EllenBinTreeMap_yield {
169 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
171 typedef EllenBinTreeMap< cds::gc::DHP, Key, Value, traits_EllenBinTreeMap_dhp_yield > EllenBinTreeMap_dhp_yield;
173 struct traits_EllenBinTreeMap_gpb_yield : traits_EllenBinTreeMap_yield {
174 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
176 typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_gpb_yield > EllenBinTreeMap_rcu_gpb_yield;
179 struct traits_EllenBinTreeMap_stat: public cc::ellen_bintree::make_set_traits<
181 ,cc::ellen_bintree::update_desc_allocator<
182 cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor >
184 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
185 ,co::stat< cc::ellen_bintree::stat<> >
186 ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
190 struct traits_EllenBinTreeMap_stat_hp : public traits_EllenBinTreeMap_stat
192 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
194 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_stat_hp > EllenBinTreeMap_hp_stat;
196 struct traits_EllenBinTreeMap_stat_dhp : public traits_EllenBinTreeMap_stat
198 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
200 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_stat_dhp > EllenBinTreeMap_dhp_stat;
202 struct traits_EllenBinTreeMap_stat_gpi : public traits_EllenBinTreeMap_stat
204 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
206 typedef EllenBinTreeMap< rcu_gpi, Key, Value, traits_EllenBinTreeMap_stat_gpi > EllenBinTreeMap_rcu_gpi_stat;
208 struct traits_EllenBinTreeMap_stat_gpb : public traits_EllenBinTreeMap_stat
210 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
212 typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_stat_gpb > EllenBinTreeMap_rcu_gpb_stat;
214 struct traits_EllenBinTreeMap_stat_gpt : public traits_EllenBinTreeMap_stat
216 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
218 typedef EllenBinTreeMap< rcu_gpt, Key, Value, traits_EllenBinTreeMap_stat_gpt > EllenBinTreeMap_rcu_gpt_stat;
220 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
221 struct traits_EllenBinTreeMap_stat_shb : public traits_EllenBinTreeMap_stat
223 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
225 typedef EllenBinTreeMap< rcu_shb, Key, Value, traits_EllenBinTreeMap_stat_shb > EllenBinTreeMap_rcu_shb_stat;
229 template <typename GC, typename Key, typename T, typename Traits>
230 static inline void print_stat( cds_test::property_stream& o, EllenBinTreeMap<GC, Key, T, Traits> const& s )
234 template <typename GC, typename Key, typename T, typename Traits>
235 static inline void additional_cleanup( EllenBinTreeMap<GC, Key, T, Traits>& /*s*/ )
237 ellen_bintree_pool::internal_node_counter::reset();
239 namespace ellen_bintree_check {
240 static inline void check_stat( cds::intrusive::ellen_bintree::empty_stat const& /*s*/ )
242 // This check is not valid for thread-based RCU
244 CPPUNIT_CHECK_CURRENT_EX( ellen_bintree_pool::internal_node_counter::m_nAlloc.get() == ellen_bintree_pool::internal_node_counter::m_nFree.get(),
245 "m_nAlloc=" << ellen_bintree_pool::internal_node_counter::m_nAlloc.get()
246 << ", m_nFree=" << ellen_bintree_pool::internal_node_counter::m_nFree.get()
251 static inline void check_stat( cds::intrusive::ellen_bintree::stat<> const& stat )
253 EXPECT_EQ( stat.m_nInternalNodeCreated, stat.m_nInternalNodeDeleted );
254 EXPECT_EQ( stat.m_nUpdateDescCreated, stat.m_nUpdateDescDeleted );
255 EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), stat.m_nInternalNodeCreated );
257 } // namespace ellen_bintree_check
258 template <typename GC, typename Key, typename T, typename Traits>
259 static inline void additional_check( EllenBinTreeMap<GC, Key, T, Traits>& m )
262 ellen_bintree_check::check_stat( m.statistics());
265 template <typename GC, typename Key, typename T, typename Traits>
266 static inline void check_before_cleanup( EllenBinTreeMap<GC, Key, T, Traits>& m )
268 EXPECT_TRUE( m.check_consistency());
273 #define CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, ellen_map_type, key_type, value_type ) \
274 TEST_F( fixture, ellen_map_type ) \
276 typedef map::map_type< tag_EllenBinTreeMap, key_type, value_type >::ellen_map_type map_type; \
277 test_case<map_type>(); \
280 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
281 # define CDSSTRESS_EllenBinTreeMap_SHRCU( fixture, test_case, key_type, value_type ) \
282 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_shb, key_type, value_type ) \
283 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_shb_stat, key_type, value_type ) \
286 # define CDSSTRESS_EllenBinTreeMap_SHRCU( fixture, test_case, key_type, value_type )
289 #if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL > 0
290 # define CDSSTRESS_EllenBinTreeMap_HP_1( fixture, test_case, key_type, value_type ) \
291 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_hp_yield, key_type, value_type ) \
292 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_dhp_yield, key_type, value_type ) \
295 # define CDSSTRESS_EllenBinTreeMap_RCU_1( fixture, test_case, key_type, value_type ) \
296 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpi, key_type, value_type ) \
297 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpb_yield, key_type, value_type ) \
298 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpi_stat, key_type, value_type ) \
299 CDSSTRESS_EllenBinTreeMap_SHRCU( fixture, test_case, key_type, value_type ) \
302 # define CDSSTRESS_EllenBinTreeMap_HP_1( fixture, test_case, key_type, value_type )
303 # define CDSSTRESS_EllenBinTreeMap_RCU_1( fixture, test_case, key_type, value_type )
306 #define CDSSTRESS_EllenBinTreeMap_HP( fixture, test_case, key_type, value_type ) \
307 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_hp, key_type, value_type ) \
308 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_dhp, key_type, value_type ) \
309 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_hp_stat, key_type, value_type ) \
310 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_dhp_stat, key_type, value_type ) \
311 CDSSTRESS_EllenBinTreeMap_HP_1( fixture, test_case, key_type, value_type ) \
313 #define CDSSTRESS_EllenBinTreeMap_RCU( fixture, test_case, key_type, value_type ) \
314 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpb, key_type, value_type ) \
315 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpt, key_type, value_type ) \
316 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpb_stat, key_type, value_type ) \
317 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpt_stat, key_type, value_type ) \
318 CDSSTRESS_EllenBinTreeMap_RCU_1( fixture, test_case, key_type, value_type ) \
320 #define CDSSTRESS_EllenBinTreeMap( fixture, test_case, key_type, value_type ) \
321 CDSSTRESS_EllenBinTreeMap_HP( fixture, test_case, key_type, value_type ) \
322 CDSSTRESS_EllenBinTreeMap_RCU( fixture, test_case, key_type, value_type ) \
324 #endif // ifndef CDSUNIT_MAP_TYPE_ELLEN_BINTREE_H