2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H
32 #define CDSLIB_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H
34 #include <type_traits>
35 #include <cds/intrusive/details/base.h>
36 #include <cds/opt/options.h>
37 #include <cds/urcu/options.h>
38 #include <cds/details/marked_ptr.h>
40 namespace cds { namespace intrusive {
42 /// EllenBinTree related declarations
43 namespace ellen_bintree {
45 template <class GC> struct base_node;
46 template <class GC, typename Tag = opt::none> struct node;
47 template <class GC, typename Key> struct internal_node;
51 Update descriptor is used internally for helping concurrent threads
52 to complete modifying operation.
53 Usually, you should not use \p update_desc type directly until
54 you want to develop special free-list of update descriptor.
57 - \p LeafNode - leaf node type, see \ref node
58 - \p InternalNode - internal node type, see \ref internal_node
60 @note Size of update descriptor is constant.
61 It does not depends of template arguments.
63 template <typename LeafNode, typename InternalNode>
66 typedef LeafNode leaf_node;
67 typedef InternalNode internal_node;
69 typedef cds::details::marked_ptr< update_desc, 3 > update_ptr;
79 internal_node * pParent;
85 internal_node * pGrandParent;
86 internal_node * pParent;
88 update_desc * pUpdateParent;
89 bool bDisposeLeaf; // true if pLeaf should be disposed, false otherwise (for extract operation, RCU)
99 update_desc * pNextRetire; // for local retired list (RCU)
102 : pNextRetire( nullptr )
111 internal = 1, ///< set for internal node
112 key_infinite1 = 2, ///< set if node's key is Inf1
113 key_infinite2 = 4, ///< set if node's key is Inf2
115 key_infinite = key_infinite1 | key_infinite2 ///< Cumulative infinite flags
118 atomics::atomic<unsigned int> m_nFlags; ///< Internal flags
120 /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
121 explicit basic_node( bool bInternal )
122 : m_nFlags( bInternal ? internal : 0 )
125 /// Checks if the node is a leaf
128 return !is_internal();
131 /// Checks if the node is internal
132 bool is_internal() const
134 return (m_nFlags.load(atomics::memory_order_relaxed) & internal) != 0;
137 /// Returns infinite key, 0 if the node is not infinite
138 unsigned int infinite_key() const
140 return m_nFlags.load(atomics::memory_order_relaxed) & key_infinite;
143 /// Sets infinite key for the node (for internal use only!!!)
144 void infinite_key( int nInf )
146 unsigned int nFlags = m_nFlags.load(atomics::memory_order_relaxed);
147 nFlags &= ~key_infinite;
150 nFlags |= key_infinite1;
153 nFlags |= key_infinite2;
161 m_nFlags.store( nFlags, atomics::memory_order_relaxed );
166 struct base_node: public basic_node
168 typedef basic_node base_class;
170 typedef GC gc ; ///< Garbage collector
171 /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
172 explicit base_node( bool bInternal )
173 : base_class( bInternal )
178 /// Ellen's binary tree leaf node
181 - \p GC - one of \ref cds_garbage_collector "garbage collector type"
182 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
184 template <typename GC,
185 # ifdef CDS_DOXYGEN_INVOKED
186 typename Tag = opt::none
192 # ifndef CDS_DOXYGEN_INVOKED
193 : public base_node< GC >
197 typedef base_node< GC > base_class;
200 typedef GC gc; ///< Garbage collector
201 typedef Tag tag; ///< Tag
205 : base_class( false )
209 /// Ellen's binary tree internal node
213 - \p LeafNode - leaf node type
215 template <typename Key, typename LeafNode>
217 # ifndef CDS_DOXYGEN_INVOKED
218 : public base_node<typename LeafNode::gc>
222 typedef base_node<typename LeafNode::gc> base_class;
225 typedef Key key_type; ///< key type
226 typedef LeafNode leaf_node; ///< type of leaf node
227 typedef update_desc< leaf_node, internal_node > update_desc_type; ///< Update descriptor
228 typedef typename update_desc_type::update_ptr update_ptr; ///< Marked pointer to update descriptor
230 key_type m_Key; ///< Regular key
231 atomics::atomic<base_class *> m_pLeft; ///< Left subtree
232 atomics::atomic<base_class *> m_pRight; ///< Right subtree
233 atomics::atomic<update_ptr> m_pUpdate; ///< Update descriptor
235 uintptr_t m_nEmptyUpdate; ///< ABA prevention for m_pUpdate, from 0..2^16 step 4
242 , m_pRight( nullptr )
243 , m_pUpdate( update_ptr() )
248 update_ptr null_update_desc()
250 return update_ptr( reinterpret_cast<update_desc_type *>( (++m_nEmptyUpdate << 2) & 0xFFFF ) );
253 base_class * get_child( bool bRight, atomics::memory_order mo ) const
255 return bRight ? m_pRight.load( mo ) : m_pLeft.load( mo );
260 /// Types of EllenBinTree node
262 This struct declares different \p %EllenBinTree node types.
263 It can be useful for simplifying \p %EllenBinTree node declaration in your application.
266 - \p GC - one of \ref cds_garbage_collector "garbage collector type"
268 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
270 template <typename GC, typename Key, typename Tag = opt::none>
273 typedef node<GC, Tag> leaf_node_type; ///< Leaf node type
274 typedef internal_node<Key, leaf_node_type> internal_node_type; ///< Internal node type
275 typedef update_desc<leaf_node_type, internal_node_type> update_desc_type; ///< Update descriptor type
280 struct default_hook {
281 typedef undefined_gc gc;
282 typedef opt::none tag;
287 template < typename HookType, typename... Options>
290 typedef typename opt::make_options< default_hook, Options...>::type options;
291 typedef typename options::gc gc;
292 typedef typename options::tag tag;
293 typedef node<gc, tag> node_type;
294 typedef HookType hook_type;
301 - \p opt::gc - garbage collector
302 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
304 template < typename... Options >
305 struct base_hook: public hook< opt::base_hook_tag, Options... >
310 \p MemberOffset defines offset in bytes of \ref node member into your structure.
311 Use \p offsetof macro to define \p MemberOffset
314 - \p opt::gc - garbage collector
315 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
317 template < size_t MemberOffset, typename... Options >
318 struct member_hook: public hook< opt::member_hook_tag, Options... >
321 static CDS_CONSTEXPR const size_t c_nMemberOffset = MemberOffset;
327 \p NodeTraits defines type traits for node.
328 See \ref node_traits for \p NodeTraits interface description
331 - opt::gc - garbage collector
332 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
334 template <typename NodeTraits, typename... Options >
335 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
338 typedef NodeTraits node_traits;
342 /// Key extracting functor option setter
343 template <typename Type>
344 struct key_extractor {
346 template <typename Base> struct pack: public Base
348 typedef Type key_extractor;
353 /// Update descriptor allocator option setter
354 template <typename Type>
355 struct update_desc_allocator {
357 template <typename Base> struct pack: public Base
359 typedef Type update_desc_allocator;
364 /// EllenBinTree internal statistics
365 template <typename Counter = cds::atomicity::event_counter>
367 typedef Counter event_counter ; ///< Event counter type
369 event_counter m_nInternalNodeCreated ; ///< Total count of created internal node
370 event_counter m_nInternalNodeDeleted ; ///< Total count of deleted internal node
371 event_counter m_nUpdateDescCreated ; ///< Total count of created update descriptors
372 event_counter m_nUpdateDescDeleted ; ///< Total count of deleted update descriptors
374 event_counter m_nInsertSuccess ; ///< Count of success insertion
375 event_counter m_nInsertFailed ; ///< Count of failed insertion
376 event_counter m_nInsertRetries ; ///< Count of unsuccessful retries of insertion
377 event_counter m_nUpdateExist ; ///< Count of \p update() call for existed node
378 event_counter m_nUpdateNew ; ///< Count of \p update() call for new node
379 event_counter m_nUpdateRetries ; ///< Count of unsuccessful retries of ensuring
380 event_counter m_nEraseSuccess ; ///< Count of successful call of \p erase and \p unlink
381 event_counter m_nEraseFailed ; ///< Count of failed call of \p erase and \p unlink
382 event_counter m_nEraseRetries ; ///< Count of unsuccessful retries inside erasing/unlinking
383 event_counter m_nFindSuccess ; ///< Count of successful \p find call
384 event_counter m_nFindFailed ; ///< Count of failed \p find call
385 event_counter m_nExtractMinSuccess ; ///< Count of successful call of \p extract_min
386 event_counter m_nExtractMinFailed ; ///< Count of failed call of \p extract_min
387 event_counter m_nExtractMinRetries ; ///< Count of unsuccessful retries inside \p extract_min
388 event_counter m_nExtractMaxSuccess ; ///< Count of successful call of \p extract_max
389 event_counter m_nExtractMaxFailed ; ///< Count of failed call of \p extract_max
390 event_counter m_nExtractMaxRetries ; ///< Count of unsuccessful retries inside \p extract_max
391 event_counter m_nSearchRetry ; ///< How many times the deleting node was encountered while searching
393 event_counter m_nHelpInsert ; ///< The number of insert help from the other thread
394 event_counter m_nHelpDelete ; ///< The number of delete help from the other thread
395 event_counter m_nHelpMark ; ///< The number of delete help (mark phase) from the other thread
396 event_counter m_nHelpGuardSuccess ; ///< The number of successful guarding of update descriptor data
397 event_counter m_nHelpGuardFailed ; ///< The number of failed guarding of update descriptor data
400 void onInternalNodeCreated() { ++m_nInternalNodeCreated ; }
401 void onInternalNodeDeleted() { ++m_nInternalNodeDeleted ; }
402 void onUpdateDescCreated() { ++m_nUpdateDescCreated ; }
403 void onUpdateDescDeleted() { ++m_nUpdateDescDeleted ; }
404 void onInsertSuccess() { ++m_nInsertSuccess ; }
405 void onInsertFailed() { ++m_nInsertFailed ; }
406 void onInsertRetry() { ++m_nInsertRetries ; }
407 void onUpdateExist() { ++m_nUpdateExist ; }
408 void onUpdateNew() { ++m_nUpdateNew ; }
409 void onUpdateRetry() { ++m_nUpdateRetries ; }
410 void onEraseSuccess() { ++m_nEraseSuccess ; }
411 void onEraseFailed() { ++m_nEraseFailed ; }
412 void onEraseRetry() { ++m_nEraseRetries ; }
413 void onExtractMinSuccess() { ++m_nExtractMinSuccess ; }
414 void onExtractMinFailed() { ++m_nExtractMinFailed ; }
415 void onExtractMinRetry() { ++m_nExtractMinRetries ; }
416 void onExtractMaxSuccess() { ++m_nExtractMaxSuccess ; }
417 void onExtractMaxFailed() { ++m_nExtractMaxFailed ; }
418 void onExtractMaxRetry() { ++m_nExtractMaxRetries ; }
419 void onFindSuccess() { ++m_nFindSuccess ; }
420 void onFindFailed() { ++m_nFindFailed ; }
421 void onSearchRetry() { ++m_nSearchRetry ; }
422 void onHelpInsert() { ++m_nHelpInsert ; }
423 void onHelpDelete() { ++m_nHelpDelete ; }
424 void onHelpMark() { ++m_nHelpMark ; }
425 void onHelpGuardSuccess() { ++m_nHelpGuardSuccess ; }
426 void onHelpGuardFailed() { ++m_nHelpGuardFailed ; }
430 /// EllenBinTree empty statistics
433 void onInternalNodeCreated() const {}
434 void onInternalNodeDeleted() const {}
435 void onUpdateDescCreated() const {}
436 void onUpdateDescDeleted() const {}
437 void onInsertSuccess() const {}
438 void onInsertFailed() const {}
439 void onInsertRetry() const {}
440 void onUpdateExist() const {}
441 void onUpdateNew() const {}
442 void onUpdateRetry() const {}
443 void onEraseSuccess() const {}
444 void onEraseFailed() const {}
445 void onEraseRetry() const {}
446 void onExtractMinSuccess() const {}
447 void onExtractMinFailed() const {}
448 void onExtractMinRetry() const {}
449 void onExtractMaxSuccess() const {}
450 void onExtractMaxFailed() const {}
451 void onExtractMaxRetry() const {}
452 void onFindSuccess() const {}
453 void onFindFailed() const {}
454 void onSearchRetry() const {}
455 void onHelpInsert() const {}
456 void onHelpDelete() const {}
457 void onHelpMark() const {}
458 void onHelpGuardSuccess() const {}
459 void onHelpGuardFailed() const {}
463 /// EllenBinTree traits
466 /// Hook used (mandatory)
468 Possible values are: \p ellen_bintree::base_hook, \p ellen_bintree::member_hook, \p ellen_bintree::traits_hook.
470 typedef base_hook<> hook;
472 /// Key extracting functor (mandatory)
474 You should explicit define a valid functor.
475 The functor has the following prototype:
477 struct key_extractor {
478 void operator ()( Key& dest, T const& src );
481 It should initialize \p dest key from \p src data.
482 The functor is used to initialize internal nodes.
484 typedef opt::none key_extractor;
486 /// Key comparison functor
488 No default functor is provided. If the option is not specified, the \p less is used.
490 See \p cds::opt::compare option description for functor interface.
492 You should provide \p compare or \p less functor.
493 See \ref cds_intrusive_EllenBinTree_rcu_less "predicate requirements".
495 typedef opt::none compare;
497 /// Specifies binary predicate used for key compare.
499 See \p cds::opt::less option description for predicate interface.
501 You should provide \p compare or \p less functor.
502 See \ref cds_intrusive_EllenBinTree_rcu_less "predicate requirements".
504 typedef opt::none less;
508 The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
510 typedef opt::v::empty_disposer disposer;
514 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
515 To enable it use \p atomicity::item_counter
517 typedef atomicity::empty_item_counter item_counter;
519 /// C++ memory ordering model
521 List of available memory ordering see \p opt::memory_model
523 typedef opt::v::relaxed_ordering memory_model;
525 /// Allocator for update descriptors
527 The allocator type is used for \p ellen_bintree::update_desc.
529 Update descriptor is helping data structure with short lifetime and it is good candidate
530 for pooling. The number of simultaneously existing descriptors is bounded and it is
531 limited the number of threads working with the tree.
532 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue
533 is good choice for the free-list of update descriptors,
534 see \p cds::memory::vyukov_queue_pool free-list implementation.
536 Also notice that size of update descriptor is constant and not dependent on the type of data
537 stored in the tree so single free-list object can be used for several \p EllenBinTree object.
539 typedef CDS_DEFAULT_ALLOCATOR update_desc_allocator;
541 /// Allocator for internal nodes
543 The allocator type is used for \p ellen_bintree::internal_node.
545 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
547 /// Internal statistics
549 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
550 To enable it use \p ellen_bintree::stat.
552 typedef empty_stat stat;
554 /// Back-off strategy
555 typedef cds::backoff::empty back_off;
557 /// RCU deadlock checking policy (only for \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
559 List of available options see \p opt::rcu_check_deadlock
561 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
564 /// Metafunction converting option list to EllenBinTree traits
567 - \p opt::hook - hook used. Possible values are: \p ellen_bintree::base_hook, \p ellen_bintree::member_hook, \p ellen_bintree::traits_hook.
568 If the option is not specified, <tt>ellen_bintree::base_hook<></tt> is used.
569 - \p ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
571 struct key_extractor {
572 void operator ()( Key& dest, T const& src );
575 It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
576 - \p opt::compare - key compare functor. No default functor is provided.
577 If the option is not specified, \p %opt::less is used.
578 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
579 - \p opt::disposer - the functor used for dispose removed nodes. Default is \p opt::v::empty_disposer. Due the nature
580 of GC schema the disposer may be called asynchronously. The disposer is used only for leaf nodes.
581 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
582 To enable it use \p atomicity::item_counter
583 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
584 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
585 - \p ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
586 default is \ref CDS_DEFAULT_ALLOCATOR.
587 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
588 The number of simultaneously existing descriptors is bounded and depends on the number of threads
589 working with the tree and GC internals.
590 A bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good candidate
591 for the free-list of update descriptors, see cds::memory::vyukov_queue_pool free-list implementation.
592 Also notice that size of update descriptor is constant and not dependent on the type of data
593 stored in the tree so single free-list object can be used for all \p %EllenBinTree objects.
594 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
595 - \p opt::stat - internal statistics, by default it is disabled (\p ellen_bintree::empty_stat)
596 To enable statistics use \p \p ellen_bintree::stat
597 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
598 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
600 template <typename... Options>
602 # ifdef CDS_DOXYGEN_INVOKED
603 typedef implementation_defined type ; ///< Metafunction result
605 typedef typename cds::opt::make_options<
606 typename cds::opt::find_type_traits< traits, Options... >::type
615 template <typename Key, typename T, typename Compare, typename NodeTraits>
618 typedef Compare key_compare;
619 typedef Key key_type;
620 typedef T value_type;
621 typedef NodeTraits node_traits;
623 template <typename Q1, typename Q2>
624 int operator()( Q1 const& v1, Q2 const& v2) const
626 return key_compare()( v1, v2 );
629 template <typename LeafNode>
630 int operator()( internal_node<key_type, LeafNode> const& n1, internal_node<key_type, LeafNode> const& n2 ) const
632 if ( n1.infinite_key() )
633 return n2.infinite_key() ? n1.infinite_key() - n2.infinite_key() : 1;
634 else if ( n2.infinite_key() )
636 return operator()( n1.m_Key, n2.m_Key );
639 template <typename LeafNode, typename Q>
640 int operator()( internal_node<key_type, LeafNode> const& n, Q const& v ) const
642 if ( n.infinite_key() )
644 return operator()( n.m_Key, v );
647 template <typename LeafNode, typename Q>
648 int operator()( Q const& v, internal_node<key_type, LeafNode> const& n ) const
650 if ( n.infinite_key() )
652 return operator()( v, n.m_Key );
655 template <typename GC, typename Tag>
656 int operator()( node<GC, Tag> const& n1, node<GC, Tag> const& n2 ) const
658 if ( n1.infinite_key() != n2.infinite_key() )
659 return n1.infinite_key() - n2.infinite_key();
660 return operator()( *node_traits::to_value_ptr( n1 ), *node_traits::to_value_ptr( n2 ));
663 template <typename GC, typename Tag, typename Q>
664 int operator()( node<GC, Tag> const& n, Q const& v ) const
666 if ( n.infinite_key() )
668 return operator()( *node_traits::to_value_ptr( n ), v );
671 template <typename GC, typename Tag, typename Q>
672 int operator()( Q const& v, node<GC, Tag> const& n ) const
674 if ( n.infinite_key() )
676 return operator()( v, *node_traits::to_value_ptr( n ) );
679 template <typename GC>
680 int operator()( base_node<GC> const& n1, base_node<GC> const& n2 ) const
682 if ( n1.infinite_key() != n2.infinite_key() )
683 return n1.infinite_key() - n2.infinite_key();
684 if ( n1.is_leaf() ) {
686 return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_leaf_node( n2 ));
688 return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_internal_node( n2 ));
692 return operator()( node_traits::to_internal_node( n1 ), node_traits::to_leaf_node( n2 ));
694 return operator()( node_traits::to_internal_node( n1 ), node_traits::to_internal_node( n2 ));
697 template <typename GC, typename Q>
698 int operator()( base_node<GC> const& n, Q const& v ) const
700 if ( n.infinite_key())
703 return operator()( node_traits::to_leaf_node( n ), v );
704 return operator()( node_traits::to_internal_node( n ), v );
707 template <typename GC, typename Q>
708 int operator()( Q const& v, base_node<GC> const& n ) const
710 return -operator()( n, v );
713 template <typename GC, typename LeafNode >
714 int operator()( base_node<GC> const& i, internal_node<key_type, LeafNode> const& n ) const
717 return operator()( static_cast<LeafNode const&>(i), n );
718 return operator()( static_cast<internal_node<key_type, LeafNode> const&>(i), n );
721 template <typename GC, typename LeafNode >
722 int operator()( internal_node<key_type, LeafNode> const& n, base_node<GC> const& i ) const
724 return -operator()( i, n );
727 template <typename GC, typename Tag >
728 int operator()( node<GC, Tag> const& n, internal_node<key_type, node<GC, Tag> > const& i ) const
730 if ( !n.infinite_key() ) {
731 if ( i.infinite_key() )
733 return operator()( n, i.m_Key );
736 if ( !i.infinite_key())
738 return int( n.infinite_key()) - int( i.infinite_key());
741 template <typename GC, typename Tag >
742 int operator()( internal_node<key_type, node<GC, Tag> > const& i, node<GC, Tag> const& n ) const
744 return -operator()( n, i );
749 } // namespace details
751 } // namespace ellen_bintree
754 template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
757 }} // namespace cds::intrusive
759 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H