1 /* Copyright 2003-2015 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_SEQ_INDEX_NODE_HPP
10 #define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_NODE_HPP
16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
18 #include <boost/detail/allocator_utilities.hpp>
19 #include <boost/multi_index/detail/raw_ptr.hpp>
23 namespace multi_index{
27 /* doubly-linked node for use by sequenced_index */
29 template<typename Allocator>
30 struct sequenced_index_node_impl
33 boost::detail::allocator::rebind_to<
34 Allocator,sequenced_index_node_impl
35 >::type::pointer pointer;
37 boost::detail::allocator::rebind_to<
38 Allocator,sequenced_index_node_impl
39 >::type::const_pointer const_pointer;
41 pointer& prior(){return prior_;}
42 pointer prior()const{return prior_;}
43 pointer& next(){return next_;}
44 pointer next()const{return next_;}
46 /* interoperability with bidir_node_iterator */
48 static void increment(pointer& x){x=x->next();}
49 static void decrement(pointer& x){x=x->prior();}
51 /* algorithmic stuff */
53 static void link(pointer x,pointer header)
55 x->prior()=header->prior();
57 x->prior()->next()=x->next()->prior()=x;
60 static void unlink(pointer x)
62 x->prior()->next()=x->next();
63 x->next()->prior()=x->prior();
66 static void relink(pointer position,pointer x)
69 x->prior()=position->prior();
71 x->prior()->next()=x->next()->prior()=x;
74 static void relink(pointer position,pointer x,pointer y)
76 /* position is assumed not to be in [x,y) */
81 y->prior()=x->prior();
82 x->prior()=position->prior();
89 static void reverse(pointer header)
94 std::swap(x->prior(),x->next());
99 static void swap(pointer x,pointer y)
101 /* This swap function does not exchange the header nodes,
102 * but rather their pointers. This is *not* used for implementing
103 * sequenced_index::swap.
108 std::swap(x->next(),y->next());
109 std::swap(x->prior(),y->prior());
110 x->next()->prior()=x->prior()->next()=x;
111 y->next()->prior()=y->prior()->next()=y;
115 y->prior()=x->prior();
116 x->next()=x->prior()=x;
117 y->next()->prior()=y->prior()->next()=y;
120 else if(y->next()!=y){
122 x->prior()=y->prior();
123 y->next()=y->prior()=y;
124 x->next()->prior()=x->prior()->next()=x;
133 template<typename Super>
134 struct sequenced_index_node_trampoline:
135 sequenced_index_node_impl<
136 typename boost::detail::allocator::rebind_to<
137 typename Super::allocator_type,
142 typedef sequenced_index_node_impl<
143 typename boost::detail::allocator::rebind_to<
144 typename Super::allocator_type,
150 template<typename Super>
151 struct sequenced_index_node:Super,sequenced_index_node_trampoline<Super>
154 typedef sequenced_index_node_trampoline<Super> trampoline;
157 typedef typename trampoline::impl_type impl_type;
158 typedef typename trampoline::pointer impl_pointer;
159 typedef typename trampoline::const_pointer const_impl_pointer;
161 impl_pointer& prior(){return trampoline::prior();}
162 impl_pointer prior()const{return trampoline::prior();}
163 impl_pointer& next(){return trampoline::next();}
164 impl_pointer next()const{return trampoline::next();}
168 return static_cast<impl_pointer>(
169 static_cast<impl_type*>(static_cast<trampoline*>(this)));
172 const_impl_pointer impl()const
174 return static_cast<const_impl_pointer>(
175 static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
178 static sequenced_index_node* from_impl(impl_pointer x)
181 static_cast<sequenced_index_node*>(
182 static_cast<trampoline*>(
183 raw_ptr<impl_type*>(x)));
186 static const sequenced_index_node* from_impl(const_impl_pointer x)
189 static_cast<const sequenced_index_node*>(
190 static_cast<const trampoline*>(
191 raw_ptr<const impl_type*>(x)));
194 /* interoperability with bidir_node_iterator */
196 static void increment(sequenced_index_node*& x)
198 impl_pointer xi=x->impl();
199 trampoline::increment(xi);
203 static void decrement(sequenced_index_node*& x)
205 impl_pointer xi=x->impl();
206 trampoline::decrement(xi);
211 } /* namespace multi_index::detail */
213 } /* namespace multi_index */
215 } /* namespace boost */