| ///////////////////////////////////////////////////////////////////////////// |
| // |
| // (C) Copyright Olaf Krzikalla 2004-2006. |
| // (C) Copyright Ion Gaztanaga 2006-2008 |
| // |
| // 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 <cstddef> |
| #include <utility> |
| |
| 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; |
| |
| #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) == 0 |
| //! |
| //! <b>Complexity</b>: Constant |
| //! |
| //! <b>Throws</b>: Nothing. |
| static void init(node_ptr this_node); |
| |
| //! <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 !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); |
| |
| //! <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); |
| |
| //! <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); |
| |
| //! <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); |
| |
| //! <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); |
| |
| //! <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); |
| |
| #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. |
| static void init_header(node_ptr this_node) |
| { NodeTraits::set_next(this_node, node_ptr(0)); } |
| |
| //! <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. |
| static node_ptr get_previous_node(node_ptr prev_init_node, node_ptr this_node) |
| { 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>: Constant |
| //! |
| //! <b>Throws</b>: Nothing. |
| static std::size_t count(const_node_ptr this_node) |
| { |
| 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. |
| static void swap_trailing_nodes(node_ptr this_node, node_ptr other_node) |
| { |
| 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) |
| { |
| if(!p) return node_ptr(0); |
| 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 std::pair<node_ptr, node_ptr> move_first_n_backwards(node_ptr p, std::size_t n) |
| { |
| std::pair<node_ptr, node_ptr> ret(node_ptr(0), node_ptr(0)); |
| //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(0); |
| node_ptr old_last(0); |
| |
| //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 == 0){ |
| //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(0)); |
| } |
| |
| //Now link p after the new last node |
| NodeTraits::set_next(old_last, p); |
| NodeTraits::set_next(new_last, node_ptr(0)); |
| 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 std::pair<node_ptr, node_ptr> move_first_n_forward(node_ptr p, std::size_t n) |
| { |
| std::pair<node_ptr, node_ptr> ret(node_ptr(0), node_ptr(0)); |
| //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(0)); |
| ret.first = new_first; |
| ret.second = new_last; |
| return ret; |
| } |
| }; |
| |
| } //namespace intrusive |
| } //namespace boost |
| |
| #include <boost/intrusive/detail/config_end.hpp> |
| |
| #endif //BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP |