1/*
2 * Copyright (c) 2017-2018 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder. You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
13 *
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions are
16 * met: redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer;
18 * redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution;
21 * neither the name of the copyright holders nor the names of its
22 * contributors may be used to endorse or promote products derived from
23 * this software without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 *
37 * Authors: Rekai Gonzalez-Alberquilla
38 */
39
40#ifndef __BASE_CIRCULAR_QUEUE_HH__
41#define __BASE_CIRCULAR_QUEUE_HH__
42
43#include <vector>
44
45/** Circular queue.
46 * Circular queue implemented on top of a standard vector. Instead of using
47 * a sentinel entry, we use a boolean to distinguish the case in which the
48 * queue is full or empty.
49 * Thus, a circular queue is represented by the 5-tuple
50 * (Capacity, IsEmpty?, Head, Tail, Round)
51 * Where:
52 * - Capacity is the size of the underlying vector.
53 * - IsEmpty? can be T or F.
54 * - Head is the index in the vector of the first element of the queue.
55 * - Tail is the index in the vector of the last element of the queue.
56 * - Round is the counter of how many times the Tail has wrapped around.
57 * A queue is empty when
58 * Head == (Tail + 1 mod Capacity) && IsEmpty?.
59 * Conversely, a queue if full when
60 * Head == (Tail + 1 mod Capacity) && !IsEmpty?.
61 * Comments may show depictions of the underlying vector in the following
62 * format: '|' delimit the 'cells' of the underlying vector. '-' represents
63 * an element of the vector that is out-of-bounds of the circular queue,
64 * while 'o' represents and element that is inside the bounds. The
65 * characters '[' and ']' are added to mark the entries that hold the head
66 * and tail of the circular queue respectively.
67 * E.g.:
68 * - Empty queues of capacity 4:
69 * (4,T,1,0,_): |-]|[-|-|-| (4,T,3,2): |-|-|-]|[-|
70 * - Full queues of capacity 4:
71 * (4,F,1,0,_): |o]|[o|o|o| (4,F,3,2): |o|o|o]|[o|
72 * - Queues of capacity 4 with 2 elements:
73 * (4,F,0,1,_): |[o|o]|-|-| (4,F,3,0): |o]|-|-|[o|
74 *
75 * The Round number is only relevant for checking validity of indices,
76 * therefore it will be omitted or shown as '_'
77 */
78template <typename T>
79class CircularQueue : private std::vector<T>
80{
81 protected:
82 using Base = std::vector<T>;
83 using typename Base::reference;
84 using typename Base::const_reference;
85 const uint32_t _capacity;
86 uint32_t _head;
87 uint32_t _tail;
88 uint32_t _empty;
89
90 /** Counter for how many times the tail wraps around.
91 * Some parts of the code rely on getting the past the end iterator, and
92 * expect to use it after inserting on the tail. To support this without
93 * ambiguity, we need the round number to guarantee that it did not become
94 * a before-the-beginning iterator.
95 */
96 uint32_t _round;
97
98 /** General modular addition. */
99 static uint32_t
100 moduloAdd(uint32_t op1, uint32_t op2, uint32_t size)
101 {
102 return (op1 + op2) % size;
103 }
104
105 /** General modular subtraction. */
106 static uint32_t
107 moduloSub(uint32_t op1, uint32_t op2, uint32_t size)
108 {
109 int ret = (uint32_t)(op1 - op2) % size;
110 return ret >= 0 ? ret : ret + size;
111 }
112
113 void increase(uint32_t& v, size_t delta = 1)
114 {
115 v = moduloAdd(v, delta, _capacity);
116 }
117
118 void decrease(uint32_t& v)
119 {
120 v = (v ? v : _capacity) - 1;
121 }
122
123 /** Iterator to the circular queue.
124 * iterator implementation to provide the circular-ness that the
125 * standard std::vector<T>::iterator does not implement.
126 * Iterators to a queue are represented by a pair of a character and the
127 * round counter. For the character, '*' denotes the element pointed to by
128 * the iterator if it is valid. 'x' denotes the element pointed to by the
129 * iterator when it is BTB or PTE.
130 * E.g.:
131 * - Iterator to the head of a queue of capacity 4 with 2 elems.
132 * (4,F,0,1,R): |[(*,R)|o]|-|-| (4,F,3,0): |o]|-|-|[(*,R)|
133 * - Iterator to the tail of a queue of capacity 4 with 2 elems.
134 * (4,F,0,1,R): |[o|(*,R)]|-|-| (4,F,3,0): |(*,R)]|-|-|[o|
135 * - Iterator to the end of a queue of capacity 4 with 2 elems.
136 * (4,F,0,1,R): |[o|o]|(x,R)|-| (4,F,3,0): |o]|(x,R)|-|[o|
137 */
138 public:
139 struct iterator {
140 CircularQueue* _cq;
141 uint32_t _idx;
142 uint32_t _round;
143
144 public:
145 iterator(CircularQueue* cq, uint32_t idx, uint32_t round)
146 : _cq(cq), _idx(idx), _round(round) {}
147
148 /** Iterator Traits */
149 using value_type = T;
150 using difference_type = std::ptrdiff_t;
151 using reference = value_type&;
152 using const_reference = const value_type&;
153 using pointer = value_type*;
154 using const_pointer = const value_type*;
155 using iterator_category = std::random_access_iterator_tag;
156
157 /** Trait reference type
158 * iterator satisfies OutputIterator, therefore reference
159 * must be T& */
160 static_assert(std::is_same<reference, T&>::value,
161 "reference type is not assignable as required");
162
163 iterator() : _cq(nullptr), _idx(0), _round(0) { }
164
165 iterator(const iterator& it)
166 : _cq(it._cq), _idx(it._idx), _round(it._round) {}
167
168 iterator&
169 operator=(const iterator& it)
170 {
171 _cq = it._cq;
172 _idx = it._idx;
173 _round = it._round;
174 return *this;
175 }
176
177 ~iterator() { _cq = nullptr; _idx = 0; _round = 0; }
178
179 /** Test dereferenceability.
180 * An iterator is dereferenceable if it is pointing to a non-null
181 * circular queue, it is not the past-the-end iterator and the
182 * index is a valid index to that queue. PTE test is required to
183 * distinguish between:
184 * - An iterator to the first element of a full queue
185 * (4,F,1,0): |o]|[*|o|o|
186 * - The end() iterator of a full queue
187 * (4,F,1,0): |o]|x[o|o|o|
188 * Sometimes, though, users will get the PTE iterator and expect it
189 * to work after growing the buffer on the tail, so we have to
190 * check if the iterator is still PTE.
191 */
192 bool
193 dereferenceable() const
194 {
195 return _cq != nullptr && _cq->isValidIdx(_idx, _round);
196 }
197
198 /** InputIterator. */
199
200 /** Equality operator.
201 * Two iterators must point to the same, possibly null, circular
202 * queue and the same element on it, including PTE, to be equal.
203 * In case the clients the the PTE iterator and then grow on the back
204 * and expect it to work, we have to check if the PTE is still PTE
205 */
206 bool operator==(const iterator& that) const
207 {
208 return _cq == that._cq && _idx == that._idx &&
209 _round == that._round;
210 }
211
212 /** Inequality operator.
213 * Conversely, two iterators are different if they both point to
214 * different circular queues or they point to different elements.
215 */
216 bool operator!=(const iterator& that)
217 {
218 return !(*this == that);
219 }
220
221 /** Dereference operator. */
222 reference operator*()
223 {
224 /* this has to be dereferenceable. */
225 return (*_cq)[_idx];
226 }
227
228 const_reference operator*() const
229 {
230 /* this has to be dereferenceable. */
231 return (*_cq)[_idx];
232 }
233
234 /** Dereference operator.
235 * Rely on operator* to check for dereferenceability.
236 */
237 pointer operator->()
238 {
239 return &((*_cq)[_idx]);
240 }
241
242 const_pointer operator->() const
243 {
244 return &((*_cq)[_idx]);
245 }
246
247 /** Pre-increment operator. */
248 iterator& operator++()
249 {
250 /* this has to be dereferenceable. */
251 _cq->increase(_idx);
252 if (_idx == 0)
253 ++_round;
254 return *this;
255 }
256
257 /** Post-increment operator. */
258 iterator
259 operator++(int)
260 {
261 iterator t = *this;
262 ++*this;
263 return t;
264 }
265
266 /** ForwardIterator
267 * The multipass guarantee is provided by the reliance on _idx.
268 */
269
270 /** BidirectionalIterator requirements. */
271 private:
272 /** Test decrementability.
273 * An iterator to a non-null circular queue is not-decrementable
274 * if it is pointing to the head element, unless the queue is full
275 * and we are talking about the past-the-end iterator. In that case,
276 * the iterator round equals the cq round unless the head is at the
277 * zero position and the round is one more than the cq round.
278 */
279 bool
280 decrementable() const
281 {
282 return _cq && !(_idx == _cq->head() &&
283 (_cq->empty() ||
284 (_idx == 0 && _round != _cq->_round + 1) ||
285 (_idx !=0 && _round != _cq->_round)));
286 }
287
288 public:
289 /** Pre-decrement operator. */
290 iterator& operator--()
291 {
292 /* this has to be decrementable. */
293 assert(decrementable());
294 if (_idx == 0)
295 --_round;
296 _cq->decrease(_idx);
297 return *this;
298 }
299
300 /** Post-decrement operator. */
301 iterator operator--(int ) { iterator t = *this; --*this; return t; }
302
303 /** RandomAccessIterator requirements.*/
304 iterator& operator+=(const difference_type& t)
305 {
306 assert(_cq);
307 _round += (t + _idx) / _cq->capacity();
308 _idx = _cq->moduloAdd(_idx, t);
309 return *this;
310 }
311
312 iterator& operator-=(const difference_type& t)
313 {
314 assert(_cq);
315
316 /* C does not do euclidean division, so we have to adjust */
317 if (t >= 0)
318 _round += (-t + _idx) / _cq->capacity();
319 else
320 _round += (-t + _idx - _cq->capacity() + 1) / _cq->capacity();
321
322 _idx = _cq->moduloSub(_idx, t);
323 return *this;
324 }
325
326 /** Addition operator. */
327 iterator operator+(const difference_type& t)
328 {
329 iterator ret(*this);
330 return ret += t;
331 }
332
333 friend iterator operator+(const difference_type& t, iterator& it)
334 {
335 iterator ret = it;
336 return ret += t;
337 }
338
339 /** Substraction operator. */
340 iterator operator-(const difference_type& t)
341 {
342 iterator ret(*this);
343 return ret -= t;
344 }
345
346 friend iterator operator-(const difference_type& t, iterator& it)
347 {
348 iterator ret = it;
349 return ret -= t;
350 }
351
352 /** Difference operator.
353 * that + ret == this
354 */
355 difference_type operator-(const iterator& that)
356 {
357 /* If a is already at the end, we can safely return 0. */
358 auto ret = _cq->moduloSub(this->_idx, that._idx);
359
360 if (ret == 0 && this->_round != that._round) {
361 ret += this->_round * _cq->capacity();
362 }
363 return ret;
364 }
365
366 /** Index operator.
367 * The use of * tests for dereferenceability.
368 */
369 template<typename Idx>
370 typename std::enable_if<std::is_integral<Idx>::value,reference>::type
371 operator[](const Idx& index) { return *(*this + index); }
372
373 /** Comparisons. */
374 bool
375 operator<(const iterator& that) const
376 {
377 assert(_cq && that._cq == _cq);
378 return (this->_round < that._round) ||
379 (this->_round == that._round && _idx < that._idx);
380 }
381
382 bool
383 operator>(const iterator& that) const
384 { return !(*this <= that); }
385
386 bool operator>=(const iterator& that) const
387 { return !(*this < that); }
388
389 bool operator<=(const iterator& that) const
390 { return !(that < *this); }
391
392 /** OutputIterator has no extra requirements.*/
393 size_t idx() const { return _idx; }
394 };
395
396 public:
| 1/*
2 * Copyright (c) 2017-2018 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder. You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
13 *
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions are
16 * met: redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer;
18 * redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution;
21 * neither the name of the copyright holders nor the names of its
22 * contributors may be used to endorse or promote products derived from
23 * this software without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 *
37 * Authors: Rekai Gonzalez-Alberquilla
38 */
39
40#ifndef __BASE_CIRCULAR_QUEUE_HH__
41#define __BASE_CIRCULAR_QUEUE_HH__
42
43#include <vector>
44
45/** Circular queue.
46 * Circular queue implemented on top of a standard vector. Instead of using
47 * a sentinel entry, we use a boolean to distinguish the case in which the
48 * queue is full or empty.
49 * Thus, a circular queue is represented by the 5-tuple
50 * (Capacity, IsEmpty?, Head, Tail, Round)
51 * Where:
52 * - Capacity is the size of the underlying vector.
53 * - IsEmpty? can be T or F.
54 * - Head is the index in the vector of the first element of the queue.
55 * - Tail is the index in the vector of the last element of the queue.
56 * - Round is the counter of how many times the Tail has wrapped around.
57 * A queue is empty when
58 * Head == (Tail + 1 mod Capacity) && IsEmpty?.
59 * Conversely, a queue if full when
60 * Head == (Tail + 1 mod Capacity) && !IsEmpty?.
61 * Comments may show depictions of the underlying vector in the following
62 * format: '|' delimit the 'cells' of the underlying vector. '-' represents
63 * an element of the vector that is out-of-bounds of the circular queue,
64 * while 'o' represents and element that is inside the bounds. The
65 * characters '[' and ']' are added to mark the entries that hold the head
66 * and tail of the circular queue respectively.
67 * E.g.:
68 * - Empty queues of capacity 4:
69 * (4,T,1,0,_): |-]|[-|-|-| (4,T,3,2): |-|-|-]|[-|
70 * - Full queues of capacity 4:
71 * (4,F,1,0,_): |o]|[o|o|o| (4,F,3,2): |o|o|o]|[o|
72 * - Queues of capacity 4 with 2 elements:
73 * (4,F,0,1,_): |[o|o]|-|-| (4,F,3,0): |o]|-|-|[o|
74 *
75 * The Round number is only relevant for checking validity of indices,
76 * therefore it will be omitted or shown as '_'
77 */
78template <typename T>
79class CircularQueue : private std::vector<T>
80{
81 protected:
82 using Base = std::vector<T>;
83 using typename Base::reference;
84 using typename Base::const_reference;
85 const uint32_t _capacity;
86 uint32_t _head;
87 uint32_t _tail;
88 uint32_t _empty;
89
90 /** Counter for how many times the tail wraps around.
91 * Some parts of the code rely on getting the past the end iterator, and
92 * expect to use it after inserting on the tail. To support this without
93 * ambiguity, we need the round number to guarantee that it did not become
94 * a before-the-beginning iterator.
95 */
96 uint32_t _round;
97
98 /** General modular addition. */
99 static uint32_t
100 moduloAdd(uint32_t op1, uint32_t op2, uint32_t size)
101 {
102 return (op1 + op2) % size;
103 }
104
105 /** General modular subtraction. */
106 static uint32_t
107 moduloSub(uint32_t op1, uint32_t op2, uint32_t size)
108 {
109 int ret = (uint32_t)(op1 - op2) % size;
110 return ret >= 0 ? ret : ret + size;
111 }
112
113 void increase(uint32_t& v, size_t delta = 1)
114 {
115 v = moduloAdd(v, delta, _capacity);
116 }
117
118 void decrease(uint32_t& v)
119 {
120 v = (v ? v : _capacity) - 1;
121 }
122
123 /** Iterator to the circular queue.
124 * iterator implementation to provide the circular-ness that the
125 * standard std::vector<T>::iterator does not implement.
126 * Iterators to a queue are represented by a pair of a character and the
127 * round counter. For the character, '*' denotes the element pointed to by
128 * the iterator if it is valid. 'x' denotes the element pointed to by the
129 * iterator when it is BTB or PTE.
130 * E.g.:
131 * - Iterator to the head of a queue of capacity 4 with 2 elems.
132 * (4,F,0,1,R): |[(*,R)|o]|-|-| (4,F,3,0): |o]|-|-|[(*,R)|
133 * - Iterator to the tail of a queue of capacity 4 with 2 elems.
134 * (4,F,0,1,R): |[o|(*,R)]|-|-| (4,F,3,0): |(*,R)]|-|-|[o|
135 * - Iterator to the end of a queue of capacity 4 with 2 elems.
136 * (4,F,0,1,R): |[o|o]|(x,R)|-| (4,F,3,0): |o]|(x,R)|-|[o|
137 */
138 public:
139 struct iterator {
140 CircularQueue* _cq;
141 uint32_t _idx;
142 uint32_t _round;
143
144 public:
145 iterator(CircularQueue* cq, uint32_t idx, uint32_t round)
146 : _cq(cq), _idx(idx), _round(round) {}
147
148 /** Iterator Traits */
149 using value_type = T;
150 using difference_type = std::ptrdiff_t;
151 using reference = value_type&;
152 using const_reference = const value_type&;
153 using pointer = value_type*;
154 using const_pointer = const value_type*;
155 using iterator_category = std::random_access_iterator_tag;
156
157 /** Trait reference type
158 * iterator satisfies OutputIterator, therefore reference
159 * must be T& */
160 static_assert(std::is_same<reference, T&>::value,
161 "reference type is not assignable as required");
162
163 iterator() : _cq(nullptr), _idx(0), _round(0) { }
164
165 iterator(const iterator& it)
166 : _cq(it._cq), _idx(it._idx), _round(it._round) {}
167
168 iterator&
169 operator=(const iterator& it)
170 {
171 _cq = it._cq;
172 _idx = it._idx;
173 _round = it._round;
174 return *this;
175 }
176
177 ~iterator() { _cq = nullptr; _idx = 0; _round = 0; }
178
179 /** Test dereferenceability.
180 * An iterator is dereferenceable if it is pointing to a non-null
181 * circular queue, it is not the past-the-end iterator and the
182 * index is a valid index to that queue. PTE test is required to
183 * distinguish between:
184 * - An iterator to the first element of a full queue
185 * (4,F,1,0): |o]|[*|o|o|
186 * - The end() iterator of a full queue
187 * (4,F,1,0): |o]|x[o|o|o|
188 * Sometimes, though, users will get the PTE iterator and expect it
189 * to work after growing the buffer on the tail, so we have to
190 * check if the iterator is still PTE.
191 */
192 bool
193 dereferenceable() const
194 {
195 return _cq != nullptr && _cq->isValidIdx(_idx, _round);
196 }
197
198 /** InputIterator. */
199
200 /** Equality operator.
201 * Two iterators must point to the same, possibly null, circular
202 * queue and the same element on it, including PTE, to be equal.
203 * In case the clients the the PTE iterator and then grow on the back
204 * and expect it to work, we have to check if the PTE is still PTE
205 */
206 bool operator==(const iterator& that) const
207 {
208 return _cq == that._cq && _idx == that._idx &&
209 _round == that._round;
210 }
211
212 /** Inequality operator.
213 * Conversely, two iterators are different if they both point to
214 * different circular queues or they point to different elements.
215 */
216 bool operator!=(const iterator& that)
217 {
218 return !(*this == that);
219 }
220
221 /** Dereference operator. */
222 reference operator*()
223 {
224 /* this has to be dereferenceable. */
225 return (*_cq)[_idx];
226 }
227
228 const_reference operator*() const
229 {
230 /* this has to be dereferenceable. */
231 return (*_cq)[_idx];
232 }
233
234 /** Dereference operator.
235 * Rely on operator* to check for dereferenceability.
236 */
237 pointer operator->()
238 {
239 return &((*_cq)[_idx]);
240 }
241
242 const_pointer operator->() const
243 {
244 return &((*_cq)[_idx]);
245 }
246
247 /** Pre-increment operator. */
248 iterator& operator++()
249 {
250 /* this has to be dereferenceable. */
251 _cq->increase(_idx);
252 if (_idx == 0)
253 ++_round;
254 return *this;
255 }
256
257 /** Post-increment operator. */
258 iterator
259 operator++(int)
260 {
261 iterator t = *this;
262 ++*this;
263 return t;
264 }
265
266 /** ForwardIterator
267 * The multipass guarantee is provided by the reliance on _idx.
268 */
269
270 /** BidirectionalIterator requirements. */
271 private:
272 /** Test decrementability.
273 * An iterator to a non-null circular queue is not-decrementable
274 * if it is pointing to the head element, unless the queue is full
275 * and we are talking about the past-the-end iterator. In that case,
276 * the iterator round equals the cq round unless the head is at the
277 * zero position and the round is one more than the cq round.
278 */
279 bool
280 decrementable() const
281 {
282 return _cq && !(_idx == _cq->head() &&
283 (_cq->empty() ||
284 (_idx == 0 && _round != _cq->_round + 1) ||
285 (_idx !=0 && _round != _cq->_round)));
286 }
287
288 public:
289 /** Pre-decrement operator. */
290 iterator& operator--()
291 {
292 /* this has to be decrementable. */
293 assert(decrementable());
294 if (_idx == 0)
295 --_round;
296 _cq->decrease(_idx);
297 return *this;
298 }
299
300 /** Post-decrement operator. */
301 iterator operator--(int ) { iterator t = *this; --*this; return t; }
302
303 /** RandomAccessIterator requirements.*/
304 iterator& operator+=(const difference_type& t)
305 {
306 assert(_cq);
307 _round += (t + _idx) / _cq->capacity();
308 _idx = _cq->moduloAdd(_idx, t);
309 return *this;
310 }
311
312 iterator& operator-=(const difference_type& t)
313 {
314 assert(_cq);
315
316 /* C does not do euclidean division, so we have to adjust */
317 if (t >= 0)
318 _round += (-t + _idx) / _cq->capacity();
319 else
320 _round += (-t + _idx - _cq->capacity() + 1) / _cq->capacity();
321
322 _idx = _cq->moduloSub(_idx, t);
323 return *this;
324 }
325
326 /** Addition operator. */
327 iterator operator+(const difference_type& t)
328 {
329 iterator ret(*this);
330 return ret += t;
331 }
332
333 friend iterator operator+(const difference_type& t, iterator& it)
334 {
335 iterator ret = it;
336 return ret += t;
337 }
338
339 /** Substraction operator. */
340 iterator operator-(const difference_type& t)
341 {
342 iterator ret(*this);
343 return ret -= t;
344 }
345
346 friend iterator operator-(const difference_type& t, iterator& it)
347 {
348 iterator ret = it;
349 return ret -= t;
350 }
351
352 /** Difference operator.
353 * that + ret == this
354 */
355 difference_type operator-(const iterator& that)
356 {
357 /* If a is already at the end, we can safely return 0. */
358 auto ret = _cq->moduloSub(this->_idx, that._idx);
359
360 if (ret == 0 && this->_round != that._round) {
361 ret += this->_round * _cq->capacity();
362 }
363 return ret;
364 }
365
366 /** Index operator.
367 * The use of * tests for dereferenceability.
368 */
369 template<typename Idx>
370 typename std::enable_if<std::is_integral<Idx>::value,reference>::type
371 operator[](const Idx& index) { return *(*this + index); }
372
373 /** Comparisons. */
374 bool
375 operator<(const iterator& that) const
376 {
377 assert(_cq && that._cq == _cq);
378 return (this->_round < that._round) ||
379 (this->_round == that._round && _idx < that._idx);
380 }
381
382 bool
383 operator>(const iterator& that) const
384 { return !(*this <= that); }
385
386 bool operator>=(const iterator& that) const
387 { return !(*this < that); }
388
389 bool operator<=(const iterator& that) const
390 { return !(that < *this); }
391
392 /** OutputIterator has no extra requirements.*/
393 size_t idx() const { return _idx; }
394 };
395
396 public:
|
398
399 explicit CircularQueue(uint32_t size = 0)
400 : _capacity(size), _head(1), _tail(0), _empty(true), _round(0)
401 {
402 Base::resize(size);
403 }
404
405 /**
406 * Remove all the elements in the queue.
407 *
408 * Note: This does not actually remove elements from the backing
409 * store.
410 */
411 void flush()
412 {
413 _head = 1;
414 _round = 0;
415 _tail = 0;
416 _empty = true;
417 }
418
419 /** Test if the index is in the range of valid elements. */
420 bool isValidIdx(size_t idx) const
421 {
422 /* An index is invalid if:
423 * - The queue is empty.
424 * (6,T,3,2): |-|-|-]|[-|-|x|
425 * - head is small than tail and:
426 * - It is greater than both head and tail.
427 * (6,F,1,3): |-|[o|o|o]|-|x|
428 * - It is less than both head and tail.
429 * (6,F,1,3): |x|[o|o|o]|-|-|
430 * - It is greater than the tail and not than the head.
431 * (6,F,4,1): |o|o]|-|x|[o|o|
432 */
433 return !(_empty || (
434 (_head < _tail) && (
435 (_head < idx && _tail < idx) ||
436 (_head > idx && _tail > idx)
437 )) || (_tail < idx && idx < _head));
438 }
439
440 /** Test if the index is in the range of valid elements.
441 * The round counter is used to disambiguate aliasing.
442 */
443 bool isValidIdx(size_t idx, uint32_t round) const
444 {
445 /* An index is valid if:
446 * - The queue is not empty.
447 * - round == R and
448 * - index <= tail (if index > tail, that would be PTE)
449 * - Either:
450 * - head <= index
451 * (6,F,1,3,R): |-|[o|(*,r)|o]|-|-|
452 * - head > tail
453 * (6,F,5,3,R): |o|o|(*,r)|o]|-|[o|
454 * The remaining case means the the iterator is BTB:
455 * (6,F,3,4,R): |-|-|(x,r)|[o|o]|-|
456 * - round + 1 == R and:
457 * - index > tail. If index <= tail, that would be BTB:
458 * (6,F,2,3,r): | -|- |[(*,r)|o]|-|-|
459 * (6,F,0,1,r+1): |[o|o]| (x,r)|- |-|-|
460 * (6,F,0,3,r+1): |[o|o | (*,r)|o]|-|-|
461 * - index >= head. If index < head, that would be BTB:
462 * (6,F,5,2,R): |o|o]|-|-|(x,r)|[o|
463 * - head > tail. If head <= tail, that would be BTB:
464 * (6,F,3,4,R): |[o|o]|(x,r)|-|-|-|
465 * Other values of the round meand that the index is PTE or BTB
466 */
467 return (!_empty && (
468 (round == _round && idx <= _tail && (
469 _head <= idx || _head > _tail)) ||
470 (round + 1 == _round &&
471 idx > _tail &&
472 idx >= _head &&
473 _head > _tail)
474 ));
475 }
476
477 reference front() { return (*this)[_head]; }
478 reference back() { return (*this)[_tail]; }
479 uint32_t head() const { return _head; }
480 uint32_t tail() const { return _tail; }
481 size_t capacity() const { return _capacity; }
482
483 uint32_t size() const
484 {
485 if (_empty)
486 return 0;
487 else if (_head <= _tail)
488 return _tail - _head + 1;
489 else
490 return _capacity - _head + _tail + 1;
491 }
492
493 uint32_t moduloAdd(uint32_t s1, uint32_t s2) const
494 {
495 return moduloAdd(s1, s2, _capacity);
496 }
497
498 uint32_t moduloSub(uint32_t s1, uint32_t s2) const
499 {
500 return moduloSub(s1, s2, _capacity);
501 }
502
503 /** Circularly increase the head pointer.
504 * By increasing the head pointer we are removing elements from
505 * the begin of the circular queue.
506 * Check that the queue is not empty. And set it to empty if it
507 * had only one value prior to insertion.
508 *
509 * @params num_elem number of elements to remove
510 */
511 void pop_front(size_t num_elem = 1)
512 {
513 if (num_elem == 0) return;
514 auto hIt = begin();
515 hIt += num_elem;
516 assert(hIt <= end());
517 _empty = hIt == end();
518 _head = hIt._idx;
519 }
520
521 /** Circularly decrease the tail pointer. */
522 void pop_back()
523 {
524 assert (!_empty);
525 _empty = _head == _tail;
526 if (_tail == 0)
527 --_round;
528 decrease(_tail);
529 }
530
531 /** Pushes an element at the end of the queue. */
532 void push_back(typename Base::value_type val)
533 {
534 advance_tail();
535 (*this)[_tail] = val;
536 }
537
538 /** Increases the tail by one.
539 * Check for wrap-arounds to update the round counter.
540 */
541 void advance_tail()
542 {
543 increase(_tail);
544 if (_tail == 0)
545 ++_round;
546
547 if (_tail == _head && !_empty)
548 increase(_head);
549
550 _empty = false;
551 }
552
553 /** Increases the tail by a specified number of steps
554 *
555 * @param len Number of steps
556 */
557 void advance_tail(uint32_t len)
558 {
559 for (auto idx = 0; idx < len; idx++)
560 advance_tail();
561 }
562
563 /** Is the queue empty? */
564 bool empty() const { return _empty; }
565
566 /** Is the queue full?
567 * A queue is full if the head is the 0^{th} element and the tail is
568 * the (size-1)^{th} element, or if the head is the n^{th} element and
569 * the tail the (n-1)^{th} element.
570 */
571 bool full() const
572 {
573 return !_empty &&
574 (_tail + 1 == _head || (_tail + 1 == _capacity && _head == 0));
575 }
576
577 /** Iterators. */
578 iterator begin()
579 {
580 if (_empty)
581 return end();
582 else if (_head > _tail)
583 return iterator(this, _head, _round - 1);
584 else
585 return iterator(this, _head, _round);
586 }
587
588 /* TODO: This should return a const_iterator. */
589 iterator begin() const
590 {
591 if (_empty)
592 return end();
593 else if (_head > _tail)
594 return iterator(const_cast<CircularQueue*>(this), _head,
595 _round - 1);
596 else
597 return iterator(const_cast<CircularQueue*>(this), _head,
598 _round);
599 }
600
601 iterator end()
602 {
603 auto poi = moduloAdd(_tail, 1);
604 auto round = _round;
605 if (poi == 0)
606 ++round;
607 return iterator(this, poi, round);
608 }
609
610 iterator end() const
611 {
612 auto poi = moduloAdd(_tail, 1);
613 auto round = _round;
614 if (poi == 0)
615 ++round;
616 return iterator(const_cast<CircularQueue*>(this), poi, round);
617 }
618
619 /** Return an iterator to an index in the vector.
620 * This poses the problem of round determination. By convention, the round
621 * is picked so that isValidIndex(idx, round) is true. If that is not
622 * possible, then the round value is _round, unless _tail is at the end of
623 * the storage, in which case the PTE wraps up and becomes _round + 1
624 */
625 iterator getIterator(size_t idx)
626 {
627 assert(isValidIdx(idx) || moduloAdd(_tail, 1) == idx);
628 if (_empty)
629 return end();
630
631 uint32_t round = _round;
632 if (idx > _tail) {
633 if (idx >= _head && _head > _tail) {
634 round -= 1;
635 }
636 } else if (idx < _head && _tail + 1 == _capacity) {
637 round += 1;
638 }
639 return iterator(this, idx, round);
640 }
641};
642
643#endif /* __BASE_CIRCULARQUEUE_HH__ */
| 398
399 explicit CircularQueue(uint32_t size = 0)
400 : _capacity(size), _head(1), _tail(0), _empty(true), _round(0)
401 {
402 Base::resize(size);
403 }
404
405 /**
406 * Remove all the elements in the queue.
407 *
408 * Note: This does not actually remove elements from the backing
409 * store.
410 */
411 void flush()
412 {
413 _head = 1;
414 _round = 0;
415 _tail = 0;
416 _empty = true;
417 }
418
419 /** Test if the index is in the range of valid elements. */
420 bool isValidIdx(size_t idx) const
421 {
422 /* An index is invalid if:
423 * - The queue is empty.
424 * (6,T,3,2): |-|-|-]|[-|-|x|
425 * - head is small than tail and:
426 * - It is greater than both head and tail.
427 * (6,F,1,3): |-|[o|o|o]|-|x|
428 * - It is less than both head and tail.
429 * (6,F,1,3): |x|[o|o|o]|-|-|
430 * - It is greater than the tail and not than the head.
431 * (6,F,4,1): |o|o]|-|x|[o|o|
432 */
433 return !(_empty || (
434 (_head < _tail) && (
435 (_head < idx && _tail < idx) ||
436 (_head > idx && _tail > idx)
437 )) || (_tail < idx && idx < _head));
438 }
439
440 /** Test if the index is in the range of valid elements.
441 * The round counter is used to disambiguate aliasing.
442 */
443 bool isValidIdx(size_t idx, uint32_t round) const
444 {
445 /* An index is valid if:
446 * - The queue is not empty.
447 * - round == R and
448 * - index <= tail (if index > tail, that would be PTE)
449 * - Either:
450 * - head <= index
451 * (6,F,1,3,R): |-|[o|(*,r)|o]|-|-|
452 * - head > tail
453 * (6,F,5,3,R): |o|o|(*,r)|o]|-|[o|
454 * The remaining case means the the iterator is BTB:
455 * (6,F,3,4,R): |-|-|(x,r)|[o|o]|-|
456 * - round + 1 == R and:
457 * - index > tail. If index <= tail, that would be BTB:
458 * (6,F,2,3,r): | -|- |[(*,r)|o]|-|-|
459 * (6,F,0,1,r+1): |[o|o]| (x,r)|- |-|-|
460 * (6,F,0,3,r+1): |[o|o | (*,r)|o]|-|-|
461 * - index >= head. If index < head, that would be BTB:
462 * (6,F,5,2,R): |o|o]|-|-|(x,r)|[o|
463 * - head > tail. If head <= tail, that would be BTB:
464 * (6,F,3,4,R): |[o|o]|(x,r)|-|-|-|
465 * Other values of the round meand that the index is PTE or BTB
466 */
467 return (!_empty && (
468 (round == _round && idx <= _tail && (
469 _head <= idx || _head > _tail)) ||
470 (round + 1 == _round &&
471 idx > _tail &&
472 idx >= _head &&
473 _head > _tail)
474 ));
475 }
476
477 reference front() { return (*this)[_head]; }
478 reference back() { return (*this)[_tail]; }
479 uint32_t head() const { return _head; }
480 uint32_t tail() const { return _tail; }
481 size_t capacity() const { return _capacity; }
482
483 uint32_t size() const
484 {
485 if (_empty)
486 return 0;
487 else if (_head <= _tail)
488 return _tail - _head + 1;
489 else
490 return _capacity - _head + _tail + 1;
491 }
492
493 uint32_t moduloAdd(uint32_t s1, uint32_t s2) const
494 {
495 return moduloAdd(s1, s2, _capacity);
496 }
497
498 uint32_t moduloSub(uint32_t s1, uint32_t s2) const
499 {
500 return moduloSub(s1, s2, _capacity);
501 }
502
503 /** Circularly increase the head pointer.
504 * By increasing the head pointer we are removing elements from
505 * the begin of the circular queue.
506 * Check that the queue is not empty. And set it to empty if it
507 * had only one value prior to insertion.
508 *
509 * @params num_elem number of elements to remove
510 */
511 void pop_front(size_t num_elem = 1)
512 {
513 if (num_elem == 0) return;
514 auto hIt = begin();
515 hIt += num_elem;
516 assert(hIt <= end());
517 _empty = hIt == end();
518 _head = hIt._idx;
519 }
520
521 /** Circularly decrease the tail pointer. */
522 void pop_back()
523 {
524 assert (!_empty);
525 _empty = _head == _tail;
526 if (_tail == 0)
527 --_round;
528 decrease(_tail);
529 }
530
531 /** Pushes an element at the end of the queue. */
532 void push_back(typename Base::value_type val)
533 {
534 advance_tail();
535 (*this)[_tail] = val;
536 }
537
538 /** Increases the tail by one.
539 * Check for wrap-arounds to update the round counter.
540 */
541 void advance_tail()
542 {
543 increase(_tail);
544 if (_tail == 0)
545 ++_round;
546
547 if (_tail == _head && !_empty)
548 increase(_head);
549
550 _empty = false;
551 }
552
553 /** Increases the tail by a specified number of steps
554 *
555 * @param len Number of steps
556 */
557 void advance_tail(uint32_t len)
558 {
559 for (auto idx = 0; idx < len; idx++)
560 advance_tail();
561 }
562
563 /** Is the queue empty? */
564 bool empty() const { return _empty; }
565
566 /** Is the queue full?
567 * A queue is full if the head is the 0^{th} element and the tail is
568 * the (size-1)^{th} element, or if the head is the n^{th} element and
569 * the tail the (n-1)^{th} element.
570 */
571 bool full() const
572 {
573 return !_empty &&
574 (_tail + 1 == _head || (_tail + 1 == _capacity && _head == 0));
575 }
576
577 /** Iterators. */
578 iterator begin()
579 {
580 if (_empty)
581 return end();
582 else if (_head > _tail)
583 return iterator(this, _head, _round - 1);
584 else
585 return iterator(this, _head, _round);
586 }
587
588 /* TODO: This should return a const_iterator. */
589 iterator begin() const
590 {
591 if (_empty)
592 return end();
593 else if (_head > _tail)
594 return iterator(const_cast<CircularQueue*>(this), _head,
595 _round - 1);
596 else
597 return iterator(const_cast<CircularQueue*>(this), _head,
598 _round);
599 }
600
601 iterator end()
602 {
603 auto poi = moduloAdd(_tail, 1);
604 auto round = _round;
605 if (poi == 0)
606 ++round;
607 return iterator(this, poi, round);
608 }
609
610 iterator end() const
611 {
612 auto poi = moduloAdd(_tail, 1);
613 auto round = _round;
614 if (poi == 0)
615 ++round;
616 return iterator(const_cast<CircularQueue*>(this), poi, round);
617 }
618
619 /** Return an iterator to an index in the vector.
620 * This poses the problem of round determination. By convention, the round
621 * is picked so that isValidIndex(idx, round) is true. If that is not
622 * possible, then the round value is _round, unless _tail is at the end of
623 * the storage, in which case the PTE wraps up and becomes _round + 1
624 */
625 iterator getIterator(size_t idx)
626 {
627 assert(isValidIdx(idx) || moduloAdd(_tail, 1) == idx);
628 if (_empty)
629 return end();
630
631 uint32_t round = _round;
632 if (idx > _tail) {
633 if (idx >= _head && _head > _tail) {
634 round -= 1;
635 }
636 } else if (idx < _head && _tail + 1 == _capacity) {
637 round += 1;
638 }
639 return iterator(this, idx, round);
640 }
641};
642
643#endif /* __BASE_CIRCULARQUEUE_HH__ */
|