2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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*/)
56 static CDS_CONSTEXPR bool const c_bExtractSupported = true;
57 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
58 static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
61 struct tag_EllenBinTreeMap;
63 template <typename Key, typename Value>
64 struct map_type< tag_EllenBinTreeMap, Key, Value >: public map_type_base< Key, Value >
66 typedef map_type_base< Key, Value > base_class;
67 typedef typename base_class::key_compare compare;
68 typedef typename base_class::key_less less;
70 struct ellen_bintree_props {
72 typedef cc::ellen_bintree::map_node<cds::gc::HP, Key, Value> leaf_node;
73 typedef cc::ellen_bintree::internal_node< Key, leaf_node > internal_node;
74 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
77 typedef cc::ellen_bintree::map_node<cds::gc::DHP, Key, Value> leaf_node;
78 typedef cc::ellen_bintree::internal_node< Key, leaf_node > internal_node;
79 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
82 typedef cc::ellen_bintree::map_node<rcu_gpi, Key, Value> leaf_node;
83 typedef cc::ellen_bintree::internal_node< Key, leaf_node > internal_node;
84 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
87 typedef cc::ellen_bintree::map_node<rcu_gpb, Key, Value> leaf_node;
88 typedef cc::ellen_bintree::internal_node< Key, leaf_node > internal_node;
89 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
92 typedef cc::ellen_bintree::map_node<rcu_gpt, Key, Value> leaf_node;
93 typedef cc::ellen_bintree::internal_node< Key, leaf_node > internal_node;
94 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
96 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
98 typedef cc::ellen_bintree::map_node<rcu_shb, 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_sht, 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;
110 struct traits_EllenBinTreeMap: public cc::ellen_bintree::make_set_traits<
112 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
113 ,co::item_counter< cds::atomicity::item_counter >
116 struct traits_EllenBinTreeMap_hp : traits_EllenBinTreeMap {
117 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
119 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_hp > EllenBinTreeMap_hp;
121 struct traits_EllenBinTreeMap_dhp : traits_EllenBinTreeMap {
122 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
124 typedef EllenBinTreeMap< cds::gc::DHP, Key, Value, traits_EllenBinTreeMap_dhp > EllenBinTreeMap_dhp;
126 struct traits_EllenBinTreeMap_gpi : traits_EllenBinTreeMap {
127 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
129 typedef EllenBinTreeMap< rcu_gpi, Key, Value, traits_EllenBinTreeMap_gpi > EllenBinTreeMap_rcu_gpi;
131 struct traits_EllenBinTreeMap_gpb : traits_EllenBinTreeMap {
132 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
134 typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_gpb > EllenBinTreeMap_rcu_gpb;
136 struct traits_EllenBinTreeMap_gpt : traits_EllenBinTreeMap {
137 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
139 typedef EllenBinTreeMap< rcu_gpt, Key, Value, traits_EllenBinTreeMap_gpt > EllenBinTreeMap_rcu_gpt;
141 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
142 struct traits_EllenBinTreeMap_shb : traits_EllenBinTreeMap {
143 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
145 typedef EllenBinTreeMap< rcu_shb, Key, Value, traits_EllenBinTreeMap_shb > EllenBinTreeMap_rcu_shb;
147 struct traits_EllenBinTreeMap_sht : traits_EllenBinTreeMap {
148 typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
150 typedef EllenBinTreeMap< rcu_sht, Key, Value, traits_EllenBinTreeMap_sht > EllenBinTreeMap_rcu_sht;
153 struct traits_EllenBinTreeMap_yield : public traits_EllenBinTreeMap
155 typedef cds::backoff::yield back_off;
157 struct traits_EllenBinTreeMap_hp_yield : traits_EllenBinTreeMap_yield {
158 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
160 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_hp_yield > EllenBinTreeMap_hp_yield;
162 struct traits_EllenBinTreeMap_dhp_yield : traits_EllenBinTreeMap_yield {
163 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
165 typedef EllenBinTreeMap< cds::gc::DHP, Key, Value, traits_EllenBinTreeMap_dhp_yield > EllenBinTreeMap_dhp_yield;
167 struct traits_EllenBinTreeMap_gpb_yield : traits_EllenBinTreeMap_yield {
168 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
170 typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_gpb_yield > EllenBinTreeMap_rcu_gpb_yield;
173 struct traits_EllenBinTreeMap_stat: public cc::ellen_bintree::make_set_traits<
175 ,cc::ellen_bintree::update_desc_allocator<
176 cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor >
178 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
179 ,co::stat< cc::ellen_bintree::stat<> >
180 ,co::item_counter< cds::atomicity::item_counter >
184 struct traits_EllenBinTreeMap_stat_hp : public traits_EllenBinTreeMap_stat
186 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
188 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_stat_hp > EllenBinTreeMap_hp_stat;
190 struct traits_EllenBinTreeMap_stat_dhp : public traits_EllenBinTreeMap_stat
192 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
194 typedef EllenBinTreeMap< cds::gc::HP, Key, Value, traits_EllenBinTreeMap_stat_dhp > EllenBinTreeMap_dhp_stat;
196 struct traits_EllenBinTreeMap_stat_gpi : public traits_EllenBinTreeMap_stat
198 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
200 typedef EllenBinTreeMap< rcu_gpi, Key, Value, traits_EllenBinTreeMap_stat_gpi > EllenBinTreeMap_rcu_gpi_stat;
202 struct traits_EllenBinTreeMap_stat_gpb : public traits_EllenBinTreeMap_stat
204 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
206 typedef EllenBinTreeMap< rcu_gpb, Key, Value, traits_EllenBinTreeMap_stat_gpb > EllenBinTreeMap_rcu_gpb_stat;
208 struct traits_EllenBinTreeMap_stat_gpt : public traits_EllenBinTreeMap_stat
210 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
212 typedef EllenBinTreeMap< rcu_gpt, Key, Value, traits_EllenBinTreeMap_stat_gpt > EllenBinTreeMap_rcu_gpt_stat;
214 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
215 struct traits_EllenBinTreeMap_stat_shb : public traits_EllenBinTreeMap_stat
217 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
219 typedef EllenBinTreeMap< rcu_shb, Key, Value, traits_EllenBinTreeMap_stat_shb > EllenBinTreeMap_rcu_shb_stat;
221 struct traits_EllenBinTreeMap_stat_sht : public traits_EllenBinTreeMap_stat
223 typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
225 typedef EllenBinTreeMap< rcu_sht, Key, Value, traits_EllenBinTreeMap_stat_sht > EllenBinTreeMap_rcu_sht_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, level ) \
274 TEST_F( fixture, ellen_map_type ) \
276 if ( !check_detail_level( level )) return; \
277 typedef map::map_type< tag_EllenBinTreeMap, key_type, value_type >::ellen_map_type map_type; \
278 test_case<map_type>(); \
281 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
282 # define CDSSTRESS_EllenBinTreeMap_SHRCU( fixture, test_case, key_type, value_type ) \
283 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_shb, key_type, value_type, 0 ) \
284 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_sht, key_type, value_type, 0 ) \
285 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_shb_stat, key_type, value_type, 0 ) \
286 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_sht_stat, key_type, value_type, 0 )
288 # define CDSSTRESS_EllenBinTreeMap_SHRCU( fixture, test_case, key_type, value_type )
291 #define CDSSTRESS_EllenBinTreeMap( fixture, test_case, key_type, value_type ) \
292 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_hp, key_type, value_type, 0 ) \
293 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_dhp, key_type, value_type, 0 ) \
294 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpi, key_type, value_type, 1 ) \
295 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpb, key_type, value_type, 0 ) \
296 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpt, key_type, value_type, 0 ) \
297 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_hp_yield, key_type, value_type, 1 ) \
298 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_dhp_yield, key_type, value_type, 1 ) \
299 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpb_yield, key_type, value_type, 1 ) \
300 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_hp_stat, key_type, value_type, 0 ) \
301 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_dhp_stat, key_type, value_type, 0 ) \
302 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpi_stat, key_type, value_type, 1 ) \
303 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpb_stat, key_type, value_type, 0 ) \
304 CDSSTRESS_EllenBinTreeMap_case( fixture, test_case, EllenBinTreeMap_rcu_gpt_stat, key_type, value_type, 0 ) \
305 CDSSTRESS_EllenBinTreeMap_SHRCU( fixture, test_case, key_type, value_type )
307 #endif // ifndef CDSUNIT_MAP_TYPE_ELLEN_BINTREE_H