#ifndef __CDS_INTRUSIVE_IMPL_LAZY_LIST_H
#define __CDS_INTRUSIVE_IMPL_LAZY_LIST_H
+#include <mutex> // unique_lock
#include <cds/intrusive/details/lazy_list_base.h>
#include <cds/gc/guarded_ptr.h>
-
namespace cds { namespace intrusive {
/// Lazy ordered single-linked list
There are different specializations of this template for each garbage collecting schema used.
You should select GC needed and include appropriate .h-file:
- for gc::HP: \code #include <cds/intrusive/lazy_list_hp.h> \endcode
- - for gc::PTB: \code #include <cds/intrusive/lazy_list_ptb.h> \endcode
- - for gc::HRC: \code #include <cds/intrusive/lazy_list_hrc.h> \endcode
+ - for gc::DHP: \code #include <cds/intrusive/lazy_list_dhp.h> \endcode
- for gc::nogc: \code #include <cds/intrusive/lazy_list_nogc.h> \endcode
- for \ref cds_urcu_type "RCU" - see \ref cds_intrusive_LazyList_rcu "LazyList RCU specialization"
Example for gc::PTB and base hook:
\code
// Include GC-related lazy list specialization
- #include <cds/intrusive/lazy_list_ptb.h>
+ #include <cds/intrusive/lazy_list_dhp.h>
// Data stored in lazy list
struct my_data: public cds::intrusive::lazy_list::node< cds::gc::PTB >
Equivalent option-based code:
\code
// GC-related specialization
- #include <cds/intrusive/lazy_list_ptb.h>
+ #include <cds/intrusive/lazy_list_dhp.h>
struct my_data {
// see above
protected:
//@cond
- typedef lazy_list::boundary_nodes<
- gc
- ,typename opt::select_default< typename options::boundary_node_type, node_type >::type
- ,typename options::allocator
- > boundary_nodes;
- boundary_nodes m_Boundary ; ///< Head & tail dummy nodes
-
- node_type * head()
- {
- return m_Boundary.head();
- }
- node_type const * head() const
- {
- return m_Boundary.head();
- }
- node_type * tail()
- {
- return m_Boundary.tail();
- }
- node_type const * tail() const
- {
- return m_Boundary.tail();
- }
- //@endcond
+ node_type m_Head;
+ node_type m_Tail;
item_counter m_ItemCounter ; ///< Item counter
The forward iterator for lazy list has some features:
- it has no post-increment operator
- to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
- For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
+ For some GC (\p gc::HP), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
may be thrown if a limit of guard count per thread is exceeded.
- The iterator cannot be moved across thread boundary since it contains 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
*/
iterator begin()
{
- iterator it( head() );
+ iterator it( &m_Head );
++it ; // skip dummy head
return it;
}
*/
iterator end()
{
- return iterator( tail() );
+ return iterator( &m_Tail );
}
/// Returns a forward const iterator addressing the first element in a list
//@cond
const_iterator get_const_begin() const
{
- const_iterator it( const_cast<node_type *>( head() ));
+ const_iterator it( const_cast<node_type *>( &m_Head ));
++it ; // skip dummy head
return it;
}
const_iterator get_const_end() const
{
- return const_iterator( const_cast<node_type *>( tail() ));
+ return const_iterator( const_cast<node_type *>(&m_Tail) );
}
//@endcond
LazyList()
{
static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
-
- //m_pTail = cxx_allocator().New();
- head()->m_pNext.store( marked_node_ptr( tail() ), memory_model::memory_order_relaxed );
+ m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
}
/// Destroys the list object
~LazyList()
{
clear();
- assert( head()->m_pNext.load(memory_model::memory_order_relaxed).ptr() == tail() );
- head()->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
+ assert( m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail );
+ m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
}
/// Inserts new node
*/
bool insert( value_type& val )
{
- return insert_at( head(), val );
+ return insert_at( &m_Head, val );
}
/// Inserts new node
\endcode
where \p val is the item inserted.
While the functor \p f is working the item \p val is locked.
- The user-defined functor is called only if the inserting is success and may be passed by reference
- using \p std::ref
+ The user-defined functor is called only if the inserting is success.
+
+ @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
*/
template <typename Func>
bool insert( value_type& val, Func f )
{
- return insert_at( head(), val, f );
+ return insert_at( &m_Head, val, f );
}
/// Ensures that the \p item exists in the list
The functor may change non-key fields of the \p item.
While the functor \p f is working the item \p item is locked.
- You may pass \p func argument by reference using \p std::ref.
-
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 list.
+
+ @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
*/
template <typename Func>
std::pair<bool, bool> ensure( value_type& val, Func func )
{
- return ensure_at( head(), val, func );
+ return ensure_at( &m_Head, val, func );
}
/// Unlinks the item \p val from the list
*/
bool unlink( value_type& val )
{
- return unlink_at( head(), val );
+ return unlink_at( &m_Head, val );
}
/// Deletes the item from the list
template <typename Q>
bool erase( Q const& val )
{
- return erase_at( head(), val, key_comparator() );
+ return erase_at( &m_Head, val, key_comparator() );
}
/// Deletes the item from the list using \p pred predicate for searching
template <typename Q, typename Less>
bool erase_with( Q const& val, Less pred )
{
- return erase_at( head(), val, cds::opt::details::make_comparator_from_less<Less>() );
+ return erase_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>() );
}
/// Deletes the item from the list
template <typename Q, typename Func>
bool erase( const Q& val, Func func )
{
- return erase_at( head(), val, key_comparator(), func );
+ return erase_at( &m_Head, val, key_comparator(), func );
}
/// Deletes the item from the list using \p pred predicate for searching
template <typename Q, typename Less, typename Func>
bool erase_with( const Q& val, Less pred, Func func )
{
- return erase_at( head(), val, cds::opt::details::make_comparator_from_less<Less>(), func );
+ return erase_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), func );
}
/// Extracts the item from the list with specified \p key
template <typename Q>
bool extract( guarded_ptr& dest, Q const& key )
{
- return extract_at( head(), dest.guard(), key, key_comparator() );
+ return extract_at( &m_Head, dest.guard(), key, key_comparator() );
}
/// Extracts the item from the list with comparing functor \p pred
template <typename Q, typename Less>
bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
{
- return extract_at( head(), dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
+ return extract_at( &m_Head, dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
}
/// Finds the key \p val
template <typename Q, typename Func>
bool find( Q& val, Func f )
{
- return find_at( head(), val, key_comparator(), f );
+ return find_at( &m_Head, val, key_comparator(), f );
}
/// Finds the key \p val using \p pred predicate for searching
template <typename Q, typename Less, typename Func>
bool find_with( Q& val, Less pred, Func f )
{
- return find_at( head(), val, cds::opt::details::make_comparator_from_less<Less>(), f );
+ return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), f );
}
/// Finds the key \p val
template <typename Q, typename Func>
bool find( Q const& val, Func f )
{
- return find_at( head(), val, key_comparator(), f );
+ return find_at( &m_Head, val, key_comparator(), f );
}
/// Finds the key \p val using \p pred predicate for searching
template <typename Q, typename Less, typename Func>
bool find_with( Q const& val, Less pred, Func f )
{
- return find_at( head(), val, cds::opt::details::make_comparator_from_less<Less>(), f );
+ return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), f );
}
/// Finds the key \p val
template <typename Q>
bool find( Q const & val )
{
- return find_at( head(), val, key_comparator() );
+ return find_at( &m_Head, val, key_comparator() );
}
/// Finds the key \p val using \p pred predicate for searching
template <typename Q, typename Less>
bool find_with( Q const& val, Less pred )
{
- return find_at( head(), val, cds::opt::details::make_comparator_from_less<Less>() );
+ return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>() );
}
/// Finds the key \p val and return the item found
template <typename Q>
bool get( guarded_ptr& ptr, Q const& val )
{
- return get_at( head(), ptr.guard(), val, key_comparator() );
+ return get_at( &m_Head, ptr.guard(), val, key_comparator() );
}
/// Finds the key \p val and return the item found
template <typename Q, typename Less>
bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
{
- return get_at( head(), ptr.guard(), val, cds::opt::details::make_comparator_from_less<Less>() );
+ return get_at( &m_Head, ptr.guard(), val, cds::opt::details::make_comparator_from_less<Less>() );
}
/// Clears the list
typename gc::Guard guard;
marked_node_ptr h;
while ( !empty() ) {
- h = head()->m_pNext.load(memory_model::memory_order_relaxed);
+ h = m_Head.m_pNext.load( memory_model::memory_order_relaxed );
guard.assign( node_traits::to_value_ptr( h.ptr() ));
- if ( head()->m_pNext.load(memory_model::memory_order_acquire) == h ) {
- head()->m_Lock.lock();
+ if ( m_Head.m_pNext.load(memory_model::memory_order_acquire) == h ) {
+ m_Head.m_Lock.lock();
h->m_Lock.lock();
- unlink_node( head(), h.ptr(), head() );
+ unlink_node( &m_Head, h.ptr(), &m_Head );
h->m_Lock.unlock();
- head()->m_Lock.unlock();
+ m_Head.m_Lock.unlock();
retire_node( h.ptr() ) ; // free node
}
/// Checks if the list is empty
bool empty() const
{
- return head()->m_pNext.load(memory_model::memory_order_relaxed).ptr() == tail();
+ return m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail;
}
/// Returns list's item count
// split-list support
bool insert_aux_node( node_type * pNode )
{
- return insert_aux_node( head(), pNode );
+ return insert_aux_node( &m_Head, pNode );
}
// split-list support
{
auto_lock_position alp( pos );
if ( validate( pos.pPred, pos.pCur )) {
- if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
+ if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
// failed: key already in list
return false;
}
{
auto_lock_position alp( pos );
if ( validate( pos.pPred, pos.pCur )) {
- if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
+ if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
// failed: key already in list
return false;
}
{
auto_lock_position alp( pos );
if ( validate( pos.pPred, pos.pCur )) {
- if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
+ if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
// key already in the list
func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
{
auto_lock_position alp( pos );
if ( validate( pos.pPred, pos.pCur ) ) {
- if ( pos.pCur != tail()
+ if ( pos.pCur != &m_Tail
&& cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
&& node_traits::to_value_ptr( pos.pCur ) == &val )
{
{
auto_lock_position alp( pos );
if ( validate( pos.pPred, pos.pCur )) {
- if ( pos.pCur != tail() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
+ if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
// key found
unlink_node( pos.pPred, pos.pCur, pHead );
f( *node_traits::to_value_ptr( *pos.pCur ) );
position pos;
search( pHead, val, pos, cmp );
- if ( pos.pCur != tail() ) {
- cds::lock::scoped_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
+ if ( pos.pCur != &m_Tail ) {
+ std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
if ( !pos.pCur->is_marked()
&& cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
{
position pos;
search( pHead, val, pos, cmp );
- return pos.pCur != tail()
+ return pos.pCur != &m_Tail
&& !pos.pCur->is_marked()
&& cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0;
}
position pos;
search( pHead, val, pos, cmp );
- if ( pos.pCur != tail()
+ if ( pos.pCur != &m_Tail
&& !pos.pCur->is_marked()
&& cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
{
template <typename Q, typename Compare>
void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
{
- const node_type * pTail = tail();
+ const node_type * pTail = &m_Tail;
marked_node_ptr pCur( pHead );
marked_node_ptr pPrev( pHead );
projects / libcds.git / blobdiff