]>
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_RND_INDEX_NODE_HPP | |
10 | #define BOOST_MULTI_INDEX_DETAIL_RND_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/integer/common_factor_rt.hpp> | |
20 | #include <boost/multi_index/detail/raw_ptr.hpp> | |
21 | #include <cstddef> | |
22 | #include <functional> | |
23 | ||
24 | namespace boost{ | |
25 | ||
26 | namespace multi_index{ | |
27 | ||
28 | namespace detail{ | |
29 | ||
30 | template<typename Allocator> | |
31 | struct random_access_index_node_impl | |
32 | { | |
33 | typedef typename | |
34 | boost::detail::allocator::rebind_to< | |
35 | Allocator,random_access_index_node_impl | |
36 | >::type::pointer pointer; | |
37 | typedef typename | |
38 | boost::detail::allocator::rebind_to< | |
39 | Allocator,random_access_index_node_impl | |
40 | >::type::const_pointer const_pointer; | |
41 | typedef typename | |
42 | boost::detail::allocator::rebind_to< | |
43 | Allocator,pointer | |
44 | >::type::pointer ptr_pointer; | |
45 | ||
46 | ptr_pointer& up(){return up_;} | |
47 | ptr_pointer up()const{return up_;} | |
48 | ||
49 | /* interoperability with rnd_node_iterator */ | |
50 | ||
51 | static void increment(pointer& x) | |
52 | { | |
53 | x=*(x->up()+1); | |
54 | } | |
55 | ||
56 | static void decrement(pointer& x) | |
57 | { | |
58 | x=*(x->up()-1); | |
59 | } | |
60 | ||
61 | static void advance(pointer& x,std::ptrdiff_t n) | |
62 | { | |
63 | x=*(x->up()+n); | |
64 | } | |
65 | ||
66 | static std::ptrdiff_t distance(pointer x,pointer y) | |
67 | { | |
68 | return y->up()-x->up(); | |
69 | } | |
70 | ||
71 | /* algorithmic stuff */ | |
72 | ||
73 | static void relocate(ptr_pointer pos,ptr_pointer x) | |
74 | { | |
75 | pointer n=*x; | |
76 | if(x<pos){ | |
77 | extract(x,pos); | |
78 | *(pos-1)=n; | |
79 | n->up()=pos-1; | |
80 | } | |
81 | else{ | |
82 | while(x!=pos){ | |
83 | *x=*(x-1); | |
84 | (*x)->up()=x; | |
85 | --x; | |
86 | } | |
87 | *pos=n; | |
88 | n->up()=pos; | |
89 | } | |
90 | }; | |
91 | ||
92 | static void relocate(ptr_pointer pos,ptr_pointer first,ptr_pointer last) | |
93 | { | |
94 | ptr_pointer begin,middle,end; | |
95 | if(pos<first){ | |
96 | begin=pos; | |
97 | middle=first; | |
98 | end=last; | |
99 | } | |
100 | else{ | |
101 | begin=first; | |
102 | middle=last; | |
103 | end=pos; | |
104 | } | |
105 | ||
106 | std::ptrdiff_t n=end-begin; | |
107 | std::ptrdiff_t m=middle-begin; | |
108 | std::ptrdiff_t n_m=n-m; | |
109 | std::ptrdiff_t p=integer::gcd(n,m); | |
110 | ||
111 | for(std::ptrdiff_t i=0;i<p;++i){ | |
112 | pointer tmp=begin[i]; | |
113 | for(std::ptrdiff_t j=i,k;;){ | |
114 | if(j<n_m)k=j+m; | |
115 | else k=j-n_m; | |
116 | if(k==i){ | |
117 | *(begin+j)=tmp; | |
118 | (*(begin+j))->up()=begin+j; | |
119 | break; | |
120 | } | |
121 | else{ | |
122 | *(begin+j)=*(begin+k); | |
123 | (*(begin+j))->up()=begin+j; | |
124 | } | |
125 | ||
126 | if(k<n_m)j=k+m; | |
127 | else j=k-n_m; | |
128 | if(j==i){ | |
129 | *(begin+k)=tmp; | |
130 | (*(begin+k))->up()=begin+k; | |
131 | break; | |
132 | } | |
133 | else{ | |
134 | *(begin+k)=*(begin+j); | |
135 | (*(begin+k))->up()=begin+k; | |
136 | } | |
137 | } | |
138 | } | |
139 | }; | |
140 | ||
141 | static void extract(ptr_pointer x,ptr_pointer pend) | |
142 | { | |
143 | --pend; | |
144 | while(x!=pend){ | |
145 | *x=*(x+1); | |
146 | (*x)->up()=x; | |
147 | ++x; | |
148 | } | |
149 | } | |
150 | ||
151 | static void transfer( | |
152 | ptr_pointer pbegin0,ptr_pointer pend0,ptr_pointer pbegin1) | |
153 | { | |
154 | while(pbegin0!=pend0){ | |
155 | *pbegin1=*pbegin0++; | |
156 | (*pbegin1)->up()=pbegin1; | |
157 | ++pbegin1; | |
158 | } | |
159 | } | |
160 | ||
161 | static void reverse(ptr_pointer pbegin,ptr_pointer pend) | |
162 | { | |
163 | std::ptrdiff_t d=(pend-pbegin)/2; | |
164 | for(std::ptrdiff_t i=0;i<d;++i){ | |
165 | std::swap(*pbegin,*--pend); | |
166 | (*pbegin)->up()=pbegin; | |
167 | (*pend)->up()=pend; | |
168 | ++pbegin; | |
169 | } | |
170 | } | |
171 | ||
172 | private: | |
173 | ptr_pointer up_; | |
174 | }; | |
175 | ||
176 | template<typename Super> | |
177 | struct random_access_index_node_trampoline: | |
178 | random_access_index_node_impl< | |
179 | typename boost::detail::allocator::rebind_to< | |
180 | typename Super::allocator_type, | |
181 | char | |
182 | >::type | |
183 | > | |
184 | { | |
185 | typedef random_access_index_node_impl< | |
186 | typename boost::detail::allocator::rebind_to< | |
187 | typename Super::allocator_type, | |
188 | char | |
189 | >::type | |
190 | > impl_type; | |
191 | }; | |
192 | ||
193 | template<typename Super> | |
194 | struct random_access_index_node: | |
195 | Super,random_access_index_node_trampoline<Super> | |
196 | { | |
197 | private: | |
198 | typedef random_access_index_node_trampoline<Super> trampoline; | |
199 | ||
200 | public: | |
201 | typedef typename trampoline::impl_type impl_type; | |
202 | typedef typename trampoline::pointer impl_pointer; | |
203 | typedef typename trampoline::const_pointer const_impl_pointer; | |
204 | typedef typename trampoline::ptr_pointer impl_ptr_pointer; | |
205 | ||
206 | impl_ptr_pointer& up(){return trampoline::up();} | |
207 | impl_ptr_pointer up()const{return trampoline::up();} | |
208 | ||
209 | impl_pointer impl() | |
210 | { | |
211 | return static_cast<impl_pointer>( | |
212 | static_cast<impl_type*>(static_cast<trampoline*>(this))); | |
213 | } | |
214 | ||
215 | const_impl_pointer impl()const | |
216 | { | |
217 | return static_cast<const_impl_pointer>( | |
218 | static_cast<const impl_type*>(static_cast<const trampoline*>(this))); | |
219 | } | |
220 | ||
221 | static random_access_index_node* from_impl(impl_pointer x) | |
222 | { | |
223 | return | |
224 | static_cast<random_access_index_node*>( | |
225 | static_cast<trampoline*>( | |
226 | raw_ptr<impl_type*>(x))); | |
227 | } | |
228 | ||
229 | static const random_access_index_node* from_impl(const_impl_pointer x) | |
230 | { | |
231 | return | |
232 | static_cast<const random_access_index_node*>( | |
233 | static_cast<const trampoline*>( | |
234 | raw_ptr<const impl_type*>(x))); | |
235 | } | |
236 | ||
237 | /* interoperability with rnd_node_iterator */ | |
238 | ||
239 | static void increment(random_access_index_node*& x) | |
240 | { | |
241 | impl_pointer xi=x->impl(); | |
242 | trampoline::increment(xi); | |
243 | x=from_impl(xi); | |
244 | } | |
245 | ||
246 | static void decrement(random_access_index_node*& x) | |
247 | { | |
248 | impl_pointer xi=x->impl(); | |
249 | trampoline::decrement(xi); | |
250 | x=from_impl(xi); | |
251 | } | |
252 | ||
253 | static void advance(random_access_index_node*& x,std::ptrdiff_t n) | |
254 | { | |
255 | impl_pointer xi=x->impl(); | |
256 | trampoline::advance(xi,n); | |
257 | x=from_impl(xi); | |
258 | } | |
259 | ||
260 | static std::ptrdiff_t distance( | |
261 | random_access_index_node* x,random_access_index_node* y) | |
262 | { | |
263 | return trampoline::distance(x->impl(),y->impl()); | |
264 | } | |
265 | }; | |
266 | ||
267 | } /* namespace multi_index::detail */ | |
268 | ||
269 | } /* namespace multi_index */ | |
270 | ||
271 | } /* namespace boost */ | |
272 | ||
273 | #endif |