1 /*=============================================================================
2 Copyright (c) 2001, Daniel C. Nuffer
3 Copyright (c) 2003, Hartmut Kaiser
4 http://spirit.sourceforge.net/
5
6 Distributed under the Boost Software License, Version 1.0. (See accompanying
7 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
8 =============================================================================*/
9 #ifndef BOOST_SPIRIT_CLASSIC_ITERATOR_FIXED_SIZE_QUEUE_HPP
10 #define BOOST_SPIRIT_CLASSIC_ITERATOR_FIXED_SIZE_QUEUE_HPP
11
12 #include <cstddef>
13 #include <cstdlib>
14 #include <iterator>
15
16 #include <boost/spirit/home/classic/namespace.hpp>
17 #include <boost/spirit/home/classic/core/assert.hpp> // for BOOST_SPIRIT_ASSERT
18
19 // FIXES for broken compilers
20 #include <boost/config.hpp>
21 #include <boost/iterator_adaptors.hpp>
22
23 #define BOOST_SPIRIT_ASSERT_FSQ_SIZE \
24 BOOST_SPIRIT_ASSERT(((m_tail + N + 1) - m_head) % (N+1) == m_size % (N+1)) \
25 /**/
26
27 ///////////////////////////////////////////////////////////////////////////////
28 namespace boost { namespace spirit {
29
30 BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
31
32 ///////////////////////////////////////////////////////////////////////////////
33 namespace impl {
34
35 #if !defined(BOOST_ITERATOR_ADAPTORS_VERSION) || \
36 BOOST_ITERATOR_ADAPTORS_VERSION < 0x0200
37 #error "Please use at least Boost V1.31.0 while compiling the fixed_size_queue class!"
38 #else // BOOST_ITERATOR_ADAPTORS_VERSION < 0x0200
39
40 template <typename QueueT, typename T, typename PointerT>
41 class fsq_iterator
42 : public boost::iterator_adaptor<
43 fsq_iterator<QueueT, T, PointerT>,
44 PointerT,
45 T,
46 std::random_access_iterator_tag
47 >
48 {
49 public:
50 typedef typename QueueT::position_t position;
51 typedef boost::iterator_adaptor<
52 fsq_iterator<QueueT, T, PointerT>, PointerT, T,
53 std::random_access_iterator_tag
54 > base_t;
55
56 fsq_iterator() {}
57 fsq_iterator(position const &p_) : p(p_) {}
58
59 position const &get_position() const { return p; }
60
61 private:
62 friend class boost::iterator_core_access;
63
64 typename base_t::reference dereference() const
65 {
66 return p.self->m_queue[p.pos];
67 }
68
69 void increment()
70 {
71 ++p.pos;
72 if (p.pos == QueueT::MAX_SIZE+1)
73 p.pos = 0;
74 }
75
76 void decrement()
77 {
78 if (p.pos == 0)
79 p.pos = QueueT::MAX_SIZE;
80 else
81 --p.pos;
82 }
83
84 template <
85 typename OtherDerivedT, typename OtherIteratorT,
86 typename V, typename C, typename R, typename D
87 >
88 bool equal(iterator_adaptor<OtherDerivedT, OtherIteratorT, V, C, R, D>
89 const &x) const
90 {
91 position const &rhs_pos =
92 static_cast<OtherDerivedT const &>(x).get_position();
93 return (p.self == rhs_pos.self) && (p.pos == rhs_pos.pos);
94 }
95
96 template <
97 typename OtherDerivedT, typename OtherIteratorT,
98 typename V, typename C, typename R, typename D
99 >
100 typename base_t::difference_type distance_to(
101 iterator_adaptor<OtherDerivedT, OtherIteratorT, V, C, R, D>
102 const &x) const
103 {
104 typedef typename base_t::difference_type diff_t;
105
106 position const &p2 =
107 static_cast<OtherDerivedT const &>(x).get_position();
108 std::size_t pos1 = p.pos;
109 std::size_t pos2 = p2.pos;
110
111 // Undefined behaviour if the iterators come from different
112 // containers
113 BOOST_SPIRIT_ASSERT(p.self == p2.self);
114
115 if (pos1 < p.self->m_head)
116 pos1 += QueueT::MAX_SIZE;
117 if (pos2 < p2.self->m_head)
118 pos2 += QueueT::MAX_SIZE;
119
120 if (pos2 > pos1)
121 return diff_t(pos2 - pos1);
122 else
123 return -diff_t(pos1 - pos2);
124 }
125
126 void advance(typename base_t::difference_type n)
127 {
128 // Notice that we don't care values of n that can
129 // wrap around more than one time, since it would
130 // be undefined behaviour anyway (going outside
131 // the begin/end range). Negative wrapping is a bit
132 // cumbersome because we don't want to case p.pos
133 // to signed.
134 if (n < 0)
135 {
136 n = -n;
137 if (p.pos < (std::size_t)n)
138 p.pos = QueueT::MAX_SIZE+1 - (n - p.pos);
139 else
140 p.pos -= n;
141 }
142 else
143 {
144 p.pos += n;
145 if (p.pos >= QueueT::MAX_SIZE+1)
146 p.pos -= QueueT::MAX_SIZE+1;
147 }
148 }
149
150 private:
151 position p;
152 };
153
154 #endif // BOOST_ITERATOR_ADAPTORS_VERSION < 0x0200
155
156 ///////////////////////////////////////////////////////////////////////////////
157 } /* namespace impl */
158
159 template <typename T, std::size_t N>
160 class fixed_size_queue
161 {
162 private:
163 struct position
164 {
165 fixed_size_queue* self;
166 std::size_t pos;
167
positionboost::spirit::fixed_size_queue::position168 position() : self(0), pos(0) {}
169
170 // The const_cast here is just to avoid to have two different
171 // position structures for the const and non-const case.
172 // The const semantic is guaranteed by the iterator itself
positionboost::spirit::fixed_size_queue::position173 position(const fixed_size_queue* s, std::size_t p)
174 : self(const_cast<fixed_size_queue*>(s)), pos(p)
175 {}
176 };
177
178 public:
179 // Declare the iterators
180 typedef impl::fsq_iterator<fixed_size_queue<T, N>, T, T*> iterator;
181 typedef impl::fsq_iterator<fixed_size_queue<T, N>, T const, T const*>
182 const_iterator;
183 typedef position position_t;
184
185 friend class impl::fsq_iterator<fixed_size_queue<T, N>, T, T*>;
186 friend class impl::fsq_iterator<fixed_size_queue<T, N>, T const, T const*>;
187
188 fixed_size_queue();
189 fixed_size_queue(const fixed_size_queue& x);
190 fixed_size_queue& operator=(const fixed_size_queue& x);
191 ~fixed_size_queue();
192
193 void push_back(const T& e);
194 void push_front(const T& e);
195 void serve(T& e);
196 void pop_front();
197
empty() const198 bool empty() const
199 {
200 return m_size == 0;
201 }
202
full() const203 bool full() const
204 {
205 return m_size == N;
206 }
207
begin()208 iterator begin()
209 {
210 return iterator(position(this, m_head));
211 }
212
begin() const213 const_iterator begin() const
214 {
215 return const_iterator(position(this, m_head));
216 }
217
end()218 iterator end()
219 {
220 return iterator(position(this, m_tail));
221 }
222
end() const223 const_iterator end() const
224 {
225 return const_iterator(position(this, m_tail));
226 }
227
size() const228 std::size_t size() const
229 {
230 return m_size;
231 }
232
front()233 T& front()
234 {
235 return m_queue[m_head];
236 }
237
front() const238 const T& front() const
239 {
240 return m_queue[m_head];
241 }
242
243 private:
244 // Redefine the template parameters to avoid using partial template
245 // specialization on the iterator policy to extract N.
246 BOOST_STATIC_CONSTANT(std::size_t, MAX_SIZE = N);
247
248 std::size_t m_head;
249 std::size_t m_tail;
250 std::size_t m_size;
251 T m_queue[N+1];
252 };
253
254 template <typename T, std::size_t N>
255 inline
fixed_size_queue()256 fixed_size_queue<T, N>::fixed_size_queue()
257 : m_head(0)
258 , m_tail(0)
259 , m_size(0)
260 {
261 BOOST_SPIRIT_ASSERT(m_size <= N+1);
262 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
263 BOOST_SPIRIT_ASSERT(m_head <= N+1);
264 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
265 }
266
267 template <typename T, std::size_t N>
268 inline
fixed_size_queue(const fixed_size_queue & x)269 fixed_size_queue<T, N>::fixed_size_queue(const fixed_size_queue& x)
270 : m_head(x.m_head)
271 , m_tail(x.m_tail)
272 , m_size(x.m_size)
273 {
274 copy(x.begin(), x.end(), begin());
275 BOOST_SPIRIT_ASSERT(m_size <= N+1);
276 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
277 BOOST_SPIRIT_ASSERT(m_head <= N+1);
278 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
279 }
280
281 template <typename T, std::size_t N>
282 inline fixed_size_queue<T, N>&
operator =(const fixed_size_queue & x)283 fixed_size_queue<T, N>::operator=(const fixed_size_queue& x)
284 {
285 if (this != &x)
286 {
287 m_head = x.m_head;
288 m_tail = x.m_tail;
289 m_size = x.m_size;
290 copy(x.begin(), x.end(), begin());
291 }
292 BOOST_SPIRIT_ASSERT(m_size <= N+1);
293 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
294 BOOST_SPIRIT_ASSERT(m_head <= N+1);
295 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
296
297 return *this;
298 }
299
300 template <typename T, std::size_t N>
301 inline
~fixed_size_queue()302 fixed_size_queue<T, N>::~fixed_size_queue()
303 {
304 BOOST_SPIRIT_ASSERT(m_size <= N+1);
305 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
306 BOOST_SPIRIT_ASSERT(m_head <= N+1);
307 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
308 }
309
310 template <typename T, std::size_t N>
311 inline void
push_back(const T & e)312 fixed_size_queue<T, N>::push_back(const T& e)
313 {
314 BOOST_SPIRIT_ASSERT(m_size <= N+1);
315 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
316 BOOST_SPIRIT_ASSERT(m_head <= N+1);
317 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
318
319 BOOST_SPIRIT_ASSERT(!full());
320
321 m_queue[m_tail] = e;
322 ++m_size;
323 ++m_tail;
324 if (m_tail == N+1)
325 m_tail = 0;
326
327
328 BOOST_SPIRIT_ASSERT(m_size <= N+1);
329 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
330 BOOST_SPIRIT_ASSERT(m_head <= N+1);
331 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
332 }
333
334 template <typename T, std::size_t N>
335 inline void
push_front(const T & e)336 fixed_size_queue<T, N>::push_front(const T& e)
337 {
338 BOOST_SPIRIT_ASSERT(m_size <= N+1);
339 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
340 BOOST_SPIRIT_ASSERT(m_head <= N+1);
341 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
342
343 BOOST_SPIRIT_ASSERT(!full());
344
345 if (m_head == 0)
346 m_head = N;
347 else
348 --m_head;
349
350 m_queue[m_head] = e;
351 ++m_size;
352
353 BOOST_SPIRIT_ASSERT(m_size <= N+1);
354 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
355 BOOST_SPIRIT_ASSERT(m_head <= N+1);
356 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
357 }
358
359
360 template <typename T, std::size_t N>
361 inline void
serve(T & e)362 fixed_size_queue<T, N>::serve(T& e)
363 {
364 BOOST_SPIRIT_ASSERT(m_size <= N+1);
365 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
366 BOOST_SPIRIT_ASSERT(m_head <= N+1);
367 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
368
369 e = m_queue[m_head];
370 pop_front();
371 }
372
373
374
375 template <typename T, std::size_t N>
376 inline void
pop_front()377 fixed_size_queue<T, N>::pop_front()
378 {
379 BOOST_SPIRIT_ASSERT(m_size <= N+1);
380 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
381 BOOST_SPIRIT_ASSERT(m_head <= N+1);
382 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
383
384 ++m_head;
385 if (m_head == N+1)
386 m_head = 0;
387 --m_size;
388
389 BOOST_SPIRIT_ASSERT(m_size <= N+1);
390 BOOST_SPIRIT_ASSERT_FSQ_SIZE;
391 BOOST_SPIRIT_ASSERT(m_head <= N+1);
392 BOOST_SPIRIT_ASSERT(m_tail <= N+1);
393 }
394
395 ///////////////////////////////////////////////////////////////////////////////
396 BOOST_SPIRIT_CLASSIC_NAMESPACE_END
397
398 }} // namespace BOOST_SPIRIT_CLASSIC_NS
399
400 #undef BOOST_SPIRIT_ASSERT_FSQ_SIZE
401
402 #endif
403