]>
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_SEQ_INDEX_NODE_HPP | |
10 | #define BOOST_MULTI_INDEX_DETAIL_SEQ_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 <algorithm> | |
18 | #include <boost/detail/allocator_utilities.hpp> | |
19 | #include <boost/multi_index/detail/raw_ptr.hpp> | |
20 | ||
21 | namespace boost{ | |
22 | ||
23 | namespace multi_index{ | |
24 | ||
25 | namespace detail{ | |
26 | ||
27 | /* doubly-linked node for use by sequenced_index */ | |
28 | ||
29 | template<typename Allocator> | |
30 | struct sequenced_index_node_impl | |
31 | { | |
32 | typedef typename | |
33 | boost::detail::allocator::rebind_to< | |
34 | Allocator,sequenced_index_node_impl | |
35 | >::type::pointer pointer; | |
36 | typedef typename | |
37 | boost::detail::allocator::rebind_to< | |
38 | Allocator,sequenced_index_node_impl | |
39 | >::type::const_pointer const_pointer; | |
40 | ||
41 | pointer& prior(){return prior_;} | |
42 | pointer prior()const{return prior_;} | |
43 | pointer& next(){return next_;} | |
44 | pointer next()const{return next_;} | |
45 | ||
46 | /* interoperability with bidir_node_iterator */ | |
47 | ||
48 | static void increment(pointer& x){x=x->next();} | |
49 | static void decrement(pointer& x){x=x->prior();} | |
50 | ||
51 | /* algorithmic stuff */ | |
52 | ||
53 | static void link(pointer x,pointer header) | |
54 | { | |
55 | x->prior()=header->prior(); | |
56 | x->next()=header; | |
57 | x->prior()->next()=x->next()->prior()=x; | |
58 | }; | |
59 | ||
60 | static void unlink(pointer x) | |
61 | { | |
62 | x->prior()->next()=x->next(); | |
63 | x->next()->prior()=x->prior(); | |
64 | } | |
65 | ||
66 | static void relink(pointer position,pointer x) | |
67 | { | |
68 | unlink(x); | |
69 | x->prior()=position->prior(); | |
70 | x->next()=position; | |
71 | x->prior()->next()=x->next()->prior()=x; | |
72 | } | |
73 | ||
74 | static void relink(pointer position,pointer x,pointer y) | |
75 | { | |
76 | /* position is assumed not to be in [x,y) */ | |
77 | ||
78 | if(x!=y){ | |
79 | pointer z=y->prior(); | |
80 | x->prior()->next()=y; | |
81 | y->prior()=x->prior(); | |
82 | x->prior()=position->prior(); | |
83 | z->next()=position; | |
84 | x->prior()->next()=x; | |
85 | z->next()->prior()=z; | |
86 | } | |
87 | } | |
88 | ||
89 | static void reverse(pointer header) | |
90 | { | |
91 | pointer x=header; | |
92 | do{ | |
93 | pointer y=x->next(); | |
94 | std::swap(x->prior(),x->next()); | |
95 | x=y; | |
96 | }while(x!=header); | |
97 | } | |
98 | ||
99 | static void swap(pointer x,pointer y) | |
100 | { | |
101 | /* This swap function does not exchange the header nodes, | |
102 | * but rather their pointers. This is *not* used for implementing | |
103 | * sequenced_index::swap. | |
104 | */ | |
105 | ||
106 | if(x->next()!=x){ | |
107 | if(y->next()!=y){ | |
108 | std::swap(x->next(),y->next()); | |
109 | std::swap(x->prior(),y->prior()); | |
110 | x->next()->prior()=x->prior()->next()=x; | |
111 | y->next()->prior()=y->prior()->next()=y; | |
112 | } | |
113 | else{ | |
114 | y->next()=x->next(); | |
115 | y->prior()=x->prior(); | |
116 | x->next()=x->prior()=x; | |
117 | y->next()->prior()=y->prior()->next()=y; | |
118 | } | |
119 | } | |
120 | else if(y->next()!=y){ | |
121 | x->next()=y->next(); | |
122 | x->prior()=y->prior(); | |
123 | y->next()=y->prior()=y; | |
124 | x->next()->prior()=x->prior()->next()=x; | |
125 | } | |
126 | } | |
127 | ||
128 | private: | |
129 | pointer prior_; | |
130 | pointer next_; | |
131 | }; | |
132 | ||
133 | template<typename Super> | |
134 | struct sequenced_index_node_trampoline: | |
135 | sequenced_index_node_impl< | |
136 | typename boost::detail::allocator::rebind_to< | |
137 | typename Super::allocator_type, | |
138 | char | |
139 | >::type | |
140 | > | |
141 | { | |
142 | typedef sequenced_index_node_impl< | |
143 | typename boost::detail::allocator::rebind_to< | |
144 | typename Super::allocator_type, | |
145 | char | |
146 | >::type | |
147 | > impl_type; | |
148 | }; | |
149 | ||
150 | template<typename Super> | |
151 | struct sequenced_index_node:Super,sequenced_index_node_trampoline<Super> | |
152 | { | |
153 | private: | |
154 | typedef sequenced_index_node_trampoline<Super> trampoline; | |
155 | ||
156 | public: | |
157 | typedef typename trampoline::impl_type impl_type; | |
158 | typedef typename trampoline::pointer impl_pointer; | |
159 | typedef typename trampoline::const_pointer const_impl_pointer; | |
160 | ||
161 | impl_pointer& prior(){return trampoline::prior();} | |
162 | impl_pointer prior()const{return trampoline::prior();} | |
163 | impl_pointer& next(){return trampoline::next();} | |
164 | impl_pointer next()const{return trampoline::next();} | |
165 | ||
166 | impl_pointer impl() | |
167 | { | |
168 | return static_cast<impl_pointer>( | |
169 | static_cast<impl_type*>(static_cast<trampoline*>(this))); | |
170 | } | |
171 | ||
172 | const_impl_pointer impl()const | |
173 | { | |
174 | return static_cast<const_impl_pointer>( | |
175 | static_cast<const impl_type*>(static_cast<const trampoline*>(this))); | |
176 | } | |
177 | ||
178 | static sequenced_index_node* from_impl(impl_pointer x) | |
179 | { | |
180 | return | |
181 | static_cast<sequenced_index_node*>( | |
182 | static_cast<trampoline*>( | |
183 | raw_ptr<impl_type*>(x))); | |
184 | } | |
185 | ||
186 | static const sequenced_index_node* from_impl(const_impl_pointer x) | |
187 | { | |
188 | return | |
189 | static_cast<const sequenced_index_node*>( | |
190 | static_cast<const trampoline*>( | |
191 | raw_ptr<const impl_type*>(x))); | |
192 | } | |
193 | ||
194 | /* interoperability with bidir_node_iterator */ | |
195 | ||
196 | static void increment(sequenced_index_node*& x) | |
197 | { | |
198 | impl_pointer xi=x->impl(); | |
199 | trampoline::increment(xi); | |
200 | x=from_impl(xi); | |
201 | } | |
202 | ||
203 | static void decrement(sequenced_index_node*& x) | |
204 | { | |
205 | impl_pointer xi=x->impl(); | |
206 | trampoline::decrement(xi); | |
207 | x=from_impl(xi); | |
208 | } | |
209 | }; | |
210 | ||
211 | } /* namespace multi_index::detail */ | |
212 | ||
213 | } /* namespace multi_index */ | |
214 | ||
215 | } /* namespace boost */ | |
216 | ||
217 | #endif |