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 CDSLIB_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H
32 #define CDSLIB_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H
34 #include <cds/intrusive/details/ellen_bintree_base.h>
35 #include <cds/container/details/base.h>
36 #include <cds/opt/compare.h>
37 #include <cds/details/binary_functor_wrapper.h>
40 namespace cds { namespace container {
41 /// EllenBinTree related definitions
42 /** @ingroup cds_nonintrusive_helper
44 namespace ellen_bintree {
45 #ifdef CDS_DOXYGEN_INVOKED
46 /// Typedef for \p cds::intrusive::ellen_bintree::update_desc
47 typedef cds::intrusive::ellen_bintree::update_desc update_desc;
49 /// Typedef for \p cds::intrusive::ellen_bintree::internal_node
50 typedef cds::intrusive::ellen_bintree::internal_node internal_node;
52 /// Typedef for \p cds::intrusive::ellen_bintree::key_extractor
53 typedef cds::intrusive::ellen_bintree::key_extractor key_extractor;
55 /// Typedef for \p cds::intrusive::ellen_bintree::update_desc_allocator
56 typedef cds::intrusive::ellen_bintree::update_desc_allocator update_desc_allocator;
58 using cds::intrusive::ellen_bintree::update_desc;
59 using cds::intrusive::ellen_bintree::internal_node;
60 using cds::intrusive::ellen_bintree::key_extractor;
61 using cds::intrusive::ellen_bintree::update_desc_allocator;
62 using cds::intrusive::ellen_bintree::node_types;
64 /// EllenBinTree internal statistics
65 template <typename Counter = cds::intrusive::ellen_bintree::stat<>::event_counter >
66 using stat = cds::intrusive::ellen_bintree::stat< Counter >;
68 /// EllenBinTree empty internal statistics
69 typedef cds::intrusive::ellen_bintree::empty_stat empty_stat;
71 /// EllenBinTree leaf node
72 template <typename GC, typename T>
73 struct node: public cds::intrusive::ellen_bintree::node<GC>
75 typedef T value_type ; ///< Value type
77 T m_Value ; ///< Value
90 template <typename... Args>
91 node( Args const&... args )
96 template <typename... Args>
97 node( Args&&... args )
98 : m_Value( std::forward<Args>( args )... )
102 /// EllenBinTreeMap leaf node
103 template <typename GC, typename Key, typename T>
104 struct map_node: public cds::intrusive::ellen_bintree::node< GC >
106 typedef Key key_type ; ///< key type
107 typedef T mapped_type ; ///< value type
108 typedef std::pair<key_type const, mapped_type> value_type ; ///< key-value pair stored in the map
110 value_type m_Value ; ///< Key-value pair stored in map leaf node
112 /// Initializes key field, value if default-constructed
113 template <typename K>
114 map_node( K const& key )
115 : m_Value( std::make_pair( key_type(key), mapped_type()))
118 /// Initializes key and value fields
119 template <typename K, typename Q>
120 map_node( K const& key, Q const& v )
121 : m_Value( std::make_pair(key_type(key), mapped_type(v)))
125 /// Type traits for \p EllenBinTreeSet and \p EllenBinTreeMap
128 /// Key extracting functor (only for \p EllenBinTreeSet)
130 This is mandatory functor for \p %EllenBinTreeSet.
131 It has the following prototype:
133 struct key_extractor {
134 void operator ()( Key& dest, T const& src );
137 It should initialize \p dest key from \p src data.
138 The functor is used to initialize internal nodes of \p %EllenBinTreeSet
140 typedef opt::none key_extractor;
142 /// Key comparison functor
144 No default functor is provided. If the option is not specified, the \p less is used.
146 See \p cds::opt::compare option description for functor interface.
148 You should provide \p compare or \p less functor.
149 See \ref cds_container_EllenBinTreeSet_rcu_less "predicate requirements".
151 typedef opt::none compare;
153 /// Specifies binary predicate used for key compare.
155 See \p cds::opt::less option description.
157 You should provide \p compare or \p less functor.
158 See \ref cds_container_EllenBinTreeSet_rcu_less "predicate requirements".
160 typedef opt::none less;
164 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
165 To enable it use \p atomicity::item_counter
167 typedef atomicity::empty_item_counter item_counter;
169 /// C++ memory ordering model
171 List of available memory ordering see \p opt::memory_model
173 typedef opt::v::relaxed_ordering memory_model;
175 /// Allocator for update descriptors
177 The allocator type is used for \p ellen_bintree::update_desc.
179 Update descriptor is helping data structure with short lifetime and it is good candidate
180 for pooling. The number of simultaneously existing descriptors is a small number
181 limited the number of threads working with the tree.
182 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue
183 is good choice for the free-list of update descriptors,
184 see \p cds::memory::vyukov_queue_pool free-list implementation.
186 Also notice that size of update descriptor is not dependent on the type of data
187 stored in the tree so single free-list object can be used for several \p EllenBinTree object.
189 typedef CDS_DEFAULT_ALLOCATOR update_desc_allocator;
191 /// Allocator for internal nodes
193 The allocator type is used for \p ellen_bintree::internal_node.
195 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
197 /// Allocator for leaf nodes
199 Each leaf node contains data stored in the container.
201 typedef CDS_DEFAULT_ALLOCATOR allocator;
203 /// Internal statistics
205 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
206 To enable it use \p ellen_bintree::stat.
208 typedef empty_stat stat;
210 /// Back-off strategy
211 typedef cds::backoff::empty back_off;
213 /// RCU deadlock checking policy (only for RCU-based EllenBinTree<i>XXX</i> classes)
215 List of available options see \p opt::rcu_check_deadlock
217 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
219 /// Key copy policy (for \p EllenBinTreeMap)
221 The key copy policy defines a functor to copy leaf node's key to internal node.
222 This policy is used only in \p EllenBinTreeMap.
223 By default, assignment operator is used.
225 The copy functor interface is:
227 struct copy_functor {
228 void operator()( Key& dest, Key const& src );
232 typedef opt::none copy_policy;
236 /// Metafunction converting option list to \p EllenBinTreeSet traits
239 - \p ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
241 struct key_extractor {
242 void operator ()( Key& dest, T const& src );
245 It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
246 - \p opt::compare - key compare functor. No default functor is provided.
247 If the option is not specified, \p %opt::less is used.
248 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
249 - \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
250 To enable it use \p atomicity::item_counter
251 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
252 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
253 - \p opt::allocator - the allocator for \ref ellen_bintree::node "leaf nodes" which contains data.
254 Default is \ref CDS_DEFAULT_ALLOCATOR.
255 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
256 - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
257 default is \ref CDS_DEFAULT_ALLOCATOR.
258 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
259 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
260 working with the tree and RCU buffer size.
261 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
262 of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation.
263 Also notice that size of update descriptor is not dependent on the type of data
264 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
265 - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable
266 it use \p ellen_bintree::stat.
267 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
268 - \p opt::rcu_check_deadlock - a deadlock checking policy, only for RCU-based tree.
269 Default is \p opt::v::rcu_throw_deadlock.
271 template <typename... Options>
272 struct make_set_traits {
273 # ifdef CDS_DOXYGEN_INVOKED
274 typedef implementation_defined type ; ///< Metafunction result
276 typedef typename cds::opt::make_options<
277 typename cds::opt::find_type_traits< traits, Options... >::type
283 /// Metafunction converting option list to \p EllenBinTreeMap traits
286 - \p opt::compare - key compare functor. No default functor is provided.
287 If the option is not specified, \p %opt::less is used.
288 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
289 - \p opt::item_counter - the type of item counter, default is disabled (\p atomicity::empty_item_counter).
290 To enable it use \p atomicity::item_counter
291 - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
292 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
293 - \p opt::allocator - the allocator used for \ref ellen_bintree::map_node "leaf nodes" which contains data.
294 Default is \ref CDS_DEFAULT_ALLOCATOR.
295 - \p opt::node_allocator - the allocator used for \ref ellen_bintree::internal_node "internal nodes".
296 Default is \ref CDS_DEFAULT_ALLOCATOR.
297 - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
298 default is \ref CDS_DEFAULT_ALLOCATOR.
299 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
300 The number of simultaneously existing descriptors is a relatively small number limited the number of threads
301 working with the tree and RCU buffer size.
302 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
303 of update descriptors, see \p cds::memory::vyukov_queue_pool free-list implementation.
304 Also notice that size of update descriptor is not dependent on the type of data
305 stored in the tree so single free-list object can be used for several EllenBinTree-based object.
306 - \p opt::stat - internal statistics, by default disabled (\p ellen_bintree::empty_stat). To enable
307 it use \p ellen_bintree::stat.
308 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
309 - \p opt::rcu_check_deadlock - a deadlock checking policy, only for RCU-based tree. Default is \p opt::v::rcu_throw_deadlock
310 - opt::copy_policy - key copying policy defines a functor to copy leaf node's key to internal node.
311 By default, assignment operator is used.
312 The copy functor interface is:
314 struct copy_functor {
315 void operator()( Key& dest, Key const& src );
319 template <typename... Options>
320 struct make_map_traits {
321 # ifdef CDS_DOXYGEN_INVOKED
322 typedef implementation_defined type ; ///< Metafunction result
324 typedef typename cds::opt::make_options<
325 typename cds::opt::find_type_traits< traits, Options... >::type
334 template < class GC, typename Key, typename T, class Traits>
335 struct make_ellen_bintree_set
338 typedef Key key_type;
339 typedef T value_type;
340 typedef Traits original_traits;
342 typedef node< gc, value_type > leaf_node;
344 struct intrusive_key_extractor
346 void operator()( key_type& dest, leaf_node const& src ) const
348 typename original_traits::key_extractor()( dest, src.m_Value );
352 struct value_accessor
354 value_type const& operator()( leaf_node const& node ) const
360 typedef typename cds::opt::details::make_comparator< value_type, original_traits, false >::type key_comparator;
362 typedef cds::details::Allocator< leaf_node, typename original_traits::allocator> cxx_leaf_node_allocator;
363 struct leaf_deallocator
365 void operator()( leaf_node * p ) const
367 cxx_leaf_node_allocator().Delete( p );
371 struct intrusive_traits: public original_traits
373 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc >> hook;
374 typedef intrusive_key_extractor key_extractor;
375 typedef leaf_deallocator disposer;
376 typedef cds::details::compare_wrapper< leaf_node, key_comparator, value_accessor > compare;
379 // Metafunction result
380 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits > type;
383 template < class GC, typename Key, typename T, class Traits>
384 struct make_ellen_bintree_map
387 typedef Key key_type;
388 typedef T mapped_type;
389 typedef map_node< gc, key_type, mapped_type > leaf_node;
390 typedef typename leaf_node::value_type value_type;
392 typedef Traits original_traits;
394 struct assignment_copy_policy {
395 void operator()( key_type& dest, key_type const& src )
400 typedef typename std::conditional<
401 std::is_same< typename original_traits::copy_policy, opt::none >::value,
402 assignment_copy_policy,
403 typename original_traits::copy_policy
406 struct intrusive_key_extractor
408 void operator()( key_type& dest, leaf_node const& src ) const
410 copy_policy()( dest, src.m_Value.first );
416 key_type const& operator()( leaf_node const& node ) const
418 return node.m_Value.first;
422 typedef typename cds::opt::details::make_comparator< key_type, original_traits, false >::type key_comparator;
424 typedef cds::details::Allocator< leaf_node, typename original_traits::allocator> cxx_leaf_node_allocator;
425 struct leaf_deallocator
427 void operator()( leaf_node * p ) const
429 cxx_leaf_node_allocator().Delete( p );
433 struct intrusive_traits: public original_traits
435 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc< gc > > hook;
436 typedef intrusive_key_extractor key_extractor;
437 typedef leaf_deallocator disposer;
438 typedef cds::details::compare_wrapper< leaf_node, key_comparator, key_accessor > compare;
441 // Metafunction result
442 typedef cds::intrusive::EllenBinTree< gc, key_type, leaf_node, intrusive_traits > type;
445 } // namespace details
447 } // namespace ellen_bintree
449 // Forward declarations
451 template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
452 class EllenBinTreeSet;
454 template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
455 class EllenBinTreeMap;
458 }} // namespace cds::container
460 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_ELLEN_BINTREE_BASE_H