Line data Source code
1 : /* Copyright 2003-2020 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 43154184 : color_ref(uintptr_type* r_):r(r_){}
146 : color_ref(const color_ref& x):r(x.r){}
147 :
148 12509181 : operator ordered_index_color()const
149 : {
150 12509181 : return ordered_index_color(*r&uintptr_type(1));
151 : }
152 :
153 9067911 : color_ref& operator=(ordered_index_color c)
154 : {
155 9067911 : *r&=~uintptr_type(1);
156 9067911 : *r|=uintptr_type(c);
157 9067911 : return *this;
158 : }
159 :
160 342670 : color_ref& operator=(const color_ref& x)
161 : {
162 342670 : return operator=(x.operator ordered_index_color());
163 : }
164 :
165 : private:
166 : uintptr_type* r;
167 : };
168 :
169 : struct parent_ref
170 : {
171 97906028 : parent_ref(uintptr_type* r_):r(r_){}
172 2979850 : parent_ref(const parent_ref& x):r(x.r){}
173 :
174 49720077 : operator pointer()const
175 : {
176 49720077 : return (pointer)(void*)(*r&~uintptr_type(1));
177 : }
178 :
179 6006326 : parent_ref& operator=(pointer p)
180 : {
181 6006326 : *r=((uintptr_type)(void*)p)|(*r&uintptr_type(1));
182 6006326 : return *this;
183 : }
184 :
185 2106944 : parent_ref& operator=(const parent_ref& x)
186 : {
187 2106944 : return operator=(x.operator pointer());
188 : }
189 :
190 22408241 : pointer operator->()const
191 : {
192 22408241 : return operator pointer();
193 : }
194 :
195 : private:
196 : uintptr_type* r;
197 : };
198 :
199 21577092 : 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 48953014 : parent_ref parent(){return parent_ref(&parentcolor_);}
206 : pointer parent()const
207 : {
208 : return (pointer)(void*)(parentcolor_&~uintptr_type(1));
209 : }
210 :
211 52979331 : pointer& left(){return left_;}
212 : pointer left()const{return left_;}
213 39553976 : 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 3564384 : static void increment(pointer& x)
267 : {
268 3564384 : if(x->right()!=pointer(0)){
269 1763605 : x=x->right();
270 3439946 : while(x->left()!=pointer(0))x=x->left();
271 1763605 : }
272 : else{
273 1800779 : pointer y=x->parent();
274 3754811 : while(x==y->right()){
275 1954032 : x=y;
276 1954032 : y=y->parent();
277 : }
278 1800779 : if(x->right()!=y)x=y;
279 : }
280 3564384 : }
281 :
282 4549499 : static void decrement(pointer& x)
283 : {
284 4549499 : if(x->color()==red&&x->parent()->parent()==x){
285 0 : x=x->right();
286 0 : }
287 4549499 : else if(x->left()!=pointer(0)){
288 2229961 : pointer y=x->left();
289 4081863 : while(y->right()!=pointer(0))y=y->right();
290 2229961 : x=y;
291 2229961 : }else{
292 2319538 : pointer y=x->parent();
293 4285444 : while(x==y->left()){
294 1965906 : x=y;
295 1965906 : y=y->parent();
296 : }
297 2319538 : x=y;
298 : }
299 4549499 : }
300 :
301 : /* algorithmic stuff */
302 :
303 389142 : static void rotate_left(pointer x,parent_ref root)
304 : {
305 389142 : pointer y=x->right();
306 389142 : x->right()=y->left();
307 389142 : if(y->left()!=pointer(0))y->left()->parent()=x;
308 389142 : y->parent()=x->parent();
309 :
310 389142 : if(x==root) root=y;
311 382057 : else if(x==x->parent()->left())x->parent()->left()=y;
312 120722 : else x->parent()->right()=y;
313 389142 : y->left()=x;
314 389142 : x->parent()=y;
315 389142 : AugmentPolicy::rotate_left(x,y);
316 389142 : }
317 :
318 9113 : static pointer minimum(pointer x)
319 : {
320 9113 : while(x->left()!=pointer(0))x=x->left();
321 9113 : return x;
322 : }
323 :
324 308154 : static pointer maximum(pointer x)
325 : {
326 308154 : while(x->right()!=pointer(0))x=x->right();
327 308154 : return x;
328 : }
329 :
330 1100783 : static void rotate_right(pointer x,parent_ref root)
331 : {
332 1100783 : pointer y=x->left();
333 1100783 : x->left()=y->right();
334 1100783 : if(y->right()!=pointer(0))y->right()->parent()=x;
335 1100783 : y->parent()=x->parent();
336 :
337 1100783 : if(x==root) root=y;
338 1089754 : else if(x==x->parent()->right())x->parent()->right()=y;
339 463516 : else x->parent()->left()=y;
340 1100783 : y->right()=x;
341 1100783 : x->parent()=y;
342 1100783 : AugmentPolicy::rotate_right(x,y);
343 1100783 : }
344 :
345 1113941 : static void rebalance(pointer x,parent_ref root)
346 : {
347 1113941 : x->color()=red;
348 2564783 : while(x!=root&&x->parent()->color()==red){
349 1450842 : if(x->parent()==x->parent()->parent()->left()){
350 1153736 : pointer y=x->parent()->parent()->right();
351 1153736 : if(y!=pointer(0)&&y->color()==red){
352 633258 : x->parent()->color()=black;
353 633258 : y->color()=black;
354 633258 : x->parent()->parent()->color()=red;
355 633258 : x=x->parent()->parent();
356 633258 : }
357 : else{
358 520478 : if(x==x->parent()->right()){
359 31192 : x=x->parent();
360 31192 : rotate_left(x,root);
361 31192 : }
362 520478 : x->parent()->color()=black;
363 520478 : x->parent()->parent()->color()=red;
364 520478 : rotate_right(x->parent()->parent(),root);
365 : }
366 1153736 : }
367 : else{
368 297106 : pointer y=x->parent()->parent()->left();
369 297106 : if(y!=pointer(0)&&y->color()==red){
370 57335 : x->parent()->color()=black;
371 57335 : y->color()=black;
372 57335 : x->parent()->parent()->color()=red;
373 57335 : x=x->parent()->parent();
374 57335 : }
375 : else{
376 239771 : if(x==x->parent()->left()){
377 202307 : x=x->parent();
378 202307 : rotate_right(x,root);
379 202307 : }
380 239771 : x->parent()->color()=black;
381 239771 : x->parent()->parent()->color()=red;
382 239771 : rotate_left(x->parent()->parent(),root);
383 : }
384 : }
385 : }
386 1113941 : root->color()=black;
387 1113941 : }
388 :
389 1113941 : static void link(
390 : pointer x,ordered_index_side side,pointer position,pointer header)
391 : {
392 1113941 : if(side==to_left){
393 811182 : position->left()=x; /* also makes leftmost=x when parent==header */
394 811182 : if(position==header){
395 1388 : header->parent()=x;
396 1388 : header->right()=x;
397 1388 : }
398 809794 : else if(position==header->left()){
399 329353 : header->left()=x; /* maintain leftmost pointing to min node */
400 329353 : }
401 811182 : }
402 : else{
403 302759 : position->right()=x;
404 302759 : if(position==header->right()){
405 32852 : header->right()=x; /* maintain rightmost pointing to max node */
406 32852 : }
407 : }
408 1113941 : x->parent()=position;
409 1113941 : x->left()=pointer(0);
410 1113941 : x->right()=pointer(0);
411 1113941 : AugmentPolicy::add(x,pointer(header->parent()));
412 1113941 : ordered_index_node_impl::rebalance(x,header->parent());
413 1113941 : }
414 :
415 1107326 : static pointer rebalance_for_extract(
416 : pointer z,parent_ref root,pointer& leftmost,pointer& rightmost)
417 : {
418 1107326 : pointer y=z;
419 1107326 : pointer x=pointer(0);
420 1107326 : pointer x_parent=pointer(0);
421 1107326 : if(y->left()==pointer(0)){ /* z has at most one non-null child. y==z. */
422 582596 : x=y->right(); /* x might be null */
423 582596 : }
424 : else{
425 524730 : if(y->right()==pointer(0)){ /* z has exactly one non-null child. y==z. */
426 327598 : x=y->left(); /* x is not null */
427 327598 : }
428 : else{ /* z has two non-null children. Set y to */
429 197132 : y=y->right(); /* z's successor. x might be null. */
430 563574 : while(y->left()!=pointer(0))y=y->left();
431 197132 : x=y->right();
432 : }
433 : }
434 1107326 : AugmentPolicy::remove(y,pointer(root));
435 1107326 : if(y!=z){
436 197132 : AugmentPolicy::copy(z,y);
437 197132 : z->left()->parent()=y; /* relink y in place of z. y is z's successor */
438 197132 : y->left()=z->left();
439 197132 : if(y!=z->right()){
440 146516 : x_parent=y->parent();
441 146516 : if(x!=pointer(0))x->parent()=y->parent();
442 146516 : y->parent()->left()=x; /* y must be a child of left */
443 146516 : y->right()=z->right();
444 146516 : z->right()->parent()=y;
445 146516 : }
446 : else{
447 50616 : x_parent=y;
448 : }
449 :
450 197132 : if(root==z) root=y;
451 194677 : else if(z->parent()->left()==z)z->parent()->left()=y;
452 85136 : else z->parent()->right()=y;
453 197132 : y->parent()=z->parent();
454 197132 : ordered_index_color c=y->color();
455 197132 : y->color()=z->color();
456 197132 : z->color()=c;
457 197132 : y=z; /* y now points to node to be actually deleted */
458 197132 : }
459 : else{ /* y==z */
460 910194 : x_parent=y->parent();
461 910194 : if(x!=pointer(0))x->parent()=y->parent();
462 910194 : if(root==z){
463 2394 : root=x;
464 2394 : }
465 : else{
466 907800 : if(z->parent()->left()==z)z->parent()->left()=x;
467 745071 : else z->parent()->right()=x;
468 : }
469 910194 : if(leftmost==z){
470 27216 : if(z->right()==pointer(0)){ /* z->left() must be null also */
471 18103 : leftmost=z->parent();
472 18103 : }
473 : else{
474 9113 : leftmost=minimum(x); /* makes leftmost==header if z==root */
475 : }
476 27216 : }
477 910194 : if(rightmost==z){
478 658214 : if(z->left()==pointer(0)){ /* z->right() must be null also */
479 350060 : rightmost=z->parent();
480 350060 : }
481 : else{ /* x==z->left() */
482 308154 : rightmost=maximum(x); /* makes rightmost==header if z==root */
483 : }
484 658214 : }
485 : }
486 1107326 : if(y->color()!=red){
487 3170130 : while(x!=root&&(x==pointer(0)|| x->color()==black)){
488 831262 : if(x==x_parent->left()){
489 101511 : pointer w=x_parent->right();
490 101511 : if(w->color()==red){
491 24624 : w->color()=black;
492 24624 : x_parent->color()=red;
493 24624 : rotate_left(x_parent,root);
494 24624 : w=x_parent->right();
495 24624 : }
496 189815 : if((w->left()==pointer(0)||w->left()->color()==black) &&
497 88304 : (w->right()==pointer(0)||w->right()->color()==black)){
498 67976 : w->color()=red;
499 67976 : x=x_parent;
500 67976 : x_parent=x_parent->parent();
501 67976 : }
502 : else{
503 66566 : if(w->right()==pointer(0 )
504 33535 : || w->right()->color()==black){
505 7214 : if(w->left()!=pointer(0)) w->left()->color()=black;
506 7214 : w->color()=red;
507 7214 : rotate_right(w,root);
508 7214 : w=x_parent->right();
509 7214 : }
510 33535 : w->color()=x_parent->color();
511 33535 : x_parent->color()=black;
512 33535 : if(w->right()!=pointer(0))w->right()->color()=black;
513 33535 : rotate_left(x_parent,root);
514 33535 : break;
515 : }
516 67976 : }
517 : else{ /* same as above,with right <-> left */
518 729751 : pointer w=x_parent->left();
519 729751 : if(w->color()==red){
520 258781 : w->color()=black;
521 258781 : x_parent->color()=red;
522 258781 : rotate_right(x_parent,root);
523 258781 : w=x_parent->left();
524 258781 : }
525 1377261 : if((w->right()==pointer(0)||w->right()->color()==black) &&
526 647510 : (w->left()==pointer(0)||w->left()->color()==black)){
527 617748 : w->color()=red;
528 617748 : x=x_parent;
529 617748 : x_parent=x_parent->parent();
530 617748 : }
531 : else{
532 112003 : if(w->left()==pointer(0)||w->left()->color()==black){
533 60020 : if(w->right()!=pointer(0))w->right()->color()=black;
534 60020 : w->color()=red;
535 60020 : rotate_left(w,root);
536 60020 : w=x_parent->left();
537 60020 : }
538 112003 : w->color()=x_parent->color();
539 112003 : x_parent->color()=black;
540 112003 : if(w->left()!=pointer(0))w->left()->color()=black;
541 112003 : rotate_right(x_parent,root);
542 112003 : break;
543 : }
544 : }
545 : }
546 902668 : if(x!=pointer(0))x->color()=black;
547 902668 : }
548 1107326 : 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 191744 : impl_color_ref color(){return trampoline::color();}
615 : ordered_index_color color()const{return trampoline::color();}
616 3173061 : impl_parent_ref parent(){return trampoline::parent();}
617 : impl_pointer parent()const{return trampoline::parent();}
618 18619089 : impl_pointer& left(){return trampoline::left();}
619 : impl_pointer left()const{return trampoline::left();}
620 7873210 : impl_pointer& right(){return trampoline::right();}
621 : impl_pointer right()const{return trampoline::right();}
622 :
623 12946520 : impl_pointer impl()
624 : {
625 12946520 : return static_cast<impl_pointer>(
626 12946520 : 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 33882033 : static ordered_index_node* from_impl(impl_pointer x)
636 : {
637 33882033 : return
638 33882033 : static_cast<ordered_index_node*>(
639 : static_cast<trampoline*>(
640 33882033 : 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 3564384 : static void increment(ordered_index_node*& x)
654 : {
655 3564384 : impl_pointer xi=x->impl();
656 3564384 : trampoline::increment(xi);
657 3564384 : x=from_impl(xi);
658 3564384 : }
659 :
660 4549499 : static void decrement(ordered_index_node*& x)
661 : {
662 4549499 : impl_pointer xi=x->impl();
663 4549499 : trampoline::decrement(xi);
664 4549499 : x=from_impl(xi);
665 4549499 : }
666 : };
667 :
668 : } /* namespace multi_index::detail */
669 :
670 : } /* namespace multi_index */
671 :
672 : } /* namespace boost */
673 :
674 : #endif
|
