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