base: Iterable CircularQueue implementation

The former implementation of CircleBuf is functional but a bit too
tailored to match a use-case. This patches introduces a new iterable
circular queue, which adds some more functionality so it can also be
used for the newer LSQ implementation, where iteration and iterators
are a very desirable feature.

Additional contributors: Gabor Dozsa.

Change-Id: I5cfb95c8abc1f5e566a114acdbf23fc52a38ce5e
Signed-off-by: Giacomo Gabrielli <giacomo.gabrielli@arm.com>
Reviewed-on: https://gem5-review.googlesource.com/c/13127
Maintainer: Andreas Sandberg <andreas.sandberg@arm.com>
Reviewed-by: Daniel Carvalho <odanrc@yahoo.com.br>

3 files changed, 887 insertions, 0 deletions

diff --git a/src/base/SConscript b/src/base/SConscript
index d1ebbc9d4..29f87eb98 100644
--- a/src/base/SConscript
+++ b/src/base/SConscript
@@ -87,6 +87,7 @@ GTest('addr_range.test', 'addr_range.test.cc')
 GTest('addr_range_map.test', 'addr_range_map.test.cc')
 GTest('bitunion.test', 'bitunion.test.cc')
 GTest('circlebuf.test', 'circlebuf.test.cc')
+GTest('circular_queue.test', 'circular_queue.test.cc')
 
 DebugFlag('Annotate', "State machine annotation debugging")
 DebugFlag('AnnotateQ', "State machine annotation queue debugging")
