]>
Commit | Line | Data |
---|---|---|
92f5a8d4 | 1 | /* Copyright 2003-2019 Joaquin M Lopez Munoz. |
7c673cae FG |
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 */ | |
92f5a8d4 | 17 | #include <boost/multi_index/detail/allocator_traits.hpp> |
7c673cae FG |
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 | { | |
92f5a8d4 | 102 | typedef typename rebind_alloc_for< |
7c673cae | 103 | Allocator,hashed_index_base_node_impl |
92f5a8d4 TL |
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; | |
7c673cae FG |
115 | |
116 | 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 | 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 | ||
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 | 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 | 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->next()); | |
243 | } | |
244 | ||
245 | static pointer after_local(pointer x) | |
246 | { | |
247 | return is_last_of_bucket(x)?pointer(0):pointer_from(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->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(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->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 | ||
332 | private: | |
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 | ||
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 | } | |
92f5a8d4 | 411 | } |
7c673cae FG |
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< | |
92f5a8d4 TL |
692 | typename rebind_alloc_for< |
693 | typename Super::allocator_type,char | |
7c673cae FG |
694 | >::type |
695 | > | |
696 | { | |
92f5a8d4 TL |
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; | |
7c673cae FG |
701 | }; |
702 | ||
703 | template<typename Super,typename Category> | |
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 hashed_index_node_alg< | |
713 | impl_type,Category> node_alg; | |
714 | typedef typename trampoline::base_pointer impl_base_pointer; | |
715 | typedef typename trampoline::const_base_pointer const_impl_base_pointer; | |
716 | typedef typename trampoline::pointer impl_pointer; | |
717 | typedef typename trampoline::const_pointer const_impl_pointer; | |
92f5a8d4 | 718 | typedef typename trampoline::difference_type difference_type; |
7c673cae FG |
719 | |
720 | impl_pointer& prior(){return trampoline::prior();} | |
721 | impl_pointer prior()const{return trampoline::prior();} | |
722 | impl_base_pointer& next(){return trampoline::next();} | |
723 | impl_base_pointer next()const{return trampoline::next();} | |
724 | ||
725 | impl_pointer impl() | |
726 | { | |
727 | return static_cast<impl_pointer>( | |
728 | static_cast<impl_type*>(static_cast<trampoline*>(this))); | |
729 | } | |
730 | ||
731 | const_impl_pointer impl()const | |
732 | { | |
733 | return static_cast<const_impl_pointer>( | |
734 | static_cast<const impl_type*>(static_cast<const trampoline*>(this))); | |
735 | } | |
736 | ||
737 | static hashed_index_node* from_impl(impl_pointer x) | |
738 | { | |
739 | return | |
740 | static_cast<hashed_index_node*>( | |
741 | static_cast<trampoline*>( | |
742 | raw_ptr<impl_type*>(x))); | |
743 | } | |
744 | ||
745 | static const hashed_index_node* from_impl(const_impl_pointer x) | |
746 | { | |
747 | return | |
748 | static_cast<const hashed_index_node*>( | |
749 | static_cast<const trampoline*>( | |
750 | raw_ptr<const impl_type*>(x))); | |
751 | } | |
752 | ||
753 | /* interoperability with hashed_index_iterator */ | |
754 | ||
755 | static void increment(hashed_index_node*& x) | |
756 | { | |
757 | x=from_impl(node_alg::after(x->impl())); | |
758 | } | |
759 | ||
760 | static void increment_local(hashed_index_node*& x) | |
761 | { | |
762 | x=from_impl(node_alg::after_local(x->impl())); | |
763 | } | |
764 | }; | |
765 | ||
766 | } /* namespace multi_index::detail */ | |
767 | ||
768 | } /* namespace multi_index */ | |
769 | ||
770 | } /* namespace boost */ | |
771 | ||
772 | #endif |