]>
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. | |
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 | ||
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 |