1/* Copyright 2003-2021 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
24namespace boost{
25
26namespace multi_index{
27
28namespace detail{
29
30template<typename Allocator>
31struct 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
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,difference_type n)
62 {
63 x=*(x->up()+n);
64 }
65
66 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
73 static void relocate(ptr_pointer pos,ptr_pointer x)
74 {
75 pointer n=*x;
76 if(x<pos){
77 extract(x,pend: 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(a: n,b: 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 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
191private:
192 ptr_pointer up_;
193};
194
195template<typename Super>
196struct random_access_index_node_trampoline:
197 random_access_index_node_impl<
198 typename rebind_alloc_for<
199 typename Super::allocator_type,
200 char
201 >::type
202 >
203{
204 typedef random_access_index_node_impl<
205 typename rebind_alloc_for<
206 typename Super::allocator_type,
207 char
208 >::type
209 > impl_type;
210};
211
212template<typename Super>
213struct random_access_index_node:
214 Super,random_access_index_node_trampoline<Super>
215{
216private:
217 typedef random_access_index_node_trampoline<Super> trampoline;
218
219public:
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;
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
273 static void advance(random_access_index_node*& x,difference_type n)
274 {
275 impl_pointer xi=x->impl();
276 trampoline::advance(xi,n);
277 x=from_impl(xi);
278 }
279
280 static difference_type distance(
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
294

source code of boost/libs/multi_index/include/boost/multi_index/detail/rnd_index_node.hpp