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 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 & internal) != 0;
111 /// Returns infinite key, 0 if the node is not infinite
112 unsigned int infinite_key() const
114 return m_nFlags & key_infinite;
117 /// Sets infinite key for the node (for internal use only!!!)
118 void infinite_key( int nInf )
120 m_nFlags &= ~key_infinite;
123 m_nFlags |= key_infinite1;
126 m_nFlags |= key_infinite2;
138 struct base_node: public basic_node
140 typedef basic_node base_class;
142 typedef GC gc ; ///< Garbage collector
143 /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
144 explicit base_node( bool bInternal )
145 : base_class( bInternal )
150 /// Ellen's binary tree leaf node
153 - \p GC - one of \ref cds_garbage_collector "garbage collector type"
154 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
156 template <typename GC,
157 # ifdef CDS_DOXYGEN_INVOKED
158 typename Tag = opt::none
164 # ifndef CDS_DOXYGEN_INVOKED
165 : public base_node< GC >
169 typedef base_node< GC > base_class;
172 typedef GC gc; ///< Garbage collector
173 typedef Tag tag; ///< Tag
177 : base_class( false )
181 /// Ellen's binary tree internal node
185 - \p LeafNode - leaf node type
187 template <typename Key, typename LeafNode>
189 # ifndef CDS_DOXYGEN_INVOKED
190 : public base_node<typename LeafNode::gc>
194 typedef base_node<typename LeafNode::gc> base_class;
197 typedef Key key_type; ///< key type
198 typedef LeafNode leaf_node; ///< type of leaf node
199 typedef update_desc< leaf_node, internal_node > update_desc_type; ///< Update descriptor
200 typedef typename update_desc_type::update_ptr update_ptr; ///< Marked pointer to update descriptor
202 key_type m_Key; ///< Regular key
203 atomics::atomic<base_class *> m_pLeft; ///< Left subtree
204 atomics::atomic<base_class *> m_pRight; ///< Right subtree
205 atomics::atomic<update_ptr> m_pUpdate; ///< Update descriptor
207 uintptr_t m_nEmptyUpdate; ///< ABA prevention for m_pUpdate, from 0..2^16 step 4
214 , m_pRight( nullptr )
215 , m_pUpdate( update_ptr() )
220 update_ptr null_update_desc()
222 return update_ptr( reinterpret_cast<update_desc_type *>( (++m_nEmptyUpdate << 2) & 0xFFFF ) );
227 /// Types of EllenBinTree node
229 This struct declares different \p %EllenBinTree node types.
230 It can be useful for simplifying \p %EllenBinTree node declaration in your application.
233 - \p GC - one of \ref cds_garbage_collector "garbage collector type"
235 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
237 template <typename GC, typename Key, typename Tag = opt::none>
240 typedef node<GC, Tag> leaf_node_type; ///< Leaf node type
241 typedef internal_node<Key, leaf_node_type> internal_node_type; ///< Internal node type
242 typedef update_desc<leaf_node_type, internal_node_type> update_desc_type; ///< Update descriptor type
247 struct default_hook {
248 typedef undefined_gc gc;
249 typedef opt::none tag;
254 template < typename HookType, typename... Options>
257 typedef typename opt::make_options< default_hook, Options...>::type options;
258 typedef typename options::gc gc;
259 typedef typename options::tag tag;
260 typedef node<gc, tag> node_type;
261 typedef HookType hook_type;
268 - \p opt::gc - garbage collector
269 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
271 template < typename... Options >
272 struct base_hook: public hook< opt::base_hook_tag, Options... >
277 \p MemberOffset defines offset in bytes of \ref node member into your structure.
278 Use \p offsetof macro to define \p MemberOffset
281 - \p opt::gc - garbage collector
282 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
284 template < size_t MemberOffset, typename... Options >
285 struct member_hook: public hook< opt::member_hook_tag, Options... >
288 static CDS_CONSTEXPR const size_t c_nMemberOffset = MemberOffset;
294 \p NodeTraits defines type traits for node.
295 See \ref node_traits for \p NodeTraits interface description
298 - opt::gc - garbage collector
299 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
301 template <typename NodeTraits, typename... Options >
302 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
305 typedef NodeTraits node_traits;
309 /// Key extracting functor option setter
310 template <typename Type>
311 struct key_extractor {
313 template <typename Base> struct pack: public Base
315 typedef Type key_extractor;
320 /// Update descriptor allocator option setter
321 template <typename Type>
322 struct update_desc_allocator {
324 template <typename Base> struct pack: public Base
326 typedef Type update_desc_allocator;
331 /// EllenBinTree internal statistics
332 template <typename Counter = cds::atomicity::event_counter>
334 typedef Counter event_counter ; ///< Event counter type
336 event_counter m_nInternalNodeCreated ; ///< Total count of created internal node
337 event_counter m_nInternalNodeDeleted ; ///< Total count of deleted internal node
338 event_counter m_nUpdateDescCreated ; ///< Total count of created update descriptors
339 event_counter m_nUpdateDescDeleted ; ///< Total count of deleted update descriptors
341 event_counter m_nInsertSuccess ; ///< Count of success insertion
342 event_counter m_nInsertFailed ; ///< Count of failed insertion
343 event_counter m_nInsertRetries ; ///< Count of unsuccessful retries of insertion
344 event_counter m_nEnsureExist ; ///< Count of \p ensure call for existed node
345 event_counter m_nEnsureNew ; ///< Count of \p ensure call for new node
346 event_counter m_nEnsureRetries ; ///< Count of unsuccessful retries of ensuring
347 event_counter m_nEraseSuccess ; ///< Count of successful call of \p erase and \p unlink
348 event_counter m_nEraseFailed ; ///< Count of failed call of \p erase and \p unlink
349 event_counter m_nEraseRetries ; ///< Count of unsuccessful retries inside erasing/unlinking
350 event_counter m_nFindSuccess ; ///< Count of successful \p find call
351 event_counter m_nFindFailed ; ///< Count of failed \p find call
352 event_counter m_nExtractMinSuccess ; ///< Count of successful call of \p extract_min
353 event_counter m_nExtractMinFailed ; ///< Count of failed call of \p extract_min
354 event_counter m_nExtractMinRetries ; ///< Count of unsuccessful retries inside \p extract_min
355 event_counter m_nExtractMaxSuccess ; ///< Count of successful call of \p extract_max
356 event_counter m_nExtractMaxFailed ; ///< Count of failed call of \p extract_max
357 event_counter m_nExtractMaxRetries ; ///< Count of unsuccessful retries inside \p extract_max
358 event_counter m_nSearchRetry ; ///< How many times the deleting node was encountered while searching
360 event_counter m_nHelpInsert ; ///< The number of insert help from the other thread
361 event_counter m_nHelpDelete ; ///< The number of delete help from the other thread
362 event_counter m_nHelpMark ; ///< The number of delete help (mark phase) from the other thread
363 event_counter m_nHelpGuardSuccess ; ///< The number of successful guarding of update descriptor data
364 event_counter m_nHelpGuardFailed ; ///< The number of failed guarding of update descriptor data
367 void onInternalNodeCreated() { ++m_nInternalNodeCreated ; }
368 void onInternalNodeDeleted() { ++m_nInternalNodeDeleted ; }
369 void onUpdateDescCreated() { ++m_nUpdateDescCreated ; }
370 void onUpdateDescDeleted() { ++m_nUpdateDescDeleted ; }
371 void onInsertSuccess() { ++m_nInsertSuccess ; }
372 void onInsertFailed() { ++m_nInsertFailed ; }
373 void onInsertRetry() { ++m_nInsertRetries ; }
374 void onEnsureExist() { ++m_nEnsureExist ; }
375 void onEnsureNew() { ++m_nEnsureNew ; }
376 void onEnsureRetry() { ++m_nEnsureRetries ; }
377 void onEraseSuccess() { ++m_nEraseSuccess ; }
378 void onEraseFailed() { ++m_nEraseFailed ; }
379 void onEraseRetry() { ++m_nEraseRetries ; }
380 void onExtractMinSuccess() { ++m_nExtractMinSuccess ; }
381 void onExtractMinFailed() { ++m_nExtractMinFailed ; }
382 void onExtractMinRetry() { ++m_nExtractMinRetries ; }
383 void onExtractMaxSuccess() { ++m_nExtractMaxSuccess ; }
384 void onExtractMaxFailed() { ++m_nExtractMaxFailed ; }
385 void onExtractMaxRetry() { ++m_nExtractMaxRetries ; }
386 void onFindSuccess() { ++m_nFindSuccess ; }
387 void onFindFailed() { ++m_nFindFailed ; }
388 void onSearchRetry() { ++m_nSearchRetry ; }
389 void onHelpInsert() { ++m_nHelpInsert ; }
390 void onHelpDelete() { ++m_nHelpDelete ; }
391 void onHelpMark() { ++m_nHelpMark ; }
392 void onHelpGuardSuccess() { ++m_nHelpGuardSuccess ; }
393 void onHelpGuardFailed() { ++m_nHelpGuardFailed ; }
397 /// EllenBinTree empty statistics
400 void onInternalNodeCreated() {}
401 void onInternalNodeDeleted() {}
402 void onUpdateDescCreated() {}
403 void onUpdateDescDeleted() {}
404 void onInsertSuccess() {}
405 void onInsertFailed() {}
406 void onInsertRetry() {}
407 void onEnsureExist() {}
408 void onEnsureNew() {}
409 void onEnsureRetry() {}
410 void onEraseSuccess() {}
411 void onEraseFailed() {}
412 void onEraseRetry() {}
413 void onExtractMinSuccess() {}
414 void onExtractMinFailed() {}
415 void onExtractMinRetry() {}
416 void onExtractMaxSuccess() {}
417 void onExtractMaxFailed() {}
418 void onExtractMaxRetry() {}
419 void onFindSuccess() {}
420 void onFindFailed() {}
421 void onSearchRetry() {}
422 void onHelpInsert() {}
423 void onHelpDelete() {}
425 void onHelpGuardSuccess() {}
426 void onHelpGuardFailed() {}
430 /// EllenBinTree traits
435 Possible values are: \p ellen_bintree::base_hook, \p ellen_bintree::member_hook, \p ellen_bintree::traits_hook.
437 typedef base_hook<> hook;
439 /// Key extracting functor
441 You should explicit define a valid functor.
442 The functor has the following prototype:
444 struct key_extractor {
445 void operator ()( Key& dest, T const& src );
448 It should initialize \p dest key from \p src data.
449 The functor is used to initialize internal nodes.
451 typedef opt::none key_extractor;
453 /// Key comparison functor
455 No default functor is provided. If the option is not specified, the \p less is used.
457 See \p cds::opt::compare option description for functor interface.
459 You should provide \p compare or \p less functor.
460 See \ref cds_intrusive_EllenBinTree_rcu_less "predicate requirements".
462 typedef opt::none compare;
464 /// Specifies binary predicate used for key compare.
466 See \p cds::opt::less option description for predicate interface.
468 You should provide \p compare or \p less functor.
469 See \ref cds_intrusive_EllenBinTree_rcu_less "predicate requirements".
471 typedef opt::none less;
475 The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
477 typedef opt::v::empty_disposer disposer;
481 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
482 To enable it use \p atomicity::item_counter
484 typedef atomicity::empty_item_counter item_counter;
486 /// C++ memory ordering model
488 List of available memory ordering see \p opt::memory_model
490 typedef opt::v::relaxed_ordering memory_model;
492 /// Allocator for update descriptors
494 The allocator type is used for \p ellen_bintree::update_desc.
496 Update descriptor is helping data structure with short lifetime and it is good candidate
497 for pooling. The number of simultaneously existing descriptors is bounded and it is
498 limited the number of threads working with the tree.
499 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue
500 is good choice for the free-list of update descriptors,
501 see \p cds::memory::vyukov_queue_pool free-list implementation.
503 Also notice that size of update descriptor is constant and not dependent on the type of data
504 stored in the tree so single free-list object can be used for several \p EllenBinTree object.
506 typedef CDS_DEFAULT_ALLOCATOR update_desc_allocator;
508 /// Allocator for internal nodes
510 The allocator type is used for \p ellen_bintree::internal_node.
512 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
514 /// Internal statistics
516 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
517 To enable it use \p ellen_bintree::stat.
519 typedef empty_stat stat;
521 /// Back-off strategy
522 typedef cds::backoff::empty back_off;
524 /// RCU deadlock checking policy (only for \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
526 List of available options see \p opt::rcu_check_deadlock
528 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
531 /// Metafunction converting option list to EllenBinTree traits
534 - \p opt::hook - hook used. Possible values are: \p ellen_bintree::base_hook, \p ellen_bintree::member_hook, \p ellen_bintree::traits_hook.
535 If the option is not specified, <tt>ellen_bintree::base_hook<></tt> is used.
536 - \p ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
538 struct key_extractor {
539 void operator ()( Key& dest, T const& src );
542 It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
543 - \p opt::compare - key compare functor. No default functor is provided.
544 If the option is not specified, \p %opt::less is used.
545 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
546 - \p opt::disposer - the functor used for dispose removed nodes. Default is \p opt::v::empty_disposer. Due the nature
547 of GC schema the disposer may be called asynchronously. The disposer is used only for leaf nodes.
548 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
549 To enable it use \p atomicity::item_counter
550 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
551 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
552 - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
553 default is \ref CDS_DEFAULT_ALLOCATOR.
554 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
555 The number of simultaneously existing descriptors is bounded and depends on the number of threads
556 working with the tree and GC internals.
557 A bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good candidate
558 for the free-list of update descriptors, see cds::memory::vyukov_queue_pool free-list implementation.
559 Also notice that size of update descriptor is constant and not dependent on the type of data
560 stored in the tree so single free-list object can be used for all \p %EllenBinTree objects.
561 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
562 - \p opt::stat - internal statistics, by default it is disabled (\p ellen_bintree::empty_stat)
563 To enable statistics use \p \p ellen_bintree::stat
564 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
565 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
567 template <typename... Options>
569 # ifdef CDS_DOXYGEN_INVOKED
570 typedef implementation_defined type ; ///< Metafunction result
572 typedef typename cds::opt::make_options<
573 typename cds::opt::find_type_traits< traits, Options... >::type
582 template <typename Key, typename T, typename Compare, typename NodeTraits>
585 typedef Compare key_compare;
586 typedef Key key_type;
587 typedef T value_type;
588 typedef NodeTraits node_traits;
590 template <typename Q1, typename Q2>
591 int operator()( Q1 const& v1, Q2 const& v2) const
593 return key_compare()( v1, v2 );
596 template <typename LeafNode>
597 int operator()( internal_node<key_type, LeafNode> const& n1, internal_node<key_type, LeafNode> const& n2 ) const
599 if ( n1.infinite_key() )
600 return n2.infinite_key() ? n1.infinite_key() - n2.infinite_key() : 1;
601 else if ( n2.infinite_key() )
603 return operator()( n1.m_Key, n2.m_Key );
606 template <typename LeafNode, typename Q>
607 int operator()( internal_node<key_type, LeafNode> const& n, Q const& v ) const
609 if ( n.infinite_key() )
611 return operator()( n.m_Key, v );
614 template <typename LeafNode, typename Q>
615 int operator()( Q const& v, internal_node<key_type, LeafNode> const& n ) const
617 if ( n.infinite_key() )
619 return operator()( v, n.m_Key );
622 template <typename GC, typename Tag>
623 int operator()( node<GC, Tag> const& n1, node<GC, Tag> const& n2 ) const
625 if ( n1.infinite_key() != n2.infinite_key() )
626 return n1.infinite_key() - n2.infinite_key();
627 return operator()( *node_traits::to_value_ptr( n1 ), *node_traits::to_value_ptr( n2 ));
630 template <typename GC, typename Tag, typename Q>
631 int operator()( node<GC, Tag> const& n, Q const& v ) const
633 if ( n.infinite_key() )
635 return operator()( *node_traits::to_value_ptr( n ), v );
638 template <typename GC, typename Tag, typename Q>
639 int operator()( Q const& v, node<GC, Tag> const& n ) const
641 if ( n.infinite_key() )
643 return operator()( v, *node_traits::to_value_ptr( n ) );
646 template <typename GC>
647 int operator()( base_node<GC> const& n1, base_node<GC> const& n2 ) const
649 if ( n1.infinite_key() != n2.infinite_key() )
650 return n1.infinite_key() - n2.infinite_key();
651 if ( n1.is_leaf() ) {
653 return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_leaf_node( n2 ));
655 return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_internal_node( n2 ));
659 return operator()( node_traits::to_internal_node( n1 ), node_traits::to_leaf_node( n2 ));
661 return operator()( node_traits::to_internal_node( n1 ), node_traits::to_internal_node( n2 ));
664 template <typename GC, typename Q>
665 int operator()( base_node<GC> const& n, Q const& v ) const
667 if ( n.infinite_key())
670 return operator()( node_traits::to_leaf_node( n ), v );
671 return operator()( node_traits::to_internal_node( n ), v );
674 template <typename GC, typename Q>
675 int operator()( Q const& v, base_node<GC> const& n ) const
677 return -operator()( n, v );
680 template <typename GC, typename LeafNode >
681 int operator()( base_node<GC> const& i, internal_node<key_type, LeafNode> const& n ) const
684 return operator()( static_cast<LeafNode const&>(i), n );
685 return operator()( static_cast<internal_node<key_type, LeafNode> const&>(i), n );
688 template <typename GC, typename LeafNode >
689 int operator()( internal_node<key_type, LeafNode> const& n, base_node<GC> const& i ) const
691 return -operator()( i, n );
694 template <typename GC, typename Tag >
695 int operator()( node<GC, Tag> const& n, internal_node<key_type, node<GC, Tag> > const& i ) const
697 if ( !n.infinite_key() ) {
698 if ( i.infinite_key() )
700 return operator()( n, i.m_Key );
703 if ( !i.infinite_key())
705 return int( n.infinite_key()) - int( i.infinite_key());
708 template <typename GC, typename Tag >
709 int operator()( internal_node<key_type, node<GC, Tag> > const& i, node<GC, Tag> const& n ) const
711 return -operator()( n, i );
716 } // namespace details
718 } // namespace ellen_bintree
721 template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
724 }} // namespace cds::intrusive
726 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H