SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef CDSLIB_INTRUSIVE_MICHAEL_SET_H
#define CDSLIB_INTRUSIVE_MICHAEL_SET_H
#include <cds/intrusive/details/michael_set_base.h>
-#include <cds/details/allocator.h>
+#include <cds/intrusive/details/iterable_list_base.h>
namespace cds { namespace intrusive {
Template parameters are:
- \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for \p OrderedList
- - \p OrderedList - ordered list implementation used as bucket for hash set, for example, \p MichaelList, \p LazyList.
+ - \p OrderedList - ordered list implementation used as bucket for hash set, for example, \p MichaelList, \p LazyList, \p IterableList.
The intrusive ordered list implementation specifies the type \p T stored in the hash-set, the reclamation
schema \p GC used by hash-set, the comparison functor for the type \p T and other features specific for
the ordered list.
\code
// Our node type
struct Foo {
- std::string key_; // key field
+ std::string key_; // key field
// ... other fields
};
public:
typedef GC gc; ///< Garbage collector
typedef OrderedList ordered_list; ///< type of ordered list used as a bucket implementation
- typedef ordered_list bucket_type; ///< bucket type
- typedef Traits traits; ///< Set traits
+ typedef Traits traits; ///< Set traits
- typedef typename ordered_list::value_type value_type ; ///< type of value to be stored in the set
- typedef typename ordered_list::key_comparator key_comparator ; ///< key comparing functor
- typedef typename ordered_list::disposer disposer ; ///< Node disposer functor
+ typedef typename ordered_list::value_type value_type ; ///< type of value to be stored in the set
+ typedef typename ordered_list::key_comparator key_comparator ; ///< key comparing functor
+ typedef typename ordered_list::disposer disposer ; ///< Node disposer functor
+ typedef typename ordered_list::stat stat ; ///< Internal statistics
/// Hash functor for \p value_type and all its derivatives that you use
typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
typedef typename traits::item_counter item_counter; ///< Item counter type
+ typedef typename traits::allocator allocator; ///< Bucket table allocator
typedef typename ordered_list::guarded_ptr guarded_ptr; ///< Guarded pointer
- /// Bucket table allocator
- typedef cds::details::Allocator< bucket_type, typename traits::allocator > bucket_table_allocator;
-
/// Count of hazard pointer required for the algorithm
static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount;
- protected:
- item_counter m_ItemCounter; ///< Item counter
- hash m_HashFunctor; ///< Hash functor
- bucket_type * m_Buckets; ///< bucket table
+ // GC and OrderedList::gc must be the same
+ static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
- private:
- //@cond
- const size_t m_nHashBitmask;
- //@endcond
+ // atomicity::empty_item_counter is not allowed as a item counter
+ static_assert(!std::is_same<item_counter, atomicity::empty_item_counter>::value,
+ "cds::atomicity::empty_item_counter is not allowed as a item counter");
protected:
//@cond
- /// Calculates hash value of \p key
- template <typename Q>
- size_t hash_value( const Q& key ) const
- {
- return m_HashFunctor( key ) & m_nHashBitmask;
- }
+ typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
- /// Returns the bucket (ordered list) for \p key
- template <typename Q>
- bucket_type& bucket( const Q& key )
- {
- return m_Buckets[ hash_value( key ) ];
- }
+ typedef typename ordered_list::template rebind_traits<
+ cds::opt::item_counter< cds::atomicity::empty_item_counter >
+ , cds::opt::stat< typename bucket_stat::wrapped_stat >
+ >::type internal_bucket_type;
+
+ typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
+
+ hash m_HashFunctor; ///< Hash functor
+ size_t const m_nHashBitmask;
+ internal_bucket_type* m_Buckets; ///< bucket table
+ item_counter m_ItemCounter; ///< Item counter
+ typename bucket_stat::stat m_Stat; ///< Internal statistics
//@endcond
public:
- ///@name Forward iterators (only for debugging purpose)
+ ///@name Forward iterators
//@{
/// Forward iterator
/**
- it has no post-increment operator
- it iterates items in unordered fashion
- The iterator cannot be moved across thread boundary because it may contain GC's guard that is thread-private GC data.
- - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
- deleting operations it is no guarantee that you iterate all item in the set.
- Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
- @warning Use this iterator on the concurrent container for debugging purpose only.
+ Iterator thread safety depends on type of \p OrderedList:
+ - for \p MichaelList and \p LazyList: iterator guarantees safety even if you delete the item that iterator points to
+ because that item is guarded by hazard pointer.
+ However, in case of concurrent deleting operations it is no guarantee that you iterate all item in the set.
+ Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
+ Use this iterator on the concurrent container for debugging purpose only.
+ - for \p IterableList: iterator is thread-safe. You may use it freely in concurrent environment.
+
*/
- typedef michael_set::details::iterator< bucket_type, false > iterator;
+ typedef michael_set::details::iterator< internal_bucket_type, false > iterator;
/// Const forward iterator
/**
For iterator's features and requirements see \ref iterator
*/
- typedef michael_set::details::iterator< bucket_type, true > const_iterator;
+ typedef michael_set::details::iterator< internal_bucket_type, true > const_iterator;
/// Returns a forward iterator addressing the first element in a set
/**
*/
iterator begin()
{
- return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
+ return iterator( m_Buckets[0].begin(), bucket_begin(), bucket_end() );
}
/// Returns an iterator that addresses the location succeeding the last element in a set
*/
iterator end()
{
- return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
+ return iterator( bucket_end()[-1].end(), bucket_end() - 1, bucket_end() );
}
/// Returns a forward const iterator addressing the first element in a set
}
//@}
- private:
- //@cond
- const_iterator get_const_begin() const
- {
- return const_iterator( m_Buckets[0].cbegin(), m_Buckets, m_Buckets + bucket_count() );
- }
- const_iterator get_const_end() const
- {
- return const_iterator( m_Buckets[bucket_count() - 1].cend(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
- }
- //@endcond
-
public:
/// Initializes hash set
/** @anchor cds_intrusive_MichaelHashSet_hp_ctor
size_t nMaxItemCount, ///< estimation of max item count in the hash set
size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket. Small integer up to 10.
) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
+ , m_Buckets( bucket_table_allocator().allocate( bucket_count()))
{
- // GC and OrderedList::gc must be the same
- static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
-
- // atomicity::empty_item_counter is not allowed as a item counter
- static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
- "cds::atomicity::empty_item_counter is not allowed as a item counter");
-
- m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
+ for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
+ construct_bucket<bucket_stat>( it );
}
/// Clears hash set object and destroys it
~MichaelHashSet()
{
clear();
- bucket_table_allocator().Delete( m_Buckets, bucket_count() );
+
+ for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
+ it->~internal_bucket_type();
+ bucket_table_allocator().deallocate( m_Buckets, bucket_count() );
}
/// Inserts new node
If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
Otherwise, the functor \p func is called with item found.
- The functor signature is:
- \code
- struct functor {
- void operator()( 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 set
- - \p val - argument \p val passed into the \p %update() function
- If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
- refers to the same thing.
-
- The functor may change non-key fields of the \p item.
- Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
+ The functor signature depends of the type of \p OrderedList:
+
+ <b>for \p MichaelList, \p LazyList</b>
+ \code
+ struct functor {
+ void operator()( 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 set
+ - \p val - argument \p val passed into the \p %update() function
+ If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
+ refers to the same thing.
+
+ The functor may change non-key fields of the \p item.
+ @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
+ \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
+ synchronization.
+
+ <b>for \p IterableList</b>
+ \code
+ void func( value_type& val, value_type * old );
+ \endcode
+ where
+ - \p val - argument \p val passed into the \p %update() function
+ - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
+
+ Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
\p second is \p true if new item has been added or \p false if the item with \p key
already is in the set.
-
- @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
- \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
- synchronization.
*/
template <typename Func>
std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
}
//@endcond
+ /// Inserts or updates the node (only for \p IterableList)
+ /**
+ The operation performs inserting or changing data with lock-free manner.
+
+ If the item \p val is not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
+ Otherwise, the current element is changed to \p val, the old element will be retired later
+ by call \p Traits::disposer.
+
+ Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
+ \p second is \p true if \p val has been added or \p false if the item with that key
+ already in the set.
+ */
+#ifdef CDS_DOXYGEN_INVOKED
+ std::pair<bool, bool> upsert( value_type& val, bool bAllowInsert = true )
+#else
+ template <typename Q>
+ typename std::enable_if<
+ std::is_same< Q, value_type>::value && is_iterable_list< ordered_list >::value,
+ std::pair<bool, bool>
+ >::type
+ upsert( Q& val, bool bAllowInsert = true )
+#endif
+ {
+ std::pair<bool, bool> bRet = bucket( val ).upsert( val, bAllowInsert );
+ if ( bRet.second )
+ ++m_ItemCounter;
+ return bRet;
+ }
+
/// Unlinks the item \p val from the set
/**
The function searches the item \p val in the set and unlink it
}
//@endcond
+ /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList)
+ /**
+ If \p key is not found the function returns \p end().
+
+ @note This function is supported only for the set based on \p IterableList
+ */
+ template <typename Q>
+#ifdef CDS_DOXYGEN_INVOKED
+ iterator
+#else
+ typename std::enable_if< std::is_same<Q,Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
+#endif
+ find( Q& key )
+ {
+ internal_bucket_type& b = bucket( key );
+ typename internal_bucket_type::iterator it = b.find( key );
+ if ( it == b.end() )
+ return end();
+ return iterator( it, &b, bucket_end());
+ }
+ //@cond
+ template <typename Q>
+ typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
+ find( Q const& key )
+ {
+ internal_bucket_type& b = bucket( key );
+ typename internal_bucket_type::iterator it = b.find( key );
+ if ( it == b.end() )
+ return end();
+ return iterator( it, &b, bucket_end() );
+ }
+ //@endcond
+
+
/// Finds the key \p key using \p pred predicate for searching
/**
The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_find_func "find(Q&, Func)"
}
//@endcond
+ /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList)
+ /**
+ The function is an analog of \p find(Q&) but \p pred is used for key comparing.
+ \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 set.
+
+ If \p key is not found the function returns \p end().
+
+ @note This function is supported only for the set based on \p IterableList
+ */
+ template <typename Q, typename Less>
+#ifdef CDS_DOXYGEN_INVOKED
+ iterator
+#else
+ typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
+#endif
+ find_with( Q& key, Less pred )
+ {
+ internal_bucket_type& b = bucket( key );
+ typename internal_bucket_type::iterator it = b.find_with( key, pred );
+ if ( it == b.end() )
+ return end();
+ return iterator( it, &b, bucket_end() );
+ }
+ //@cond
+ template <typename Q, typename Less>
+ typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
+ find_with( Q const& key, Less pred )
+ {
+ internal_bucket_type& b = bucket( key );
+ typename internal_bucket_type::iterator it = b.find_with( key, pred );
+ if ( it == b.end() )
+ return end();
+ return iterator( it, &b, bucket_end() );
+ }
+ //@endcond
+
/// Checks whether the set contains \p key
/**
{
return bucket( key ).contains( key );
}
- //@cond
- template <typename Q>
- CDS_DEPRECATED("use contains()")
- bool find( Q const& key )
- {
- return contains( key );
- }
- //@endcond
/// Checks whether the set contains \p key using \p pred predicate for searching
/**
{
return bucket( key ).contains( key, pred );
}
- //@cond
- template <typename Q, typename Less>
- CDS_DEPRECATED("use contains()")
- bool find_with( Q const& key, Less pred )
- {
- return contains( key, pred );
- }
- //@endcond
/// Finds the key \p key and return the item found
/** \anchor cds_intrusive_MichaelHashSet_hp_get
return m_ItemCounter;
}
+ /// Returns const reference to internal statistics
+ stat const& statistics() const
+ {
+ return m_Stat;
+ }
+
/// Returns the size of hash table
/**
Since \p %MichaelHashSet cannot dynamically extend the hash table size,
{
return m_nHashBitmask + 1;
}
+
+ private:
+ //@cond
+ internal_bucket_type * bucket_begin() const
+ {
+ return m_Buckets;
+ }
+
+ internal_bucket_type * bucket_end() const
+ {
+ return m_Buckets + bucket_count();
+ }
+
+ const_iterator get_const_begin() const
+ {
+ return const_iterator( m_Buckets[0].cbegin(), bucket_begin(), bucket_end() );
+ }
+ const_iterator get_const_end() const
+ {
+ return const_iterator( bucket_end()[-1].cend(), bucket_end() - 1, bucket_end() );
+ }
+
+ template <typename Stat>
+ typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type * bucket )
+ {
+ new (bucket) internal_bucket_type;
+ }
+
+ template <typename Stat>
+ typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type * bucket )
+ {
+ new (bucket) internal_bucket_type( m_Stat );
+ }
+
+ /// Calculates hash value of \p key
+ template <typename Q>
+ size_t hash_value( const Q& key ) const
+ {
+ return m_HashFunctor( key ) & m_nHashBitmask;
+ }
+
+ /// Returns the bucket (ordered list) for \p key
+ template <typename Q>
+ internal_bucket_type& bucket( const Q& key )
+ {
+ return m_Buckets[hash_value( key )];
+ }
+ //@endcond
};
}} // namespace cds::intrusive
projects / libcds.git / blobdiff