3 #ifndef __CDS_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H
4 #define __CDS_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 {
18 template <class GC> struct base_node;
19 template <class GC, typename Tag = opt::none> struct node;
20 template <class GC, typename Key> struct internal_node;
24 Update descriptor is used internally for helping concurrent threads
25 to complete modifying operation.
26 Usually, you should not use \p update_desc type directly until
27 you want to develop special free-list of update descriptor.
30 - \p LeafNode - leaf node type, see \ref node
31 - \p InternalNode - internal node type, see \ref internal_node
33 @note Size of update descriptor is constant.
34 It does not depends of template arguments.
36 template <typename LeafNode, typename InternalNode>
39 typedef LeafNode leaf_node;
40 typedef InternalNode internal_node;
42 typedef cds::details::marked_ptr< update_desc, 3 > update_ptr;
52 internal_node * pParent;
58 internal_node * pGrandParent;
59 internal_node * pParent;
61 update_desc * pUpdateParent;
62 bool bDisposeLeaf; // true if pLeaf should be disposed, false otherwise (for extract operation, RCU)
72 update_desc * pNextRetire ; // for local retired list (RCU)
75 : pNextRetire( nullptr )
84 internal = 1, ///< set for internal node
85 key_infinite1 = 2, ///< set if node's key is Inf1
86 key_infinite2 = 4, ///< set if node's key is Inf2
88 key_infinite = key_infinite1 | key_infinite2 ///< Cumulative infinite flags
91 unsigned int m_nFlags ; ///< Internal flags
93 /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
94 explicit basic_node( bool bInternal )
95 : m_nFlags( bInternal ? internal : 0 )
98 /// Checks if the node is a leaf
101 return !is_internal();
104 /// Checks if the node is internal
105 bool is_internal() const
107 return (m_nFlags & internal) != 0;
110 /// Returns infinite key, 0 if the node is not infinite
111 unsigned int infinite_key() const
113 return m_nFlags & key_infinite;
116 /// Sets infinite key for the node (for internal use only!!!)
117 void infinite_key( int nInf )
119 m_nFlags &= ~key_infinite;
122 m_nFlags |= key_infinite1;
125 m_nFlags |= key_infinite2;
137 struct base_node: public basic_node
139 typedef basic_node base_class;
141 typedef GC gc ; ///< Garbage collector
142 /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
143 explicit base_node( bool bInternal )
144 : base_class( bInternal )
149 /// Ellen's binary tree leaf node
152 - \p GC - one of \ref cds_garbage_collector "garbage collector type"
153 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
155 template <typename GC,
156 # ifdef CDS_DOXYGEN_INVOKED
157 typename Tag = opt::none
163 # ifndef CDS_DOXYGEN_INVOKED
164 : public base_node< GC >
168 typedef base_node< GC > base_class;
171 typedef GC gc; ///< Garbage collector
172 typedef Tag tag; ///< Tag
176 : base_class( false )
180 /// Ellen's binary tree internal node
184 - \p LeafNode - leaf node type
186 template <typename Key, typename LeafNode>
188 # ifndef CDS_DOXYGEN_INVOKED
189 : public base_node<typename LeafNode::gc>
193 typedef base_node<typename LeafNode::gc> base_class;
196 typedef Key key_type; ///< key type
197 typedef LeafNode leaf_node; ///< type of leaf node
198 typedef update_desc< leaf_node, internal_node > update_desc_type; ///< Update descriptor
199 typedef typename update_desc_type::update_ptr update_ptr; ///< Marked pointer to update descriptor
201 key_type m_Key; ///< Regular key
202 atomics::atomic<base_class *> m_pLeft; ///< Left subtree
203 atomics::atomic<base_class *> m_pRight; ///< Right subtree
204 atomics::atomic<update_ptr> m_pUpdate; ///< Update descriptor
206 uintptr_t m_nEmptyUpdate; ///< ABA prevention for m_pUpdate, from 0..2^16 step 4
213 , m_pRight( nullptr )
214 , m_pUpdate( update_ptr() )
219 update_ptr null_update_desc()
221 return update_ptr( reinterpret_cast<update_desc_type *>( (++m_nEmptyUpdate << 2) & 0xFFFF ) );
226 /// Types of EllenBinTree node
228 This struct declares different \p %EllenBinTree node types.
229 It can be useful for simplifying \p %EllenBinTree node declaration in your application.
232 - \p GC - one of \ref cds_garbage_collector "garbage collector type"
234 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
236 template <typename GC, typename Key, typename Tag = opt::none>
239 typedef node<GC, Tag> leaf_node_type; ///< Leaf node type
240 typedef internal_node<Key, leaf_node_type> internal_node_type; ///< Internal node type
241 typedef update_desc<leaf_node_type, internal_node_type> update_desc_type; ///< Update descriptor type
246 struct default_hook {
247 typedef undefined_gc gc;
248 typedef opt::none tag;
253 template < typename HookType, typename... Options>
256 typedef typename opt::make_options< default_hook, Options...>::type options;
257 typedef typename options::gc gc;
258 typedef typename options::tag tag;
259 typedef node<gc, tag> node_type;
260 typedef HookType hook_type;
267 - \p opt::gc - garbage collector
268 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
270 template < typename... Options >
271 struct base_hook: public hook< opt::base_hook_tag, Options... >
276 \p MemberOffset defines offset in bytes of \ref node member into your structure.
277 Use \p offsetof macro to define \p MemberOffset
280 - \p opt::gc - garbage collector
281 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
283 template < size_t MemberOffset, typename... Options >
284 struct member_hook: public hook< opt::member_hook_tag, Options... >
287 static CDS_CONSTEXPR const size_t c_nMemberOffset = MemberOffset;
293 \p NodeTraits defines type traits for node.
294 See \ref node_traits for \p NodeTraits interface description
297 - opt::gc - garbage collector
298 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
300 template <typename NodeTraits, typename... Options >
301 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
304 typedef NodeTraits node_traits;
308 /// Key extracting functor option setter
309 template <typename Type>
310 struct key_extractor {
312 template <typename Base> struct pack: public Base
314 typedef Type key_extractor;
319 /// Update descriptor allocator option setter
320 template <typename Type>
321 struct update_desc_allocator {
323 template <typename Base> struct pack: public Base
325 typedef Type update_desc_allocator;
330 /// EllenBinTree internal statistics
331 template <typename Counter = cds::atomicity::event_counter>
333 typedef Counter event_counter ; ///< Event counter type
335 event_counter m_nInternalNodeCreated ; ///< Total count of created internal node
336 event_counter m_nInternalNodeDeleted ; ///< Total count of deleted internal node
337 event_counter m_nUpdateDescCreated ; ///< Total count of created update descriptors
338 event_counter m_nUpdateDescDeleted ; ///< Total count of deleted update descriptors
340 event_counter m_nInsertSuccess ; ///< Count of success insertion
341 event_counter m_nInsertFailed ; ///< Count of failed insertion
342 event_counter m_nInsertRetries ; ///< Count of unsuccessful retries of insertion
343 event_counter m_nEnsureExist ; ///< Count of \p ensure call for existed node
344 event_counter m_nEnsureNew ; ///< Count of \p ensure call for new node
345 event_counter m_nEnsureRetries ; ///< Count of unsuccessful retries of ensuring
346 event_counter m_nEraseSuccess ; ///< Count of successful call of \p erase and \p unlink
347 event_counter m_nEraseFailed ; ///< Count of failed call of \p erase and \p unlink
348 event_counter m_nEraseRetries ; ///< Count of unsuccessful retries inside erasing/unlinking
349 event_counter m_nFindSuccess ; ///< Count of successful \p find call
350 event_counter m_nFindFailed ; ///< Count of failed \p find call
351 event_counter m_nExtractMinSuccess ; ///< Count of successful call of \p extract_min
352 event_counter m_nExtractMinFailed ; ///< Count of failed call of \p extract_min
353 event_counter m_nExtractMinRetries ; ///< Count of unsuccessful retries inside \p extract_min
354 event_counter m_nExtractMaxSuccess ; ///< Count of successful call of \p extract_max
355 event_counter m_nExtractMaxFailed ; ///< Count of failed call of \p extract_max
356 event_counter m_nExtractMaxRetries ; ///< Count of unsuccessful retries inside \p extract_max
357 event_counter m_nSearchRetry ; ///< How many times the deleting node was encountered while searching
359 event_counter m_nHelpInsert ; ///< The number of insert help from the other thread
360 event_counter m_nHelpDelete ; ///< The number of delete help from the other thread
361 event_counter m_nHelpMark ; ///< The number of delete help (mark phase) from the other thread
362 event_counter m_nHelpGuardSuccess ; ///< The number of successful guarding of update descriptor data
363 event_counter m_nHelpGuardFailed ; ///< The number of failed guarding of update descriptor data
366 void onInternalNodeCreated() { ++m_nInternalNodeCreated ; }
367 void onInternalNodeDeleted() { ++m_nInternalNodeDeleted ; }
368 void onUpdateDescCreated() { ++m_nUpdateDescCreated ; }
369 void onUpdateDescDeleted() { ++m_nUpdateDescDeleted ; }
370 void onInsertSuccess() { ++m_nInsertSuccess ; }
371 void onInsertFailed() { ++m_nInsertFailed ; }
372 void onInsertRetry() { ++m_nInsertRetries ; }
373 void onEnsureExist() { ++m_nEnsureExist ; }
374 void onEnsureNew() { ++m_nEnsureNew ; }
375 void onEnsureRetry() { ++m_nEnsureRetries ; }
376 void onEraseSuccess() { ++m_nEraseSuccess ; }
377 void onEraseFailed() { ++m_nEraseFailed ; }
378 void onEraseRetry() { ++m_nEraseRetries ; }
379 void onExtractMinSuccess() { ++m_nExtractMinSuccess ; }
380 void onExtractMinFailed() { ++m_nExtractMinFailed ; }
381 void onExtractMinRetry() { ++m_nExtractMinRetries ; }
382 void onExtractMaxSuccess() { ++m_nExtractMaxSuccess ; }
383 void onExtractMaxFailed() { ++m_nExtractMaxFailed ; }
384 void onExtractMaxRetry() { ++m_nExtractMaxRetries ; }
385 void onFindSuccess() { ++m_nFindSuccess ; }
386 void onFindFailed() { ++m_nFindFailed ; }
387 void onSearchRetry() { ++m_nSearchRetry ; }
388 void onHelpInsert() { ++m_nHelpInsert ; }
389 void onHelpDelete() { ++m_nHelpDelete ; }
390 void onHelpMark() { ++m_nHelpMark ; }
391 void onHelpGuardSuccess() { ++m_nHelpGuardSuccess ; }
392 void onHelpGuardFailed() { ++m_nHelpGuardFailed ; }
396 /// EllenBinTree empty statistics
399 void onInternalNodeCreated() {}
400 void onInternalNodeDeleted() {}
401 void onUpdateDescCreated() {}
402 void onUpdateDescDeleted() {}
403 void onInsertSuccess() {}
404 void onInsertFailed() {}
405 void onInsertRetry() {}
406 void onEnsureExist() {}
407 void onEnsureNew() {}
408 void onEnsureRetry() {}
409 void onEraseSuccess() {}
410 void onEraseFailed() {}
411 void onEraseRetry() {}
412 void onExtractMinSuccess() {}
413 void onExtractMinFailed() {}
414 void onExtractMinRetry() {}
415 void onExtractMaxSuccess() {}
416 void onExtractMaxFailed() {}
417 void onExtractMaxRetry() {}
418 void onFindSuccess() {}
419 void onFindFailed() {}
420 void onSearchRetry() {}
421 void onHelpInsert() {}
422 void onHelpDelete() {}
424 void onHelpGuardSuccess() {}
425 void onHelpGuardFailed() {}
429 /// EllenBinTree traits
434 Possible values are: \p ellen_bintree::base_hook, \p ellen_bintree::member_hook, \p ellen_bintree::traits_hook.
436 typedef base_hook<> hook;
438 /// Key extracting functor
440 You should explicit define a valid functor.
441 The functor has the following prototype:
443 struct key_extractor {
444 void operator ()( Key& dest, T const& src );
447 It should initialize \p dest key from \p src data.
448 The functor is used to initialize internal nodes.
450 typedef opt::none key_extractor;
452 /// Key comparison functor
454 No default functor is provided. If the option is not specified, the \p less is used.
456 See \p cds::opt::compare option description for functor interface.
458 You should provide \p compare or \p less functor.
459 See \ref cds_intrusive_EllenBinTree_rcu_less "predicate requirements".
461 typedef opt::none compare;
463 /// Specifies binary predicate used for key compare.
465 See \p cds::opt::less option description for predicate interface.
467 You should provide \p compare or \p less functor.
468 See \ref cds_intrusive_EllenBinTree_rcu_less "predicate requirements".
470 typedef opt::none less;
474 The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
476 typedef opt::v::empty_disposer disposer;
480 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
481 To enable it use \p atomicity::item_counter
483 typedef atomicity::empty_item_counter item_counter;
485 /// C++ memory ordering model
487 List of available memory ordering see \p opt::memory_model
489 typedef opt::v::relaxed_ordering memory_model;
491 /// Allocator for update descriptors
493 The allocator type is used for \p ellen_bintree::update_desc.
495 Update descriptor is helping data structure with short lifetime and it is good candidate
496 for pooling. The number of simultaneously existing descriptors is bounded and it is
497 limited the number of threads working with the tree.
498 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue
499 is good choice for the free-list of update descriptors,
500 see \p cds::memory::vyukov_queue_pool free-list implementation.
502 Also notice that size of update descriptor is constant and not dependent on the type of data
503 stored in the tree so single free-list object can be used for several \p EllenBinTree object.
505 typedef CDS_DEFAULT_ALLOCATOR update_desc_allocator;
507 /// Allocator for internal nodes
509 The allocator type is used for \p ellen_bintree::internal_node.
511 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
513 /// Internal statistics
515 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
516 To enable it use \p ellen_bintree::stat.
518 typedef empty_stat stat;
520 /// Back-off strategy
521 typedef cds::backoff::empty back_off;
523 /// RCU deadlock checking policy (only for \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
525 List of available options see \p opt::rcu_check_deadlock
527 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
530 /// Metafunction converting option list to EllenBinTree traits
533 - \p opt::hook - hook used. Possible values are: \p ellen_bintree::base_hook, \p ellen_bintree::member_hook, \p ellen_bintree::traits_hook.
534 If the option is not specified, <tt>ellen_bintree::base_hook<></tt> is used.
535 - \p ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
537 struct key_extractor {
538 void operator ()( Key& dest, T const& src );
541 It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
542 - \p opt::compare - key compare functor. No default functor is provided.
543 If the option is not specified, \p %opt::less is used.
544 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
545 - \p opt::disposer - the functor used for dispose removed nodes. Default is \p opt::v::empty_disposer. Due the nature
546 of GC schema the disposer may be called asynchronously. The disposer is used only for leaf nodes.
547 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
548 To enable it use \p atomicity::item_counter
549 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
550 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
551 - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
552 default is \ref CDS_DEFAULT_ALLOCATOR.
553 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
554 The number of simultaneously existing descriptors is bounded and depends on the number of threads
555 working with the tree and GC internals.
556 A bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good candidate
557 for the free-list of update descriptors, see cds::memory::vyukov_queue_pool free-list implementation.
558 Also notice that size of update descriptor is constant and not dependent on the type of data
559 stored in the tree so single free-list object can be used for all \p %EllenBinTree objects.
560 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
561 - \p opt::stat - internal statistics, by default it is disabled (\p ellen_bintree::empty_stat)
562 To enable statistics use \p \p ellen_bintree::stat
563 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
564 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
566 template <typename... Options>
568 # ifdef CDS_DOXYGEN_INVOKED
569 typedef implementation_defined type ; ///< Metafunction result
571 typedef typename cds::opt::make_options<
572 typename cds::opt::find_type_traits< traits, Options... >::type
581 template <typename Key, typename T, typename Compare, typename NodeTraits>
584 typedef Compare key_compare;
585 typedef Key key_type;
586 typedef T value_type;
587 typedef NodeTraits node_traits;
589 template <typename Q1, typename Q2>
590 int operator()( Q1 const& v1, Q2 const& v2) const
592 return key_compare()( v1, v2 );
595 template <typename LeafNode>
596 int operator()( internal_node<key_type, LeafNode> const& n1, internal_node<key_type, LeafNode> const& n2 ) const
598 if ( n1.infinite_key() )
599 return n2.infinite_key() ? n1.infinite_key() - n2.infinite_key() : 1;
600 else if ( n2.infinite_key() )
602 return operator()( n1.m_Key, n2.m_Key );
605 template <typename LeafNode, typename Q>
606 int operator()( internal_node<key_type, LeafNode> const& n, Q const& v ) const
608 if ( n.infinite_key() )
610 return operator()( n.m_Key, v );
613 template <typename LeafNode, typename Q>
614 int operator()( Q const& v, internal_node<key_type, LeafNode> const& n ) const
616 if ( n.infinite_key() )
618 return operator()( v, n.m_Key );
621 template <typename GC, typename Tag>
622 int operator()( node<GC, Tag> const& n1, node<GC, Tag> const& n2 ) const
624 if ( n1.infinite_key() != n2.infinite_key() )
625 return n1.infinite_key() - n2.infinite_key();
626 return operator()( *node_traits::to_value_ptr( n1 ), *node_traits::to_value_ptr( n2 ));
629 template <typename GC, typename Tag, typename Q>
630 int operator()( node<GC, Tag> const& n, Q const& v ) const
632 if ( n.infinite_key() )
634 return operator()( *node_traits::to_value_ptr( n ), v );
637 template <typename GC, typename Tag, typename Q>
638 int operator()( Q const& v, node<GC, Tag> const& n ) const
640 if ( n.infinite_key() )
642 return operator()( v, *node_traits::to_value_ptr( n ) );
645 template <typename GC>
646 int operator()( base_node<GC> const& n1, base_node<GC> const& n2 ) const
648 if ( n1.infinite_key() != n2.infinite_key() )
649 return n1.infinite_key() - n2.infinite_key();
650 if ( n1.is_leaf() ) {
652 return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_leaf_node( n2 ));
654 return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_internal_node( n2 ));
658 return operator()( node_traits::to_internal_node( n1 ), node_traits::to_leaf_node( n2 ));
660 return operator()( node_traits::to_internal_node( n1 ), node_traits::to_internal_node( n2 ));
663 template <typename GC, typename Q>
664 int operator()( base_node<GC> const& n, Q const& v ) const
666 if ( n.infinite_key())
669 return operator()( node_traits::to_leaf_node( n ), v );
670 return operator()( node_traits::to_internal_node( n ), v );
673 template <typename GC, typename Q>
674 int operator()( Q const& v, base_node<GC> const& n ) const
676 return -operator()( n, v );
679 template <typename GC, typename LeafNode >
680 int operator()( base_node<GC> const& i, internal_node<key_type, LeafNode> const& n ) const
683 return operator()( static_cast<LeafNode const&>(i), n );
684 return operator()( static_cast<internal_node<key_type, LeafNode> const&>(i), n );
687 template <typename GC, typename LeafNode >
688 int operator()( internal_node<key_type, LeafNode> const& n, base_node<GC> const& i ) const
690 return -operator()( i, n );
693 template <typename GC, typename Tag >
694 int operator()( node<GC, Tag> const& n, internal_node<key_type, node<GC, Tag> > const& i ) const
696 if ( !n.infinite_key() ) {
697 if ( i.infinite_key() )
699 return operator()( n, i.m_Key );
702 if ( !i.infinite_key())
704 return int( n.infinite_key()) - int( i.infinite_key());
707 template <typename GC, typename Tag >
708 int operator()( internal_node<key_type, node<GC, Tag> > const& i, node<GC, Tag> const& n ) const
710 return -operator()( n, i );
715 } // namespace details
717 } // namespace ellen_bintree
720 template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
723 }} // namespace cds::intrusive
725 #endif // #ifndef __CDS_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H