boost::intrusive::circular_list_algorithms< NodeTraits > Singleton Reference

circular_list_algorithms provides basic algorithms to manipulate nodes forming a circular doubly linked list. More...

#include <intrusive_fwd.hpp>

Classes
struct	stable_partition_info

Public Types
typedef NodeTraits::node	node
typedef NodeTraits::node_ptr	node_ptr
typedef NodeTraits::const_node_ptr	const_node_ptr
typedef NodeTraits	node_traits

Static Public Member Functions
static void	init (const node_ptr &this_node)
	Effects: Constructs an non-used list element, so that inited(this_node) == true More...
static bool	inited (const const_node_ptr &this_node)
	Effects: Returns true is "this_node" is in a non-used state as if it was initialized by the "init" function. More...
static void	init_header (const node_ptr &this_node)
	Effects: Constructs an empty list, making this_node the only node of the circular list: NodeTraits::get_next(this_node) == NodeTraits::get_previous(this_node) == this_node. More...
static bool	unique (const const_node_ptr &this_node)
	Requires: this_node must be in a circular list or be an empty circular list. More...
static std::size_t	count (const const_node_ptr &this_node)
	Requires: this_node must be in a circular list or be an empty circular list. More...
static node_ptr	unlink (const node_ptr &this_node)
	Requires: this_node must be in a circular list or be an empty circular list. More...
static void	unlink (const node_ptr &b, const node_ptr &e)
	Requires: b and e must be nodes of the same circular list or an empty range. More...
static void	link_before (const node_ptr &nxt_node, const node_ptr &this_node)
	Requires: nxt_node must be a node of a circular list. More...
static void	link_after (const node_ptr &prev_node, const node_ptr &this_node)
	Requires: prev_node must be a node of a circular list. More...
static void	swap_nodes (const node_ptr &this_node, const node_ptr &other_node)
static void	transfer (const node_ptr &p, const node_ptr &b, const node_ptr &e)
	Requires: b and e must be nodes of the same circular list or an empty range. More...
static void	transfer (const node_ptr &p, const node_ptr &i)
	Requires: i must a node of a circular list and p must be a node of a different circular list. More...
static void	reverse (const node_ptr &p)
	Effects: Reverses the order of elements in the list. More...
static void	move_backwards (const node_ptr &p, std::size_t n)
	Effects: Moves the node p n positions towards the end of the list. More...
static void	move_forward (const node_ptr &p, std::size_t n)
	Effects: Moves the node p n positions towards the beginning of the list. More...
static std::size_t	distance (const const_node_ptr &f, const const_node_ptr &l)
	Requires: f and l must be in a circular list. More...
template<class Pred >
static void	stable_partition (node_ptr beg, const node_ptr &end, Pred pred, stable_partition_info &info)

Detailed Description

template<class NodeTraits>
singleton boost::intrusive::circular_list_algorithms< NodeTraits >

circular_list_algorithms provides basic algorithms to manipulate nodes forming a circular doubly linked list.

An empty circular list is formed by a node whose pointers point to itself.

circular_list_algorithms is configured with a NodeTraits class, which encapsulates the information about the node to be manipulated. NodeTraits must support the following interface:

Typedefs:

node: The type of the node that forms the circular list

node_ptr: A pointer to a node

const_node_ptr: A pointer to a const node

Static functions:

static node_ptr get_previous(const_node_ptr n);

static void set_previous(node_ptr n, node_ptr prev);

static node_ptr get_next(const_node_ptr n);

static void set_next(node_ptr n, node_ptr next);

Member Typedef Documentation

template<class NodeTraits >

typedef NodeTraits::const_node_ptr boost::intrusive::circular_list_algorithms< NodeTraits >::const_node_ptr

template<class NodeTraits >

typedef NodeTraits::node boost::intrusive::circular_list_algorithms< NodeTraits >::node

template<class NodeTraits >

typedef NodeTraits::node_ptr boost::intrusive::circular_list_algorithms< NodeTraits >::node_ptr

template<class NodeTraits >

typedef NodeTraits boost::intrusive::circular_list_algorithms< NodeTraits >::node_traits

Member Function Documentation

template<class NodeTraits >

