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 47509212 : color_ref(uintptr_type* r_):r(r_){}
146 : color_ref(const color_ref& x):r(x.r){}
147 :
148 13579288 : operator ordered_index_color()const
149 : {
150 13579288 : return ordered_index_color(*r&uintptr_type(1));
151 : }
152 :
153 10175318 : color_ref& operator=(ordered_index_color c)
154 : {
155 10175318 : *r&=~uintptr_type(1);
156 10175318 : *r|=uintptr_type(c);
157 10175318 : return *this;
158 : }
159 :
160 396850 : color_ref& operator=(const color_ref& x)
161 : {
162 396850 : return operator=(x.operator ordered_index_color());
163 : }
164 :
165 : private:
166 : uintptr_type* r;
167 : };
168 :
169 : struct parent_ref
170 : {
171 108288242 : parent_ref(uintptr_type* r_):r(r_){}
172 3253382 : parent_ref(const parent_ref& x):r(x.r){}
173 :
174 54912504 : operator pointer()const
175 : {
176 54912504 : return (pointer)(void*)(*r&~uintptr_type(1));
177 : }
178 :
179 6774692 : parent_ref& operator=(pointer p)
180 : {
181 6774692 : *r=((uintptr_type)(void*)p)|(*r&uintptr_type(1));
182 6774692 : return *this;
183 : }
184 :
185 2303101 : parent_ref& operator=(const parent_ref& x)
186 : {
187 2303101 : return operator=(x.operator pointer());
188 : }
189 :
190 24626931 : pointer operator->()const
191 : {
192 24626931 : return operator pointer();
193 : }
194 :
195 : private:
196 : uintptr_type* r;
197 : };
198 :
199 23754606 : 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 54144121 : parent_ref parent(){return parent_ref(&parentcolor_);}
206 : pointer parent()const
207 : {
208 : return (pointer)(void*)(parentcolor_&~uintptr_type(1));
209 : }
210 :
211 56775316 : pointer& left(){return left_;}
212 : pointer left()const{return left_;}
213 43207651 : 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 3828085 : static void increment(pointer& x)
267 : {
268 3828085 : if(x->right()!=pointer(0)){
269 1843676 : x=x->right();
270 3570552 : while(x->left()!=pointer(0))x=x->left();
271 1843676 : }
272 : else{
273 1984409 : pointer y=x->parent();
274 4348080 : while(x==y->right()){
275 2363671 : x=y;
276 2363671 : y=y->parent();
277 : }
278 1984409 : if(x->right()!=y)x=y;
279 : }
280 3828085 : }
281 :
282 4752950 : static void decrement(pointer& x)
283 : {
284 4752950 : if(x->color()==red&&x->parent()->parent()==x){
285 0 : x=x->right();
286 0 : }
287 4752950 : else if(x->left()!=pointer(0)){
288 2297224 : pointer y=x->left();
289 4181893 : while(y->right()!=pointer(0))y=y->right();
290 2297224 : x=y;
291 2297224 : }else{
292 2455726 : pointer y=x->parent();
293 4512841 : while(x==y->left()){
294 2057115 : x=y;
295 2057115 : y=y->parent();
296 : }
297 2455726 : x=y;
298 : }
299 4752950 : }
300 :
301 : /* algorithmic stuff */
302 :
303 459771 : static void rotate_left(pointer x,parent_ref root)
304 : {
305 459771 : pointer y=x->right();
306 459771 : x->right()=y->left();
307 459771 : if(y->left()!=pointer(0))y->left()->parent()=x;
308 459771 : y->parent()=x->parent();
309 :
310 459771 : if(x==root) root=y;
311 448471 : else if(x==x->parent()->left())x->parent()->left()=y;
312 156205 : else x->parent()->right()=y;
313 459771 : y->left()=x;
314 459771 : x->parent()=y;
315 459771 : AugmentPolicy::rotate_left(x,y);
316 459771 : }
317 :
318 23286 : static pointer minimum(pointer x)
319 : {
320 23286 : while(x->left()!=pointer(0))x=x->left();
321 23286 : return x;
322 : }
323 :
324 317690 : static pointer maximum(pointer x)
325 : {
326 317690 : while(x->right()!=pointer(0))x=x->right();
327 317690 : return x;
328 : }
329 :
330 1166920 : static void rotate_right(pointer x,parent_ref root)
331 : {
332 1166920 : pointer y=x->left();
333 1166920 : x->left()=y->right();
334 1166920 : if(y->right()!=pointer(0))y->right()->parent()=x;
335 1166920 : y->parent()=x->parent();
336 :
337 1166920 : if(x==root) root=y;
338 1147645 : else if(x==x->parent()->right())x->parent()->right()=y;
339 490653 : else x->parent()->left()=y;
340 1166920 : y->right()=x;
341 1166920 : x->parent()=y;
342 1166920 : AugmentPolicy::rotate_right(x,y);
343 1166920 : }
344 :
345 1261820 : static void rebalance(pointer x,parent_ref root)
346 : {
347 1261820 : x->color()=red;
348 2852568 : while(x!=root&&x->parent()->color()==red){
349 1590748 : if(x->parent()==x->parent()->parent()->left()){
350 1215659 : pointer y=x->parent()->parent()->right();
351 1215659 : if(y!=pointer(0)&&y->color()==red){
352 662521 : x->parent()->color()=black;
353 662521 : y->color()=black;
354 662521 : x->parent()->parent()->color()=red;
355 662521 : x=x->parent()->parent();
356 662521 : }
357 : else{
358 553138 : if(x==x->parent()->right()){
359 37460 : x=x->parent();
360 37460 : rotate_left(x,root);
361 37460 : }
362 553138 : x->parent()->color()=black;
363 553138 : x->parent()->parent()->color()=red;
364 553138 : rotate_right(x->parent()->parent(),root);
365 : }
366 1215659 : }
367 : else{
368 375089 : pointer y=x->parent()->parent()->left();
369 375089 : if(y!=pointer(0)&&y->color()==red){
370 95209 : x->parent()->color()=black;
371 95209 : y->color()=black;
372 95209 : x->parent()->parent()->color()=red;
373 95209 : x=x->parent()->parent();
374 95209 : }
375 : else{
376 279880 : if(x==x->parent()->left()){
377 210085 : x=x->parent();
378 210085 : rotate_right(x,root);
379 210085 : }
380 279880 : x->parent()->color()=black;
381 279880 : x->parent()->parent()->color()=red;
382 279880 : rotate_left(x->parent()->parent(),root);
383 : }
384 : }
385 : }
386 1261820 : root->color()=black;
387 1261820 : }
388 :
389 1261820 : static void link(
390 : pointer x,ordered_index_side side,pointer position,pointer header)
391 : {
392 1261820 : if(side==to_left){
393 896905 : position->left()=x; /* also makes leftmost=x when parent==header */
394 896905 : if(position==header){
395 15788 : header->parent()=x;
396 15788 : header->right()=x;
397 15788 : }
398 881117 : else if(position==header->left()){
399 362989 : header->left()=x; /* maintain leftmost pointing to min node */
400 362989 : }
401 896905 : }
402 : else{
403 364915 : position->right()=x;
404 364915 : if(position==header->right()){
405 69276 : header->right()=x; /* maintain rightmost pointing to max node */
406 69276 : }
407 : }
408 1261820 : x->parent()=position;
409 1261820 : x->left()=pointer(0);
410 1261820 : x->right()=pointer(0);
411 1261820 : AugmentPolicy::add(x,pointer(header->parent()));
412 1261820 : ordered_index_node_impl::rebalance(x,header->parent());
413 1261820 : }
414 :
415 1248950 : static pointer rebalance_for_extract(
416 : pointer z,parent_ref root,pointer& leftmost,pointer& rightmost)
417 : {
418 1248950 : pointer y=z;
419 1248950 : pointer x=pointer(0);
420 1248950 : pointer x_parent=pointer(0);
421 1248950 : if(y->left()==pointer(0)){ /* z has at most one non-null child. y==z. */
422 683657 : x=y->right(); /* x might be null */
423 683657 : }
424 : else{
425 565293 : if(y->right()==pointer(0)){ /* z has exactly one non-null child. y==z. */
426 341199 : x=y->left(); /* x is not null */
427 341199 : }
428 : else{ /* z has two non-null children. Set y to */
429 224094 : y=y->right(); /* z's successor. x might be null. */
430 609105 : while(y->left()!=pointer(0))y=y->left();
431 224094 : x=y->right();
432 : }
433 : }
434 1248950 : AugmentPolicy::remove(y,pointer(root));
435 1248950 : if(y!=z){
436 224094 : AugmentPolicy::copy(z,y);
437 224094 : z->left()->parent()=y; /* relink y in place of z. y is z's successor */
438 224094 : y->left()=z->left();
439 224094 : if(y!=z->right()){
440 157723 : x_parent=y->parent();
441 157723 : if(x!=pointer(0))x->parent()=y->parent();
442 157723 : y->parent()->left()=x; /* y must be a child of left */
443 157723 : y->right()=z->right();
444 157723 : z->right()->parent()=y;
445 157723 : }
446 : else{
447 66371 : x_parent=y;
448 : }
449 :
450 224094 : if(root==z) root=y;
451 218440 : else if(z->parent()->left()==z)z->parent()->left()=y;
452 98267 : else z->parent()->right()=y;
453 224094 : y->parent()=z->parent();
454 224094 : ordered_index_color c=y->color();
455 224094 : y->color()=z->color();
456 224094 : z->color()=c;
457 224094 : y=z; /* y now points to node to be actually deleted */
458 224094 : }
459 : else{ /* y==z */
460 1024856 : x_parent=y->parent();
461 1024856 : if(x!=pointer(0))x->parent()=y->parent();
462 1024856 : if(root==z){
463 19461 : root=x;
464 19461 : }
465 : else{
466 1005395 : if(z->parent()->left()==z)z->parent()->left()=x;
467 781925 : else z->parent()->right()=x;
468 : }
469 1024856 : if(leftmost==z){
470 80320 : if(z->right()==pointer(0)){ /* z->left() must be null also */
471 57034 : leftmost=z->parent();
472 57034 : }
473 : else{
474 23286 : leftmost=minimum(x); /* makes leftmost==header if z==root */
475 : }
476 80320 : }
477 1024856 : if(rightmost==z){
478 694659 : if(z->left()==pointer(0)){ /* z->right() must be null also */
479 376969 : rightmost=z->parent();
480 376969 : }
481 : else{ /* x==z->left() */
482 317690 : rightmost=maximum(x); /* makes rightmost==header if z==root */
483 : }
484 694659 : }
485 : }
486 1248950 : if(y->color()!=red){
487 3491354 : while(x!=root&&(x==pointer(0)|| x->color()==black)){
488 922966 : if(x==x_parent->left()){
489 148108 : pointer w=x_parent->right();
490 148108 : if(w->color()==red){
491 31938 : w->color()=black;
492 31938 : x_parent->color()=red;
493 31938 : rotate_left(x_parent,root);
494 31938 : w=x_parent->right();
495 31938 : }
496 274434 : if((w->left()==pointer(0)||w->left()->color()==black) &&
497 126326 : (w->right()==pointer(0)||w->right()->color()==black)){
498 100685 : w->color()=red;
499 100685 : x=x_parent;
500 100685 : x_parent=x_parent->parent();
501 100685 : }
502 : else{
503 90772 : if(w->right()==pointer(0 )
504 47423 : || w->right()->color()==black){
505 12120 : if(w->left()!=pointer(0)) w->left()->color()=black;
506 12120 : w->color()=red;
507 12120 : rotate_right(w,root);
508 12120 : w=x_parent->right();
509 12120 : }
510 47423 : w->color()=x_parent->color();
511 47423 : x_parent->color()=black;
512 47423 : if(w->right()!=pointer(0))w->right()->color()=black;
513 47423 : rotate_left(x_parent,root);
514 47423 : break;
515 : }
516 100685 : }
517 : else{ /* same as above,with right <-> left */
518 774858 : pointer w=x_parent->left();
519 774858 : if(w->color()==red){
520 266244 : w->color()=black;
521 266244 : x_parent->color()=red;
522 266244 : rotate_right(x_parent,root);
523 266244 : w=x_parent->left();
524 266244 : }
525 1461460 : if((w->right()==pointer(0)||w->right()->color()==black) &&
526 686602 : (w->left()==pointer(0)||w->left()->color()==black)){
527 649525 : w->color()=red;
528 649525 : x=x_parent;
529 649525 : x_parent=x_parent->parent();
530 649525 : }
531 : else{
532 125333 : if(w->left()==pointer(0)||w->left()->color()==black){
533 63070 : if(w->right()!=pointer(0))w->right()->color()=black;
534 63070 : w->color()=red;
535 63070 : rotate_left(w,root);
536 63070 : w=x_parent->left();
537 63070 : }
538 125333 : w->color()=x_parent->color();
539 125333 : x_parent->color()=black;
540 125333 : if(w->left()!=pointer(0))w->left()->color()=black;
541 125333 : rotate_right(x_parent,root);
542 125333 : break;
543 : }
544 : }
545 : }
546 1008966 : if(x!=pointer(0))x->color()=black;
547 1008966 : }
548 1248950 : 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 335190 : impl_color_ref color(){return trampoline::color();}
615 : ordered_index_color color()const{return trampoline::color();}
616 3731875 : impl_parent_ref parent(){return trampoline::parent();}
617 : impl_pointer parent()const{return trampoline::parent();}
618 19748907 : impl_pointer& left(){return trampoline::left();}
619 : impl_pointer left()const{return trampoline::left();}
620 8759348 : impl_pointer& right(){return trampoline::right();}
621 : impl_pointer right()const{return trampoline::right();}
622 :
623 14285825 : impl_pointer impl()
624 : {
625 14285825 : return static_cast<impl_pointer>(
626 14285825 : 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 36068745 : static ordered_index_node* from_impl(impl_pointer x)
636 : {
637 36068745 : return
638 36068745 : static_cast<ordered_index_node*>(
639 : static_cast<trampoline*>(
640 36068745 : 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 3828085 : static void increment(ordered_index_node*& x)
654 : {
655 3828085 : impl_pointer xi=x->impl();
656 3828085 : trampoline::increment(xi);
657 3828085 : x=from_impl(xi);
658 3828085 : }
659 :
660 4752950 : static void decrement(ordered_index_node*& x)
661 : {
662 4752950 : impl_pointer xi=x->impl();
663 4752950 : trampoline::decrement(xi);
664 4752950 : x=from_impl(xi);
665 4752950 : }
666 : };
667 :
668 : } /* namespace multi_index::detail */
669 :
670 : } /* namespace multi_index */
671 :
672 : } /* namespace boost */
673 :
674 : #endif
|
