cds::container::MichaelList< gc::nogc, T, Traits > Class Template Reference

Michael's lock-free ordered single-linked list (template specialization for gc::nogc) More...

#include <cds/container/michael_list_nogc.h>

Inheritance diagram for cds::container::MichaelList< gc::nogc, T, Traits >:

Public Types
typedef cds::gc::nogc	gc
	Garbage collector used.
typedef T	value_type
	Type of value stored in the list.
typedef Traits	traits
	List traits.
typedef base_class::back_off	back_off
	Back-off strategy used.
typedef maker::allocator_type	allocator_type
	Allocator type used for allocate/deallocate the nodes.
typedef base_class::item_counter	item_counter
	Item counting policy used.
typedef maker::key_comparator	key_comparator
	key comparison functor
typedef base_class::memory_model	memory_model
	Memory ordering. See cds::opt::memory_model option.
typedef base_class::stat	stat
	Internal statistics.

Public Member Functions
	MichaelList ()
	Default constructor. More...
	~MichaelList ()
	List destructor. More...
template<typename Q >
iterator	insert (Q &&val)
	Inserts new node. More...
template<typename Q >
std::pair< iterator, bool >	update (Q &&key, bool bAllowInsert=true)
	Updates the item. More...
template<typename... Args>
iterator	emplace (Args &&...args)
	Inserts data of type value_type constructed with std::forward<Args>(args)... More...
template<typename Q >
iterator	contains (Q const &key)
	Checks whether the list contains key. More...
template<typename Q , typename Less >
iterator	contains (Q const &key, Less pred)
	Checks whether the map contains key using pred predicate for searching. More...
bool	empty () const
	Check if the list is empty.
size_t	size () const
	Returns list's item count. More...
stat const &	statistics () const
	Returns const reference to internal statistics.
void	clear ()
	Clears the list.

Forward iterators
typedef iterator_type< false >	iterator
	Returns a forward iterator addressing the first element in a list. More...
typedef iterator_type< true >	const_iterator
	Const forward iterator. More...
iterator	begin ()
	Returns a forward iterator addressing the first element in a list. More...
iterator	end ()
	Returns an iterator that addresses the location succeeding the last element in a list. More...
const_iterator	begin () const
	Returns a forward const iterator addressing the first element in a list.
const_iterator	cbegin () const
	Returns a forward const iterator addressing the first element in a list.
const_iterator	end () const
	Returns an const iterator that addresses the location succeeding the last element in a list.
const_iterator	cend () const
	Returns an const iterator that addresses the location succeeding the last element in a list.

Additional Inherited Members
Protected Types inherited from cds::intrusive::MichaelList< gc::nogc, T, Traits >
typedef node_type::atomic_ptr	atomic_node_ptr
	Atomic node pointer.
typedef atomic_node_ptr	auxiliary_head
	Auxiliary head type (for split-list support)
typedef gc::nogc	gc
	Garbage collector.
typedef T	value_type
	type of value to be stored in the queue
typedef Traits	traits
	List traits.
typedef traits::hook	hook
	hook type
typedef hook::node_type	node_type
	node type
typedef implementation_defined	key_comparator
	key comparison functor based on opt::compare and opt::less option setter.
typedef traits::disposer	disposer
	disposer used
typedef get_node_traits< value_type, node_type, hook >::type	node_traits
	node traits
typedef michael_list::get_link_checker< node_type, traits::link_checker >::type	link_checker
	link checker
typedef traits::back_off	back_off
	back-off strategy
typedef traits::item_counter	item_counter
	Item counting policy used.
typedef traits::memory_model	memory_model
	Memory ordering. See cds::opt::memory_model option.
typedef traits::stat	stat
	Internal statistics.
typedef iterator_type< false >	iterator
	Forward iterator.
typedef iterator_type< true >	const_iterator
	Const forward iterator.
Protected Member Functions inherited from cds::intrusive::MichaelList< gc::nogc, T, Traits >
iterator	begin ()
	Returns a forward iterator addressing the first element in a list. More...
iterator	end ()
	Returns an iterator that addresses the location succeeding the last element in a list. More...
const_iterator	begin () const
	Returns a forward const iterator addressing the first element in a list.
const_iterator	cbegin () const
	Returns a forward const iterator addressing the first element in a list.
const_iterator	end () const
	Returns an const iterator that addresses the location succeeding the last element in a list.
const_iterator	cend () const
	Returns an const iterator that addresses the location succeeding the last element in a list.
	MichaelList ()
	Default constructor initializes empty list.
	~MichaelList ()
	Destroys the list objects.
bool	insert (value_type &val)
	Inserts new node. More...
template<typename Func >
std::pair< bool, bool >	update (value_type &val, Func func, bool bAllowInsert=true)
	Updates the item. More...
template<typename Q , typename Func >
bool	find (Q &key, Func f)
	Finds the key val. More...
template<typename Q , typename Less , typename Func >
bool	find_with (Q &key, Less pred, Func f)
	Finds the key key using pred predicate for searching. More...
