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_SET_TYPE_ELLEN_BINTREE_H
32 #define CDSUNIT_SET_TYPE_ELLEN_BINTREE_H
34 #include "set2/set_type.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 "print_ellenbintree_stat.h"
44 template <class GC, typename Key, typename T, typename Traits = cc::ellen_bintree::traits >
45 class EllenBinTreeSet : public cc::EllenBinTreeSet< GC, Key, T, Traits >
47 typedef cc::EllenBinTreeSet< GC, Key, T, Traits > base_class;
49 template <typename Config>
50 EllenBinTreeSet( Config const& /*cfg*/ )
54 static CDS_CONSTEXPR bool const c_bExtractSupported = true;
55 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
56 static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
59 struct tag_EllenBinTreeSet;
61 template <typename Key, typename Val>
62 struct set_type< tag_EllenBinTreeSet, Key, Val >: public set_type_base< Key, Val >
64 typedef set_type_base< Key, Val > base_class;
65 typedef typename base_class::key_type key_type;
66 typedef typename base_class::key_val key_val;
67 typedef typename base_class::compare compare;
68 typedef typename base_class::less less;
69 typedef typename base_class::key_less key_less;
71 struct ellen_bintree_props {
72 struct key_extractor {
73 void operator()( key_type& dest, key_val const& src ) const
80 bool operator()( key_val const& v1, key_val const& v2 ) const
82 return key_less()( v1.key, v2.key );
84 bool operator()( key_type const& k, key_val const& v ) const
86 return key_less()( k, v.key );
88 bool operator()( key_val const& v, key_type const& k ) const
90 return key_less()( v.key, k );
92 bool operator()( key_type const& k1, key_type const& k2 ) const
94 return key_less()( k1, k2 );
99 typedef cc::ellen_bintree::node<cds::gc::HP, key_val> leaf_node;
100 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
101 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
105 typedef cc::ellen_bintree::node<cds::gc::DHP, key_val> leaf_node;
106 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
107 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
111 typedef cc::ellen_bintree::node<rcu_gpi, key_val> leaf_node;
112 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
113 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
116 typedef cc::ellen_bintree::node<rcu_gpb, key_val> leaf_node;
117 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
118 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
121 typedef cc::ellen_bintree::node<rcu_gpt, key_val> leaf_node;
122 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
123 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
125 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
127 typedef cc::ellen_bintree::node<rcu_shb, key_val> leaf_node;
128 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
129 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
132 typedef cc::ellen_bintree::node<rcu_sht, key_val> leaf_node;
133 typedef cc::ellen_bintree::internal_node< key_type, leaf_node > internal_node;
134 typedef cc::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
139 struct traits_EllenBinTreeSet: public cc::ellen_bintree::make_set_traits<
140 cc::ellen_bintree::key_extractor< typename ellen_bintree_props::key_extractor >
141 ,co::less< typename ellen_bintree_props::less >
142 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
146 struct traits_EllenBinTreeSet_hp : public traits_EllenBinTreeSet
148 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
150 typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_hp > EllenBinTreeSet_hp;
152 struct traits_EllenBinTreeSet_dhp : public traits_EllenBinTreeSet
154 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
156 typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_dhp > EllenBinTreeSet_dhp;
158 struct traits_EllenBinTreeSet_gpi : public traits_EllenBinTreeSet
160 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
162 typedef EllenBinTreeSet< rcu_gpi, key_type, key_val, traits_EllenBinTreeSet_gpi > EllenBinTreeSet_rcu_gpi;
164 struct traits_EllenBinTreeSet_gpb : public traits_EllenBinTreeSet
166 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
168 typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_gpb > EllenBinTreeSet_rcu_gpb;
170 struct traits_EllenBinTreeSet_gpt : public traits_EllenBinTreeSet
172 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
174 typedef EllenBinTreeSet< rcu_gpt, key_type, key_val, traits_EllenBinTreeSet_gpt > EllenBinTreeSet_rcu_gpt;
176 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
177 struct traits_EllenBinTreeSet_shb : public traits_EllenBinTreeSet
179 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
181 typedef EllenBinTreeSet< rcu_shb, key_type, key_val, traits_EllenBinTreeSet_shb > EllenBinTreeSet_rcu_shb;
183 struct traits_EllenBinTreeSet_sht : public traits_EllenBinTreeSet
185 typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
187 typedef EllenBinTreeSet< rcu_sht, key_type, key_val, traits_EllenBinTreeSet_sht > EllenBinTreeSet_rcu_sht;
191 struct traits_EllenBinTreeSet_yield : public traits_EllenBinTreeSet
193 typedef cds::backoff::yield back_off;
196 struct traits_EllenBinTreeSet_yield_hp : public traits_EllenBinTreeSet_yield
198 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
200 typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_yield_hp > EllenBinTreeSet_yield_hp;
202 struct traits_EllenBinTreeSet_yield_dhp : public traits_EllenBinTreeSet_yield
204 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
206 typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_yield_dhp > EllenBinTreeSet_yield_dhp;
209 struct traits_EllenBinTreeSet_yield_gpb : public traits_EllenBinTreeSet_yield
211 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
213 typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_yield_gpb > EllenBinTreeSet_yield_rcu_gpb;
216 struct traits_EllenBinTreeSet_stat: public cc::ellen_bintree::make_set_traits<
217 cc::ellen_bintree::key_extractor< typename ellen_bintree_props::key_extractor >
218 ,co::less< typename ellen_bintree_props::less >
219 ,co::node_allocator< ellen_bintree_pool::internal_node_allocator< int > >
220 ,co::stat< cc::ellen_bintree::stat<> >
224 struct traits_EllenBinTreeSet_stat_hp : public traits_EllenBinTreeSet_stat
226 typedef cds::memory::pool_allocator< typename ellen_bintree_props::hp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
228 typedef EllenBinTreeSet< cds::gc::HP, key_type, key_val, traits_EllenBinTreeSet_stat_hp > EllenBinTreeSet_hp_stat;
230 struct traits_EllenBinTreeSet_stat_dhp : public traits_EllenBinTreeSet_stat
232 typedef cds::memory::pool_allocator< typename ellen_bintree_props::dhp_gc::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
234 typedef EllenBinTreeSet< cds::gc::DHP, key_type, key_val, traits_EllenBinTreeSet_stat_dhp > EllenBinTreeSet_dhp_stat;
236 struct traits_EllenBinTreeSet_stat_gpi : public traits_EllenBinTreeSet_stat
238 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpi::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
240 typedef EllenBinTreeSet< rcu_gpi, key_type, key_val, traits_EllenBinTreeSet_stat_gpi > EllenBinTreeSet_rcu_gpi_stat;
242 struct traits_EllenBinTreeSet_stat_gpb : public traits_EllenBinTreeSet_stat
244 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
246 typedef EllenBinTreeSet< rcu_gpb, key_type, key_val, traits_EllenBinTreeSet_stat_gpb > EllenBinTreeSet_rcu_gpb_stat;
248 struct traits_EllenBinTreeSet_stat_gpt : public traits_EllenBinTreeSet_stat
250 typedef cds::memory::pool_allocator< typename ellen_bintree_props::gpt::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
252 typedef EllenBinTreeSet< rcu_gpt, key_type, key_val, traits_EllenBinTreeSet_stat_gpt > EllenBinTreeSet_rcu_gpt_stat;
254 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
255 struct traits_EllenBinTreeSet_stat_shb : public traits_EllenBinTreeSet_stat
257 typedef cds::memory::pool_allocator< typename ellen_bintree_props::shb::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
259 typedef EllenBinTreeSet< rcu_shb, key_type, key_val, traits_EllenBinTreeSet_stat_shb > EllenBinTreeSet_rcu_shb_stat;
261 struct traits_EllenBinTreeSet_stat_sht : public traits_EllenBinTreeSet_stat
263 typedef cds::memory::pool_allocator< typename ellen_bintree_props::sht::update_desc, ellen_bintree_pool::update_desc_pool_accessor > update_desc_allocator;
265 typedef EllenBinTreeSet< rcu_sht, key_type, key_val, traits_EllenBinTreeSet_stat_sht > EllenBinTreeSet_rcu_sht_stat;
270 template <typename GC, typename Key, typename T, typename Traits>
271 static inline void print_stat( EllenBinTreeSet<GC, Key, T, Traits> const& s )
273 CPPUNIT_MSG( s.statistics() );
276 namespace ellen_bintree_check {
277 static inline void check_stat( cds::intrusive::ellen_bintree::empty_stat const& /*s*/ )
279 // Not true for threaded RCU
281 CPPUNIT_CHECK_CURRENT_EX( ellen_bintree_pool::internal_node_counter::m_nAlloc.get() == ellen_bintree_pool::internal_node_counter::m_nFree.get(),
282 "m_nAlloc=" << ellen_bintree_pool::internal_node_counter::m_nAlloc.get()
283 << ", m_nFree=" << ellen_bintree_pool::internal_node_counter::m_nFree.get()
288 static inline void check_stat( cds::intrusive::ellen_bintree::stat<> const& stat )
290 CPPUNIT_CHECK_CURRENT( stat.m_nInternalNodeCreated == stat.m_nInternalNodeDeleted );
291 CPPUNIT_CHECK_CURRENT( stat.m_nUpdateDescCreated == stat.m_nUpdateDescDeleted );
292 //CPPUNIT_CHECK_CURRENT( ellen_bintree_pool::internal_node_counter::m_nAlloc.get() == ellen_bintree_pool::internal_node_counter::m_nFree.get() );
293 CPPUNIT_CHECK_CURRENT( ellen_bintree_pool::internal_node_counter::m_nAlloc.get() == stat.m_nInternalNodeCreated );
294 // true if RCU is not threaded
295 //CPPUNIT_CHECK_CURRENT( stat.m_nInternalNodeDeleted == ellen_bintree_pool::internal_node_counter::m_nFree.get() );
297 } // namespace ellen_bintree_check
299 template <typename GC, typename Key, typename T, typename Traits>
300 static inline void additional_check( EllenBinTreeSet<GC, Key, T, Traits>& s )
303 ellen_bintree_check::check_stat( s.statistics() );
306 template <typename GC, typename Key, typename T, typename Traits>
307 static inline void additional_cleanup( EllenBinTreeSet<GC, Key, T, Traits>& /*s*/ )
309 ellen_bintree_pool::internal_node_counter::reset();
312 template <typename GC, typename Key, typename T, typename Traits>
313 static inline void check_before_clear( cds::container::EllenBinTreeSet<GC, Key, T, Traits>& s )
315 CPPUNIT_CHECK_CURRENT( s.check_consistency() );
321 #endif // #ifndef CDSUNIT_SET_TYPE_ELLEN_BINTREE_H