1 /* Copyright 2003-2015 Joaquin M Lopez Munoz.
2 * Distributed under the Boost Software License, Version 1.0.
3 * (See accompanying file LICENSE_1_0.txt or copy at
4 * http://www.boost.org/LICENSE_1_0.txt)
6 * See http://www.boost.org/libs/multi_index for library home page.
8 * The internal implementation of red-black trees is based on that of SGI STL
11 * Copyright (c) 1996,1997
12 * Silicon Graphics Computer Systems, Inc.
14 * Permission to use, copy, modify, distribute and sell this software
15 * and its documentation for any purpose is hereby granted without fee,
16 * provided that the above copyright notice appear in all copies and
17 * that both that copyright notice and this permission notice appear
18 * in supporting documentation. Silicon Graphics makes no
19 * representations about the suitability of this software for any
20 * purpose. It is provided "as is" without express or implied warranty.
24 * Hewlett-Packard Company
26 * Permission to use, copy, modify, distribute and sell this software
27 * and its documentation for any purpose is hereby granted without fee,
28 * provided that the above copyright notice appear in all copies and
29 * that both that copyright notice and this permission notice appear
30 * in supporting documentation. Hewlett-Packard Company makes no
31 * representations about the suitability of this software for any
32 * purpose. It is provided "as is" without express or implied warranty.
36 #ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_NODE_HPP
37 #define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_NODE_HPP
43 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
45 #include <boost/detail/allocator_utilities.hpp>
46 #include <boost/multi_index/detail/raw_ptr.hpp>
48 #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
49 #include <boost/mpl/and.hpp>
50 #include <boost/mpl/if.hpp>
51 #include <boost/multi_index/detail/uintptr_type.hpp>
52 #include <boost/type_traits/alignment_of.hpp>
53 #include <boost/type_traits/is_same.hpp>
58 namespace multi_index{
62 /* definition of red-black nodes for ordered_index */
64 enum ordered_index_color{red=false,black=true};
65 enum ordered_index_side{to_left=false,to_right=true};
67 template<typename AugmentPolicy,typename Allocator>
68 struct ordered_index_node_impl; /* fwd decl. */
70 template<typename AugmentPolicy,typename Allocator>
71 struct ordered_index_node_std_base
74 boost::detail::allocator::rebind_to<
76 ordered_index_node_impl<AugmentPolicy,Allocator>
77 >::type::pointer pointer;
79 boost::detail::allocator::rebind_to<
81 ordered_index_node_impl<AugmentPolicy,Allocator>
82 >::type::const_pointer const_pointer;
83 typedef ordered_index_color& color_ref;
84 typedef pointer& parent_ref;
86 ordered_index_color& color(){return color_;}
87 ordered_index_color color()const{return color_;}
88 pointer& parent(){return parent_;}
89 pointer parent()const{return parent_;}
90 pointer& left(){return left_;}
91 pointer left()const{return left_;}
92 pointer& right(){return right_;}
93 pointer right()const{return right_;}
96 ordered_index_color color_;
102 #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
103 /* If ordered_index_node_impl has even alignment, we can use the least
104 * significant bit of one of the ordered_index_node_impl pointers to
105 * store color information. This typically reduces the size of
106 * ordered_index_node_impl by 25%.
109 #if defined(BOOST_MSVC)
110 /* This code casts pointers to an integer type that has been computed
111 * to be large enough to hold the pointer, however the metaprogramming
112 * logic is not always spotted by the VC++ code analyser that issues a
113 * long list of warnings.
116 #pragma warning(push)
117 #pragma warning(disable:4312 4311)
120 template<typename AugmentPolicy,typename Allocator>
121 struct ordered_index_node_compressed_base
123 typedef ordered_index_node_impl<
124 AugmentPolicy,Allocator>* pointer;
125 typedef const ordered_index_node_impl<
126 AugmentPolicy,Allocator>* const_pointer;
130 color_ref(uintptr_type* r_):r(r_){}
132 operator ordered_index_color()const
134 return ordered_index_color(*r&uintptr_type(1));
137 color_ref& operator=(ordered_index_color c)
139 *r&=~uintptr_type(1);
144 color_ref& operator=(const color_ref& x)
146 return operator=(x.operator ordered_index_color());
155 parent_ref(uintptr_type* r_):r(r_){}
157 operator pointer()const
159 return (pointer)(void*)(*r&~uintptr_type(1));
162 parent_ref& operator=(pointer p)
164 *r=((uintptr_type)(void*)p)|(*r&uintptr_type(1));
168 parent_ref& operator=(const parent_ref& x)
170 return operator=(x.operator pointer());
173 pointer operator->()const
175 return operator pointer();
182 color_ref color(){return color_ref(&parentcolor_);}
183 ordered_index_color color()const
185 return ordered_index_color(parentcolor_&uintptr_type(1));
188 parent_ref parent(){return parent_ref(&parentcolor_);}
189 pointer parent()const
191 return (pointer)(void*)(parentcolor_&~uintptr_type(1));
194 pointer& left(){return left_;}
195 pointer left()const{return left_;}
196 pointer& right(){return right_;}
197 pointer right()const{return right_;}
200 uintptr_type parentcolor_;
204 #if defined(BOOST_MSVC)
209 template<typename AugmentPolicy,typename Allocator>
210 struct ordered_index_node_impl_base:
212 #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
213 AugmentPolicy::template augmented_node<
215 !(has_uintptr_type::value)||
217 ordered_index_node_compressed_base<AugmentPolicy,Allocator>
220 typename boost::detail::allocator::rebind_to<
222 ordered_index_node_impl<AugmentPolicy,Allocator>
224 ordered_index_node_impl<AugmentPolicy,Allocator>*>::value),
225 ordered_index_node_std_base<AugmentPolicy,Allocator>,
226 ordered_index_node_compressed_base<AugmentPolicy,Allocator>
230 AugmentPolicy::template augmented_node<
231 ordered_index_node_std_base<AugmentPolicy,Allocator>
237 template<typename AugmentPolicy,typename Allocator>
238 struct ordered_index_node_impl:
239 ordered_index_node_impl_base<AugmentPolicy,Allocator>
242 typedef ordered_index_node_impl_base<AugmentPolicy,Allocator> super;
245 typedef typename super::color_ref color_ref;
246 typedef typename super::parent_ref parent_ref;
247 typedef typename super::pointer pointer;
248 typedef typename super::const_pointer const_pointer;
250 /* interoperability with bidir_node_iterator */
252 static void increment(pointer& x)
254 if(x->right()!=pointer(0)){
256 while(x->left()!=pointer(0))x=x->left();
259 pointer y=x->parent();
260 while(x==y->right()){
264 if(x->right()!=y)x=y;
268 static void decrement(pointer& x)
270 if(x->color()==red&&x->parent()->parent()==x){
273 else if(x->left()!=pointer(0)){
275 while(y->right()!=pointer(0))y=y->right();
278 pointer y=x->parent();
287 /* algorithmic stuff */
289 static void rotate_left(pointer x,parent_ref root)
291 pointer y=x->right();
292 x->right()=y->left();
293 if(y->left()!=pointer(0))y->left()->parent()=x;
294 y->parent()=x->parent();
297 else if(x==x->parent()->left())x->parent()->left()=y;
298 else x->parent()->right()=y;
301 AugmentPolicy::rotate_left(x,y);
304 static pointer minimum(pointer x)
306 while(x->left()!=pointer(0))x=x->left();
310 static pointer maximum(pointer x)
312 while(x->right()!=pointer(0))x=x->right();
316 static void rotate_right(pointer x,parent_ref root)
319 x->left()=y->right();
320 if(y->right()!=pointer(0))y->right()->parent()=x;
321 y->parent()=x->parent();
324 else if(x==x->parent()->right())x->parent()->right()=y;
325 else x->parent()->left()=y;
328 AugmentPolicy::rotate_right(x,y);
331 static void rebalance(pointer x,parent_ref root)
334 while(x!=root&&x->parent()->color()==red){
335 if(x->parent()==x->parent()->parent()->left()){
336 pointer y=x->parent()->parent()->right();
337 if(y!=pointer(0)&&y->color()==red){
338 x->parent()->color()=black;
340 x->parent()->parent()->color()=red;
341 x=x->parent()->parent();
344 if(x==x->parent()->right()){
348 x->parent()->color()=black;
349 x->parent()->parent()->color()=red;
350 rotate_right(x->parent()->parent(),root);
354 pointer y=x->parent()->parent()->left();
355 if(y!=pointer(0)&&y->color()==red){
356 x->parent()->color()=black;
358 x->parent()->parent()->color()=red;
359 x=x->parent()->parent();
362 if(x==x->parent()->left()){
364 rotate_right(x,root);
366 x->parent()->color()=black;
367 x->parent()->parent()->color()=red;
368 rotate_left(x->parent()->parent(),root);
376 pointer x,ordered_index_side side,pointer position,pointer header)
379 position->left()=x; /* also makes leftmost=x when parent==header */
380 if(position==header){
384 else if(position==header->left()){
385 header->left()=x; /* maintain leftmost pointing to min node */
390 if(position==header->right()){
391 header->right()=x; /* maintain rightmost pointing to max node */
394 x->parent()=position;
395 x->left()=pointer(0);
396 x->right()=pointer(0);
397 AugmentPolicy::add(x,pointer(header->parent()));
398 ordered_index_node_impl::rebalance(x,header->parent());
401 static pointer rebalance_for_erase(
402 pointer z,parent_ref root,pointer& leftmost,pointer& rightmost)
405 pointer x=pointer(0);
406 pointer x_parent=pointer(0);
407 if(y->left()==pointer(0)){ /* z has at most one non-null child. y==z. */
408 x=y->right(); /* x might be null */
411 if(y->right()==pointer(0)){ /* z has exactly one non-null child. y==z. */
412 x=y->left(); /* x is not null */
414 else{ /* z has two non-null children. Set y to */
415 y=y->right(); /* z's successor. x might be null. */
416 while(y->left()!=pointer(0))y=y->left();
420 AugmentPolicy::remove(y,pointer(root));
422 AugmentPolicy::copy(z,y);
423 z->left()->parent()=y; /* relink y in place of z. y is z's successor */
426 x_parent=y->parent();
427 if(x!=pointer(0))x->parent()=y->parent();
428 y->parent()->left()=x; /* y must be a child of left */
429 y->right()=z->right();
430 z->right()->parent()=y;
437 else if(z->parent()->left()==z)z->parent()->left()=y;
438 else z->parent()->right()=y;
439 y->parent()=z->parent();
440 ordered_index_color c=y->color();
441 y->color()=z->color();
443 y=z; /* y now points to node to be actually deleted */
446 x_parent=y->parent();
447 if(x!=pointer(0))x->parent()=y->parent();
452 if(z->parent()->left()==z)z->parent()->left()=x;
453 else z->parent()->right()=x;
456 if(z->right()==pointer(0)){ /* z->left() must be null also */
457 leftmost=z->parent();
460 leftmost=minimum(x); /* makes leftmost==header if z==root */
464 if(z->left()==pointer(0)){ /* z->right() must be null also */
465 rightmost=z->parent();
467 else{ /* x==z->left() */
468 rightmost=maximum(x); /* makes rightmost==header if z==root */
473 while(x!=root&&(x==pointer(0)|| x->color()==black)){
474 if(x==x_parent->left()){
475 pointer w=x_parent->right();
478 x_parent->color()=red;
479 rotate_left(x_parent,root);
482 if((w->left()==pointer(0)||w->left()->color()==black) &&
483 (w->right()==pointer(0)||w->right()->color()==black)){
486 x_parent=x_parent->parent();
489 if(w->right()==pointer(0 )
490 || w->right()->color()==black){
491 if(w->left()!=pointer(0)) w->left()->color()=black;
493 rotate_right(w,root);
496 w->color()=x_parent->color();
497 x_parent->color()=black;
498 if(w->right()!=pointer(0))w->right()->color()=black;
499 rotate_left(x_parent,root);
503 else{ /* same as above,with right <-> left */
504 pointer w=x_parent->left();
507 x_parent->color()=red;
508 rotate_right(x_parent,root);
511 if((w->right()==pointer(0)||w->right()->color()==black) &&
512 (w->left()==pointer(0)||w->left()->color()==black)){
515 x_parent=x_parent->parent();
518 if(w->left()==pointer(0)||w->left()->color()==black){
519 if(w->right()!=pointer(0))w->right()->color()=black;
524 w->color()=x_parent->color();
525 x_parent->color()=black;
526 if(w->left()!=pointer(0))w->left()->color()=black;
527 rotate_right(x_parent,root);
532 if(x!=pointer(0))x->color()=black;
537 static void restore(pointer x,pointer position,pointer header)
539 if(position->left()==pointer(0)||position->left()==header){
540 link(x,to_left,position,header);
544 link(x,to_right,position,header);
548 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
549 /* invariant stuff */
551 static std::size_t black_count(pointer node,pointer root)
553 if(node==pointer(0))return 0;
556 if(node->color()==black)++sum;
565 template<typename AugmentPolicy,typename Super>
566 struct ordered_index_node_trampoline:
567 ordered_index_node_impl<
569 typename boost::detail::allocator::rebind_to<
570 typename Super::allocator_type,
575 typedef ordered_index_node_impl<
577 typename boost::detail::allocator::rebind_to<
578 typename Super::allocator_type,
584 template<typename AugmentPolicy,typename Super>
585 struct ordered_index_node:
586 Super,ordered_index_node_trampoline<AugmentPolicy,Super>
589 typedef ordered_index_node_trampoline<AugmentPolicy,Super> trampoline;
592 typedef typename trampoline::impl_type impl_type;
593 typedef typename trampoline::color_ref impl_color_ref;
594 typedef typename trampoline::parent_ref impl_parent_ref;
595 typedef typename trampoline::pointer impl_pointer;
596 typedef typename trampoline::const_pointer const_impl_pointer;
598 impl_color_ref color(){return trampoline::color();}
599 ordered_index_color color()const{return trampoline::color();}
600 impl_parent_ref parent(){return trampoline::parent();}
601 impl_pointer parent()const{return trampoline::parent();}
602 impl_pointer& left(){return trampoline::left();}
603 impl_pointer left()const{return trampoline::left();}
604 impl_pointer& right(){return trampoline::right();}
605 impl_pointer right()const{return trampoline::right();}
609 return static_cast<impl_pointer>(
610 static_cast<impl_type*>(static_cast<trampoline*>(this)));
613 const_impl_pointer impl()const
615 return static_cast<const_impl_pointer>(
616 static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
619 static ordered_index_node* from_impl(impl_pointer x)
622 static_cast<ordered_index_node*>(
623 static_cast<trampoline*>(
624 raw_ptr<impl_type*>(x)));
627 static const ordered_index_node* from_impl(const_impl_pointer x)
630 static_cast<const ordered_index_node*>(
631 static_cast<const trampoline*>(
632 raw_ptr<const impl_type*>(x)));
635 /* interoperability with bidir_node_iterator */
637 static void increment(ordered_index_node*& x)
639 impl_pointer xi=x->impl();
640 trampoline::increment(xi);
644 static void decrement(ordered_index_node*& x)
646 impl_pointer xi=x->impl();
647 trampoline::decrement(xi);
652 } /* namespace multi_index::detail */
654 } /* namespace multi_index */
656 } /* namespace boost */