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;
119 typedef cc::ellen_bintree::map_node<rcu_sht, Key, Value> leaf_node;
120 typedef cc::ellen_bintree::internal_node< Key, leaf_node > internal_node;
121 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
126 struct traits_EllenBinTreeMap: public cc::ellen_bintree::make_set_traits<
128 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
129 ,co::item_counter< cds::atomicity::item_counter >
132 struct traits_EllenBinTreeMap_hp : traits_EllenBinTreeMap {
133 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
135 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_hp > EllenBinTreeMap_hp;
137 struct traits_EllenBinTreeMap_dhp : traits_EllenBinTreeMap {
138 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
140 typedef EllenBinTreeMap< cds::gc::DHP, Key, Value, traits_EllenBinTreeMap_dhp > EllenBinTreeMap_dhp;
142 struct traits_EllenBinTreeMap_gpi : traits_EllenBinTreeMap {
143 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
145 typedef EllenBinTreeMap< rcu_gpi, Key, Value, traits_EllenBinTreeMap_gpi > EllenBinTreeMap_rcu_gpi;
147 struct traits_EllenBinTreeMap_gpb : traits_EllenBinTreeMap {
148 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
150 typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_gpb > EllenBinTreeMap_rcu_gpb;
152 struct traits_EllenBinTreeMap_gpt : traits_EllenBinTreeMap {
153 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
155 typedef EllenBinTreeMap< rcu_gpt, Key, Value, traits_EllenBinTreeMap_gpt > EllenBinTreeMap_rcu_gpt;
157 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
158 struct traits_EllenBinTreeMap_shb : traits_EllenBinTreeMap {
159 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
161 typedef EllenBinTreeMap< rcu_shb, Key, Value, traits_EllenBinTreeMap_shb > EllenBinTreeMap_rcu_shb;
163 struct traits_EllenBinTreeMap_sht : traits_EllenBinTreeMap {
164 typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
166 typedef EllenBinTreeMap< rcu_sht, Key, Value, traits_EllenBinTreeMap_sht > EllenBinTreeMap_rcu_sht;
169 struct traits_EllenBinTreeMap_yield : public traits_EllenBinTreeMap
171 typedef cds::backoff::yield back_off;
173 struct traits_EllenBinTreeMap_hp_yield : traits_EllenBinTreeMap_yield {
174 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
176 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_hp_yield > EllenBinTreeMap_hp_yield;
178 struct traits_EllenBinTreeMap_dhp_yield : traits_EllenBinTreeMap_yield {
179 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
181 typedef EllenBinTreeMap< cds::gc::DHP, Key, Value, traits_EllenBinTreeMap_dhp_yield > EllenBinTreeMap_dhp_yield;
183 struct traits_EllenBinTreeMap_gpb_yield : traits_EllenBinTreeMap_yield {
184 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
186 typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_gpb_yield > EllenBinTreeMap_rcu_gpb_yield;
189 struct traits_EllenBinTreeMap_stat: public cc::ellen_bintree::make_set_traits<
191 ,cc::ellen_bintree::update_desc_allocator<
192 cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor >
194 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
195 ,co::stat< cc::ellen_bintree::stat<> >
196 ,co::item_counter< cds::atomicity::item_counter >
200 struct traits_EllenBinTreeMap_stat_hp : public traits_EllenBinTreeMap_stat
202 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
204 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_stat_hp > EllenBinTreeMap_hp_stat;
206 struct traits_EllenBinTreeMap_stat_dhp : public traits_EllenBinTreeMap_stat
208 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
210 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_stat_dhp > EllenBinTreeMap_dhp_stat;
212 struct traits_EllenBinTreeMap_stat_gpi : public traits_EllenBinTreeMap_stat
214 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
216 typedef EllenBinTreeMap< rcu_gpi, Key, Value, traits_EllenBinTreeMap_stat_gpi > EllenBinTreeMap_rcu_gpi_stat;
218 struct traits_EllenBinTreeMap_stat_gpb : public traits_EllenBinTreeMap_stat
220 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
222 typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_stat_gpb > EllenBinTreeMap_rcu_gpb_stat;
224 struct traits_EllenBinTreeMap_stat_gpt : public traits_EllenBinTreeMap_stat
226 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
228 typedef EllenBinTreeMap< rcu_gpt, Key, Value, traits_EllenBinTreeMap_stat_gpt > EllenBinTreeMap_rcu_gpt_stat;
230 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
231 struct traits_EllenBinTreeMap_stat_shb : public traits_EllenBinTreeMap_stat
233 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
235 typedef EllenBinTreeMap< rcu_shb, Key, Value, traits_EllenBinTreeMap_stat_shb > EllenBinTreeMap_rcu_shb_stat;
237 struct traits_EllenBinTreeMap_stat_sht : public traits_EllenBinTreeMap_stat
239 typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
241 typedef EllenBinTreeMap< rcu_sht, Key, Value, traits_EllenBinTreeMap_stat_sht > EllenBinTreeMap_rcu_sht_stat;
245 template <typename GC, typename Key, typename T, typename Traits>
246 static inline void print_stat( cds_test::property_stream& o, EllenBinTreeMap<GC, Key, T, Traits> const& s )
250 template <typename GC, typename Key, typename T, typename Traits>
251 static inline void additional_cleanup( EllenBinTreeMap<GC, Key, T, Traits>& /*s*/ )
253 ellen_bintree_pool::internal_node_counter::reset();
255 namespace ellen_bintree_check {
256 static inline void check_stat( cds::intrusive::ellen_bintree::empty_stat const& /*s*/ )
258 // This check is not valid for thread-based RCU
260 CPPUNIT_CHECK_CURRENT_EX( ellen_bintree_pool::internal_node_counter::m_nAlloc.get() == ellen_bintree_pool::internal_node_counter::m_nFree.get(),
261 "m_nAlloc=" << ellen_bintree_pool::internal_node_counter::m_nAlloc.get()
262 << ", m_nFree=" << ellen_bintree_pool::internal_node_counter::m_nFree.get()
267 static inline void check_stat( cds::intrusive::ellen_bintree::stat<> const& stat )
269 EXPECT_EQ( stat.m_nInternalNodeCreated, stat.m_nInternalNodeDeleted );
270 EXPECT_EQ( stat.m_nUpdateDescCreated, stat.m_nUpdateDescDeleted );
271 EXPECT_EQ( ellen_bintree_pool::internal_node_counter::m_nAlloc.get(), stat.m_nInternalNodeCreated );
273 } // namespace ellen_bintree_check
274 template <typename GC, typename Key, typename T, typename Traits>
275 static inline void additional_check( EllenBinTreeMap<GC, Key, T, Traits>& m )
278 ellen_bintree_check::check_stat( m.statistics());
281 template <typename GC, typename Key, typename T, typename Traits>
282 static inline void check_before_cleanup( EllenBinTreeMap<GC, Key, T, Traits>& m )
284 EXPECT_TRUE( m.check_consistency());
289 #define CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, ellen_map_type, key_type, value_type ) \
290 TEST_F( fixture, ellen_map_type ) \
292 typedef map::map_type< tag_EllenBinTreeMap, key_type, value_type >::ellen_map_type map_type; \
293 test_case<map_type>(); \
296 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
297 # if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL > 0
298 # define CDSSTRESS_EllenBinTreeMap_SHRCU_1( fixture, test_case, key_type, value_type ) \
299 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_sht, key_type, value_type ) \
300 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_sht_stat, key_type, value_type ) \
303 # define CDSSTRESS_EllenBinTreeMap_SHRCU_1( fixture, test_case, key_type, value_type )
306 # define CDSSTRESS_EllenBinTreeMap_SHRCU( fixture, test_case, key_type, value_type ) \
307 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_shb, key_type, value_type ) \
308 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_shb_stat, key_type, value_type ) \
309 CDSSTRESS_EllenBinTreeMap_SHRCU_1( fixture, test_case, key_type, value_type ) \
312 # define CDSSTRESS_EllenBinTreeMap_SHRCU( fixture, test_case, key_type, value_type )
315 #if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL > 0
316 # define CDSSTRESS_EllenBinTreeMap_HP_1( fixture, test_case, key_type, value_type ) \
317 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_hp_yield, key_type, value_type ) \
318 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_dhp_yield, key_type, value_type ) \
321 # define CDSSTRESS_EllenBinTreeMap_RCU_1( fixture, test_case, key_type, value_type ) \
322 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpi, key_type, value_type ) \
323 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpb_yield, key_type, value_type ) \
324 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpi_stat, key_type, value_type ) \
325 CDSSTRESS_EllenBinTreeMap_SHRCU( fixture, test_case, key_type, value_type ) \
328 # define CDSSTRESS_EllenBinTreeMap_HP_1( fixture, test_case, key_type, value_type )
329 # define CDSSTRESS_EllenBinTreeMap_RCU_1( fixture, test_case, key_type, value_type )
332 #define CDSSTRESS_EllenBinTreeMap_HP( fixture, test_case, key_type, value_type ) \
333 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_hp, key_type, value_type ) \
334 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_dhp, key_type, value_type ) \
335 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_hp_stat, key_type, value_type ) \
336 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_dhp_stat, key_type, value_type ) \
337 CDSSTRESS_EllenBinTreeMap_HP_1( fixture, test_case, key_type, value_type ) \
339 #define CDSSTRESS_EllenBinTreeMap_RCU( fixture, test_case, key_type, value_type ) \
340 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpb, key_type, value_type ) \
341 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpt, key_type, value_type ) \
342 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpb_stat, key_type, value_type ) \
343 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpt_stat, key_type, value_type ) \
344 CDSSTRESS_EllenBinTreeMap_RCU_1( fixture, test_case, key_type, value_type ) \
346 #define CDSSTRESS_EllenBinTreeMap( fixture, test_case, key_type, value_type ) \
347 CDSSTRESS_EllenBinTreeMap_HP( fixture, test_case, key_type, value_type ) \
348 CDSSTRESS_EllenBinTreeMap_RCU( fixture, test_case, key_type, value_type ) \
350 #endif // ifndef CDSUNIT_MAP_TYPE_ELLEN_BINTREE_H