Michael's ordered list (key-value pair, template specialization for gc::nogc) More...

#include <cds/container/michael_kvlist_nogc.h>

Inheritance diagram for cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >:

Public Types
typedef Key	key_type
	Key type.

typedef Value	mapped_type
	Type of value stored in the list.

typedef std::pair< key_type const, mapped_type >	value_type
	key/value pair stored in the list

typedef base_class::gc	gc
	Garbage collector used.

typedef base_class::back_off	back_off
	Back-off strategy used.

typedef options::allocator_type	allocator_type
	Allocator type used for allocate/deallocate the nodes.

typedef base_class::item_counter	item_counter
	Item counting policy used.

typedef options::key_comparator	key_comparator
	key comparision functor

typedef base_class::memory_model	memory_model
	Memory ordering. See cds::opt::memory_model option.

typedef iterator_type< false >	iterator
	Forward iterator. More...

typedef iterator_type< true >	const_iterator
	Const forward iterator. More...

Public Member Functions
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...

	MichaelKVList ()
	Default constructor. More...

	~MichaelKVList ()
	List desctructor. More...

template<typename K >
iterator	insert (const K &key)
	Inserts new node with key and default value. More...

template<typename K , typename V >
iterator	insert (const K &key, const V &val)
	Inserts new node with a key and a value. More...

template<typename K , typename Func >
iterator	insert_key (const K &key, Func func)
	Inserts new node and initialize it by a functor. More...

template<typename K >
std::pair< iterator, bool >	ensure (const K &key)
	Ensures that the key `key` exists in the list. More...

template<typename K , typename... Args>
iterator	emplace (K &&key, Args &&...args)
	Inserts data of type mapped_type constructed with `std::forward<Args>(args)...` More...

template<typename Q >
iterator	find (Q const &key)
	Find the key `key`. More...

template<typename Q , typename Less >
iterator	find_with (Q const &key, Less pred)
	Finds the key `val` 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...

void	clear ()
	Clears the list. More...


const_iterator	begin () const
	Returns a forward const iterator addressing the first element in a list.

const_iterator	cbegin ()


const_iterator	end () const
	Returns an const iterator that addresses the location succeeding the last element in a list.

const_iterator	cend ()

Additional Inherited Members
Protected Types inherited from cds::intrusive::MichaelList< gc::nogc, implementation_defined, Traits >
typedef implementation_defined	value_type
	type of value stored in the list

typedef Traits	options
	Traits template parameter.

typedef options::hook	hook
	hook type

typedef hook::node_type	node_type
	node type

typedef implementation_defined	key_comparator
	key comparision functor based on opt::compare and opt::less option setter.

typedef options::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, options::link_checker >::type	link_checker
	link checker

typedef gc::nogc	gc
	Garbage collector.

typedef options::back_off	back_off
	back-off strategy

typedef options::item_counter	item_counter
	Item counting policy used.

typedef options::memory_model	memory_model
	Memory ordering. See cds::opt::memory_model option.

typedef iterator_type< false >	iterator
	Forward iterator. More...

typedef iterator_type< true >	const_iterator
	Const forward iterator. More...

typedef node_type::atomic_marked_ptr	atomic_node_ptr
	Atomic node pointer.

typedef node_type::marked_ptr	marked_node_ptr
	Node marked pointer.

typedef atomic_node_ptr	auxiliary_head
	Auxiliary head type (for split-list support)

Protected Member Functions inherited from cds::intrusive::MichaelList< gc::nogc, implementation_defined, Traits >
iterator	begin ()
	Returns a forward iterator addressing the first element in a list. More...

const_iterator	begin () const
	Returns a forward const iterator addressing the first element in a list.

iterator	end ()
	Returns an iterator that addresses the location succeeding the last element in a list. More...

const_iterator	end () const
	Returns an const iterator that addresses the location succeeding the last element in a list.

const_iterator	cbegin ()
	Returns a forward const iterator addressing the first element in a list.

const_iterator	cend ()
	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 object.

bool	insert (value_type &val)
	Inserts new node. More...

bool	insert (value_type &val, Func f)
	Inserts new node. More...

std::pair< bool, bool >	ensure (value_type &val, Func func)
	Ensures that the `item` exists in the list. More...

bool	unlink (value_type &val)
	Unlinks the item `val` from the list. More...

bool	erase (Q const &val)
	Deletes the item from the list. More...

bool	erase (Q const &val, Func func)
	Deletes the item from the list. More...

bool	erase_with (Q const &val, Less pred)
	Deletes the item from the list using `pred` predicate for searching. More...

bool	erase_with (Q const &val, Less pred, Func f)
	Deletes the item from the list using `pred` predicate for searching. More...

bool	find (Q &val, Func f)
	Finds the key `val`. More...

bool	find (Q const &val, Func f)
	Finds the key `val`. More...

bool	find (Q const &val)
	Finds the key `val`. More...

bool	find_with (Q &val, Less pred, Func f)
	Finds the key `val` using `pred` predicate for searching. More...

bool	find_with (Q const &val, Less pred, Func f)
	Finds the key `val` using `pred` predicate for searching. More...

bool	find_with (Q const &val, Less pred)
	Finds the key `val` using `pred` predicate for searching. More...

void	clear ()
	Clears the list. More...

bool	empty () const
	Checks if the list is empty.

size_t	size () const
	Returns list's item count. More...