diff --git a/src/base/circular_queue.hh b/src/base/circular_queue.hh
new file mode 100644
index 000000000..ff7f73dc1
--- /dev/null
+++ b/src/base/circular_queue.hh
@@ -0,0 +1,643 @@
+/*
+ * 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)
+    {
+        int ret = (uint32_t)(op1 - op2) % size;
+        return ret >= 0 ? ret : ret + 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();
+            else
+                _round += (-t + _idx - _cq->capacity() + 1) / _cq->capacity();
+
+            _idx = _cq->moduloSub(_idx, 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->moduloSub(this->_idx, that._idx);
+
+            if (ret == 0 && this->_round != that._round) {
+                ret += this->_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 typename 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__ */
diff --git a/src/base/circular_queue.test.cc b/src/base/circular_queue.test.cc
new file mode 100644
index 000000000..db59c3049
--- /dev/null
+++ b/src/base/circular_queue.test.cc
@@ -0,0 +1,243 @@
+/*
+ * Copyright (c) 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: Giacomo Travaglini
+ */
+
+#include <gtest/gtest.h>
+
+#include "base/circular_queue.hh"
+
+/** Testing that once instantiated with a fixed size,
+ * the queue is still empty */
+TEST(CircularQueueTest, Empty)
+{
+    const auto cq_size = 8;
+    CircularQueue<uint32_t> cq(cq_size);
+
+    ASSERT_EQ(cq.capacity(), cq_size);
+    ASSERT_EQ(cq.size(), 0);
+    ASSERT_TRUE(cq.empty());
+}
+
+/** Testing that once instantiated with a fixed size,
+ * the queue has Head = Tail + 1 */
+TEST(CircularQueueTest, HeadTailEmpty)
+{
+    const auto cq_size = 8;
+    CircularQueue<uint32_t> cq(cq_size);
+    ASSERT_EQ(cq.head(), cq.tail() + 1);
+}
+
+/** Adding elements to the circular queue.
+ * Once an element has been added we test the new value
+ * of front() and back() (head an tail). Since we are just
+ * adding elements and not removing them, we expect the front
+ * value to be fixed and the back value to change, matching
+ * the latest pushed value.*/
+TEST(CircularQueueTest, AddingElements)
+{
+    const auto cq_size = 8;
+    CircularQueue<uint32_t> cq(cq_size);
+
+    const auto first_element = 0xAAAAAAAA;
+    cq.push_back(first_element);
+    ASSERT_EQ(cq.front(), first_element);
+    ASSERT_EQ(cq.back(), first_element);
+
+    const auto second_element = 0x55555555;
+    cq.push_back(second_element);
+    ASSERT_EQ(cq.front(), first_element);
+    ASSERT_EQ(cq.back(), second_element);
+
+    ASSERT_EQ(cq.size(), 2);
+}
+
+/** Removing elements from the circular queue.
+ * We add two elements and we consequently remove them.
+ * After removing them we check that the elements have been
+ * effectively removed, which means the circular queue is
+ * empty */
+TEST(CircularQueueTest, RemovingElements)
+{
+    const auto cq_size = 8;
+    CircularQueue<uint32_t> cq(cq_size);
+
+    // Adding first element
+    const auto first_element = 0xAAAAAAAA;
+    cq.push_back(first_element);
+
+    // Adding second element
+    const auto second_element = 0x55555555;
+    cq.push_back(second_element);
+
+    auto initial_head = cq.head();
+    auto initial_tail = cq.tail();
+
+    // Removing first and second element
+    cq.pop_front();
+    ASSERT_EQ(cq.head(), initial_head + 1);
+    ASSERT_EQ(cq.tail(), initial_tail);
+
+    cq.pop_front();
+    ASSERT_EQ(cq.head(), initial_head + 2);
+    ASSERT_EQ(cq.tail(), initial_tail);
+
+    ASSERT_EQ(cq.size(), 0);
+    ASSERT_TRUE(cq.empty());
+}
+
+/** Testing CircularQueue::full
+ * This tests adds elements to the queue and checks that it is full,
+ * which means:
+ *    - CircularQueue::full == true
+ *    - Head = Tail + 1
+ */
+TEST(CircularQueueTest, Full)
+{
+    const auto cq_size = 8;
+    CircularQueue<uint32_t> cq(cq_size);
+
+    const auto value = 0xAAAAAAAA;
+    for (auto idx = 0; idx < cq_size; idx++) {
+        cq.push_back(value);
+    }
+
+    ASSERT_TRUE(cq.full());
+    ASSERT_EQ(cq.head(), cq.tail() + 1);
+}
+
+/** Testing CircularQueue::begin(), CircularQueue::end()
+ * This tests the following:
+ *     - In an empty queue, begin() == end()
+ *     - After pushing some elements in the queue, the begin()
+ *       and end() iterators are correctly misaligned
+ */
+TEST(CircularQueueTest, BeginEnd)
+{
+    const auto cq_size = 8;
+    CircularQueue<uint32_t> cq(cq_size);
+
+    // Begin/End are the same (empty)
+    ASSERT_EQ(cq.begin(), cq.end());
+
+    const auto first_value = 0xAAAAAAAA;
+    const auto second_value = 0x55555555;
+
+    cq.push_back(first_value);
+    cq.push_back(second_value);
+
+    // End = Begin + 2
+    ASSERT_EQ(cq.begin() + 2, cq.end());
+}
+
+/** Testing that begin() and end() (-1) iterators
+ * actually point to the correct values
+ * so that dereferencing them leads to a match with the
+ * values of (front() and back())
+ */
+TEST(CircularQueueTest, BeginFrontEndBack)
+{
+    const auto cq_size = 8;
+    CircularQueue<uint32_t> cq(cq_size);
+
+    const auto front_value = 0xAAAAAAAA;
+    const auto back_value = 0x55555555;
+
+    cq.push_back(front_value);
+    cq.push_back(back_value);
+
+    ASSERT_EQ(*(cq.begin()), cq.front());
+    ASSERT_EQ(*(cq.end() - 1), cq.back());
+}
+
+/** Testing circular queue iterators:
+ * By allocating two iterators to a queue we test several
+ * operators.
+ */
+TEST(CircularQueueTest, IteratorsOp)
+{
+    const auto cq_size = 8;
+    CircularQueue<uint32_t> cq(cq_size);
+
+    const auto first_value = 0xAAAAAAAA;
+    const auto second_value = 0x55555555;
+    cq.push_back(first_value);
+    cq.push_back(second_value);
+
+    auto it_1 = cq.begin();
+    auto it_2 = cq.begin() + 1;
+
+    // Operators test
+    ASSERT_TRUE(it_1 != it_2);
+    ASSERT_FALSE(it_1 == it_2);
+    ASSERT_FALSE(it_1 > it_2);
+    ASSERT_FALSE(it_1 >= it_2);
+    ASSERT_TRUE(it_1 < it_2);
+    ASSERT_TRUE(it_1 <= it_2);
+    ASSERT_EQ(*it_1, first_value);
+    ASSERT_EQ(it_1 + 1, it_2);
+    ASSERT_EQ(it_1, it_2 - 1);
+    ASSERT_EQ(it_2 - it_1, 1);
+
+    auto temp_it = it_1;
+    ASSERT_EQ(++temp_it, it_2);
+    ASSERT_EQ(--temp_it, it_1);
+    ASSERT_EQ(temp_it++, it_1);
+    ASSERT_EQ(temp_it, it_2);
+    ASSERT_EQ(temp_it--, it_2);
+    ASSERT_EQ(temp_it, it_1);
+}
+
+/**
+ * Testing a full loop, which is incrementing one iterator until
+ * it wraps and has the same index as the starting iterator.
+ * This test checks that even if they have the same index, they are
+ * not the same iterator since they have different round.
+ */
+TEST(CircularQueueTest, FullLoop)
+{
+    const auto cq_size = 8;
+    CircularQueue<uint32_t> cq(cq_size);
+
+    // ending_it does a full loop and points at the same
+    // index as starting_it but with a different round
+    auto starting_it = cq.begin();
+    auto ending_it = starting_it + cq_size;
+
+    ASSERT_EQ(starting_it._idx, ending_it._idx);
+    ASSERT_TRUE(starting_it != ending_it);
+}