1 /* Copyright 2003-2018 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/integer/common_factor_rt.hpp>
19 #include <boost/multi_index/detail/allocator_traits.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 rebind_alloc_for<
34     Allocator,random_access_index_node_impl
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<
41     Allocator,pointer
42   >::type                                             ptr_allocator;
43   typedef allocator_traits<ptr_allocator>             ptr_alloc_traits;
44   typedef typename ptr_alloc_traits::pointer          ptr_pointer;
45 
upboost::multi_index::detail::random_access_index_node_impl46   ptr_pointer& up(){return up_;}
upboost::multi_index::detail::random_access_index_node_impl47   ptr_pointer  up()const{return up_;}
48 
49   /* interoperability with rnd_node_iterator */
50 
incrementboost::multi_index::detail::random_access_index_node_impl51   static void increment(pointer& x)
52   {
53     x=*(x->up()+1);
54   }
55 
decrementboost::multi_index::detail::random_access_index_node_impl56   static void decrement(pointer& x)
57   {
58     x=*(x->up()-1);
59   }
60 
advanceboost::multi_index::detail::random_access_index_node_impl61   static void advance(pointer& x,difference_type n)
62   {
63     x=*(x->up()+n);
64   }
65 
distanceboost::multi_index::detail::random_access_index_node_impl66   static difference_type distance(pointer x,pointer y)
67   {
68     return static_cast<difference_type>(y->up()-x->up());
69   }
70 
71   /* algorithmic stuff */
72 
relocateboost::multi_index::detail::random_access_index_node_impl73   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 
relocateboost::multi_index::detail::random_access_index_node_impl92   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 
extractboost::multi_index::detail::random_access_index_node_impl141   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 
transferboost::multi_index::detail::random_access_index_node_impl151   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 
reverseboost::multi_index::detail::random_access_index_node_impl161   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 rebind_alloc_for<
180       typename Super::allocator_type,
181       char
182     >::type
183   >
184 {
185   typedef random_access_index_node_impl<
186     typename rebind_alloc_for<
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::difference_type   difference_type;
205   typedef typename trampoline::ptr_pointer       impl_ptr_pointer;
206 
upboost::multi_index::detail::random_access_index_node207   impl_ptr_pointer& up(){return trampoline::up();}
upboost::multi_index::detail::random_access_index_node208   impl_ptr_pointer  up()const{return trampoline::up();}
209 
implboost::multi_index::detail::random_access_index_node210   impl_pointer impl()
211   {
212     return static_cast<impl_pointer>(
213       static_cast<impl_type*>(static_cast<trampoline*>(this)));
214   }
215 
implboost::multi_index::detail::random_access_index_node216   const_impl_pointer impl()const
217   {
218     return static_cast<const_impl_pointer>(
219       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
220   }
221 
from_implboost::multi_index::detail::random_access_index_node222   static random_access_index_node* from_impl(impl_pointer x)
223   {
224     return
225       static_cast<random_access_index_node*>(
226         static_cast<trampoline*>(
227           raw_ptr<impl_type*>(x)));
228   }
229 
from_implboost::multi_index::detail::random_access_index_node230   static const random_access_index_node* from_impl(const_impl_pointer x)
231   {
232     return
233       static_cast<const random_access_index_node*>(
234         static_cast<const trampoline*>(
235           raw_ptr<const impl_type*>(x)));
236   }
237 
238   /* interoperability with rnd_node_iterator */
239 
incrementboost::multi_index::detail::random_access_index_node240   static void increment(random_access_index_node*& x)
241   {
242     impl_pointer xi=x->impl();
243     trampoline::increment(xi);
244     x=from_impl(xi);
245   }
246 
decrementboost::multi_index::detail::random_access_index_node247   static void decrement(random_access_index_node*& x)
248   {
249     impl_pointer xi=x->impl();
250     trampoline::decrement(xi);
251     x=from_impl(xi);
252   }
253 
advanceboost::multi_index::detail::random_access_index_node254   static void advance(random_access_index_node*& x,difference_type n)
255   {
256     impl_pointer xi=x->impl();
257     trampoline::advance(xi,n);
258     x=from_impl(xi);
259   }
260 
distanceboost::multi_index::detail::random_access_index_node261   static difference_type distance(
262     random_access_index_node* x,random_access_index_node* y)
263   {
264     return trampoline::distance(x->impl(),y->impl());
265   }
266 };
267 
268 } /* namespace multi_index::detail */
269 
270 } /* namespace multi_index */
271 
272 } /* namespace boost */
273 
274 #endif
275