]>
Commit | Line | Data |
---|---|---|
20effc67 | 1 | /* Copyright 2003-2020 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> | |
92f5a8d4 | 45 | #include <boost/multi_index/detail/allocator_traits.hpp> |
7c673cae FG |
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> | |
11fdf7f2 | 71 | struct ordered_index_node_traits |
7c673cae | 72 | { |
92f5a8d4 | 73 | typedef typename rebind_alloc_for< |
7c673cae FG |
74 | Allocator, |
75 | ordered_index_node_impl<AugmentPolicy,Allocator> | |
11fdf7f2 | 76 | >::type allocator; |
92f5a8d4 TL |
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; | |
11fdf7f2 TL |
82 | }; |
83 | ||
84 | template<typename AugmentPolicy,typename Allocator> | |
85 | struct ordered_index_node_std_base | |
86 | { | |
87 | typedef ordered_index_node_traits< | |
92f5a8d4 TL |
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; | |
7c673cae FG |
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 | { | |
92f5a8d4 TL |
134 | typedef ordered_index_node_traits< |
135 | AugmentPolicy,Allocator> node_traits; | |
7c673cae | 136 | typedef ordered_index_node_impl< |
92f5a8d4 | 137 | AugmentPolicy,Allocator>* pointer; |
7c673cae | 138 | typedef const ordered_index_node_impl< |
92f5a8d4 TL |
139 | AugmentPolicy,Allocator>* const_pointer; |
140 | typedef typename node_traits::difference_type difference_type; | |
141 | typedef typename node_traits::size_type size_type; | |
7c673cae FG |
142 | |
143 | struct color_ref | |
144 | { | |
145 | color_ref(uintptr_type* r_):r(r_){} | |
92f5a8d4 | 146 | color_ref(const color_ref& x):r(x.r){} |
7c673cae FG |
147 | |
148 | operator ordered_index_color()const | |
149 | { | |
150 | return ordered_index_color(*r&uintptr_type(1)); | |
151 | } | |
152 | ||
153 | color_ref& operator=(ordered_index_color c) | |
154 | { | |
155 | *r&=~uintptr_type(1); | |
156 | *r|=uintptr_type(c); | |
157 | return *this; | |
158 | } | |
159 | ||
160 | color_ref& operator=(const color_ref& x) | |
161 | { | |
162 | return operator=(x.operator ordered_index_color()); | |
163 | } | |
164 | ||
165 | private: | |
166 | uintptr_type* r; | |
167 | }; | |
168 | ||
169 | struct parent_ref | |
170 | { | |
171 | parent_ref(uintptr_type* r_):r(r_){} | |
92f5a8d4 | 172 | parent_ref(const parent_ref& x):r(x.r){} |
7c673cae FG |
173 | |
174 | operator pointer()const | |
175 | { | |
176 | return (pointer)(void*)(*r&~uintptr_type(1)); | |
177 | } | |
178 | ||
179 | parent_ref& operator=(pointer p) | |
180 | { | |
181 | *r=((uintptr_type)(void*)p)|(*r&uintptr_type(1)); | |
182 | return *this; | |
183 | } | |
184 | ||
185 | parent_ref& operator=(const parent_ref& x) | |
186 | { | |
187 | return operator=(x.operator pointer()); | |
188 | } | |
189 | ||
190 | pointer operator->()const | |
191 | { | |
192 | return operator pointer(); | |
193 | } | |
194 | ||
195 | private: | |
196 | uintptr_type* r; | |
197 | }; | |
198 | ||
199 | 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 | parent_ref parent(){return parent_ref(&parentcolor_);} | |
206 | pointer parent()const | |
207 | { | |
208 | return (pointer)(void*)(parentcolor_&~uintptr_type(1)); | |
209 | } | |
210 | ||
211 | pointer& left(){return left_;} | |
212 | pointer left()const{return left_;} | |
213 | 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< | |
11fdf7f2 | 237 | typename ordered_index_node_traits<AugmentPolicy,Allocator>::pointer, |
7c673cae FG |
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 | static void increment(pointer& x) | |
267 | { | |
268 | if(x->right()!=pointer(0)){ | |
269 | x=x->right(); | |
270 | while(x->left()!=pointer(0))x=x->left(); | |
271 | } | |
272 | else{ | |
273 | pointer y=x->parent(); | |
274 | while(x==y->right()){ | |
275 | x=y; | |
276 | y=y->parent(); | |
277 | } | |
278 | if(x->right()!=y)x=y; | |
279 | } | |
280 | } | |
281 | ||
282 | static void decrement(pointer& x) | |
283 | { | |
284 | if(x->color()==red&&x->parent()->parent()==x){ | |
285 | x=x->right(); | |
286 | } | |
287 | else if(x->left()!=pointer(0)){ | |
288 | pointer y=x->left(); | |
289 | while(y->right()!=pointer(0))y=y->right(); | |
290 | x=y; | |
291 | }else{ | |
292 | pointer y=x->parent(); | |
293 | while(x==y->left()){ | |
294 | x=y; | |
295 | y=y->parent(); | |
296 | } | |
297 | x=y; | |
298 | } | |
299 | } | |
300 | ||
301 | /* algorithmic stuff */ | |
302 | ||
303 | static void rotate_left(pointer x,parent_ref root) | |
304 | { | |
305 | pointer y=x->right(); | |
306 | x->right()=y->left(); | |
307 | if(y->left()!=pointer(0))y->left()->parent()=x; | |
308 | y->parent()=x->parent(); | |
309 | ||
310 | if(x==root) root=y; | |
311 | else if(x==x->parent()->left())x->parent()->left()=y; | |
312 | else x->parent()->right()=y; | |
313 | y->left()=x; | |
314 | x->parent()=y; | |
315 | AugmentPolicy::rotate_left(x,y); | |
316 | } | |
317 | ||
318 | static pointer minimum(pointer x) | |
319 | { | |
320 | while(x->left()!=pointer(0))x=x->left(); | |
321 | return x; | |
322 | } | |
323 | ||
324 | static pointer maximum(pointer x) | |
325 | { | |
326 | while(x->right()!=pointer(0))x=x->right(); | |
327 | return x; | |
328 | } | |
329 | ||
330 | static void rotate_right(pointer x,parent_ref root) | |
331 | { | |
332 | pointer y=x->left(); | |
333 | x->left()=y->right(); | |
334 | if(y->right()!=pointer(0))y->right()->parent()=x; | |
335 | y->parent()=x->parent(); | |
336 | ||
337 | if(x==root) root=y; | |
338 | else if(x==x->parent()->right())x->parent()->right()=y; | |
339 | else x->parent()->left()=y; | |
340 | y->right()=x; | |
341 | x->parent()=y; | |
342 | AugmentPolicy::rotate_right(x,y); | |
343 | } | |
344 | ||
345 | static void rebalance(pointer x,parent_ref root) | |
346 | { | |
347 | x->color()=red; | |
348 | while(x!=root&&x->parent()->color()==red){ | |
349 | if(x->parent()==x->parent()->parent()->left()){ | |
350 | pointer y=x->parent()->parent()->right(); | |
351 | if(y!=pointer(0)&&y->color()==red){ | |
352 | x->parent()->color()=black; | |
353 | y->color()=black; | |
354 | x->parent()->parent()->color()=red; | |
355 | x=x->parent()->parent(); | |
356 | } | |
357 | else{ | |
358 | if(x==x->parent()->right()){ | |
359 | x=x->parent(); | |
360 | rotate_left(x,root); | |
361 | } | |
362 | x->parent()->color()=black; | |
363 | x->parent()->parent()->color()=red; | |
364 | rotate_right(x->parent()->parent(),root); | |
365 | } | |
366 | } | |
367 | else{ | |
368 | pointer y=x->parent()->parent()->left(); | |
369 | if(y!=pointer(0)&&y->color()==red){ | |
370 | x->parent()->color()=black; | |
371 | y->color()=black; | |
372 | x->parent()->parent()->color()=red; | |
373 | x=x->parent()->parent(); | |
374 | } | |
375 | else{ | |
376 | if(x==x->parent()->left()){ | |
377 | x=x->parent(); | |
378 | rotate_right(x,root); | |
379 | } | |
380 | x->parent()->color()=black; | |
381 | x->parent()->parent()->color()=red; | |
382 | rotate_left(x->parent()->parent(),root); | |
383 | } | |
384 | } | |
385 | } | |
386 | root->color()=black; | |
387 | } | |
388 | ||
389 | static void link( | |
390 | pointer x,ordered_index_side side,pointer position,pointer header) | |
391 | { | |
392 | if(side==to_left){ | |
393 | position->left()=x; /* also makes leftmost=x when parent==header */ | |
394 | if(position==header){ | |
395 | header->parent()=x; | |
396 | header->right()=x; | |
397 | } | |
398 | else if(position==header->left()){ | |
399 | header->left()=x; /* maintain leftmost pointing to min node */ | |
400 | } | |
401 | } | |
402 | else{ | |
403 | position->right()=x; | |
404 | if(position==header->right()){ | |
405 | header->right()=x; /* maintain rightmost pointing to max node */ | |
406 | } | |
407 | } | |
408 | x->parent()=position; | |
409 | x->left()=pointer(0); | |
410 | x->right()=pointer(0); | |
411 | AugmentPolicy::add(x,pointer(header->parent())); | |
412 | ordered_index_node_impl::rebalance(x,header->parent()); | |
413 | } | |
414 | ||
20effc67 | 415 | static pointer rebalance_for_extract( |
7c673cae FG |
416 | pointer z,parent_ref root,pointer& leftmost,pointer& rightmost) |
417 | { | |
418 | pointer y=z; | |
419 | pointer x=pointer(0); | |
420 | pointer x_parent=pointer(0); | |
421 | if(y->left()==pointer(0)){ /* z has at most one non-null child. y==z. */ | |
422 | x=y->right(); /* x might be null */ | |
423 | } | |
424 | else{ | |
425 | if(y->right()==pointer(0)){ /* z has exactly one non-null child. y==z. */ | |
426 | x=y->left(); /* x is not null */ | |
427 | } | |
428 | else{ /* z has two non-null children. Set y to */ | |
429 | y=y->right(); /* z's successor. x might be null. */ | |
430 | while(y->left()!=pointer(0))y=y->left(); | |
431 | x=y->right(); | |
432 | } | |
433 | } | |
434 | AugmentPolicy::remove(y,pointer(root)); | |
435 | if(y!=z){ | |
436 | AugmentPolicy::copy(z,y); | |
437 | z->left()->parent()=y; /* relink y in place of z. y is z's successor */ | |
438 | y->left()=z->left(); | |
439 | if(y!=z->right()){ | |
440 | x_parent=y->parent(); | |
441 | if(x!=pointer(0))x->parent()=y->parent(); | |
442 | y->parent()->left()=x; /* y must be a child of left */ | |
443 | y->right()=z->right(); | |
444 | z->right()->parent()=y; | |
445 | } | |
446 | else{ | |
447 | x_parent=y; | |
448 | } | |
449 | ||
450 | if(root==z) root=y; | |
451 | else if(z->parent()->left()==z)z->parent()->left()=y; | |
452 | else z->parent()->right()=y; | |
453 | y->parent()=z->parent(); | |
454 | ordered_index_color c=y->color(); | |
455 | y->color()=z->color(); | |
456 | z->color()=c; | |
457 | y=z; /* y now points to node to be actually deleted */ | |
458 | } | |
459 | else{ /* y==z */ | |
460 | x_parent=y->parent(); | |
461 | if(x!=pointer(0))x->parent()=y->parent(); | |
462 | if(root==z){ | |
463 | root=x; | |
464 | } | |
465 | else{ | |
466 | if(z->parent()->left()==z)z->parent()->left()=x; | |
467 | else z->parent()->right()=x; | |
468 | } | |
469 | if(leftmost==z){ | |
470 | if(z->right()==pointer(0)){ /* z->left() must be null also */ | |
471 | leftmost=z->parent(); | |
472 | } | |
473 | else{ | |
474 | leftmost=minimum(x); /* makes leftmost==header if z==root */ | |
475 | } | |
476 | } | |
477 | if(rightmost==z){ | |
478 | if(z->left()==pointer(0)){ /* z->right() must be null also */ | |
479 | rightmost=z->parent(); | |
480 | } | |
481 | else{ /* x==z->left() */ | |
482 | rightmost=maximum(x); /* makes rightmost==header if z==root */ | |
483 | } | |
484 | } | |
485 | } | |
486 | if(y->color()!=red){ | |
487 | while(x!=root&&(x==pointer(0)|| x->color()==black)){ | |
488 | if(x==x_parent->left()){ | |
489 | pointer w=x_parent->right(); | |
490 | if(w->color()==red){ | |
491 | w->color()=black; | |
492 | x_parent->color()=red; | |
493 | rotate_left(x_parent,root); | |
494 | w=x_parent->right(); | |
495 | } | |
496 | if((w->left()==pointer(0)||w->left()->color()==black) && | |
497 | (w->right()==pointer(0)||w->right()->color()==black)){ | |
498 | w->color()=red; | |
499 | x=x_parent; | |
500 | x_parent=x_parent->parent(); | |
501 | } | |
502 | else{ | |
503 | if(w->right()==pointer(0 ) | |
504 | || w->right()->color()==black){ | |
505 | if(w->left()!=pointer(0)) w->left()->color()=black; | |
506 | w->color()=red; | |
507 | rotate_right(w,root); | |
508 | w=x_parent->right(); | |
509 | } | |
510 | w->color()=x_parent->color(); | |
511 | x_parent->color()=black; | |
512 | if(w->right()!=pointer(0))w->right()->color()=black; | |
513 | rotate_left(x_parent,root); | |
514 | break; | |
515 | } | |
516 | } | |
517 | else{ /* same as above,with right <-> left */ | |
518 | pointer w=x_parent->left(); | |
519 | if(w->color()==red){ | |
520 | w->color()=black; | |
521 | x_parent->color()=red; | |
522 | rotate_right(x_parent,root); | |
523 | w=x_parent->left(); | |
524 | } | |
525 | if((w->right()==pointer(0)||w->right()->color()==black) && | |
526 | (w->left()==pointer(0)||w->left()->color()==black)){ | |
527 | w->color()=red; | |
528 | x=x_parent; | |
529 | x_parent=x_parent->parent(); | |
530 | } | |
531 | else{ | |
532 | if(w->left()==pointer(0)||w->left()->color()==black){ | |
533 | if(w->right()!=pointer(0))w->right()->color()=black; | |
534 | w->color()=red; | |
535 | rotate_left(w,root); | |
536 | w=x_parent->left(); | |
537 | } | |
538 | w->color()=x_parent->color(); | |
539 | x_parent->color()=black; | |
540 | if(w->left()!=pointer(0))w->left()->color()=black; | |
541 | rotate_right(x_parent,root); | |
542 | break; | |
543 | } | |
544 | } | |
545 | } | |
546 | if(x!=pointer(0))x->color()=black; | |
547 | } | |
548 | 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, | |
92f5a8d4 | 583 | typename rebind_alloc_for< |
7c673cae FG |
584 | typename Super::allocator_type, |
585 | char | |
586 | >::type | |
587 | > | |
588 | { | |
589 | typedef ordered_index_node_impl< | |
590 | AugmentPolicy, | |
92f5a8d4 | 591 | typename rebind_alloc_for< |
7c673cae FG |
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: | |
92f5a8d4 TL |
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; | |
7c673cae FG |
613 | |
614 | impl_color_ref color(){return trampoline::color();} | |
615 | ordered_index_color color()const{return trampoline::color();} | |
616 | impl_parent_ref parent(){return trampoline::parent();} | |
617 | impl_pointer parent()const{return trampoline::parent();} | |
618 | impl_pointer& left(){return trampoline::left();} | |
619 | impl_pointer left()const{return trampoline::left();} | |
620 | impl_pointer& right(){return trampoline::right();} | |
621 | impl_pointer right()const{return trampoline::right();} | |
622 | ||
623 | impl_pointer impl() | |
624 | { | |
625 | return static_cast<impl_pointer>( | |
626 | 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 | static ordered_index_node* from_impl(impl_pointer x) | |
636 | { | |
637 | return | |
638 | static_cast<ordered_index_node*>( | |
639 | static_cast<trampoline*>( | |
640 | 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 | static void increment(ordered_index_node*& x) | |
654 | { | |
655 | impl_pointer xi=x->impl(); | |
656 | trampoline::increment(xi); | |
657 | x=from_impl(xi); | |
658 | } | |
659 | ||
660 | static void decrement(ordered_index_node*& x) | |
661 | { | |
662 | impl_pointer xi=x->impl(); | |
663 | trampoline::decrement(xi); | |
664 | x=from_impl(xi); | |
665 | } | |
666 | }; | |
667 | ||
668 | } /* namespace multi_index::detail */ | |
669 | ||
670 | } /* namespace multi_index */ | |
671 | ||
672 | } /* namespace boost */ | |
673 | ||
674 | #endif |