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