1/////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Olaf Krzikalla 2004-2006.
4// (C) Copyright Ion Gaztanaga 2006-2014
5//
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)
9//
10// See http://www.boost.org/libs/intrusive for documentation.
11//
12/////////////////////////////////////////////////////////////////////////////
13
14#ifndef BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP
15#define BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP
16
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>
21#include <cstddef>
22
23#if defined(BOOST_HAS_PRAGMA_ONCE)
24# pragma once
25#endif
26
27namespace boost {
28namespace intrusive {
29
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.
33//!
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:
37//!
38//! <b>Typedefs</b>:
39//!
40//! <tt>node</tt>: The type of the node that forms the circular list
41//!
42//! <tt>node_ptr</tt>: A pointer to a node
43//!
44//! <tt>const_node_ptr</tt>: A pointer to a const node
45//!
46//! <b>Static functions</b>:
47//!
48//! <tt>static node_ptr get_previous(const_node_ptr n);</tt>
49//!
50//! <tt>static void set_previous(node_ptr n, node_ptr prev);</tt>
51//!
52//! <tt>static node_ptr get_next(const_node_ptr n);</tt>
53//!
54//! <tt>static void set_next(node_ptr n, node_ptr next);</tt>
55template<class NodeTraits>
56class circular_list_algorithms
57{
58 public:
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;
63
64 //! <b>Effects</b>: Constructs an non-used list element, so that
65 //! inited(this_node) == true
66 //!
67 //! <b>Complexity</b>: Constant
68 //!
69 //! <b>Throws</b>: Nothing.
70 BOOST_INTRUSIVE_FORCEINLINE static void init(const node_ptr &this_node)
71 {
72 const node_ptr null_node((node_ptr()));
73 NodeTraits::set_next(this_node, null_node);
74 NodeTraits::set_previous(this_node, null_node);
75 }
76
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.
79 //!
80 //! <b>Complexity</b>: Constant
81 //!
82 //! <b>Throws</b>: Nothing.
83 BOOST_INTRUSIVE_FORCEINLINE static bool inited(const const_node_ptr &this_node)
84 { return !NodeTraits::get_next(this_node); }
85
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>.
90 //!
91 //! <b>Complexity</b>: Constant
92 //!
93 //! <b>Throws</b>: Nothing.
94 BOOST_INTRUSIVE_FORCEINLINE static void init_header(const node_ptr &this_node)
95 {
96 NodeTraits::set_next(this_node, this_node);
97 NodeTraits::set_previous(this_node, this_node);
98 }
99
100
101 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
102 //!
103 //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list:
104 //! <tt>return NodeTraits::get_next(this_node) == this_node</tt>
105 //!
106 //! <b>Complexity</b>: Constant
107 //!
108 //! <b>Throws</b>: Nothing.
109 BOOST_INTRUSIVE_FORCEINLINE static bool unique(const const_node_ptr &this_node)
110 {
111 node_ptr next = NodeTraits::get_next(this_node);
112 return !next || next == this_node;
113 }
114
115 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
116 //!
117 //! <b>Effects</b>: Returns the number of nodes in a circular list. If the circular list
118 //! is empty, returns 1.
119 //!
120 //! <b>Complexity</b>: Linear
121 //!
122 //! <b>Throws</b>: Nothing.
123 static std::size_t count(const const_node_ptr &this_node)
124 {
125 std::size_t result = 0;
126 const_node_ptr p = this_node;
127 do{
128 p = NodeTraits::get_next(p);
129 ++result;
130 }while (p != this_node);
131 return result;
132 }
133
134 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
135 //!
136 //! <b>Effects</b>: Unlinks the node from the circular list.
137 //!
138 //! <b>Complexity</b>: Constant
139 //!
140 //! <b>Throws</b>: Nothing.
141 BOOST_INTRUSIVE_FORCEINLINE static node_ptr unlink(const node_ptr &this_node)
142 {
143 node_ptr next(NodeTraits::get_next(this_node));
144 node_ptr prev(NodeTraits::get_previous(this_node));
145 NodeTraits::set_next(prev, next);
146 NodeTraits::set_previous(next, prev);
147 return next;
148 }
149
150 //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.
151 //!
152 //! <b>Effects</b>: Unlinks the node [b, e) from the circular list.
153 //!
154 //! <b>Complexity</b>: Constant
155 //!
156 //! <b>Throws</b>: Nothing.
157 BOOST_INTRUSIVE_FORCEINLINE static void unlink(const node_ptr &b, const node_ptr &e)
158 {
159 if (b != e) {
160 node_ptr prevb(NodeTraits::get_previous(b));
161 NodeTraits::set_previous(e, prevb);
162 NodeTraits::set_next(prevb, e);
163 }
164 }
165
166 //! <b>Requires</b>: nxt_node must be a node of a circular list.
167 //!
168 //! <b>Effects</b>: Links this_node before nxt_node in the circular list.
169 //!
170 //! <b>Complexity</b>: Constant
171 //!
172 //! <b>Throws</b>: Nothing.
173 BOOST_INTRUSIVE_FORCEINLINE static void link_before(const node_ptr &nxt_node, const node_ptr &this_node)
174 {
175 node_ptr prev(NodeTraits::get_previous(nxt_node));
176 NodeTraits::set_previous(this_node, prev);
177 NodeTraits::set_next(this_node, nxt_node);
178 //nxt_node might be an alias for prev->next_
179 //so use it before NodeTraits::set_next(prev, ...)
180 //is called and the reference changes its value
181 NodeTraits::set_previous(nxt_node, this_node);
182 NodeTraits::set_next(prev, this_node);
183 }
184
185 //! <b>Requires</b>: prev_node must be a node of a circular list.
186 //!
187 //! <b>Effects</b>: Links this_node after prev_node in the circular list.
188 //!
189 //! <b>Complexity</b>: Constant
190 //!
191 //! <b>Throws</b>: Nothing.
192 BOOST_INTRUSIVE_FORCEINLINE static void link_after(const node_ptr &prev_node, const node_ptr &this_node)
193 {
194 node_ptr next(NodeTraits::get_next(prev_node));
195 NodeTraits::set_previous(this_node, prev_node);
196 NodeTraits::set_next(this_node, next);
197 //prev_node might be an alias for next->next_
198 //so use it before update it before NodeTraits::set_previous(next, ...)
199 //is called and the reference changes it's value
200 NodeTraits::set_next(prev_node, this_node);
201 NodeTraits::set_previous(next, this_node);
202 }
203
204 //! <b>Requires</b>: this_node and other_node must be nodes inserted
205 //! in circular lists or be empty circular lists.
206 //!
207 //! <b>Effects</b>: Swaps the position of the nodes: this_node is inserted in
208 //! other_nodes position in the second circular list and the other_node is inserted
209 //! in this_node's position in the first circular list.
210 //!
211 //! <b>Complexity</b>: Constant
212 //!
213 //! <b>Throws</b>: Nothing.
214 static void swap_nodes(const node_ptr &this_node, const node_ptr &other_node)
215 {
216 if (other_node == this_node)
217 return;
218 bool this_inited = inited(this_node);
219 bool other_inited = inited(other_node);
220 if(this_inited){
221 init_header(this_node);
222 }
223 if(other_inited){
224 init_header(other_node);
225 }
226
227 node_ptr next_this(NodeTraits::get_next(this_node));
228 node_ptr prev_this(NodeTraits::get_previous(this_node));
229 node_ptr next_other(NodeTraits::get_next(other_node));
230 node_ptr prev_other(NodeTraits::get_previous(other_node));
231 //these first two swaps must happen before the other two
232 swap_prev(next_this, next_other);
233 swap_next(prev_this, prev_other);
234 swap_next(this_node, other_node);
235 swap_prev(this_node, other_node);
236
237 if(this_inited){
238 init(other_node);
239 }
240 if(other_inited){
241 init(this_node);
242 }
243 }
244
245 //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.
246 //! and p must be a node of a different circular list or may not be an iterator in
247 // [b, e).
248 //!
249 //! <b>Effects</b>: Removes the nodes from [b, e) range from their circular list and inserts
250 //! them before p in p's circular list.
251 //!
252 //! <b>Complexity</b>: Constant
253 //!
254 //! <b>Throws</b>: Nothing.
255 static void transfer(const node_ptr &p, const node_ptr &b, const node_ptr &e)
256 {
257 if (b != e) {
258 node_ptr prev_p(NodeTraits::get_previous(p));
259 node_ptr prev_b(NodeTraits::get_previous(b));
260 node_ptr prev_e(NodeTraits::get_previous(e));
261 NodeTraits::set_next(prev_e, p);
262 NodeTraits::set_previous(p, prev_e);
263 NodeTraits::set_next(prev_b, e);
264 NodeTraits::set_previous(e, prev_b);
265 NodeTraits::set_next(prev_p, b);
266 NodeTraits::set_previous(b, prev_p);
267 }
268 }
269
270 //! <b>Requires</b>: i must a node of a circular list
271 //! and p must be a node of a different circular list.
272 //!
273 //! <b>Effects</b>: Removes the node i from its circular list and inserts
274 //! it before p in p's circular list.
275 //! If p == i or p == NodeTraits::get_next(i), this function is a null operation.
276 //!
277 //! <b>Complexity</b>: Constant
278 //!
279 //! <b>Throws</b>: Nothing.
280 static void transfer(const node_ptr &p, const node_ptr &i)
281 {
282 node_ptr n(NodeTraits::get_next(i));
283 if(n != p && i != p){
284 node_ptr prev_p(NodeTraits::get_previous(p));
285 node_ptr prev_i(NodeTraits::get_previous(i));
286 NodeTraits::set_next(prev_p, i);
287 NodeTraits::set_previous(i, prev_p);
288 NodeTraits::set_next(i, p);
289 NodeTraits::set_previous(p, i);
290 NodeTraits::set_previous(n, prev_i);
291 NodeTraits::set_next(prev_i, n);
292
293 }
294 }
295
296 //! <b>Effects</b>: Reverses the order of elements in the list.
297 //!
298 //! <b>Throws</b>: Nothing.
299 //!
300 //! <b>Complexity</b>: This function is linear time.
301 static void reverse(const node_ptr &p)
302 {
303 node_ptr f(NodeTraits::get_next(p));
304 node_ptr i(NodeTraits::get_next(f)), e(p);
305
306 while(i != e) {
307 node_ptr n = i;
308 i = NodeTraits::get_next(i);
309 transfer(f, n, i);
310 f = n;
311 }
312 }
313
314 //! <b>Effects</b>: Moves the node p n positions towards the end of the list.
315 //!
316 //! <b>Throws</b>: Nothing.
317 //!
318 //! <b>Complexity</b>: Linear to the number of moved positions.
319 static void move_backwards(const node_ptr &p, std::size_t n)
320 {
321 //Null shift, nothing to do
322 if(!n) return;
323 node_ptr first = NodeTraits::get_next(p);
324 //size() == 0 or 1, nothing to do
325 if(first == NodeTraits::get_previous(p)) return;
326 unlink(p);
327 //Now get the new first node
328 while(n--){
329 first = NodeTraits::get_next(first);
330 }
331 link_before(first, p);
332 }
333
334 //! <b>Effects</b>: Moves the node p n positions towards the beginning of the list.
335 //!
336 //! <b>Throws</b>: Nothing.
337 //!
338 //! <b>Complexity</b>: Linear to the number of moved positions.
339 static void move_forward(const node_ptr &p, std::size_t n)
340 {
341 //Null shift, nothing to do
342 if(!n) return;
343 node_ptr last = NodeTraits::get_previous(p);
344 //size() == 0 or 1, nothing to do
345 if(last == NodeTraits::get_next(p)) return;
346
347 unlink(p);
348 //Now get the new last node
349 while(n--){
350 last = NodeTraits::get_previous(last);
351 }
352 link_after(last, p);
353 }
354
355 //! <b>Requires</b>: f and l must be in a circular list.
356 //!
357 //! <b>Effects</b>: Returns the number of nodes in the range [f, l).
358 //!
359 //! <b>Complexity</b>: Linear
360 //!
361 //! <b>Throws</b>: Nothing.
362 static std::size_t distance(const const_node_ptr &f, const const_node_ptr &l)
363 {
364 const_node_ptr i(f);
365 std::size_t result = 0;
366 while(i != l){
367 i = NodeTraits::get_next(i);
368 ++result;
369 }
370 return result;
371 }
372
373 struct stable_partition_info
374 {
375 std::size_t num_1st_partition;
376 std::size_t num_2nd_partition;
377 node_ptr beg_2st_partition;
378 };
379
380 template<class Pred>
381 static void stable_partition(node_ptr beg, const node_ptr &end, Pred pred, stable_partition_info &info)
382 {
383 node_ptr bcur = node_traits::get_previous(beg);
384 node_ptr cur = beg;
385 node_ptr new_f = end;
386
387 std::size_t num1 = 0, num2 = 0;
388 while(cur != end){
389 if(pred(cur)){
390 ++num1;
391 bcur = cur;
392 cur = node_traits::get_next(cur);
393 }
394 else{
395 ++num2;
396 node_ptr last_to_remove = bcur;
397 new_f = cur;
398 bcur = cur;
399 cur = node_traits::get_next(cur);
400 BOOST_TRY{
401 //Main loop
402 while(cur != end){
403 if(pred(cur)){ //Might throw
404 ++num1;
405 //Process current node
406 node_traits::set_next (last_to_remove, cur);
407 node_traits::set_previous(cur, last_to_remove);
408 last_to_remove = cur;
409 node_ptr nxt = node_traits::get_next(cur);
410 node_traits::set_next (bcur, nxt);
411 node_traits::set_previous(nxt, bcur);
412 cur = nxt;
413 }
414 else{
415 ++num2;
416 bcur = cur;
417 cur = node_traits::get_next(cur);
418 }
419 }
420 }
421 BOOST_CATCH(...){
422 node_traits::set_next (last_to_remove, new_f);
423 node_traits::set_previous(new_f, last_to_remove);
424 BOOST_RETHROW;
425 }
426 BOOST_CATCH_END
427 node_traits::set_next(last_to_remove, new_f);
428 node_traits::set_previous(new_f, last_to_remove);
429 break;
430 }
431 }
432 info.num_1st_partition = num1;
433 info.num_2nd_partition = num2;
434 info.beg_2st_partition = new_f;
435 }
436
437 private:
438 BOOST_INTRUSIVE_FORCEINLINE static void swap_prev(const node_ptr &this_node, const node_ptr &other_node)
439 {
440 node_ptr temp(NodeTraits::get_previous(this_node));
441 NodeTraits::set_previous(this_node, NodeTraits::get_previous(other_node));
442 NodeTraits::set_previous(other_node, temp);
443 }
444
445 BOOST_INTRUSIVE_FORCEINLINE static void swap_next(const node_ptr &this_node, const node_ptr &other_node)
446 {
447 node_ptr temp(NodeTraits::get_next(this_node));
448 NodeTraits::set_next(this_node, NodeTraits::get_next(other_node));
449 NodeTraits::set_next(other_node, temp);
450 }
451};
452
453/// @cond
454
455template<class NodeTraits>
456struct get_algo<CircularListAlgorithms, NodeTraits>
457{
458 typedef circular_list_algorithms<NodeTraits> type;
459};
460
461/// @endcond
462
463} //namespace intrusive
464} //namespace boost
465
466#include <boost/intrusive/detail/config_end.hpp>
467
468#endif //BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP
469