1 /* Copyright 2003-2007 Joaquín M López Muñoz.
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
12 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
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/prevent_eti.hpp>
23 namespace multi_index{
27 /* doubly-linked node for use by sequenced_index */
29 template<typename Allocator>
30 struct sequenced_index_node_impl
32 typedef typename prevent_eti<
34 typename boost::detail::allocator::rebind_to<
35 Allocator,sequenced_index_node_impl
37 >::type::pointer pointer;
38 typedef typename prevent_eti<
40 typename boost::detail::allocator::rebind_to<
41 Allocator,sequenced_index_node_impl
43 >::type::const_pointer const_pointer;
45 pointer& prior(){return prior_;}
46 pointer prior()const{return prior_;}
47 pointer& next(){return next_;}
48 pointer next()const{return next_;}
50 /* interoperability with bidir_node_iterator */
52 static void increment(pointer& x){x=x->next();}
53 static void decrement(pointer& x){x=x->prior();}
55 /* algorithmic stuff */
57 static void link(pointer x,pointer header)
59 x->prior()=header->prior();
61 x->prior()->next()=x->next()->prior()=x;
64 static void unlink(pointer x)
66 x->prior()->next()=x->next();
67 x->next()->prior()=x->prior();
70 static void relink(pointer position,pointer x)
73 x->prior()=position->prior();
75 x->prior()->next()=x->next()->prior()=x;
78 static void relink(pointer position,pointer x,pointer y)
80 /* position is assumed not to be in [x,y) */
85 y->prior()=x->prior();
86 x->prior()=position->prior();
93 static void reverse(pointer header)
98 std::swap(x->prior(),x->next());
103 static void swap(pointer x,pointer y)
105 /* This swap function does not exchange the header nodes,
106 * but rather their pointers. This is *not* used for implementing
107 * sequenced_index::swap.
112 std::swap(x->next(),y->next());
113 std::swap(x->prior(),y->prior());
114 x->next()->prior()=x->prior()->next()=x;
115 y->next()->prior()=y->prior()->next()=y;
119 y->prior()=x->prior();
120 x->next()=x->prior()=x;
121 y->next()->prior()=y->prior()->next()=y;
124 else if(y->next()!=y){
126 x->prior()=y->prior();
127 y->next()=y->prior()=y;
128 x->next()->prior()=x->prior()->next()=x;
137 template<typename Super>
138 struct sequenced_index_node_trampoline:
141 sequenced_index_node_impl<
142 typename boost::detail::allocator::rebind_to<
143 typename Super::allocator_type,
149 typedef typename prevent_eti<
151 sequenced_index_node_impl<
152 typename boost::detail::allocator::rebind_to<
153 typename Super::allocator_type,
160 template<typename Super>
161 struct sequenced_index_node:Super,sequenced_index_node_trampoline<Super>
164 typedef sequenced_index_node_trampoline<Super> trampoline;
167 typedef typename trampoline::impl_type impl_type;
168 typedef typename trampoline::pointer impl_pointer;
169 typedef typename trampoline::const_pointer const_impl_pointer;
171 impl_pointer& prior(){return trampoline::prior();}
172 impl_pointer prior()const{return trampoline::prior();}
173 impl_pointer& next(){return trampoline::next();}
174 impl_pointer next()const{return trampoline::next();}
178 return static_cast<impl_pointer>(
179 static_cast<impl_type*>(static_cast<trampoline*>(this)));
182 const_impl_pointer impl()const
184 return static_cast<const_impl_pointer>(
185 static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
188 static sequenced_index_node* from_impl(impl_pointer x)
190 return static_cast<sequenced_index_node*>(
191 static_cast<trampoline*>(&*x));
194 static const sequenced_index_node* from_impl(const_impl_pointer x)
196 return static_cast<const sequenced_index_node*>(
197 static_cast<const trampoline*>(&*x));
200 /* interoperability with bidir_node_iterator */
202 static void increment(sequenced_index_node*& x)
204 impl_pointer xi=x->impl();
205 trampoline::increment(xi);
209 static void decrement(sequenced_index_node*& x)
211 impl_pointer xi=x->impl();
212 trampoline::decrement(xi);
217 } /* namespace multi_index::detail */
219 } /* namespace multi_index */
221 } /* namespace boost */