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)
6 * See http://www.boost.org/libs/multi_index for library home page.
9 #ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_NODE_HPP
10 #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_NODE_HPP
16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
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>
26 namespace multi_index{
30 template<typename Allocator>
31 struct random_access_index_node_impl
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<
42 >::type ptr_allocator;
43 typedef allocator_traits<ptr_allocator> ptr_alloc_traits;
44 typedef typename ptr_alloc_traits::pointer ptr_pointer;
46 ptr_pointer& up(){return up_;}
47 ptr_pointer up()const{return up_;}
49 /* interoperability with rnd_node_iterator */
51 static void increment(pointer& x)
56 static void decrement(pointer& x)
61 static void advance(pointer& x,difference_type n)
66 static difference_type distance(pointer x,pointer y)
68 return static_cast<difference_type>(y->up()-x->up());
71 /* algorithmic stuff */
73 static void relocate(ptr_pointer pos,ptr_pointer x)
92 static void relocate(ptr_pointer pos,ptr_pointer first,ptr_pointer last)
94 ptr_pointer begin,middle,end;
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);
111 for(std::ptrdiff_t i=0;i<p;++i){
112 pointer tmp=begin[i];
113 for(std::ptrdiff_t j=i,k;;){
118 (*(begin+j))->up()=begin+j;
122 *(begin+j)=*(begin+k);
123 (*(begin+j))->up()=begin+j;
130 (*(begin+k))->up()=begin+k;
134 *(begin+k)=*(begin+j);
135 (*(begin+k))->up()=begin+k;
141 static void extract(ptr_pointer x,ptr_pointer pend)
151 static void transfer(
152 ptr_pointer pbegin0,ptr_pointer pend0,ptr_pointer pbegin1)
154 while(pbegin0!=pend0){
156 (*pbegin1)->up()=pbegin1;
161 static void reverse(ptr_pointer pbegin,ptr_pointer pend)
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;
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,
185 typedef random_access_index_node_impl<
186 typename rebind_alloc_for<
187 typename Super::allocator_type,
193 template<typename Super>
194 struct random_access_index_node:
195 Super,random_access_index_node_trampoline<Super>
198 typedef random_access_index_node_trampoline<Super> trampoline;
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;
207 impl_ptr_pointer& up(){return trampoline::up();}
208 impl_ptr_pointer up()const{return trampoline::up();}
212 return static_cast<impl_pointer>(
213 static_cast<impl_type*>(static_cast<trampoline*>(this)));
216 const_impl_pointer impl()const
218 return static_cast<const_impl_pointer>(
219 static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
222 static random_access_index_node* from_impl(impl_pointer x)
225 static_cast<random_access_index_node*>(
226 static_cast<trampoline*>(
227 raw_ptr<impl_type*>(x)));
230 static const random_access_index_node* from_impl(const_impl_pointer x)
233 static_cast<const random_access_index_node*>(
234 static_cast<const trampoline*>(
235 raw_ptr<const impl_type*>(x)));
238 /* interoperability with rnd_node_iterator */
240 static void increment(random_access_index_node*& x)
242 impl_pointer xi=x->impl();
243 trampoline::increment(xi);
247 static void decrement(random_access_index_node*& x)
249 impl_pointer xi=x->impl();
250 trampoline::decrement(xi);
254 static void advance(random_access_index_node*& x,difference_type n)
256 impl_pointer xi=x->impl();
257 trampoline::advance(xi,n);
261 static difference_type distance(
262 random_access_index_node* x,random_access_index_node* y)
264 return trampoline::distance(x->impl(),y->impl());
268 } /* namespace multi_index::detail */
270 } /* namespace multi_index */
272 } /* namespace boost */