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