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 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/multi_index/detail/allocator_traits.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 rebind_alloc_for< 103 Allocator,hashed_index_base_node_impl 104 >::type base_allocator; 105 typedef typename rebind_alloc_for< 106 Allocator,hashed_index_node_impl<Allocator> 107 >::type node_allocator; 108 typedef allocator_traits<base_allocator> base_alloc_traits; 109 typedef allocator_traits<node_allocator> node_alloc_traits; 110 typedef typename base_alloc_traits::pointer base_pointer; 111 typedef typename base_alloc_traits::const_pointer const_base_pointer; 112 typedef typename node_alloc_traits::pointer pointer; 113 typedef typename node_alloc_traits::const_pointer const_pointer; 114 typedef typename node_alloc_traits::difference_type difference_type; 115 priorboost::multi_index::detail::hashed_index_base_node_impl116 pointer& prior(){return prior_;} priorboost::multi_index::detail::hashed_index_base_node_impl117 pointer prior()const{return prior_;} 118 119 private: 120 pointer prior_; 121 }; 122 123 /* full header (prior() and next()) for the nodes */ 124 125 template<typename Allocator> 126 struct hashed_index_node_impl:hashed_index_base_node_impl<Allocator> 127 { 128 private: 129 typedef hashed_index_base_node_impl<Allocator> super; 130 131 public: 132 typedef typename super::base_pointer base_pointer; 133 typedef typename super::const_base_pointer const_base_pointer; 134 typedef typename super::pointer pointer; 135 typedef typename super::const_pointer const_pointer; 136 nextboost::multi_index::detail::hashed_index_node_impl137 base_pointer& next(){return next_;} nextboost::multi_index::detail::hashed_index_node_impl138 base_pointer next()const{return next_;} 139 pointer_fromboost::multi_index::detail::hashed_index_node_impl140 static pointer pointer_from(base_pointer x) 141 { 142 return static_cast<pointer>( 143 static_cast<hashed_index_node_impl*>( 144 raw_ptr<super*>(x))); 145 } 146 base_pointer_fromboost::multi_index::detail::hashed_index_node_impl147 static base_pointer base_pointer_from(pointer x) 148 { 149 return static_cast<base_pointer>( 150 raw_ptr<hashed_index_node_impl*>(x)); 151 } 152 153 private: 154 base_pointer next_; 155 }; 156 157 /* Boost.MultiIndex requires machinery to reverse unlink operations. A simple 158 * way to make a pointer-manipulation function undoable is to templatize 159 * its internal pointer assignments with a functor that, besides doing the 160 * assignment, keeps track of the original pointer values and can later undo 161 * the operations in reverse order. 162 */ 163 164 struct default_assigner 165 { operator ()boost::multi_index::detail::default_assigner166 template<typename T> void operator()(T& x,const T& val){x=val;} 167 }; 168 169 template<typename Node> 170 struct unlink_undo_assigner 171 { 172 typedef typename Node::base_pointer base_pointer; 173 typedef typename Node::pointer pointer; 174 unlink_undo_assignerboost::multi_index::detail::unlink_undo_assigner175 unlink_undo_assigner():pointer_track_count(0),base_pointer_track_count(0){} 176 operator ()boost::multi_index::detail::unlink_undo_assigner177 void operator()(pointer& x,pointer val) 178 { 179 pointer_tracks[pointer_track_count].x=&x; 180 pointer_tracks[pointer_track_count++].val=x; 181 x=val; 182 } 183 operator ()boost::multi_index::detail::unlink_undo_assigner184 void operator()(base_pointer& x,base_pointer val) 185 { 186 base_pointer_tracks[base_pointer_track_count].x=&x; 187 base_pointer_tracks[base_pointer_track_count++].val=x; 188 x=val; 189 } 190 operator ()boost::multi_index::detail::unlink_undo_assigner191 void operator()() /* undo op */ 192 { 193 /* in the absence of aliasing, restitution order is immaterial */ 194 195 while(pointer_track_count--){ 196 *(pointer_tracks[pointer_track_count].x)= 197 pointer_tracks[pointer_track_count].val; 198 } 199 while(base_pointer_track_count--){ 200 *(base_pointer_tracks[base_pointer_track_count].x)= 201 base_pointer_tracks[base_pointer_track_count].val; 202 } 203 } 204 205 struct pointer_track {pointer* x; pointer val;}; 206 struct base_pointer_track{base_pointer* x; base_pointer val;}; 207 208 /* We know the maximum number of pointer and base pointer assignments that 209 * the two unlink versions do, so we can statically reserve the needed 210 * storage. 211 */ 212 213 pointer_track pointer_tracks[3]; 214 int pointer_track_count; 215 base_pointer_track base_pointer_tracks[2]; 216 int base_pointer_track_count; 217 }; 218 219 /* algorithmic stuff for unique and non-unique variants */ 220 221 struct hashed_unique_tag{}; 222 struct hashed_non_unique_tag{}; 223 224 template<typename Node,typename Category> 225 struct hashed_index_node_alg; 226 227 template<typename Node> 228 struct hashed_index_node_alg<Node,hashed_unique_tag> 229 { 230 typedef typename Node::base_pointer base_pointer; 231 typedef typename Node::const_base_pointer const_base_pointer; 232 typedef typename Node::pointer pointer; 233 typedef typename Node::const_pointer const_pointer; 234 is_first_of_bucketboost::multi_index::detail::hashed_index_node_alg235 static bool is_first_of_bucket(pointer x) 236 { 237 return x->prior()->next()!=base_pointer_from(x); 238 } 239 afterboost::multi_index::detail::hashed_index_node_alg240 static pointer after(pointer x) 241 { 242 return is_last_of_bucket(x)?x->next()->prior():pointer_from(x->next()); 243 } 244 after_localboost::multi_index::detail::hashed_index_node_alg245 static pointer after_local(pointer x) 246 { 247 return is_last_of_bucket(x)?pointer(0):pointer_from(x->next()); 248 } 249 next_to_inspectboost::multi_index::detail::hashed_index_node_alg250 static pointer next_to_inspect(pointer x) 251 { 252 return is_last_of_bucket(x)?pointer(0):pointer_from(x->next()); 253 } 254 linkboost::multi_index::detail::hashed_index_node_alg255 static void link(pointer x,base_pointer buc,pointer end) 256 { 257 if(buc->prior()==pointer(0)){ /* empty bucket */ 258 x->prior()=end->prior(); 259 x->next()=end->prior()->next(); 260 x->prior()->next()=buc; 261 buc->prior()=x; 262 end->prior()=x; 263 } 264 else{ 265 x->prior()=buc->prior()->prior(); 266 x->next()=base_pointer_from(buc->prior()); 267 buc->prior()=x; 268 x->next()->prior()=x; 269 } 270 } 271 unlinkboost::multi_index::detail::hashed_index_node_alg272 static void unlink(pointer x) 273 { 274 default_assigner assign; 275 unlink(x,assign); 276 } 277 278 typedef unlink_undo_assigner<Node> unlink_undo; 279 280 template<typename Assigner> unlinkboost::multi_index::detail::hashed_index_node_alg281 static void unlink(pointer x,Assigner& assign) 282 { 283 if(is_first_of_bucket(x)){ 284 if(is_last_of_bucket(x)){ 285 assign(x->prior()->next()->prior(),pointer(0)); 286 assign(x->prior()->next(),x->next()); 287 assign(x->next()->prior()->prior(),x->prior()); 288 } 289 else{ 290 assign(x->prior()->next()->prior(),pointer_from(x->next())); 291 assign(x->next()->prior(),x->prior()); 292 } 293 } 294 else if(is_last_of_bucket(x)){ 295 assign(x->prior()->next(),x->next()); 296 assign(x->next()->prior()->prior(),x->prior()); 297 } 298 else{ 299 assign(x->prior()->next(),x->next()); 300 assign(x->next()->prior(),x->prior()); 301 } 302 } 303 304 /* used only at rehashing */ 305 appendboost::multi_index::detail::hashed_index_node_alg306 static void append(pointer x,pointer end) 307 { 308 x->prior()=end->prior(); 309 x->next()=end->prior()->next(); 310 x->prior()->next()=base_pointer_from(x); 311 end->prior()=x; 312 } 313 unlink_lastboost::multi_index::detail::hashed_index_node_alg314 static bool unlink_last(pointer end) 315 { 316 /* returns true iff bucket is emptied */ 317 318 pointer x=end->prior(); 319 if(x->prior()->next()==base_pointer_from(x)){ 320 x->prior()->next()=x->next(); 321 end->prior()=x->prior(); 322 return false; 323 } 324 else{ 325 x->prior()->next()->prior()=pointer(0); 326 x->prior()->next()=x->next(); 327 end->prior()=x->prior(); 328 return true; 329 } 330 } 331 332 private: pointer_fromboost::multi_index::detail::hashed_index_node_alg333 static pointer pointer_from(base_pointer x) 334 { 335 return Node::pointer_from(x); 336 } 337 base_pointer_fromboost::multi_index::detail::hashed_index_node_alg338 static base_pointer base_pointer_from(pointer x) 339 { 340 return Node::base_pointer_from(x); 341 } 342 is_last_of_bucketboost::multi_index::detail::hashed_index_node_alg343 static bool is_last_of_bucket(pointer x) 344 { 345 return x->next()->prior()!=x; 346 } 347 }; 348 349 template<typename Node> 350 struct hashed_index_node_alg<Node,hashed_non_unique_tag> 351 { 352 typedef typename Node::base_pointer base_pointer; 353 typedef typename Node::const_base_pointer const_base_pointer; 354 typedef typename Node::pointer pointer; 355 typedef typename Node::const_pointer const_pointer; 356 is_first_of_bucketboost::multi_index::detail::hashed_index_node_alg357 static bool is_first_of_bucket(pointer x) 358 { 359 return x->prior()->next()->prior()==x; 360 } 361 is_first_of_groupboost::multi_index::detail::hashed_index_node_alg362 static bool is_first_of_group(pointer x) 363 { 364 return 365 x->next()->prior()!=x&& 366 x->next()->prior()->prior()->next()==base_pointer_from(x); 367 } 368 afterboost::multi_index::detail::hashed_index_node_alg369 static pointer after(pointer x) 370 { 371 if(x->next()->prior()==x)return pointer_from(x->next()); 372 if(x->next()->prior()->prior()==x)return x->next()->prior(); 373 if(x->next()->prior()->prior()->next()==base_pointer_from(x)) 374 return pointer_from(x->next()); 375 return pointer_from(x->next())->next()->prior(); 376 } 377 after_localboost::multi_index::detail::hashed_index_node_alg378 static pointer after_local(pointer x) 379 { 380 if(x->next()->prior()==x)return pointer_from(x->next()); 381 if(x->next()->prior()->prior()==x)return pointer(0); 382 if(x->next()->prior()->prior()->next()==base_pointer_from(x)) 383 return pointer_from(x->next()); 384 return pointer_from(x->next())->next()->prior(); 385 } 386 next_to_inspectboost::multi_index::detail::hashed_index_node_alg387 static pointer next_to_inspect(pointer x) 388 { 389 if(x->next()->prior()==x)return pointer_from(x->next()); 390 if(x->next()->prior()->prior()==x)return pointer(0); 391 if(x->next()->prior()->next()->prior()!=x->next()->prior()) 392 return pointer(0); 393 return pointer_from(x->next()->prior()->next()); 394 } 395 linkboost::multi_index::detail::hashed_index_node_alg396 static void link(pointer x,base_pointer buc,pointer end) 397 { 398 if(buc->prior()==pointer(0)){ /* empty bucket */ 399 x->prior()=end->prior(); 400 x->next()=end->prior()->next(); 401 x->prior()->next()=buc; 402 buc->prior()=x; 403 end->prior()=x; 404 } 405 else{ 406 x->prior()=buc->prior()->prior(); 407 x->next()=base_pointer_from(buc->prior()); 408 buc->prior()=x; 409 x->next()->prior()=x; 410 } 411 } 412 linkboost::multi_index::detail::hashed_index_node_alg413 static void link(pointer x,pointer first,pointer last) 414 { 415 x->prior()=first->prior(); 416 x->next()=base_pointer_from(first); 417 if(is_first_of_bucket(first)){ 418 x->prior()->next()->prior()=x; 419 } 420 else{ 421 x->prior()->next()=base_pointer_from(x); 422 } 423 424 if(first==last){ 425 last->prior()=x; 426 } 427 else if(first->next()==base_pointer_from(last)){ 428 first->prior()=last; 429 first->next()=base_pointer_from(x); 430 } 431 else{ 432 pointer second=pointer_from(first->next()), 433 lastbutone=last->prior(); 434 second->prior()=first; 435 first->prior()=last; 436 lastbutone->next()=base_pointer_from(x); 437 } 438 } 439 unlinkboost::multi_index::detail::hashed_index_node_alg440 static void unlink(pointer x) 441 { 442 default_assigner assign; 443 unlink(x,assign); 444 } 445 446 typedef unlink_undo_assigner<Node> unlink_undo; 447 448 template<typename Assigner> unlinkboost::multi_index::detail::hashed_index_node_alg449 static void unlink(pointer x,Assigner& assign) 450 { 451 if(x->prior()->next()==base_pointer_from(x)){ 452 if(x->next()->prior()==x){ 453 left_unlink(x,assign); 454 right_unlink(x,assign); 455 } 456 else if(x->next()->prior()->prior()==x){ /* last of bucket */ 457 left_unlink(x,assign); 458 right_unlink_last_of_bucket(x,assign); 459 } 460 else if(x->next()->prior()->prior()->next()== 461 base_pointer_from(x)){ /* first of group size */ 462 left_unlink(x,assign); 463 right_unlink_first_of_group(x,assign); 464 } 465 else{ /* n-1 of group */ 466 unlink_last_but_one_of_group(x,assign); 467 } 468 } 469 else if(x->prior()->next()->prior()==x){ /* first of bucket */ 470 if(x->next()->prior()==x){ 471 left_unlink_first_of_bucket(x,assign); 472 right_unlink(x,assign); 473 } 474 else if(x->next()->prior()->prior()==x){ /* last of bucket */ 475 assign(x->prior()->next()->prior(),pointer(0)); 476 assign(x->prior()->next(),x->next()); 477 assign(x->next()->prior()->prior(),x->prior()); 478 } 479 else{ /* first of group */ 480 left_unlink_first_of_bucket(x,assign); 481 right_unlink_first_of_group(x,assign); 482 } 483 } 484 else if(x->next()->prior()->prior()==x){ /* last of group and bucket */ 485 left_unlink_last_of_group(x,assign); 486 right_unlink_last_of_bucket(x,assign); 487 } 488 else if(pointer_from(x->prior()->prior()->next()) 489 ->next()==base_pointer_from(x)){ /* second of group */ 490 unlink_second_of_group(x,assign); 491 } 492 else{ /* last of group, ~(last of bucket) */ 493 left_unlink_last_of_group(x,assign); 494 right_unlink(x,assign); 495 } 496 } 497 498 /* used only at rehashing */ 499 link_rangeboost::multi_index::detail::hashed_index_node_alg500 static void link_range( 501 pointer first,pointer last,base_pointer buc,pointer cend) 502 { 503 if(buc->prior()==pointer(0)){ /* empty bucket */ 504 first->prior()=cend->prior(); 505 last->next()=cend->prior()->next(); 506 first->prior()->next()=buc; 507 buc->prior()=first; 508 cend->prior()=last; 509 } 510 else{ 511 first->prior()=buc->prior()->prior(); 512 last->next()=base_pointer_from(buc->prior()); 513 buc->prior()=first; 514 last->next()->prior()=last; 515 } 516 } 517 append_rangeboost::multi_index::detail::hashed_index_node_alg518 static void append_range(pointer first,pointer last,pointer cend) 519 { 520 first->prior()=cend->prior(); 521 last->next()=cend->prior()->next(); 522 first->prior()->next()=base_pointer_from(first); 523 cend->prior()=last; 524 } 525 unlink_last_groupboost::multi_index::detail::hashed_index_node_alg526 static std::pair<pointer,bool> unlink_last_group(pointer end) 527 { 528 /* returns first of group true iff bucket is emptied */ 529 530 pointer x=end->prior(); 531 if(x->prior()->next()==base_pointer_from(x)){ 532 x->prior()->next()=x->next(); 533 end->prior()=x->prior(); 534 return std::make_pair(x,false); 535 } 536 else if(x->prior()->next()->prior()==x){ 537 x->prior()->next()->prior()=pointer(0); 538 x->prior()->next()=x->next(); 539 end->prior()=x->prior(); 540 return std::make_pair(x,true); 541 } 542 else{ 543 pointer y=pointer_from(x->prior()->next()); 544 545 if(y->prior()->next()==base_pointer_from(y)){ 546 y->prior()->next()=x->next(); 547 end->prior()=y->prior(); 548 return std::make_pair(y,false); 549 } 550 else{ 551 y->prior()->next()->prior()=pointer(0); 552 y->prior()->next()=x->next(); 553 end->prior()=y->prior(); 554 return std::make_pair(y,true); 555 } 556 } 557 } 558 unlink_rangeboost::multi_index::detail::hashed_index_node_alg559 static void unlink_range(pointer first,pointer last) 560 { 561 if(is_first_of_bucket(first)){ 562 if(is_last_of_bucket(last)){ 563 first->prior()->next()->prior()=pointer(0); 564 first->prior()->next()=last->next(); 565 last->next()->prior()->prior()=first->prior(); 566 } 567 else{ 568 first->prior()->next()->prior()=pointer_from(last->next()); 569 last->next()->prior()=first->prior(); 570 } 571 } 572 else if(is_last_of_bucket(last)){ 573 first->prior()->next()=last->next(); 574 last->next()->prior()->prior()=first->prior(); 575 } 576 else{ 577 first->prior()->next()=last->next(); 578 last->next()->prior()=first->prior(); 579 } 580 } 581 582 private: pointer_fromboost::multi_index::detail::hashed_index_node_alg583 static pointer pointer_from(base_pointer x) 584 { 585 return Node::pointer_from(x); 586 } 587 base_pointer_fromboost::multi_index::detail::hashed_index_node_alg588 static base_pointer base_pointer_from(pointer x) 589 { 590 return Node::base_pointer_from(x); 591 } 592 is_last_of_bucketboost::multi_index::detail::hashed_index_node_alg593 static bool is_last_of_bucket(pointer x) 594 { 595 return x->next()->prior()->prior()==x; 596 } 597 598 template<typename Assigner> left_unlinkboost::multi_index::detail::hashed_index_node_alg599 static void left_unlink(pointer x,Assigner& assign) 600 { 601 assign(x->prior()->next(),x->next()); 602 } 603 604 template<typename Assigner> right_unlinkboost::multi_index::detail::hashed_index_node_alg605 static void right_unlink(pointer x,Assigner& assign) 606 { 607 assign(x->next()->prior(),x->prior()); 608 } 609 610 template<typename Assigner> left_unlink_first_of_bucketboost::multi_index::detail::hashed_index_node_alg611 static void left_unlink_first_of_bucket(pointer x,Assigner& assign) 612 { 613 assign(x->prior()->next()->prior(),pointer_from(x->next())); 614 } 615 616 template<typename Assigner> right_unlink_last_of_bucketboost::multi_index::detail::hashed_index_node_alg617 static void right_unlink_last_of_bucket(pointer x,Assigner& assign) 618 { 619 assign(x->next()->prior()->prior(),x->prior()); 620 } 621 622 template<typename Assigner> right_unlink_first_of_groupboost::multi_index::detail::hashed_index_node_alg623 static void right_unlink_first_of_group(pointer x,Assigner& assign) 624 { 625 pointer second=pointer_from(x->next()), 626 last=second->prior(), 627 lastbutone=last->prior(); 628 if(second==lastbutone){ 629 assign(second->next(),base_pointer_from(last)); 630 assign(second->prior(),x->prior()); 631 } 632 else{ 633 assign(lastbutone->next(),base_pointer_from(second)); 634 assign(second->next()->prior(),last); 635 assign(second->prior(),x->prior()); 636 } 637 } 638 639 template<typename Assigner> left_unlink_last_of_groupboost::multi_index::detail::hashed_index_node_alg640 static void left_unlink_last_of_group(pointer x,Assigner& assign) 641 { 642 pointer lastbutone=x->prior(), 643 first=pointer_from(lastbutone->next()), 644 second=pointer_from(first->next()); 645 if(lastbutone==second){ 646 assign(lastbutone->prior(),first); 647 assign(lastbutone->next(),x->next()); 648 } 649 else{ 650 assign(second->prior(),lastbutone); 651 assign(lastbutone->prior()->next(),base_pointer_from(first)); 652 assign(lastbutone->next(),x->next()); 653 } 654 } 655 656 template<typename Assigner> unlink_last_but_one_of_groupboost::multi_index::detail::hashed_index_node_alg657 static void unlink_last_but_one_of_group(pointer x,Assigner& assign) 658 { 659 pointer first=pointer_from(x->next()), 660 second=pointer_from(first->next()), 661 last=second->prior(); 662 if(second==x){ 663 assign(last->prior(),first); 664 assign(first->next(),base_pointer_from(last)); 665 } 666 else{ 667 assign(last->prior(),x->prior()); 668 assign(x->prior()->next(),base_pointer_from(first)); 669 } 670 } 671 672 template<typename Assigner> unlink_second_of_groupboost::multi_index::detail::hashed_index_node_alg673 static void unlink_second_of_group(pointer x,Assigner& assign) 674 { 675 pointer last=x->prior(), 676 lastbutone=last->prior(), 677 first=pointer_from(lastbutone->next()); 678 if(lastbutone==x){ 679 assign(first->next(),base_pointer_from(last)); 680 assign(last->prior(),first); 681 } 682 else{ 683 assign(first->next(),x->next()); 684 assign(x->next()->prior(),last); 685 } 686 } 687 }; 688 689 template<typename Super> 690 struct hashed_index_node_trampoline: 691 hashed_index_node_impl< 692 typename rebind_alloc_for< 693 typename Super::allocator_type,char 694 >::type 695 > 696 { 697 typedef typename rebind_alloc_for< 698 typename Super::allocator_type,char 699 >::type impl_allocator_type; 700 typedef hashed_index_node_impl<impl_allocator_type> impl_type; 701 }; 702 703 template<typename Super> 704 struct hashed_index_node: 705 Super,hashed_index_node_trampoline<Super> 706 { 707 private: 708 typedef hashed_index_node_trampoline<Super> trampoline; 709 710 public: 711 typedef typename trampoline::impl_type impl_type; 712 typedef typename trampoline::base_pointer impl_base_pointer; 713 typedef typename trampoline::const_base_pointer const_impl_base_pointer; 714 typedef typename trampoline::pointer impl_pointer; 715 typedef typename trampoline::const_pointer const_impl_pointer; 716 typedef typename trampoline::difference_type difference_type; 717 718 template<typename Category> 719 struct node_alg{ 720 typedef hashed_index_node_alg<impl_type,Category> type; 721 }; 722 priorboost::multi_index::detail::hashed_index_node723 impl_pointer& prior(){return trampoline::prior();} priorboost::multi_index::detail::hashed_index_node724 impl_pointer prior()const{return trampoline::prior();} nextboost::multi_index::detail::hashed_index_node725 impl_base_pointer& next(){return trampoline::next();} nextboost::multi_index::detail::hashed_index_node726 impl_base_pointer next()const{return trampoline::next();} 727 implboost::multi_index::detail::hashed_index_node728 impl_pointer impl() 729 { 730 return static_cast<impl_pointer>( 731 static_cast<impl_type*>(static_cast<trampoline*>(this))); 732 } 733 implboost::multi_index::detail::hashed_index_node734 const_impl_pointer impl()const 735 { 736 return static_cast<const_impl_pointer>( 737 static_cast<const impl_type*>(static_cast<const trampoline*>(this))); 738 } 739 from_implboost::multi_index::detail::hashed_index_node740 static hashed_index_node* from_impl(impl_pointer x) 741 { 742 return 743 static_cast<hashed_index_node*>( 744 static_cast<trampoline*>( 745 raw_ptr<impl_type*>(x))); 746 } 747 from_implboost::multi_index::detail::hashed_index_node748 static const hashed_index_node* from_impl(const_impl_pointer x) 749 { 750 return 751 static_cast<const hashed_index_node*>( 752 static_cast<const trampoline*>( 753 raw_ptr<const impl_type*>(x))); 754 } 755 756 /* interoperability with hashed_index_iterator */ 757 758 template<typename Category> incrementboost::multi_index::detail::hashed_index_node759 static void increment(hashed_index_node*& x) 760 { 761 x=from_impl(node_alg<Category>::type::after(x->impl())); 762 } 763 764 template<typename Category> increment_localboost::multi_index::detail::hashed_index_node765 static void increment_local(hashed_index_node*& x) 766 { 767 x=from_impl(node_alg<Category>::type::after_local(x->impl())); 768 } 769 }; 770 771 } /* namespace multi_index::detail */ 772 773 } /* namespace multi_index */ 774 775 } /* namespace boost */ 776 777 #endif 778