static std::size_t boost::intrusive::circular_list_algorithms< NodeTraits >::count ( const const_node_ptr &  this_node )

inlinestatic

Requires: this_node must be in a circular list or be an empty circular list.

Effects: Returns the number of nodes in a circular list. If the circular list is empty, returns 1.

Complexity: Linear

Throws: Nothing.

References boost::multiprecision::backends::p.

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::size().

template<class NodeTraits >

static std::size_t boost::intrusive::circular_list_algorithms< NodeTraits >::distance ( const const_node_ptr &  f, const const_node_ptr &  l  )

inlinestatic

Requires: f and l must be in a circular list.

Effects: Returns the number of nodes in the range [f, l).

Complexity: Linear

Throws: Nothing.

References boost::multiprecision::backends::i.

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::erase(), and boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::splice().

template<class NodeTraits >

static void boost::intrusive::circular_list_algorithms< NodeTraits >::init ( const node_ptr &  this_node )

inlinestatic

Effects: Constructs an non-used list element, so that inited(this_node) == true

Complexity: Constant

Throws: Nothing.

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::clear_and_dispose(), boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::erase_and_dispose(), boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::pop_back_and_dispose(), boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::pop_front_and_dispose(), boost::intrusive::circular_list_algorithms< NodeTraits >::swap_nodes(), and boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::~list_impl().

template<class NodeTraits >

static void boost::intrusive::circular_list_algorithms< NodeTraits >::init_header ( const node_ptr &  this_node )

inlinestatic

Effects: Constructs an empty list, making this_node the only node of the circular list: NodeTraits::get_next(this_node) == NodeTraits::get_previous(this_node) == this_node.

Complexity: Constant

Throws: Nothing.

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::clear(), boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::clear_and_dispose(), boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::list_impl(), and boost::intrusive::circular_list_algorithms< NodeTraits >::swap_nodes().

template<class NodeTraits >

static bool boost::intrusive::circular_list_algorithms< NodeTraits >::inited ( const const_node_ptr &  this_node )

inlinestatic

Effects: Returns true is "this_node" is in a non-used state as if it was initialized by the "init" function.

Complexity: Constant

Throws: Nothing.

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::insert(), boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::iterator_to(), boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::push_back(), boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::push_front(), boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::s_iterator_to(), and boost::intrusive::circular_list_algorithms< NodeTraits >::swap_nodes().

template<class NodeTraits >

static void boost::intrusive::circular_list_algorithms< NodeTraits >::link_after ( const node_ptr &  prev_node, const node_ptr &  this_node  )

inlinestatic

Requires: prev_node must be a node of a circular list.

Effects: Links this_node after prev_node in the circular list.

Complexity: Constant

Throws: Nothing.

References boost::next().

Referenced by boost::intrusive::circular_list_algorithms< NodeTraits >::move_forward().

template<class NodeTraits >

static void boost::intrusive::circular_list_algorithms< NodeTraits >::link_before ( const node_ptr &  nxt_node, const node_ptr &  this_node  )

inlinestatic

Requires: nxt_node must be a node of a circular list.

Effects: Links this_node before nxt_node in the circular list.

Complexity: Constant

Throws: Nothing.

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::insert(), boost::intrusive::circular_list_algorithms< NodeTraits >::move_backwards(), boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::push_back(), and boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::push_front().

template<class NodeTraits >

static void boost::intrusive::circular_list_algorithms< NodeTraits >::move_backwards ( const node_ptr &  p, std::size_t  n  )

inlinestatic

Effects: Moves the node p n positions towards the end of the list.

Throws: Nothing.

Complexity: Linear to the number of moved positions.

References boost::xpressive::first, boost::intrusive::circular_list_algorithms< NodeTraits >::link_before(), and boost::intrusive::circular_list_algorithms< NodeTraits >::unlink().

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::shift_forward().

template<class NodeTraits >

static void boost::intrusive::circular_list_algorithms< NodeTraits >::move_forward ( const node_ptr &  p, std::size_t  n  )

inlinestatic

Effects: Moves the node p n positions towards the beginning of the list.

Throws: Nothing.

Complexity: Linear to the number of moved positions.

References boost::last, boost::intrusive::circular_list_algorithms< NodeTraits >::link_after(), and boost::intrusive::circular_list_algorithms< NodeTraits >::unlink().

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::shift_backwards().

