From 4b1cae2a5c9ac920c7dccbb14e42a37fdeebda1d Mon Sep 17 00:00:00 2001 From: khizmax Date: Tue, 24 Feb 2015 12:47:27 +0300 Subject: [PATCH] Improved BronsonAVLTreeMap doc --- cds/container/bronson_avltree_map_rcu.h | 22 +++++++++++++++----- cds/container/details/bronson_avltree_base.h | 21 +++++++++---------- cds/container/impl/bronson_avltree_map_rcu.h | 1 + 3 files changed, 28 insertions(+), 16 deletions(-) diff --git a/cds/container/bronson_avltree_map_rcu.h b/cds/container/bronson_avltree_map_rcu.h index f5c6b603..c544547a 100644 --- a/cds/container/bronson_avltree_map_rcu.h +++ b/cds/container/bronson_avltree_map_rcu.h @@ -43,8 +43,18 @@ namespace cds { namespace container { Source: - [2010] N.Bronson, J.Casper, H.Chafi, K.Olukotun "A Practical Concurrent Binary Search Tree" - - bla-bla-bla + - Java implementation + + This is a concurrent AVL tree algorithm that uses hand-over-hand optimistic validation, + a concurrency control mechanism for searching and navigating a binary search tree. + This mechanism minimizes spurious retries when concurrent structural changes cannot + affect the correctness of the search or navigation result. The algorithm is based on + partially external trees, a simple scheme that simplifies deletions by leaving a routing + node in the tree when deleting a node that has two children, then opportunistically unlinking + routing nodes during rebalancing. As in external trees, which store values only in leaf nodes, + deletions can be performed locally while holding a fixed number of locks. Partially + external trees, however, require far fewer routing nodes than an external tree for most sequences + of insertions and deletions. Template arguments: - \p RCU - one of \ref cds_urcu_gc "RCU type" @@ -53,6 +63,8 @@ namespace cds { namespace container { - \p Traits - tree traits, default is \p bronson_avltree::traits It is possible to declare option-based tree with \p bronson_avltree::make_traits metafunction instead of \p Traits template argument. + + There is \ref cds_container_BronsonAVLTreeMap_rcu_ptr "a specialization" for "key -> value pointer" map. @note Before including you should include appropriate RCU header file, see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files. @@ -400,7 +412,7 @@ namespace cds { namespace container { \code key_type key; exempt_ptr xp = theTree.extract_min( [&key]( key_type const& k ) { key = k; } ); - \endode + \endcode \p key_type should be copy-assignable. The copy of minimal key is returned in \p min_key argument. */ @@ -416,7 +428,7 @@ namespace cds { namespace container { If the set is empty, returns empty \p exempt_ptr. Note that the function returns only the value for maximal key. - To retrieve its key use \p extract_max( Func ) member function. + To retrieve its key use \p extract_max( Func ) or \p extract_max_key(key_type&) member function. @note Due the concurrent nature of the map, the function extracts nearly maximal key. It means that the function gets rightmost leaf of the tree and tries to unlink it. @@ -471,7 +483,7 @@ namespace cds { namespace container { \code key_type key; exempt_ptr xp = theTree.extract_max( [&key]( key_type const& k ) { key = k; } ); - \endode + \endcode \p key_type should be copy-assignable. The copy of maximal key is returned in \p max_key argument. */ diff --git a/cds/container/details/bronson_avltree_base.h b/cds/container/details/bronson_avltree_base.h index 2cb57610..95290cde 100644 --- a/cds/container/details/bronson_avltree_base.h +++ b/cds/container/details/bronson_avltree_base.h @@ -42,7 +42,6 @@ namespace cds { namespace container { atomics::atomic m_pValue; ///< Value public: - //@cond link_node() : m_nHeight( 0 ) , m_nVersion( 0 ) @@ -123,8 +122,6 @@ namespace cds { namespace container { { return value( order ) != nullptr; } - - //@endcond }; //@endcond @@ -138,7 +135,9 @@ namespace cds { namespace container { typedef Key key_type; ///< key type typedef T mapped_type; ///< value type + //@cond typedef typename base_class::version_type version_type; + //@endcond key_type const m_key; ///< Key node * m_pNextRemoved; ///< thread-local list of removed node @@ -249,9 +248,9 @@ namespace cds { namespace container { //@endcond }; - /// Option to allow relaxed insert into Bronson et al AVL-tree + /// Option to allow relaxed insert into \ref cds_container_BronsonAVLTreeMap_rcu "Bronson et al AVL-tree" /** - By default, this opton is disabled and the new node is created under its parent lock. + By default, this option is disabled and the new node is created under its parent lock. In this case, it is guaranteed the new node will be attached to its parent. On the other hand, constructing of the new node can be too complex to make it under the lock, that can lead to lock contention. @@ -270,11 +269,11 @@ namespace cds { namespace container { //@endcond }; - /// BronsnAVLTreeMap traits + /// \p BronsonAVLTreeMap traits /** Note that there are two main specialization of Bronson et al AVL-tree: - - pointer-oriented - the tree node stores an user-provided pointer to value: BronsonAVLTreeMap - - data-oriented - the tree node contains a copy of values: BronsonAVLTreeMap where \p T is not a pointer type. + - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value + - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values Depends on tree specialization, different traits member can be used. */ @@ -308,7 +307,7 @@ namespace cds { namespace container { /** The functor used for dispose removed values. The user-provided disposer is used only for pointer-oriented tree specialization - like \p BronsonAVLTreeMap. When the node becomes the rounting node without value, + like \p BronsonAVLTreeMap. When the node becomes the routing node without value, the disposer will be called to signal that the memory for the value can be safely freed. Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator. */ @@ -357,8 +356,8 @@ namespace cds { namespace container { /// Metafunction converting option list to BronsonAVLTreeMap traits /** Note that there are two main specialization of Bronson et al AVL-tree: - - pointer-oriented - the tree node stores an user-provided pointer to value: BronsonAVLTreeMap - - data-oriented - the tree node contains a copy of values: BronsonAVLTreeMap where \p T is not a pointer type. + - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value + - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values Depends on tree specialization, different options can be specified. diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h index a314847f..f9304624 100644 --- a/cds/container/impl/bronson_avltree_map_rcu.h +++ b/cds/container/impl/bronson_avltree_map_rcu.h @@ -14,6 +14,7 @@ namespace cds { namespace container { /** @ingroup cds_nonintrusive_map @ingroup cds_nonintrusive_tree @headerfile cds/container/bronson_avltree_map_rcu.h + @anchor cds_container_BronsonAVLTreeMap_rcu_ptr This is the specialization of \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based Bronson et al AVL-tree" for "key -> value pointer" map. This specialization stores the pointer to user-allocated values instead of the copy -- 2.34.1