gdax-orderbook-hpp/demo/dependencies/libcds-2.3.2/cds/container/details/bronson_avltree_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_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
  32 #define CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
  33
  34 #include <cds/container/details/base.h>
  35 #include <cds/opt/compare.h>
  36 #include <cds/urcu/options.h>
  37 #include <cds/sync/spinlock.h>
  38 #include <cds/sync/injecting_monitor.h>
  39
  40 namespace cds { namespace container {
  41
  42     /// BronsonAVLTree related declarations
  43     namespace bronson_avltree {
  44
  45         template <typename Key, typename T, typename SyncMonitor >
  46         struct node;
  47
  48         //@cond
  49         template <typename Node, typename T, typename SyncMonitor>
  50         struct link_node
  51         {
  52             typedef Node     node_type;
  53             typedef T        mapped_type;
  54             typedef uint32_t version_type;  ///< version type (internal)
  55
  56             enum
  57             {
  58                 shrinking = 1,
  59                 unlinked = 2,
  60                 version_flags = shrinking | unlinked
  61                 // the rest is version counter
  62             };
  63
  64             atomics::atomic< int >          m_nHeight;  ///< Node height
  65             atomics::atomic<version_type>   m_nVersion; ///< Version bits
  66             atomics::atomic<node_type *>    m_pParent;  ///< Parent node
  67             atomics::atomic<node_type *>    m_pLeft;    ///< Left child
  68             atomics::atomic<node_type *>    m_pRight;   ///< Right child
  69             typename SyncMonitor::node_injection m_SyncMonitorInjection;    ///< @ref cds_sync_monitor "synchronization monitor" injected data
  70             atomics::atomic<mapped_type *>  m_pValue;   ///< Value
  71
  72         public:
  73             link_node()
  74                 : m_nHeight( 0 )
  75                 , m_nVersion( 0 )
  76                 , m_pParent( nullptr )
  77                 , m_pLeft( nullptr )
  78                 , m_pRight( nullptr )
  79             {
  80                 m_pValue.store( nullptr, atomics::memory_order_release );
  81             }
  82
  83             link_node( int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
  84                 : m_nHeight( nHeight )
  85                 , m_nVersion( version )
  86                 , m_pParent( pParent )
  87                 , m_pLeft( pLeft )
  88                 , m_pRight( pRight )
  89             {
  90                 m_pValue.store( nullptr, atomics::memory_order_release );
  91             }
  92
  93             node_type * parent( atomics::memory_order order ) const
  94             {
  95                 return m_pParent.load( order );
  96             }
  97
  98             void parent( node_type * p, atomics::memory_order order )
  99             {
 100                 m_pParent.store( p, order );
 101             }
 102
 103             node_type * child( int nDirection, atomics::memory_order order ) const
 104             {
 105                 assert( nDirection != 0 );
 106                 return nDirection < 0 ? m_pLeft.load( order ) : m_pRight.load( order );
 107             }
 108
 109             void child( node_type * pChild, int nDirection, atomics::memory_order order )
 110             {
 111                 assert( nDirection != 0 );
 112                 if ( nDirection < 0 )
 113                     m_pLeft.store( pChild, order );
 114                 else
 115                     m_pRight.store( pChild, order );
 116             }
 117
 118             version_type version( atomics::memory_order order ) const
 119             {
 120                 return m_nVersion.load( order );
 121             }
 122
 123             void version( version_type ver, atomics::memory_order order )
 124             {
 125                 m_nVersion.store( ver, order );
 126             }
 127
 128             void exchange_version( version_type ver, atomics::memory_order order )
 129             {
 130                 m_nVersion.exchange( ver, order );
 131             }
 132
 133             int height( atomics::memory_order order ) const
 134             {
 135                 return m_nHeight.load( order );
 136             }
 137
 138             void height( int h, atomics::memory_order order )
 139             {
 140                 m_nHeight.store( h, order );
 141             }
 142
 143             template <typename BackOff>
 144             void wait_until_shrink_completed( atomics::memory_order order ) const
 145             {
 146                 BackOff bkoff;
 147                 while ( is_shrinking( order ))
 148                     bkoff();
 149             }
 150
 151             bool is_unlinked( atomics::memory_order order ) const
 152             {
 153                 return m_nVersion.load( order ) == unlinked;
 154             }
 155
 156             bool is_shrinking( atomics::memory_order order ) const
 157             {
 158                 return (m_nVersion.load( order ) & shrinking) != 0;
 159             }
 160
 161             mapped_type * value( atomics::memory_order order ) const
 162             {
 163                 return m_pValue.load( order );
 164             }
 165
 166             bool is_valued( atomics::memory_order order ) const
 167             {
 168                 return value( order ) != nullptr;
 169             }
 170         };
 171         //@endcond
 172
 173         /// BronsonAVLTree internal node
 174         template <typename Key, typename T, typename SyncMonitor >
 175         struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor >
 176         {
 177             //@cond
 178             typedef link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor > base_class;
 179             //@endcond
 180
 181             typedef Key key_type;       ///< key type
 182             typedef T   mapped_type;    ///< value type
 183             //@cond
 184             typedef typename base_class::version_type version_type;
 185             //@endcond
 186
 187             key_type const                  m_key;      ///< Key
 188             node *                          m_pNextRemoved; ///< thread-local list of removed node
 189
 190         public:
 191             //@cond
 192             template <typename Q>
 193             node( Q&& key )
 194                 : base_class()
 195                 , m_key( std::forward<Q>( key ))
 196                 , m_pNextRemoved( nullptr )
 197             {}
 198
 199             template <typename Q>
 200             node( Q&& key, int nHeight, version_type version, node * pParent, node * pLeft, node * pRight )
 201                 : base_class( nHeight, version, pParent, pLeft, pRight )
 202                 , m_key( std::forward<Q>( key ))
 203                 , m_pNextRemoved( nullptr )
 204             {}
 205             //@endcond
 206         };
 207
 208         /// BronsonAVLTreeMap internal statistics
 209         template <typename Counter = cds::atomicity::event_counter>
 210         struct stat {
 211             typedef Counter   event_counter; ///< Event counter type
 212
 213             event_counter   m_nFindSuccess; ///< Count of success \p find() call
 214             event_counter   m_nFindFailed;  ///< Count of failed \p find() call
 215             event_counter   m_nFindRetry;   ///< Count of retries during \p find()
 216             event_counter   m_nFindWaitShrinking;   ///< Count of waiting until shrinking completed duting \p find() call
 217
 218             event_counter   m_nInsertSuccess;       ///< Count of inserting data node
 219             event_counter   m_nInsertFailed;        ///< Count of insert failures
 220             event_counter   m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
 221             event_counter   m_nInsertRetry;         ///< Count of insert retries via concurrent operations
 222             event_counter   m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call
 223             event_counter   m_nUpdateRetry;         ///< Count of update retries via concurrent operations
 224             event_counter   m_nUpdateRootWaitShrinking;  ///< Count of waiting until root shrinking completed duting \p update() call
 225             event_counter   m_nUpdateSuccess;       ///< Count of updating data node
 226             event_counter   m_nUpdateUnlinked;      ///< Count of attempts to update unlinked node
 227             event_counter   m_nDisposedNode;        ///< Count of disposed node
 228             event_counter   m_nDisposedValue;       ///< Count of disposed value
 229             event_counter   m_nExtractedValue;      ///< Count of extracted value
 230             event_counter   m_nRemoveSuccess;       ///< Count of successfully \p erase() call
 231             event_counter   m_nRemoveFailed;        ///< Count of failed \p erase() call
 232             event_counter   m_nRemoveRetry;         ///< Count o erase/extract retries
 233             event_counter   m_nExtractSuccess;      ///< Count of successfully \p extract() call
 234             event_counter   m_nExtractFailed;       ///< Count of failed \p extract() call
 235             event_counter   m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
 236             event_counter   m_nRemoveRootWaitShrinking;  ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
 237             event_counter   m_nMakeRoutingNode;     ///< How many nodes were converted to routing (valueless) nodes
 238
 239             event_counter   m_nRightRotation;       ///< Count of single right rotation
 240             event_counter   m_nLeftRotation;        ///< Count of single left rotation
 241             event_counter   m_nLeftRightRotation;   ///< Count of double left-over-right rotation
 242             event_counter   m_nRightLeftRotation;   ///< Count of double right-over-left rotation
 243
 244             event_counter   m_nRotateAfterRightRotation; ///< Count of rotation required after single right rotation
 245             event_counter   m_nRemoveAfterRightRotation; ///< Count of removal required after single right rotation
 246             event_counter   m_nDamageAfterRightRotation; ///< Count of damaged node after single right rotation
 247
 248             event_counter   m_nRotateAfterLeftRotation;  ///< Count of rotation required after signle left rotation
 249             event_counter   m_nRemoveAfterLeftRotation;  ///< Count of removal required after single left rotation
 250             event_counter   m_nDamageAfterLeftRotation;  ///< Count of damaged node after single left rotation
 251
 252             event_counter   m_nRotateAfterRLRotation;    ///< Count of rotation required after right-over-left rotation
 253             event_counter   m_nRemoveAfterRLRotation;    ///< Count of removal required after right-over-left rotation
 254             event_counter   m_nRotateAfterLRRotation;    ///< Count of rotation required after left-over-right rotation
 255             event_counter   m_nRemoveAfterLRRotation;    ///< Count of removal required after left-over-right rotation
 256
 257             event_counter   m_nInsertRebalanceReq;  ///< Count of rebalance required after inserting
 258             event_counter   m_nRemoveRebalanceReq;  ///< Count of rebalance required after removing
 259
 260             //@cond
 261             void onFindSuccess()        { ++m_nFindSuccess      ; }
 262             void onFindFailed()         { ++m_nFindFailed       ; }
 263             void onFindRetry()          { ++m_nFindRetry        ; }
 264             void onFindWaitShrinking()  { ++m_nFindWaitShrinking; }
 265
 266             void onInsertSuccess()          { ++m_nInsertSuccess; }
 267             void onInsertFailed()           { ++m_nInsertFailed; }
 268             void onRelaxedInsertFailed()    { ++m_nRelaxedInsertFailed; }
 269             void onInsertRetry()            { ++m_nInsertRetry      ; }
 270             void onUpdateWaitShrinking()    { ++m_nUpdateWaitShrinking; }
 271             void onUpdateRetry()            { ++m_nUpdateRetry; }
 272             void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
 273             void onUpdateSuccess()          { ++m_nUpdateSuccess;  }
 274             void onUpdateUnlinked()         { ++m_nUpdateUnlinked; }
 275             void onDisposeNode()            { ++m_nDisposedNode; }
 276             void onDisposeValue()           { ++m_nDisposedValue; }
 277             void onExtractValue()           { ++m_nExtractedValue; }
 278             void onRemove(bool bSuccess)
 279             {
 280                 if ( bSuccess )
 281                     ++m_nRemoveSuccess;
 282                 else
 283                     ++m_nRemoveFailed;
 284             }
 285             void onExtract( bool bSuccess )
 286             {
 287                 if ( bSuccess )
 288                     ++m_nExtractSuccess;
 289                 else
 290                     ++m_nExtractFailed;
 291             }
 292             void onRemoveRetry()            { ++m_nRemoveRetry; }
 293             void onRemoveWaitShrinking()    { ++m_nRemoveWaitShrinking; }
 294             void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
 295             void onMakeRoutingNode()        { ++m_nMakeRoutingNode; }
 296
 297             void onRotateRight()            { ++m_nRightRotation; }
 298             void onRotateLeft()             { ++m_nLeftRotation; }
 299             void onRotateRightOverLeft()    { ++m_nRightLeftRotation; }
 300             void onRotateLeftOverRight()    { ++m_nLeftRightRotation; }
 301
 302             void onRotateAfterRightRotation() { ++m_nRotateAfterRightRotation; }
 303             void onRemoveAfterRightRotation() { ++m_nRemoveAfterRightRotation; }
 304             void onDamageAfterRightRotation() { ++m_nDamageAfterRightRotation; }
 305
 306             void onRotateAfterLeftRotation()  { ++m_nRotateAfterLeftRotation; }
 307             void onRemoveAfterLeftRotation()  { ++m_nRemoveAfterLeftRotation; }
 308             void onDamageAfterLeftRotation()  { ++m_nDamageAfterLeftRotation; }
 309
 310             void onRotateAfterRLRotation()    { ++m_nRotateAfterRLRotation; }
 311             void onRemoveAfterRLRotation()    { ++m_nRemoveAfterRLRotation; }
 312             void onRotateAfterLRRotation()    { ++m_nRotateAfterLRRotation; }
 313             void onRemoveAfterLRRotation()    { ++m_nRemoveAfterLRRotation; }
 314
 315             void onInsertRebalanceRequired() { ++m_nInsertRebalanceReq; }
 316             void onRemoveRebalanceRequired() { ++m_nRemoveRebalanceReq; }
 317             //@endcond
 318         };
 319
 320         /// BronsonAVLTreeMap empty statistics
 321         struct empty_stat {
 322             //@cond
 323             void onFindSuccess()        const {}
 324             void onFindFailed()         const {}
 325             void onFindRetry()          const {}
 326             void onFindWaitShrinking()  const {}
 327
 328             void onInsertSuccess()          const {}
 329             void onInsertFailed()           const {}
 330             void onRelaxedInsertFailed()    const {}
 331             void onInsertRetry()            const {}
 332             void onUpdateWaitShrinking()    const {}
 333             void onUpdateRetry()            const {}
 334             void onUpdateRootWaitShrinking() const {}
 335             void onUpdateSuccess()          const {}
 336             void onUpdateUnlinked()         const {}
 337             void onDisposeNode()            const {}
 338             void onDisposeValue()           const {}
 339             void onExtractValue()           const {}
 340             void onRemove(bool /*bSuccess*/) const {}
 341             void onExtract(bool /*bSuccess*/) const {}
 342             void onRemoveRetry()            const {}
 343             void onRemoveWaitShrinking()    const {}
 344             void onRemoveRootWaitShrinking() const {}
 345             void onMakeRoutingNode()        const {}
 346
 347             void onRotateRight()            const {}
 348             void onRotateLeft()             const {}
 349             void onRotateRightOverLeft()    const {}
 350             void onRotateLeftOverRight()    const {}
 351
 352             void onRotateAfterRightRotation() const {}
 353             void onRemoveAfterRightRotation() const {}
 354             void onDamageAfterRightRotation() const {}
 355
 356             void onRotateAfterLeftRotation()  const {}
 357             void onRemoveAfterLeftRotation()  const {}
 358             void onDamageAfterLeftRotation()  const {}
 359
 360             void onRotateAfterRLRotation()    const {}
 361             void onRemoveAfterRLRotation()    const {}
 362             void onRotateAfterLRRotation()    const {}
 363             void onRemoveAfterLRRotation()    const {}
 364
 365             void onInsertRebalanceRequired() const {}
 366             void onRemoveRebalanceRequired() const {}
 367             //@endcond
 368         };
 369
 370         /// Option to allow relaxed insert into \ref cds_container_BronsonAVLTreeMap_rcu "Bronson et al AVL-tree"
 371         /**
 372             By default, this option is disabled and the new node is created under its parent lock.
 373             In this case, it is guaranteed the new node will be attached to its parent.
 374             On the other hand, constructing of the new node can be too complex to make it under the lock,
 375             that can lead to lock contention.
 376
 377             When this option is enabled, the new node is created before locking the parent node.
 378             After that, the parent is locked and checked whether the new node can be attached to the parent.
 379             In this case, false node creating can be performed, but locked section can be significantly small.
 380         */
 381         template <bool Enable>
 382         struct relaxed_insert {
 383             //@cond
 384             template <typename Base> struct pack : public Base
 385             {
 386                 enum { relaxed_insert = Enable };
 387             };
 388             //@endcond
 389         };
 390
 391         /// \p BronsonAVLTreeMap traits
 392         /**
 393             Note that there are two main specialization of Bronson et al AVL-tree:
 394             - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
 395             - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
 396
 397             Depends on tree specialization, different traits member can be used.
 398         */
 399         struct traits
 400         {
 401             /// Key comparison functor
 402             /**
 403                 No default functor is provided. If the option is not specified, the \p less is used.
 404
 405                 See \p cds::opt::compare option description for functor interface.
 406
 407                 You should provide \p compare or \p less functor.
 408             */
 409             typedef opt::none                       compare;
 410
 411             /// Specifies binary predicate used for key compare.
 412             /**
 413                 See \p cds::opt::less option description for predicate interface.
 414
 415                 You should provide \p compare or \p less functor.
 416             */
 417             typedef opt::none                       less;
 418
 419             /// Allocator for internal node
 420             typedef CDS_DEFAULT_ALLOCATOR           node_allocator;
 421
 422             /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
 423             typedef CDS_DEFAULT_ALLOCATOR           allocator;
 424
 425             /// Disposer (only for pointer-oriented tree specialization)
 426             /**
 427                 The functor used for dispose removed values.
 428                 The user-provided disposer is used only for pointer-oriented tree specialization
 429                 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the routing node without value,
 430                 the disposer will be called to signal that the memory for the value can be safely freed.
 431                 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
 432             */
 433             typedef opt::v::delete_disposer<>       disposer;
 434
 435             /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
 436             typedef cds::sync::injecting_monitor<cds::sync::spin>  sync_monitor;
 437
 438             /// Enable relaxed insertion.
 439             /**
 440                 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
 441                 By default, this option is disabled.
 442             */
 443             static bool const relaxed_insert = false;
 444
 445             /// Item counter
 446             /**
 447                 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
 448                 To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter.
 449             */
 450             typedef atomicity::empty_item_counter     item_counter;
 451
 452             /// C++ memory ordering model
 453             /**
 454                 List of available memory ordering see \p opt::memory_model
 455             */
 456             typedef opt::v::relaxed_ordering        memory_model;
 457
 458             /// Internal statistics
 459             /**
 460                 By default, internal statistics is disabled (\p bronson_avltree::empty_stat).
 461                 To enable it use \p bronson_avltree::stat.
 462             */
 463             typedef empty_stat                      stat;
 464
 465             /// Back-off strategy
 466             typedef cds::backoff::empty             back_off;
 467
 468             /// RCU deadlock checking policy
 469             /**
 470                 List of available options see \p opt::rcu_check_deadlock
 471             */
 472             typedef cds::opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 473         };
 474
 475         /// Metafunction converting option list to BronsonAVLTreeMap traits
 476         /**
 477             Note that there are two main specialization of Bronson et al AVL-tree:
 478             - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
 479             - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
 480
 481             Depends on tree specialization, different options can be specified.
 482
 483             \p Options are:
 484             - \p opt::compare - key compare functor. No default functor is provided.
 485                 If the option is not specified, \p %opt::less is used.
 486             - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
 487             - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
 488             - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
 489                 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
 490             - \p cds::intrusive::opt::disposer - the functor used for dispose removed values.
 491                 The user-provided disposer is used only for pointer-oriented tree specialization
 492                 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
 493                 the disposer will be called to signal that the memory for the value can be safely freed.
 494                 Default is \p cds::intrusive::opt::delete_disposer which calls \p delete operator.
 495                 Due the nature of GC schema the disposer may be called asynchronously.
 496             - \p opt::sync_monitor -  @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
 497                 default is \p cds::sync::injecting_monitor<cds::sync::spin>
 498             - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
 499                 @ref bronson_avltree::relaxed_insert "relaxed insertion"
 500             - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
 501                 To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
 502             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 503                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 504             - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
 505                 To enable statistics use \p \p bronson_avltree::stat
 506             - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
 507             - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
 508         */
 509         template <typename... Options>
 510         struct make_traits {
 511 #   ifdef CDS_DOXYGEN_INVOKED
 512             typedef implementation_defined type ;   ///< Metafunction result
 513 #   else
 514             typedef typename cds::opt::make_options<
 515                 typename cds::opt::find_type_traits< traits, Options... >::type
 516                 ,Options...
 517             >::type   type;
 518 #   endif
 519         };
 520     } // namespace bronson_avltree
 521
 522     // Forwards
 523     template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
 524     class BronsonAVLTreeMap;
 525
 526 }} // namespace cds::container
 527
 528 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H