cds/intrusive/details/ellen_bintree_base.h

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