1 /* Copyright 2003-2018 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 9 #ifndef BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_NODE_HPP 10 #define BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_NODE_HPP 11 12 #if defined(_MSC_VER) 13 #pragma once 14 #endif 15 16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ 17 #include <boost/detail/allocator_utilities.hpp> 18 #include <boost/multi_index/detail/raw_ptr.hpp> 19 #include <utility> 20 #include <memory> 21 22 namespace boost{ 23 24 namespace multi_index{ 25 26 namespace detail{ 27 28 /* Certain C++ requirements on unordered associative containers (see LWG issue 29 * #579) imply a data structure where nodes are linked in a single list, which 30 * in its turn forces implementors to add additional overhed per node to 31 * associate each with its corresponding bucket. Others resort to storing hash 32 * values, we use an alternative structure providing unconditional O(1) 33 * manipulation, even in situations of unfair hash distribution, plus some 34 * lookup speedups. For unique indices we maintain a doubly linked list of 35 * nodes except that if N is the first node of a bucket its associated 36 * bucket node is embedded between N and the preceding node in the following 37 * manner: 38 * 39 * +---+ +---+ +---+ +---+ 40 * <--+ |<--+ | <--+ |<--+ | 41 * ... | B0| | B1| ... | B1| | B2| ... 42 * | |-+ | +--> | |-+ | +--> 43 * +-+-+ | +---+ +-+-+ | +---+ 44 * | ^ | ^ 45 * | | | | 46 * | +-+ | +-+ 47 * | | | | 48 * v | v | 49 * --+---+---+---+-- --+---+---+---+-- 50 * ... | | B1| | ... | | B2| | ... 51 * --+---+---+---+-- --+---+---+---+-- 52 * 53 * 54 * The fist and last nodes of buckets can be checked with 55 * 56 * first node of a bucket: Npn != N 57 * last node of a bucket: Nnp != N 58 * 59 * (n and p short for ->next(), ->prior(), bucket nodes have prior pointers 60 * only). Pure insert and erase (without lookup) can be unconditionally done 61 * in O(1). 62 * For non-unique indices we add the following additional complexity: when 63 * there is a group of 3 or more equivalent elements, they are linked as 64 * follows: 65 * 66 * +-----------------------+ 67 * | v 68 * +---+ | +---+ +---+ +---+ 69 * | | +-+ | | |<--+ | 70 * | F | | S | ... | P | | L | 71 * | +-->| | | +-+ | | 72 * +---+ +---+ +---+ | +---+ 73 * ^ | 74 * +-----------------------+ 75 * 76 * F, S, P and L are the first, second, penultimate and last node in the 77 * group, respectively (S and P can coincide if the group has size 3.) This 78 * arrangement is used to skip equivalent elements in O(1) when doing lookup, 79 * while preserving O(1) insert/erase. The following invariants identify 80 * special positions (some of the operations have to be carefully implemented 81 * as Xnn is not valid if Xn points to a bucket): 82 * 83 * first node of a bucket: Npnp == N 84 * last node of a bucket: Nnpp == N 85 * first node of a group: Nnp != N && Nnppn == N 86 * second node of a group: Npn != N && Nppnn == N 87 * n-1 node of a group: Nnp != N && Nnnpp == N 88 * last node of a group: Npn != N && Npnnp == N 89 * 90 * The memory overhead is one pointer per bucket plus two pointers per node, 91 * probably unbeatable. The resulting structure is bidirectonally traversable, 92 * though currently we are just providing forward iteration. 93 */ 94 95 template<typename Allocator> 96 struct hashed_index_node_impl; 97 98 /* half-header (only prior() pointer) to use for the bucket array */ 99 100 template<typename Allocator> 101 struct hashed_index_base_node_impl 102 { 103 typedef typename 104 boost::detail::allocator::rebind_to< 105 Allocator,hashed_index_base_node_impl 106 >::type base_allocator; 107 typedef typename 108 boost::detail::allocator::rebind_to< 109 Allocator, 110 hashed_index_node_impl<Allocator> 111 >::type node_allocator; 112 #ifdef BOOST_NO_CXX11_ALLOCATOR 113 typedef typename base_allocator::pointer base_pointer; 114 typedef typename base_allocator::const_pointer const_base_pointer; 115 typedef typename node_allocator::pointer pointer; 116 typedef typename node_allocator::const_pointer const_pointer; 117 #else 118 typedef typename std::allocator_traits< 119 base_allocator 120 >::pointer base_pointer; 121 typedef typename std::allocator_traits< 122 base_allocator 123 >::const_pointer const_base_pointer; 124 typedef typename std::allocator_traits< 125 node_allocator 126 >::pointer pointer; 127 typedef typename std::allocator_traits< 128 node_allocator 129 >::const_pointer const_pointer; 130 #endif 131 priorboost::multi_index::detail::hashed_index_base_node_impl132 pointer& prior(){return prior_;} priorboost::multi_index::detail::hashed_index_base_node_impl133 pointer prior()const{return prior_;} 134 135 private: 136 pointer prior_; 137 }; 138 139 /* full header (prior() and next()) for the nodes */ 140 141 template<typename Allocator> 142 struct hashed_index_node_impl:hashed_index_base_node_impl<Allocator> 143 { 144 private: 145 typedef hashed_index_base_node_impl<Allocator> super; 146 147 public: 148 typedef typename super::base_pointer base_pointer; 149 typedef typename super::const_base_pointer const_base_pointer; 150 typedef typename super::pointer pointer; 151 typedef typename super::const_pointer const_pointer; 152 nextboost::multi_index::detail::hashed_index_node_impl153 base_pointer& next(){return next_;} nextboost::multi_index::detail::hashed_index_node_impl154 base_pointer next()const{return next_;} 155 pointer_fromboost::multi_index::detail::hashed_index_node_impl156 static pointer pointer_from(base_pointer x) 157 { 158 return static_cast<pointer>( 159 static_cast<hashed_index_node_impl*>( 160 raw_ptr<super*>(x))); 161 } 162 base_pointer_fromboost::multi_index::detail::hashed_index_node_impl163 static base_pointer base_pointer_from(pointer x) 164 { 165 return static_cast<base_pointer>( 166 raw_ptr<hashed_index_node_impl*>(x)); 167 } 168 169 private: 170 base_pointer next_; 171 }; 172 173 /* Boost.MultiIndex requires machinery to reverse unlink operations. A simple 174 * way to make a pointer-manipulation function undoable is to templatize 175 * its internal pointer assignments with a functor that, besides doing the 176 * assignment, keeps track of the original pointer values and can later undo 177 * the operations in reverse order. 178 */ 179 180 struct default_assigner 181 { operator ()boost::multi_index::detail::default_assigner182 template<typename T> void operator()(T& x,const T& val){x=val;} 183 }; 184 185 template<typename Node> 186 struct unlink_undo_assigner 187 { 188 typedef typename Node::base_pointer base_pointer; 189 typedef typename Node::pointer pointer; 190 unlink_undo_assignerboost::multi_index::detail::unlink_undo_assigner191 unlink_undo_assigner():pointer_track_count(0),base_pointer_track_count(0){} 192 operator ()boost::multi_index::detail::unlink_undo_assigner193 void operator()(pointer& x,pointer val) 194 { 195 pointer_tracks[pointer_track_count].x=&x; 196 pointer_tracks[pointer_track_count++].val=x; 197 x=val; 198 } 199 operator ()boost::multi_index::detail::unlink_undo_assigner200 void operator()(base_pointer& x,base_pointer val) 201 { 202 base_pointer_tracks[base_pointer_track_count].x=&x; 203 base_pointer_tracks[base_pointer_track_count++].val=x; 204 x=val; 205 } 206 operator ()boost::multi_index::detail::unlink_undo_assigner207 void operator()() /* undo op */ 208 { 209 /* in the absence of aliasing, restitution order is immaterial */ 210 211 while(pointer_track_count--){ 212 *(pointer_tracks[pointer_track_count].x)= 213 pointer_tracks[pointer_track_count].val; 214 } 215 while(base_pointer_track_count--){ 216 *(base_pointer_tracks[base_pointer_track_count].x)= 217 base_pointer_tracks[base_pointer_track_count].val; 218 } 219 } 220 221 struct pointer_track {pointer* x; pointer val;}; 222 struct base_pointer_track{base_pointer* x; base_pointer val;}; 223 224 /* We know the maximum number of pointer and base pointer assignments that 225 * the two unlink versions do, so we can statically reserve the needed 226 * storage. 227 */ 228 229 pointer_track pointer_tracks[3]; 230 int pointer_track_count; 231 base_pointer_track base_pointer_tracks[2]; 232 int base_pointer_track_count; 233 }; 234 235 /* algorithmic stuff for unique and non-unique variants */ 236 237 struct hashed_unique_tag{}; 238 struct hashed_non_unique_tag{}; 239 240 template<typename Node,typename Category> 241 struct hashed_index_node_alg; 242 243 template<typename Node> 244 struct hashed_index_node_alg<Node,hashed_unique_tag> 245 { 246 typedef typename Node::base_pointer base_pointer; 247 typedef typename Node::const_base_pointer const_base_pointer; 248 typedef typename Node::pointer pointer; 249 typedef typename Node::const_pointer const_pointer; 250 is_first_of_bucketboost::multi_index::detail::hashed_index_node_alg251 static bool is_first_of_bucket(pointer x) 252 { 253 return x->prior()->next()!=base_pointer_from(x); 254 } 255 afterboost::multi_index::detail::hashed_index_node_alg256 static pointer after(pointer x) 257 { 258 return is_last_of_bucket(x)?x->next()->prior():pointer_from(x->next()); 259 } 260 after_localboost::multi_index::detail::hashed_index_node_alg261 static pointer after_local(pointer x) 262 { 263 return is_last_of_bucket(x)?pointer(0):pointer_from(x->next()); 264 } 265 next_to_inspectboost::multi_index::detail::hashed_index_node_alg266 static pointer next_to_inspect(pointer x) 267 { 268 return is_last_of_bucket(x)?pointer(0):pointer_from(x->next()); 269 } 270 linkboost::multi_index::detail::hashed_index_node_alg271 static void link(pointer x,base_pointer buc,pointer end) 272 { 273 if(buc->prior()==pointer(0)){ /* empty bucket */ 274 x->prior()=end->prior(); 275 x->next()=end->prior()->next(); 276 x->prior()->next()=buc; 277 buc->prior()=x; 278 end->prior()=x; 279 } 280 else{ 281 x->prior()=buc->prior()->prior(); 282 x->next()=base_pointer_from(buc->prior()); 283 buc->prior()=x; 284 x->next()->prior()=x; 285 } 286 } 287 unlinkboost::multi_index::detail::hashed_index_node_alg288 static void unlink(pointer x) 289 { 290 default_assigner assign; 291 unlink(x,assign); 292 } 293 294 typedef unlink_undo_assigner<Node> unlink_undo; 295 296 template<typename Assigner> unlinkboost::multi_index::detail::hashed_index_node_alg297 static void unlink(pointer x,Assigner& assign) 298 { 299 if(is_first_of_bucket(x)){ 300 if(is_last_of_bucket(x)){ 301 assign(x->prior()->next()->prior(),pointer(0)); 302 assign(x->prior()->next(),x->next()); 303 assign(x->next()->prior()->prior(),x->prior()); 304 } 305 else{ 306 assign(x->prior()->next()->prior(),pointer_from(x->next())); 307 assign(x->next()->prior(),x->prior()); 308 } 309 } 310 else if(is_last_of_bucket(x)){ 311 assign(x->prior()->next(),x->next()); 312 assign(x->next()->prior()->prior(),x->prior()); 313 } 314 else{ 315 assign(x->prior()->next(),x->next()); 316 assign(x->next()->prior(),x->prior()); 317 } 318 } 319 320 /* used only at rehashing */ 321 appendboost::multi_index::detail::hashed_index_node_alg322 static void append(pointer x,pointer end) 323 { 324 x->prior()=end->prior(); 325 x->next()=end->prior()->next(); 326 x->prior()->next()=base_pointer_from(x); 327 end->prior()=x; 328 } 329 unlink_lastboost::multi_index::detail::hashed_index_node_alg330 static bool unlink_last(pointer end) 331 { 332 /* returns true iff bucket is emptied */ 333 334 pointer x=end->prior(); 335 if(x->prior()->next()==base_pointer_from(x)){ 336 x->prior()->next()=x->next(); 337 end->prior()=x->prior(); 338 return false; 339 } 340 else{ 341 x->prior()->next()->prior()=pointer(0); 342 x->prior()->next()=x->next(); 343 end->prior()=x->prior(); 344 return true; 345 } 346 } 347 348 private: pointer_fromboost::multi_index::detail::hashed_index_node_alg349 static pointer pointer_from(base_pointer x) 350 { 351 return Node::pointer_from(x); 352 } 353 base_pointer_fromboost::multi_index::detail::hashed_index_node_alg354 static base_pointer base_pointer_from(pointer x) 355 { 356 return Node::base_pointer_from(x); 357 } 358 is_last_of_bucketboost::multi_index::detail::hashed_index_node_alg359 static bool is_last_of_bucket(pointer x) 360 { 361 return x->next()->prior()!=x; 362 } 363 }; 364 365 template<typename Node> 366 struct hashed_index_node_alg<Node,hashed_non_unique_tag> 367 { 368 typedef typename Node::base_pointer base_pointer; 369 typedef typename Node::const_base_pointer const_base_pointer; 370 typedef typename Node::pointer pointer; 371 typedef typename Node::const_pointer const_pointer; 372 is_first_of_bucketboost::multi_index::detail::hashed_index_node_alg373 static bool is_first_of_bucket(pointer x) 374 { 375 return x->prior()->next()->prior()==x; 376 } 377 is_first_of_groupboost::multi_index::detail::hashed_index_node_alg378 static bool is_first_of_group(pointer x) 379 { 380 return 381 x->next()->prior()!=x&& 382 x->next()->prior()->prior()->next()==base_pointer_from(x); 383 } 384 afterboost::multi_index::detail::hashed_index_node_alg385 static pointer after(pointer x) 386 { 387 if(x->next()->prior()==x)return pointer_from(x->next()); 388 if(x->next()->prior()->prior()==x)return x->next()->prior(); 389 if(x->next()->prior()->prior()->next()==base_pointer_from(x)) 390 return pointer_from(x->next()); 391 return pointer_from(x->next())->next()->prior(); 392 } 393 after_localboost::multi_index::detail::hashed_index_node_alg394 static pointer after_local(pointer x) 395 { 396 if(x->next()->prior()==x)return pointer_from(x->next()); 397 if(x->next()->prior()->prior()==x)return pointer(0); 398 if(x->next()->prior()->prior()->next()==base_pointer_from(x)) 399 return pointer_from(x->next()); 400 return pointer_from(x->next())->next()->prior(); 401 } 402 next_to_inspectboost::multi_index::detail::hashed_index_node_alg403 static pointer next_to_inspect(pointer x) 404 { 405 if(x->next()->prior()==x)return pointer_from(x->next()); 406 if(x->next()->prior()->prior()==x)return pointer(0); 407 if(x->next()->prior()->next()->prior()!=x->next()->prior()) 408 return pointer(0); 409 return pointer_from(x->next()->prior()->next()); 410 } 411 linkboost::multi_index::detail::hashed_index_node_alg412 static void link(pointer x,base_pointer buc,pointer end) 413 { 414 if(buc->prior()==pointer(0)){ /* empty bucket */ 415 x->prior()=end->prior(); 416 x->next()=end->prior()->next(); 417 x->prior()->next()=buc; 418 buc->prior()=x; 419 end->prior()=x; 420 } 421 else{ 422 x->prior()=buc->prior()->prior(); 423 x->next()=base_pointer_from(buc->prior()); 424 buc->prior()=x; 425 x->next()->prior()=x; 426 } 427 }; 428 linkboost::multi_index::detail::hashed_index_node_alg429 static void link(pointer x,pointer first,pointer last) 430 { 431 x->prior()=first->prior(); 432 x->next()=base_pointer_from(first); 433 if(is_first_of_bucket(first)){ 434 x->prior()->next()->prior()=x; 435 } 436 else{ 437 x->prior()->next()=base_pointer_from(x); 438 } 439 440 if(first==last){ 441 last->prior()=x; 442 } 443 else if(first->next()==base_pointer_from(last)){ 444 first->prior()=last; 445 first->next()=base_pointer_from(x); 446 } 447 else{ 448 pointer second=pointer_from(first->next()), 449 lastbutone=last->prior(); 450 second->prior()=first; 451 first->prior()=last; 452 lastbutone->next()=base_pointer_from(x); 453 } 454 } 455 unlinkboost::multi_index::detail::hashed_index_node_alg456 static void unlink(pointer x) 457 { 458 default_assigner assign; 459 unlink(x,assign); 460 } 461 462 typedef unlink_undo_assigner<Node> unlink_undo; 463 464 template<typename Assigner> unlinkboost::multi_index::detail::hashed_index_node_alg465 static void unlink(pointer x,Assigner& assign) 466 { 467 if(x->prior()->next()==base_pointer_from(x)){ 468 if(x->next()->prior()==x){ 469 left_unlink(x,assign); 470 right_unlink(x,assign); 471 } 472 else if(x->next()->prior()->prior()==x){ /* last of bucket */ 473 left_unlink(x,assign); 474 right_unlink_last_of_bucket(x,assign); 475 } 476 else if(x->next()->prior()->prior()->next()== 477 base_pointer_from(x)){ /* first of group size */ 478 left_unlink(x,assign); 479 right_unlink_first_of_group(x,assign); 480 } 481 else{ /* n-1 of group */ 482 unlink_last_but_one_of_group(x,assign); 483 } 484 } 485 else if(x->prior()->next()->prior()==x){ /* first of bucket */ 486 if(x->next()->prior()==x){ 487 left_unlink_first_of_bucket(x,assign); 488 right_unlink(x,assign); 489 } 490 else if(x->next()->prior()->prior()==x){ /* last of bucket */ 491 assign(x->prior()->next()->prior(),pointer(0)); 492 assign(x->prior()->next(),x->next()); 493 assign(x->next()->prior()->prior(),x->prior()); 494 } 495 else{ /* first of group */ 496 left_unlink_first_of_bucket(x,assign); 497 right_unlink_first_of_group(x,assign); 498 } 499 } 500 else if(x->next()->prior()->prior()==x){ /* last of group and bucket */ 501 left_unlink_last_of_group(x,assign); 502 right_unlink_last_of_bucket(x,assign); 503 } 504 else if(pointer_from(x->prior()->prior()->next()) 505 ->next()==base_pointer_from(x)){ /* second of group */ 506 unlink_second_of_group(x,assign); 507 } 508 else{ /* last of group, ~(last of bucket) */ 509 left_unlink_last_of_group(x,assign); 510 right_unlink(x,assign); 511 } 512 } 513 514 /* used only at rehashing */ 515 link_rangeboost::multi_index::detail::hashed_index_node_alg516 static void link_range( 517 pointer first,pointer last,base_pointer buc,pointer cend) 518 { 519 if(buc->prior()==pointer(0)){ /* empty bucket */ 520 first->prior()=cend->prior(); 521 last->next()=cend->prior()->next(); 522 first->prior()->next()=buc; 523 buc->prior()=first; 524 cend->prior()=last; 525 } 526 else{ 527 first->prior()=buc->prior()->prior(); 528 last->next()=base_pointer_from(buc->prior()); 529 buc->prior()=first; 530 last->next()->prior()=last; 531 } 532 } 533 append_rangeboost::multi_index::detail::hashed_index_node_alg534 static void append_range(pointer first,pointer last,pointer cend) 535 { 536 first->prior()=cend->prior(); 537 last->next()=cend->prior()->next(); 538 first->prior()->next()=base_pointer_from(first); 539 cend->prior()=last; 540 } 541 unlink_last_groupboost::multi_index::detail::hashed_index_node_alg542 static std::pair<pointer,bool> unlink_last_group(pointer end) 543 { 544 /* returns first of group true iff bucket is emptied */ 545 546 pointer x=end->prior(); 547 if(x->prior()->next()==base_pointer_from(x)){ 548 x->prior()->next()=x->next(); 549 end->prior()=x->prior(); 550 return std::make_pair(x,false); 551 } 552 else if(x->prior()->next()->prior()==x){ 553 x->prior()->next()->prior()=pointer(0); 554 x->prior()->next()=x->next(); 555 end->prior()=x->prior(); 556 return std::make_pair(x,true); 557 } 558 else{ 559 pointer y=pointer_from(x->prior()->next()); 560 561 if(y->prior()->next()==base_pointer_from(y)){ 562 y->prior()->next()=x->next(); 563 end->prior()=y->prior(); 564 return std::make_pair(y,false); 565 } 566 else{ 567 y->prior()->next()->prior()=pointer(0); 568 y->prior()->next()=x->next(); 569 end->prior()=y->prior(); 570 return std::make_pair(y,true); 571 } 572 } 573 } 574 unlink_rangeboost::multi_index::detail::hashed_index_node_alg575 static void unlink_range(pointer first,pointer last) 576 { 577 if(is_first_of_bucket(first)){ 578 if(is_last_of_bucket(last)){ 579 first->prior()->next()->prior()=pointer(0); 580 first->prior()->next()=last->next(); 581 last->next()->prior()->prior()=first->prior(); 582 } 583 else{ 584 first->prior()->next()->prior()=pointer_from(last->next()); 585 last->next()->prior()=first->prior(); 586 } 587 } 588 else if(is_last_of_bucket(last)){ 589 first->prior()->next()=last->next(); 590 last->next()->prior()->prior()=first->prior(); 591 } 592 else{ 593 first->prior()->next()=last->next(); 594 last->next()->prior()=first->prior(); 595 } 596 } 597 598 private: pointer_fromboost::multi_index::detail::hashed_index_node_alg599 static pointer pointer_from(base_pointer x) 600 { 601 return Node::pointer_from(x); 602 } 603 base_pointer_fromboost::multi_index::detail::hashed_index_node_alg604 static base_pointer base_pointer_from(pointer x) 605 { 606 return Node::base_pointer_from(x); 607 } 608 is_last_of_bucketboost::multi_index::detail::hashed_index_node_alg609 static bool is_last_of_bucket(pointer x) 610 { 611 return x->next()->prior()->prior()==x; 612 } 613 614 template<typename Assigner> left_unlinkboost::multi_index::detail::hashed_index_node_alg615 static void left_unlink(pointer x,Assigner& assign) 616 { 617 assign(x->prior()->next(),x->next()); 618 } 619 620 template<typename Assigner> right_unlinkboost::multi_index::detail::hashed_index_node_alg621 static void right_unlink(pointer x,Assigner& assign) 622 { 623 assign(x->next()->prior(),x->prior()); 624 } 625 626 template<typename Assigner> left_unlink_first_of_bucketboost::multi_index::detail::hashed_index_node_alg627 static void left_unlink_first_of_bucket(pointer x,Assigner& assign) 628 { 629 assign(x->prior()->next()->prior(),pointer_from(x->next())); 630 } 631 632 template<typename Assigner> right_unlink_last_of_bucketboost::multi_index::detail::hashed_index_node_alg633 static void right_unlink_last_of_bucket(pointer x,Assigner& assign) 634 { 635 assign(x->next()->prior()->prior(),x->prior()); 636 } 637 638 template<typename Assigner> right_unlink_first_of_groupboost::multi_index::detail::hashed_index_node_alg639 static void right_unlink_first_of_group(pointer x,Assigner& assign) 640 { 641 pointer second=pointer_from(x->next()), 642 last=second->prior(), 643 lastbutone=last->prior(); 644 if(second==lastbutone){ 645 assign(second->next(),base_pointer_from(last)); 646 assign(second->prior(),x->prior()); 647 } 648 else{ 649 assign(lastbutone->next(),base_pointer_from(second)); 650 assign(second->next()->prior(),last); 651 assign(second->prior(),x->prior()); 652 } 653 } 654 655 template<typename Assigner> left_unlink_last_of_groupboost::multi_index::detail::hashed_index_node_alg656 static void left_unlink_last_of_group(pointer x,Assigner& assign) 657 { 658 pointer lastbutone=x->prior(), 659 first=pointer_from(lastbutone->next()), 660 second=pointer_from(first->next()); 661 if(lastbutone==second){ 662 assign(lastbutone->prior(),first); 663 assign(lastbutone->next(),x->next()); 664 } 665 else{ 666 assign(second->prior(),lastbutone); 667 assign(lastbutone->prior()->next(),base_pointer_from(first)); 668 assign(lastbutone->next(),x->next()); 669 } 670 } 671 672 template<typename Assigner> unlink_last_but_one_of_groupboost::multi_index::detail::hashed_index_node_alg673 static void unlink_last_but_one_of_group(pointer x,Assigner& assign) 674 { 675 pointer first=pointer_from(x->next()), 676 second=pointer_from(first->next()), 677 last=second->prior(); 678 if(second==x){ 679 assign(last->prior(),first); 680 assign(first->next(),base_pointer_from(last)); 681 } 682 else{ 683 assign(last->prior(),x->prior()); 684 assign(x->prior()->next(),base_pointer_from(first)); 685 } 686 } 687 688 template<typename Assigner> unlink_second_of_groupboost::multi_index::detail::hashed_index_node_alg689 static void unlink_second_of_group(pointer x,Assigner& assign) 690 { 691 pointer last=x->prior(), 692 lastbutone=last->prior(), 693 first=pointer_from(lastbutone->next()); 694 if(lastbutone==x){ 695 assign(first->next(),base_pointer_from(last)); 696 assign(last->prior(),first); 697 } 698 else{ 699 assign(first->next(),x->next()); 700 assign(x->next()->prior(),last); 701 } 702 } 703 }; 704 705 template<typename Super> 706 struct hashed_index_node_trampoline: 707 hashed_index_node_impl< 708 typename boost::detail::allocator::rebind_to< 709 typename Super::allocator_type, 710 char 711 >::type 712 > 713 { 714 typedef typename boost::detail::allocator::rebind_to< 715 typename Super::allocator_type, 716 char 717 >::type impl_allocator_type; 718 typedef hashed_index_node_impl<impl_allocator_type> impl_type; 719 }; 720 721 template<typename Super,typename Category> 722 struct hashed_index_node: 723 Super,hashed_index_node_trampoline<Super> 724 { 725 private: 726 typedef hashed_index_node_trampoline<Super> trampoline; 727 728 public: 729 typedef typename trampoline::impl_type impl_type; 730 typedef hashed_index_node_alg< 731 impl_type,Category> node_alg; 732 typedef typename trampoline::base_pointer impl_base_pointer; 733 typedef typename trampoline::const_base_pointer const_impl_base_pointer; 734 typedef typename trampoline::pointer impl_pointer; 735 typedef typename trampoline::const_pointer const_impl_pointer; 736 priorboost::multi_index::detail::hashed_index_node737 impl_pointer& prior(){return trampoline::prior();} priorboost::multi_index::detail::hashed_index_node738 impl_pointer prior()const{return trampoline::prior();} nextboost::multi_index::detail::hashed_index_node739 impl_base_pointer& next(){return trampoline::next();} nextboost::multi_index::detail::hashed_index_node740 impl_base_pointer next()const{return trampoline::next();} 741 implboost::multi_index::detail::hashed_index_node742 impl_pointer impl() 743 { 744 return static_cast<impl_pointer>( 745 static_cast<impl_type*>(static_cast<trampoline*>(this))); 746 } 747 implboost::multi_index::detail::hashed_index_node748 const_impl_pointer impl()const 749 { 750 return static_cast<const_impl_pointer>( 751 static_cast<const impl_type*>(static_cast<const trampoline*>(this))); 752 } 753 from_implboost::multi_index::detail::hashed_index_node754 static hashed_index_node* from_impl(impl_pointer x) 755 { 756 return 757 static_cast<hashed_index_node*>( 758 static_cast<trampoline*>( 759 raw_ptr<impl_type*>(x))); 760 } 761 from_implboost::multi_index::detail::hashed_index_node762 static const hashed_index_node* from_impl(const_impl_pointer x) 763 { 764 return 765 static_cast<const hashed_index_node*>( 766 static_cast<const trampoline*>( 767 raw_ptr<const impl_type*>(x))); 768 } 769 770 /* interoperability with hashed_index_iterator */ 771 incrementboost::multi_index::detail::hashed_index_node772 static void increment(hashed_index_node*& x) 773 { 774 x=from_impl(node_alg::after(x->impl())); 775 } 776 increment_localboost::multi_index::detail::hashed_index_node777 static void increment_local(hashed_index_node*& x) 778 { 779 x=from_impl(node_alg::after_local(x->impl())); 780 } 781 }; 782 783 } /* namespace multi_index::detail */ 784 785 } /* namespace multi_index */ 786 787 } /* namespace boost */ 788 789 #endif 790