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 | |
27 | namespace boost { |
28 | namespace 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> |
55 | template<class NodeTraits> |
56 | class 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 | 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 | 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 | static void (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 | 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 | 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 | 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 | 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 it's 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 | 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(this_node: other_node); |
220 | if(this_inited){ |
221 | init_header(this_node); |
222 | } |
223 | if(other_inited){ |
224 | init_header(this_node: 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(this_node: next_this, other_node: next_other); |
233 | swap_next(this_node: prev_this, other_node: prev_other); |
234 | swap_next(this_node, other_node); |
235 | swap_prev(this_node, other_node); |
236 | |
237 | if(this_inited){ |
238 | init(this_node: 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(nxt_node: first, this_node: 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(prev_node: last, this_node: 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 | 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 | 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 | |
455 | template<class NodeTraits> |
456 | struct 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 | |