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 \ref cds_intrusive_hook_tag "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
 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 parameters:
 233             - \p GC - one of \ref cds_garbage_collector "garbage collector type"
 234             - \p Key - key type
 235             - \p Tag - a \ref cds_intrusive_hook_tag "tag"
 236         */
 237         template <typename GC, typename Key, typename Tag = opt::none>
 238         struct node_types
 239         {
 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
 243         };
 244
 245         //@cond
 246         struct undefined_gc;
 247         struct default_hook {
 248             typedef undefined_gc    gc;
 249             typedef opt::none       tag;
 250         };
 251         //@endcond
 252
 253         //@cond
 254         template < typename HookType, typename... Options>
 255         struct hook
 256         {
 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;
 262         };
 263         //@endcond
 264
 265         /// Base hook
 266         /**
 267             \p Options are:
 268             - \p opt::gc - garbage collector
 269             - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
 270         */
 271         template < typename... Options >
 272         struct base_hook: public hook< opt::base_hook_tag, Options... >
 273         {};
 274
 275         /// Member hook
 276         /**
 277             \p MemberOffset defines offset in bytes of \ref node member into your structure.
 278             Use \p offsetof macro to define \p MemberOffset
 279
 280             \p Options are:
 281             - \p opt::gc - garbage collector
 282             - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
 283         */
 284         template < size_t MemberOffset, typename... Options >
 285         struct member_hook: public hook< opt::member_hook_tag, Options... >
 286         {
 287             //@cond
 288             static CDS_CONSTEXPR const size_t c_nMemberOffset = MemberOffset;
 289             //@endcond
 290         };
 291
 292         /// Traits hook
 293         /**
 294             \p NodeTraits defines type traits for node.
 295             See \ref node_traits for \p NodeTraits interface description
 296
 297             \p Options are:
 298             - opt::gc - garbage collector
 299             - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
 300         */
 301         template <typename NodeTraits, typename... Options >
 302         struct traits_hook: public hook< opt::traits_hook_tag, Options... >
 303         {
 304             //@cond
 305             typedef NodeTraits node_traits;
 306             //@endcond
 307         };
 308
 309         /// Key extracting functor option setter
 310         template <typename Type>
 311         struct key_extractor {
 312             //@cond
 313             template <typename Base> struct pack: public Base
 314             {
 315                 typedef Type key_extractor;
 316             };
 317             //@endcond
 318         };
 319
 320         /// Update descriptor allocator option setter
 321         template <typename Type>
 322         struct update_desc_allocator {
 323             //@cond
 324             template <typename Base> struct pack: public Base
 325             {
 326                 typedef Type update_desc_allocator;
 327             };
 328             //@endcond
 329         };
 330
 331         /// EllenBinTree internal statistics
 332         template <typename Counter = cds::atomicity::event_counter>
 333         struct stat {
 334             typedef Counter   event_counter ; ///< Event counter type
 335
 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
 340
 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
 359
 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
 365
 366             //@cond
 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      ; }
 394             //@endcond
 395         };
 396
 397         /// EllenBinTree empty statistics
 398         struct empty_stat {
 399             //@cond
 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()                  {}
 424             void    onHelpMark()                    {}
 425             void    onHelpGuardSuccess()            {}
 426             void    onHelpGuardFailed()             {}
 427             //@endcond
 428         };
 429
 430         /// EllenBinTree traits
 431         struct traits
 432         {
 433             /// Hook used
 434             /**
 435                 Possible values are: \p ellen_bintree::base_hook, \p ellen_bintree::member_hook, \p ellen_bintree::traits_hook.
 436             */
 437             typedef base_hook<>       hook;
 438
 439             /// Key extracting functor
 440             /**
 441                 You should explicit define a valid functor.
 442                 The functor has the following prototype:
 443                 \code
 444                 struct key_extractor {
 445                     void operator ()( Key& dest, T const& src );
 446                 };
 447                 \endcode
 448                 It should initialize \p dest key from \p src data.
 449                 The functor is used to initialize internal nodes.
 450             */
 451             typedef opt::none           key_extractor;
 452
 453             /// Key comparison functor
 454             /**
 455                 No default functor is provided. If the option is not specified, the \p less is used.
 456
 457                 See \p cds::opt::compare option description for functor interface.
 458
 459                 You should provide \p compare or \p less functor.
 460                 See \ref cds_intrusive_EllenBinTree_rcu_less "predicate requirements".
 461             */
 462             typedef opt::none                       compare;
 463
 464             /// Specifies binary predicate used for key compare.
 465             /**
 466                 See \p cds::opt::less option description for predicate interface.
 467
 468                 You should provide \p compare or \p less functor.
 469                 See \ref cds_intrusive_EllenBinTree_rcu_less "predicate requirements".
 470             */
 471             typedef opt::none                       less;
 472
 473             /// Disposer
 474             /**
 475                 The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
 476             */
 477             typedef opt::v::empty_disposer          disposer;
 478
 479             /// Item counter
 480             /**
 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
 483             */
 484             typedef atomicity::empty_item_counter     item_counter;
 485
 486             /// C++ memory ordering model
 487             /**
 488                 List of available memory ordering see \p opt::memory_model
 489             */
 490             typedef opt::v::relaxed_ordering        memory_model;
 491
 492             /// Allocator for update descriptors
 493             /**
 494                 The allocator type is used for \p ellen_bintree::update_desc.
 495
 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.
 502
 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.
 505             */
 506             typedef CDS_DEFAULT_ALLOCATOR           update_desc_allocator;
 507
 508             /// Allocator for internal nodes
 509             /**
 510                 The allocator type is used for \p ellen_bintree::internal_node.
 511             */
 512             typedef CDS_DEFAULT_ALLOCATOR           node_allocator;
 513
 514             /// Internal statistics
 515             /**
 516                 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
 517                 To enable it use \p ellen_bintree::stat.
 518             */
 519             typedef empty_stat                      stat;
 520
 521             /// RCU deadlock checking policy (only for \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
 522             /**
 523                 List of available options see \p opt::rcu_check_deadlock
 524             */
 525             typedef cds::opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 526         };
 527
 528         /// Metafunction converting option list to EllenBinTree traits
 529         /**
 530             \p Options are:
 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:
 534                 \code
 535                     struct key_extractor {
 536                         void operator ()( Key& dest, T const& src );
 537                     };
 538                 \endcode
 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
 562         */
 563         template <typename... Options>
 564         struct make_traits {
 565 #   ifdef CDS_DOXYGEN_INVOKED
 566             typedef implementation_defined type ;   ///< Metafunction result
 567 #   else
 568             typedef typename cds::opt::make_options<
 569                 typename cds::opt::find_type_traits< traits, Options... >::type
 570                 ,Options...
 571             >::type   type;
 572 #   endif
 573         };
 574
 575         //@cond
 576         namespace details {
 577
 578             template <typename Key, typename T, typename Compare, typename NodeTraits>
 579             struct compare
 580             {
 581                 typedef Compare     key_compare;
 582                 typedef Key         key_type;
 583                 typedef T           value_type;
 584                 typedef NodeTraits  node_traits;
 585
 586                 template <typename Q1, typename Q2>
 587                 int operator()( Q1 const& v1, Q2 const& v2) const
 588                 {
 589                     return key_compare()( v1, v2 );
 590                 }
 591
 592                 template <typename LeafNode>
 593                 int operator()( internal_node<key_type, LeafNode> const& n1, internal_node<key_type, LeafNode> const& n2 ) const
 594                 {
 595                     if ( n1.infinite_key() )
 596                         return n2.infinite_key() ? n1.infinite_key() - n2.infinite_key() : 1;
 597                     else if ( n2.infinite_key() )
 598                         return -1;
 599                     return operator()( n1.m_Key, n2.m_Key );
 600                 }
 601
 602                 template <typename LeafNode, typename Q>
 603                 int operator()( internal_node<key_type, LeafNode> const& n, Q const& v ) const
 604                 {
 605                     if ( n.infinite_key() )
 606                         return 1;
 607                     return operator()( n.m_Key, v );
 608                 }
 609
 610                 template <typename LeafNode, typename Q>
 611                 int operator()( Q const& v, internal_node<key_type, LeafNode> const& n ) const
 612                 {
 613                     if ( n.infinite_key() )
 614                         return -1;
 615                     return operator()( v, n.m_Key );
 616                 }
 617
 618                 template <typename GC, typename Tag>
 619                 int operator()( node<GC, Tag> const& n1, node<GC, Tag> const& n2 ) const
 620                 {
 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 ));
 624                 }
 625
 626                 template <typename GC, typename Tag, typename Q>
 627                 int operator()( node<GC, Tag> const& n, Q const& v ) const
 628                 {
 629                     if ( n.infinite_key() )
 630                         return 1;
 631                     return operator()( *node_traits::to_value_ptr( n ), v );
 632                 }
 633
 634                 template <typename GC, typename Tag, typename Q>
 635                 int operator()( Q const& v, node<GC, Tag> const& n ) const
 636                 {
 637                     if ( n.infinite_key() )
 638                         return -1;
 639                     return operator()( v, *node_traits::to_value_ptr( n ) );
 640                 }
 641
 642                 template <typename GC>
 643                 int operator()( base_node<GC> const& n1, base_node<GC> const& n2 ) const
 644                 {
 645                     if ( n1.infinite_key() != n2.infinite_key() )
 646                         return n1.infinite_key() - n2.infinite_key();
 647                     if ( n1.is_leaf() ) {
 648                         if ( n2.is_leaf() )
 649                             return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_leaf_node( n2 ));
 650                         else
 651                             return operator()( node_traits::to_leaf_node( n1 ), node_traits::to_internal_node( n2 ));
 652                     }
 653
 654                     if ( n2.is_leaf() )
 655                         return operator()( node_traits::to_internal_node( n1 ), node_traits::to_leaf_node( n2 ));
 656                     else
 657                         return operator()( node_traits::to_internal_node( n1 ), node_traits::to_internal_node( n2 ));
 658                 }
 659
 660                 template <typename GC, typename Q>
 661                 int operator()( base_node<GC> const& n, Q const& v ) const
 662                 {
 663                     if ( n.infinite_key())
 664                         return 1;
 665                     if ( n.is_leaf() )
 666                         return operator()( node_traits::to_leaf_node( n ), v );
 667                     return operator()( node_traits::to_internal_node( n ), v );
 668                 }
 669
 670                 template <typename GC, typename Q>
 671                 int operator()( Q const& v, base_node<GC> const& n ) const
 672                 {
 673                     return -operator()( n, v );
 674                 }
 675
 676                 template <typename GC, typename LeafNode >
 677                 int operator()( base_node<GC> const& i, internal_node<key_type, LeafNode> const& n ) const
 678                 {
 679                     if ( i.is_leaf() )
 680                         return operator()( static_cast<LeafNode const&>(i), n );
 681                     return operator()( static_cast<internal_node<key_type, LeafNode> const&>(i), n );
 682                 }
 683
 684                 template <typename GC, typename LeafNode >
 685                 int operator()( internal_node<key_type, LeafNode> const& n, base_node<GC> const& i ) const
 686                 {
 687                     return -operator()( i, n );
 688                 }
 689
 690                 template <typename GC, typename Tag >
 691                 int operator()( node<GC, Tag> const& n, internal_node<key_type, node<GC, Tag> > const& i ) const
 692                 {
 693                     if ( !n.infinite_key() ) {
 694                         if ( i.infinite_key() )
 695                             return -1;
 696                         return operator()( n, i.m_Key );
 697                     }
 698
 699                     if ( !i.infinite_key())
 700                         return 1;
 701                     return int( n.infinite_key()) - int( i.infinite_key());
 702                 }
 703
 704                 template <typename GC, typename Tag >
 705                 int operator()( internal_node<key_type, node<GC, Tag> > const& i, node<GC, Tag> const& n ) const
 706                 {
 707                     return -operator()( n, i );
 708                 }
 709
 710             };
 711
 712         } // namespace details
 713         //@endcond
 714     }   // namespace ellen_bintree
 715
 716     // Forwards
 717     template < class GC, typename Key, typename T, class Traits = ellen_bintree::traits >
 718     class EllenBinTree;
 719
 720 }} // namespace cds::intrusive
 721
 722 #endif  // #ifndef __CDS_INTRUSIVE_DETAILS_ELLEN_BINTREE_BASE_H