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) |
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);
typedef NodeTraits::const_node_ptr boost::intrusive::circular_list_algorithms< NodeTraits >::const_node_ptr |
typedef NodeTraits::node boost::intrusive::circular_list_algorithms< NodeTraits >::node |
typedef NodeTraits::node_ptr boost::intrusive::circular_list_algorithms< NodeTraits >::node_ptr |
typedef NodeTraits boost::intrusive::circular_list_algorithms< NodeTraits >::node_traits |
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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.
|
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().
|
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().
|
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.