1 /* Copyright 2003-2019 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_SEQ_INDEX_NODE_HPP
10 #define BOOST_MULTI_INDEX_DETAIL_SEQ_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/multi_index/detail/allocator_traits.hpp>
19 #include <boost/multi_index/detail/raw_ptr.hpp>
20 
21 namespace boost{
22 
23 namespace multi_index{
24 
25 namespace detail{
26 
27 /* doubly-linked node for use by sequenced_index */
28 
29 template<typename Allocator>
30 struct sequenced_index_node_impl
31 {
32   typedef typename rebind_alloc_for<
33     Allocator,sequenced_index_node_impl
34   >::type                                        node_allocator;
35   typedef allocator_traits<node_allocator>       alloc_traits;
36   typedef typename alloc_traits::pointer         pointer;
37   typedef typename alloc_traits::const_pointer   const_pointer;
38   typedef typename alloc_traits::difference_type difference_type;
39 
priorboost::multi_index::detail::sequenced_index_node_impl40   pointer& prior(){return prior_;}
priorboost::multi_index::detail::sequenced_index_node_impl41   pointer  prior()const{return prior_;}
nextboost::multi_index::detail::sequenced_index_node_impl42   pointer& next(){return next_;}
nextboost::multi_index::detail::sequenced_index_node_impl43   pointer  next()const{return next_;}
44 
45   /* interoperability with bidir_node_iterator */
46 
incrementboost::multi_index::detail::sequenced_index_node_impl47   static void increment(pointer& x){x=x->next();}
decrementboost::multi_index::detail::sequenced_index_node_impl48   static void decrement(pointer& x){x=x->prior();}
49 
50   /* algorithmic stuff */
51 
linkboost::multi_index::detail::sequenced_index_node_impl52   static void link(pointer x,pointer header)
53   {
54     x->prior()=header->prior();
55     x->next()=header;
56     x->prior()->next()=x->next()->prior()=x;
57   }
58 
unlinkboost::multi_index::detail::sequenced_index_node_impl59   static void unlink(pointer x)
60   {
61     x->prior()->next()=x->next();
62     x->next()->prior()=x->prior();
63   }
64 
relinkboost::multi_index::detail::sequenced_index_node_impl65   static void relink(pointer position,pointer x)
66   {
67     unlink(x);
68     x->prior()=position->prior();
69     x->next()=position;
70     x->prior()->next()=x->next()->prior()=x;
71   }
72 
relinkboost::multi_index::detail::sequenced_index_node_impl73   static void relink(pointer position,pointer x,pointer y)
74   {
75     /* position is assumed not to be in [x,y) */
76 
77     if(x!=y){
78       pointer z=y->prior();
79       x->prior()->next()=y;
80       y->prior()=x->prior();
81       x->prior()=position->prior();
82       z->next()=position;
83       x->prior()->next()=x;
84       z->next()->prior()=z;
85     }
86   }
87 
reverseboost::multi_index::detail::sequenced_index_node_impl88   static void reverse(pointer header)
89   {
90     pointer x=header;
91     do{
92       pointer y=x->next();
93       std::swap(x->prior(),x->next());
94       x=y;
95     }while(x!=header);
96   }
97 
swapboost::multi_index::detail::sequenced_index_node_impl98   static void swap(pointer x,pointer y)
99   {
100     /* This swap function does not exchange the header nodes,
101      * but rather their pointers. This is *not* used for implementing
102      * sequenced_index::swap.
103      */
104 
105     if(x->next()!=x){
106       if(y->next()!=y){
107         std::swap(x->next(),y->next());
108         std::swap(x->prior(),y->prior());
109         x->next()->prior()=x->prior()->next()=x;
110         y->next()->prior()=y->prior()->next()=y;
111       }
112       else{
113         y->next()=x->next();
114         y->prior()=x->prior();
115         x->next()=x->prior()=x;
116         y->next()->prior()=y->prior()->next()=y;
117       }
118     }
119     else if(y->next()!=y){
120       x->next()=y->next();
121       x->prior()=y->prior();
122       y->next()=y->prior()=y;
123       x->next()->prior()=x->prior()->next()=x;
124     }
125   }
126 
127 private:
128   pointer prior_;
129   pointer next_;
130 };
131 
132 template<typename Super>
133 struct sequenced_index_node_trampoline:
134   sequenced_index_node_impl<
135     typename rebind_alloc_for<
136       typename Super::allocator_type,
137       char
138     >::type
139   >
140 {
141   typedef sequenced_index_node_impl<
142     typename rebind_alloc_for<
143       typename Super::allocator_type,
144       char
145     >::type
146   > impl_type;
147 };
148 
149 template<typename Super>
150 struct sequenced_index_node:Super,sequenced_index_node_trampoline<Super>
151 {
152 private:
153   typedef sequenced_index_node_trampoline<Super> trampoline;
154 
155 public:
156   typedef typename trampoline::impl_type       impl_type;
157   typedef typename trampoline::pointer         impl_pointer;
158   typedef typename trampoline::const_pointer   const_impl_pointer;
159   typedef typename trampoline::difference_type difference_type;
160 
priorboost::multi_index::detail::sequenced_index_node161   impl_pointer& prior(){return trampoline::prior();}
priorboost::multi_index::detail::sequenced_index_node162   impl_pointer  prior()const{return trampoline::prior();}
nextboost::multi_index::detail::sequenced_index_node163   impl_pointer& next(){return trampoline::next();}
nextboost::multi_index::detail::sequenced_index_node164   impl_pointer  next()const{return trampoline::next();}
165 
implboost::multi_index::detail::sequenced_index_node166   impl_pointer impl()
167   {
168     return static_cast<impl_pointer>(
169       static_cast<impl_type*>(static_cast<trampoline*>(this)));
170   }
171 
implboost::multi_index::detail::sequenced_index_node172   const_impl_pointer impl()const
173   {
174     return static_cast<const_impl_pointer>(
175       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
176   }
177 
from_implboost::multi_index::detail::sequenced_index_node178   static sequenced_index_node* from_impl(impl_pointer x)
179   {
180     return
181       static_cast<sequenced_index_node*>(
182         static_cast<trampoline*>(
183           raw_ptr<impl_type*>(x)));
184   }
185 
from_implboost::multi_index::detail::sequenced_index_node186   static const sequenced_index_node* from_impl(const_impl_pointer x)
187   {
188     return
189       static_cast<const sequenced_index_node*>(
190         static_cast<const trampoline*>(
191           raw_ptr<const impl_type*>(x)));
192   }
193 
194   /* interoperability with bidir_node_iterator */
195 
incrementboost::multi_index::detail::sequenced_index_node196   static void increment(sequenced_index_node*& x)
197   {
198     impl_pointer xi=x->impl();
199     trampoline::increment(xi);
200     x=from_impl(xi);
201   }
202 
decrementboost::multi_index::detail::sequenced_index_node203   static void decrement(sequenced_index_node*& x)
204   {
205     impl_pointer xi=x->impl();
206     trampoline::decrement(xi);
207     x=from_impl(xi);
208   }
209 };
210 
211 } /* namespace multi_index::detail */
212 
213 } /* namespace multi_index */
214 
215 } /* namespace boost */
216 
217 #endif
218