#ifndef __CDS_INTRUSIVE_MICHAEL_SET_NOGC_H
#define __CDS_INTRUSIVE_MICHAEL_SET_NOGC_H
-#include <cds/intrusive/michael_set_base.h>
+#include <cds/intrusive/details/michael_set_base.h>
#include <cds/gc/nogc.h>
#include <cds/details/allocator.h>
/** @ingroup cds_intrusive_map
\anchor cds_intrusive_MichaelHashSet_nogc
- This specialization is intended for so-called persistent usage when no item
- reclamation may be performed. The class does not support deleting of list item.
+ This specialization is so-called append-only when no item
+ reclamation may be performed. The set does not support deleting of list item.
See \ref cds_intrusive_MichaelHashSet_hp "MichaelHashSet" for description of template parameters.
- The template parameter \p OrderedList should be any gc::nogc-derived ordered list, for example,
- \ref cds_intrusive_MichaelList_nogc "persistent MichaelList".
-
- The interface of the specialization is a slightly different.
+ The template parameter \p OrderedList should be any \p cds::gc::nogc -derived ordered list, for example,
+ \ref cds_intrusive_MichaelList_nogc "append-only MichaelList".
*/
template <
class OrderedList,
#ifdef CDS_DOXYGEN_INVOKED
- class Traits = michael_set::type_traits
+ class Traits = michael_set::traits
#else
class Traits
#endif
>
- class MichaelHashSet< gc::nogc, OrderedList, Traits >
+ class MichaelHashSet< cds::gc::nogc, OrderedList, Traits >
{
public:
- typedef OrderedList bucket_type ; ///< type of ordered list used as a bucket implementation
- typedef Traits options ; ///< Traits template parameters
+ typedef cds::gc::nogc gc; ///< Garbage collector
+ typedef OrderedList bucket_type; ///< Type of ordered list to be used as buckets
+ typedef Traits traits; ///< Set traits
- typedef typename bucket_type::value_type value_type ; ///< type of value stored in the list
- typedef gc::nogc gc ; ///< Garbage collector
- typedef typename bucket_type::key_comparator key_comparator ; ///< key comparison functor
- typedef typename bucket_type::disposer disposer ; ///< Node disposer functor
+ typedef typename bucket_type::value_type value_type; ///< type of value to be stored in the set
+ typedef typename bucket_type::key_comparator key_comparator; ///< key comparing functor
+ typedef typename bucket_type::disposer disposer; ///< Node disposer functor
- /// Hash functor for \ref value_type and all its derivatives that you use
- typedef typename cds::opt::v::hash_selector< typename options::hash >::type hash;
- typedef typename options::item_counter item_counter ; ///< Item counter type
+ /// 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
/// Bucket table allocator
- typedef cds::details::Allocator< bucket_type, typename options::allocator > bucket_table_allocator;
+ typedef cds::details::Allocator< bucket_type, typename traits::allocator > bucket_table_allocator;
protected:
- item_counter m_ItemCounter ; ///< Item counter
- hash m_HashFunctor ; ///< Hash functor
-
- bucket_type * m_Buckets ; ///< bucket table
+ item_counter m_ItemCounter; ///< Item counter
+ hash m_HashFunctor; ///< Hash functor
+ bucket_type * m_Buckets; ///< bucket table
private:
//@cond
//@endcond
protected:
+ //@cond
/// Calculates hash value of \p key
template <typename Q>
size_t hash_value( Q const & key ) const
{
return m_Buckets[ hash_value( key ) ];
}
+ //@endcond
public:
/// Forward iterator
//@{
const_iterator begin() const
{
- return get_const_begin();
+ return cbegin();
}
- const_iterator cbegin()
+ const_iterator cbegin() const
{
- return get_const_begin();
+ return const_iterator( m_Buckets[0].cbegin(), m_Buckets, m_Buckets + bucket_count() );
}
//@}
//@{
const_iterator end() const
{
- return get_const_end();
+ return cend();
}
- const_iterator cend()
+ const_iterator cend() const
{
- return get_const_end();
+ return const_iterator( m_Buckets[bucket_count() - 1].cend(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
}
//@}
- private:
- //@cond
- const_iterator get_const_begin() const
- {
- return const_iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
- }
- const_iterator get_const_end() const
- {
- return const_iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
- }
- //@endcond
-
public:
/// Initializes hash set
- /**
- See \ref cds_intrusive_MichaelHashSet_hp "MichaelHashSet" ctor for explanation
+ /** @copydetails cds_intrusive_MichaelHashSet_hp_ctor
*/
MichaelHashSet(
size_t nMaxItemCount, ///< estimation of max item count in the hash set
) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
{
// 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");
+ 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 ), "atomicity::empty_item_counter is not allowed as a item counter");
+ static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
+ "atomicity::empty_item_counter is not allowed as a item counter");
m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
}
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 can change non-key fields of the \p item; however, \p func must guarantee
- that during changing no any other modifications could be made on this item by concurrent threads.
-
- You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
+ The functor can change non-key fields of the \p item.
Returns std::pair<bool, bool> 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 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_nogc "LazyList" provides exclusive access to inserted item and does not require any node-level
+ synchronization.
*/
template <typename Func>
std::pair<bool, bool> ensure( value_type& val, Func func )
return bRet;
}
- /// Finds the key \p val
+ /// Finds the key \p key
/** \anchor cds_intrusive_MichaelHashSet_nogc_find_val
- The function searches the item with key equal to \p val
- and returns pointer to item found, otherwise \p NULL.
+ The function searches the item with key equal to \p key
+ and returns pointer to item found, otherwise \p nullptr.
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.
*/
template <typename Q>
- value_type * find( Q const& val )
+ value_type * find( Q const& key )
{
- return bucket( val ).find( val );
+ return bucket( key ).find( key );
}
- /// Finds the key \p val using \p pred predicate for searching
+ /// Finds the key \p key using \p pred predicate for searching
/**
The function is an analog of \ref cds_intrusive_MichaelHashSet_nogc_find_val "find(Q const&)"
but \p pred is used for key comparing.
\p pred must imply the same element order as the comparator used for building the set.
*/
template <typename Q, typename Less>
- value_type * find_with( Q const& val, Less pred )
+ value_type * find_with( Q const& key, Less pred )
{
- return bucket( val ).find_with( val, pred );
+ return bucket( key ).find_with( key, pred );
}
- /// Finds the key \p val
+ /// Finds the key \p key
/** \anchor cds_intrusive_MichaelHashSet_nogc_find_func
- The function searches the item with key equal to \p val and calls the functor \p f for item found.
+ 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& val );
+ void operator()( value_type& item, Q& key );
};
\endcode
- where \p item is the item found, \p val is the <tt>find</tt> function argument.
-
- You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
+ 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.
The functor does not serialize simultaneous access to the set \p item. If such access is
possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
- The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
+ The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
can modify both arguments.
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 returns \p true if \p val is found, \p false otherwise.
+ The function returns \p true if \p key is found, \p false otherwise.
*/
template <typename Q, typename Func>
- bool find( Q& val, Func f )
+ bool find( Q& key, Func f )
{
- return bucket( val ).find( val, f );
+ return bucket( key ).find( key, f );
}
- /// Finds the key \p val using \p pred predicate for searching
+ /// Finds the key \p key using \p pred predicate for searching
/**
The function is an analog of \ref cds_intrusive_MichaelHashSet_nogc_find_func "find(Q&, Func)"
but \p pred is used for key comparing.
\p pred must imply the same element order as the comparator used for building the set.
*/
template <typename Q, typename Less, typename Func>
- bool find( Q& val, Less pred, Func f )
- {
- return bucket( val ).find_with( val, pred, f );
- }
-
- /// Finds the key \p val
- /** \anchor cds_intrusive_MichaelHashSet_nogc_find_cfunc
- The function searches the item with key equal to \p val 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 const& val );
- };
- \endcode
- where \p item is the item found, \p val is the <tt>find</tt> function argument.
-
- You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
-
- The functor can change non-key fields of \p item.
- The functor does not serialize simultaneous access to the set \p item. If such access is
- possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
-
- 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 returns \p true if \p val is found, \p false otherwise.
- */
- template <typename Q, typename Func>
- bool find( Q const& val, Func f )
- {
- return bucket( val ).find( val, f );
- }
-
- /// Finds the key \p val using \p pred predicate for searching
- /**
- The function is an analog of \ref cds_intrusive_MichaelHashSet_nogc_find_cfunc "find(Q const&, Func)"
- 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.
- */
- template <typename Q, typename Less, typename Func>
- bool find_with( Q const& val, Less pred, Func f )
+ bool find_with( Q& key, Less pred, Func f )
{
- return bucket( val ).find_with( val, pred, f );
+ return bucket( key ).find_with( key, pred, f );
}
/// Clears the set (non-atomic)
/// Returns the size of hash table
/**
- Since MichaelHashSet cannot dynamically extend the hash table size,
+ Since \p %MichaelHashSet cannot dynamically extend the hash table size,
the value returned is an constant depending on object initialization parameters;
see MichaelHashSet::MichaelHashSet for explanation.
*/
projects / libcds.git / blobdiff