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 <cds/intrusive/base.h>
   7 #include <cds/opt/options.h>
   8 #include <cds/urcu/options.h>
   9 #include <cds/details/std/type_traits.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( null_ptr<update_desc *>() )
  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             CDS_ATOMIC::atomic<base_class *> m_pLeft     ;   ///< Left subtree
 204             CDS_ATOMIC::atomic<base_class *> m_pRight    ;   ///< Right subtree
 205             CDS_ATOMIC::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( null_ptr<base_class *>() )
 214                 , m_pRight( null_ptr<base_class *>() )
 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, CDS_DECL_OPTIONS2>
 250         struct hook
 251         {
 252             typedef typename opt::make_options< default_hook, CDS_OPTIONS2>::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 < CDS_DECL_OPTIONS2 >
 267         struct base_hook: public hook< opt::base_hook_tag, CDS_OPTIONS2 >
 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, CDS_DECL_OPTIONS2 >
 280         struct member_hook: public hook< opt::member_hook_tag, CDS_OPTIONS2 >
 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, CDS_DECL_OPTIONS2 >
 297         struct traits_hook: public hook< opt::traits_hook_tag, CDS_OPTIONS2 >
 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 <CDS_DECL_OPTIONS12>
 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, CDS_OPTIONS12 >::type
 535                 ,CDS_OPTIONS12
 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