--- /dev/null
+/////////////////////////////////////////////////////////////////////////////\r
+//\r
+// (C) Copyright Olaf Krzikalla 2004-2006.\r
+// (C) Copyright Ion Gaztañaga 2006-2007\r
+//\r
+// Distributed under the Boost Software License, Version 1.0.\r
+// (See accompanying file LICENSE_1_0.txt or copy at\r
+// http://www.boost.org/LICENSE_1_0.txt)\r
+//\r
+// See http://www.boost.org/libs/intrusive for documentation.\r
+//\r
+/////////////////////////////////////////////////////////////////////////////\r
+\r
+#ifndef BOOST_INTRUSIVE_LIST_ALGORITHMS_HPP\r
+#define BOOST_INTRUSIVE_LIST_ALGORITHMS_HPP\r
+\r
+#include "detail/config_begin.hpp"\r
+#include <iterator>\r
+#include <boost/assert.hpp>\r
+#include "detail/pointer_type.hpp"\r
+#include "detail/pointer_to_other.hpp"\r
+#include <boost/get_pointer.hpp>\r
+#include <cstddef>\r
+\r
+namespace boost {\r
+namespace intrusive {\r
+\r
+//! list_algorithms provides basic algorithms to manipulate nodes\r
+//! forming a circular doubly linked list. An empty circular list is formed by a node\r
+//! whose pointers point to itself.\r
+//!\r
+//! list_algorithms is configured with a NodeTraits class, which encapsulates the\r
+//! information about the node to be manipulated. NodeTraits must support the\r
+//! following interface:\r
+//!\r
+//! <b>Typedefs</b>:\r
+//!\r
+//! <tt>node</tt>: The type of the node that forms the circular list\r
+//!\r
+//! <tt>node_ptr</tt>: A pointer to a node\r
+//!\r
+//! <tt>const_node_ptr</tt>: A pointer to a const node\r
+//!\r
+//! <b>Static functions</b>:\r
+//!\r
+//! <tt>static node_ptr get_previous(const_node_ptr n);</tt>\r
+//! \r
+//! <tt>static void set_previous(node_ptr n, node_ptr prev);</tt>\r
+//! \r
+//! <tt>static node_ptr get_next(const_node_ptr n);</tt>\r
+//! \r
+//! <tt>static void set_next(node_ptr n, node_ptr next);</tt>\r
+template<class NodeTraits>\r
+class list_algorithms\r
+{\r
+ public:\r
+ typedef typename NodeTraits::node_ptr node_ptr;\r
+ typedef typename NodeTraits::const_node_ptr const_node_ptr;\r
+\r
+ //! <b>Effects</b>: Constructs an empty list, making this_node the only\r
+ //! node of the circular list:\r
+ //! <tt>NodeTraits::get_next(this_node) == NodeTraits::get_previous(this_node)\r
+ //! == this_node</tt>.\r
+ //! \r
+ //! <b>Complexity</b>: Constant \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static void init(node_ptr this_node)\r
+ {\r
+ NodeTraits::set_next(this_node, this_node);\r
+ NodeTraits::set_previous(this_node, this_node);\r
+ } \r
+\r
+ //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.\r
+ //! \r
+ //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list:\r
+ //! <tt>return NodeTraits::get_next(this_node) == this_node</tt>\r
+ //! \r
+ //! <b>Complexity</b>: Constant \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static bool unique(const_node_ptr this_node) \r
+ { return NodeTraits::get_next(this_node) == this_node; }\r
+\r
+ //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.\r
+ //! \r
+ //! <b>Effects</b>: Returns the number of nodes in a circular list. If the circular list\r
+ //! is empty, returns 1.\r
+ //! \r
+ //! <b>Complexity</b>: Constant \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static std::size_t count(const_node_ptr this_node) \r
+ {\r
+ std::size_t result = 0;\r
+ const_node_ptr p = this_node;\r
+ do{\r
+ p = NodeTraits::get_next(p);\r
+ ++result;\r
+ }while (p != this_node);\r
+ return result;\r
+ }\r
+\r
+ //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.\r
+ //! \r
+ //! <b>Effects</b>: Unlinks the node from the circular list.\r
+ //! \r
+ //! <b>Complexity</b>: Constant \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static node_ptr unlink(node_ptr this_node)\r
+ {\r
+ node_ptr next(NodeTraits::get_next(this_node));\r
+ node_ptr prev(NodeTraits::get_previous(this_node));\r
+ NodeTraits::set_next(prev, next);\r
+ NodeTraits::set_previous(next, prev);\r
+ return next;\r
+ }\r
+\r
+ //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.\r
+ //! \r
+ //! <b>Effects</b>: Unlinks the node [b, e) from the circular list.\r
+ //! \r
+ //! <b>Complexity</b>: Constant \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static void unlink(node_ptr b, node_ptr e)\r
+ {\r
+ if (b != e) {\r
+ node_ptr prev(NodeTraits::get_previous(b));\r
+ node_ptr next(NodeTraits::get_next(e));\r
+ NodeTraits::set_previous(next, prev);\r
+ NodeTraits::set_next(prev, next);\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: nxt_node must be a node of a circular list.\r
+ //! \r
+ //! <b>Effects</b>: Links this_node before nxt_node in the circular list.\r
+ //! \r
+ //! <b>Complexity</b>: Constant \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static void link_before(node_ptr nxt_node, node_ptr this_node)\r
+ {\r
+ node_ptr prev(NodeTraits::get_previous(nxt_node));\r
+ NodeTraits::set_previous(this_node, prev);\r
+ NodeTraits::set_next(prev, this_node);\r
+ NodeTraits::set_previous(nxt_node, this_node);\r
+ NodeTraits::set_next(this_node, nxt_node);\r
+ }\r
+\r
+ //! <b>Requires</b>: prev_node must be a node of a circular list.\r
+ //! \r
+ //! <b>Effects</b>: Links this_node after prev_node in the circular list.\r
+ //! \r
+ //! <b>Complexity</b>: Constant \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static void link_after(node_ptr prev_node, node_ptr this_node)\r
+ {\r
+ node_ptr next(NodeTraits::get_next(prev_node));\r
+ NodeTraits::set_previous(this_node, prev_node);\r
+ NodeTraits::set_next(this_node, next);\r
+ NodeTraits::set_previous(next, this_node);\r
+ NodeTraits::set_next(prev_node, this_node);\r
+ }\r
+\r
+ //! <b>Requires</b>: this_node and other_node must be nodes inserted\r
+ //! in circular lists or be empty circular lists.\r
+ //! \r
+ //! <b>Effects</b>: Swaps the position of the nodes: this_node is inserted in\r
+ //! other_nodes position in the second circular list and the other_node is inserted\r
+ //! in this_node's position in the first circular list.\r
+ //! \r
+ //! <b>Complexity</b>: Constant \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static void swap_nodes(node_ptr this_node, node_ptr other_node)\r
+ {\r
+ if (other_node == this_node)\r
+ return;\r
+ bool empty1 = unique(this_node);\r
+ bool empty2 = unique(other_node);\r
+\r
+ node_ptr next_this(NodeTraits::get_next(this_node));\r
+ node_ptr prev_this(NodeTraits::get_previous(this_node));\r
+ node_ptr next_other(NodeTraits::get_next(other_node));\r
+ node_ptr prev_other(NodeTraits::get_previous(other_node));\r
+\r
+ //Do the swap\r
+ NodeTraits::set_next(this_node, next_other);\r
+ NodeTraits::set_next(other_node, next_this);\r
+\r
+ NodeTraits::set_previous(this_node, prev_other);\r
+ NodeTraits::set_previous(other_node, prev_this);\r
+\r
+ if (empty2){\r
+ init(this_node);\r
+ }\r
+ else{\r
+ NodeTraits::set_next(prev_other, this_node);\r
+ NodeTraits::set_previous(next_other, this_node);\r
+ }\r
+ if (empty1){\r
+ init(other_node);\r
+ }\r
+ else{\r
+ NodeTraits::set_next(prev_this, other_node);\r
+ NodeTraits::set_previous(next_this, other_node);\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.\r
+ //! and p must be a node of a different circular list or may not be an iterator in \r
+ // [b, e).\r
+ //! \r
+ //! <b>Effects</b>: Removes the nodes from [b, e) range from their circular list and inserts\r
+ //! them before p in p's circular list.\r
+ //! \r
+ //! <b>Complexity</b>: Constant \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static void transfer(node_ptr p, node_ptr b, node_ptr e)\r
+ {\r
+ if (b != e) {\r
+ node_ptr prev_p(NodeTraits::get_previous(p));\r
+ node_ptr prev_e(NodeTraits::get_previous(e));\r
+ node_ptr prev_b(NodeTraits::get_previous(b));\r
+ NodeTraits::set_next(prev_e, p);\r
+ NodeTraits::set_previous(p, prev_e);\r
+ NodeTraits::set_next(prev_b, e);\r
+ NodeTraits::set_previous(e, prev_b);\r
+ NodeTraits::set_next(prev_p, b);\r
+ NodeTraits::set_previous(b, prev_p);\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: i must a node of a circular list\r
+ //! and p must be a node of a different circular list.\r
+ //! \r
+ //! <b>Effects</b>: Removes the node i from its circular list and inserts\r
+ //! it before p in p's circular list. \r
+ //! If p == i or p == NodeTraits::get_next(i), this function is a null operation.\r
+ //! \r
+ //! <b>Complexity</b>: Constant \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static void transfer(node_ptr p, node_ptr i)\r
+ {\r
+ node_ptr n(NodeTraits::get_next(i));\r
+ if(n != p && i != p){\r
+ node_ptr prev_p(NodeTraits::get_previous(p));\r
+ node_ptr prev_i(NodeTraits::get_previous(i));\r
+ NodeTraits::set_next(prev_p, i);\r
+ NodeTraits::set_previous(i, prev_p);\r
+ NodeTraits::set_next(i, p);\r
+ NodeTraits::set_previous(p, i);\r
+ NodeTraits::set_previous(n, prev_i);\r
+ NodeTraits::set_next(prev_i, n);\r
+\r
+ }\r
+ }\r
+\r
+ //! <b>Effects</b>: Reverses the order of elements in the list. \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: This function is linear time.\r
+ static void reverse(node_ptr p)\r
+ {\r
+ node_ptr f(NodeTraits::get_next(p));\r
+ node_ptr i(NodeTraits::get_next(f)), e(p);\r
+ \r
+ while(i != e) {\r
+ node_ptr n = i;\r
+ i = NodeTraits::get_next(i);\r
+ transfer(f, n, i);\r
+ f = n;\r
+ }\r
+ }\r
+};\r
+\r
+} //namespace intrusive \r
+} //namespace boost \r
+\r
+#include "detail/config_end.hpp"\r
+\r
+#endif //BOOST_INTRUSIVE_LIST_ALGORITHMS_HPP\r
projects / senf.git / blobdiff