]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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. | |
1e59de90 | 70 | static void init(node_ptr this_node) BOOST_NOEXCEPT |
7c673cae | 71 | { |
b32b8144 | 72 | const node_ptr null_node = node_ptr(); |
7c673cae FG |
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. | |
1e59de90 | 83 | BOOST_INTRUSIVE_FORCEINLINE static bool inited(const_node_ptr this_node) BOOST_NOEXCEPT |
7c673cae FG |
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. | |
1e59de90 | 94 | static void init_header(node_ptr this_node) BOOST_NOEXCEPT |
7c673cae FG |
95 | { |
96 | NodeTraits::set_next(this_node, this_node); | |
97 | NodeTraits::set_previous(this_node, this_node); | |
98 | } | |
99 | ||
7c673cae FG |
100 | //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list. |
101 | //! | |
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> | |
104 | //! | |
105 | //! <b>Complexity</b>: Constant | |
106 | //! | |
107 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 108 | static bool unique(const_node_ptr this_node) BOOST_NOEXCEPT |
7c673cae FG |
109 | { |
110 | node_ptr next = NodeTraits::get_next(this_node); | |
111 | return !next || next == this_node; | |
112 | } | |
113 | ||
114 | //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list. | |
115 | //! | |
116 | //! <b>Effects</b>: Returns the number of nodes in a circular list. If the circular list | |
117 | //! is empty, returns 1. | |
118 | //! | |
119 | //! <b>Complexity</b>: Linear | |
120 | //! | |
121 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 122 | static std::size_t count(const_node_ptr this_node) BOOST_NOEXCEPT |
7c673cae FG |
123 | { |
124 | std::size_t result = 0; | |
125 | const_node_ptr p = this_node; | |
126 | do{ | |
127 | p = NodeTraits::get_next(p); | |
128 | ++result; | |
129 | }while (p != this_node); | |
130 | return result; | |
131 | } | |
132 | ||
133 | //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list. | |
134 | //! | |
135 | //! <b>Effects</b>: Unlinks the node from the circular list. | |
136 | //! | |
137 | //! <b>Complexity</b>: Constant | |
138 | //! | |
139 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 140 | static node_ptr unlink(node_ptr this_node) BOOST_NOEXCEPT |
7c673cae FG |
141 | { |
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); | |
146 | return next; | |
147 | } | |
148 | ||
149 | //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range. | |
150 | //! | |
151 | //! <b>Effects</b>: Unlinks the node [b, e) from the circular list. | |
152 | //! | |
153 | //! <b>Complexity</b>: Constant | |
154 | //! | |
155 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 156 | static void unlink(node_ptr b, node_ptr e) BOOST_NOEXCEPT |
7c673cae FG |
157 | { |
158 | if (b != e) { | |
159 | node_ptr prevb(NodeTraits::get_previous(b)); | |
160 | NodeTraits::set_previous(e, prevb); | |
161 | NodeTraits::set_next(prevb, e); | |
162 | } | |
163 | } | |
164 | ||
165 | //! <b>Requires</b>: nxt_node must be a node of a circular list. | |
166 | //! | |
167 | //! <b>Effects</b>: Links this_node before nxt_node in the circular list. | |
168 | //! | |
169 | //! <b>Complexity</b>: Constant | |
170 | //! | |
171 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 172 | static void link_before(node_ptr nxt_node, node_ptr this_node) BOOST_NOEXCEPT |
7c673cae FG |
173 | { |
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); | |
182 | } | |
183 | ||
184 | //! <b>Requires</b>: prev_node must be a node of a circular list. | |
185 | //! | |
186 | //! <b>Effects</b>: Links this_node after prev_node in the circular list. | |
187 | //! | |
188 | //! <b>Complexity</b>: Constant | |
189 | //! | |
190 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 191 | static void link_after(node_ptr prev_node, node_ptr this_node) BOOST_NOEXCEPT |
7c673cae FG |
192 | { |
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); | |
201 | } | |
202 | ||
203 | //! <b>Requires</b>: this_node and other_node must be nodes inserted | |
204 | //! in circular lists or be empty circular lists. | |
205 | //! | |
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. | |
209 | //! | |
210 | //! <b>Complexity</b>: Constant | |
211 | //! | |
212 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 213 | static void swap_nodes(node_ptr this_node, node_ptr other_node) BOOST_NOEXCEPT |
7c673cae FG |
214 | { |
215 | if (other_node == this_node) | |
216 | return; | |
217 | bool this_inited = inited(this_node); | |
218 | bool other_inited = inited(other_node); | |
219 | if(this_inited){ | |
220 | init_header(this_node); | |
221 | } | |
222 | if(other_inited){ | |
223 | init_header(other_node); | |
224 | } | |
225 | ||
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); | |
235 | ||
236 | if(this_inited){ | |
237 | init(other_node); | |
238 | } | |
239 | if(other_inited){ | |
240 | init(this_node); | |
241 | } | |
242 | } | |
243 | ||
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 | |
246 | // [b, e). | |
247 | //! | |
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. | |
250 | //! | |
251 | //! <b>Complexity</b>: Constant | |
252 | //! | |
253 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 254 | static void transfer(node_ptr p, node_ptr b, node_ptr e) BOOST_NOEXCEPT |
7c673cae | 255 | { |
1e59de90 | 256 | if (b != e && p != b && p != e) { |
7c673cae FG |
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); | |
266 | } | |
267 | } | |
268 | ||
269 | //! <b>Requires</b>: i must a node of a circular list | |
270 | //! and p must be a node of a different circular list. | |
271 | //! | |
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. | |
275 | //! | |
276 | //! <b>Complexity</b>: Constant | |
277 | //! | |
278 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 279 | static void transfer(node_ptr p, node_ptr i) BOOST_NOEXCEPT |
7c673cae FG |
280 | { |
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); | |
291 | ||
292 | } | |
293 | } | |
294 | ||
295 | //! <b>Effects</b>: Reverses the order of elements in the list. | |
296 | //! | |
297 | //! <b>Throws</b>: Nothing. | |
298 | //! | |
299 | //! <b>Complexity</b>: This function is linear time. | |
1e59de90 | 300 | static void reverse(node_ptr p) BOOST_NOEXCEPT |
7c673cae FG |
301 | { |
302 | node_ptr f(NodeTraits::get_next(p)); | |
303 | node_ptr i(NodeTraits::get_next(f)), e(p); | |
304 | ||
305 | while(i != e) { | |
306 | node_ptr n = i; | |
307 | i = NodeTraits::get_next(i); | |
308 | transfer(f, n, i); | |
309 | f = n; | |
310 | } | |
311 | } | |
312 | ||
313 | //! <b>Effects</b>: Moves the node p n positions towards the end of the list. | |
314 | //! | |
315 | //! <b>Throws</b>: Nothing. | |
316 | //! | |
317 | //! <b>Complexity</b>: Linear to the number of moved positions. | |
1e59de90 | 318 | static void move_backwards(node_ptr p, std::size_t n) BOOST_NOEXCEPT |
7c673cae FG |
319 | { |
320 | //Null shift, nothing to do | |
321 | if(!n) return; | |
322 | node_ptr first = NodeTraits::get_next(p); | |
323 | //size() == 0 or 1, nothing to do | |
324 | if(first == NodeTraits::get_previous(p)) return; | |
325 | unlink(p); | |
326 | //Now get the new first node | |
327 | while(n--){ | |
328 | first = NodeTraits::get_next(first); | |
329 | } | |
330 | link_before(first, p); | |
331 | } | |
332 | ||
333 | //! <b>Effects</b>: Moves the node p n positions towards the beginning of the list. | |
334 | //! | |
335 | //! <b>Throws</b>: Nothing. | |
336 | //! | |
337 | //! <b>Complexity</b>: Linear to the number of moved positions. | |
1e59de90 | 338 | static void move_forward(node_ptr p, std::size_t n) BOOST_NOEXCEPT |
7c673cae FG |
339 | { |
340 | //Null shift, nothing to do | |
341 | if(!n) return; | |
342 | node_ptr last = NodeTraits::get_previous(p); | |
343 | //size() == 0 or 1, nothing to do | |
344 | if(last == NodeTraits::get_next(p)) return; | |
345 | ||
346 | unlink(p); | |
347 | //Now get the new last node | |
348 | while(n--){ | |
349 | last = NodeTraits::get_previous(last); | |
350 | } | |
351 | link_after(last, p); | |
352 | } | |
353 | ||
354 | //! <b>Requires</b>: f and l must be in a circular list. | |
355 | //! | |
356 | //! <b>Effects</b>: Returns the number of nodes in the range [f, l). | |
357 | //! | |
358 | //! <b>Complexity</b>: Linear | |
359 | //! | |
360 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 361 | static std::size_t distance(const_node_ptr f, const_node_ptr l) BOOST_NOEXCEPT |
7c673cae | 362 | { |
7c673cae | 363 | std::size_t result = 0; |
1e59de90 TL |
364 | while(f != l){ |
365 | f = NodeTraits::get_next(f); | |
7c673cae FG |
366 | ++result; |
367 | } | |
368 | return result; | |
369 | } | |
370 | ||
371 | struct stable_partition_info | |
372 | { | |
373 | std::size_t num_1st_partition; | |
374 | std::size_t num_2nd_partition; | |
375 | node_ptr beg_2st_partition; | |
376 | }; | |
377 | ||
378 | template<class Pred> | |
92f5a8d4 | 379 | static void stable_partition(node_ptr beg, node_ptr end, Pred pred, stable_partition_info &info) |
7c673cae FG |
380 | { |
381 | node_ptr bcur = node_traits::get_previous(beg); | |
382 | node_ptr cur = beg; | |
383 | node_ptr new_f = end; | |
384 | ||
385 | std::size_t num1 = 0, num2 = 0; | |
386 | while(cur != end){ | |
387 | if(pred(cur)){ | |
388 | ++num1; | |
389 | bcur = cur; | |
390 | cur = node_traits::get_next(cur); | |
391 | } | |
392 | else{ | |
393 | ++num2; | |
394 | node_ptr last_to_remove = bcur; | |
395 | new_f = cur; | |
396 | bcur = cur; | |
397 | cur = node_traits::get_next(cur); | |
398 | BOOST_TRY{ | |
399 | //Main loop | |
400 | while(cur != end){ | |
401 | if(pred(cur)){ //Might throw | |
402 | ++num1; | |
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); | |
410 | cur = nxt; | |
411 | } | |
412 | else{ | |
413 | ++num2; | |
414 | bcur = cur; | |
415 | cur = node_traits::get_next(cur); | |
416 | } | |
417 | } | |
418 | } | |
419 | BOOST_CATCH(...){ | |
420 | node_traits::set_next (last_to_remove, new_f); | |
421 | node_traits::set_previous(new_f, last_to_remove); | |
422 | BOOST_RETHROW; | |
423 | } | |
424 | BOOST_CATCH_END | |
425 | node_traits::set_next(last_to_remove, new_f); | |
426 | node_traits::set_previous(new_f, last_to_remove); | |
427 | break; | |
428 | } | |
429 | } | |
430 | info.num_1st_partition = num1; | |
431 | info.num_2nd_partition = num2; | |
432 | info.beg_2st_partition = new_f; | |
433 | } | |
434 | ||
435 | private: | |
1e59de90 | 436 | static void swap_prev(node_ptr this_node, node_ptr other_node) BOOST_NOEXCEPT |
7c673cae FG |
437 | { |
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); | |
441 | } | |
442 | ||
1e59de90 | 443 | static void swap_next(node_ptr this_node, node_ptr other_node) BOOST_NOEXCEPT |
7c673cae FG |
444 | { |
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); | |
448 | } | |
449 | }; | |
450 | ||
451 | /// @cond | |
452 | ||
453 | template<class NodeTraits> | |
454 | struct get_algo<CircularListAlgorithms, NodeTraits> | |
455 | { | |
456 | typedef circular_list_algorithms<NodeTraits> type; | |
457 | }; | |
458 | ||
459 | /// @endcond | |
460 | ||
461 | } //namespace intrusive | |
462 | } //namespace boost | |
463 | ||
464 | #include <boost/intrusive/detail/config_end.hpp> | |
465 | ||
466 | #endif //BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP |