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 colorboost::multi_index::detail::ordered_index_node_std_base97 ordered_index_color& color(){return color_;} colorboost::multi_index::detail::ordered_index_node_std_base98 ordered_index_color color()const{return color_;} parentboost::multi_index::detail::ordered_index_node_std_base99 pointer& parent(){return parent_;} parentboost::multi_index::detail::ordered_index_node_std_base100 pointer parent()const{return parent_;} leftboost::multi_index::detail::ordered_index_node_std_base101 pointer& left(){return left_;} leftboost::multi_index::detail::ordered_index_node_std_base102 pointer left()const{return left_;} rightboost::multi_index::detail::ordered_index_node_std_base103 pointer& right(){return right_;} rightboost::multi_index::detail::ordered_index_node_std_base104 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 { color_refboost::multi_index::detail::ordered_index_node_compressed_base::color_ref145 color_ref(uintptr_type* r_):r(r_){} color_refboost::multi_index::detail::ordered_index_node_compressed_base::color_ref146 color_ref(const color_ref& x):r(x.r){} 147 operator ordered_index_colorboost::multi_index::detail::ordered_index_node_compressed_base::color_ref148 operator ordered_index_color()const 149 { 150 return ordered_index_color(*r&uintptr_type(1)); 151 } 152 operator =boost::multi_index::detail::ordered_index_node_compressed_base::color_ref153 color_ref& operator=(ordered_index_color c) 154 { 155 *r&=~uintptr_type(1); 156 *r|=uintptr_type(c); 157 return *this; 158 } 159 operator =boost::multi_index::detail::ordered_index_node_compressed_base::color_ref160 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 { parent_refboost::multi_index::detail::ordered_index_node_compressed_base::parent_ref171 parent_ref(uintptr_type* r_):r(r_){} parent_refboost::multi_index::detail::ordered_index_node_compressed_base::parent_ref172 parent_ref(const parent_ref& x):r(x.r){} 173 operator pointerboost::multi_index::detail::ordered_index_node_compressed_base::parent_ref174 operator pointer()const 175 { 176 return (pointer)(void*)(*r&~uintptr_type(1)); 177 } 178 operator =boost::multi_index::detail::ordered_index_node_compressed_base::parent_ref179 parent_ref& operator=(pointer p) 180 { 181 *r=((uintptr_type)(void*)p)|(*r&uintptr_type(1)); 182 return *this; 183 } 184 operator =boost::multi_index::detail::ordered_index_node_compressed_base::parent_ref185 parent_ref& operator=(const parent_ref& x) 186 { 187 return operator=(x.operator pointer()); 188 } 189 operator ->boost::multi_index::detail::ordered_index_node_compressed_base::parent_ref190 pointer operator->()const 191 { 192 return operator pointer(); 193 } 194 195 private: 196 uintptr_type* r; 197 }; 198 colorboost::multi_index::detail::ordered_index_node_compressed_base199 color_ref color(){return color_ref(&parentcolor_);} colorboost::multi_index::detail::ordered_index_node_compressed_base200 ordered_index_color color()const 201 { 202 return ordered_index_color(parentcolor_&uintptr_type(1)); 203 } 204 parentboost::multi_index::detail::ordered_index_node_compressed_base205 parent_ref parent(){return parent_ref(&parentcolor_);} parentboost::multi_index::detail::ordered_index_node_compressed_base206 pointer parent()const 207 { 208 return (pointer)(void*)(parentcolor_&~uintptr_type(1)); 209 } 210 leftboost::multi_index::detail::ordered_index_node_compressed_base211 pointer& left(){return left_;} leftboost::multi_index::detail::ordered_index_node_compressed_base212 pointer left()const{return left_;} rightboost::multi_index::detail::ordered_index_node_compressed_base213 pointer& right(){return right_;} rightboost::multi_index::detail::ordered_index_node_compressed_base214 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 incrementboost::multi_index::detail::ordered_index_node_impl266 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 decrementboost::multi_index::detail::ordered_index_node_impl282 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 rotate_leftboost::multi_index::detail::ordered_index_node_impl303 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 minimumboost::multi_index::detail::ordered_index_node_impl318 static pointer minimum(pointer x) 319 { 320 while(x->left()!=pointer(0))x=x->left(); 321 return x; 322 } 323 maximumboost::multi_index::detail::ordered_index_node_impl324 static pointer maximum(pointer x) 325 { 326 while(x->right()!=pointer(0))x=x->right(); 327 return x; 328 } 329 rotate_rightboost::multi_index::detail::ordered_index_node_impl330 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 rebalanceboost::multi_index::detail::ordered_index_node_impl345 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 linkboost::multi_index::detail::ordered_index_node_impl389 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 rebalance_for_extractboost::multi_index::detail::ordered_index_node_impl415 static pointer rebalance_for_extract( 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 restoreboost::multi_index::detail::ordered_index_node_impl551 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 black_countboost::multi_index::detail::ordered_index_node_impl565 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 colorboost::multi_index::detail::ordered_index_node614 impl_color_ref color(){return trampoline::color();} colorboost::multi_index::detail::ordered_index_node615 ordered_index_color color()const{return trampoline::color();} parentboost::multi_index::detail::ordered_index_node616 impl_parent_ref parent(){return trampoline::parent();} parentboost::multi_index::detail::ordered_index_node617 impl_pointer parent()const{return trampoline::parent();} leftboost::multi_index::detail::ordered_index_node618 impl_pointer& left(){return trampoline::left();} leftboost::multi_index::detail::ordered_index_node619 impl_pointer left()const{return trampoline::left();} rightboost::multi_index::detail::ordered_index_node620 impl_pointer& right(){return trampoline::right();} rightboost::multi_index::detail::ordered_index_node621 impl_pointer right()const{return trampoline::right();} 622 implboost::multi_index::detail::ordered_index_node623 impl_pointer impl() 624 { 625 return static_cast<impl_pointer>( 626 static_cast<impl_type*>(static_cast<trampoline*>(this))); 627 } 628 implboost::multi_index::detail::ordered_index_node629 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 from_implboost::multi_index::detail::ordered_index_node635 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 from_implboost::multi_index::detail::ordered_index_node643 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 incrementboost::multi_index::detail::ordered_index_node653 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 decrementboost::multi_index::detail::ordered_index_node660 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 675