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