diff options
| -rw-r--r-- | src/base/SConscript | 1 | ||||
| -rw-r--r-- | src/base/circular_queue.hh | 643 | ||||
| -rw-r--r-- | src/base/circular_queue.test.cc | 243 |
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); +} |