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
21namespace boost{
22
23namespace multi_index{
24
25namespace 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
94template<typename Allocator>
95struct hashed_index_node_impl;
96
97/* half-header (only prior() pointer) to use for the bucket array */
98
99template<typename Allocator>
100struct 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
116 pointer& prior(){return prior_;}
117 pointer prior()const{return prior_;}
118
119private:
120 pointer prior_;
121};
122
123/* full header (prior() and next()) for the nodes */
124
125template<typename Allocator>
126struct hashed_index_node_impl:hashed_index_base_node_impl<Allocator>
127{
128private:
129 typedef hashed_index_base_node_impl<Allocator> super;
130
131public:
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
137 base_pointer& next(){return next_;}
138 base_pointer next()const{return next_;}
139
140 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
147 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
153private:
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
164struct default_assigner
165{
166 template<typename T> void operator()(T& x,const T& val){x=val;}
167};
168
169template<typename Node>
170struct unlink_undo_assigner
171{
172 typedef typename Node::base_pointer base_pointer;
173 typedef typename Node::pointer pointer;
174
175 unlink_undo_assigner():pointer_track_count(0),base_pointer_track_count(0){}
176
177 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
184 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
191 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
221struct hashed_unique_tag{};
222struct hashed_non_unique_tag{};
223
224template<typename Node,typename Category>
225struct hashed_index_node_alg;
226
227template<typename Node>
228struct 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
235 static bool is_first_of_bucket(pointer x)
236 {
237 return x->prior()->next()!=base_pointer_from(x);
238 }
239
240 static pointer after(pointer x)
241 {
242 return is_last_of_bucket(x)?x->next()->prior():pointer_from(x: x->next());
243 }
244
245 static pointer after_local(pointer x)
246 {
247 return is_last_of_bucket(x)?pointer(0):pointer_from(x: x->next());
248 }
249
250 static pointer next_to_inspect(pointer x)
251 {
252 return is_last_of_bucket(x)?pointer(0):pointer_from(x: x->next());
253 }
254
255 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(x: buc->prior());
267 buc->prior()=x;
268 x->next()->prior()=x;
269 }
270 }
271
272 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>
281 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: 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
306 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
314 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
332private:
333 static pointer pointer_from(base_pointer x)
334 {
335 return Node::pointer_from(x);
336 }
337
338 static base_pointer base_pointer_from(pointer x)
339 {
340 return Node::base_pointer_from(x);
341 }
342
343 static bool is_last_of_bucket(pointer x)
344 {
345 return x->next()->prior()!=x;
346 }
347};
348
349template<typename Node>
350struct 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
357 static bool is_first_of_bucket(pointer x)
358 {
359 return x->prior()->next()->prior()==x;
360 }
361
362 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
369 static pointer after(pointer x)
370 {
371 if(x->next()->prior()==x)return pointer_from(x: 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: x->next());
375 return pointer_from(x: x->next())->next()->prior();
376 }
377
378 static pointer after_local(pointer x)
379 {
380 if(x->next()->prior()==x)return pointer_from(x: 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: x->next());
384 return pointer_from(x: x->next())->next()->prior();
385 }
386
387 static pointer next_to_inspect(pointer x)
388 {
389 if(x->next()->prior()==x)return pointer_from(x: 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: x->next()->prior()->next());
394 }
395
396 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(x: buc->prior());
408 buc->prior()=x;
409 x->next()->prior()=x;
410 }
411 }
412
413 static void link(pointer x,pointer first,pointer last)
414 {
415 x->prior()=first->prior();
416 x->next()=base_pointer_from(x: first);
417 if(is_first_of_bucket(x: 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(x: last)){
428 first->prior()=last;
429 first->next()=base_pointer_from(x);
430 }
431 else{
432 pointer second=pointer_from(x: first->next()),
433 lastbutone=last->prior();
434 second->prior()=first;
435 first->prior()=last;
436 lastbutone->next()=base_pointer_from(x);
437 }
438 }
439
440 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>
449 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: 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
500 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(x: buc->prior());
513 buc->prior()=first;
514 last->next()->prior()=last;
515 }
516 }
517
518 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(x: first);
523 cend->prior()=last;
524 }
525
526 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: x->prior()->next());
544
545 if(y->prior()->next()==base_pointer_from(x: 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
559 static void unlink_range(pointer first,pointer last)
560 {
561 if(is_first_of_bucket(x: first)){
562 if(is_last_of_bucket(x: 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(x: last->next());
569 last->next()->prior()=first->prior();
570 }
571 }
572 else if(is_last_of_bucket(x: 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
582private:
583 static pointer pointer_from(base_pointer x)
584 {
585 return Node::pointer_from(x);
586 }
587
588 static base_pointer base_pointer_from(pointer x)
589 {
590 return Node::base_pointer_from(x);
591 }
592
593 static bool is_last_of_bucket(pointer x)
594 {
595 return x->next()->prior()->prior()==x;
596 }
597
598 template<typename Assigner>
599 static void left_unlink(pointer x,Assigner& assign)
600 {
601 assign(x->prior()->next(),x->next());
602 }
603
604 template<typename Assigner>
605 static void right_unlink(pointer x,Assigner& assign)
606 {
607 assign(x->next()->prior(),x->prior());
608 }
609
610 template<typename Assigner>
611 static void left_unlink_first_of_bucket(pointer x,Assigner& assign)
612 {
613 assign(x->prior()->next()->prior(),pointer_from(x: x->next()));
614 }
615
616 template<typename Assigner>
617 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>
623 static void right_unlink_first_of_group(pointer x,Assigner& assign)
624 {
625 pointer second=pointer_from(x: x->next()),
626 last=second->prior(),
627 lastbutone=last->prior();
628 if(second==lastbutone){
629 assign(second->next(),base_pointer_from(x: last));
630 assign(second->prior(),x->prior());
631 }
632 else{
633 assign(lastbutone->next(),base_pointer_from(x: second));
634 assign(second->next()->prior(),last);
635 assign(second->prior(),x->prior());
636 }
637 }
638
639 template<typename Assigner>
640 static void left_unlink_last_of_group(pointer x,Assigner& assign)
641 {
642 pointer lastbutone=x->prior(),
643 first=pointer_from(x: lastbutone->next()),
644 second=pointer_from(x: 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(x: first));
652 assign(lastbutone->next(),x->next());
653 }
654 }
655
656 template<typename Assigner>
657 static void unlink_last_but_one_of_group(pointer x,Assigner& assign)
658 {
659 pointer first=pointer_from(x: x->next()),
660 second=pointer_from(x: first->next()),
661 last=second->prior();
662 if(second==x){
663 assign(last->prior(),first);
664 assign(first->next(),base_pointer_from(x: last));
665 }
666 else{
667 assign(last->prior(),x->prior());
668 assign(x->prior()->next(),base_pointer_from(x: first));
669 }
670 }
671
672 template<typename Assigner>
673 static void unlink_second_of_group(pointer x,Assigner& assign)
674 {
675 pointer last=x->prior(),
676 lastbutone=last->prior(),
677 first=pointer_from(x: lastbutone->next());
678 if(lastbutone==x){
679 assign(first->next(),base_pointer_from(x: 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
689template<typename Super>
690struct 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
703template<typename Super>
704struct hashed_index_node:
705 Super,hashed_index_node_trampoline<Super>
706{
707private:
708 typedef hashed_index_node_trampoline<Super> trampoline;
709
710public:
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
723 impl_pointer& prior(){return trampoline::prior();}
724 impl_pointer prior()const{return trampoline::prior();}
725 impl_base_pointer& next(){return trampoline::next();}
726 impl_base_pointer next()const{return trampoline::next();}
727
728 impl_pointer impl()
729 {
730 return static_cast<impl_pointer>(
731 static_cast<impl_type*>(static_cast<trampoline*>(this)));
732 }
733
734 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
740 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
748 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>
759 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>
765 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