]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
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_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 | ||
95 | private: | |
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 | ||
120 | template<typename AugmentPolicy,typename Allocator> | |
121 | struct 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 | ||
199 | private: | |
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 | ||
209 | template<typename AugmentPolicy,typename Allocator> | |
210 | struct 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 | ||
237 | template<typename AugmentPolicy,typename Allocator> | |
238 | struct ordered_index_node_impl: | |
239 | ordered_index_node_impl_base<AugmentPolicy,Allocator> | |
240 | { | |
241 | private: | |
242 | typedef ordered_index_node_impl_base<AugmentPolicy,Allocator> super; | |
243 | ||
244 | public: | |
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 | ||
565 | template<typename AugmentPolicy,typename Super> | |
566 | struct 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 | ||
584 | template<typename AugmentPolicy,typename Super> | |
585 | struct ordered_index_node: | |
586 | Super,ordered_index_node_trampoline<AugmentPolicy,Super> | |
587 | { | |
588 | private: | |
589 | typedef ordered_index_node_trampoline<AugmentPolicy,Super> trampoline; | |
590 | ||
591 | public: | |
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 |