Line data Source code
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 :
116 8079310 : pointer& prior(){return prior_;}
117 : 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 :
137 2666093 : base_pointer& next(){return next_;}
138 : base_pointer next()const{return next_;}
139 :
140 619721 : static pointer pointer_from(base_pointer x)
141 : {
142 619721 : return static_cast<pointer>(
143 : static_cast<hashed_index_node_impl*>(
144 619721 : raw_ptr<super*>(x)));
145 : }
146 :
147 32413 : static base_pointer base_pointer_from(pointer x)
148 : {
149 32413 : return static_cast<base_pointer>(
150 32413 : 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 : {
166 70745 : 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 :
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 :
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 :
235 24701 : static bool is_first_of_bucket(pointer x)
236 : {
237 24701 : return x->prior()->next()!=base_pointer_from(x);
238 : }
239 :
240 25687 : static pointer after(pointer x)
241 : {
242 25687 : return is_last_of_bucket(x)?x->next()->prior():pointer_from(x->next());
243 : }
244 :
245 1648406 : static pointer after_local(pointer x)
246 : {
247 1648406 : return is_last_of_bucket(x)?pointer(0):pointer_from(x->next());
248 : }
249 :
250 15739 : static pointer next_to_inspect(pointer x)
251 : {
252 15739 : return is_last_of_bucket(x)?pointer(0):pointer_from(x->next());
253 : }
254 :
255 29974 : static void link(pointer x,base_pointer buc,pointer end)
256 : {
257 29974 : if(buc->prior()==pointer(0)){ /* empty bucket */
258 24945 : x->prior()=end->prior();
259 24945 : x->next()=end->prior()->next();
260 24945 : x->prior()->next()=buc;
261 24945 : buc->prior()=x;
262 24945 : end->prior()=x;
263 24945 : }
264 : else{
265 5029 : x->prior()=buc->prior()->prior();
266 5029 : x->next()=base_pointer_from(buc->prior());
267 5029 : buc->prior()=x;
268 5029 : x->next()->prior()=x;
269 : }
270 29974 : }
271 :
272 24701 : static void unlink(pointer x)
273 : {
274 : default_assigner assign;
275 24701 : unlink(x,assign);
276 24701 : }
277 :
278 : typedef unlink_undo_assigner<Node> unlink_undo;
279 :
280 : template<typename Assigner>
281 24701 : static void unlink(pointer x,Assigner& assign)
282 : {
283 24701 : if(is_first_of_bucket(x)){
284 23717 : if(is_last_of_bucket(x)){
285 21343 : assign(x->prior()->next()->prior(),pointer(0));
286 21343 : assign(x->prior()->next(),x->next());
287 21343 : assign(x->next()->prior()->prior(),x->prior());
288 21343 : }
289 : else{
290 2374 : assign(x->prior()->next()->prior(),pointer_from(x->next()));
291 2374 : assign(x->next()->prior(),x->prior());
292 : }
293 23717 : }
294 984 : else if(is_last_of_bucket(x)){
295 890 : assign(x->prior()->next(),x->next());
296 890 : assign(x->next()->prior()->prior(),x->prior());
297 890 : }
298 : else{
299 94 : assign(x->prior()->next(),x->next());
300 94 : assign(x->next()->prior(),x->prior());
301 : }
302 24701 : }
303 :
304 : /* used only at rehashing */
305 :
306 0 : static void append(pointer x,pointer end)
307 : {
308 0 : x->prior()=end->prior();
309 0 : x->next()=end->prior()->next();
310 0 : x->prior()->next()=base_pointer_from(x);
311 0 : end->prior()=x;
312 0 : }
313 :
314 2683 : static bool unlink_last(pointer end)
315 : {
316 : /* returns true iff bucket is emptied */
317 :
318 2683 : pointer x=end->prior();
319 2683 : if(x->prior()->next()==base_pointer_from(x)){
320 1006 : x->prior()->next()=x->next();
321 1006 : end->prior()=x->prior();
322 1006 : return false;
323 : }
324 : else{
325 1677 : x->prior()->next()->prior()=pointer(0);
326 1677 : x->prior()->next()=x->next();
327 1677 : end->prior()=x->prior();
328 1677 : return true;
329 : }
330 2683 : }
331 :
332 : private:
333 619721 : static pointer pointer_from(base_pointer x)
334 : {
335 619721 : return Node::pointer_from(x);
336 : }
337 :
338 32413 : static base_pointer base_pointer_from(pointer x)
339 : {
340 32413 : return Node::base_pointer_from(x);
341 : }
342 :
343 1714533 : static bool is_last_of_bucket(pointer x)
344 : {
345 1714533 : 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 :
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->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 :
378 : 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 :
387 : 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 :
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(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(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 :
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->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(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(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->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 :
559 : 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:
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->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->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>
640 : 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>
657 : 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>
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(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 :
723 : impl_pointer& prior(){return trampoline::prior();}
724 : impl_pointer prior()const{return trampoline::prior();}
725 24322 : impl_base_pointer& next(){return trampoline::next();}
726 : impl_base_pointer next()const{return trampoline::next();}
727 :
728 1284734 : impl_pointer impl()
729 : {
730 1284734 : return static_cast<impl_pointer>(
731 1284734 : 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 841331 : static hashed_index_node* from_impl(impl_pointer x)
741 : {
742 841331 : return
743 841331 : static_cast<hashed_index_node*>(
744 : static_cast<trampoline*>(
745 841331 : 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 25481 : static void increment(hashed_index_node*& x)
760 : {
761 25481 : x=from_impl(node_alg<Category>::type::after(x->impl()));
762 25481 : }
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
|