Detailed Description

template<typename Key, typename Value, typename Traits = michael_list::type_traits>
class cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >

Michael's ordered list (key-value pair, template specialization for gc::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.

See MichaelList for description of template parameters.

The interface of the specialization is a little different.

Member Typedef Documentation

template<typename Key , typename Value , typename Traits = michael_list::type_traits>

typedef iterator_type<true> cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >::const_iterator

Const forward iterator.

For iterator's features and requirements see iterator

template<typename Key , typename Value , typename Traits = michael_list::type_traits>

typedef iterator_type<false> cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >::iterator

Forward iterator.

The forward iterator for Michael's list based on gc::nogc has pre- and post-increment operators.

The iterator interface to access item data:

operator -> - returns a pointer to value_type for iterator
operator * - returns a reference (a const reference for const_iterator) to value_type for iterator
const key_type& key() - returns a key reference for iterator
mapped_type& val() - retuns a value reference for iterator (const reference for const_iterator)

For both functions the iterator should not be equal to end()

Constructor & Destructor Documentation

template<typename Key , typename Value , typename Traits = michael_list::type_traits>

cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >::MichaelKVList ( )

inline

Default constructor.

Initialize empty list

template<typename Key , typename Value , typename Traits = michael_list::type_traits>

cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >::~MichaelKVList ( )

inline

List desctructor.

Clears the list

Member Function Documentation

template<typename Key , typename Value , typename Traits = michael_list::type_traits>

iterator cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >::begin ( )

inline

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

For empty list

begin() == end()

template<typename Key , typename Value , typename Traits = michael_list::type_traits>

void cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >::clear ( )

inline

Clears the list.

Post-condition: the list is empty

template<typename Key , typename Value , typename Traits = michael_list::type_traits>

template<typename K , typename... Args>

iterator cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >::emplace	(	K &&	key,
		Args &&...	args
	)

inline

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

Returns an iterator pointed to inserted value, or end() if inserting is failed

This function is available only for compiler that supports variadic template and move semantics

template<typename Key , typename Value , typename Traits = michael_list::type_traits>

iterator cds::container::MichaelKVList< gc::nogc, Key, Value, 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 NULL.

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

begin() == end()

template<typename Key , typename Value , typename Traits = michael_list::type_traits>

template<typename K >

std::pair<iterator, bool> cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >::ensure ( const K & key )

inline

Ensures that the key key exists in the list.

The operation inserts new item if the key key is not found in the list. Otherwise, the function returns an iterator that points to 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.

template<typename Key , typename Value , typename Traits = michael_list::type_traits>

template<typename Q >

iterator cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >::find ( Q const & key )

inline

Find the key 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 Key , typename Value , typename Traits = michael_list::type_traits>

template<typename Q , typename Less >

iterator cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >::find_with	(	Q const &	key,
		Less	pred
	)

inline

Finds the key val using pred predicate for searching.

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

template<typename Key , typename Value , typename Traits = michael_list::type_traits>

template<typename K >

iterator cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >::insert ( const K & key )

inline

Inserts new node with key and default value.

The function creates a node with key and default value, and then inserts the node created into the list.

Preconditions:

The key_type should be constructible from value of type K. In trivial case, K is equal to key_type.
The mapped_type should be default-constructible.

Returns an iterator pointed to inserted value, or end() if inserting is failed

template<typename Key , typename Value , typename Traits = michael_list::type_traits>

template<typename K , typename V >

iterator cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >::insert	(	const K &	key,
		const V &	val
	)

inline

Inserts new node with a key and a value.

The function creates a node with key and value val, and then inserts the node created into the list.

Preconditions:

The key_type should be constructible from key of type K.
The mapped_type should be constructible from val of type V.

Returns an iterator pointed to inserted value, or end() if inserting is failed

template<typename Key , typename Value , typename Traits = michael_list::type_traits>

template<typename K , typename Func >

iterator cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >::insert_key	(	const K &	key,
		Func	func
	)

inline

Inserts new node and initialize it by a functor.

This function inserts new node with key key and if inserting is successful then it calls func functor with signature

void func( value_type& item ) ;
   struct functor {
       void operator()( value_type& item )  ;
   };

The argument item of user-defined functor func is the reference to the list's item inserted. item.second is a reference to item's value that may be changed. User-defined functor func should guarantee that during changing item's value no any other changes could be made on this list's item by concurrent threads. The user-defined functor can be passed by reference using boost::ref and it is called only if the inserting is successful.

The key_type should be constructible from value of type K.

The function allows to split creating of new item into two part:

create item from key;
insert new item into the list;
if inserting is successful, initialize the value of item by calling f functor

This can be useful if complete initialization of object of mapped_type is heavyweight and it is preferable that the initialization should be completed only if inserting is successful.

Returns an iterator pointed to inserted value, or end() if inserting is failed

template<typename Key , typename Value , typename Traits = michael_list::type_traits>

size_t cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >::size ( ) const

inline

Returns list's item count.

The value returned depends on opt::item_counter option. For atomicity::empty_item_counter, this function always returns 0.

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

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

cds/container/michael_kvlist_nogc.h

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

template<typename Key, typename Value, typename Traits = michael_list::type_traits> class cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<typename Key, typename Value, typename Traits = michael_list::type_traits>
class cds::container::MichaelKVList< gc::nogc, Key, Value, Traits >