3 #ifndef CDSLIB_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H
4 #define CDSLIB_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H
7 #include <cds/intrusive/details/base.h>
8 #include <cds/opt/options.h>
9 #include <cds/urcu/options.h>
10 #include <cds/details/marked_ptr.h>
12 namespace cds { namespace intrusive {
14 /// EllenBinTree related declarations
15 namespace ellen_bintree {
16 struct implementation_tag;
19 template <class GC> struct base_node;
20 template <class GC, typename Tag = opt::none> struct node;
21 template <class GC, typename Key> struct internal_node;
25 Update descriptor is used internally for helping concurrent threads
26 to complete modifying operation.
27 Usually, you should not use \p update_desc type directly until
28 you want to develop special free-list of update descriptor.
31 - \p LeafNode - leaf node type, see \ref node
32 - \p InternalNode - internal node type, see \ref internal_node
34 @note Size of update descriptor is constant.
35 It does not depends of template arguments.
37 template <typename LeafNode, typename InternalNode>
40 typedef LeafNode leaf_node;
41 typedef InternalNode internal_node;
43 typedef cds::details::marked_ptr< update_desc, 3 > update_ptr;
53 internal_node * pParent;
59 internal_node * pGrandParent;
60 internal_node * pParent;
62 update_desc * pUpdateParent;
63 bool bDisposeLeaf; // true if pLeaf should be disposed, false otherwise (for extract operation, RCU)
73 update_desc * pNextRetire ; // for local retired list (RCU)
76 : pNextRetire( nullptr )
85 internal = 1, ///< set for internal node
86 key_infinite1 = 2, ///< set if node's key is Inf1
87 key_infinite2 = 4, ///< set if node's key is Inf2
89 key_infinite = key_infinite1 | key_infinite2 ///< Cumulative infinite flags
92 atomics::atomic<unsigned int> m_nFlags ; ///< Internal flags
94 /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
95 explicit basic_node( bool bInternal )
96 : m_nFlags( bInternal ? internal : 0 )
99 /// Checks if the node is a leaf
102 return !is_internal();
105 /// Checks if the node is internal
106 bool is_internal() const
108 return (m_nFlags.load( atomics::memory_order_relaxed ) & internal) != 0;
111 /// Returns infinite key, 0 if the node is not infinite
112 unsigned int infinite_key() const
114 return m_nFlags.load( atomics::memory_order_relaxed ) & key_infinite;
117 /// Sets infinite key for the node (for internal use only!!!)
118 void infinite_key( int nInf )
120 const unsigned int nFlags = m_nFlags.load( atomics::memory_order_relaxed ) & ~key_infinite;
121 m_nFlags.store( nFlags, atomics::memory_order_relaxed );
124 m_nFlags.store( nFlags | key_infinite1, atomics::memory_order_relaxed );
127 m_nFlags.store( nFlags | key_infinite2, atomics::memory_order_relaxed );
139 struct base_node: public basic_node
141 typedef basic_node base_class;
143 typedef GC gc ; ///< Garbage collector
144 /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
145 explicit base_node( bool bInternal )
146 : base_class( bInternal )
151 /// Ellen's binary tree leaf node
154 - \p GC - one of \ref cds_garbage_collector "garbage collector type"
155 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
157 template <typename GC,
158 # ifdef CDS_DOXYGEN_INVOKED
159 typename Tag = opt::none
165 # ifndef CDS_DOXYGEN_INVOKED
166 : public base_node< GC >
170 typedef base_node< GC > base_class;
173 typedef GC gc; ///< Garbage collector
174 typedef Tag tag; ///< Tag
178 : base_class( false )
182 /// Ellen's binary tree internal node
186 - \p LeafNode - leaf node type
188 template <typename Key, typename LeafNode>
190 # ifndef CDS_DOXYGEN_INVOKED
191 : public base_node<typename LeafNode::gc>
195 typedef base_node<typename LeafNode::gc> base_class;
198 typedef Key key_type; ///< key type
199 typedef LeafNode leaf_node; ///< type of leaf node
200 typedef update_desc< leaf_node, internal_node > update_desc_type; ///< Update descriptor
201 typedef typename update_desc_type::update_ptr update_ptr; ///< Marked pointer to update descriptor
203 key_type m_Key; ///< Regular key
204 atomics::atomic<base_class *> m_pLeft; ///< Left subtree
205 atomics::atomic<base_class *> m_pRight; ///< Right subtree
206 atomics::atomic<update_ptr> m_pUpdate; ///< Update descriptor
208 uintptr_t m_nEmptyUpdate; ///< ABA prevention for m_pUpdate, from 0..2^16 step 4
215 , m_pRight( nullptr )
216 , m_pUpdate( update_ptr() )
221 update_ptr null_update_desc()
223 return update_ptr( reinterpret_cast<update_desc_type *>( (++m_nEmptyUpdate << 2) & 0xFFFF ) );
228 /// Types of EllenBinTree node
230 This struct declares different \p %EllenBinTree node types.
231 It can be useful for simplifying \p %EllenBinTree node declaration in your application.
234 - \p GC - one of \ref cds_garbage_collector "garbage collector type"
236 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
238 template <typename GC, typename Key, typename Tag = opt::none>
241 typedef node<GC, Tag> leaf_node_type; ///< Leaf node type
242 typedef internal_node<Key, leaf_node_type> internal_node_type; ///< Internal node type
243 typedef update_desc<leaf_node_type, internal_node_type> update_desc_type; ///< Update descriptor type
248 struct default_hook {
249 typedef undefined_gc gc;
250 typedef opt::none tag;
255 template < typename HookType, typename... Options>
258 typedef typename opt::make_options< default_hook, Options...>::type options;
259 typedef typename options::gc gc;
260 typedef typename options::tag tag;
261 typedef node<gc, tag> node_type;
262 typedef HookType hook_type;
269 - \p opt::gc - garbage collector
270 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
272 template < typename... Options >
273 struct base_hook: public hook< opt::base_hook_tag, Options... >
278 \p MemberOffset defines offset in bytes of \ref node member into your structure.
279 Use \p offsetof macro to define \p MemberOffset
282 - \p opt::gc - garbage collector
283 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
285 template < size_t MemberOffset, typename... Options >
286 struct member_hook: public hook< opt::member_hook_tag, Options... >
289 static CDS_CONSTEXPR const size_t c_nMemberOffset = MemberOffset;
295 \p NodeTraits defines type traits for node.
296 See \ref node_traits for \p NodeTraits interface description
299 - opt::gc - garbage collector
300 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
302 template <typename NodeTraits, typename... Options >
303 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
306 typedef NodeTraits node_traits;
310 /// Key extracting functor option setter
311 template <typename Type>
312 struct key_extractor {
314 template <typename Base> struct pack: public Base
316 typedef Type key_extractor;
321 /// Update descriptor allocator option setter
322 template <typename Type>
323 struct update_desc_allocator {
325 template <typename Base> struct pack: public Base
327 typedef Type update_desc_allocator;
332 /// EllenBinTree internal statistics
333 template <typename Counter = cds::atomicity::event_counter>
335 typedef Counter event_counter ; ///< Event counter type
337 event_counter m_nInternalNodeCreated ; ///< Total count of created internal node
338 event_counter m_nInternalNodeDeleted ; ///< Total count of deleted internal node
339 event_counter m_nUpdateDescCreated ; ///< Total count of created update descriptors
340 event_counter m_nUpdateDescDeleted ; ///< Total count of deleted update descriptors
342 event_counter m_nInsertSuccess ; ///< Count of success insertion
343 event_counter m_nInsertFailed ; ///< Count of failed insertion
344 event_counter m_nInsertRetries ; ///< Count of unsuccessful retries of insertion
345 event_counter m_nEnsureExist ; ///< Count of \p ensure call for existed node
346 event_counter m_nEnsureNew ; ///< Count of \p ensure call for new node
347 event_counter m_nEnsureRetries ; ///< Count of unsuccessful retries of ensuring
348 event_counter m_nEraseSuccess ; ///< Count of successful call of \p erase and \p unlink
349 event_counter m_nEraseFailed ; ///< Count of failed call of \p erase and \p unlink
350 event_counter m_nEraseRetries ; ///< Count of unsuccessful retries inside erasing/unlinking
351 event_counter m_nFindSuccess ; ///< Count of successful \p find call
352 event_counter m_nFindFailed ; ///< Count of failed \p find call
353 event_counter m_nExtractMinSuccess ; ///< Count of successful call of \p extract_min
354 event_counter m_nExtractMinFailed ; ///< Count of failed call of \p extract_min
355 event_counter m_nExtractMinRetries ; ///< Count of unsuccessful retries inside \p extract_min
356 event_counter m_nExtractMaxSuccess ; ///< Count of successful call of \p extract_max
357 event_counter m_nExtractMaxFailed ; ///< Count of failed call of \p extract_max
358 event_counter m_nExtractMaxRetries ; ///< Count of unsuccessful retries inside \p extract_max
359 event_counter m_nSearchRetry ; ///< How many times the deleting node was encountered while searching
361 event_counter m_nHelpInsert ; ///< The number of insert help from the other thread
362 event_counter m_nHelpDelete ; ///< The number of delete help from the other thread
363 event_counter m_nHelpMark ; ///< The number of delete help (mark phase) from the other thread
364 event_counter m_nHelpGuardSuccess ; ///< The number of successful guarding of update descriptor data
365 event_counter m_nHelpGuardFailed ; ///< The number of failed guarding of update descriptor data
368 void onInternalNodeCreated() { ++m_nInternalNodeCreated ; }
369 void onInternalNodeDeleted() { ++m_nInternalNodeDeleted ; }
370 void onUpdateDescCreated() { ++m_nUpdateDescCreated ; }
371 void onUpdateDescDeleted() { ++m_nUpdateDescDeleted ; }
372 void onInsertSuccess() { ++m_nInsertSuccess ; }
373 void onInsertFailed() { ++m_nInsertFailed ; }
374 void onInsertRetry() { ++m_nInsertRetries ; }
375 void onEnsureExist() { ++m_nEnsureExist ; }
376 void onEnsureNew() { ++m_nEnsureNew ; }
377 void onEnsureRetry() { ++m_nEnsureRetries ; }
378 void onEraseSuccess() { ++m_nEraseSuccess ; }
379 void onEraseFailed() { ++m_nEraseFailed ; }
380 void onEraseRetry() { ++m_nEraseRetries ; }
381 void onExtractMinSuccess() { ++m_nExtractMinSuccess ; }
382 void onExtractMinFailed() { ++m_nExtractMinFailed ; }
383 void onExtractMinRetry() { ++m_nExtractMinRetries ; }
384 void onExtractMaxSuccess() { ++m_nExtractMaxSuccess ; }
385 void onExtractMaxFailed() { ++m_nExtractMaxFailed ; }
386 void onExtractMaxRetry() { ++m_nExtractMaxRetries ; }
387 void onFindSuccess() { ++m_nFindSuccess ; }
388 void onFindFailed() { ++m_nFindFailed ; }
389 void onSearchRetry() { ++m_nSearchRetry ; }
390 void onHelpInsert() { ++m_nHelpInsert ; }
391 void onHelpDelete() { ++m_nHelpDelete ; }
392 void onHelpMark() { ++m_nHelpMark ; }
393 void onHelpGuardSuccess() { ++m_nHelpGuardSuccess ; }
394 void onHelpGuardFailed() { ++m_nHelpGuardFailed ; }
398 /// EllenBinTree empty statistics
401 void onInternalNodeCreated() {}
402 void onInternalNodeDeleted() {}
403 void onUpdateDescCreated() {}
404 void onUpdateDescDeleted() {}
405 void onInsertSuccess() {}
406 void onInsertFailed() {}
407 void onInsertRetry() {}
408 void onEnsureExist() {}
409 void onEnsureNew() {}
410 void onEnsureRetry() {}
411 void onEraseSuccess() {}
412 void onEraseFailed() {}
413 void onEraseRetry() {}
414 void onExtractMinSuccess() {}
415 void onExtractMinFailed() {}
416 void onExtractMinRetry() {}
417 void onExtractMaxSuccess() {}
418 void onExtractMaxFailed() {}
419 void onExtractMaxRetry() {}
420 void onFindSuccess() {}
421 void onFindFailed() {}
422 void onSearchRetry() {}
423 void onHelpInsert() {}
424 void onHelpDelete() {}
426 void onHelpGuardSuccess() {}
427 void onHelpGuardFailed() {}
431 /// EllenBinTree traits
436 Possible values are: \p ellen_bintree::base_hook, \p ellen_bintree::member_hook, \p ellen_bintree::traits_hook.
438 typedef base_hook<> hook;
440 /// Key extracting functor
442 You should explicit define a valid functor.
443 The functor has the following prototype:
445 struct key_extractor {
446 void operator ()( Key& dest, T const& src );
449 It should initialize \p dest key from \p src data.
450 The functor is used to initialize internal nodes.
452 typedef opt::none key_extractor;
454 /// Key comparison functor
456 No default functor is provided. If the option is not specified, the \p less is used.
458 See \p cds::opt::compare option description for functor interface.
460 You should provide \p compare or \p less functor.
461 See \ref cds_intrusive_EllenBinTree_rcu_less "predicate requirements".
463 typedef opt::none compare;
465 /// Specifies binary predicate used for key compare.
467 See \p cds::opt::less option description for predicate interface.
469 You should provide \p compare or \p less functor.
470 See \ref cds_intrusive_EllenBinTree_rcu_less "predicate requirements".
472 typedef opt::none less;
476 The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
478 typedef opt::v::empty_disposer disposer;
482 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
483 To enable it use \p atomicity::item_counter
485 typedef atomicity::empty_item_counter item_counter;
487 /// C++ memory ordering model
489 List of available memory ordering see \p opt::memory_model
491 typedef opt::v::relaxed_ordering memory_model;
493 /// Allocator for update descriptors
495 The allocator type is used for \p ellen_bintree::update_desc.
497 Update descriptor is helping data structure with short lifetime and it is good candidate
498 for pooling. The number of simultaneously existing descriptors is bounded and it is
499 limited the number of threads working with the tree.
500 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue
501 is good choice for the free-list of update descriptors,
502 see \p cds::memory::vyukov_queue_pool free-list implementation.
504 Also notice that size of update descriptor is constant and not dependent on the type of data
505 stored in the tree so single free-list object can be used for several \p EllenBinTree object.
507 typedef CDS_DEFAULT_ALLOCATOR update_desc_allocator;
509 /// Allocator for internal nodes
511 The allocator type is used for \p ellen_bintree::internal_node.
513 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
515 /// Internal statistics
517 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
518 To enable it use \p ellen_bintree::stat.
520 typedef empty_stat stat;
522 /// Back-off strategy
523 typedef cds::backoff::empty back_off;
525 /// RCU deadlock checking policy (only for \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
527 List of available options see \p opt::rcu_check_deadlock
529 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
532 /// Metafunction converting option list to EllenBinTree traits
535 - \p opt::hook - hook used. Possible values are: \p ellen_bintree::base_hook, \p ellen_bintree::member_hook, \p ellen_bintree::traits_hook.
536 If the option is not specified, <tt>ellen_bintree::base_hook<></tt> is used.
537 - \p ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
539 struct key_extractor {
540 void operator ()( Key& dest, T const& src );
543 It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
544 - \p opt::compare - key compare functor. No default functor is provided.
545 If the option is not specified, \p %opt::less is used.
546 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
547 - \p opt::disposer - the functor used for dispose removed nodes. Default is \p opt::v::empty_disposer. Due the nature
548 of GC schema the disposer may be called asynchronously. The disposer is used only for leaf nodes.
549 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
550 To enable it use \p atomicity::item_counter
551 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
552 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
553 - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
554 default is \ref CDS_DEFAULT_ALLOCATOR.
555 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
556 The number of simultaneously existing descriptors is bounded and depends on the number of threads
557 working with the tree and GC internals.
558 A bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good candidate
559 for the free-list of update descriptors, see cds::memory::vyukov_queue_pool free-list implementation.
560 Also notice that size of update descriptor is constant and not dependent on the type of data
561 stored in the tree so single free-list object can be used for all \p %EllenBinTree objects.
562 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
563 - \p opt::stat - internal statistics, by default it is disabled (\p ellen_bintree::empty_stat)
564 To enable statistics use \p \p ellen_bintree::stat
565 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
566 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
568 template <typename... Options>
570 # ifdef CDS_DOXYGEN_INVOKED
571 typedef implementation_defined type ; ///< Metafunction result
573 typedef typename cds::opt::make_options<
574 typename cds::opt::find_type_traits< traits, Options... >::type
583 template <typename Key, typename T, typename Compare, typename NodeTraits>
586 typedef Compare key_compare;
587 typedef Key key_type;
588 typedef T value_type;
589 typedef NodeTraits node_traits;
591 template <typename Q1, typename Q2>
592 int operator()( Q1 const& v1, Q2 const& v2) const
594 return key_compare()( v1, v2 );
597 template <typename LeafNode>
598 int operator()( internal_node<key_type, LeafNode> const& n1, internal_node<key_type, LeafNode> const& n2 ) const
600 if ( n1.infinite_key() )
601 return n2.infinite_key() ? n1.infinite_key() - n2.infinite_key() : 1;
602 else if ( n2.infinite_key() )
604 return operator()( n1.m_Key, n2.m_Key );
607 template <typename LeafNode, typename Q>
608 int operator()( internal_node<key_type, LeafNode> const& n, Q const& v ) const
610 if ( n.infinite_key() )
612 return operator()( n.m_Key, v );
615 template <typename LeafNode, typename Q>
616 int operator()( Q const& v, internal_node<key_type, LeafNode> const& n ) const
618 if ( n.infinite_key() )
620 return operator()( v, n.m_Key );
623 template <typename GC, typename Tag>
624 int operator()( node<GC, Tag> const& n1, node<GC, Tag> const& n2 ) const
626 if ( n1.infinite_key() != n2.infinite_key() )
627 return n1.infinite_key() - n2.infinite_key();
628 return operator()( *node_traits::to_value_ptr( n1 ), *node_traits::to_value_ptr( n2 ));
631 template <typename GC, typename Tag, typename Q>
632 int operator()( node<GC, Tag> const& n, Q const& v ) const
634 if ( n.infinite_key() )
636 return operator()( *node_traits::to_value_ptr( n ), v );
639 template <typename GC, typename Tag, typename Q>
640 int operator()( Q const& v, node<GC, Tag> const& n ) const
642 if ( n.infinite_key() )
644 return operator()( v, *node_traits::to_value_ptr( n ) );
647 template <typename GC>
648 int operator()( base_node<GC> const& n1, base_node<GC> const& n2 ) const
650 if ( n1.infinite_key() != n2.infinite_key() )
651 return n1.infinite_key() - n2.infinite_key();
652 if ( n1.is_leaf() ) {
654 return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_leaf_node( n2 ));
656 return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_internal_node( n2 ));
660 return operator()( node_traits::to_internal_node( n1 ), node_traits::to_leaf_node( n2 ));
662 return operator()( node_traits::to_internal_node( n1 ), node_traits::to_internal_node( n2 ));
665 template <typename GC, typename Q>
666 int operator()( base_node<GC> const& n, Q const& v ) const
668 if ( n.infinite_key())
671 return operator()( node_traits::to_leaf_node( n ), v );
672 return operator()( node_traits::to_internal_node( n ), v );
675 template <typename GC, typename Q>
676 int operator()( Q const& v, base_node<GC> const& n ) const
678 return -operator()( n, v );
681 template <typename GC, typename LeafNode >
682 int operator()( base_node<GC> const& i, internal_node<key_type, LeafNode> const& n ) const
685 return operator()( static_cast<LeafNode const&>(i), n );
686 return operator()( static_cast<internal_node<key_type, LeafNode> const&>(i), n );
689 template <typename GC, typename LeafNode >
690 int operator()( internal_node<key_type, LeafNode> const& n, base_node<GC> const& i ) const
692 return -operator()( i, n );
695 template <typename GC, typename Tag >
696 int operator()( node<GC, Tag> const& n, internal_node<key_type, node<GC, Tag> > const& i ) const
698 if ( !n.infinite_key() ) {
699 if ( i.infinite_key() )
701 return operator()( n, i.m_Key );
704 if ( !i.infinite_key())
706 return int( n.infinite_key()) - int( i.infinite_key());
709 template <typename GC, typename Tag >
710 int operator()( internal_node<key_type, node<GC, Tag> > const& i, node<GC, Tag> const& n ) const
712 return -operator()( n, i );
717 } // namespace details
719 } // namespace ellen_bintree
722 template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
725 }} // namespace cds::intrusive
727 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H