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>
11 #include <cds/details/allocator.h>
13 namespace cds { namespace intrusive {
15 /// EllenBinTree related declarations
16 namespace ellen_bintree {
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 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 /// RCU deadlock checking policy (only for \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
523 List of available options see \p opt::rcu_check_deadlock
525 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
528 /// Metafunction converting option list to EllenBinTree traits
531 - \p opt::hook - hook used. Possible values are: \p ellen_bintree::base_hook, \p ellen_bintree::member_hook, \p ellen_bintree::traits_hook.
532 If the option is not specified, <tt>ellen_bintree::base_hook<></tt> is used.
533 - \p ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
535 struct key_extractor {
536 void operator ()( Key& dest, T const& src );
539 It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
540 - \p opt::compare - key compare functor. No default functor is provided.
541 If the option is not specified, \p %opt::less is used.
542 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
543 - \p opt::disposer - the functor used for dispose removed nodes. Default is \p opt::v::empty_disposer. Due the nature
544 of GC schema the disposer may be called asynchronously. The disposer is used only for leaf nodes.
545 - \p opt::item_counter - the type of item counting feature, by defaulr it is disabled (\p atomicity::empty_item_counter)
546 To enable it use \p atomicity::item_counter
547 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
548 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
549 - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
550 default is \ref CDS_DEFAULT_ALLOCATOR.
551 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
552 The number of simultaneously existing descriptors is bounded and depends on the number of threads
553 working with the tree and GC internals.
554 A bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good candidate
555 for the free-list of update descriptors, see cds::memory::vyukov_queue_pool free-list implementation.
556 Also notice that size of update descriptor is constant and not dependent on the type of data
557 stored in the tree so single free-list object can be used for all \p %EllenBinTree objects.
558 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
559 - \p opt::stat - internal statistics, by default it is disabled (\p ellen_bintree::empty_stat)
560 To enable statistics use \p \p ellen_bintree::stat
561 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
563 template <typename... Options>
565 # ifdef CDS_DOXYGEN_INVOKED
566 typedef implementation_defined type ; ///< Metafunction result
568 typedef typename cds::opt::make_options<
569 typename cds::opt::find_type_traits< traits, Options... >::type
578 template <typename Key, typename T, typename Compare, typename NodeTraits>
581 typedef Compare key_compare;
582 typedef Key key_type;
583 typedef T value_type;
584 typedef NodeTraits node_traits;
586 template <typename Q1, typename Q2>
587 int operator()( Q1 const& v1, Q2 const& v2) const
589 return key_compare()( v1, v2 );
592 template <typename LeafNode>
593 int operator()( internal_node<key_type, LeafNode> const& n1, internal_node<key_type, LeafNode> const& n2 ) const
595 if ( n1.infinite_key() )
596 return n2.infinite_key() ? n1.infinite_key() - n2.infinite_key() : 1;
597 else if ( n2.infinite_key() )
599 return operator()( n1.m_Key, n2.m_Key );
602 template <typename LeafNode, typename Q>
603 int operator()( internal_node<key_type, LeafNode> const& n, Q const& v ) const
605 if ( n.infinite_key() )
607 return operator()( n.m_Key, v );
610 template <typename LeafNode, typename Q>
611 int operator()( Q const& v, internal_node<key_type, LeafNode> const& n ) const
613 if ( n.infinite_key() )
615 return operator()( v, n.m_Key );
618 template <typename GC, typename Tag>
619 int operator()( node<GC, Tag> const& n1, node<GC, Tag> const& n2 ) const
621 if ( n1.infinite_key() != n2.infinite_key() )
622 return n1.infinite_key() - n2.infinite_key();
623 return operator()( *node_traits::to_value_ptr( n1 ), *node_traits::to_value_ptr( n2 ));
626 template <typename GC, typename Tag, typename Q>
627 int operator()( node<GC, Tag> const& n, Q const& v ) const
629 if ( n.infinite_key() )
631 return operator()( *node_traits::to_value_ptr( n ), v );
634 template <typename GC, typename Tag, typename Q>
635 int operator()( Q const& v, node<GC, Tag> const& n ) const
637 if ( n.infinite_key() )
639 return operator()( v, *node_traits::to_value_ptr( n ) );
642 template <typename GC>
643 int operator()( base_node<GC> const& n1, base_node<GC> const& n2 ) const
645 if ( n1.infinite_key() != n2.infinite_key() )
646 return n1.infinite_key() - n2.infinite_key();
647 if ( n1.is_leaf() ) {
649 return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_leaf_node( n2 ));
651 return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_internal_node( n2 ));
655 return operator()( node_traits::to_internal_node( n1 ), node_traits::to_leaf_node( n2 ));
657 return operator()( node_traits::to_internal_node( n1 ), node_traits::to_internal_node( n2 ));
660 template <typename GC, typename Q>
661 int operator()( base_node<GC> const& n, Q const& v ) const
663 if ( n.infinite_key())
666 return operator()( node_traits::to_leaf_node( n ), v );
667 return operator()( node_traits::to_internal_node( n ), v );
670 template <typename GC, typename Q>
671 int operator()( Q const& v, base_node<GC> const& n ) const
673 return -operator()( n, v );
676 template <typename GC, typename LeafNode >
677 int operator()( base_node<GC> const& i, internal_node<key_type, LeafNode> const& n ) const
680 return operator()( static_cast<LeafNode const&>(i), n );
681 return operator()( static_cast<internal_node<key_type, LeafNode> const&>(i), n );
684 template <typename GC, typename LeafNode >
685 int operator()( internal_node<key_type, LeafNode> const& n, base_node<GC> const& i ) const
687 return -operator()( i, n );
690 template <typename GC, typename Tag >
691 int operator()( node<GC, Tag> const& n, internal_node<key_type, node<GC, Tag> > const& i ) const
693 if ( !n.infinite_key() ) {
694 if ( i.infinite_key() )
696 return operator()( n, i.m_Key );
699 if ( !i.infinite_key())
701 return int( n.infinite_key()) - int( i.infinite_key());
704 template <typename GC, typename Tag >
705 int operator()( internal_node<key_type, node<GC, Tag> > const& i, node<GC, Tag> const& n ) const
707 return -operator()( n, i );
712 } // namespace details
714 } // namespace ellen_bintree
717 template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
720 }} // namespace cds::intrusive
722 #endif // #ifndef __CDS_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H