LazyList refactoring
[libcds.git] / cds / intrusive / details / ellen_bintree_base.h
1 //$$CDS-header$$
2
3 #ifndef __CDS_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H
4 #define __CDS_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H
5
6 #include <type_traits>
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>
12
13 namespace cds { namespace intrusive {
14
15     /// EllenBinTree related declarations
16     namespace ellen_bintree {
17
18         //Forwards
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;
22
23         /// Update descriptor
24         /**
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.
29
30             Template parameters:
31             - \p LeafNode - leaf node type, see \ref node
32             - \p InternalNode - internal node type, see \ref internal_node
33
34             @note Size of update descriptor is constant.
35             It does not depends of template arguments.
36         */
37         template <typename LeafNode, typename InternalNode>
38         struct update_desc {
39             //@cond
40             typedef LeafNode        leaf_node;
41             typedef InternalNode    internal_node;
42
43             typedef cds::details::marked_ptr< update_desc, 3 > update_ptr;
44
45             enum {
46                 Clean = 0,
47                 DFlag = 1,
48                 IFlag = 2,
49                 Mark  = 3
50             };
51
52             struct insert_info {
53                 internal_node *    pParent;
54                 internal_node *    pNew;
55                 leaf_node *        pLeaf;
56                 bool               bRightLeaf;
57             };
58             struct delete_info {
59                 internal_node *    pGrandParent;
60                 internal_node *    pParent;
61                 leaf_node *        pLeaf;
62                 update_desc *      pUpdateParent;
63                 bool               bDisposeLeaf; // true if pLeaf should be disposed, false otherwise (for extract operation, RCU)
64                 bool               bRightParent;
65                 bool               bRightLeaf;
66             };
67
68             union {
69                 insert_info     iInfo;
70                 delete_info     dInfo;
71             };
72
73             update_desc *   pNextRetire     ;   // for local retired list (RCU)
74
75             update_desc()
76                 : pNextRetire( nullptr )
77             {}
78             //@endcond
79         };
80
81         //@cond
82         struct basic_node
83         {
84             enum flags {
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
88
89                 key_infinite = key_infinite1 | key_infinite2    ///< Cumulative infinite flags
90             };
91
92             unsigned int    m_nFlags    ;   ///< Internal flags
93
94             /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
95             explicit basic_node( bool bInternal )
96                 : m_nFlags( bInternal ? internal : 0 )
97             {}
98
99             /// Checks if the node is a leaf
100             bool is_leaf() const
101             {
102                 return !is_internal();
103             }
104
105             /// Checks if the node is internal
106             bool is_internal() const
107             {
108                 return (m_nFlags & internal) != 0;
109             }
110
111             /// Returns infinite key, 0 if the node is not infinite
112             unsigned int infinite_key() const
113             {
114                 return m_nFlags & key_infinite;
115             }
116
117             /// Sets infinite key for the node (for internal use only!!!)
118             void infinite_key( int nInf )
119             {
120                 m_nFlags &= ~key_infinite;
121                 switch ( nInf ) {
122                 case 1:
123                     m_nFlags |= key_infinite1;
124                     break;
125                 case 2:
126                     m_nFlags |= key_infinite2;
127                     break;
128                 case 0:
129                     break;
130                 default:
131                     assert( false );
132                     break;
133                 }
134             }
135         };
136
137         template <class GC>
138         struct base_node: public basic_node
139         {
140             typedef basic_node base_class;
141
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 )
146             {}
147         };
148         //@endcond
149
150         /// Ellen's binary tree leaf node
151         /**
152             Template parameters:
153             - \p GC - one of \ref cds_garbage_collector "garbage collector type"
154             - \p Tag - a tag used to distinguish between different implementation. An incomplete type may be used as a tag.
155         */
156         template <typename GC,
157 #   ifdef CDS_DOXYGEN_INVOKED
158             typename Tag = opt::none
159 #   else
160             typename Tag
161 #   endif
162         >
163         struct node
164 #   ifndef CDS_DOXYGEN_INVOKED
165             : public base_node< GC >
166 #   endif
167         {
168             //@cond
169             typedef base_node< GC >   base_class;
170             //@endcond
171
172             typedef GC              gc       ;   ///< Garbage collector type
173             typedef Tag             tag      ;   ///< Tag
174
175             /// Default ctor
176             node()
177                 : base_class( false )
178             {}
179         };
180
181         /// Ellen's binary tree internal node
182         /**
183             Template arguments:
184             - \p Key - key type
185             - \p LeafNode - leaf node type
186         */
187         template <typename Key, typename LeafNode>
188         struct internal_node
189 #   ifndef CDS_DOXYGEN_INVOKED
190             : public base_node<typename LeafNode::gc>
191 #   endif
192         {
193             //@cond
194             typedef base_node<typename LeafNode::gc>   base_class;
195             //@endcond
196
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
201
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
206             //@cond
207             uintptr_t                           m_nEmptyUpdate; ///< ABA prevention for m_pUpdate, from 0..2^16 step 4
208             //@endcond
209
210             /// Default ctor
211             internal_node()
212                 : base_class( true )
213                 , m_pLeft( nullptr )
214                 , m_pRight( nullptr )
215                 , m_pUpdate( update_ptr() )
216                 , m_nEmptyUpdate(0)
217             {}
218
219             //@cond
220             update_ptr null_update_desc()
221             {
222                 return update_ptr( reinterpret_cast<update_desc_type *>( (++m_nEmptyUpdate << 2) & 0xFFFF ) );
223             }
224             //@endcond
225         };
226
227         /// Types of EllenBinTree node
228         /**
229             This struct declares different \p %EllenBinTree node types.
230             It can be useful for simplifying \p %EllenBinTree node declaration in your application.
231         */
232         template <typename GC, typename Key, typename Tag = opt::none>
233         struct node_types
234         {
235             typedef node<GC, Tag>                       leaf_node_type      ;   ///< Leaf node type
236             typedef internal_node<Key, leaf_node_type>  internal_node_type  ;   ///< Internal node type
237             typedef update_desc<leaf_node_type, internal_node_type> update_desc_type ;  ///< Update descriptor type
238         };
239
240         //@cond
241         struct undefined_gc;
242         struct default_hook {
243             typedef undefined_gc    gc;
244             typedef opt::none       tag;
245         };
246         //@endcond
247
248         //@cond
249         template < typename HookType, typename... Options>
250         struct hook
251         {
252             typedef typename opt::make_options< default_hook, Options...>::type  options;
253             typedef typename options::gc    gc;
254             typedef typename options::tag   tag;
255             typedef node<gc, tag>           node_type;
256             typedef HookType                hook_type;
257         };
258         //@endcond
259
260         /// Base hook
261         /**
262             \p Options are:
263             - opt::gc - garbage collector used.
264             - opt::tag - a tag
265         */
266         template < typename... Options >
267         struct base_hook: public hook< opt::base_hook_tag, Options... >
268         {};
269
270         /// Member hook
271         /**
272             \p MemberOffset defines offset in bytes of \ref node member into your structure.
273             Use \p offsetof macro to define \p MemberOffset
274
275             \p Options are:
276             - opt::gc - garbage collector used.
277             - opt::tag - a tag
278         */
279         template < size_t MemberOffset, typename... Options >
280         struct member_hook: public hook< opt::member_hook_tag, Options... >
281         {
282             //@cond
283             static const size_t c_nMemberOffset = MemberOffset;
284             //@endcond
285         };
286
287         /// Traits hook
288         /**
289             \p NodeTraits defines type traits for node.
290             See \ref node_traits for \p NodeTraits interface description
291
292             \p Options are:
293             - opt::gc - garbage collector used.
294             - opt::tag - a tag
295         */
296         template <typename NodeTraits, typename... Options >
297         struct traits_hook: public hook< opt::traits_hook_tag, Options... >
298         {
299             //@cond
300             typedef NodeTraits node_traits;
301             //@endcond
302         };
303
304         /// Key extracting functor option setter
305         template <typename Type>
306         struct key_extractor {
307             //@cond
308             template <typename Base> struct pack: public Base
309             {
310                 typedef Type key_extractor;
311             };
312             //@endcond
313         };
314
315         /// Update descriptor allocator option setter
316         template <typename Type>
317         struct update_desc_allocator {
318             //@cond
319             template <typename Base> struct pack: public Base
320             {
321                 typedef Type update_desc_allocator;
322             };
323             //@endcond
324         };
325
326         /// EllenBinTree internal statistics
327         template <typename Counter = cds::atomicity::event_counter>
328         struct stat {
329             typedef Counter   event_counter ; ///< Event counter type
330
331             event_counter   m_nInternalNodeCreated  ;   ///< Total count of created internal node
332             event_counter   m_nInternalNodeDeleted  ;   ///< Total count of deleted internal node
333             event_counter   m_nUpdateDescCreated    ;   ///< Total count of created update descriptors
334             event_counter   m_nUpdateDescDeleted    ;   ///< Total count of deleted update descriptors
335
336             event_counter   m_nInsertSuccess        ; ///< Count of success insertion
337             event_counter   m_nInsertFailed         ; ///< Count of failed insertion
338             event_counter   m_nInsertRetries        ; ///< Count of unsuccessful retries of insertion
339             event_counter   m_nEnsureExist          ; ///< Count of \p ensure call for existed node
340             event_counter   m_nEnsureNew            ; ///< Count of \p ensure call for new node
341             event_counter   m_nEnsureRetries        ; ///< Count of unsuccessful retries of ensuring
342             event_counter   m_nEraseSuccess         ; ///< Count of successful call of \p erase and \p unlink
343             event_counter   m_nEraseFailed          ; ///< Count of failed call of \p erase and \p unlink
344             event_counter   m_nEraseRetries         ; ///< Count of unsuccessful retries inside erasing/unlinking
345             event_counter   m_nFindSuccess          ; ///< Count of successful \p find call
346             event_counter   m_nFindFailed           ; ///< Count of failed \p find call
347             event_counter   m_nExtractMinSuccess    ; ///< Count of successful call of \p extract_min
348             event_counter   m_nExtractMinFailed     ; ///< Count of failed call of \p extract_min
349             event_counter   m_nExtractMinRetries    ; ///< Count of unsuccessful retries inside \p extract_min
350             event_counter   m_nExtractMaxSuccess    ; ///< Count of successful call of \p extract_max
351             event_counter   m_nExtractMaxFailed     ; ///< Count of failed call of \p extract_max
352             event_counter   m_nExtractMaxRetries    ; ///< Count of unsuccessful retries inside \p extract_max
353             event_counter   m_nSearchRetry          ; ///< How many times the deleting node was encountered while searching
354
355             event_counter   m_nHelpInsert           ; ///< The number of insert help from the other thread
356             event_counter   m_nHelpDelete           ; ///< The number of delete help from the other thread
357             event_counter   m_nHelpMark             ; ///< The number of delete help (mark phase) from the other thread
358             event_counter   m_nHelpGuardSuccess     ; ///< The number of successful guarding of update descriptor data
359             event_counter   m_nHelpGuardFailed      ; ///< The number of failed guarding of update descriptor data
360
361             //@cond
362             void    onInternalNodeCreated()         { ++m_nInternalNodeCreated  ; }
363             void    onInternalNodeDeleted()         { ++m_nInternalNodeDeleted  ; }
364             void    onUpdateDescCreated()           { ++m_nUpdateDescCreated    ; }
365             void    onUpdateDescDeleted()           { ++m_nUpdateDescDeleted    ; }
366             void    onInsertSuccess()               { ++m_nInsertSuccess        ; }
367             void    onInsertFailed()                { ++m_nInsertFailed         ; }
368             void    onInsertRetry()                 { ++m_nInsertRetries        ; }
369             void    onEnsureExist()                 { ++m_nEnsureExist          ; }
370             void    onEnsureNew()                   { ++m_nEnsureNew            ; }
371             void    onEnsureRetry()                 { ++m_nEnsureRetries        ; }
372             void    onEraseSuccess()                { ++m_nEraseSuccess         ; }
373             void    onEraseFailed()                 { ++m_nEraseFailed          ; }
374             void    onEraseRetry()                  { ++m_nEraseRetries         ; }
375             void    onExtractMinSuccess()           { ++m_nExtractMinSuccess    ; }
376             void    onExtractMinFailed()            { ++m_nExtractMinFailed     ; }
377             void    onExtractMinRetry()             { ++m_nExtractMinRetries    ; }
378             void    onExtractMaxSuccess()           { ++m_nExtractMaxSuccess    ; }
379             void    onExtractMaxFailed()            { ++m_nExtractMaxFailed     ; }
380             void    onExtractMaxRetry()             { ++m_nExtractMaxRetries    ; }
381             void    onFindSuccess()                 { ++m_nFindSuccess          ; }
382             void    onFindFailed()                  { ++m_nFindFailed           ; }
383             void    onSearchRetry()                 { ++m_nSearchRetry          ; }
384             void    onHelpInsert()                  { ++m_nHelpInsert           ; }
385             void    onHelpDelete()                  { ++m_nHelpDelete           ; }
386             void    onHelpMark()                    { ++m_nHelpMark             ; }
387             void    onHelpGuardSuccess()            { ++m_nHelpGuardSuccess     ; }
388             void    onHelpGuardFailed()             { ++m_nHelpGuardFailed      ; }
389             //@endcond
390         };
391
392         /// EllenBinTree empty statistics
393         struct empty_stat {
394             //@cond
395             void    onInternalNodeCreated()         {}
396             void    onInternalNodeDeleted()         {}
397             void    onUpdateDescCreated()           {}
398             void    onUpdateDescDeleted()           {}
399             void    onInsertSuccess()               {}
400             void    onInsertFailed()                {}
401             void    onInsertRetry()                 {}
402             void    onEnsureExist()                 {}
403             void    onEnsureNew()                   {}
404             void    onEnsureRetry()                 {}
405             void    onEraseSuccess()                {}
406             void    onEraseFailed()                 {}
407             void    onEraseRetry()                  {}
408             void    onExtractMinSuccess()           {}
409             void    onExtractMinFailed()            {}
410             void    onExtractMinRetry()             {}
411             void    onExtractMaxSuccess()           {}
412             void    onExtractMaxFailed()            {}
413             void    onExtractMaxRetry()             {}
414             void    onFindSuccess()                 {}
415             void    onFindFailed()                  {}
416             void    onSearchRetry()                 {}
417             void    onHelpInsert()                  {}
418             void    onHelpDelete()                  {}
419             void    onHelpMark()                    {}
420             void    onHelpGuardSuccess()            {}
421             void    onHelpGuardFailed()             {}
422             //@endcond
423         };
424
425         /// Type traits for EllenBinTree class
426         struct type_traits
427         {
428             /// Hook used
429             /**
430                 Possible values are: ellen_bintree::base_hook, ellen_bintree::member_hook, ellen_bintree::traits_hook.
431             */
432             typedef base_hook<>       hook;
433
434             /// Key extracting functor
435             /**
436                 You should explicit define a valid functor.
437                 The functor has the following prototype:
438                 \code
439                 struct key_extractor {
440                     void operator ()( Key& dest, T const& src );
441                 };
442                 \endcode
443                 It should initialize \p dest key from \p src data.
444                 The functor is used to initialize internal nodes.
445             */
446             typedef opt::none           key_extractor;
447
448             /// Key comparison functor
449             /**
450                 No default functor is provided. If the option is not specified, the \p less is used.
451
452                 See cds::opt::compare option description for functor interface.
453
454                 You should provide \p compare or \p less functor.
455                 See \ref cds_intrusive_EllenBinTree_rcu_less "predicate requirements".
456             */
457             typedef opt::none                       compare;
458
459             /// Specifies binary predicate used for key compare.
460             /**
461                 See cds::opt::less option description for predicate interface.
462
463                 You should provide \p compare or \p less functor.
464                 See \ref cds_intrusive_EllenBinTree_rcu_less "predicate requirements".
465             */
466             typedef opt::none                       less;
467
468             /// Disposer
469             /**
470                 The functor used for dispose removed items. Default is opt::v::empty_disposer.
471             */
472             typedef opt::v::empty_disposer          disposer;
473
474             /// Item counter
475             /**
476                 The type for item counting feature (see cds::opt::item_counter).
477                 Default is no item counter (\ref atomicity::empty_item_counter)
478             */
479             typedef atomicity::empty_item_counter     item_counter;
480
481             /// C++ memory ordering model
482             /**
483                 List of available memory ordering see opt::memory_model
484             */
485             typedef opt::v::relaxed_ordering        memory_model;
486
487             /// Allocator for update descriptors
488             /**
489                 The allocator type is used for \ref update_desc.
490
491                 Update descriptor is helping data structure with short lifetime and it is good candidate
492                 for pooling. The number of simultaneously existing descriptors is bounded number
493                 limited the number of threads working with the tree.
494                 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue
495                 is good choice for the free-list of update descriptors,
496                 see cds::memory::vyukov_queue_pool free-list implementation.
497
498                 Also notice that size of update descriptor is constant and not dependent on the type of data
499                 stored in the tree so single free-list object can be used for several \p EllenBinTree object.
500             */
501             typedef CDS_DEFAULT_ALLOCATOR           update_desc_allocator;
502
503             /// Allocator for internal nodes
504             /**
505                 The allocator type is used for \ref internal_node.
506             */
507             typedef CDS_DEFAULT_ALLOCATOR           node_allocator;
508
509             /// Internal statistics
510             /**
511                 Possible types: \p ellen_bintree::empty_stat (the default), \p ellen_bintree::stat or any
512                 other with interface like \p %stat.
513             */
514             typedef empty_stat                      stat;
515
516             /// RCU deadlock checking policy (only for \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
517             /**
518                 List of available options see opt::rcu_check_deadlock
519             */
520             typedef cds::opt::v::rcu_throw_deadlock      rcu_check_deadlock;
521         };
522
523         /// Metafunction converting option list to EllenBinTree traits
524         /**
525             This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
526             \p Options list see \ref EllenBinTree.
527         */
528         template <typename... Options>
529         struct make_traits {
530 #   ifdef CDS_DOXYGEN_INVOKED
531             typedef implementation_defined type ;   ///< Metafunction result
532 #   else
533             typedef typename cds::opt::make_options<
534                 typename cds::opt::find_type_traits< type_traits, Options... >::type
535                 ,Options...
536             >::type   type;
537 #   endif
538         };
539
540         //@cond
541         namespace details {
542
543             template <typename Key, typename T, typename Compare, typename NodeTraits>
544             struct compare
545             {
546                 typedef Compare     key_compare;
547                 typedef Key         key_type;
548                 typedef T           value_type;
549                 typedef NodeTraits  node_traits;
550
551                 template <typename Q1, typename Q2>
552                 int operator()( Q1 const& v1, Q2 const& v2) const
553                 {
554                     return key_compare()( v1, v2 );
555                 }
556
557                 template <typename LeafNode>
558                 int operator()( internal_node<key_type, LeafNode> const& n1, internal_node<key_type, LeafNode> const& n2 ) const
559                 {
560                     if ( n1.infinite_key() )
561                         return n2.infinite_key() ? n1.infinite_key() - n2.infinite_key() : 1;
562                     else if ( n2.infinite_key() )
563                         return -1;
564                     return operator()( n1.m_Key, n2.m_Key );
565                 }
566
567                 template <typename LeafNode, typename Q>
568                 int operator()( internal_node<key_type, LeafNode> const& n, Q const& v ) const
569                 {
570                     if ( n.infinite_key() )
571                         return 1;
572                     return operator()( n.m_Key, v );
573                 }
574
575                 template <typename LeafNode, typename Q>
576                 int operator()( Q const& v, internal_node<key_type, LeafNode> const& n ) const
577                 {
578                     if ( n.infinite_key() )
579                         return -1;
580                     return operator()( v, n.m_Key );
581                 }
582
583                 template <typename GC, typename Tag>
584                 int operator()( node<GC, Tag> const& n1, node<GC, Tag> const& n2 ) const
585                 {
586                     if ( n1.infinite_key() != n2.infinite_key() )
587                         return n1.infinite_key() - n2.infinite_key();
588                     return operator()( *node_traits::to_value_ptr( n1 ), *node_traits::to_value_ptr( n2 ));
589                 }
590
591                 template <typename GC, typename Tag, typename Q>
592                 int operator()( node<GC, Tag> const& n, Q const& v ) const
593                 {
594                     if ( n.infinite_key() )
595                         return 1;
596                     return operator()( *node_traits::to_value_ptr( n ), v );
597                 }
598
599                 template <typename GC, typename Tag, typename Q>
600                 int operator()( Q const& v, node<GC, Tag> const& n ) const
601                 {
602                     if ( n.infinite_key() )
603                         return -1;
604                     return operator()( v, *node_traits::to_value_ptr( n ) );
605                 }
606
607                 template <typename GC>
608                 int operator()( base_node<GC> const& n1, base_node<GC> const& n2 ) const
609                 {
610                     if ( n1.infinite_key() != n2.infinite_key() )
611                         return n1.infinite_key() - n2.infinite_key();
612                     if ( n1.is_leaf() ) {
613                         if ( n2.is_leaf() )
614                             return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_leaf_node( n2 ));
615                         else
616                             return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_internal_node( n2 ));
617                     }
618
619                     if ( n2.is_leaf() )
620                         return operator()( node_traits::to_internal_node( n1 ), node_traits::to_leaf_node( n2 ));
621                     else
622                         return operator()( node_traits::to_internal_node( n1 ), node_traits::to_internal_node( n2 ));
623                 }
624
625                 template <typename GC, typename Q>
626                 int operator()( base_node<GC> const& n, Q const& v ) const
627                 {
628                     if ( n.infinite_key())
629                         return 1;
630                     if ( n.is_leaf() )
631                         return operator()( node_traits::to_leaf_node( n ), v );
632                     return operator()( node_traits::to_internal_node( n ), v );
633                 }
634
635                 template <typename GC, typename Q>
636                 int operator()( Q const& v, base_node<GC> const& n ) const
637                 {
638                     return -operator()( n, v );
639                 }
640
641                 template <typename GC, typename LeafNode >
642                 int operator()( base_node<GC> const& i, internal_node<key_type, LeafNode> const& n ) const
643                 {
644                     if ( i.is_leaf() )
645                         return operator()( static_cast<LeafNode const&>(i), n );
646                     return operator()( static_cast<internal_node<key_type, LeafNode> const&>(i), n );
647                 }
648
649                 template <typename GC, typename LeafNode >
650                 int operator()( internal_node<key_type, LeafNode> const& n, base_node<GC> const& i ) const
651                 {
652                     return -operator()( i, n );
653                 }
654
655                 template <typename GC, typename Tag >
656                 int operator()( node<GC, Tag> const& n, internal_node<key_type, node<GC, Tag> > const& i ) const
657                 {
658                     if ( !n.infinite_key() ) {
659                         if ( i.infinite_key() )
660                             return -1;
661                         return operator()( n, i.m_Key );
662                     }
663
664                     if ( !i.infinite_key())
665                         return 1;
666                     return int( n.infinite_key()) - int( i.infinite_key());
667                 }
668
669                 template <typename GC, typename Tag >
670                 int operator()( internal_node<key_type, node<GC, Tag> > const& i, node<GC, Tag> const& n ) const
671                 {
672                     return -operator()( n, i );
673                 }
674
675             };
676
677         } // namespace details
678         //@endcond
679
680     }   // namespace ellen_bintree
681
682     // Forwards
683     template < class GC, typename Key, typename T, class Traits = ellen_bintree::type_traits >
684     class EllenBinTree;
685
686 }} // namespace cds::intrusive
687
688 #endif  // #ifndef __CDS_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H