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