template<typename Q >
value_type *	contains (Q const &key)
	Checks whether the list contains key. More...
template<typename Q , typename Less >
value_type *	contains (Q const &key, Less pred)
	Checks whether the map contains key using pred predicate for searching. More...
template<typename Disposer >
void	clear (Disposer disp)
	Clears the list. More...
void	clear ()
	Clears the list using default disposer. More...
bool	empty () const
	Checks if the list is empty.
size_t	size () const
	Returns list's item count. More...
stat const &	statistics () const
	Returns const reference to internal statistics.
Protected Attributes inherited from cds::intrusive::MichaelList< gc::nogc, T, Traits >
atomic_node_ptr	m_pHead
	Head pointer.
item_counter	m_ItemCounter
	Item counter.
stat	m_Stat
	Internal statistics.

Detailed Description

template<typename T, class Traits = michael_list::traits>
class cds::container::MichaelList< gc::nogc, T, Traits >

Michael's lock-free ordered single-linked list (template specialization for gc::nogc)

This specialization is intended for so-called append-only usage when no item reclamation may be performed. The class does not support deleting of list item. Usually, ordered single-linked list is used as a building block for the hash table implementation. The complexity of searching is O(N).

See MichaelList for description of template parameters.

Member Typedef Documentation

template<typename T , class Traits = michael_list::traits>

typedef iterator_type<true> cds::container::MichaelList< gc::nogc, T, Traits >::const_iterator

Const forward iterator.

For iterator's features and requirements see iterator

template<typename T , class Traits = michael_list::traits>

typedef iterator_type<false> cds::container::MichaelList< gc::nogc, T, Traits >::iterator

Returns a forward iterator addressing the first element in a list.

For empty list

begin() == end() 

Constructor & Destructor Documentation

template<typename T , class Traits = michael_list::traits>

cds::container::MichaelList< gc::nogc, T, Traits >::MichaelList ( )

inline

Default constructor.

Initialize empty list

template<typename T , class Traits = michael_list::traits>

cds::container::MichaelList< gc::nogc, T, Traits >::~MichaelList ( )

inline

List destructor.

Clears the list

Member Function Documentation

template<typename T , class Traits = michael_list::traits>

iterator cds::container::MichaelList< gc::nogc, T, Traits >::begin ( )

inline

Returns a forward iterator addressing the first element in a list.

For empty list

begin() == end() 

template<typename T , class Traits = michael_list::traits>

template<typename Q >

iterator cds::container::MichaelList< gc::nogc, T, Traits >::contains ( Q const &  key )

inline

Checks whether the list contains key.

The function searches the item with key equal to key and returns an iterator pointed to item found if the key is found, and end() otherwise

template<typename T , class Traits = michael_list::traits>

template<typename Q , typename Less >

iterator cds::container::MichaelList< gc::nogc, T, Traits >::contains ( Q const &  key, Less  pred  )

inline

Checks whether the map contains key using pred predicate for searching.

The function is an analog of contains( key ) but pred is used for key comparing. Less functor has the interface like std::less. Less must imply the same element order as the comparator used for building the list.

template<typename T , class Traits = michael_list::traits>

template<typename... Args>

iterator cds::container::MichaelList< gc::nogc, T, Traits >::emplace ( Args &&...  args )

inline

Inserts data of type value_type constructed with std::forward<Args>(args)...

Return an iterator pointing to inserted item if success end() otherwise

template<typename T , class Traits = michael_list::traits>

iterator cds::container::MichaelList< gc::nogc, T, Traits >::end ( )

inline

Returns an iterator that addresses the location succeeding the last element in a list.

Do not use the value returned by end function to access any item. Internally, end returning value equals to nullptr.

The returned value can be used only to control reaching the end of the list. For empty list

begin() == end() 

template<typename T , class Traits = michael_list::traits>

template<typename Q >

iterator cds::container::MichaelList< gc::nogc, T, Traits >::insert ( Q &&  val )

inline

Inserts new node.

The function inserts val in the list if the list does not contain an item with key equal to val.

Return an iterator pointing to inserted item if success end() otherwise

template<typename T , class Traits = michael_list::traits>

size_t cds::container::MichaelList< gc::nogc, T, Traits >::size ( ) const

inline

Returns list's item count.

The value returned depends on item counter provided by Traits. For atomicity::empty_item_counter, this function always returns 0.

Note

Even if you use real item counter and it returns 0, this fact does not mean that the list is empty. To check list emptyness use empty() method.

template<typename T , class Traits = michael_list::traits>

template<typename Q >

std::pair<iterator, bool> cds::container::MichaelList< gc::nogc, T, Traits >::update ( Q &&  key, bool  bAllowInsert = true  )

inline

Updates the item.

If key is not in the list and bAllowInsert is true, the function inserts a new item. Otherwise, the function returns an iterator pointing to the item found.

Returns std::pair<iterator, bool> where first is an iterator pointing to item found or inserted, second is true if new item has been added or false if the item already is in the list.

---

The documentation for this class was generated from the following file:

• cds/container/michael_list_nogc.h