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