1 /* Copyright 2003-2007 Joaquín M López Muñoz.
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
39 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
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/prevent_eti.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 Allocator>
68 struct ordered_index_node_impl; /* fwd decl. */
70 template<typename Allocator>
71 struct ordered_index_node_std_base
73 typedef typename prevent_eti<
75 typename boost::detail::allocator::rebind_to<
77 ordered_index_node_impl<Allocator>
79 >::type::pointer pointer;
80 typedef typename prevent_eti<
82 typename boost::detail::allocator::rebind_to<
84 ordered_index_node_impl<Allocator>
86 >::type::const_pointer const_pointer;
87 typedef ordered_index_color& color_ref;
88 typedef pointer& parent_ref;
90 ordered_index_color& color(){return color_;}
91 ordered_index_color color()const{return color_;}
92 pointer& parent(){return parent_;}
93 pointer parent()const{return parent_;}
94 pointer& left(){return left_;}
95 pointer left()const{return left_;}
96 pointer& right(){return right_;}
97 pointer right()const{return right_;}
100 ordered_index_color color_;
106 #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
107 /* If ordered_index_node_impl has even alignment, we can use the least
108 * significant bit of one of the ordered_index_node_impl pointers to
109 * store color information. This typically reduces the size of
110 * ordered_index_node_impl by 25%.
113 #if defined(BOOST_MSVC)
114 /* This code casts pointers to an integer type that has been computed
115 * to be large enough to hold the pointer, however the metaprogramming
116 * logic is not always spotted by the VC++ code analyser that issues a
117 * long list of warnings.
120 #pragma warning(push)
121 #pragma warning(disable:4312 4311)
124 template<typename Allocator>
125 struct ordered_index_node_compressed_base
127 typedef ordered_index_node_impl<Allocator>* pointer;
128 typedef const ordered_index_node_impl<Allocator>* const_pointer;
132 color_ref(uintptr_type* r_):r(r_){}
134 operator ordered_index_color()const
136 return ordered_index_color(*r&uintptr_type(1));
139 color_ref& operator=(ordered_index_color c)
141 *r&=~uintptr_type(1);
146 color_ref& operator=(const color_ref& x)
148 return operator=(x.operator ordered_index_color());
157 parent_ref(uintptr_type* r_):r(r_){}
159 operator pointer()const
161 return (pointer)(void*)(*r&~uintptr_type(1));
164 parent_ref& operator=(pointer p)
166 *r=((uintptr_type)(void*)p)|(*r&uintptr_type(1));
170 parent_ref& operator=(const parent_ref& x)
172 return operator=(x.operator pointer());
175 pointer operator->()const
177 return operator pointer();
184 color_ref color(){return color_ref(&parentcolor_);}
185 ordered_index_color color()const
187 return ordered_index_color(parentcolor_&std::size_t(1ul));
190 parent_ref parent(){return parent_ref(&parentcolor_);}
191 pointer parent()const
193 return (pointer)(void*)(parentcolor_&~uintptr_type(1));
196 pointer& left(){return left_;}
197 pointer left()const{return left_;}
198 pointer& right(){return right_;}
199 pointer right()const{return right_;}
202 uintptr_type parentcolor_;
206 #if defined(BOOST_MSVC)
211 template<typename Allocator>
212 struct ordered_index_node_impl_base:
214 #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
216 !(has_uintptr_type::value)||
217 (alignment_of<ordered_index_node_compressed_base<Allocator> >::value%2)||
219 typename prevent_eti<
221 typename boost::detail::allocator::rebind_to<
223 ordered_index_node_impl<Allocator>
226 ordered_index_node_impl<Allocator>*>::value),
227 ordered_index_node_std_base<Allocator>,
228 ordered_index_node_compressed_base<Allocator>
231 ordered_index_node_std_base<Allocator>
236 template<typename Allocator>
237 struct ordered_index_node_impl:ordered_index_node_impl_base<Allocator>
240 typedef ordered_index_node_impl_base<Allocator> super;
243 typedef typename super::color_ref color_ref;
244 typedef typename super::parent_ref parent_ref;
245 typedef typename super::pointer pointer;
246 typedef typename super::const_pointer const_pointer;
248 /* interoperability with bidir_node_iterator */
250 static void increment(pointer& x)
252 if(x->right()!=pointer(0)){
254 while(x->left()!=pointer(0))x=x->left();
257 pointer y=x->parent();
258 while(x==y->right()){
262 if(x->right()!=y)x=y;
266 static void decrement(pointer& x)
268 if(x->color()==red&&x->parent()->parent()==x){
271 else if(x->left()!=pointer(0)){
273 while(y->right()!=pointer(0))y=y->right();
276 pointer y=x->parent();
285 /* algorithmic stuff */
287 static void rotate_left(pointer x,parent_ref root)
289 pointer y=x->right();
290 x->right()=y->left();
291 if(y->left()!=pointer(0))y->left()->parent()=x;
292 y->parent()=x->parent();
295 else if(x==x->parent()->left())x->parent()->left()=y;
296 else x->parent()->right()=y;
301 static pointer minimum(pointer x)
303 while(x->left()!=pointer(0))x=x->left();
307 static pointer maximum(pointer x)
309 while(x->right()!=pointer(0))x=x->right();
313 static void rotate_right(pointer x,parent_ref root)
316 x->left()=y->right();
317 if(y->right()!=pointer(0))y->right()->parent()=x;
318 y->parent()=x->parent();
321 else if(x==x->parent()->right())x->parent()->right()=y;
322 else x->parent()->left()=y;
327 static void rebalance(pointer x,parent_ref root)
330 while(x!=root&&x->parent()->color()==red){
331 if(x->parent()==x->parent()->parent()->left()){
332 pointer y=x->parent()->parent()->right();
333 if(y!=pointer(0)&&y->color()==red){
334 x->parent()->color()=black;
336 x->parent()->parent()->color()=red;
337 x=x->parent()->parent();
340 if(x==x->parent()->right()){
344 x->parent()->color()=black;
345 x->parent()->parent()->color()=red;
346 rotate_right(x->parent()->parent(),root);
350 pointer y=x->parent()->parent()->left();
351 if(y!=pointer(0)&&y->color()==red){
352 x->parent()->color()=black;
354 x->parent()->parent()->color()=red;
355 x=x->parent()->parent();
358 if(x==x->parent()->left()){
360 rotate_right(x,root);
362 x->parent()->color()=black;
363 x->parent()->parent()->color()=red;
364 rotate_left(x->parent()->parent(),root);
372 pointer x,ordered_index_side side,pointer position,pointer header)
375 position->left()=x; /* also makes leftmost=x when parent==header */
376 if(position==header){
380 else if(position==header->left()){
381 header->left()=x; /* maintain leftmost pointing to min node */
386 if(position==header->right()){
387 header->right()=x; /* maintain rightmost pointing to max node */
390 x->parent()=position;
391 x->left()=pointer(0);
392 x->right()=pointer(0);
393 ordered_index_node_impl::rebalance(x,header->parent());
396 static pointer rebalance_for_erase(
397 pointer z,parent_ref root,pointer& leftmost,pointer& rightmost)
400 pointer x=pointer(0);
401 pointer x_parent=pointer(0);
402 if(y->left()==pointer(0)){ /* z has at most one non-null child. y==z. */
403 x=y->right(); /* x might be null */
406 if(y->right()==pointer(0)){ /* z has exactly one non-null child. y==z. */
407 x=y->left(); /* x is not null */
409 else{ /* z has two non-null children. Set y to */
410 y=y->right(); /* z's successor. x might be null. */
411 while(y->left()!=pointer(0))y=y->left();
416 z->left()->parent()=y; /* relink y in place of z. y is z's successor */
419 x_parent=y->parent();
420 if(x!=pointer(0))x->parent()=y->parent();
421 y->parent()->left()=x; /* y must be a child of left */
422 y->right()=z->right();
423 z->right()->parent()=y;
430 else if(z->parent()->left()==z)z->parent()->left()=y;
431 else z->parent()->right()=y;
432 y->parent()=z->parent();
433 ordered_index_color c=y->color();
434 y->color()=z->color();
436 y=z; /* y now points to node to be actually deleted */
439 x_parent=y->parent();
440 if(x!=pointer(0))x->parent()=y->parent();
445 if(z->parent()->left()==z)z->parent()->left()=x;
446 else z->parent()->right()=x;
449 if(z->right()==pointer(0)){ /* z->left() must be null also */
450 leftmost=z->parent();
453 leftmost=minimum(x); /* makes leftmost==header if z==root */
457 if(z->left()==pointer(0)){ /* z->right() must be null also */
458 rightmost=z->parent();
460 else{ /* x==z->left() */
461 rightmost=maximum(x); /* makes rightmost==header if z==root */
466 while(x!=root&&(x==pointer(0)|| x->color()==black)){
467 if(x==x_parent->left()){
468 pointer w=x_parent->right();
471 x_parent->color()=red;
472 rotate_left(x_parent,root);
475 if((w->left()==pointer(0)||w->left()->color()==black) &&
476 (w->right()==pointer(0)||w->right()->color()==black)){
479 x_parent=x_parent->parent();
482 if(w->right()==pointer(0 )
483 || w->right()->color()==black){
484 if(w->left()!=pointer(0)) w->left()->color()=black;
486 rotate_right(w,root);
489 w->color()=x_parent->color();
490 x_parent->color()=black;
491 if(w->right()!=pointer(0))w->right()->color()=black;
492 rotate_left(x_parent,root);
496 else{ /* same as above,with right <-> left */
497 pointer w=x_parent->left();
500 x_parent->color()=red;
501 rotate_right(x_parent,root);
504 if((w->right()==pointer(0)||w->right()->color()==black) &&
505 (w->left()==pointer(0)||w->left()->color()==black)){
508 x_parent=x_parent->parent();
511 if(w->left()==pointer(0)||w->left()->color()==black){
512 if(w->right()!=pointer(0))w->right()->color()=black;
517 w->color()=x_parent->color();
518 x_parent->color()=black;
519 if(w->left()!=pointer(0))w->left()->color()=black;
520 rotate_right(x_parent,root);
525 if(x!=pointer(0))x->color()=black;
530 static void restore(pointer x,pointer position,pointer header)
532 if(position->left()==pointer(0)||position->left()==header){
533 link(x,to_left,position,header);
537 link(x,to_right,position,header);
541 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
542 /* invariant stuff */
544 static std::size_t black_count(pointer node,pointer root)
546 if(node==pointer(0))return 0;
549 if(node->color()==black)++sum;
558 template<typename Super>
559 struct ordered_index_node_trampoline:
562 ordered_index_node_impl<
563 typename boost::detail::allocator::rebind_to<
564 typename Super::allocator_type,
570 typedef typename prevent_eti<
572 ordered_index_node_impl<
573 typename boost::detail::allocator::rebind_to<
574 typename Super::allocator_type,
581 template<typename Super>
582 struct ordered_index_node:Super,ordered_index_node_trampoline<Super>
585 typedef ordered_index_node_trampoline<Super> trampoline;
588 typedef typename trampoline::impl_type impl_type;
589 typedef typename trampoline::color_ref impl_color_ref;
590 typedef typename trampoline::parent_ref impl_parent_ref;
591 typedef typename trampoline::pointer impl_pointer;
592 typedef typename trampoline::const_pointer const_impl_pointer;
594 impl_color_ref color(){return trampoline::color();}
595 ordered_index_color color()const{return trampoline::color();}
596 impl_parent_ref parent(){return trampoline::parent();}
597 impl_pointer parent()const{return trampoline::parent();}
598 impl_pointer& left(){return trampoline::left();}
599 impl_pointer left()const{return trampoline::left();}
600 impl_pointer& right(){return trampoline::right();}
601 impl_pointer right()const{return trampoline::right();}
605 return static_cast<impl_pointer>(
606 static_cast<impl_type*>(static_cast<trampoline*>(this)));
609 const_impl_pointer impl()const
611 return static_cast<const_impl_pointer>(
612 static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
615 static ordered_index_node* from_impl(impl_pointer x)
617 return static_cast<ordered_index_node*>(
618 static_cast<trampoline*>(&*x));
621 static const ordered_index_node* from_impl(const_impl_pointer x)
623 return static_cast<const ordered_index_node*>(
624 static_cast<const trampoline*>(&*x));
627 /* interoperability with bidir_node_iterator */
629 static void increment(ordered_index_node*& x)
631 impl_pointer xi=x->impl();
632 trampoline::increment(xi);
636 static void decrement(ordered_index_node*& x)
638 impl_pointer xi=x->impl();
639 trampoline::decrement(xi);
644 } /* namespace multi_index::detail */
646 } /* namespace multi_index */
648 } /* namespace boost */