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
40namespace boost {
41namespace intrusive {
42
43#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
44
45template<class NodeTraits, class F>
46struct 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
65namespace detail {
66
67template<class ValueTraits, class NodePtrCompare, class ExtraChecker>
68struct 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 extra_checker)
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>
165template<class NodeTraits>
166class 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 header1(bstree_algo::get_header(node1)), header2(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 & header1, const node_ptr & node2, const node_ptr & header2)
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 & header, 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 init_header(const node_ptr & header)
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 & header, 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 & source_header, const node_ptr & target_header, 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 & header, 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 & header, 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 & header, 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 & header, 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 & header, 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 is_header(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 & header, 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 & header, 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
573template<class NodeTraits>
574struct get_algo<RbTreeAlgorithms, NodeTraits>
575{
576 typedef rbtree_algorithms<NodeTraits> type;
577};
578
579template <class ValueTraits, class NodePtrCompare, class ExtraChecker>
580struct 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

source code of boost/boost/intrusive/rbtree_algorithms.hpp