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 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 21 namespace boost{ 22 23 namespace multi_index{ 24 25 namespace detail{ 26 27 /* Certain C++ requirements on unordered associative containers (see LWG issue 28 * #579) imply a data structure where nodes are linked in a single list, which 29 * in its turn forces implementors to add additional overhed per node to 30 * associate each with its corresponding bucket. Others resort to storing hash 31 * values, we use an alternative structure providing unconditional O(1) 32 * manipulation, even in situations of unfair hash distribution, plus some 33 * lookup speedups. For unique indices we maintain a doubly linked list of 34 * nodes except that if N is the first node of a bucket its associated 35 * bucket node is embedded between N and the preceding node in the following 36 * manner: 37 * 38 * +---+ +---+ +---+ +---+ 39 * <--+ |<--+ | <--+ |<--+ | 40 * ... | B0| | B1| ... | B1| | B2| ... 41 * | |-+ | +--> | |-+ | +--> 42 * +-+-+ | +---+ +-+-+ | +---+ 43 * | ^ | ^ 44 * | | | | 45 * | +-+ | +-+ 46 * | | | | 47 * v | v | 48 * --+---+---+---+-- --+---+---+---+-- 49 * ... | | B1| | ... | | B2| | ... 50 * --+---+---+---+-- --+---+---+---+-- 51 * 52 * 53 * The fist and last nodes of buckets can be checked with 54 * 55 * first node of a bucket: Npn != N 56 * last node of a bucket: Nnp != N 57 * 58 * (n and p short for ->next(), ->prior(), bucket nodes have prior pointers 59 * only). Pure insert and erase (without lookup) can be unconditionally done 60 * in O(1). 61 * For non-unique indices we add the following additional complexity: when 62 * there is a group of 3 or more equivalent elements, they are linked as 63 * follows: 64 * 65 * +-----------------------+ 66 * | v 67 * +---+ | +---+ +---+ +---+ 68 * | | +-+ | | |<--+ | 69 * | F | | S | ... | P | | L | 70 * | +-->| | | +-+ | | 71 * +---+ +---+ +---+ | +---+ 72 * ^ | 73 * +-----------------------+ 74 * 75 * F, S, P and L are the first, second, penultimate and last node in the 76 * group, respectively (S and P can coincide if the group has size 3.) This 77 * arrangement is used to skip equivalent elements in O(1) when doing lookup, 78 * while preserving O(1) insert/erase. The following invariants identify 79 * special positions (some of the operations have to be carefully implemented 80 * as Xnn is not valid if Xn points to a bucket): 81 * 82 * first node of a bucket: Npnp == N 83 * last node of a bucket: Nnpp == N 84 * first node of a group: Nnp != N && Nnppn == N 85 * second node of a group: Npn != N && Nppnn == N 86 * n-1 node of a group: Nnp != N && Nnnpp == N 87 * last node of a group: Npn != N && Npnnp == N 88 * 89 * The memory overhead is one pointer per bucket plus two pointers per node, 90 * probably unbeatable. The resulting structure is bidirectonally traversable, 91 * though currently we are just providing forward iteration. 92 */ 93 94 template<typename Allocator> 95 struct hashed_index_node_impl; 96 97 /* half-header (only prior() pointer) to use for the bucket array */ 98 99 template<typename Allocator> 100 struct hashed_index_base_node_impl 101 { 102 typedef typename 103 boost::detail::allocator::rebind_to< 104 Allocator,hashed_index_base_node_impl 105 >::type::pointer base_pointer; 106 typedef typename 107 boost::detail::allocator::rebind_to< 108 Allocator,hashed_index_base_node_impl 109 >::type::const_pointer const_base_pointer; 110 typedef typename 111 boost::detail::allocator::rebind_to< 112 Allocator, 113 hashed_index_node_impl<Allocator> 114 >::type::pointer pointer; 115 typedef typename 116 boost::detail::allocator::rebind_to< 117 Allocator, 118 hashed_index_node_impl<Allocator> 119 >::type::const_pointer const_pointer; 120 priorboost::multi_index::detail::hashed_index_base_node_impl121 pointer& prior(){return prior_;} priorboost::multi_index::detail::hashed_index_base_node_impl122 pointer prior()const{return prior_;} 123 124 private: 125 pointer prior_; 126 }; 127 128 /* full header (prior() and next()) for the nodes */ 129 130 template<typename Allocator> 131 struct hashed_index_node_impl:hashed_index_base_node_impl<Allocator> 132 { 133 private: 134 typedef hashed_index_base_node_impl<Allocator> super; 135 136 public: 137 typedef typename super::base_pointer base_pointer; 138 typedef typename super::const_base_pointer const_base_pointer; 139 typedef typename super::pointer pointer; 140 typedef typename super::const_pointer const_pointer; 141 nextboost::multi_index::detail::hashed_index_node_impl142 base_pointer& next(){return next_;} nextboost::multi_index::detail::hashed_index_node_impl143 base_pointer next()const{return next_;} 144 pointer_fromboost::multi_index::detail::hashed_index_node_impl145 static pointer pointer_from(base_pointer x) 146 { 147 return static_cast<pointer>( 148 static_cast<hashed_index_node_impl*>( 149 raw_ptr<super*>(x))); 150 } 151 base_pointer_fromboost::multi_index::detail::hashed_index_node_impl152 static base_pointer base_pointer_from(pointer x) 153 { 154 return static_cast<base_pointer>( 155 raw_ptr<hashed_index_node_impl*>(x)); 156 } 157 158 private: 159 base_pointer next_; 160 }; 161 162 /* Boost.MultiIndex requires machinery to reverse unlink operations. A simple 163 * way to make a pointer-manipulation function undoable is to templatize 164 * its internal pointer assignments with a functor that, besides doing the 165 * assignment, keeps track of the original pointer values and can later undo 166 * the operations in reverse order. 167 */ 168 169 struct default_assigner 170 { operator ()boost::multi_index::detail::default_assigner171 template<typename T> void operator()(T& x,const T& val){x=val;} 172 }; 173 174 template<typename Node> 175 struct unlink_undo_assigner 176 { 177 typedef typename Node::base_pointer base_pointer; 178 typedef typename Node::pointer pointer; 179 unlink_undo_assignerboost::multi_index::detail::unlink_undo_assigner180 unlink_undo_assigner():pointer_track_count(0),base_pointer_track_count(0){} 181 operator ()boost::multi_index::detail::unlink_undo_assigner182 void operator()(pointer& x,pointer val) 183 { 184 pointer_tracks[pointer_track_count].x=&x; 185 pointer_tracks[pointer_track_count++].val=x; 186 x=val; 187 } 188 operator ()boost::multi_index::detail::unlink_undo_assigner189 void operator()(base_pointer& x,base_pointer val) 190 { 191 base_pointer_tracks[base_pointer_track_count].x=&x; 192 base_pointer_tracks[base_pointer_track_count++].val=x; 193 x=val; 194 } 195 operator ()boost::multi_index::detail::unlink_undo_assigner196 void operator()() /* undo op */ 197 { 198 /* in the absence of aliasing, restitution order is immaterial */ 199 200 while(pointer_track_count--){ 201 *(pointer_tracks[pointer_track_count].x)= 202 pointer_tracks[pointer_track_count].val; 203 } 204 while(base_pointer_track_count--){ 205 *(base_pointer_tracks[base_pointer_track_count].x)= 206 base_pointer_tracks[base_pointer_track_count].val; 207 } 208 } 209 210 struct pointer_track {pointer* x; pointer val;}; 211 struct base_pointer_track{base_pointer* x; base_pointer val;}; 212 213 /* We know the maximum number of pointer and base pointer assignments that 214 * the two unlink versions do, so we can statically reserve the needed 215 * storage. 216 */ 217 218 pointer_track pointer_tracks[3]; 219 int pointer_track_count; 220 base_pointer_track base_pointer_tracks[2]; 221 int base_pointer_track_count; 222 }; 223 224 /* algorithmic stuff for unique and non-unique variants */ 225 226 struct hashed_unique_tag{}; 227 struct hashed_non_unique_tag{}; 228 229 template<typename Node,typename Category> 230 struct hashed_index_node_alg; 231 232 template<typename Node> 233 struct hashed_index_node_alg<Node,hashed_unique_tag> 234 { 235 typedef typename Node::base_pointer base_pointer; 236 typedef typename Node::const_base_pointer const_base_pointer; 237 typedef typename Node::pointer pointer; 238 typedef typename Node::const_pointer const_pointer; 239 is_first_of_bucketboost::multi_index::detail::hashed_index_node_alg240 static bool is_first_of_bucket(pointer x) 241 { 242 return x->prior()->next()!=base_pointer_from(x); 243 } 244 afterboost::multi_index::detail::hashed_index_node_alg245 static pointer after(pointer x) 246 { 247 return is_last_of_bucket(x)?x->next()->prior():pointer_from(x->next()); 248 } 249 after_localboost::multi_index::detail::hashed_index_node_alg250 static pointer after_local(pointer x) 251 { 252 return is_last_of_bucket(x)?pointer(0):pointer_from(x->next()); 253 } 254 next_to_inspectboost::multi_index::detail::hashed_index_node_alg255 static pointer next_to_inspect(pointer x) 256 { 257 return is_last_of_bucket(x)?pointer(0):pointer_from(x->next()); 258 } 259 linkboost::multi_index::detail::hashed_index_node_alg260 static void link(pointer x,base_pointer buc,pointer end) 261 { 262 if(buc->prior()==pointer(0)){ /* empty bucket */ 263 x->prior()=end->prior(); 264 x->next()=end->prior()->next(); 265 x->prior()->next()=buc; 266 buc->prior()=x; 267 end->prior()=x; 268 } 269 else{ 270 x->prior()=buc->prior()->prior(); 271 x->next()=base_pointer_from(buc->prior()); 272 buc->prior()=x; 273 x->next()->prior()=x; 274 } 275 } 276 unlinkboost::multi_index::detail::hashed_index_node_alg277 static void unlink(pointer x) 278 { 279 default_assigner assign; 280 unlink(x,assign); 281 } 282 283 typedef unlink_undo_assigner<Node> unlink_undo; 284 285 template<typename Assigner> unlinkboost::multi_index::detail::hashed_index_node_alg286 static void unlink(pointer x,Assigner& assign) 287 { 288 if(is_first_of_bucket(x)){ 289 if(is_last_of_bucket(x)){ 290 assign(x->prior()->next()->prior(),pointer(0)); 291 assign(x->prior()->next(),x->next()); 292 assign(x->next()->prior()->prior(),x->prior()); 293 } 294 else{ 295 assign(x->prior()->next()->prior(),pointer_from(x->next())); 296 assign(x->next()->prior(),x->prior()); 297 } 298 } 299 else if(is_last_of_bucket(x)){ 300 assign(x->prior()->next(),x->next()); 301 assign(x->next()->prior()->prior(),x->prior()); 302 } 303 else{ 304 assign(x->prior()->next(),x->next()); 305 assign(x->next()->prior(),x->prior()); 306 } 307 } 308 309 /* used only at rehashing */ 310 appendboost::multi_index::detail::hashed_index_node_alg311 static void append(pointer x,pointer end) 312 { 313 x->prior()=end->prior(); 314 x->next()=end->prior()->next(); 315 x->prior()->next()=base_pointer_from(x); 316 end->prior()=x; 317 } 318 unlink_lastboost::multi_index::detail::hashed_index_node_alg319 static bool unlink_last(pointer end) 320 { 321 /* returns true iff bucket is emptied */ 322 323 pointer x=end->prior(); 324 if(x->prior()->next()==base_pointer_from(x)){ 325 x->prior()->next()=x->next(); 326 end->prior()=x->prior(); 327 return false; 328 } 329 else{ 330 x->prior()->next()->prior()=pointer(0); 331 x->prior()->next()=x->next(); 332 end->prior()=x->prior(); 333 return true; 334 } 335 } 336 337 private: pointer_fromboost::multi_index::detail::hashed_index_node_alg338 static pointer pointer_from(base_pointer x) 339 { 340 return Node::pointer_from(x); 341 } 342 base_pointer_fromboost::multi_index::detail::hashed_index_node_alg343 static base_pointer base_pointer_from(pointer x) 344 { 345 return Node::base_pointer_from(x); 346 } 347 is_last_of_bucketboost::multi_index::detail::hashed_index_node_alg348 static bool is_last_of_bucket(pointer x) 349 { 350 return x->next()->prior()!=x; 351 } 352 }; 353 354 template<typename Node> 355 struct hashed_index_node_alg<Node,hashed_non_unique_tag> 356 { 357 typedef typename Node::base_pointer base_pointer; 358 typedef typename Node::const_base_pointer const_base_pointer; 359 typedef typename Node::pointer pointer; 360 typedef typename Node::const_pointer const_pointer; 361 is_first_of_bucketboost::multi_index::detail::hashed_index_node_alg362 static bool is_first_of_bucket(pointer x) 363 { 364 return x->prior()->next()->prior()==x; 365 } 366 is_first_of_groupboost::multi_index::detail::hashed_index_node_alg367 static bool is_first_of_group(pointer x) 368 { 369 return 370 x->next()->prior()!=x&& 371 x->next()->prior()->prior()->next()==base_pointer_from(x); 372 } 373 afterboost::multi_index::detail::hashed_index_node_alg374 static pointer after(pointer x) 375 { 376 if(x->next()->prior()==x)return pointer_from(x->next()); 377 if(x->next()->prior()->prior()==x)return x->next()->prior(); 378 if(x->next()->prior()->prior()->next()==base_pointer_from(x)) 379 return pointer_from(x->next()); 380 return pointer_from(x->next())->next()->prior(); 381 } 382 after_localboost::multi_index::detail::hashed_index_node_alg383 static pointer after_local(pointer x) 384 { 385 if(x->next()->prior()==x)return pointer_from(x->next()); 386 if(x->next()->prior()->prior()==x)return pointer(0); 387 if(x->next()->prior()->prior()->next()==base_pointer_from(x)) 388 return pointer_from(x->next()); 389 return pointer_from(x->next())->next()->prior(); 390 } 391 next_to_inspectboost::multi_index::detail::hashed_index_node_alg392 static pointer next_to_inspect(pointer x) 393 { 394 if(x->next()->prior()==x)return pointer_from(x->next()); 395 if(x->next()->prior()->prior()==x)return pointer(0); 396 if(x->next()->prior()->next()->prior()!=x->next()->prior()) 397 return pointer(0); 398 return pointer_from(x->next()->prior()->next()); 399 } 400 linkboost::multi_index::detail::hashed_index_node_alg401 static void link(pointer x,base_pointer buc,pointer end) 402 { 403 if(buc->prior()==pointer(0)){ /* empty bucket */ 404 x->prior()=end->prior(); 405 x->next()=end->prior()->next(); 406 x->prior()->next()=buc; 407 buc->prior()=x; 408 end->prior()=x; 409 } 410 else{ 411 x->prior()=buc->prior()->prior(); 412 x->next()=base_pointer_from(buc->prior()); 413 buc->prior()=x; 414 x->next()->prior()=x; 415 } 416 }; 417 linkboost::multi_index::detail::hashed_index_node_alg418 static void link(pointer x,pointer first,pointer last) 419 { 420 x->prior()=first->prior(); 421 x->next()=base_pointer_from(first); 422 if(is_first_of_bucket(first)){ 423 x->prior()->next()->prior()=x; 424 } 425 else{ 426 x->prior()->next()=base_pointer_from(x); 427 } 428 429 if(first==last){ 430 last->prior()=x; 431 } 432 else if(first->next()==base_pointer_from(last)){ 433 first->prior()=last; 434 first->next()=base_pointer_from(x); 435 } 436 else{ 437 pointer second=pointer_from(first->next()), 438 lastbutone=last->prior(); 439 second->prior()=first; 440 first->prior()=last; 441 lastbutone->next()=base_pointer_from(x); 442 } 443 } 444 unlinkboost::multi_index::detail::hashed_index_node_alg445 static void unlink(pointer x) 446 { 447 default_assigner assign; 448 unlink(x,assign); 449 } 450 451 typedef unlink_undo_assigner<Node> unlink_undo; 452 453 template<typename Assigner> unlinkboost::multi_index::detail::hashed_index_node_alg454 static void unlink(pointer x,Assigner& assign) 455 { 456 if(x->prior()->next()==base_pointer_from(x)){ 457 if(x->next()->prior()==x){ 458 left_unlink(x,assign); 459 right_unlink(x,assign); 460 } 461 else if(x->next()->prior()->prior()==x){ /* last of bucket */ 462 left_unlink(x,assign); 463 right_unlink_last_of_bucket(x,assign); 464 } 465 else if(x->next()->prior()->prior()->next()== 466 base_pointer_from(x)){ /* first of group size */ 467 left_unlink(x,assign); 468 right_unlink_first_of_group(x,assign); 469 } 470 else{ /* n-1 of group */ 471 unlink_last_but_one_of_group(x,assign); 472 } 473 } 474 else if(x->prior()->next()->prior()==x){ /* first of bucket */ 475 if(x->next()->prior()==x){ 476 left_unlink_first_of_bucket(x,assign); 477 right_unlink(x,assign); 478 } 479 else if(x->next()->prior()->prior()==x){ /* last of bucket */ 480 assign(x->prior()->next()->prior(),pointer(0)); 481 assign(x->prior()->next(),x->next()); 482 assign(x->next()->prior()->prior(),x->prior()); 483 } 484 else{ /* first of group */ 485 left_unlink_first_of_bucket(x,assign); 486 right_unlink_first_of_group(x,assign); 487 } 488 } 489 else if(x->next()->prior()->prior()==x){ /* last of group and bucket */ 490 left_unlink_last_of_group(x,assign); 491 right_unlink_last_of_bucket(x,assign); 492 } 493 else if(pointer_from(x->prior()->prior()->next()) 494 ->next()==base_pointer_from(x)){ /* second of group */ 495 unlink_second_of_group(x,assign); 496 } 497 else{ /* last of group, ~(last of bucket) */ 498 left_unlink_last_of_group(x,assign); 499 right_unlink(x,assign); 500 } 501 } 502 503 /* used only at rehashing */ 504 link_rangeboost::multi_index::detail::hashed_index_node_alg505 static void link_range( 506 pointer first,pointer last,base_pointer buc,pointer cend) 507 { 508 if(buc->prior()==pointer(0)){ /* empty bucket */ 509 first->prior()=cend->prior(); 510 last->next()=cend->prior()->next(); 511 first->prior()->next()=buc; 512 buc->prior()=first; 513 cend->prior()=last; 514 } 515 else{ 516 first->prior()=buc->prior()->prior(); 517 last->next()=base_pointer_from(buc->prior()); 518 buc->prior()=first; 519 last->next()->prior()=last; 520 } 521 } 522 append_rangeboost::multi_index::detail::hashed_index_node_alg523 static void append_range(pointer first,pointer last,pointer cend) 524 { 525 first->prior()=cend->prior(); 526 last->next()=cend->prior()->next(); 527 first->prior()->next()=base_pointer_from(first); 528 cend->prior()=last; 529 } 530 unlink_last_groupboost::multi_index::detail::hashed_index_node_alg531 static std::pair<pointer,bool> unlink_last_group(pointer end) 532 { 533 /* returns first of group true iff bucket is emptied */ 534 535 pointer x=end->prior(); 536 if(x->prior()->next()==base_pointer_from(x)){ 537 x->prior()->next()=x->next(); 538 end->prior()=x->prior(); 539 return std::make_pair(x,false); 540 } 541 else if(x->prior()->next()->prior()==x){ 542 x->prior()->next()->prior()=pointer(0); 543 x->prior()->next()=x->next(); 544 end->prior()=x->prior(); 545 return std::make_pair(x,true); 546 } 547 else{ 548 pointer y=pointer_from(x->prior()->next()); 549 550 if(y->prior()->next()==base_pointer_from(y)){ 551 y->prior()->next()=x->next(); 552 end->prior()=y->prior(); 553 return std::make_pair(y,false); 554 } 555 else{ 556 y->prior()->next()->prior()=pointer(0); 557 y->prior()->next()=x->next(); 558 end->prior()=y->prior(); 559 return std::make_pair(y,true); 560 } 561 } 562 } 563 unlink_rangeboost::multi_index::detail::hashed_index_node_alg564 static void unlink_range(pointer first,pointer last) 565 { 566 if(is_first_of_bucket(first)){ 567 if(is_last_of_bucket(last)){ 568 first->prior()->next()->prior()=pointer(0); 569 first->prior()->next()=last->next(); 570 last->next()->prior()->prior()=first->prior(); 571 } 572 else{ 573 first->prior()->next()->prior()=pointer_from(last->next()); 574 last->next()->prior()=first->prior(); 575 } 576 } 577 else if(is_last_of_bucket(last)){ 578 first->prior()->next()=last->next(); 579 last->next()->prior()->prior()=first->prior(); 580 } 581 else{ 582 first->prior()->next()=last->next(); 583 last->next()->prior()=first->prior(); 584 } 585 } 586 587 private: pointer_fromboost::multi_index::detail::hashed_index_node_alg588 static pointer pointer_from(base_pointer x) 589 { 590 return Node::pointer_from(x); 591 } 592 base_pointer_fromboost::multi_index::detail::hashed_index_node_alg593 static base_pointer base_pointer_from(pointer x) 594 { 595 return Node::base_pointer_from(x); 596 } 597 is_last_of_bucketboost::multi_index::detail::hashed_index_node_alg598 static bool is_last_of_bucket(pointer x) 599 { 600 return x->next()->prior()->prior()==x; 601 } 602 603 template<typename Assigner> left_unlinkboost::multi_index::detail::hashed_index_node_alg604 static void left_unlink(pointer x,Assigner& assign) 605 { 606 assign(x->prior()->next(),x->next()); 607 } 608 609 template<typename Assigner> right_unlinkboost::multi_index::detail::hashed_index_node_alg610 static void right_unlink(pointer x,Assigner& assign) 611 { 612 assign(x->next()->prior(),x->prior()); 613 } 614 615 template<typename Assigner> left_unlink_first_of_bucketboost::multi_index::detail::hashed_index_node_alg616 static void left_unlink_first_of_bucket(pointer x,Assigner& assign) 617 { 618 assign(x->prior()->next()->prior(),pointer_from(x->next())); 619 } 620 621 template<typename Assigner> right_unlink_last_of_bucketboost::multi_index::detail::hashed_index_node_alg622 static void right_unlink_last_of_bucket(pointer x,Assigner& assign) 623 { 624 assign(x->next()->prior()->prior(),x->prior()); 625 } 626 627 template<typename Assigner> right_unlink_first_of_groupboost::multi_index::detail::hashed_index_node_alg628 static void right_unlink_first_of_group(pointer x,Assigner& assign) 629 { 630 pointer second=pointer_from(x->next()), 631 last=second->prior(), 632 lastbutone=last->prior(); 633 if(second==lastbutone){ 634 assign(second->next(),base_pointer_from(last)); 635 assign(second->prior(),x->prior()); 636 } 637 else{ 638 assign(lastbutone->next(),base_pointer_from(second)); 639 assign(second->next()->prior(),last); 640 assign(second->prior(),x->prior()); 641 } 642 } 643 644 template<typename Assigner> left_unlink_last_of_groupboost::multi_index::detail::hashed_index_node_alg645 static void left_unlink_last_of_group(pointer x,Assigner& assign) 646 { 647 pointer lastbutone=x->prior(), 648 first=pointer_from(lastbutone->next()), 649 second=pointer_from(first->next()); 650 if(lastbutone==second){ 651 assign(lastbutone->prior(),first); 652 assign(lastbutone->next(),x->next()); 653 } 654 else{ 655 assign(second->prior(),lastbutone); 656 assign(lastbutone->prior()->next(),base_pointer_from(first)); 657 assign(lastbutone->next(),x->next()); 658 } 659 } 660 661 template<typename Assigner> unlink_last_but_one_of_groupboost::multi_index::detail::hashed_index_node_alg662 static void unlink_last_but_one_of_group(pointer x,Assigner& assign) 663 { 664 pointer first=pointer_from(x->next()), 665 second=pointer_from(first->next()), 666 last=second->prior(); 667 if(second==x){ 668 assign(last->prior(),first); 669 assign(first->next(),base_pointer_from(last)); 670 } 671 else{ 672 assign(last->prior(),x->prior()); 673 assign(x->prior()->next(),base_pointer_from(first)); 674 } 675 } 676 677 template<typename Assigner> unlink_second_of_groupboost::multi_index::detail::hashed_index_node_alg678 static void unlink_second_of_group(pointer x,Assigner& assign) 679 { 680 pointer last=x->prior(), 681 lastbutone=last->prior(), 682 first=pointer_from(lastbutone->next()); 683 if(lastbutone==x){ 684 assign(first->next(),base_pointer_from(last)); 685 assign(last->prior(),first); 686 } 687 else{ 688 assign(first->next(),x->next()); 689 assign(x->next()->prior(),last); 690 } 691 } 692 }; 693 694 template<typename Super> 695 struct hashed_index_node_trampoline: 696 hashed_index_node_impl< 697 typename boost::detail::allocator::rebind_to< 698 typename Super::allocator_type, 699 char 700 >::type 701 > 702 { 703 typedef typename boost::detail::allocator::rebind_to< 704 typename Super::allocator_type, 705 char 706 >::type impl_allocator_type; 707 typedef hashed_index_node_impl<impl_allocator_type> impl_type; 708 }; 709 710 template<typename Super,typename Category> 711 struct hashed_index_node: 712 Super,hashed_index_node_trampoline<Super> 713 { 714 private: 715 typedef hashed_index_node_trampoline<Super> trampoline; 716 717 public: 718 typedef typename trampoline::impl_type impl_type; 719 typedef hashed_index_node_alg< 720 impl_type,Category> node_alg; 721 typedef typename trampoline::base_pointer impl_base_pointer; 722 typedef typename trampoline::const_base_pointer const_impl_base_pointer; 723 typedef typename trampoline::pointer impl_pointer; 724 typedef typename trampoline::const_pointer const_impl_pointer; 725 priorboost::multi_index::detail::hashed_index_node726 impl_pointer& prior(){return trampoline::prior();} priorboost::multi_index::detail::hashed_index_node727 impl_pointer prior()const{return trampoline::prior();} nextboost::multi_index::detail::hashed_index_node728 impl_base_pointer& next(){return trampoline::next();} nextboost::multi_index::detail::hashed_index_node729 impl_base_pointer next()const{return trampoline::next();} 730 implboost::multi_index::detail::hashed_index_node731 impl_pointer impl() 732 { 733 return static_cast<impl_pointer>( 734 static_cast<impl_type*>(static_cast<trampoline*>(this))); 735 } 736 implboost::multi_index::detail::hashed_index_node737 const_impl_pointer impl()const 738 { 739 return static_cast<const_impl_pointer>( 740 static_cast<const impl_type*>(static_cast<const trampoline*>(this))); 741 } 742 from_implboost::multi_index::detail::hashed_index_node743 static hashed_index_node* from_impl(impl_pointer x) 744 { 745 return 746 static_cast<hashed_index_node*>( 747 static_cast<trampoline*>( 748 raw_ptr<impl_type*>(x))); 749 } 750 from_implboost::multi_index::detail::hashed_index_node751 static const hashed_index_node* from_impl(const_impl_pointer x) 752 { 753 return 754 static_cast<const hashed_index_node*>( 755 static_cast<const trampoline*>( 756 raw_ptr<const impl_type*>(x))); 757 } 758 759 /* interoperability with hashed_index_iterator */ 760 incrementboost::multi_index::detail::hashed_index_node761 static void increment(hashed_index_node*& x) 762 { 763 x=from_impl(node_alg::after(x->impl())); 764 } 765 increment_localboost::multi_index::detail::hashed_index_node766 static void increment_local(hashed_index_node*& x) 767 { 768 x=from_impl(node_alg::after_local(x->impl())); 769 } 770 }; 771 772 } /* namespace multi_index::detail */ 773 774 } /* namespace multi_index */ 775 776 } /* namespace boost */ 777 778 #endif 779