Line data Source code
1 : /* Copyright 2003-2019 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/multi_index/detail/allocator_traits.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 :
56 : namespace boost{
57 :
58 : namespace multi_index{
59 :
60 : namespace detail{
61 :
62 : /* definition of red-black nodes for ordered_index */
63 :
64 : enum ordered_index_color{red=false,black=true};
65 : enum ordered_index_side{to_left=false,to_right=true};
66 :
67 : template<typename AugmentPolicy,typename Allocator>
68 : struct ordered_index_node_impl; /* fwd decl. */
69 :
70 : template<typename AugmentPolicy,typename Allocator>
71 : struct ordered_index_node_traits
72 : {
73 : typedef typename rebind_alloc_for<
74 : Allocator,
75 : ordered_index_node_impl<AugmentPolicy,Allocator>
76 : >::type allocator;
77 : typedef allocator_traits<allocator> alloc_traits;
78 : typedef typename alloc_traits::pointer pointer;
79 : typedef typename alloc_traits::const_pointer const_pointer;
80 : typedef typename alloc_traits::difference_type difference_type;
81 : typedef typename alloc_traits::size_type size_type;
82 : };
83 :
84 : template<typename AugmentPolicy,typename Allocator>
85 : struct ordered_index_node_std_base
86 : {
87 : typedef ordered_index_node_traits<
88 : AugmentPolicy,Allocator> node_traits;
89 : typedef typename node_traits::allocator node_allocator;
90 : typedef typename node_traits::pointer pointer;
91 : typedef typename node_traits::const_pointer const_pointer;
92 : typedef typename node_traits::difference_type difference_type;
93 : typedef typename node_traits::size_type size_type;
94 : typedef ordered_index_color& color_ref;
95 : typedef pointer& parent_ref;
96 :
97 : ordered_index_color& color(){return color_;}
98 : ordered_index_color color()const{return color_;}
99 : pointer& parent(){return parent_;}
100 : pointer parent()const{return parent_;}
101 : pointer& left(){return left_;}
102 : pointer left()const{return left_;}
103 : pointer& right(){return right_;}
104 : pointer right()const{return right_;}
105 :
106 : private:
107 : ordered_index_color color_;
108 : pointer parent_;
109 : pointer left_;
110 : pointer right_;
111 : };
112 :
113 : #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
114 : /* If ordered_index_node_impl has even alignment, we can use the least
115 : * significant bit of one of the ordered_index_node_impl pointers to
116 : * store color information. This typically reduces the size of
117 : * ordered_index_node_impl by 25%.
118 : */
119 :
120 : #if defined(BOOST_MSVC)
121 : /* This code casts pointers to an integer type that has been computed
122 : * to be large enough to hold the pointer, however the metaprogramming
123 : * logic is not always spotted by the VC++ code analyser that issues a
124 : * long list of warnings.
125 : */
126 :
127 : #pragma warning(push)
128 : #pragma warning(disable:4312 4311)
129 : #endif
130 :
131 : template<typename AugmentPolicy,typename Allocator>
132 : struct ordered_index_node_compressed_base
133 : {
134 : typedef ordered_index_node_traits<
135 : AugmentPolicy,Allocator> node_traits;
136 : typedef ordered_index_node_impl<
137 : AugmentPolicy,Allocator>* pointer;
138 : typedef const ordered_index_node_impl<
139 : AugmentPolicy,Allocator>* const_pointer;
140 : typedef typename node_traits::difference_type difference_type;
141 : typedef typename node_traits::size_type size_type;
142 :
143 : struct color_ref
144 : {
145 0 : color_ref(uintptr_type* r_):r(r_){}
146 : color_ref(const color_ref& x):r(x.r){}
147 :
148 0 : operator ordered_index_color()const
149 : {
150 0 : return ordered_index_color(*r&uintptr_type(1));
151 : }
152 :
153 0 : color_ref& operator=(ordered_index_color c)
154 : {
155 0 : *r&=~uintptr_type(1);
156 0 : *r|=uintptr_type(c);
157 : return *this;
158 : }
159 :
160 0 : color_ref& operator=(const color_ref& x)
161 : {
162 0 : return operator=(x.operator ordered_index_color());
163 : }
164 :
165 : private:
166 : uintptr_type* r;
167 : };
168 :
169 : struct parent_ref
170 : {
171 0 : parent_ref(uintptr_type* r_):r(r_){}
172 0 : parent_ref(const parent_ref& x):r(x.r){}
173 :
174 0 : operator pointer()const
175 : {
176 0 : return (pointer)(void*)(*r&~uintptr_type(1));
177 : }
178 :
179 0 : parent_ref& operator=(pointer p)
180 : {
181 0 : *r=((uintptr_type)(void*)p)|(*r&uintptr_type(1));
182 0 : return *this;
183 : }
184 :
185 0 : parent_ref& operator=(const parent_ref& x)
186 : {
187 0 : return operator=(x.operator pointer());
188 : }
189 :
190 0 : pointer operator->()const
191 : {
192 0 : return operator pointer();
193 : }
194 :
195 : private:
196 : uintptr_type* r;
197 : };
198 :
199 0 : color_ref color(){return color_ref(&parentcolor_);}
200 : ordered_index_color color()const
201 : {
202 : return ordered_index_color(parentcolor_&uintptr_type(1));
203 : }
204 :
205 0 : parent_ref parent(){return parent_ref(&parentcolor_);}
206 : pointer parent()const
207 : {
208 : return (pointer)(void*)(parentcolor_&~uintptr_type(1));
209 : }
210 :
211 0 : pointer& left(){return left_;}
212 : pointer left()const{return left_;}
213 0 : pointer& right(){return right_;}
214 : pointer right()const{return right_;}
215 :
216 : private:
217 : uintptr_type parentcolor_;
218 : pointer left_;
219 : pointer right_;
220 : };
221 : #if defined(BOOST_MSVC)
222 : #pragma warning(pop)
223 : #endif
224 : #endif
225 :
226 : template<typename AugmentPolicy,typename Allocator>
227 : struct ordered_index_node_impl_base:
228 :
229 : #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
230 : AugmentPolicy::template augmented_node<
231 : typename mpl::if_c<
232 : !(has_uintptr_type::value)||
233 : (alignment_of<
234 : ordered_index_node_compressed_base<AugmentPolicy,Allocator>
235 : >::value%2)||
236 : !(is_same<
237 : typename ordered_index_node_traits<AugmentPolicy,Allocator>::pointer,
238 : ordered_index_node_impl<AugmentPolicy,Allocator>*>::value),
239 : ordered_index_node_std_base<AugmentPolicy,Allocator>,
240 : ordered_index_node_compressed_base<AugmentPolicy,Allocator>
241 : >::type
242 : >::type
243 : #else
244 : AugmentPolicy::template augmented_node<
245 : ordered_index_node_std_base<AugmentPolicy,Allocator>
246 : >::type
247 : #endif
248 :
249 : {};
250 :
251 : template<typename AugmentPolicy,typename Allocator>
252 : struct ordered_index_node_impl:
253 : ordered_index_node_impl_base<AugmentPolicy,Allocator>
254 : {
255 : private:
256 : typedef ordered_index_node_impl_base<AugmentPolicy,Allocator> super;
257 :
258 : public:
259 : typedef typename super::color_ref color_ref;
260 : typedef typename super::parent_ref parent_ref;
261 : typedef typename super::pointer pointer;
262 : typedef typename super::const_pointer const_pointer;
263 :
264 : /* interoperability with bidir_node_iterator */
265 :
266 0 : static void increment(pointer& x)
267 : {
268 0 : if(x->right()!=pointer(0)){
269 0 : x=x->right();
270 0 : while(x->left()!=pointer(0))x=x->left();
271 : }
272 : else{
273 0 : pointer y=x->parent();
274 0 : while(x==y->right()){
275 0 : x=y;
276 0 : y=y->parent();
277 : }
278 0 : if(x->right()!=y)x=y;
279 : }
280 0 : }
281 :
282 0 : static void decrement(pointer& x)
283 : {
284 0 : if(x->color()==red&&x->parent()->parent()==x){
285 0 : x=x->right();
286 : }
287 0 : else if(x->left()!=pointer(0)){
288 0 : pointer y=x->left();
289 0 : while(y->right()!=pointer(0))y=y->right();
290 0 : x=y;
291 : }else{
292 0 : pointer y=x->parent();
293 0 : while(x==y->left()){
294 0 : x=y;
295 0 : y=y->parent();
296 : }
297 0 : x=y;
298 : }
299 0 : }
300 :
301 : /* algorithmic stuff */
302 :
303 0 : static void rotate_left(pointer x,parent_ref root)
304 : {
305 0 : pointer y=x->right();
306 0 : x->right()=y->left();
307 0 : if(y->left()!=pointer(0))y->left()->parent()=x;
308 0 : y->parent()=x->parent();
309 :
310 0 : if(x==root) root=y;
311 0 : else if(x==x->parent()->left())x->parent()->left()=y;
312 0 : else x->parent()->right()=y;
313 0 : y->left()=x;
314 0 : x->parent()=y;
315 0 : AugmentPolicy::rotate_left(x,y);
316 0 : }
317 :
318 : static pointer minimum(pointer x)
319 : {
320 0 : while(x->left()!=pointer(0))x=x->left();
321 : return x;
322 : }
323 :
324 : static pointer maximum(pointer x)
325 : {
326 0 : while(x->right()!=pointer(0))x=x->right();
327 : return x;
328 : }
329 :
330 0 : static void rotate_right(pointer x,parent_ref root)
331 : {
332 0 : pointer y=x->left();
333 0 : x->left()=y->right();
334 0 : if(y->right()!=pointer(0))y->right()->parent()=x;
335 0 : y->parent()=x->parent();
336 :
337 0 : if(x==root) root=y;
338 0 : else if(x==x->parent()->right())x->parent()->right()=y;
339 0 : else x->parent()->left()=y;
340 0 : y->right()=x;
341 0 : x->parent()=y;
342 0 : AugmentPolicy::rotate_right(x,y);
343 0 : }
344 :
345 0 : static void rebalance(pointer x,parent_ref root)
346 : {
347 0 : x->color()=red;
348 0 : while(x!=root&&x->parent()->color()==red){
349 0 : if(x->parent()==x->parent()->parent()->left()){
350 0 : pointer y=x->parent()->parent()->right();
351 0 : if(y!=pointer(0)&&y->color()==red){
352 0 : x->parent()->color()=black;
353 0 : y->color()=black;
354 0 : x->parent()->parent()->color()=red;
355 0 : x=x->parent()->parent();
356 : }
357 : else{
358 0 : if(x==x->parent()->right()){
359 0 : x=x->parent();
360 0 : rotate_left(x,root);
361 : }
362 0 : x->parent()->color()=black;
363 0 : x->parent()->parent()->color()=red;
364 0 : rotate_right(x->parent()->parent(),root);
365 : }
366 : }
367 : else{
368 0 : pointer y=x->parent()->parent()->left();
369 0 : if(y!=pointer(0)&&y->color()==red){
370 0 : x->parent()->color()=black;
371 0 : y->color()=black;
372 0 : x->parent()->parent()->color()=red;
373 0 : x=x->parent()->parent();
374 : }
375 : else{
376 0 : if(x==x->parent()->left()){
377 0 : x=x->parent();
378 0 : rotate_right(x,root);
379 : }
380 0 : x->parent()->color()=black;
381 0 : x->parent()->parent()->color()=red;
382 0 : rotate_left(x->parent()->parent(),root);
383 : }
384 : }
385 : }
386 0 : root->color()=black;
387 0 : }
388 :
389 0 : static void link(
390 : pointer x,ordered_index_side side,pointer position,pointer header)
391 : {
392 0 : if(side==to_left){
393 0 : position->left()=x; /* also makes leftmost=x when parent==header */
394 0 : if(position==header){
395 0 : header->parent()=x;
396 0 : header->right()=x;
397 : }
398 0 : else if(position==header->left()){
399 0 : header->left()=x; /* maintain leftmost pointing to min node */
400 : }
401 : }
402 : else{
403 0 : position->right()=x;
404 0 : if(position==header->right()){
405 0 : header->right()=x; /* maintain rightmost pointing to max node */
406 : }
407 : }
408 0 : x->parent()=position;
409 0 : x->left()=pointer(0);
410 0 : x->right()=pointer(0);
411 0 : AugmentPolicy::add(x,pointer(header->parent()));
412 0 : ordered_index_node_impl::rebalance(x,header->parent());
413 0 : }
414 :
415 0 : static pointer rebalance_for_erase(
416 : pointer z,parent_ref root,pointer& leftmost,pointer& rightmost)
417 : {
418 0 : pointer y=z;
419 0 : pointer x=pointer(0);
420 0 : pointer x_parent=pointer(0);
421 0 : if(y->left()==pointer(0)){ /* z has at most one non-null child. y==z. */
422 0 : x=y->right(); /* x might be null */
423 : }
424 : else{
425 0 : if(y->right()==pointer(0)){ /* z has exactly one non-null child. y==z. */
426 0 : x=y->left(); /* x is not null */
427 : }
428 : else{ /* z has two non-null children. Set y to */
429 0 : y=y->right(); /* z's successor. x might be null. */
430 0 : while(y->left()!=pointer(0))y=y->left();
431 0 : x=y->right();
432 : }
433 : }
434 0 : AugmentPolicy::remove(y,pointer(root));
435 0 : if(y!=z){
436 0 : AugmentPolicy::copy(z,y);
437 0 : z->left()->parent()=y; /* relink y in place of z. y is z's successor */
438 0 : y->left()=z->left();
439 0 : if(y!=z->right()){
440 0 : x_parent=y->parent();
441 0 : if(x!=pointer(0))x->parent()=y->parent();
442 0 : y->parent()->left()=x; /* y must be a child of left */
443 0 : y->right()=z->right();
444 0 : z->right()->parent()=y;
445 : }
446 : else{
447 : x_parent=y;
448 : }
449 :
450 0 : if(root==z) root=y;
451 0 : else if(z->parent()->left()==z)z->parent()->left()=y;
452 0 : else z->parent()->right()=y;
453 0 : y->parent()=z->parent();
454 0 : ordered_index_color c=y->color();
455 0 : y->color()=z->color();
456 0 : z->color()=c;
457 0 : y=z; /* y now points to node to be actually deleted */
458 : }
459 : else{ /* y==z */
460 0 : x_parent=y->parent();
461 0 : if(x!=pointer(0))x->parent()=y->parent();
462 0 : if(root==z){
463 0 : root=x;
464 : }
465 : else{
466 0 : if(z->parent()->left()==z)z->parent()->left()=x;
467 0 : else z->parent()->right()=x;
468 : }
469 0 : if(leftmost==z){
470 0 : if(z->right()==pointer(0)){ /* z->left() must be null also */
471 0 : leftmost=z->parent();
472 : }
473 : else{
474 0 : leftmost=minimum(x); /* makes leftmost==header if z==root */
475 : }
476 : }
477 0 : if(rightmost==z){
478 0 : if(z->left()==pointer(0)){ /* z->right() must be null also */
479 0 : rightmost=z->parent();
480 : }
481 : else{ /* x==z->left() */
482 0 : rightmost=maximum(x); /* makes rightmost==header if z==root */
483 : }
484 : }
485 : }
486 0 : if(y->color()!=red){
487 0 : while(x!=root&&(x==pointer(0)|| x->color()==black)){
488 0 : if(x==x_parent->left()){
489 0 : pointer w=x_parent->right();
490 0 : if(w->color()==red){
491 0 : w->color()=black;
492 0 : x_parent->color()=red;
493 0 : rotate_left(x_parent,root);
494 0 : w=x_parent->right();
495 : }
496 0 : if((w->left()==pointer(0)||w->left()->color()==black) &&
497 0 : (w->right()==pointer(0)||w->right()->color()==black)){
498 0 : w->color()=red;
499 0 : x=x_parent;
500 0 : x_parent=x_parent->parent();
501 : }
502 : else{
503 0 : if(w->right()==pointer(0 )
504 0 : || w->right()->color()==black){
505 0 : if(w->left()!=pointer(0)) w->left()->color()=black;
506 0 : w->color()=red;
507 0 : rotate_right(w,root);
508 0 : w=x_parent->right();
509 : }
510 0 : w->color()=x_parent->color();
511 0 : x_parent->color()=black;
512 0 : if(w->right()!=pointer(0))w->right()->color()=black;
513 0 : rotate_left(x_parent,root);
514 0 : break;
515 : }
516 : }
517 : else{ /* same as above,with right <-> left */
518 0 : pointer w=x_parent->left();
519 0 : if(w->color()==red){
520 0 : w->color()=black;
521 0 : x_parent->color()=red;
522 0 : rotate_right(x_parent,root);
523 0 : w=x_parent->left();
524 : }
525 0 : if((w->right()==pointer(0)||w->right()->color()==black) &&
526 0 : (w->left()==pointer(0)||w->left()->color()==black)){
527 0 : w->color()=red;
528 0 : x=x_parent;
529 0 : x_parent=x_parent->parent();
530 : }
531 : else{
532 0 : if(w->left()==pointer(0)||w->left()->color()==black){
533 0 : if(w->right()!=pointer(0))w->right()->color()=black;
534 0 : w->color()=red;
535 0 : rotate_left(w,root);
536 0 : w=x_parent->left();
537 : }
538 0 : w->color()=x_parent->color();
539 0 : x_parent->color()=black;
540 0 : if(w->left()!=pointer(0))w->left()->color()=black;
541 0 : rotate_right(x_parent,root);
542 0 : break;
543 : }
544 : }
545 : }
546 0 : if(x!=pointer(0))x->color()=black;
547 : }
548 0 : return y;
549 : }
550 :
551 : static void restore(pointer x,pointer position,pointer header)
552 : {
553 : if(position->left()==pointer(0)||position->left()==header){
554 : link(x,to_left,position,header);
555 : }
556 : else{
557 : decrement(position);
558 : link(x,to_right,position,header);
559 : }
560 : }
561 :
562 : #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
563 : /* invariant stuff */
564 :
565 : static std::size_t black_count(pointer node,pointer root)
566 : {
567 : if(node==pointer(0))return 0;
568 : std::size_t sum=0;
569 : for(;;){
570 : if(node->color()==black)++sum;
571 : if(node==root)break;
572 : node=node->parent();
573 : }
574 : return sum;
575 : }
576 : #endif
577 : };
578 :
579 : template<typename AugmentPolicy,typename Super>
580 : struct ordered_index_node_trampoline:
581 : ordered_index_node_impl<
582 : AugmentPolicy,
583 : typename rebind_alloc_for<
584 : typename Super::allocator_type,
585 : char
586 : >::type
587 : >
588 : {
589 : typedef ordered_index_node_impl<
590 : AugmentPolicy,
591 : typename rebind_alloc_for<
592 : typename Super::allocator_type,
593 : char
594 : >::type
595 : > impl_type;
596 : };
597 :
598 : template<typename AugmentPolicy,typename Super>
599 : struct ordered_index_node:
600 : Super,ordered_index_node_trampoline<AugmentPolicy,Super>
601 : {
602 : private:
603 : typedef ordered_index_node_trampoline<AugmentPolicy,Super> trampoline;
604 :
605 : public:
606 : typedef typename trampoline::impl_type impl_type;
607 : typedef typename trampoline::color_ref impl_color_ref;
608 : typedef typename trampoline::parent_ref impl_parent_ref;
609 : typedef typename trampoline::pointer impl_pointer;
610 : typedef typename trampoline::const_pointer const_impl_pointer;
611 : typedef typename trampoline::difference_type difference_type;
612 : typedef typename trampoline::size_type size_type;
613 :
614 0 : impl_color_ref color(){return trampoline::color();}
615 : ordered_index_color color()const{return trampoline::color();}
616 0 : impl_parent_ref parent(){return trampoline::parent();}
617 : impl_pointer parent()const{return trampoline::parent();}
618 0 : impl_pointer& left(){return trampoline::left();}
619 : impl_pointer left()const{return trampoline::left();}
620 0 : impl_pointer& right(){return trampoline::right();}
621 : impl_pointer right()const{return trampoline::right();}
622 :
623 0 : impl_pointer impl()
624 : {
625 : return static_cast<impl_pointer>(
626 0 : static_cast<impl_type*>(static_cast<trampoline*>(this)));
627 : }
628 :
629 : const_impl_pointer impl()const
630 : {
631 : return static_cast<const_impl_pointer>(
632 : static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
633 : }
634 :
635 0 : static ordered_index_node* from_impl(impl_pointer x)
636 : {
637 : return
638 0 : static_cast<ordered_index_node*>(
639 : static_cast<trampoline*>(
640 0 : raw_ptr<impl_type*>(x)));
641 : }
642 :
643 : static const ordered_index_node* from_impl(const_impl_pointer x)
644 : {
645 : return
646 : static_cast<const ordered_index_node*>(
647 : static_cast<const trampoline*>(
648 : raw_ptr<const impl_type*>(x)));
649 : }
650 :
651 : /* interoperability with bidir_node_iterator */
652 :
653 0 : static void increment(ordered_index_node*& x)
654 : {
655 0 : impl_pointer xi=x->impl();
656 0 : trampoline::increment(xi);
657 0 : x=from_impl(xi);
658 : }
659 :
660 0 : static void decrement(ordered_index_node*& x)
661 : {
662 0 : impl_pointer xi=x->impl();
663 0 : trampoline::decrement(xi);
664 0 : x=from_impl(xi);
665 0 : }
666 : };
667 :
668 : } /* namespace multi_index::detail */
669 :
670 : } /* namespace multi_index */
671 :
672 : } /* namespace boost */
673 :
674 : #endif
|
