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)
5 *
6 * See http://www.boost.org/libs/multi_index for library home page.
7 *
8 * The internal implementation of red-black trees is based on that of SGI STL
9 * stl_tree.h file:
10 *
11 * Copyright (c) 1996,1997
12 * Silicon Graphics Computer Systems, Inc.
13 *
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.
21 *
22 *
23 * Copyright (c) 1994
24 * Hewlett-Packard Company
25 *
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.
33 *
34 */
35
36#ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_NODE_HPP
37#define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_NODE_HPP
38
39#if defined(_MSC_VER)
40#pragma once
41#endif
42
43#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
44#include <cstddef>
45#include <boost/detail/allocator_utilities.hpp>
46#include <boost/multi_index/detail/raw_ptr.hpp>
47
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>
54#endif
55
56namespace boost{
57
58namespace multi_index{
59
60namespace detail{
61
62/* definition of red-black nodes for ordered_index */
63
64enum ordered_index_color{red=false,black=true};
65enum ordered_index_side{to_left=false,to_right=true};
66
67template<typename AugmentPolicy,typename Allocator>
68struct ordered_index_node_impl; /* fwd decl. */
69
70template<typename AugmentPolicy,typename Allocator>
71struct ordered_index_node_std_base
72{
73 typedef typename
74 boost::detail::allocator::rebind_to<
75 Allocator,
76 ordered_index_node_impl<AugmentPolicy,Allocator>
77 >::type::pointer pointer;
78 typedef typename
79 boost::detail::allocator::rebind_to<
80 Allocator,
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;
85
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_;}
94
95private:
96 ordered_index_color color_;
97 pointer parent_;
98 pointer left_;
99 pointer right_;
100};
101
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%.
107 */
108
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.
114 */
115
116#pragma warning(push)
117#pragma warning(disable:4312 4311)
118#endif
119
120template<typename AugmentPolicy,typename Allocator>
121struct ordered_index_node_compressed_base
122{
123 typedef ordered_index_node_impl<
124 AugmentPolicy,Allocator>* pointer;
125 typedef const ordered_index_node_impl<
126 AugmentPolicy,Allocator>* const_pointer;
127
128 struct color_ref
129 {
130 color_ref(uintptr_type* r_):r(r_){}
131
132 operator ordered_index_color()const
133 {
134 return ordered_index_color(*r&uintptr_type(1));
135 }
136
137 color_ref& operator=(ordered_index_color c)
138 {
139 *r&=~uintptr_type(1);
140 *r|=uintptr_type(c);
141 return *this;
142 }
143
144 color_ref& operator=(const color_ref& x)
145 {
146 return operator=(x.operator ordered_index_color());
147 }
148
149 private:
150 uintptr_type* r;
151 };
152
153 struct parent_ref
154 {
155 parent_ref(uintptr_type* r_):r(r_){}
156
157 operator pointer()const
158 {
159 return (pointer)(void*)(*r&~uintptr_type(1));
160 }
161
162 parent_ref& operator=(pointer p)
163 {
164 *r=((uintptr_type)(void*)p)|(*r&uintptr_type(1));
165 return *this;
166 }
167
168 parent_ref& operator=(const parent_ref& x)
169 {
170 return operator=(x.operator pointer());
171 }
172
173 pointer operator->()const
174 {
175 return operator pointer();
176 }
177
178 private:
179 uintptr_type* r;
180 };
181
182 color_ref color(){return color_ref(&parentcolor_);}
183 ordered_index_color color()const
184 {
185 return ordered_index_color(parentcolor_&uintptr_type(1));
186 }
187
188 parent_ref parent(){return parent_ref(&parentcolor_);}
189 pointer parent()const
190 {
191 return (pointer)(void*)(parentcolor_&~uintptr_type(1));
192 }
193
194 pointer& left(){return left_;}
195 pointer left()const{return left_;}
196 pointer& right(){return right_;}
197 pointer right()const{return right_;}
198
199private:
200 uintptr_type parentcolor_;
201 pointer left_;
202 pointer right_;
203};
204#if defined(BOOST_MSVC)
205#pragma warning(pop)
206#endif
207#endif
208
209template<typename AugmentPolicy,typename Allocator>
210struct ordered_index_node_impl_base:
211
212#if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
213 AugmentPolicy::template augmented_node<
214 typename mpl::if_c<
215 !(has_uintptr_type::value)||
216 (alignment_of<
217 ordered_index_node_compressed_base<AugmentPolicy,Allocator>
218 >::value%2)||
219 !(is_same<
220 typename boost::detail::allocator::rebind_to<
221 Allocator,
222 ordered_index_node_impl<AugmentPolicy,Allocator>
223 >::type::pointer,
224 ordered_index_node_impl<AugmentPolicy,Allocator>*>::value),
225 ordered_index_node_std_base<AugmentPolicy,Allocator>,
226 ordered_index_node_compressed_base<AugmentPolicy,Allocator>
227 >::type
228 >::type
229#else
230 AugmentPolicy::template augmented_node<
231 ordered_index_node_std_base<AugmentPolicy,Allocator>
232 >::type
233#endif
234
235{};
236
237template<typename AugmentPolicy,typename Allocator>
238struct ordered_index_node_impl:
239 ordered_index_node_impl_base<AugmentPolicy,Allocator>
240{
241private:
242 typedef ordered_index_node_impl_base<AugmentPolicy,Allocator> super;
243
244public:
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;
249
250 /* interoperability with bidir_node_iterator */
251
252 static void increment(pointer& x)
253 {
254 if(x->right()!=pointer(0)){
255 x=x->right();
256 while(x->left()!=pointer(0))x=x->left();
257 }
258 else{
259 pointer y=x->parent();
260 while(x==y->right()){
261 x=y;
262 y=y->parent();
263 }
264 if(x->right()!=y)x=y;
265 }
266 }
267
268 static void decrement(pointer& x)
269 {
270 if(x->color()==red&&x->parent()->parent()==x){
271 x=x->right();
272 }
273 else if(x->left()!=pointer(0)){
274 pointer y=x->left();
275 while(y->right()!=pointer(0))y=y->right();
276 x=y;
277 }else{
278 pointer y=x->parent();
279 while(x==y->left()){
280 x=y;
281 y=y->parent();
282 }
283 x=y;
284 }
285 }
286
287 /* algorithmic stuff */
288
289 static void rotate_left(pointer x,parent_ref root)
290 {
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();
295
296 if(x==root) root=y;
297 else if(x==x->parent()->left())x->parent()->left()=y;
298 else x->parent()->right()=y;
299 y->left()=x;
300 x->parent()=y;
301 AugmentPolicy::rotate_left(x,y);
302 }
303
304 static pointer minimum(pointer x)
305 {
306 while(x->left()!=pointer(0))x=x->left();
307 return x;
308 }
309
310 static pointer maximum(pointer x)
311 {
312 while(x->right()!=pointer(0))x=x->right();
313 return x;
314 }
315
316 static void rotate_right(pointer x,parent_ref root)
317 {
318 pointer y=x->left();
319 x->left()=y->right();
320 if(y->right()!=pointer(0))y->right()->parent()=x;
321 y->parent()=x->parent();
322
323 if(x==root) root=y;
324 else if(x==x->parent()->right())x->parent()->right()=y;
325 else x->parent()->left()=y;
326 y->right()=x;
327 x->parent()=y;
328 AugmentPolicy::rotate_right(x,y);
329 }
330
331 static void rebalance(pointer x,parent_ref root)
332 {
333 x->color()=red;
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;
339 y->color()=black;
340 x->parent()->parent()->color()=red;
341 x=x->parent()->parent();
342 }
343 else{
344 if(x==x->parent()->right()){
345 x=x->parent();
346 rotate_left(x,root);
347 }
348 x->parent()->color()=black;
349 x->parent()->parent()->color()=red;
350 rotate_right(x->parent()->parent(),root);
351 }
352 }
353 else{
354 pointer y=x->parent()->parent()->left();
355 if(y!=pointer(0)&&y->color()==red){
356 x->parent()->color()=black;
357 y->color()=black;
358 x->parent()->parent()->color()=red;
359 x=x->parent()->parent();
360 }
361 else{
362 if(x==x->parent()->left()){
363 x=x->parent();
364 rotate_right(x,root);
365 }
366 x->parent()->color()=black;
367 x->parent()->parent()->color()=red;
368 rotate_left(x->parent()->parent(),root);
369 }
370 }
371 }
372 root->color()=black;
373 }
374
375 static void link(
376 pointer x,ordered_index_side side,pointer position,pointer header)
377 {
378 if(side==to_left){
379 position->left()=x; /* also makes leftmost=x when parent==header */
380 if(position==header){
381 header->parent()=x;
382 header->right()=x;
383 }
384 else if(position==header->left()){
385 header->left()=x; /* maintain leftmost pointing to min node */
386 }
387 }
388 else{
389 position->right()=x;
390 if(position==header->right()){
391 header->right()=x; /* maintain rightmost pointing to max node */
392 }
393 }
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());
399 }
400
401 static pointer rebalance_for_erase(
402 pointer z,parent_ref root,pointer& leftmost,pointer& rightmost)
403 {
404 pointer y=z;
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 */
409 }
410 else{
411 if(y->right()==pointer(0)){ /* z has exactly one non-null child. y==z. */
412 x=y->left(); /* x is not null */
413 }
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();
417 x=y->right();
418 }
419 }
420 AugmentPolicy::remove(y,pointer(root));
421 if(y!=z){
422 AugmentPolicy::copy(z,y);
423 z->left()->parent()=y; /* relink y in place of z. y is z's successor */
424 y->left()=z->left();
425 if(y!=z->right()){
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;
431 }
432 else{
433 x_parent=y;
434 }
435
436 if(root==z) root=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();
442 z->color()=c;
443 y=z; /* y now points to node to be actually deleted */
444 }
445 else{ /* y==z */
446 x_parent=y->parent();
447 if(x!=pointer(0))x->parent()=y->parent();
448 if(root==z){
449 root=x;
450 }
451 else{
452 if(z->parent()->left()==z)z->parent()->left()=x;
453 else z->parent()->right()=x;
454 }
455 if(leftmost==z){
456 if(z->right()==pointer(0)){ /* z->left() must be null also */
457 leftmost=z->parent();
458 }
459 else{
460 leftmost=minimum(x); /* makes leftmost==header if z==root */
461 }
462 }
463 if(rightmost==z){
464 if(z->left()==pointer(0)){ /* z->right() must be null also */
465 rightmost=z->parent();
466 }
467 else{ /* x==z->left() */
468 rightmost=maximum(x); /* makes rightmost==header if z==root */
469 }
470 }
471 }
472 if(y->color()!=red){
473 while(x!=root&&(x==pointer(0)|| x->color()==black)){
474 if(x==x_parent->left()){
475 pointer w=x_parent->right();
476 if(w->color()==red){
477 w->color()=black;
478 x_parent->color()=red;
479 rotate_left(x_parent,root);
480 w=x_parent->right();
481 }
482 if((w->left()==pointer(0)||w->left()->color()==black) &&
483 (w->right()==pointer(0)||w->right()->color()==black)){
484 w->color()=red;
485 x=x_parent;
486 x_parent=x_parent->parent();
487 }
488 else{
489 if(w->right()==pointer(0 )
490 || w->right()->color()==black){
491 if(w->left()!=pointer(0)) w->left()->color()=black;
492 w->color()=red;
493 rotate_right(w,root);
494 w=x_parent->right();
495 }
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);
500 break;
501 }
502 }
503 else{ /* same as above,with right <-> left */
504 pointer w=x_parent->left();
505 if(w->color()==red){
506 w->color()=black;
507 x_parent->color()=red;
508 rotate_right(x_parent,root);
509 w=x_parent->left();
510 }
511 if((w->right()==pointer(0)||w->right()->color()==black) &&
512 (w->left()==pointer(0)||w->left()->color()==black)){
513 w->color()=red;
514 x=x_parent;
515 x_parent=x_parent->parent();
516 }
517 else{
518 if(w->left()==pointer(0)||w->left()->color()==black){
519 if(w->right()!=pointer(0))w->right()->color()=black;
520 w->color()=red;
521 rotate_left(w,root);
522 w=x_parent->left();
523 }
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);
528 break;
529 }
530 }
531 }
532 if(x!=pointer(0))x->color()=black;
533 }
534 return y;
535 }
536
537 static void restore(pointer x,pointer position,pointer header)
538 {
539 if(position->left()==pointer(0)||position->left()==header){
540 link(x,to_left,position,header);
541 }
542 else{
543 decrement(position);
544 link(x,to_right,position,header);
545 }
546 }
547
548#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
549 /* invariant stuff */
550
551 static std::size_t black_count(pointer node,pointer root)
552 {
553 if(node==pointer(0))return 0;
554 std::size_t sum=0;
555 for(;;){
556 if(node->color()==black)++sum;
557 if(node==root)break;
558 node=node->parent();
559 }
560 return sum;
561 }
562#endif
563};
564
565template<typename AugmentPolicy,typename Super>
566struct ordered_index_node_trampoline:
567 ordered_index_node_impl<
568 AugmentPolicy,
569 typename boost::detail::allocator::rebind_to<
570 typename Super::allocator_type,
571 char
572 >::type
573 >
574{
575 typedef ordered_index_node_impl<
576 AugmentPolicy,
577 typename boost::detail::allocator::rebind_to<
578 typename Super::allocator_type,
579 char
580 >::type
581 > impl_type;
582};
583
584template<typename AugmentPolicy,typename Super>
585struct ordered_index_node:
586 Super,ordered_index_node_trampoline<AugmentPolicy,Super>
587{
588private:
589 typedef ordered_index_node_trampoline<AugmentPolicy,Super> trampoline;
590
591public:
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;
597
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();}
606
607 impl_pointer impl()
608 {
609 return static_cast<impl_pointer>(
610 static_cast<impl_type*>(static_cast<trampoline*>(this)));
611 }
612
613 const_impl_pointer impl()const
614 {
615 return static_cast<const_impl_pointer>(
616 static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
617 }
618
619 static ordered_index_node* from_impl(impl_pointer x)
620 {
621 return
622 static_cast<ordered_index_node*>(
623 static_cast<trampoline*>(
624 raw_ptr<impl_type*>(x)));
625 }
626
627 static const ordered_index_node* from_impl(const_impl_pointer x)
628 {
629 return
630 static_cast<const ordered_index_node*>(
631 static_cast<const trampoline*>(
632 raw_ptr<const impl_type*>(x)));
633 }
634
635 /* interoperability with bidir_node_iterator */
636
637 static void increment(ordered_index_node*& x)
638 {
639 impl_pointer xi=x->impl();
640 trampoline::increment(xi);
641 x=from_impl(xi);
642 }
643
644 static void decrement(ordered_index_node*& x)
645 {
646 impl_pointer xi=x->impl();
647 trampoline::decrement(xi);
648 x=from_impl(xi);
649 }
650};
651
652} /* namespace multi_index::detail */
653
654} /* namespace multi_index */
655
656} /* namespace boost */
657
658#endif
659