template<class NodeTraits >

static void boost::intrusive::circular_list_algorithms< NodeTraits >::reverse ( const node_ptr &  p )

inlinestatic

Effects: Reverses the order of elements in the list.

Throws: Nothing.

Complexity: This function is linear time.

References boost::multiprecision::backends::i, boost::n, and boost::intrusive::circular_list_algorithms< NodeTraits >::transfer().

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::reverse().

template<class NodeTraits >

template<class Pred >

static void boost::intrusive::circular_list_algorithms< NodeTraits >::stable_partition ( node_ptr  beg, const node_ptr &  end, Pred  pred, stable_partition_info &  info  )

inlinestatic

References boost::intrusive::circular_list_algorithms< NodeTraits >::stable_partition_info::beg_2st_partition, BOOST_CATCH, BOOST_CATCH_END, BOOST_TRY, boost::end, boost::intrusive::circular_list_algorithms< NodeTraits >::stable_partition_info::num_1st_partition, and boost::intrusive::circular_list_algorithms< NodeTraits >::stable_partition_info::num_2nd_partition.

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::remove_and_dispose_if(), and boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::remove_if().

template<class NodeTraits >

static void boost::intrusive::circular_list_algorithms< NodeTraits >::swap_nodes ( const node_ptr &  this_node, const node_ptr &  other_node  )

inlinestatic

References boost::intrusive::circular_list_algorithms< NodeTraits >::init(), boost::intrusive::circular_list_algorithms< NodeTraits >::init_header(), and boost::intrusive::circular_list_algorithms< NodeTraits >::inited().

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::swap().

template<class NodeTraits >

static void boost::intrusive::circular_list_algorithms< NodeTraits >::transfer ( const node_ptr &  p, const node_ptr &  b, const node_ptr &  e  )

inlinestatic

Requires: b and e must be nodes of the same circular list or an empty range.

and p must be a node of a different circular list or may not be an iterator in Effects: Removes the nodes from [b, e) range from their circular list and inserts them before p in p's circular list.

Complexity: Constant

Throws: Nothing.

Referenced by boost::intrusive::circular_list_algorithms< NodeTraits >::reverse(), and boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::splice().

template<class NodeTraits >

static void boost::intrusive::circular_list_algorithms< NodeTraits >::transfer ( const node_ptr &  p, const node_ptr &  i  )

inlinestatic

Requires: i must a node of a circular list and p must be a node of a different circular list.

Effects: Removes the node i from its circular list and inserts it before p in p's circular list. If p == i or p == NodeTraits::get_next(i), this function is a null operation.

Complexity: Constant

Throws: Nothing.

References boost::n.

template<class NodeTraits >

static bool boost::intrusive::circular_list_algorithms< NodeTraits >::unique ( const const_node_ptr &  this_node )

inlinestatic

Requires: this_node must be in a circular list or be an empty circular list.

Effects: Returns true is "this_node" is the only node of a circular list: return NodeTraits::get_next(this_node) == this_node

Complexity: Constant

Throws: Nothing.

References boost::next().

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::empty().

template<class NodeTraits >

static node_ptr boost::intrusive::circular_list_algorithms< NodeTraits >::unlink ( const node_ptr &  this_node )

inlinestatic

Requires: this_node must be in a circular list or be an empty circular list.

Effects: Unlinks the node from the circular list.

Complexity: Constant

Throws: Nothing.

References boost::next().

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::erase(), boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::erase_and_dispose(), boost::intrusive::circular_list_algorithms< NodeTraits >::move_backwards(), boost::intrusive::circular_list_algorithms< NodeTraits >::move_forward(), boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::pop_back_and_dispose(), and boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::pop_front_and_dispose().

template<class NodeTraits >

static void boost::intrusive::circular_list_algorithms< NodeTraits >::unlink ( const node_ptr &  b, const node_ptr &  e  )

inlinestatic

Requires: b and e must be nodes of the same circular list or an empty range.

Effects: Unlinks the node [b, e) from the circular list.

Complexity: Constant

Throws: Nothing.

---

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

• boost_1_57_0/boost/intrusive/circular_list_algorithms.hpp