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 | // The tree destruction algorithm is based on Julienne Walker and The EC Team code: |
15 | // |
16 | // This code is in the public domain. Anyone may use it or change it in any way that |
17 | // they see fit. The author assumes no responsibility for damages incurred through |
18 | // use of the original code or any variations thereof. |
19 | // |
20 | // It is requested, but not required, that due credit is given to the original author |
21 | // and anyone who has modified the code through a header comment, such as this one. |
22 | |
23 | #ifndef BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP |
24 | #define BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP |
25 | |
26 | #include <boost/intrusive/detail/config_begin.hpp> |
27 | #include <boost/intrusive/intrusive_fwd.hpp> |
28 | |
29 | #include <cstddef> |
30 | |
31 | #include <boost/intrusive/detail/assert.hpp> |
32 | #include <boost/intrusive/detail/algo_type.hpp> |
33 | #include <boost/intrusive/bstree_algorithms.hpp> |
34 | #include <boost/intrusive/detail/ebo_functor_holder.hpp> |
35 | |
36 | #if defined(BOOST_HAS_PRAGMA_ONCE) |
37 | # pragma once |
38 | #endif |
39 | |
40 | namespace boost { |
41 | namespace intrusive { |
42 | |
43 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
44 | |
45 | template<class NodeTraits, class F> |
46 | struct rbtree_node_cloner |
47 | //Use public inheritance to avoid MSVC bugs with closures |
48 | : public detail::ebo_functor_holder<F> |
49 | { |
50 | typedef typename NodeTraits::node_ptr node_ptr; |
51 | typedef detail::ebo_functor_holder<F> base_t; |
52 | |
53 | explicit rbtree_node_cloner(F f) |
54 | : base_t(f) |
55 | {} |
56 | |
57 | node_ptr operator()(const node_ptr & p) |
58 | { |
59 | node_ptr n = base_t::get()(p); |
60 | NodeTraits::set_color(n, NodeTraits::get_color(p)); |
61 | return n; |
62 | } |
63 | }; |
64 | |
65 | namespace detail { |
66 | |
67 | template<class ValueTraits, class NodePtrCompare, class ExtraChecker> |
68 | struct rbtree_node_checker |
69 | : public bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> |
70 | { |
71 | typedef bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> base_checker_t; |
72 | typedef ValueTraits value_traits; |
73 | typedef typename value_traits::node_traits node_traits; |
74 | typedef typename node_traits::const_node_ptr const_node_ptr; |
75 | typedef typename node_traits::node_ptr node_ptr; |
76 | |
77 | struct return_type |
78 | : public base_checker_t::return_type |
79 | { |
80 | return_type() : black_count_(0) {} |
81 | std::size_t black_count_; |
82 | }; |
83 | |
84 | rbtree_node_checker(const NodePtrCompare& comp, ExtraChecker ) |
85 | : base_checker_t(comp, extra_checker) |
86 | {} |
87 | |
88 | void operator () (const const_node_ptr& p, |
89 | const return_type& check_return_left, const return_type& check_return_right, |
90 | return_type& check_return) |
91 | { |
92 | |
93 | if (node_traits::get_color(p) == node_traits::red()){ |
94 | //Red nodes have black children |
95 | const node_ptr p_left(node_traits::get_left(p)); (void)p_left; |
96 | const node_ptr p_right(node_traits::get_right(p)); (void)p_right; |
97 | BOOST_INTRUSIVE_INVARIANT_ASSERT(!p_left || node_traits::get_color(p_left) == node_traits::black()); |
98 | BOOST_INTRUSIVE_INVARIANT_ASSERT(!p_right || node_traits::get_color(p_right) == node_traits::black()); |
99 | //Red node can't be root |
100 | BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_parent(node_traits::get_parent(p)) != p); |
101 | } |
102 | //Every path to p contains the same number of black nodes |
103 | const std::size_t l_black_count = check_return_left.black_count_; |
104 | BOOST_INTRUSIVE_INVARIANT_ASSERT(l_black_count == check_return_right.black_count_); |
105 | check_return.black_count_ = l_black_count + |
106 | static_cast<std::size_t>(node_traits::get_color(p) == node_traits::black()); |
107 | base_checker_t::operator()(p, check_return_left, check_return_right, check_return); |
108 | } |
109 | }; |
110 | |
111 | } // namespace detail |
112 | |
113 | #endif //#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
114 | |
115 | //! rbtree_algorithms provides basic algorithms to manipulate |
116 | //! nodes forming a red-black tree. The insertion and deletion algorithms are |
117 | //! based on those in Cormen, Leiserson, and Rivest, Introduction to Algorithms |
118 | //! (MIT Press, 1990), except that |
119 | //! |
120 | //! (1) the header node is maintained with links not only to the root |
121 | //! but also to the leftmost node of the tree, to enable constant time |
122 | //! begin(), and to the rightmost node of the tree, to enable linear time |
123 | //! performance when used with the generic set algorithms (set_union, |
124 | //! etc.); |
125 | //! |
126 | //! (2) when a node being deleted has two children its successor node is |
127 | //! relinked into its place, rather than copied, so that the only |
128 | //! pointers invalidated are those referring to the deleted node. |
129 | //! |
130 | //! rbtree_algorithms is configured with a NodeTraits class, which encapsulates the |
131 | //! information about the node to be manipulated. NodeTraits must support the |
132 | //! following interface: |
133 | //! |
134 | //! <b>Typedefs</b>: |
135 | //! |
136 | //! <tt>node</tt>: The type of the node that forms the binary search tree |
137 | //! |
138 | //! <tt>node_ptr</tt>: A pointer to a node |
139 | //! |
140 | //! <tt>const_node_ptr</tt>: A pointer to a const node |
141 | //! |
142 | //! <tt>color</tt>: The type that can store the color of a node |
143 | //! |
144 | //! <b>Static functions</b>: |
145 | //! |
146 | //! <tt>static node_ptr get_parent(const_node_ptr n);</tt> |
147 | //! |
148 | //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt> |
149 | //! |
150 | //! <tt>static node_ptr get_left(const_node_ptr n);</tt> |
151 | //! |
152 | //! <tt>static void set_left(node_ptr n, node_ptr left);</tt> |
153 | //! |
154 | //! <tt>static node_ptr get_right(const_node_ptr n);</tt> |
155 | //! |
156 | //! <tt>static void set_right(node_ptr n, node_ptr right);</tt> |
157 | //! |
158 | //! <tt>static color get_color(const_node_ptr n);</tt> |
159 | //! |
160 | //! <tt>static void set_color(node_ptr n, color c);</tt> |
161 | //! |
162 | //! <tt>static color black();</tt> |
163 | //! |
164 | //! <tt>static color red();</tt> |
165 | template<class NodeTraits> |
166 | class rbtree_algorithms |
167 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
168 | : public bstree_algorithms<NodeTraits> |
169 | #endif |
170 | { |
171 | public: |
172 | typedef NodeTraits node_traits; |
173 | typedef typename NodeTraits::node node; |
174 | typedef typename NodeTraits::node_ptr node_ptr; |
175 | typedef typename NodeTraits::const_node_ptr const_node_ptr; |
176 | typedef typename NodeTraits::color color; |
177 | |
178 | /// @cond |
179 | private: |
180 | |
181 | typedef bstree_algorithms<NodeTraits> bstree_algo; |
182 | |
183 | /// @endcond |
184 | |
185 | public: |
186 | |
187 | //! This type is the information that will be |
188 | //! filled by insert_unique_check |
189 | typedef typename bstree_algo::insert_commit_data insert_commit_data; |
190 | |
191 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
192 | |
193 | //! @copydoc ::boost::intrusive::bstree_algorithms::get_header(const const_node_ptr&) |
194 | static node_ptr get_header(const const_node_ptr & n); |
195 | |
196 | //! @copydoc ::boost::intrusive::bstree_algorithms::begin_node |
197 | static node_ptr begin_node(const const_node_ptr & header); |
198 | |
199 | //! @copydoc ::boost::intrusive::bstree_algorithms::end_node |
200 | static node_ptr end_node(const const_node_ptr & header); |
201 | |
202 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree |
203 | static void swap_tree(const node_ptr & header1, const node_ptr & header2); |
204 | |
205 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
206 | |
207 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&) |
208 | static void swap_nodes(const node_ptr & node1, const node_ptr & node2) |
209 | { |
210 | if(node1 == node2) |
211 | return; |
212 | |
213 | node_ptr (bstree_algo::get_header(node1)), (bstree_algo::get_header(node2)); |
214 | swap_nodes(node1, header1, node2, header2); |
215 | } |
216 | |
217 | //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&,const node_ptr&,const node_ptr&) |
218 | static void swap_nodes(const node_ptr & node1, const node_ptr & , const node_ptr & node2, const node_ptr & ) |
219 | { |
220 | if(node1 == node2) return; |
221 | |
222 | bstree_algo::swap_nodes(node1, header1, node2, header2); |
223 | //Swap color |
224 | color c = NodeTraits::get_color(node1); |
225 | NodeTraits::set_color(node1, NodeTraits::get_color(node2)); |
226 | NodeTraits::set_color(node2, c); |
227 | } |
228 | |
229 | //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&) |
230 | static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node) |
231 | { |
232 | if(node_to_be_replaced == new_node) |
233 | return; |
234 | replace_node(node_to_be_replaced, bstree_algo::get_header(node_to_be_replaced), new_node); |
235 | } |
236 | |
237 | //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&,const node_ptr&) |
238 | static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & , const node_ptr & new_node) |
239 | { |
240 | bstree_algo::replace_node(node_to_be_replaced, header, new_node); |
241 | NodeTraits::set_color(new_node, NodeTraits::get_color(node_to_be_replaced)); |
242 | } |
243 | |
244 | //! @copydoc ::boost::intrusive::bstree_algorithms::unlink(const node_ptr&) |
245 | static void unlink(const node_ptr& node) |
246 | { |
247 | node_ptr x = NodeTraits::get_parent(node); |
248 | if(x){ |
249 | while(!is_header(p: x)) |
250 | x = NodeTraits::get_parent(x); |
251 | erase(header: x, z: node); |
252 | } |
253 | } |
254 | |
255 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
256 | //! @copydoc ::boost::intrusive::bstree_algorithms::unlink_leftmost_without_rebalance |
257 | static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header); |
258 | |
259 | //! @copydoc ::boost::intrusive::bstree_algorithms::unique(const const_node_ptr&) |
260 | static bool unique(const const_node_ptr & node); |
261 | |
262 | //! @copydoc ::boost::intrusive::bstree_algorithms::size(const const_node_ptr&) |
263 | static std::size_t size(const const_node_ptr & header); |
264 | |
265 | //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(const node_ptr&) |
266 | static node_ptr next_node(const node_ptr & node); |
267 | |
268 | //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(const node_ptr&) |
269 | static node_ptr prev_node(const node_ptr & node); |
270 | |
271 | //! @copydoc ::boost::intrusive::bstree_algorithms::init(const node_ptr&) |
272 | static void init(const node_ptr & node); |
273 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
274 | |
275 | //! @copydoc ::boost::intrusive::bstree_algorithms::init_header(const node_ptr&) |
276 | static void (const node_ptr & ) |
277 | { |
278 | bstree_algo::init_header(header); |
279 | NodeTraits::set_color(header, NodeTraits::red()); |
280 | } |
281 | |
282 | //! @copydoc ::boost::intrusive::bstree_algorithms::erase(const node_ptr&,const node_ptr&) |
283 | static node_ptr erase(const node_ptr & , const node_ptr & z) |
284 | { |
285 | typename bstree_algo::data_for_rebalance info; |
286 | bstree_algo::erase(header, z, info); |
287 | |
288 | color new_z_color; |
289 | if(info.y != z){ |
290 | new_z_color = NodeTraits::get_color(info.y); |
291 | NodeTraits::set_color(info.y, NodeTraits::get_color(z)); |
292 | } |
293 | else{ |
294 | new_z_color = NodeTraits::get_color(z); |
295 | } |
296 | //Rebalance rbtree if needed |
297 | if(new_z_color != NodeTraits::red()){ |
298 | rebalance_after_erasure(header, x: info.x, x_parent: info.x_parent); |
299 | } |
300 | return z; |
301 | } |
302 | |
303 | //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer) |
304 | template <class Cloner, class Disposer> |
305 | static void clone |
306 | (const const_node_ptr & , const node_ptr & , Cloner cloner, Disposer disposer) |
307 | { |
308 | rbtree_node_cloner<NodeTraits, Cloner> new_cloner(cloner); |
309 | bstree_algo::clone(source_header, target_header, new_cloner, disposer); |
310 | } |
311 | |
312 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
313 | //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer) |
314 | template<class Disposer> |
315 | static void clear_and_dispose(const node_ptr & header, Disposer disposer); |
316 | |
317 | //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
318 | template<class KeyType, class KeyNodePtrCompare> |
319 | static node_ptr lower_bound |
320 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); |
321 | |
322 | //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
323 | template<class KeyType, class KeyNodePtrCompare> |
324 | static node_ptr upper_bound |
325 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); |
326 | |
327 | //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) |
328 | template<class KeyType, class KeyNodePtrCompare> |
329 | static node_ptr find |
330 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); |
331 | |
332 | //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
333 | template<class KeyType, class KeyNodePtrCompare> |
334 | static std::pair<node_ptr, node_ptr> equal_range |
335 | (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); |
336 | |
337 | //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) |
338 | template<class KeyType, class KeyNodePtrCompare> |
339 | static std::pair<node_ptr, node_ptr> bounded_range |
340 | (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp |
341 | , bool left_closed, bool right_closed); |
342 | |
343 | //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) |
344 | template<class KeyType, class KeyNodePtrCompare> |
345 | static std::size_t count(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); |
346 | |
347 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
348 | |
349 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(const node_ptr&,const node_ptr&,NodePtrCompare) |
350 | template<class NodePtrCompare> |
351 | static node_ptr insert_equal_upper_bound |
352 | (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp) |
353 | { |
354 | bstree_algo::insert_equal_upper_bound(h, new_node, comp); |
355 | rebalance_after_insertion(header: h, p: new_node); |
356 | return new_node; |
357 | } |
358 | |
359 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(const node_ptr&,const node_ptr&,NodePtrCompare) |
360 | template<class NodePtrCompare> |
361 | static node_ptr insert_equal_lower_bound |
362 | (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp) |
363 | { |
364 | bstree_algo::insert_equal_lower_bound(h, new_node, comp); |
365 | rebalance_after_insertion(header: h, p: new_node); |
366 | return new_node; |
367 | } |
368 | |
369 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(const node_ptr&,const node_ptr&,const node_ptr&,NodePtrCompare) |
370 | template<class NodePtrCompare> |
371 | static node_ptr insert_equal |
372 | (const node_ptr & , const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp) |
373 | { |
374 | bstree_algo::insert_equal(header, hint, new_node, comp); |
375 | rebalance_after_insertion(header, p: new_node); |
376 | return new_node; |
377 | } |
378 | |
379 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&) |
380 | static node_ptr insert_before |
381 | (const node_ptr & , const node_ptr & pos, const node_ptr & new_node) |
382 | { |
383 | bstree_algo::insert_before(header, pos, new_node); |
384 | rebalance_after_insertion(header, p: new_node); |
385 | return new_node; |
386 | } |
387 | |
388 | //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&) |
389 | static void push_back(const node_ptr & , const node_ptr & new_node) |
390 | { |
391 | bstree_algo::push_back(header, new_node); |
392 | rebalance_after_insertion(header, p: new_node); |
393 | } |
394 | |
395 | //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&) |
396 | static void push_front(const node_ptr & , const node_ptr & new_node) |
397 | { |
398 | bstree_algo::push_front(header, new_node); |
399 | rebalance_after_insertion(header, p: new_node); |
400 | } |
401 | |
402 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
403 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) |
404 | template<class KeyType, class KeyNodePtrCompare> |
405 | static std::pair<node_ptr, bool> insert_unique_check |
406 | (const const_node_ptr & header, const KeyType &key |
407 | ,KeyNodePtrCompare comp, insert_commit_data &commit_data); |
408 | |
409 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) |
410 | template<class KeyType, class KeyNodePtrCompare> |
411 | static std::pair<node_ptr, bool> insert_unique_check |
412 | (const const_node_ptr & header, const node_ptr &hint, const KeyType &key |
413 | ,KeyNodePtrCompare comp, insert_commit_data &commit_data); |
414 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
415 | |
416 | //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data&) |
417 | static void insert_unique_commit |
418 | (const node_ptr & , const node_ptr & new_value, const insert_commit_data &commit_data) |
419 | { |
420 | bstree_algo::insert_unique_commit(header, new_value, commit_data); |
421 | rebalance_after_insertion(header, p: new_value); |
422 | } |
423 | |
424 | //! @copydoc ::boost::intrusive::bstree_algorithms::is_header |
425 | static bool (const const_node_ptr & p) |
426 | { |
427 | return NodeTraits::get_color(p) == NodeTraits::red() && |
428 | bstree_algo::is_header(p); |
429 | } |
430 | |
431 | /// @cond |
432 | private: |
433 | |
434 | static void rebalance_after_erasure(const node_ptr & , node_ptr x, node_ptr x_parent) |
435 | { |
436 | while(1){ |
437 | if(x_parent == header || (x && NodeTraits::get_color(x) != NodeTraits::black())){ |
438 | break; |
439 | } |
440 | //Don't cache x_is_leftchild or similar because x can be null and |
441 | //equal to both x_parent_left and x_parent_right |
442 | const node_ptr x_parent_left(NodeTraits::get_left(x_parent)); |
443 | if(x == x_parent_left){ //x is left child |
444 | node_ptr w = NodeTraits::get_right(x_parent); |
445 | BOOST_INTRUSIVE_INVARIANT_ASSERT(w); |
446 | if(NodeTraits::get_color(w) == NodeTraits::red()){ |
447 | NodeTraits::set_color(w, NodeTraits::black()); |
448 | NodeTraits::set_color(x_parent, NodeTraits::red()); |
449 | bstree_algo::rotate_left(x_parent, w, NodeTraits::get_parent(x_parent), header); |
450 | w = NodeTraits::get_right(x_parent); |
451 | BOOST_INTRUSIVE_INVARIANT_ASSERT(w); |
452 | } |
453 | node_ptr const w_left (NodeTraits::get_left(w)); |
454 | node_ptr const w_right(NodeTraits::get_right(w)); |
455 | if((!w_left || NodeTraits::get_color(w_left) == NodeTraits::black()) && |
456 | (!w_right || NodeTraits::get_color(w_right) == NodeTraits::black())){ |
457 | NodeTraits::set_color(w, NodeTraits::red()); |
458 | x = x_parent; |
459 | x_parent = NodeTraits::get_parent(x_parent); |
460 | } |
461 | else { |
462 | if(!w_right || NodeTraits::get_color(w_right) == NodeTraits::black()){ |
463 | NodeTraits::set_color(w_left, NodeTraits::black()); |
464 | NodeTraits::set_color(w, NodeTraits::red()); |
465 | bstree_algo::rotate_right(w, w_left, NodeTraits::get_parent(w), header); |
466 | w = NodeTraits::get_right(x_parent); |
467 | BOOST_INTRUSIVE_INVARIANT_ASSERT(w); |
468 | } |
469 | NodeTraits::set_color(w, NodeTraits::get_color(x_parent)); |
470 | NodeTraits::set_color(x_parent, NodeTraits::black()); |
471 | const node_ptr new_wright(NodeTraits::get_right(w)); |
472 | if(new_wright) |
473 | NodeTraits::set_color(new_wright, NodeTraits::black()); |
474 | bstree_algo::rotate_left(x_parent, NodeTraits::get_right(x_parent), NodeTraits::get_parent(x_parent), header); |
475 | break; |
476 | } |
477 | } |
478 | else { |
479 | // same as above, with right_ <-> left_. |
480 | node_ptr w = x_parent_left; |
481 | if(NodeTraits::get_color(w) == NodeTraits::red()){ |
482 | NodeTraits::set_color(w, NodeTraits::black()); |
483 | NodeTraits::set_color(x_parent, NodeTraits::red()); |
484 | bstree_algo::rotate_right(x_parent, w, NodeTraits::get_parent(x_parent), header); |
485 | w = NodeTraits::get_left(x_parent); |
486 | BOOST_INTRUSIVE_INVARIANT_ASSERT(w); |
487 | } |
488 | node_ptr const w_left (NodeTraits::get_left(w)); |
489 | node_ptr const w_right(NodeTraits::get_right(w)); |
490 | if((!w_right || NodeTraits::get_color(w_right) == NodeTraits::black()) && |
491 | (!w_left || NodeTraits::get_color(w_left) == NodeTraits::black())){ |
492 | NodeTraits::set_color(w, NodeTraits::red()); |
493 | x = x_parent; |
494 | x_parent = NodeTraits::get_parent(x_parent); |
495 | } |
496 | else { |
497 | if(!w_left || NodeTraits::get_color(w_left) == NodeTraits::black()){ |
498 | NodeTraits::set_color(w_right, NodeTraits::black()); |
499 | NodeTraits::set_color(w, NodeTraits::red()); |
500 | bstree_algo::rotate_left(w, w_right, NodeTraits::get_parent(w), header); |
501 | w = NodeTraits::get_left(x_parent); |
502 | BOOST_INTRUSIVE_INVARIANT_ASSERT(w); |
503 | } |
504 | NodeTraits::set_color(w, NodeTraits::get_color(x_parent)); |
505 | NodeTraits::set_color(x_parent, NodeTraits::black()); |
506 | const node_ptr new_wleft(NodeTraits::get_left(w)); |
507 | if(new_wleft) |
508 | NodeTraits::set_color(new_wleft, NodeTraits::black()); |
509 | bstree_algo::rotate_right(x_parent, NodeTraits::get_left(x_parent), NodeTraits::get_parent(x_parent), header); |
510 | break; |
511 | } |
512 | } |
513 | } |
514 | if(x) |
515 | NodeTraits::set_color(x, NodeTraits::black()); |
516 | } |
517 | |
518 | static void rebalance_after_insertion(const node_ptr & , node_ptr p) |
519 | { |
520 | NodeTraits::set_color(p, NodeTraits::red()); |
521 | while(1){ |
522 | node_ptr p_parent(NodeTraits::get_parent(p)); |
523 | const node_ptr p_grandparent(NodeTraits::get_parent(p_parent)); |
524 | if(p_parent == header || NodeTraits::get_color(p_parent) == NodeTraits::black() || p_grandparent == header){ |
525 | break; |
526 | } |
527 | |
528 | NodeTraits::set_color(p_grandparent, NodeTraits::red()); |
529 | node_ptr const p_grandparent_left (NodeTraits::get_left (p_grandparent)); |
530 | bool const p_parent_is_left_child = p_parent == p_grandparent_left; |
531 | node_ptr const x(p_parent_is_left_child ? NodeTraits::get_right(p_grandparent) : p_grandparent_left); |
532 | |
533 | if(x && NodeTraits::get_color(x) == NodeTraits::red()){ |
534 | NodeTraits::set_color(x, NodeTraits::black()); |
535 | NodeTraits::set_color(p_parent, NodeTraits::black()); |
536 | p = p_grandparent; |
537 | } |
538 | else{ //Final step |
539 | const bool p_is_left_child(NodeTraits::get_left(p_parent) == p); |
540 | if(p_parent_is_left_child){ //p_parent is left child |
541 | if(!p_is_left_child){ //p is right child |
542 | bstree_algo::rotate_left_no_parent_fix(p_parent, p); |
543 | //No need to link p and p_grandparent: |
544 | // [NodeTraits::set_parent(p, p_grandparent) + NodeTraits::set_left(p_grandparent, p)] |
545 | //as p_grandparent is not the header, another rotation is coming and p_parent |
546 | //will be the left child of p_grandparent |
547 | p_parent = p; |
548 | } |
549 | bstree_algo::rotate_right(p_grandparent, p_parent, NodeTraits::get_parent(p_grandparent), header); |
550 | } |
551 | else{ //p_parent is right child |
552 | if(p_is_left_child){ //p is left child |
553 | bstree_algo::rotate_right_no_parent_fix(p_parent, p); |
554 | //No need to link p and p_grandparent: |
555 | // [NodeTraits::set_parent(p, p_grandparent) + NodeTraits::set_right(p_grandparent, p)] |
556 | //as p_grandparent is not the header, another rotation is coming and p_parent |
557 | //will be the right child of p_grandparent |
558 | p_parent = p; |
559 | } |
560 | bstree_algo::rotate_left(p_grandparent, p_parent, NodeTraits::get_parent(p_grandparent), header); |
561 | } |
562 | NodeTraits::set_color(p_parent, NodeTraits::black()); |
563 | break; |
564 | } |
565 | } |
566 | NodeTraits::set_color(NodeTraits::get_parent(header), NodeTraits::black()); |
567 | } |
568 | /// @endcond |
569 | }; |
570 | |
571 | /// @cond |
572 | |
573 | template<class NodeTraits> |
574 | struct get_algo<RbTreeAlgorithms, NodeTraits> |
575 | { |
576 | typedef rbtree_algorithms<NodeTraits> type; |
577 | }; |
578 | |
579 | template <class ValueTraits, class NodePtrCompare, class ExtraChecker> |
580 | struct get_node_checker<RbTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker> |
581 | { |
582 | typedef detail::rbtree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type; |
583 | }; |
584 | |
585 | /// @endcond |
586 | |
587 | } //namespace intrusive |
588 | } //namespace boost |
589 | |
590 | #include <boost/intrusive/detail/config_end.hpp> |
591 | |
592 | #endif //BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP |
593 | |