boost/intrusive/linear_slist_algorithms.hpp
///////////////////////////////////////////////////////////////////////////// // // (C) Copyright Olaf Krzikalla 2004-2006. // (C) Copyright Ion Gaztanaga 2006-2014 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // // See http://www.boost.org/libs/intrusive for documentation. // ///////////////////////////////////////////////////////////////////////////// #ifndef BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP #define BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/detail/common_slist_algorithms.hpp> #include <boost/intrusive/detail/algo_type.hpp> #include <cstddef> #include <boost/intrusive/detail/twin.hpp> //for node_pair #if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif namespace boost { namespace intrusive { //! linear_slist_algorithms provides basic algorithms to manipulate nodes //! forming a linear singly linked list. //! //! linear_slist_algorithms is configured with a NodeTraits class, which encapsulates the //! information about the node to be manipulated. NodeTraits must support the //! following interface: //! //! <b>Typedefs</b>: //! //! <tt>node</tt>: The type of the node that forms the linear list //! //! <tt>node_ptr</tt>: A pointer to a node //! //! <tt>const_node_ptr</tt>: A pointer to a const node //! //! <b>Static functions</b>: //! //! <tt>static node_ptr get_next(const_node_ptr n);</tt> //! //! <tt>static void set_next(node_ptr n, node_ptr next);</tt> template<class NodeTraits> class linear_slist_algorithms /// @cond : public detail::common_slist_algorithms<NodeTraits> /// @endcond { /// @cond typedef detail::common_slist_algorithms<NodeTraits> base_t; /// @endcond public: typedef typename NodeTraits::node node; typedef typename NodeTraits::node_ptr node_ptr; typedef typename NodeTraits::const_node_ptr const_node_ptr; typedef NodeTraits node_traits; //A simple struct containing: // // typedef node_ptr type; // node_ptr first; // node_ptr second; typedef twin<node_ptr> node_pair; #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) //! <b>Effects</b>: Constructs an non-used list element, putting the next //! pointer to null: //! <tt>NodeTraits::get_next(this_node) == node_ptr()</tt> //! //! <b>Complexity</b>: Constant //! //! <b>Throws</b>: Nothing. static void init(node_ptr this_node) BOOST_NOEXCEPT; //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list. //! //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list: //! or it's a not inserted node: //! <tt>return node_ptr() == NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node</tt> //! //! <b>Complexity</b>: Constant //! //! <b>Throws</b>: Nothing. static bool unique(const_node_ptr this_node) BOOST_NOEXCEPT; //! <b>Effects</b>: Returns true is "this_node" has the same state as if //! it was inited using "init(node_ptr)" //! //! <b>Complexity</b>: Constant //! //! <b>Throws</b>: Nothing. static bool inited(const_node_ptr this_node) BOOST_NOEXCEPT; //! <b>Requires</b>: prev_node must be in a circular list or be an empty circular list. //! //! <b>Effects</b>: Unlinks the next node of prev_node from the circular list. //! //! <b>Complexity</b>: Constant //! //! <b>Throws</b>: Nothing. static void unlink_after(node_ptr prev_node) BOOST_NOEXCEPT; //! <b>Requires</b>: prev_node and last_node must be in a circular list //! or be an empty circular list. //! //! <b>Effects</b>: Unlinks the range (prev_node, last_node) from the linear list. //! //! <b>Complexity</b>: Constant //! //! <b>Throws</b>: Nothing. static void unlink_after(node_ptr prev_node, node_ptr last_node) BOOST_NOEXCEPT; //! <b>Requires</b>: prev_node must be a node of a linear list. //! //! <b>Effects</b>: Links this_node after prev_node in the linear list. //! //! <b>Complexity</b>: Constant //! //! <b>Throws</b>: Nothing. static void link_after(node_ptr prev_node, node_ptr this_node) BOOST_NOEXCEPT; //! <b>Requires</b>: b and e must be nodes of the same linear list or an empty range. //! and p must be a node of a different linear list. //! //! <b>Effects</b>: Removes the nodes from (b, e] range from their linear list and inserts //! them after p in p's linear list. //! //! <b>Complexity</b>: Constant //! //! <b>Throws</b>: Nothing. static void transfer_after(node_ptr p, node_ptr b, node_ptr e) BOOST_NOEXCEPT; #else using base_t::transfer_after; #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) //! <b>Effects</b>: Constructs an empty list, making this_node the only //! node of the circular list: //! <tt>NodeTraits::get_next(this_node) == this_node</tt>. //! //! <b>Complexity</b>: Constant //! //! <b>Throws</b>: Nothing. inline static void init_header(node_ptr this_node) BOOST_NOEXCEPT { NodeTraits::set_next(this_node, node_ptr()); } //! <b>Requires</b>: 'p' is the first node of a list. //! //! <b>Effects</b>: Returns a pointer to a node that represents the "end" (one past end) node //! //! <b>Complexity</b>: Constant time. //! //! <b>Throws</b>: Nothing. inline static node_ptr end_node(const_node_ptr) BOOST_NOEXCEPT { return node_ptr(); } //! <b>Effects</b>: Returns true if this_node_points to an empty list. //! //! <b>Complexity</b>: Constant //! //! <b>Throws</b>: Nothing. inline static bool is_empty(const_node_ptr this_node) BOOST_NOEXCEPT { return !NodeTraits::get_next(this_node); } //! <b>Effects</b>: Returns true if this_node points to a sentinel node. //! //! <b>Complexity</b>: Constant //! //! <b>Throws</b>: Nothing. inline static bool is_sentinel(const_node_ptr this_node) BOOST_NOEXCEPT { return NodeTraits::get_next(this_node) == this_node; } //! <b>Effects</b>: Marks this node as a "sentinel" node, a special state that is different from "empty", //! that can be used to mark a special state of the list //! //! <b>Complexity</b>: Constant //! //! <b>Throws</b>: Nothing. inline static void set_sentinel(node_ptr this_node) BOOST_NOEXCEPT { NodeTraits::set_next(this_node, this_node); } //! <b>Requires</b>: this_node and prev_init_node must be in the same linear list. //! //! <b>Effects</b>: Returns the previous node of this_node in the linear list starting. //! the search from prev_init_node. The first node checked for equality //! is NodeTraits::get_next(prev_init_node). //! //! <b>Complexity</b>: Linear to the number of elements between prev_init_node and this_node. //! //! <b>Throws</b>: Nothing. inline static node_ptr get_previous_node(node_ptr prev_init_node, node_ptr this_node) BOOST_NOEXCEPT { return base_t::get_previous_node(prev_init_node, this_node); } //! <b>Requires</b>: this_node must be in a linear list or be an empty linear list. //! //! <b>Effects</b>: Returns the number of nodes in a linear list. If the linear list //! is empty, returns 1. //! //! <b>Complexity</b>: Linear //! //! <b>Throws</b>: Nothing. static std::size_t count(const_node_ptr this_node) BOOST_NOEXCEPT { std::size_t result = 0; const_node_ptr p = this_node; do{ p = NodeTraits::get_next(p); ++result; } while (p); return result; } //! <b>Requires</b>: this_node and other_node must be nodes inserted //! in linear lists or be empty linear lists. //! //! <b>Effects</b>: Moves all the nodes previously chained after this_node after other_node //! and vice-versa. //! //! <b>Complexity</b>: Constant //! //! <b>Throws</b>: Nothing. inline static void swap_trailing_nodes(node_ptr this_node, node_ptr other_node) BOOST_NOEXCEPT { node_ptr this_nxt = NodeTraits::get_next(this_node); node_ptr other_nxt = NodeTraits::get_next(other_node); NodeTraits::set_next(this_node, other_nxt); NodeTraits::set_next(other_node, this_nxt); } //! <b>Effects</b>: Reverses the order of elements in the list. //! //! <b>Returns</b>: The new first node of the list. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: This function is linear to the contained elements. static node_ptr reverse(node_ptr p) BOOST_NOEXCEPT { if(!p) return node_ptr(); node_ptr i = NodeTraits::get_next(p); node_ptr first(p); while(i){ node_ptr nxti(NodeTraits::get_next(i)); base_t::unlink_after(p); NodeTraits::set_next(i, first); first = i; i = nxti; } return first; } //! <b>Effects</b>: Moves the first n nodes starting at p to the end of the list. //! //! <b>Returns</b>: A pair containing the new first and last node of the list or //! if there has been any movement, a null pair if n leads to no movement. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions. static node_pair move_first_n_backwards(node_ptr p, std::size_t n) BOOST_NOEXCEPT { node_pair ret; //Null shift, or count() == 0 or 1, nothing to do if(!n || !p || !NodeTraits::get_next(p)){ return ret; } node_ptr first = p; bool end_found = false; node_ptr new_last = node_ptr(); node_ptr old_last = node_ptr(); //Now find the new last node according to the shift count. //If we find 0 before finding the new last node //unlink p, shortcut the search now that we know the size of the list //and continue. for(std::size_t i = 1; i <= n; ++i){ new_last = first; first = NodeTraits::get_next(first); if(first == node_ptr()){ //Shortcut the shift with the modulo of the size of the list n %= i; if(!n) return ret; old_last = new_last; i = 0; //Unlink p and continue the new first node search first = p; //unlink_after(new_last); end_found = true; } } //If the p has not been found in the previous loop, find it //starting in the new first node and unlink it if(!end_found){ old_last = base_t::get_previous_node(first, node_ptr()); } //Now link p after the new last node NodeTraits::set_next(old_last, p); NodeTraits::set_next(new_last, node_ptr()); ret.first = first; ret.second = new_last; return ret; } //! <b>Effects</b>: Moves the first n nodes starting at p to the beginning of the list. //! //! <b>Returns</b>: A pair containing the new first and last node of the list or //! if there has been any movement, a null pair if n leads to no movement. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions. static node_pair move_first_n_forward(node_ptr p, std::size_t n) BOOST_NOEXCEPT { node_pair ret; //Null shift, or count() == 0 or 1, nothing to do if(!n || !p || !NodeTraits::get_next(p)) return ret; node_ptr first = p; //Iterate until p is found to know where the current last node is. //If the shift count is less than the size of the list, we can also obtain //the position of the new last node after the shift. node_ptr old_last(first), next_to_it, new_last(p); std::size_t distance = 1; while(!!(next_to_it = node_traits::get_next(old_last))){ if(distance++ > n) new_last = node_traits::get_next(new_last); old_last = next_to_it; } //If the shift was bigger or equal than the size, obtain the equivalent //forward shifts and find the new last node. if(distance <= n){ //Now find the equivalent forward shifts. //Shortcut the shift with the modulo of the size of the list std::size_t new_before_last_pos = (distance - (n % distance))% distance; //If the shift is a multiple of the size there is nothing to do if(!new_before_last_pos) return ret; for( new_last = p ; --new_before_last_pos ; new_last = node_traits::get_next(new_last)){ //empty } } //Get the first new node node_ptr new_first(node_traits::get_next(new_last)); //Now put the old beginning after the old end NodeTraits::set_next(old_last, p); NodeTraits::set_next(new_last, node_ptr()); ret.first = new_first; ret.second = new_last; return ret; } //! <b>Requires</b>: other must be a list and p must be a node of a different linear list. //! //! <b>Effects</b>: Transfers all nodes from other after p in p's linear list. //! //! <b>Complexity</b>: Linear //! //! <b>Throws</b>: Nothing. static void transfer_after(node_ptr p, node_ptr other) BOOST_NOEXCEPT { if ((is_empty)(p)) { (swap_trailing_nodes)(p, other); } else { node_ptr other_last((get_previous_node)(other, node_ptr())); base_t::transfer_after(p, other, other_last); } } //! <b>Requires</b>: "disposer" must be an object function //! taking a node_ptr parameter and shouldn't throw. //! //! <b>Effects</b>: Unlinks all nodes reachable from p (but not p) and calls //! <tt>void disposer::operator()(node_ptr)</tt> for every node of the list //! where p is linked. //! //! <b>Returns</b>: The number of disposed nodes //! //! <b>Complexity</b>: Linear to the number of element of the list. //! //! <b>Throws</b>: Nothing. template<class Disposer> inline static std::size_t detach_and_dispose(node_ptr p, Disposer disposer) BOOST_NOEXCEPT { return base_t::unlink_after_and_dispose(p, node_ptr(), disposer); } }; /// @cond template<class NodeTraits> struct get_algo<LinearSListAlgorithms, NodeTraits> { typedef linear_slist_algorithms<NodeTraits> type; }; /// @endcond } //namespace intrusive } //namespace boost #include <boost/intrusive/detail/config_end.hpp> #endif //BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP