1 /////////////////////////////////////////////////////////////////////////////
\r
3 // (C) Copyright Olaf Krzikalla 2004-2006.
\r
4 // (C) Copyright Ion GaztaƱaga 2006-2007
\r
6 // Distributed under the Boost Software License, Version 1.0.
\r
7 // (See accompanying file LICENSE_1_0.txt or copy at
\r
8 // http://www.boost.org/LICENSE_1_0.txt)
\r
10 // See http://www.boost.org/libs/intrusive for documentation.
\r
12 /////////////////////////////////////////////////////////////////////////////
\r
14 #ifndef BOOST_INTRUSIVE_LIST_ALGORITHMS_HPP
\r
15 #define BOOST_INTRUSIVE_LIST_ALGORITHMS_HPP
\r
17 #include "detail/config_begin.hpp"
\r
19 #include <boost/assert.hpp>
\r
20 #include "detail/pointer_type.hpp"
\r
21 #include "detail/pointer_to_other.hpp"
\r
22 #include <boost/get_pointer.hpp>
\r
26 namespace intrusive {
\r
28 //! list_algorithms provides basic algorithms to manipulate nodes
\r
29 //! forming a circular doubly linked list. An empty circular list is formed by a node
\r
30 //! whose pointers point to itself.
\r
32 //! list_algorithms is configured with a NodeTraits class, which encapsulates the
\r
33 //! information about the node to be manipulated. NodeTraits must support the
\r
34 //! following interface:
\r
36 //! <b>Typedefs</b>:
\r
38 //! <tt>node</tt>: The type of the node that forms the circular list
\r
40 //! <tt>node_ptr</tt>: A pointer to a node
\r
42 //! <tt>const_node_ptr</tt>: A pointer to a const node
\r
44 //! <b>Static functions</b>:
\r
46 //! <tt>static node_ptr get_previous(const_node_ptr n);</tt>
\r
48 //! <tt>static void set_previous(node_ptr n, node_ptr prev);</tt>
\r
50 //! <tt>static node_ptr get_next(const_node_ptr n);</tt>
\r
52 //! <tt>static void set_next(node_ptr n, node_ptr next);</tt>
\r
53 template<class NodeTraits>
\r
54 class list_algorithms
\r
57 typedef typename NodeTraits::node_ptr node_ptr;
\r
58 typedef typename NodeTraits::const_node_ptr const_node_ptr;
\r
60 //! <b>Effects</b>: Constructs an empty list, making this_node the only
\r
61 //! node of the circular list:
\r
62 //! <tt>NodeTraits::get_next(this_node) == NodeTraits::get_previous(this_node)
\r
63 //! == this_node</tt>.
\r
65 //! <b>Complexity</b>: Constant
\r
67 //! <b>Throws</b>: Nothing.
\r
68 static void init(node_ptr this_node)
\r
70 NodeTraits::set_next(this_node, this_node);
\r
71 NodeTraits::set_previous(this_node, this_node);
\r
74 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
\r
76 //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list:
\r
77 //! <tt>return NodeTraits::get_next(this_node) == this_node</tt>
\r
79 //! <b>Complexity</b>: Constant
\r
81 //! <b>Throws</b>: Nothing.
\r
82 static bool unique(const_node_ptr this_node)
\r
83 { return NodeTraits::get_next(this_node) == this_node; }
\r
85 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
\r
87 //! <b>Effects</b>: Returns the number of nodes in a circular list. If the circular list
\r
88 //! is empty, returns 1.
\r
90 //! <b>Complexity</b>: Constant
\r
92 //! <b>Throws</b>: Nothing.
\r
93 static std::size_t count(const_node_ptr this_node)
\r
95 std::size_t result = 0;
\r
96 const_node_ptr p = this_node;
\r
98 p = NodeTraits::get_next(p);
\r
100 }while (p != this_node);
\r
104 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
\r
106 //! <b>Effects</b>: Unlinks the node from the circular list.
\r
108 //! <b>Complexity</b>: Constant
\r
110 //! <b>Throws</b>: Nothing.
\r
111 static node_ptr unlink(node_ptr this_node)
\r
113 node_ptr next(NodeTraits::get_next(this_node));
\r
114 node_ptr prev(NodeTraits::get_previous(this_node));
\r
115 NodeTraits::set_next(prev, next);
\r
116 NodeTraits::set_previous(next, prev);
\r
120 //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.
\r
122 //! <b>Effects</b>: Unlinks the node [b, e) from the circular list.
\r
124 //! <b>Complexity</b>: Constant
\r
126 //! <b>Throws</b>: Nothing.
\r
127 static void unlink(node_ptr b, node_ptr e)
\r
130 node_ptr prev(NodeTraits::get_previous(b));
\r
131 node_ptr next(NodeTraits::get_next(e));
\r
132 NodeTraits::set_previous(next, prev);
\r
133 NodeTraits::set_next(prev, next);
\r
137 //! <b>Requires</b>: nxt_node must be a node of a circular list.
\r
139 //! <b>Effects</b>: Links this_node before nxt_node in the circular list.
\r
141 //! <b>Complexity</b>: Constant
\r
143 //! <b>Throws</b>: Nothing.
\r
144 static void link_before(node_ptr nxt_node, node_ptr this_node)
\r
146 node_ptr prev(NodeTraits::get_previous(nxt_node));
\r
147 NodeTraits::set_previous(this_node, prev);
\r
148 NodeTraits::set_next(prev, this_node);
\r
149 NodeTraits::set_previous(nxt_node, this_node);
\r
150 NodeTraits::set_next(this_node, nxt_node);
\r
153 //! <b>Requires</b>: prev_node must be a node of a circular list.
\r
155 //! <b>Effects</b>: Links this_node after prev_node in the circular list.
\r
157 //! <b>Complexity</b>: Constant
\r
159 //! <b>Throws</b>: Nothing.
\r
160 static void link_after(node_ptr prev_node, node_ptr this_node)
\r
162 node_ptr next(NodeTraits::get_next(prev_node));
\r
163 NodeTraits::set_previous(this_node, prev_node);
\r
164 NodeTraits::set_next(this_node, next);
\r
165 NodeTraits::set_previous(next, this_node);
\r
166 NodeTraits::set_next(prev_node, this_node);
\r
169 //! <b>Requires</b>: this_node and other_node must be nodes inserted
\r
170 //! in circular lists or be empty circular lists.
\r
172 //! <b>Effects</b>: Swaps the position of the nodes: this_node is inserted in
\r
173 //! other_nodes position in the second circular list and the other_node is inserted
\r
174 //! in this_node's position in the first circular list.
\r
176 //! <b>Complexity</b>: Constant
\r
178 //! <b>Throws</b>: Nothing.
\r
179 static void swap_nodes(node_ptr this_node, node_ptr other_node)
\r
181 if (other_node == this_node)
\r
183 bool empty1 = unique(this_node);
\r
184 bool empty2 = unique(other_node);
\r
186 node_ptr next_this(NodeTraits::get_next(this_node));
\r
187 node_ptr prev_this(NodeTraits::get_previous(this_node));
\r
188 node_ptr next_other(NodeTraits::get_next(other_node));
\r
189 node_ptr prev_other(NodeTraits::get_previous(other_node));
\r
192 NodeTraits::set_next(this_node, next_other);
\r
193 NodeTraits::set_next(other_node, next_this);
\r
195 NodeTraits::set_previous(this_node, prev_other);
\r
196 NodeTraits::set_previous(other_node, prev_this);
\r
202 NodeTraits::set_next(prev_other, this_node);
\r
203 NodeTraits::set_previous(next_other, this_node);
\r
209 NodeTraits::set_next(prev_this, other_node);
\r
210 NodeTraits::set_previous(next_this, other_node);
\r
214 //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.
\r
215 //! and p must be a node of a different circular list or may not be an iterator in
\r
218 //! <b>Effects</b>: Removes the nodes from [b, e) range from their circular list and inserts
\r
219 //! them before p in p's circular list.
\r
221 //! <b>Complexity</b>: Constant
\r
223 //! <b>Throws</b>: Nothing.
\r
224 static void transfer(node_ptr p, node_ptr b, node_ptr e)
\r
227 node_ptr prev_p(NodeTraits::get_previous(p));
\r
228 node_ptr prev_e(NodeTraits::get_previous(e));
\r
229 node_ptr prev_b(NodeTraits::get_previous(b));
\r
230 NodeTraits::set_next(prev_e, p);
\r
231 NodeTraits::set_previous(p, prev_e);
\r
232 NodeTraits::set_next(prev_b, e);
\r
233 NodeTraits::set_previous(e, prev_b);
\r
234 NodeTraits::set_next(prev_p, b);
\r
235 NodeTraits::set_previous(b, prev_p);
\r
239 //! <b>Requires</b>: i must a node of a circular list
\r
240 //! and p must be a node of a different circular list.
\r
242 //! <b>Effects</b>: Removes the node i from its circular list and inserts
\r
243 //! it before p in p's circular list.
\r
244 //! If p == i or p == NodeTraits::get_next(i), this function is a null operation.
\r
246 //! <b>Complexity</b>: Constant
\r
248 //! <b>Throws</b>: Nothing.
\r
249 static void transfer(node_ptr p, node_ptr i)
\r
251 node_ptr n(NodeTraits::get_next(i));
\r
252 if(n != p && i != p){
\r
253 node_ptr prev_p(NodeTraits::get_previous(p));
\r
254 node_ptr prev_i(NodeTraits::get_previous(i));
\r
255 NodeTraits::set_next(prev_p, i);
\r
256 NodeTraits::set_previous(i, prev_p);
\r
257 NodeTraits::set_next(i, p);
\r
258 NodeTraits::set_previous(p, i);
\r
259 NodeTraits::set_previous(n, prev_i);
\r
260 NodeTraits::set_next(prev_i, n);
\r
265 //! <b>Effects</b>: Reverses the order of elements in the list.
\r
267 //! <b>Throws</b>: Nothing.
\r
269 //! <b>Complexity</b>: This function is linear time.
\r
270 static void reverse(node_ptr p)
\r
272 node_ptr f(NodeTraits::get_next(p));
\r
273 node_ptr i(NodeTraits::get_next(f)), e(p);
\r
277 i = NodeTraits::get_next(i);
\r
284 } //namespace intrusive
\r
285 } //namespace boost
\r
287 #include "detail/config_end.hpp"
\r
289 #endif //BOOST_INTRUSIVE_LIST_ALGORITHMS_HPP
\r