/*
* Copyright (c) 2017-2018 ARM Limited
* All rights reserved
*
* The license below extends only to copyright in the software and shall
* not be construed as granting a license to any other intellectual
* property including but not limited to intellectual property relating
* to a hardware implementation of the functionality of the software
* licensed hereunder. You may use the software subject to the license
* terms below provided that you ensure that this notice is replicated
* unmodified and in its entirety in all distributions of the software,
* modified or unmodified, in source code or in binary form.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met: redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer;
* redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution;
* neither the name of the copyright holders nor the names of its
* contributors may be used to endorse or promote products derived from
* this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* Authors: Rekai Gonzalez-Alberquilla
*/
#ifndef __BASE_CIRCULAR_QUEUE_HH__
#define __BASE_CIRCULAR_QUEUE_HH__
#include <vector>
/** Circular queue.
* Circular queue implemented on top of a standard vector. Instead of using
* a sentinel entry, we use a boolean to distinguish the case in which the
* queue is full or empty.
* Thus, a circular queue is represented by the 5-tuple
* (Capacity, IsEmpty?, Head, Tail, Round)
* Where:
* - Capacity is the size of the underlying vector.
* - IsEmpty? can be T or F.
* - Head is the index in the vector of the first element of the queue.
* - Tail is the index in the vector of the last element of the queue.
* - Round is the counter of how many times the Tail has wrapped around.
* A queue is empty when
* Head == (Tail + 1 mod Capacity) && IsEmpty?.
* Conversely, a queue if full when
* Head == (Tail + 1 mod Capacity) && !IsEmpty?.
* Comments may show depictions of the underlying vector in the following
* format: '|' delimit the 'cells' of the underlying vector. '-' represents
* an element of the vector that is out-of-bounds of the circular queue,
* while 'o' represents and element that is inside the bounds. The
* characters '[' and ']' are added to mark the entries that hold the head
* and tail of the circular queue respectively.
* E.g.:
* - Empty queues of capacity 4:
* (4,T,1,0,_): |-]|[-|-|-| (4,T,3,2): |-|-|-]|[-|
* - Full queues of capacity 4:
* (4,F,1,0,_): |o]|[o|o|o| (4,F,3,2): |o|o|o]|[o|
* - Queues of capacity 4 with 2 elements:
* (4,F,0,1,_): |[o|o]|-|-| (4,F,3,0): |o]|-|-|[o|
*
* The Round number is only relevant for checking validity of indices,
* therefore it will be omitted or shown as '_'
*/
template <typename T>
class CircularQueue : private std::vector<T>
{
protected:
using Base = std::vector<T>;
using typename Base::reference;
using typename Base::const_reference;
const uint32_t _capacity;
uint32_t _head;
uint32_t _tail;
uint32_t _empty;
/** Counter for how many times the tail wraps around.
* Some parts of the code rely on getting the past the end iterator, and
* expect to use it after inserting on the tail. To support this without
* ambiguity, we need the round number to guarantee that it did not become
* a before-the-beginning iterator.
*/
uint32_t _round;
/** General modular addition. */
static uint32_t
moduloAdd(uint32_t op1, uint32_t op2, uint32_t size)
{
return (op1 + op2) % size;
}
/** General modular subtraction. */
static uint32_t
moduloSub(uint32_t op1, uint32_t op2, uint32_t size)
{
int32_t ret = sub(op1, op2, size);
return ret >= 0 ? ret : ret + size;
}
static int32_t
sub(uint32_t op1, uint32_t op2, uint32_t size)
{
if (op1 > op2)
return (op1 - op2) % size;
else
return -((op2 - op1) % size);
}
void increase(uint32_t& v, size_t delta = 1)
{
v = moduloAdd(v, delta, _capacity);
}
void decrease(uint32_t& v)
{
v = (v ? v : _capacity) - 1;
}
/** Iterator to the circular queue.
* iterator implementation to provide the circular-ness that the
* standard std::vector<T>::iterator does not implement.
* Iterators to a queue are represented by a pair of a character and the
* round counter. For the character, '*' denotes the element pointed to by
* the iterator if it is valid. 'x' denotes the element pointed to by the
* iterator when it is BTB or PTE.
* E.g.:
* - Iterator to the head of a queue of capacity 4 with 2 elems.
* (4,F,0,1,R): |[(*,R)|o]|-|-| (4,F,3,0): |o]|-|-|[(*,R)|
* - Iterator to the tail of a queue of capacity 4 with 2 elems.
* (4,F,0,1,R): |[o|(*,R)]|-|-| (4,F,3,0): |(*,R)]|-|-|[o|
* - Iterator to the end of a queue of capacity 4 with 2 elems.
* (4,F,0,1,R): |[o|o]|(x,R)|-| (4,F,3,0): |o]|(x,R)|-|[o|
*/
public:
struct iterator {
CircularQueue* _cq;
uint32_t _idx;
uint32_t _round;
public:
iterator(CircularQueue* cq, uint32_t idx, uint32_t round)
: _cq(cq), _idx(idx), _round(round) {}
/** Iterator Traits */
using value_type = T;
using difference_type = std::ptrdiff_t;
using reference = value_type&;
using const_reference = const value_type&;
using pointer = value_type*;
using const_pointer = const value_type*;
using iterator_category = std::random_access_iterator_tag;
/** Trait reference type
* iterator satisfies OutputIterator, therefore reference
* must be T& */
static_assert(std::is_same<reference, T&>::value,
"reference type is not assignable as required");
iterator() : _cq(nullptr), _idx(0), _round(0) { }
iterator(const iterator& it)
: _cq(it._cq), _idx(it._idx), _round(it._round) {}
iterator&
operator=(const iterator& it)
{
_cq = it._cq;
_idx = it._idx;
_round = it._round;
return *this;
}
~iterator() { _cq = nullptr; _idx = 0; _round = 0; }
/** Test dereferenceability.
* An iterator is dereferenceable if it is pointing to a non-null
* circular queue, it is not the past-the-end iterator and the
* index is a valid index to that queue. PTE test is required to
* distinguish between:
* - An iterator to the first element of a full queue
* (4,F,1,0): |o]|[*|o|o|
* - The end() iterator of a full queue
* (4,F,1,0): |o]|x[o|o|o|
* Sometimes, though, users will get the PTE iterator and expect it
* to work after growing the buffer on the tail, so we have to
* check if the iterator is still PTE.
*/
bool
dereferenceable() const
{
return _cq != nullptr && _cq->isValidIdx(_idx, _round);
}
/** InputIterator. */
/** Equality operator.
* Two iterators must point to the same, possibly null, circular
* queue and the same element on it, including PTE, to be equal.
* In case the clients the the PTE iterator and then grow on the back
* and expect it to work, we have to check if the PTE is still PTE
*/
bool operator==(const iterator& that) const
{
return _cq == that._cq && _idx == that._idx &&
_round == that._round;
}
/** Inequality operator.
* Conversely, two iterators are different if they both point to
* different circular queues or they point to different elements.
*/
bool operator!=(const iterator& that)
{
return !(*this == that);
}
/** Dereference operator. */
reference operator*()
{
/* this has to be dereferenceable. */
return (*_cq)[_idx];
}
const_reference operator*() const
{
/* this has to be dereferenceable. */
return (*_cq)[_idx];
}
/** Dereference operator.
* Rely on operator* to check for dereferenceability.
*/
pointer operator->()
{
return &((*_cq)[_idx]);
}
const_pointer operator->() const
{
return &((*_cq)[_idx]);
}
/** Pre-increment operator. */
iterator& operator++()
{
/* this has to be dereferenceable. */
_cq->increase(_idx);
if (_idx == 0)
++_round;
return *this;
}
/** Post-increment operator. */
iterator
operator++(int)
{
iterator t = *this;
++*this;
return t;
}
/** ForwardIterator
* The multipass guarantee is provided by the reliance on _idx.
*/
/** BidirectionalIterator requirements. */
private:
/** Test decrementability.
* An iterator to a non-null circular queue is not-decrementable
* if it is pointing to the head element, unless the queue is full
* and we are talking about the past-the-end iterator. In that case,
* the iterator round equals the cq round unless the head is at the
* zero position and the round is one more than the cq round.
*/
bool
decrementable() const
{
return _cq && !(_idx == _cq->head() &&
(_cq->empty() ||
(_idx == 0 && _round != _cq->_round + 1) ||
(_idx !=0 && _round != _cq->_round)));
}
public:
/** Pre-decrement operator. */
iterator& operator--()
{
/* this has to be decrementable. */
assert(decrementable());
if (_idx == 0)
--_round;
_cq->decrease(_idx);
return *this;
}
/** Post-decrement operator. */
iterator operator--(int ) { iterator t = *this; --*this; return t; }
/** RandomAccessIterator requirements.*/
iterator& operator+=(const difference_type& t)
{
assert(_cq);
_round += (t + _idx) / _cq->capacity();
_idx = _cq->moduloAdd(_idx, t);
return *this;
}
iterator& operator-=(const difference_type& t)
{
assert(_cq);
/* C does not do euclidean division, so we have to adjust */
if (t >= 0) {
_round += (-t + _idx) / _cq->capacity();
_idx = _cq->moduloSub(_idx, t);
} else {
*this += -t;
}
return *this;
}
/** Addition operator. */
iterator operator+(const difference_type& t)
{
iterator ret(*this);
return ret += t;
}
friend iterator operator+(const difference_type& t, iterator& it)
{
iterator ret = it;
return ret += t;
}
/** Substraction operator. */
iterator operator-(const difference_type& t)
{
iterator ret(*this);
return ret -= t;
}
friend iterator operator-(const difference_type& t, iterator& it)
{
iterator ret = it;
return ret -= t;
}
/** Difference operator.
* that + ret == this
*/
difference_type operator-(const iterator& that)
{
/* If a is already at the end, we can safely return 0. */
auto ret = _cq->sub(this->_idx, that._idx, _cq->capacity());
if (this->_round != that._round) {
ret += ((this->_round - that._round) * _cq->capacity());
}
return ret;
}
/** Index operator.
* The use of * tests for dereferenceability.
*/
template<typename Idx>
typename std::enable_if<std::is_integral<Idx>::value,reference>::type
operator[](const Idx& index) { return *(*this + index); }
/** Comparisons. */
bool
operator<(const iterator& that) const
{
assert(_cq && that._cq == _cq);
return (this->_round < that._round) ||
(this->_round == that._round && _idx < that._idx);
}
bool
operator>(const iterator& that) const
{ return !(*this <= that); }
bool operator>=(const iterator& that) const
{ return !(*this < that); }
bool operator<=(const iterator& that) const
{ return !(that < *this); }
/** OutputIterator has no extra requirements.*/
size_t idx() const { return _idx; }
};
public:
using Base::operator[];
explicit CircularQueue(uint32_t size = 0)
: _capacity(size), _head(1), _tail(0), _empty(true), _round(0)
{
Base::resize(size);
}
/**
* Remove all the elements in the queue.
*
* Note: This does not actually remove elements from the backing
* store.
*/
void flush()
{
_head = 1;
_round = 0;
_tail = 0;
_empty = true;
}
/** Test if the index is in the range of valid elements. */
bool isValidIdx(size_t idx) const
{
/* An index is invalid if:
* - The queue is empty.
* (6,T,3,2): |-|-|-]|[-|-|x|
* - head is small than tail and:
* - It is greater than both head and tail.
* (6,F,1,3): |-|[o|o|o]|-|x|
* - It is less than both head and tail.
* (6,F,1,3): |x|[o|o|o]|-|-|
* - It is greater than the tail and not than the head.
* (6,F,4,1): |o|o]|-|x|[o|o|
*/
return !(_empty || (
(_head < _tail) && (
(_head < idx && _tail < idx) ||
(_head > idx && _tail > idx)
)) || (_tail < idx && idx < _head));
}
/** Test if the index is in the range of valid elements.
* The round counter is used to disambiguate aliasing.
*/
bool isValidIdx(size_t idx, uint32_t round) const
{
/* An index is valid if:
* - The queue is not empty.
* - round == R and
* - index <= tail (if index > tail, that would be PTE)
* - Either:
* - head <= index
* (6,F,1,3,R): |-|[o|(*,r)|o]|-|-|
* - head > tail
* (6,F,5,3,R): |o|o|(*,r)|o]|-|[o|
* The remaining case means the the iterator is BTB:
* (6,F,3,4,R): |-|-|(x,r)|[o|o]|-|
* - round + 1 == R and:
* - index > tail. If index <= tail, that would be BTB:
* (6,F,2,3,r): | -|- |[(*,r)|o]|-|-|
* (6,F,0,1,r+1): |[o|o]| (x,r)|- |-|-|
* (6,F,0,3,r+1): |[o|o | (*,r)|o]|-|-|
* - index >= head. If index < head, that would be BTB:
* (6,F,5,2,R): |o|o]|-|-|(x,r)|[o|
* - head > tail. If head <= tail, that would be BTB:
* (6,F,3,4,R): |[o|o]|(x,r)|-|-|-|
* Other values of the round meand that the index is PTE or BTB
*/
return (!_empty && (
(round == _round && idx <= _tail && (
_head <= idx || _head > _tail)) ||
(round + 1 == _round &&
idx > _tail &&
idx >= _head &&
_head > _tail)
));
}
reference front() { return (*this)[_head]; }
reference back() { return (*this)[_tail]; }
uint32_t head() const { return _head; }
uint32_t tail() const { return _tail; }
size_t capacity() const { return _capacity; }
uint32_t size() const
{
if (_empty)
return 0;
else if (_head <= _tail)
return _tail - _head + 1;
else
return _capacity - _head + _tail + 1;
}
uint32_t moduloAdd(uint32_t s1, uint32_t s2) const
{
return moduloAdd(s1, s2, _capacity);
}
uint32_t moduloSub(uint32_t s1, uint32_t s2) const
{
return moduloSub(s1, s2, _capacity);
}
/** Circularly increase the head pointer.
* By increasing the head pointer we are removing elements from
* the begin of the circular queue.
* Check that the queue is not empty. And set it to empty if it
* had only one value prior to insertion.
*
* @params num_elem number of elements to remove
*/
void pop_front(size_t num_elem = 1)
{
if (num_elem == 0) return;
auto hIt = begin();
hIt += num_elem;
assert(hIt <= end());
_empty = hIt == end();
_head = hIt._idx;
}
/** Circularly decrease the tail pointer. */
void pop_back()
{
assert (!_empty);
_empty = _head == _tail;
if (_tail == 0)
--_round;
decrease(_tail);
}
/** Pushes an element at the end of the queue. */
void push_back(typename Base::value_type val)
{
advance_tail();
(*this)[_tail] = val;
}
/** Increases the tail by one.
* Check for wrap-arounds to update the round counter.
*/
void advance_tail()
{
increase(_tail);
if (_tail == 0)
++_round;
if (_tail == _head && !_empty)
increase(_head);
_empty = false;
}
/** Increases the tail by a specified number of steps
*
* @param len Number of steps
*/
void advance_tail(uint32_t len)
{
for (auto idx = 0; idx < len; idx++)
advance_tail();
}
/** Is the queue empty? */
bool empty() const { return _empty; }
/** Is the queue full?
* A queue is full if the head is the 0^{th} element and the tail is
* the (size-1)^{th} element, or if the head is the n^{th} element and
* the tail the (n-1)^{th} element.
*/
bool full() const
{
return !_empty &&
(_tail + 1 == _head || (_tail + 1 == _capacity && _head == 0));
}
/** Iterators. */
iterator begin()
{
if (_empty)
return end();
else if (_head > _tail)
return iterator(this, _head, _round - 1);
else
return iterator(this, _head, _round);
}
/* TODO: This should return a const_iterator. */
iterator begin() const
{
if (_empty)
return end();
else if (_head > _tail)
return iterator(const_cast<CircularQueue*>(this), _head,
_round - 1);
else
return iterator(const_cast<CircularQueue*>(this), _head,
_round);
}
iterator end()
{
auto poi = moduloAdd(_tail, 1);
auto round = _round;
if (poi == 0)
++round;
return iterator(this, poi, round);
}
iterator end() const
{
auto poi = moduloAdd(_tail, 1);
auto round = _round;
if (poi == 0)
++round;
return iterator(const_cast<CircularQueue*>(this), poi, round);
}
/** Return an iterator to an index in the vector.
* This poses the problem of round determination. By convention, the round
* is picked so that isValidIndex(idx, round) is true. If that is not
* possible, then the round value is _round, unless _tail is at the end of
* the storage, in which case the PTE wraps up and becomes _round + 1
*/
iterator getIterator(size_t idx)
{
assert(isValidIdx(idx) || moduloAdd(_tail, 1) == idx);
if (_empty)
return end();
uint32_t round = _round;
if (idx > _tail) {
if (idx >= _head && _head > _tail) {
round -= 1;
}
} else if (idx < _head && _tail + 1 == _capacity) {
round += 1;
}
return iterator(this, idx, round);
}
};
#endif /* __BASE_CIRCULARQUEUE_HH__ */