1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Olaf Krzikalla 2004-2006.
4 // (C) Copyright Ion Gaztanaga 2006-2014
6 // Distributed under the Boost Software License, Version 1.0.
7 // (See accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
10 // See http://www.boost.org/libs/intrusive for documentation.
12 /////////////////////////////////////////////////////////////////////////////
14 #ifndef BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP
15 #define BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP
17 #include <boost/intrusive/detail/config_begin.hpp>
18 #include <boost/intrusive/intrusive_fwd.hpp>
19 #include <boost/intrusive/detail/algo_type.hpp>
20 #include <boost/core/no_exceptions_support.hpp>
23 #if defined(BOOST_HAS_PRAGMA_ONCE)
30 //! circular_list_algorithms provides basic algorithms to manipulate nodes
31 //! forming a circular doubly linked list. An empty circular list is formed by a node
32 //! whose pointers point to itself.
34 //! circular_list_algorithms is configured with a NodeTraits class, which encapsulates the
35 //! information about the node to be manipulated. NodeTraits must support the
36 //! following interface:
40 //! <tt>node</tt>: The type of the node that forms the circular list
42 //! <tt>node_ptr</tt>: A pointer to a node
44 //! <tt>const_node_ptr</tt>: A pointer to a const node
46 //! <b>Static functions</b>:
48 //! <tt>static node_ptr get_previous(const_node_ptr n);</tt>
50 //! <tt>static void set_previous(node_ptr n, node_ptr prev);</tt>
52 //! <tt>static node_ptr get_next(const_node_ptr n);</tt>
54 //! <tt>static void set_next(node_ptr n, node_ptr next);</tt>
55 template<class NodeTraits>
56 class circular_list_algorithms
59 typedef typename NodeTraits::node node;
60 typedef typename NodeTraits::node_ptr node_ptr;
61 typedef typename NodeTraits::const_node_ptr const_node_ptr;
62 typedef NodeTraits node_traits;
64 //! <b>Effects</b>: Constructs an non-used list element, so that
65 //! inited(this_node) == true
67 //! <b>Complexity</b>: Constant
69 //! <b>Throws</b>: Nothing.
70 static void init(node_ptr this_node) BOOST_NOEXCEPT
72 const node_ptr null_node = node_ptr();
73 NodeTraits::set_next(this_node, null_node);
74 NodeTraits::set_previous(this_node, null_node);
77 //! <b>Effects</b>: Returns true is "this_node" is in a non-used state
78 //! as if it was initialized by the "init" function.
80 //! <b>Complexity</b>: Constant
82 //! <b>Throws</b>: Nothing.
83 BOOST_INTRUSIVE_FORCEINLINE static bool inited(const_node_ptr this_node) BOOST_NOEXCEPT
84 { return !NodeTraits::get_next(this_node); }
86 //! <b>Effects</b>: Constructs an empty list, making this_node the only
87 //! node of the circular list:
88 //! <tt>NodeTraits::get_next(this_node) == NodeTraits::get_previous(this_node)
89 //! == this_node</tt>.
91 //! <b>Complexity</b>: Constant
93 //! <b>Throws</b>: Nothing.
94 static void init_header(node_ptr this_node) BOOST_NOEXCEPT
96 NodeTraits::set_next(this_node, this_node);
97 NodeTraits::set_previous(this_node, this_node);
100 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
102 //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list:
103 //! <tt>return NodeTraits::get_next(this_node) == this_node</tt>
105 //! <b>Complexity</b>: Constant
107 //! <b>Throws</b>: Nothing.
108 static bool unique(const_node_ptr this_node) BOOST_NOEXCEPT
110 node_ptr next = NodeTraits::get_next(this_node);
111 return !next || next == this_node;
114 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
116 //! <b>Effects</b>: Returns the number of nodes in a circular list. If the circular list
117 //! is empty, returns 1.
119 //! <b>Complexity</b>: Linear
121 //! <b>Throws</b>: Nothing.
122 static std::size_t count(const_node_ptr this_node) BOOST_NOEXCEPT
124 std::size_t result = 0;
125 const_node_ptr p = this_node;
127 p = NodeTraits::get_next(p);
129 }while (p != this_node);
133 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
135 //! <b>Effects</b>: Unlinks the node from the circular list.
137 //! <b>Complexity</b>: Constant
139 //! <b>Throws</b>: Nothing.
140 static node_ptr unlink(node_ptr this_node) BOOST_NOEXCEPT
142 node_ptr next(NodeTraits::get_next(this_node));
143 node_ptr prev(NodeTraits::get_previous(this_node));
144 NodeTraits::set_next(prev, next);
145 NodeTraits::set_previous(next, prev);
149 //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.
151 //! <b>Effects</b>: Unlinks the node [b, e) from the circular list.
153 //! <b>Complexity</b>: Constant
155 //! <b>Throws</b>: Nothing.
156 static void unlink(node_ptr b, node_ptr e) BOOST_NOEXCEPT
159 node_ptr prevb(NodeTraits::get_previous(b));
160 NodeTraits::set_previous(e, prevb);
161 NodeTraits::set_next(prevb, e);
165 //! <b>Requires</b>: nxt_node must be a node of a circular list.
167 //! <b>Effects</b>: Links this_node before nxt_node in the circular list.
169 //! <b>Complexity</b>: Constant
171 //! <b>Throws</b>: Nothing.
172 static void link_before(node_ptr nxt_node, node_ptr this_node) BOOST_NOEXCEPT
174 node_ptr prev(NodeTraits::get_previous(nxt_node));
175 NodeTraits::set_previous(this_node, prev);
176 NodeTraits::set_next(this_node, nxt_node);
177 //nxt_node might be an alias for prev->next_
178 //so use it before NodeTraits::set_next(prev, ...)
179 //is called and the reference changes its value
180 NodeTraits::set_previous(nxt_node, this_node);
181 NodeTraits::set_next(prev, this_node);
184 //! <b>Requires</b>: prev_node must be a node of a circular list.
186 //! <b>Effects</b>: Links this_node after prev_node in the circular list.
188 //! <b>Complexity</b>: Constant
190 //! <b>Throws</b>: Nothing.
191 static void link_after(node_ptr prev_node, node_ptr this_node) BOOST_NOEXCEPT
193 node_ptr next(NodeTraits::get_next(prev_node));
194 NodeTraits::set_previous(this_node, prev_node);
195 NodeTraits::set_next(this_node, next);
196 //prev_node might be an alias for next->next_
197 //so use it before update it before NodeTraits::set_previous(next, ...)
198 //is called and the reference changes it's value
199 NodeTraits::set_next(prev_node, this_node);
200 NodeTraits::set_previous(next, this_node);
203 //! <b>Requires</b>: this_node and other_node must be nodes inserted
204 //! in circular lists or be empty circular lists.
206 //! <b>Effects</b>: Swaps the position of the nodes: this_node is inserted in
207 //! other_nodes position in the second circular list and the other_node is inserted
208 //! in this_node's position in the first circular list.
210 //! <b>Complexity</b>: Constant
212 //! <b>Throws</b>: Nothing.
213 static void swap_nodes(node_ptr this_node, node_ptr other_node) BOOST_NOEXCEPT
215 if (other_node == this_node)
217 bool this_inited = inited(this_node);
218 bool other_inited = inited(other_node);
220 init_header(this_node);
223 init_header(other_node);
226 node_ptr next_this(NodeTraits::get_next(this_node));
227 node_ptr prev_this(NodeTraits::get_previous(this_node));
228 node_ptr next_other(NodeTraits::get_next(other_node));
229 node_ptr prev_other(NodeTraits::get_previous(other_node));
230 //these first two swaps must happen before the other two
231 swap_prev(next_this, next_other);
232 swap_next(prev_this, prev_other);
233 swap_next(this_node, other_node);
234 swap_prev(this_node, other_node);
244 //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.
245 //! and p must be a node of a different circular list or may not be an iterator in
248 //! <b>Effects</b>: Removes the nodes from [b, e) range from their circular list and inserts
249 //! them before p in p's circular list.
251 //! <b>Complexity</b>: Constant
253 //! <b>Throws</b>: Nothing.
254 static void transfer(node_ptr p, node_ptr b, node_ptr e) BOOST_NOEXCEPT
256 if (b != e && p != b && p != e) {
257 node_ptr prev_p(NodeTraits::get_previous(p));
258 node_ptr prev_b(NodeTraits::get_previous(b));
259 node_ptr prev_e(NodeTraits::get_previous(e));
260 NodeTraits::set_next(prev_e, p);
261 NodeTraits::set_previous(p, prev_e);
262 NodeTraits::set_next(prev_b, e);
263 NodeTraits::set_previous(e, prev_b);
264 NodeTraits::set_next(prev_p, b);
265 NodeTraits::set_previous(b, prev_p);
269 //! <b>Requires</b>: i must a node of a circular list
270 //! and p must be a node of a different circular list.
272 //! <b>Effects</b>: Removes the node i from its circular list and inserts
273 //! it before p in p's circular list.
274 //! If p == i or p == NodeTraits::get_next(i), this function is a null operation.
276 //! <b>Complexity</b>: Constant
278 //! <b>Throws</b>: Nothing.
279 static void transfer(node_ptr p, node_ptr i) BOOST_NOEXCEPT
281 node_ptr n(NodeTraits::get_next(i));
282 if(n != p && i != p){
283 node_ptr prev_p(NodeTraits::get_previous(p));
284 node_ptr prev_i(NodeTraits::get_previous(i));
285 NodeTraits::set_next(prev_p, i);
286 NodeTraits::set_previous(i, prev_p);
287 NodeTraits::set_next(i, p);
288 NodeTraits::set_previous(p, i);
289 NodeTraits::set_previous(n, prev_i);
290 NodeTraits::set_next(prev_i, n);
295 //! <b>Effects</b>: Reverses the order of elements in the list.
297 //! <b>Throws</b>: Nothing.
299 //! <b>Complexity</b>: This function is linear time.
300 static void reverse(node_ptr p) BOOST_NOEXCEPT
302 node_ptr f(NodeTraits::get_next(p));
303 node_ptr i(NodeTraits::get_next(f)), e(p);
307 i = NodeTraits::get_next(i);
313 //! <b>Effects</b>: Moves the node p n positions towards the end of the list.
315 //! <b>Throws</b>: Nothing.
317 //! <b>Complexity</b>: Linear to the number of moved positions.
318 static void move_backwards(node_ptr p, std::size_t n) BOOST_NOEXCEPT
320 //Null shift, nothing to do
322 node_ptr first = NodeTraits::get_next(p);
323 //size() == 0 or 1, nothing to do
324 if(first == NodeTraits::get_previous(p)) return;
326 //Now get the new first node
328 first = NodeTraits::get_next(first);
330 link_before(first, p);
333 //! <b>Effects</b>: Moves the node p n positions towards the beginning of the list.
335 //! <b>Throws</b>: Nothing.
337 //! <b>Complexity</b>: Linear to the number of moved positions.
338 static void move_forward(node_ptr p, std::size_t n) BOOST_NOEXCEPT
340 //Null shift, nothing to do
342 node_ptr last = NodeTraits::get_previous(p);
343 //size() == 0 or 1, nothing to do
344 if(last == NodeTraits::get_next(p)) return;
347 //Now get the new last node
349 last = NodeTraits::get_previous(last);
354 //! <b>Requires</b>: f and l must be in a circular list.
356 //! <b>Effects</b>: Returns the number of nodes in the range [f, l).
358 //! <b>Complexity</b>: Linear
360 //! <b>Throws</b>: Nothing.
361 static std::size_t distance(const_node_ptr f, const_node_ptr l) BOOST_NOEXCEPT
363 std::size_t result = 0;
365 f = NodeTraits::get_next(f);
371 struct stable_partition_info
373 std::size_t num_1st_partition;
374 std::size_t num_2nd_partition;
375 node_ptr beg_2st_partition;
379 static void stable_partition(node_ptr beg, node_ptr end, Pred pred, stable_partition_info &info)
381 node_ptr bcur = node_traits::get_previous(beg);
383 node_ptr new_f = end;
385 std::size_t num1 = 0, num2 = 0;
390 cur = node_traits::get_next(cur);
394 node_ptr last_to_remove = bcur;
397 cur = node_traits::get_next(cur);
401 if(pred(cur)){ //Might throw
403 //Process current node
404 node_traits::set_next (last_to_remove, cur);
405 node_traits::set_previous(cur, last_to_remove);
406 last_to_remove = cur;
407 node_ptr nxt = node_traits::get_next(cur);
408 node_traits::set_next (bcur, nxt);
409 node_traits::set_previous(nxt, bcur);
415 cur = node_traits::get_next(cur);
420 node_traits::set_next (last_to_remove, new_f);
421 node_traits::set_previous(new_f, last_to_remove);
425 node_traits::set_next(last_to_remove, new_f);
426 node_traits::set_previous(new_f, last_to_remove);
430 info.num_1st_partition = num1;
431 info.num_2nd_partition = num2;
432 info.beg_2st_partition = new_f;
436 static void swap_prev(node_ptr this_node, node_ptr other_node) BOOST_NOEXCEPT
438 node_ptr temp(NodeTraits::get_previous(this_node));
439 NodeTraits::set_previous(this_node, NodeTraits::get_previous(other_node));
440 NodeTraits::set_previous(other_node, temp);
443 static void swap_next(node_ptr this_node, node_ptr other_node) BOOST_NOEXCEPT
445 node_ptr temp(NodeTraits::get_next(this_node));
446 NodeTraits::set_next(this_node, NodeTraits::get_next(other_node));
447 NodeTraits::set_next(other_node, temp);
453 template<class NodeTraits>
454 struct get_algo<CircularListAlgorithms, NodeTraits>
456 typedef circular_list_algorithms<NodeTraits> type;
461 } //namespace intrusive
464 #include <boost/intrusive/detail/config_end.hpp>
466 #endif //BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP