cds/intrusive/details/ellen_bintree_base.h

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