--- /dev/null
+//$$CDS-header$$
+
+#ifndef __CDS_CONTAINER_BRONSON_AVLTREE_MAP_RCU_H
+#define __CDS_CONTAINER_BRONSON_AVLTREE_MAP_RCU_H
+
+#include <cds/container/impl/bronson_avltree_map_rcu.h>
+
+namespace cds { namespace container {
+
+ namespace bronson_avltree {
+ //@cond
+ namespace details {
+
+ template <typename Key, typename T, typename Lock>
+ struct value_node : public bronson_avltree::node< Key, T, Lock >
+ {
+ T m_data; // placeholder for data
+ };
+
+ template <typename Key, typename T, typename Traits>
+ struct pointer_oriented_traits: public Traits
+ {
+ struct disposer {
+ template <typename T>
+ void operator()( T * p )
+ {
+ std::allocator().destroy( p );
+ }
+ };
+
+ typedef value_node<Key, T, typename Traits::lock_type > node_type;
+ };
+ } // namespace details
+ //@endcond
+ } // namespace bronson_avltree
+
+ /// Bronson et al AVL-tree (RCU specialization)
+ /** @ingroup cds_nonintrusive_map
+ @ingroup cds_nonintrusive_tree
+ @anchor cds_container_BronsonAVLTreeMap_rcu
+
+ Source:
+ - [2010] N.Bronson, J.Casper, H.Chafi, K.Olukotun "A Practical Concurrent Binary Search Tree"
+
+ bla-bla-bla
+
+ <b>Template arguments</b>:
+ - \p RCU - one of \ref cds_urcu_gc "RCU type"
+ - \p Key - key type
+ - \p T - value type to be stored in tree's nodes.
+ - \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.
+
+ @note Before including <tt><cds/container/bronson_avltree_map_rcu.h></tt> you should include appropriate RCU header file,
+ see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
+ */
+
+ template <
+ typename RCU,
+ typename Key,
+ typename T,
+# ifdef CDS_DOXYGEN_INVOKED
+ typename Traits = bronson_avltree::traits
+#else
+ typename Traits
+#endif
+ >
+ class BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T, Traits >
+ : private BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T*, bronson_avltree::details::pointer_oriented_traits<Key, T, Traits>>
+ {
+ //@cond
+ typedef BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T*, bronson_avltree::details::pointer_oriented_traits<Traits>> base_class;
+ //@endcond
+
+ public:
+ typedef cds::urcu::gc<RCU> gc; ///< RCU Garbage collector
+ typedef Key key_type; ///< type of a key stored in the map
+ typedef T mapped_type; ///< type of value stored in the map
+ typedef Traits traits; ///< Traits template parameter
+
+ typedef typename base_class::key_comparator key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
+ typedef typename traits::item_counter item_counter; ///< Item counting policy
+ typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model option
+ typedef typename traits::allocator allocator_type; ///< allocator for maintaining internal node
+ typedef typename traits::stat stat; ///< internal statistics
+ typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
+ typedef typename traits::back_off back_off; ///< Back-off strategy
+ typedef typename traits::lock_type lock_type; ///< Node lock type
+
+ protected:
+ //@cond
+ typedef typename base_class::alloc_node_type node_type;
+ typedef base_class::node_scoped_lock node_scoped_lock;
+ //@endcond
+
+ public:
+ /// Creates empty map
+ BronsonAVLTreeMap()
+ {}
+
+ /// Destroys the map
+ ~BronsonAVLTreeMap()
+ {}
+
+ /// Inserts new node with key and default value
+ /**
+ The function creates a node with \p key and default value, and then inserts the node created into the map.
+
+ Preconditions:
+ - The \p key_type should be constructible from a value of type \p K.
+ - The \p mapped_type should be default-constructible.
+
+ RCU \p synchronize() can be called. RCU should not be locked.
+
+ Returns \p true if inserting successful, \p false otherwise.
+ */
+ template <typename K>
+ bool insert( K const& key )
+ {
+ //TODO
+ }
+
+ /// Inserts new node
+ /**
+ The function creates a node with copy of \p val value
+ and then inserts the node created into the map.
+
+ Preconditions:
+ - The \p key_type should be constructible from \p key of type \p K.
+ - The \p mapped_type should be constructible from \p val of type \p V.
+
+ RCU \p synchronize() method can be called. RCU should not be locked.
+
+ Returns \p true if \p val is inserted into the map, \p false otherwise.
+ */
+ template <typename K, typename V>
+ bool insert( K const& key, V const& val )
+ {
+ //TODO
+ }
+
+ /// Inserts new node and initialize it by a functor
+ /**
+ This function inserts new node with key \p key and if inserting is successful then it calls
+ \p func functor with signature
+ \code
+ struct functor {
+ void operator()( mapped_type& item );
+ };
+ \endcode
+
+ The key_type should be constructible from value of type \p K.
+
+ The function allows to split creating of new item into two part:
+ - create item from \p key;
+ - insert new item into the map;
+ - if inserting is successful, initialize the value of item by calling \p func functor
+
+ This can be useful if complete initialization of object of \p value_type is heavyweight and
+ it is preferable that the initialization should be completed only if inserting is successful.
+ The functor is called under the node lock.
+
+ RCU \p synchronize() method can be called. RCU should not be locked.
+ */
+ template <typename K, typename Func>
+ bool insert_with( K const& key, Func func )
+ {
+ //TODO
+ }
+
+ /// For key \p key inserts data of type \p mapped_type created in-place from \p args
+ /**
+ Returns \p true if inserting successful, \p false otherwise.
+
+ RCU \p synchronize() method can be called. RCU should not be locked.
+ */
+ template <typename K, typename... Args>
+ bool emplace( K&& key, Args&&... args )
+ {
+ //TODO
+ }
+
+ /// Ensures that the \p key exists in the map
+ /**
+ The operation performs inserting or changing data with lock-free manner.
+
+ If the \p key not found in the map, then the new item created from \p key
+ is inserted into the map (note that in this case the \ref key_type should be
+ constructible from type \p K).
+ Otherwise, the functor \p func is called with item found.
+ The functor \p Func may be a functor:
+ \code
+ struct my_functor {
+ void operator()( bool bNew, mapped_type& item );
+ };
+ \endcode
+
+ with arguments:
+ - \p bNew - \p true if the item has been inserted, \p false otherwise
+ - \p item - item of the tree
+
+ The functor may change any fields of the \p item
+
+ RCU \p synchronize() method can be called. RCU should not be locked.
+
+ Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
+ \p second is \p true if new item has been added or \p false if the item with \p key
+ already is in the tree.
+ */
+ template <typename K, typename Func>
+ std::pair<bool, bool> ensure( K const& key, Func func )
+ {
+ //TODO
+ }
+
+ /// Delete \p key from the map
+ /**
+ RCU \p synchronize() method can be called. RCU should not be locked.
+
+ Return \p true if \p key is found and deleted, \p false otherwise
+ */
+ template <typename K>
+ bool erase( K const& key )
+ {
+ //TODO
+ }
+
+ /// Deletes the item from the map using \p pred predicate for searching
+ /**
+ The function is an analog of \p erase(K const&)
+ but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p Less must imply the same element order as the comparator used for building the map.
+ */
+ template <typename K, typename Less>
+ bool erase_with( K const& key, Less pred )
+ {
+ CDS_UNUSED( pred );
+ //TODO
+ }
+
+ /// Delete \p key from the map
+ /** \anchor cds_nonintrusive_BronsonAVLTreeMap_rcu_erase_func
+
+ The function searches an item with key \p key, calls \p f functor
+ and deletes the item. If \p key is not found, the functor is not called.
+
+ The functor \p Func interface:
+ \code
+ struct extractor {
+ void operator()(mapped_type& item) { ... }
+ };
+ \endcode
+
+ RCU \p synchronize method can be called. RCU should not be locked.
+
+ Return \p true if key is found and deleted, \p false otherwise
+ */
+ template <typename K, typename Func>
+ bool erase( K const& key, Func f )
+ {
+ //TODO
+ }
+
+ /// Deletes the item from the map using \p pred predicate for searching
+ /**
+ The function is an analog of \ref cds_nonintrusive_BronsonAVLTreeMap_rcu_erase_func "erase(K const&, Func)"
+ but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p Less must imply the same element order as the comparator used for building the map.
+ */
+ template <typename K, typename Less, typename Func>
+ bool erase_with( K const& key, Less pred, Func f )
+ {
+ CDS_UNUSED( pred );
+ //TODO
+ }
+
+ /// Extracts an item with minimal key from the map
+ /**
+ Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
+ If the set is empty, returns empty \p exempt_ptr.
+
+ @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
+ It means that the function gets leftmost leaf of the tree and tries to unlink it.
+ During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
+ So, the function returns the item with minimum key at the moment of tree traversing.
+
+ RCU \p synchronize method can be called. RCU should NOT be locked.
+ The function does not free the item.
+ The deallocator will be implicitly invoked when the returned object is destroyed or when
+ its \p release() member function is called.
+ */
+ exempt_ptr extract_min()
+ {
+ //TODO
+ }
+
+ /// Extracts an item with maximal key from the map
+ /**
+ Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
+ If the set is empty, returns empty \p exempt_ptr.
+
+ @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
+ It means that the function gets rightmost leaf of the tree and tries to unlink it.
+ During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
+ So, the function returns the item with maximum key at the moment of tree traversing.
+
+ RCU \p synchronize method can be called. RCU should NOT be locked.
+ The function does not free the item.
+ The deallocator will be implicitly invoked when the returned object is destroyed or when
+ its \p release() is called.
+ @note Before reusing \p result object you should call its \p release() method.
+ */
+ exempt_ptr extract_max()
+ {
+ //TODO
+ }
+
+ /// Extracts an item from the map
+ /**
+ The function searches an item with key equal to \p key in the tree,
+ unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
+ If \p key is not found the function returns an empty \p exempt_ptr.
+
+ RCU \p synchronize method can be called. RCU should NOT be locked.
+ The function does not destroy the item found.
+ The dealloctor will be implicitly invoked when the returned object is destroyed or when
+ its \p release() member function is called.
+ */
+ template <typename Q>
+ exempt_ptr extract( Q const& key )
+ {
+ //TODO
+ }
+
+ /// Extracts an item from the map using \p pred for searching
+ /**
+ The function is an analog of \p extract(exempt_ptr&, Q const&)
+ but \p pred is used for key compare.
+ \p Less has the interface like \p std::less and should meet \ref cds_container_EllenBinTreeSet_rcu_less
+ "predicate requirements".
+ \p pred must imply the same element order as the comparator used for building the map.
+ */
+ template <typename Q, typename Less>
+ exempt_ptr extract_with( Q const& val, Less pred )
+ {
+ CDS_UNUSED( pred );
+ //TODO
+ }
+
+ /// Find the key \p key
+ /**
+ The function searches the item with key equal to \p key and calls the functor \p f for item found.
+ The interface of \p Func functor is:
+ \code
+ struct functor {
+ void operator()( mapped_type& item );
+ };
+ \endcode
+ where \p item is the item found.
+ The functor is called under node-level lock.
+
+ The function applies RCU lock internally.
+
+ The function returns \p true if \p key is found, \p false otherwise.
+ */
+ template <typename K, typename Func>
+ bool find( K const& key, Func f )
+ {
+ return base_class::find( key, f );
+ }
+
+ /// Finds the key \p val using \p pred predicate for searching
+ /**
+ The function is an analog of \p find(K const&, Func)
+ but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p Less must imply the same element order as the comparator used for building the map.
+ */
+ template <typename K, typename Less, typename Func>
+ bool find_with( K const& key, Less pred, Func f )
+ {
+ return base_class::find_with( key, pred, f );
+ }
+
+ /// Find the key \p key
+ /**
+ The function searches the item with key equal to \p key
+ and returns \p true if it is found, and \p false otherwise.
+
+ The function applies RCU lock internally.
+ */
+ template <typename K>
+ bool find( K const& key )
+ {
+ return base_class::find( key );
+ }
+
+ /// Finds the key \p val using \p pred predicate for searching
+ /**
+ The function is an analog of \p find(K const&)
+ but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p Less must imply the same element order as the comparator used for building the map.
+ */
+ template <typename K, typename Less>
+ bool find_with( K const& key, Less pred )
+ {
+ return base_class::find_with( key, pred );
+ }
+
+ /// Finds \p key and return the item found
+ /**
+ The function searches the item with key equal to \p key and returns the pointer to item found.
+ If \p key is not found it returns \p nullptr.
+
+ RCU should be locked before call the function.
+ Returned pointer is valid while RCU is locked.
+ */
+ template <typename Q>
+ mapped_type * get( Q const& key ) const
+ {
+ //TODO
+ }
+
+ /// Finds \p key with \p pred predicate and return the item found
+ /**
+ The function is an analog of \p get(Q const&)
+ but \p pred is used for comparing the keys.
+
+ \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type
+ and \p Q in any order.
+ \p pred must imply the same element order as the comparator used for building the map.
+ */
+ template <typename Q, typename Less>
+ mapped_type * get_with( Q const& key, Less pred ) const
+ {
+ CDS_UNUSED( pred );
+ //TODO
+ }
+
+ /// Clears the map
+ void clear()
+ {
+ base_class::clear();
+ }
+
+ /// Checks if the map is empty
+ bool empty() const
+ {
+ return base_class::empty();
+ }
+
+ /// Returns item count in the map
+ /**
+ Only leaf nodes containing user data are counted.
+
+ The value returned depends on item counter type provided by \p Traits template parameter.
+ If it is \p atomicity::empty_item_counter this function always returns 0.
+
+ The function is not suitable for checking the tree emptiness, use \p empty()
+ member function for this purpose.
+ */
+ size_t size() const
+ {
+ return base_class::size();
+ }
+
+ /// Returns const reference to internal statistics
+ stat const& statistics() const
+ {
+ return base_class::statistics();
+ }
+
+ /// Checks internal consistency (not atomic, not thread-safe)
+ /**
+ The debugging function to check internal consistency of the tree.
+ */
+ bool check_consistency() const
+ {
+ return base_class::check_consistency();
+ }
+
+ };
+}} // namespace cds::container
+
+#endif // #ifndef __CDS_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
#define __CDS_CONTAINER_DETAILS_BASE_H
#include <cds/intrusive/details/base.h>
-#include <cds/details/allocator.h>
namespace cds {
--- /dev/null
+//$$CDS-header$$
+
+#ifndef __CDS_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
+#define __CDS_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
+
+#include <cds/container/details/base.h>
+#include <cds/opt/compare.h>
+#include <cds/urcu/options.h>
+#include <cds/lock/spinlock.h>
+
+namespace cds { namespace container {
+
+ /// BronsonAVLTree related declarations
+ namespace bronson_avltree {
+
+ template <typename Key, typename T>
+ struct node;
+
+ //@cond
+ template <typename Key, typename T, typename Lock>
+ struct link
+ {
+ typedef node<Key, T> node_type;
+ typedef uint64_t version_type;
+ typedef Lock lock_type;
+
+ enum class version_flags : version_type
+ {
+ unlinked = 1,
+ growing = 2,
+ shrinking = 4,
+ grow_count_increment = 1 << 3,
+ grow_count_mask = 0xff << 3,
+ shrink_count_increment = 1 << 11,
+ ignore_grow = ~(growing | grow_count_mask)
+ };
+
+ atomics::atomic< int > m_nHeight; ///< Node height
+ atomics::atomic<version_type> m_nVersion; ///< Version bits
+ atomics::atomic<node_type *> m_pParent; ///< Parent node
+ atomics::atomic<node_type *> m_pLeft; ///< Left child
+ atomics::atomic<node_type *> m_pRight; ///< Right child
+ lock_type m_Lock; ///< Node-level lock
+
+ atomics::atomic<node_type *>& child( int nDirection ) const
+ {
+ assert( nDirection != 0 );
+ return nDirection < 0 ? m_pLeft : m_pRight;
+ }
+
+ version_type version( atomics::memory_order order ) const
+ {
+ return m_nVersion.load( order );
+ }
+
+ template <typename BackOff>
+ void wait_until_shrink_completed( atomics::memory_order order ) const
+ {
+ BackOff bkoff;
+ while ( version( order ) & version_flags::shrinking )
+ bkoff();
+ }
+ };
+
+ template <typename Key, typename T, typename Lock>
+ struct node : public link< Key, T, Lock >
+ {
+ typedef Key key_type;
+ typedef T mapped_type;
+ typedef link< key_type, mapped_type, Lock > base_class;
+
+ key_type const m_key;
+ atomics::atomic<mapped_type *> m_pValue;
+
+ template <typename Q>
+ node( Q&& key )
+ : m_key( std::forward<Q>(key) )
+ , m_pValue( nullptr )
+ {}
+
+ template <typename Q>
+ node( Q&& key, mapped_type * pVal )
+ : m_key( std::forward<Q>(key) )
+ , m_pValue( pVal )
+ {}
+
+ T * value( atomics::memory_order order ) const
+ {
+ return m_pValue.load( order );
+ }
+ };
+ //@endcond
+
+ /// BronsonAVLTreeMap internal statistics
+ template <typename Counter = cds::atomicity::event_counter>
+ struct stat {
+ typedef Counter event_counter; ///< Event counter type
+
+ event_counter m_nFindSuccess; ///< Count of success \p find() call
+ event_counter m_nFindFailed; ///< Count of failed \p find() call
+ event_counter m_nFindRetry; ///< Count of retries during \p find()
+ event_counter m_nFindWaitShrinking; ///< Count of waiting until shrinking completed duting \p find() call
+
+ //@cond
+ void onFindSuccess() { ++m_nFindSuccess ; }
+ void onFindFailed() { ++m_nFindFailed ; }
+ void onFindRetry() { ++m_nFindRetry ; }
+ void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
+
+ //@endcond
+ };
+
+ /// BronsonAVLTreeMap empty statistics
+ struct empty_stat {
+ //@cond
+ void onFindSuccess() const {}
+ void onFindFailed() const {}
+ void onFindRetry() const {}
+ void onFindWaitShrinking() const {}
+ //@endcond
+ };
+
+ /// BronsnAVLTreeMap 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: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
+ - data-oriented - the tree node contains a copy of values: <tt>BronsonAVLTreeMap<GC, Key, T, Traits> </tt> where \p T is not a pointer type.
+
+ Depends on tree specialization, different traits member can be used.
+ */
+ struct traits
+ {
+ /// Key comparison functor
+ /**
+ No default functor is provided. If the option is not specified, the \p less is used.
+
+ See \p cds::opt::compare option description for functor interface.
+
+ You should provide \p compare or \p less functor.
+ */
+ typedef opt::none compare;
+
+ /// Specifies binary predicate used for key compare.
+ /**
+ See \p cds::opt::less option description for predicate interface.
+
+ You should provide \p compare or \p less functor.
+ */
+ typedef opt::none less;
+
+ /// Allocator for internal node
+ typedef CDS_DEFAULT_ALLOCATOR allocator;
+
+ /// Disposer (only for pointer-oriented tree specialization)
+ /**
+ The functor used for dispose removed values.
+ The user-provided disposer is used only for pointer-oriented tree specialization
+ like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting 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::v::delete_disposer "cds::container::opt::v::delete_disposer" which calls \p delete operator.
+ */
+ typedef opt::v::delete_disposer disposer;
+
+ /// Node lock
+ typedef cds::SpinLock lock_type;
+
+ /// Item counter
+ /**
+ The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
+ To enable it use \p atomicity::item_counter
+ */
+ typedef atomicity::empty_item_counter item_counter;
+
+ /// C++ memory ordering model
+ /**
+ List of available memory ordering see \p opt::memory_model
+ */
+ typedef opt::v::relaxed_ordering memory_model;
+
+ /// Internal statistics
+ /**
+ By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
+ To enable it use \p ellen_bintree::stat.
+ */
+ typedef empty_stat stat;
+
+ /// Back-off strategy
+ typedef cds::backoff::empty back_off;
+
+ /// RCU deadlock checking policy (only for \ref cds_intrusive_BronsonAVLTree_rcu "RCU-based BronsonAVLTree")
+ /**
+ List of available options see \p opt::rcu_check_deadlock
+ */
+ typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
+
+ //@cond
+ // Internal traits, not for direct usage
+ typedef opt::none node_type;
+ //@endcond
+ };
+
+ /// 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: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
+ - data-oriented - the tree node contains a copy of values: <tt>BronsonAVLTreeMap<GC, Key, T, Traits> </tt> where \p T is not a pointer type.
+
+ Depends on tree specialization, different options can be specified.
+
+ \p Options are:
+ - \p opt::compare - key compare functor. No default functor is provided.
+ If the option is not specified, \p %opt::less is used.
+ - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
+ - \p opt::allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
+ - \ref cds::intusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
+ The user-provided disposer is used only for pointer-oriented tree specialization
+ like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting 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::v::delete_disposer "cds::container::opt::v::delete_disposer" which calls \p delete operator.
+ Due the nature of GC schema the disposer may be called asynchronously.
+ - \p opt::lock_type - node lock type, default is \p cds::SpinLock
+ - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
+ To enable it use \p atomicity::item_counter
+ - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
+ or \p opt::v::sequential_consistent (sequentially consisnent memory model).
+ - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
+ To enable statistics use \p \p bronson_avltree::stat
+ - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
+ - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
+ */
+ template <typename... Options>
+ struct make_traits {
+# ifdef CDS_DOXYGEN_INVOKED
+ typedef implementation_defined type ; ///< Metafunction result
+# else
+ typedef typename cds::opt::make_options<
+ typename cds::opt::find_type_traits< traits, Options... >::type
+ ,Options...
+ >::type type;
+# endif
+ };
+
+
+ } // namespace bronson_avltree
+
+ // Forwards
+ template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
+ class BronsonAVLTreeMap;
+
+}} // namespace cds::container
+
+
+#endif // #ifndef __CDS_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
RCU \p synchronize() method can be called. RCU should not be locked.
*/
template <typename K, typename Func>
- bool insert_with( const K& key, Func func )
+ bool insert_with( K const& key, Func func )
{
scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key ));
if ( base_class::insert( *pNode, [&func]( leaf_node& item ) { func( item.m_Value ); } )) {
with arguments:
- \p bNew - \p true if the item has been inserted, \p false otherwise
- - \p item - item of the list
+ - \p item - item of the tree
The functor may change any fields of the \p item.second that is \ref value_type.
RCU \p synchronize() method can be called. RCU should not be locked.
- Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
- \p second is true if new item has been added or \p false if the item with \p key
- already is in the list.
+ Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
+ \p second is \p true if new item has been added or \p false if the item with \p key
+ already is in the tree.
@warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
*/
--- /dev/null
+//$$CDS-header$$
+
+#ifndef __CDS_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
+#define __CDS_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
+
+#include <cds/container/details/bronson_avltree_base.h>
+#include <cds/urcu/details/check_deadlock.h>
+
+namespace cds { namespace container {
+
+ template <
+ typename RCU,
+ typename Key,
+ typename T,
+# ifdef CDS_DOXYGEN_INVOKED
+ typename Traits = bronson_avltree::traits
+#else
+ typename Traits
+#endif
+ >
+ class BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T*, Traits >
+ {
+ public:
+ typedef cds::urcu::gc<RCU> gc; ///< RCU Garbage collector
+ typedef Key key_type; ///< type of a key stored in the map
+ typedef T * mapped_type; ///< type of value stored in the map
+ typedef Traits traits; ///< Traits template parameter
+
+# ifdef CDS_DOXYGEN_INVOKED
+ typedef implementation_defined key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
+# else
+ typedef typename opt::details::make_comparator< key_type, traits >::type key_comparator;
+#endif
+ typedef typename traits::item_counter item_counter; ///< Item counting policy
+ typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model option
+ typedef typename traits::allocator allocator_type; ///< allocator for maintaining internal node
+ typedef typename traits::stat stat; ///< internal statistics
+ typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
+ typedef typename traits::back_off back_off; ///< Back-off strategy
+ typedef typename traits::disposer disposer; ///< Value disposer
+ typedef typename traits::lock_type lock_type; ///< Node lock type
+
+ protected:
+ //@cond
+ typedef bronson_avltree::node< key_type, mapped_type, lock_type > node_type;
+
+ typedef typename std::conditional <
+ std::is_same< typename traits::node_type, opt::none >::value,
+ bronson_avltree::node< key_type, mapped_type, lock_type >,
+ typename traits::node_type
+ >::type alloc_node_type;
+
+ typedef typename allocator_type::template rebind<alloc_node_type>::other memory_allocator;
+
+ typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock > check_deadlock_policy;
+
+ enum class find_result
+ {
+ not_found,
+ found,
+ retry,
+ };
+
+ class node_scoped_lock
+ {
+ node_type * m_pNode;
+ public:
+ node_scoped_lock( node_type * pNode )
+ : m_pNode( pNode )
+ {
+ pNode->m_Lock.lock();
+ }
+
+ ~node_scoped_lock()
+ {
+ m_pNode->m_Lock.unlock();
+ }
+ };
+
+ //@endcond
+
+ protected:
+ //@cond
+ template <typename K>
+ node_type * alloc_node( K&& key )
+ {
+ alloc_node_type * pNode = memory_allocator().allocate( 1 );
+ return new (static_cast<node_type *>(pNode)) node_type( std::forward<K>( key ) );
+ }
+
+ template <typename K>
+ node_type * alloc_node( K&& key, mapped_type * pVal )
+ {
+ alloc_node_type * pNode = memory_allocator().allocate( 1 );
+ return new (static_cast<node_type *>(pNode)) node_type( std::forward<K>( key ), pVal );
+ }
+
+ //@endcond
+
+ protected:
+ //@cond
+ typename node_type::base_class m_Root;
+ node_type * m_pRoot;
+ item_counter m_ItemCounter;
+ mutable stat m_stat;
+ //@endcond
+
+ public:
+ /// Creates empty map
+ BronsonAVLTreeMap()
+ : m_pRoot( static_cast<node_type *>(&m_Root) )
+ {}
+
+ /// Destroys the map
+ ~BronsonAVLTreeMap()
+ {
+ unsafe_clear();
+ }
+
+ /// Inserts new node
+ /**
+ The \p key_type should be constructible from a value of type \p K.
+
+ RCU \p synchronize() can be called. RCU should not be locked.
+
+ Returns \p true if inserting successful, \p false otherwise.
+ */
+ template <typename K>
+ bool insert( K const& key, mapped_type * pVal )
+ {
+ //TODO
+ }
+
+ /// Ensures that the \p key exists in the map
+ /**
+ The operation performs inserting or changing data with lock-free manner.
+
+ If the \p key not found in the map, then the new item created from \p key
+ is inserted into the map (note that in this case the \ref key_type should be
+ constructible from type \p K).
+ Otherwise, the value is changed to \p pVal.
+
+ RCU \p synchronize() method can be called. RCU should not be locked.
+
+ Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
+ \p second is \p true if new item has been added or \p false if the item with \p key
+ already is in the tree.
+ */
+ template <typename K, typename Func>
+ std::pair<bool, bool> ensure( K const& key, mapped_type * pVal )
+ {
+ //TODO
+ }
+
+ /// Delete \p key from the map
+ /**
+ RCU \p synchronize() method can be called. RCU should not be locked.
+
+ Return \p true if \p key is found and deleted, \p false otherwise
+ */
+ template <typename K>
+ bool erase( K const& key )
+ {
+ //TODO
+ }
+
+ /// Deletes the item from the map using \p pred predicate for searching
+ /**
+ The function is an analog of \p erase(K const&)
+ but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p Less must imply the same element order as the comparator used for building the map.
+ */
+ template <typename K, typename Less>
+ bool erase_with( K const& key, Less pred )
+ {
+ CDS_UNUSED( pred );
+ //TODO
+ }
+
+ /// Delete \p key from the map
+ /**
+ The function searches an item with key \p key, calls \p f functor
+ and deletes the item. If \p key is not found, the functor is not called.
+
+ The functor \p Func interface:
+ \code
+ struct extractor {
+ void operator()(mapped_type& item) { ... }
+ };
+ \endcode
+
+ RCU \p synchronize method can be called. RCU should not be locked.
+
+ Return \p true if key is found and deleted, \p false otherwise
+ */
+ template <typename K, typename Func>
+ bool erase( K const& key, Func f )
+ {
+ //TODO
+ }
+
+ /// Deletes the item from the map using \p pred predicate for searching
+ /**
+ The function is an analog of \p erase(K const&, Func)
+ but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p Less must imply the same element order as the comparator used for building the map.
+ */
+ template <typename K, typename Less, typename Func>
+ bool erase_with( K const& key, Less pred, Func f )
+ {
+ CDS_UNUSED( pred );
+ //TODO
+ }
+
+ /// Extracts an item with minimal key from the map
+ /**
+ Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
+ If the set is empty, returns empty \p exempt_ptr.
+
+ @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
+ It means that the function gets leftmost leaf of the tree and tries to unlink it.
+ During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
+ So, the function returns the item with minimum key at the moment of tree traversing.
+
+ RCU \p synchronize method can be called. RCU should NOT be locked.
+ The function does not free the item.
+ The deallocator will be implicitly invoked when the returned object is destroyed or when
+ its \p release() member function is called.
+ */
+ exempt_ptr extract_min()
+ {
+ //TODO
+ }
+
+ /// Extracts an item with maximal key from the map
+ /**
+ Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
+ If the set is empty, returns empty \p exempt_ptr.
+
+ @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
+ It means that the function gets rightmost leaf of the tree and tries to unlink it.
+ During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
+ So, the function returns the item with maximum key at the moment of tree traversing.
+
+ RCU \p synchronize method can be called. RCU should NOT be locked.
+ The function does not free the item.
+ The deallocator will be implicitly invoked when the returned object is destroyed or when
+ its \p release() is called.
+ @note Before reusing \p result object you should call its \p release() method.
+ */
+ exempt_ptr extract_max()
+ {
+ //TODO
+ }
+
+ /// Extracts an item from the map
+ /**
+ The function searches an item with key equal to \p key in the tree,
+ unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
+ If \p key is not found the function returns an empty \p exempt_ptr.
+
+ RCU \p synchronize method can be called. RCU should NOT be locked.
+ The function does not destroy the item found.
+ The dealloctor will be implicitly invoked when the returned object is destroyed or when
+ its \p release() member function is called.
+ */
+ template <typename Q>
+ exempt_ptr extract( Q const& key )
+ {
+ //TODO
+ }
+
+ /// Extracts an item from the map using \p pred for searching
+ /**
+ The function is an analog of \p extract(exempt_ptr&, Q const&)
+ but \p pred is used for key compare.
+ \p Less has the interface like \p std::less and should meet \ref cds_container_EllenBinTreeSet_rcu_less
+ "predicate requirements".
+ \p pred must imply the same element order as the comparator used for building the map.
+ */
+ template <typename Q, typename Less>
+ exempt_ptr extract_with( Q const& val, Less pred )
+ {
+ CDS_UNUSED( pred );
+ //TODO
+ }
+
+ /// Find the key \p key
+ /**
+ The function searches the item with key equal to \p key and calls the functor \p f for item found.
+ The interface of \p Func functor is:
+ \code
+ struct functor {
+ void operator()( mapped_type& item );
+ };
+ \endcode
+ where \p item is the item found.
+ The functor is called under node-level lock.
+
+ The function applies RCU lock internally.
+
+ The function returns \p true if \p key is found, \p false otherwise.
+ */
+ template <typename K, typename Func>
+ bool find( K const& key, Func f )
+ {
+ return do_find( key, key_comparator(), [&f]( node_type * pNode ) -> bool {
+ node_scoped_lock l( pNode );
+ if ( pNode->m_pValue ) {
+ f( *pNode->m_pValue );
+ return true;
+ }
+ return false;
+ });
+ }
+
+ /// Finds the key \p val using \p pred predicate for searching
+ /**
+ The function is an analog of \p find(K const&, Func)
+ but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p Less must imply the same element order as the comparator used for building the map.
+ */
+ template <typename K, typename Less, typename Func>
+ bool find_with( K const& key, Less pred, Func f )
+ {
+ CDS_UNUSED( pred );
+ return do_find( key, opt::details::make_comparator_from_less<Less>(), [&f]( node_type * pNode ) -> bool {
+ node_scoped_lock l( pNode );
+ if ( pNode->m_pValue ) {
+ f( *pNode->m_pValue );
+ return true;
+ }
+ return false;
+ } );
+
+ //TODO
+ }
+
+ /// Find the key \p key
+ /**
+ The function searches the item with key equal to \p key
+ and returns \p true if it is found, and \p false otherwise.
+
+ The function applies RCU lock internally.
+ */
+ template <typename K>
+ bool find( K const& key )
+ {
+ return do_find( key, key_comparator(), []( node_type * ) -> bool { return true; });
+ }
+
+ /// Finds the key \p val using \p pred predicate for searching
+ /**
+ The function is an analog of \p find(K const&)
+ but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p Less must imply the same element order as the comparator used for building the map.
+ */
+ template <typename K, typename Less>
+ bool find_with( K const& key, Less pred )
+ {
+ CDS_UNUSED( pred );
+ return do_find( key, opt::details::make_comparator_from_less<Less>(), []( node_type * ) -> bool { return true; } );
+ }
+
+ /// Finds \p key and return the item found
+ /**
+ The function searches the item with key equal to \p key and returns the pointer to item found.
+ If \p key is not found it returns \p nullptr.
+
+ RCU should be locked before call the function.
+ Returned pointer is valid while RCU is locked.
+ */
+ template <typename Q>
+ mapped_type * get( Q const& key ) const
+ {
+ //TODO
+ }
+
+ /// Finds \p key with \p pred predicate and return the item found
+ /**
+ The function is an analog of \p get(Q const&)
+ but \p pred is used for comparing the keys.
+
+ \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type
+ and \p Q in any order.
+ \p pred must imply the same element order as the comparator used for building the map.
+ */
+ template <typename Q, typename Less>
+ mapped_type * get_with( Q const& key, Less pred ) const
+ {
+ CDS_UNUSED( pred );
+ //TODO
+ }
+
+ /// Clears the tree (thread safe, not atomic)
+ /**
+ The function unlink all items from the tree.
+ The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
+ this sequence
+ \code
+ set.clear();
+ assert( set.empty() );
+ \endcode
+ the assertion could be raised.
+
+ For each node the \ref disposer will be called after unlinking.
+
+ RCU \p synchronize method can be called. RCU should not be locked.
+ */
+ void clear()
+ {
+ for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min() )
+ ep.release();
+ }
+
+ /// Clears the tree (not thread safe)
+ /**
+ This function is not thread safe and may be called only when no other thread deals with the tree.
+ The function is used in the tree destructor.
+ */
+ void unsafe_clear()
+ {
+ //TODO
+ }
+
+ /// Checks if the map is empty
+ bool empty() const
+ {
+ return m_Root.m_pRight.load( memory_model::memory_order_relaxed ) == nullptr;
+ }
+
+ /// Returns item count in the map
+ /**
+ Only leaf nodes containing user data are counted.
+
+ The value returned depends on item counter type provided by \p Traits template parameter.
+ If it is \p atomicity::empty_item_counter this function always returns 0.
+
+ The function is not suitable for checking the tree emptiness, use \p empty()
+ member function for this purpose.
+ */
+ size_t size() const
+ {
+ return m_ItemCounter;
+ }
+
+ /// Returns const reference to internal statistics
+ stat const& statistics() const
+ {
+ return m_Stat;
+ }
+
+ /// Checks internal consistency (not atomic, not thread-safe)
+ /**
+ The debugging function to check internal consistency of the tree.
+ */
+ bool check_consistency() const
+ {
+ //TODO
+ }
+
+ protected:
+ //@cond
+ template <typename Q, typename Compare, typename Func>
+ bool do_find( Q& key, Compare cmp, Func f ) const
+ {
+ find_result result;
+ {
+ rcu_lock l;
+ result = try_find( key, cmp, f, m_pRoot, 1, 0 );
+ }
+ assert( result != find_result::retry );
+ return result == find_result::found;
+ }
+
+ template <typename Q, typename Compare, typename Func>
+ find_result try_find( Q const& key, Compare cmp, Func f, node_type * pNode, int nDir, typename node_type::version_type nVersion ) const
+ {
+ assert( gc::is_locked() );
+ assert( pNode );
+
+ while ( true ) {
+ node_type * pChild = pNode->child( nDir ).load( memory_model::memory_order_relaxed );
+ if ( !pChild ) {
+ if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion ) {
+ m_stat.onFindRetry();
+ return find_result::retry;
+ }
+
+ m_stat.onFindFailed();
+ return find_result::not_found;
+ }
+
+ int nCmp = cmp( key, pChild->m_key );
+ if ( nCmp == 0 ) {
+ if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) {
+ // key found
+ if ( f( pChild ) ) {
+ m_stat.onFindSuccess();
+ return find_result::found;
+ }
+ }
+
+ m_stat.onFindFailed();
+ return find_result::not_found;
+ }
+
+ typename node_type::version_type nChildVersion = pChild->version( memory_model::memory_order_relaxed );
+ if ( nChildVersion & node_type::version_flags::shrinking ) {
+ m_stat.onFindWaitShrinking();
+ pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
+
+ if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion ) {
+ m_stat.onFindRetry();
+ return find_result::retry;
+ }
+ }
+ else if ( nChildVersion != node_type::version_flags::unlinked ) {
+
+ if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion ) {
+ m_stat.onFindRetry();
+ return find_result::retry;
+ }
+
+ find_result found = try_find( key, cmp, f, pChild, nCmp, nChildVersion );
+ if ( found != find_result::retry )
+ return found;
+ }
+ }
+ }
+ //@endcond
+
+ };
+}} // namespace cds::container
+
+#endif // #ifndef __CDS_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef __CDS_INTRUSIVE_BRONSON_AVLTREE_RCU_H
-#define __CDS_INTRUSIVE_BRONSON_AVLTREE_RCU_H
-
-#include <cds/intrusive/details/bronson_avltree_base.h>
-#include <cds/opt/compare.h>
-#include <cds/urcu/details/check_deadlock.h>
-#include <cds/urcu/exempt_ptr.h>
-
-namespace cds { namespace intrusive {
-
- /// Bronson et al AVL-tree (RCU specialization)
- /** @ingroup cds_intrusive_map
- @ingroup cds_intrusive_tree
- @anchor cds_intrusive_BronsonAVLTree_rcu
-
- Source:
- - [2010] N.Bronson, J.Casper, H.Chafi, K.Olukotun "A Practical Concurrent Binary Search Tree"
-
- bla-bla-bla
-
- <b>Template arguments</b>:
- - \p RCU - one of \ref cds_urcu_gc "RCU type"
- - \p T - type to be stored in tree's nodes. The type must be based on \p bronson_avltree::node
- (for \p bronson_avltree::base_hook) or it must have a member of type \p bronson_avltree::node
- (for \p bronson_avltree::member_hook).
- - \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.
-
- @note Before including <tt><cds/intrusive/bronson_avltree_rcu.h></tt> you should include appropriate RCU header file,
- see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
- */
- template <
- class RCU,
- typename T,
-# ifdef CDS_DOXYGEN_INVOKED
- class Traits = bronson_avltree::traits
-# else
- class Traits
-# endif
- >
- class BronsonAVLTree < cds::urcu::gc<RCU>, T, Traits >
- {
- public:
- typedef cds::urcu::gc<RCU> gc; ///< RCU Garbage collector
- typedef T value_type; ///< type of value stored in the tree
- typedef Traits traits; ///< Traits template parameter
-
- typedef typename traits::hook hook; ///< hook type
- typedef typename hook::node_type node_type; ///< node type
-
- typedef typename traits::disposer disposer; ///< node disposer
- typedef typename traits::value_cleaner value_cleaner; ///< the functor to clean node's field except key field, see bronson_avltree::traits::value_cleaner
- typedef typename traits::back_off back_off; ///< back-off strategy
- typedef typename traits::item_counter item_counter; ///< Item counting policy used
- typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
- typedef typename traits::stat stat; ///< internal statistics type
- typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
-
- public:
- using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void >; ///< pointer to extracted node
- typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
-# ifdef CDS_DOXYGEN_INVOKED
- typedef implementation_defined key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
-# else
- typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
-#endif
-
- protected:
- //@cond
- typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< Node traits
- typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock > check_deadlock_policy;
- //@endcond
-
- protected:
- //@cond
- bronson_avltree::base_node< node_type > m_Root; ///< Tree root
- node_type * m_pRoot; ///< pointer to root node
-
- item_counter m_ItemCounter; ///< item counter
- mutable stat m_Stat; ///< internal statistics
- //@endcond
-
- public:
- /// Default ctor creates empty tree
- BronsonAVLTree()
- : m_pRoot(static_cast<node_type *>( &m_Root ))
- {}
-
- /// Cleans the tree
- ~BronsonAVLTree()
- {
- unsafe_clean();
- }
-
- /// Inserts new node
- /**
- The function inserts \p val in the tree if it does not contain
- an item with key equal to \p val.
-
- The function applies RCU lock internally.
-
- Returns \p true if \p val is placed into the tree, \p false otherwise.
- */
- bool insert( value_type& val )
- {
- return insert( val, []( value_type& ) {} );
- }
-
- /// Inserts new node
- /**
- This function is intended for derived non-intrusive containers.
-
- The function allows to split creating of new item into two part:
- - create item with key only
- - insert new item into the tree
- - if inserting is success, calls \p f functor to initialize value-field of \p val.
-
- The functor signature is:
- \code
- void func( value_type& val );
- \endcode
- where \p val is the item inserted. User-defined functor \p f is called under node-level spin-lock.
- The user-defined functor is called only if the inserting is success.
-
- RCU \p synchronize method can be called. RCU should not be locked.
- */
- template <typename Func>
- bool insert( value_type& val, Func f )
- {
- //TODO
- }
-
- /// Ensures that the \p val exists in the tree
- /**
- The operation performs inserting or changing data with lock-free manner.
-
- If the item \p val is not found in the tree, then \p val is inserted into the tree.
- Otherwise, the functor \p func is called with item found.
- The functor signature is:
- \code
- void func( bool bNew, value_type& item, value_type& val );
- \endcode
- with arguments:
- - \p bNew - \p true if the item has been inserted, \p false otherwise
- - \p item - item of the tree
- - \p val - argument \p val passed into the \p ensure function
- If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
- refer to the same thing.
-
- The functor can change non-key fields of the \p item.
- The functor is called under node-level spin-lock.
-
- RCU \p synchronize method can be called. RCU should not be locked.
-
- Returns <tt>std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
- \p second is \p true if new item has been added or \p false if the item with \p key
- already is in the tree.
- */
- template <typename Func>
- std::pair<bool, bool> ensure( value_type& val, Func func )
- {
- //TODO
- }
-
- /// Unlinks the item \p val from the tree
- /**
- The function searches the item \p val in the tree and unlink it from the tree
- if it is found and is equal to \p val.
-
- Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
- and deletes the item found. \p %unlink() finds an item by key and deletes it
- only if \p val is an item of the tree, i.e. the pointer to item found
- is equal to <tt> &val </tt>.
-
- RCU \p synchronize method can be called. RCU should not be locked.
-
- The \ref disposer specified in \p Traits class template parameter is called
- by garbage collector \p GC asynchronously.
-
- The function returns \p true if success and \p false otherwise.
- */
- bool unlink( value_type& val )
- {
- //TODO
- }
-
- /// Deletes the item from the tree
- /** \anchor cds_intrusive_BronsonAVLTree_rcu_erase
- The function searches an item with key equal to \p key in the tree,
- unlinks it from the tree, and returns \p true.
- If the item with key equal to \p key is not found the function return \p false.
-
- Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
-
- RCU \p synchronize method can be called. RCU should not be locked.
- */
- template <typename Q>
- bool erase( const Q& key )
- {
- //TODO
- }
-
- /// Delete the item from the tree with comparing functor \p pred
- /**
- The function is an analog of \ref cds_intrusive_BronsonAVLTree_rcu_erase "erase(Q const&)"
- but \p pred predicate is used for key comparing.
- \p Less has the interface like \p std::less.
- \p pred must imply the same element order as the comparator used for building the tree.
- */
- template <typename Q, typename Less>
- bool erase_with( const Q& key, Less pred )
- {
- CDS_UNUSED( pred );
- //TODO
- }
-
- /// Deletes the item from the tree
- /** \anchor cds_intrusive_BronsonAVLTree_rcu_erase_func
- The function searches an item with key equal to \p key in the tree,
- call \p f functor with item found, unlinks it from the tree, and returns \p true.
- The \ref disposer specified in \p Traits class template parameter is called
- by garbage collector \p GC asynchronously.
-
- The \p Func interface is
- \code
- struct functor {
- void operator()( value_type const& item );
- };
- \endcode
-
- If the item with key equal to \p key is not found the function return \p false.
-
- Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
-
- RCU \p synchronize method can be called. RCU should not be locked.
- */
- template <typename Q, typename Func>
- bool erase( Q const& key, Func f )
- {
- //TODO
- }
-
- /// Delete the item from the tree with comparing functor \p pred
- /**
- The function is an analog of \ref cds_intrusive_BronsonAVLTree_rcu_erase_func "erase(Q const&, Func)"
- but \p pred predicate is used for key comparing.
- \p Less has the interface like \p std::less.
- \p pred must imply the same element order as the comparator used for building the tree.
- */
- template <typename Q, typename Less, typename Func>
- bool erase_with( Q const& key, Less pred, Func f )
- {
- CDS_UNUSED( pred );
- //TODO
- }
-
- /// Extracts an item with minimal key from the tree
- /**
- The function searches an item with minimal key, unlinks it, and returns
- \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
- If the tree is empty the function returns empty \p exempt_ptr.
-
- @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
- It means that the function gets leftmost leaf of the tree and tries to unlink it.
- During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
- So, the function returns the item with minimum key at the moment of tree traversing.
-
- RCU \p synchronize method can be called. RCU should NOT be locked.
- The function does not call the disposer for the item found.
- The disposer will be implicitly invoked when the returned object is destroyed or when
- its \p release() member function is called.
- */
- exempt_ptr extract_min()
- {
- return exempt_ptr( extract_min_() );
- }
-
- /// Extracts an item with maximal key from the tree
- /**
- The function searches an item with maximal key, unlinks it, and returns
- \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
- If the tree is empty the function returns empty \p exempt_ptr.
-
- @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
- It means that the function gets rightmost leaf of the tree and tries to unlink it.
- During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
- So, the function returns the item with maximum key at the moment of tree traversing.
-
- RCU \p synchronize method can be called. RCU should NOT be locked.
- The function does not call the disposer for the item found.
- The disposer will be implicitly invoked when the returned object is destroyed or when
- its \p release() member function is called.
- */
- exempt_ptr extract_max()
- {
- return exempt_ptr( extract_max_() );
- }
-
- /// Extracts an item from the tree
- /** \anchor cds_intrusive_BronsonAVLTree_rcu_extract
- The function searches an item with key equal to \p key in the tree,
- unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
- If the item with the key equal to \p key is not found the function returns empty \p exempt_ptr.
-
- RCU \p synchronize method can be called. RCU should NOT be locked.
- The function does not call the disposer for the item found.
- The disposer will be implicitly invoked when the returned object is destroyed or when
- its \p release() member function is called.
- */
- template <typename Q>
- exempt_ptr extract( Q const& key )
- {
- return exempt_ptr( extract_( key, key_comparator() ) );
- }
-
- /// Extracts an item from the set using \p pred for searching
- /**
- The function is an analog of \ref cds_intrusive_BronsonAVLTree_rcu_extract "extract(exempt_ptr&, Q const&)"
- but \p pred is used for key compare.
- \p Less has the interface like \p std::less.
- \p pred must imply the same element order as the comparator used for building the tree.
- */
- template <typename Q, typename Less>
- exempt_ptr extract_with( Q const& key, Less pred )
- {
- return exempt_ptr( extract_with_( key, pred ));
- }
-
- /// Finds the key \p key
- /** @anchor cds_intrusive_BronsonAVLTree_rcu_find_val
- The function searches the item with key equal to \p key
- and returns \p true if it is found, and \p false otherwise.
-
- Note the hash functor specified for class \p Traits template parameter
- should accept a parameter of type \p Q that can be not the same as \p value_type.
-
- The function applies RCU lock internally.
- */
- template <typename Q>
- bool find( Q const& key ) const
- {
- //TODO
- }
-
- /// Finds the key \p key with comparing functor \p pred
- /**
- The function is an analog of \ref cds_intrusive_BronsonAVLTree_rcu_find_val "find(Q const&)"
- but \p pred is used for key compare.
- \p Less functor has the interface like \p std::less.
- \p pred must imply the same element order as the comparator used for building the tree.
- \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
- */
- template <typename Q, typename Less>
- bool find_with( Q const& key, Less pred ) const
- {
- CDS_UNUSED( pred );
- //TODO
- }
-
- /// Finds the key \p key
- /** @anchor cds_intrusive_BronsonAVLTree_rcu_find_func
- The function searches the item with key equal to \p key and calls the functor \p f for item found.
- The interface of \p Func functor is:
- \code
- struct functor {
- void operator()( value_type& item, Q& key );
- };
- \endcode
- where \p item is the item found, \p key is the <tt>find</tt> function argument.
-
- The functor can change non-key fields of \p item. Note that the functor is only guarantee
- that \p item cannot be disposed during functor is executing.
- The functor does not serialize simultaneous access to the tree \p item. If such access is
- possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
-
- The function applies RCU lock internally.
-
- The function returns \p true if \p key is found, \p false otherwise.
- */
- template <typename Q, typename Func>
- bool find( Q& key, Func f ) const
- {
- //TODO
- }
- //@cond
- template <typename Q, typename Func>
- bool find( Q const& key, Func f ) const
- {
- //TODO
- }
- //@endcond
-
- /// Finds the key \p key with comparing functor \p pred
- /**
- The function is an analog of \ref cds_intrusive_BronsonAVLTree_rcu_find_func "find(Q&, Func)"
- but \p pred is used for key comparison.
- \p Less functor has the interface like \p std::less.
- \p pred must imply the same element order as the comparator used for building the tree.
- */
- template <typename Q, typename Less, typename Func>
- bool find_with( Q& key, Less pred, Func f ) const
- {
- //TODO
- }
- //@cond
- template <typename Q, typename Less, typename Func>
- bool find_with( Q const& key, Less pred, Func f ) const
- {
- //TODO
- }
- //@endcond
-
- /// Finds \p key and return the item found
- /** \anchor cds_intrusive_BronsonAVLTree_rcu_get
- The function searches the item with key equal to \p key and returns the pointer to item found.
- If \p key is not found it returns \p nullptr.
-
- RCU should be locked before call the function.
- Returned pointer is valid while RCU is locked.
- */
- template <typename Q>
- value_type * get( Q const& key ) const
- {
- return get_( key, node_compare() );
- }
-
- /// Finds \p key with \p pred predicate and return the item found
- /**
- The function is an analog of \ref cds_intrusive_BronsonAVLTree_rcu_get "get(Q const&)"
- but \p pred is used for comparing the keys.
-
- \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
- in any order.
- \p pred must imply the same element order as the comparator used for building the tree.
- */
- template <typename Q, typename Less>
- value_type * get_with( Q const& key, Less pred ) const
- {
- //TODO
- }
-
- /// Checks if the tree is empty
- bool empty() const
- {
- //TODO
- }
-
- /// Clears the tree (thread safe, not atomic)
- /**
- The function unlink all items from the tree.
- The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
- this sequence
- \code
- set.clear();
- assert( set.empty() );
- \endcode
- the assertion could be raised.
-
- For each node the \ref disposer will be called after unlinking.
-
- RCU \p synchronize method can be called. RCU should not be locked.
- */
- void clear()
- {
- for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min() )
- ep.release();
- }
-
- /// Clears the tree (not thread safe)
- /**
- This function is not thread safe and may be called only when no other thread deals with the tree.
- The function is used in the tree destructor.
- */
- void unsafe_clear()
- {
- //TODO
- }
-
- /// Returns item count in the tree
- /**
- The value returned depends on item counter type provided by \p Traits template parameter.
- If it is \p atomicity::empty_item_counter this function always returns 0.
-
- The function is not suitable for checking the tree emptiness, use \p empty()
- member function for that.
- */
- size_t size() const
- {
- return m_ItemCounter;
- }
-
- /// Returns const reference to internal statistics
- stat const& statistics() const
- {
- return m_Stat;
- }
-
- /// Checks internal consistency (not atomic, not thread-safe)
- /**
- The debugging function to check internal consistency of the tree.
- */
- bool check_consistency() const
- {
- //TODO
- }
-
- protected:
- //@cond
- //@endcond
- };
-
-}} // nsmespace cds::intrusive
-
-#endif // #ifndef __CDS_INTRUSIVE_BRONSON_AVLTREE_RCU_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef __CDS_INTRUSIVE_DETAILS_BRONSON_AVLTREE_BASE_H
-#define __CDS_INTRUSIVE_DETAILS_BRONSON_AVLTREE_BASE_H
-
-#include <type_traits>
-#include <cds/intrusive/details/base.h>
-#include <cds/opt/options.h>
-#include <cds/urcu/options.h>
-#include <cds/opt/value_cleaner.h>
-
-namespace cds { namespace intrusive {
-
- /// BronsonAVLTree related declarations
- namespace bronson_avltree {
-
- //@cond
- template <typename Node>
- struct base_node
- {
- typedef Node node_type;
-
- atomics::atomic< int > m_nHeight; ///< Node height
- atomics::atomic<uint64_t> m_nVersion; ///< Version bits
- atomics::atomic<node_type *> m_pParent; ///< Parent node
- atomics::atomic<node_type *> m_pLeft; ///< Left child
- atomics::atomic<node_type *> m_pRight; ///< Right child
- atomics::atomic<uint32_t> m_flags; ///< Internal flags
-
- enum class version : uint64_t
- {
- unlinked = 1,
- growing = 2,
- shrinking = 4,
- grow_count_increment = 1 << 3,
- grow_count_mask = 0xff << 3,
- shrink_count_increment = 1 << 11,
- ignore_grow = ~(growing | grow_count_mask)
- };
-
- enum class flags : uint32_t
- {
- lock_bit = 1, ///< spin-lock bit
- value_null = 2, ///< "value is null" flag
- };
-
- base_node()
- : m_nHeight( 0 )
- , m_nVersion( 0 )
- , m_pParent( nullptr )
- , m_pLeft( nullptr )
- , m_pRight( nullptr )
- , m_flags( 0 )
- {}
-
- atomics::atomic<node_type *>& child( int nDirection )
- {
- assert( nDirection != 0 );
- return nDirection < 0 ? m_pLeft : m_pRight;
- }
- };
- //@endcond
-
- /// Bronson's AVLtree node
- /**
- Template parameters:
- - \p GC - one of \ref cds_garbage_collector "garbage collector type"
- - \p Tag - a \ref cds_intrusive_hook_tag "tag"
- */
- template <typename GC, typename Tag = opt::none>
- struct node : public base_node< node >
- {};
-
- //@cond
- struct undefined_gc;
- struct default_hook {
- typedef undefined_gc gc;
- typedef opt::none tag;
- };
- //@endcond
-
- //@cond
- template < typename HookType, typename... Options>
- struct hook
- {
- typedef typename opt::make_options< default_hook, Options...>::type options;
- typedef typename options::gc gc;
- typedef typename options::tag tag;
- typedef node<gc, tag> node_type;
- typedef HookType hook_type;
- };
- //@endcond
-
- /// Base hook
- /**
- \p Options are:
- - \p opt::gc - garbage collector
- - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
- */
- template < typename... Options >
- struct base_hook: public hook< opt::base_hook_tag, Options... >
- {};
-
- /// Member hook
- /**
- \p MemberOffset defines offset in bytes of \ref node member into your structure.
- Use \p offsetof macro to define \p MemberOffset
-
- \p Options are:
- - \p opt::gc - garbage collector
- - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
- */
- template < size_t MemberOffset, typename... Options >
- struct member_hook: public hook< opt::member_hook_tag, Options... >
- {
- //@cond
- static CDS_CONSTEXPR const size_t c_nMemberOffset = MemberOffset;
- //@endcond
- };
-
- /// Traits hook
- /**
- \p NodeTraits defines type traits for node.
- See \ref node_traits for \p NodeTraits interface description
-
- \p Options are:
- - opt::gc - garbage collector
- - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
- */
- template <typename NodeTraits, typename... Options >
- struct traits_hook: public hook< opt::traits_hook_tag, Options... >
- {
- //@cond
- typedef NodeTraits node_traits;
- //@endcond
- };
-
- /// BronsonAVLTree internal statistics
- template <typename Counter = cds::atomicity::event_counter>
- struct stat {
- typedef Counter event_counter; ///< Event counter type
- };
-
- /// BronsonAVLTree empty statistics
- struct empty_stat {
- //@cond
- //@endcond
- };
-
- /// BronsnAVLTree traits
- struct traits
- {
- /// Hook used
- /**
- Possible values are: \p bronson_avltree::base_hook, \p bronson_avltree::member_hook, \p bronson_avltree::traits_hook.
- */
- typedef base_hook<> hook;
-
- /// Key comparison functor
- /**
- No default functor is provided. If the option is not specified, the \p less is used.
-
- See \p cds::opt::compare option description for functor interface.
-
- You should provide \p compare or \p less functor.
- */
- typedef opt::none compare;
-
- /// Specifies binary predicate used for key compare.
- /**
- See \p cds::opt::less option description for predicate interface.
-
- You should provide \p compare or \p less functor.
- */
- typedef opt::none less;
-
- /// Value cleaner
- /**
- The Bronson et al AVLTree algorithm uses partially extenal trees, in witch routing nodes are
- only created during the removal of a node with two children. Routing nodes are never created
- during insertion, and routing nodes with fewer then two children are unlinked during rebalancing.
- Routing nodes should contain only key field(s), other data field(s) is unneeded. When a leaf
- becomes the routing node, the \p %value_cleaner functor is called under the node lock
- for that node to clean all fields except key.
- By default, the functor is disabled (\p opt::v::empty_cleaner).
- \p opt::v::destruct_cleaner is prohibited since it can destruct key field.
- */
- typedef opt::v::empty_cleaner value_cleaner;
-
- /// Disposer
- /**
- The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
- */
- typedef opt::v::empty_disposer disposer;
-
- /// Item counter
- /**
- The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
- To enable it use \p atomicity::item_counter
- */
- typedef atomicity::empty_item_counter item_counter;
-
- /// C++ memory ordering model
- /**
- List of available memory ordering see \p opt::memory_model
- */
- typedef opt::v::relaxed_ordering memory_model;
-
- /// Internal statistics
- /**
- By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
- To enable it use \p ellen_bintree::stat.
- */
- typedef empty_stat stat;
-
- /// Back-off strategy
- typedef cds::backoff::empty back_off;
-
- /// RCU deadlock checking policy (only for \ref cds_intrusive_BronsonAVLTree_rcu "RCU-based BronsonAVLTree")
- /**
- List of available options see \p opt::rcu_check_deadlock
- */
- typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
- };
-
- /// Metafunction converting option list to BronsonAVLTree traits
- /**
- \p Options are:
- - \p opt::hook - hook used. Possible values are: \p bronson_avltree::base_hook, \p bronson_avltree::member_hook, \p bronson_avltree::traits_hook.
- If the option is not specified, <tt>bronson_avltree::base_hook<></tt> is used.
- - \p opt::compare - key compare functor. No default functor is provided.
- If the option is not specified, \p %opt::less is used.
- - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
- - \p opt::value_cleaner - the functor is used to clean all value fields except key, see \p traits::value_cleaner.
- By default, the emoty cleaner \p opt::v::empty_cleaner is used. Note that \p opt::v::destruct_cleaner is prohibited
- since it can clean the key field(s).
- - \p opt::disposer - the functor used for dispose removed nodes. Default is \p opt::v::empty_disposer. Due the nature
- of GC schema the disposer may be called asynchronously.
- - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
- To enable it use \p atomicity::item_counter
- - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
- or \p opt::v::sequential_consistent (sequentially consisnent memory model).
- - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
- To enable statistics use \p \p bronson_avltree::stat
- - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
- - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
- */
- template <typename... Options>
- struct make_traits {
-# ifdef CDS_DOXYGEN_INVOKED
- typedef implementation_defined type ; ///< Metafunction result
-# else
- typedef typename cds::opt::make_options<
- typename cds::opt::find_type_traits< traits, Options... >::type
- ,Options...
- >::type type;
-# endif
- };
-
- } // namespace bronson_avltree
-
- // Forwards
- template < class GC, typename T, class Traits = bronson_avltree::traits >
- class BronsonAVLTree;
-
-}} // namespce cds::intrusive
-
-#endif // #ifndef __CDS_INTRUSIVE_DETAILS_BRONSON_AVLTREE_BASE_H
<ClInclude Include="..\..\..\cds\compiler\vc\amd64\cxx11_atomic.h" />\r
<ClInclude Include="..\..\..\cds\compiler\vc\x86\cxx11_atomic.h" />\r
<ClInclude Include="..\..\..\cds\container\basket_queue.h" />\r
+ <ClInclude Include="..\..\..\cds\container\bronson_avltree_map_rcu.h" />\r
<ClInclude Include="..\..\..\cds\container\cuckoo_map.h" />\r
<ClInclude Include="..\..\..\cds\container\cuckoo_set.h" />\r
<ClInclude Include="..\..\..\cds\container\details\base.h" />\r
+ <ClInclude Include="..\..\..\cds\container\details\bronson_avltree_base.h" />\r
<ClInclude Include="..\..\..\cds\container\details\cuckoo_base.h" />\r
<ClInclude Include="..\..\..\cds\container\details\ellen_bintree_base.h" />\r
<ClInclude Include="..\..\..\cds\container\details\guarded_ptr_cast.h" />\r
<ClInclude Include="..\..\..\cds\container\ellen_bintree_set_dhp.h" />\r
<ClInclude Include="..\..\..\cds\container\ellen_bintree_set_hp.h" />\r
<ClInclude Include="..\..\..\cds\container\ellen_bintree_set_rcu.h" />\r
+ <ClInclude Include="..\..\..\cds\container\impl\bronson_avltree_map_rcu.h" />\r
<ClInclude Include="..\..\..\cds\container\impl\ellen_bintree_map.h" />\r
<ClInclude Include="..\..\..\cds\container\impl\ellen_bintree_set.h" />\r
<ClInclude Include="..\..\..\cds\container\impl\lazy_kvlist.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\bronson_avltree_rcu.h">\r
<Filter>Header Files\cds\intrusive</Filter>\r
</ClInclude>\r
+ <ClInclude Include="..\..\..\cds\container\details\bronson_avltree_base.h">\r
+ <Filter>Header Files\cds\container\details</Filter>\r
+ </ClInclude>\r
+ <ClInclude Include="..\..\..\cds\container\impl\bronson_avltree_map_rcu.h">\r
+ <Filter>Header Files\cds\container\impl</Filter>\r
+ </ClInclude>\r
+ <ClInclude Include="..\..\..\cds\container\bronson_avltree_map_rcu.h">\r
+ <Filter>Header Files\cds\container</Filter>\r
+ </ClInclude>\r
</ItemGroup>\r
</Project>
\ No newline at end of file
projects / libcds.git / commitdiff