]>
Commit | Line | Data |
---|---|---|
1e59de90 | 1 | /* Copyright 2003-2021 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_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> | |
7c673cae | 18 | #include <boost/integer/common_factor_rt.hpp> |
92f5a8d4 | 19 | #include <boost/multi_index/detail/allocator_traits.hpp> |
7c673cae FG |
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 | { | |
92f5a8d4 | 33 | typedef typename rebind_alloc_for< |
7c673cae | 34 | Allocator,random_access_index_node_impl |
92f5a8d4 TL |
35 | >::type node_allocator; |
36 | typedef allocator_traits<node_allocator> node_alloc_traits; | |
37 | typedef typename node_alloc_traits::pointer pointer; | |
38 | typedef typename node_alloc_traits::const_pointer const_pointer; | |
39 | typedef typename node_alloc_traits::difference_type difference_type; | |
40 | typedef typename rebind_alloc_for< | |
7c673cae | 41 | Allocator,pointer |
92f5a8d4 TL |
42 | >::type ptr_allocator; |
43 | typedef allocator_traits<ptr_allocator> ptr_alloc_traits; | |
44 | typedef typename ptr_alloc_traits::pointer ptr_pointer; | |
45 | ||
7c673cae FG |
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 | ||
92f5a8d4 | 61 | static void advance(pointer& x,difference_type n) |
7c673cae FG |
62 | { |
63 | x=*(x->up()+n); | |
64 | } | |
65 | ||
92f5a8d4 | 66 | static difference_type distance(pointer x,pointer y) |
7c673cae | 67 | { |
92f5a8d4 | 68 | return static_cast<difference_type>(y->up()-x->up()); |
7c673cae FG |
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 | ||
1e59de90 TL |
172 | static ptr_pointer gather_nulls( |
173 | ptr_pointer pbegin,ptr_pointer pend,ptr_pointer x) | |
174 | { | |
175 | for(ptr_pointer p=pbegin;p!=x;++p){ | |
176 | if(*p){ | |
177 | *pbegin=*p; | |
178 | (*pbegin)->up()=pbegin; | |
179 | ++pbegin; | |
180 | } | |
181 | } | |
182 | for(ptr_pointer p=pend;p!=x;){ | |
183 | if(*--p){ | |
184 | *--pend=*p; | |
185 | (*pend)->up()=pend; | |
186 | } | |
187 | } | |
188 | return pbegin; | |
189 | } | |
190 | ||
7c673cae FG |
191 | private: |
192 | ptr_pointer up_; | |
193 | }; | |
194 | ||
195 | template<typename Super> | |
196 | struct random_access_index_node_trampoline: | |
197 | random_access_index_node_impl< | |
92f5a8d4 | 198 | typename rebind_alloc_for< |
7c673cae FG |
199 | typename Super::allocator_type, |
200 | char | |
201 | >::type | |
202 | > | |
203 | { | |
204 | typedef random_access_index_node_impl< | |
92f5a8d4 | 205 | typename rebind_alloc_for< |
7c673cae FG |
206 | typename Super::allocator_type, |
207 | char | |
208 | >::type | |
209 | > impl_type; | |
210 | }; | |
211 | ||
212 | template<typename Super> | |
213 | struct random_access_index_node: | |
214 | Super,random_access_index_node_trampoline<Super> | |
215 | { | |
216 | private: | |
217 | typedef random_access_index_node_trampoline<Super> trampoline; | |
218 | ||
219 | public: | |
92f5a8d4 TL |
220 | typedef typename trampoline::impl_type impl_type; |
221 | typedef typename trampoline::pointer impl_pointer; | |
222 | typedef typename trampoline::const_pointer const_impl_pointer; | |
223 | typedef typename trampoline::difference_type difference_type; | |
224 | typedef typename trampoline::ptr_pointer impl_ptr_pointer; | |
7c673cae FG |
225 | |
226 | impl_ptr_pointer& up(){return trampoline::up();} | |
227 | impl_ptr_pointer up()const{return trampoline::up();} | |
228 | ||
229 | impl_pointer impl() | |
230 | { | |
231 | return static_cast<impl_pointer>( | |
232 | static_cast<impl_type*>(static_cast<trampoline*>(this))); | |
233 | } | |
234 | ||
235 | const_impl_pointer impl()const | |
236 | { | |
237 | return static_cast<const_impl_pointer>( | |
238 | static_cast<const impl_type*>(static_cast<const trampoline*>(this))); | |
239 | } | |
240 | ||
241 | static random_access_index_node* from_impl(impl_pointer x) | |
242 | { | |
243 | return | |
244 | static_cast<random_access_index_node*>( | |
245 | static_cast<trampoline*>( | |
246 | raw_ptr<impl_type*>(x))); | |
247 | } | |
248 | ||
249 | static const random_access_index_node* from_impl(const_impl_pointer x) | |
250 | { | |
251 | return | |
252 | static_cast<const random_access_index_node*>( | |
253 | static_cast<const trampoline*>( | |
254 | raw_ptr<const impl_type*>(x))); | |
255 | } | |
256 | ||
257 | /* interoperability with rnd_node_iterator */ | |
258 | ||
259 | static void increment(random_access_index_node*& x) | |
260 | { | |
261 | impl_pointer xi=x->impl(); | |
262 | trampoline::increment(xi); | |
263 | x=from_impl(xi); | |
264 | } | |
265 | ||
266 | static void decrement(random_access_index_node*& x) | |
267 | { | |
268 | impl_pointer xi=x->impl(); | |
269 | trampoline::decrement(xi); | |
270 | x=from_impl(xi); | |
271 | } | |
272 | ||
92f5a8d4 | 273 | static void advance(random_access_index_node*& x,difference_type n) |
7c673cae FG |
274 | { |
275 | impl_pointer xi=x->impl(); | |
276 | trampoline::advance(xi,n); | |
277 | x=from_impl(xi); | |
278 | } | |
279 | ||
92f5a8d4 | 280 | static difference_type distance( |
7c673cae FG |
281 | random_access_index_node* x,random_access_index_node* y) |
282 | { | |
283 | return trampoline::distance(x->impl(),y->impl()); | |
284 | } | |
285 | }; | |
286 | ||
287 | } /* namespace multi_index::detail */ | |
288 | ||
289 | } /* namespace multi_index */ | |
290 | ||
291 | } /* namespace boost */ | |
292 | ||
293 | #endif |