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
21namespace boost{
22
23namespace multi_index{
24
25namespace detail{
26
27/* doubly-linked node for use by sequenced_index */
28
29template<typename Allocator>
30struct 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
40 pointer& prior(){return prior_;}
41 pointer prior()const{return prior_;}
42 pointer& next(){return next_;}
43 pointer next()const{return next_;}
44
45 /* interoperability with bidir_node_iterator */
46
47 static void increment(pointer& x){x=x->next();}
48 static void decrement(pointer& x){x=x->prior();}
49
50 /* algorithmic stuff */
51
52 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
59 static void unlink(pointer x)
60 {
61 x->prior()->next()=x->next();
62 x->next()->prior()=x->prior();
63 }
64
65 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
73 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
88 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
98 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
127private:
128 pointer prior_;
129 pointer next_;
130};
131
132template<typename Super>
133struct 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
149template<typename Super>
150struct sequenced_index_node:Super,sequenced_index_node_trampoline<Super>
151{
152private:
153 typedef sequenced_index_node_trampoline<Super> trampoline;
154
155public:
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
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();}
165
166 impl_pointer impl()
167 {
168 return static_cast<impl_pointer>(
169 static_cast<impl_type*>(static_cast<trampoline*>(this)));
170 }
171
172 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
178 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
186 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
196 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
203 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

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