circular_queue.hh revision 13482
113482Srekai.gonzalezalberquilla@arm.com/* 213482Srekai.gonzalezalberquilla@arm.com * Copyright (c) 2017-2018 ARM Limited 313482Srekai.gonzalezalberquilla@arm.com * All rights reserved 413482Srekai.gonzalezalberquilla@arm.com * 513482Srekai.gonzalezalberquilla@arm.com * The license below extends only to copyright in the software and shall 613482Srekai.gonzalezalberquilla@arm.com * not be construed as granting a license to any other intellectual 713482Srekai.gonzalezalberquilla@arm.com * property including but not limited to intellectual property relating 813482Srekai.gonzalezalberquilla@arm.com * to a hardware implementation of the functionality of the software 913482Srekai.gonzalezalberquilla@arm.com * licensed hereunder. You may use the software subject to the license 1013482Srekai.gonzalezalberquilla@arm.com * terms below provided that you ensure that this notice is replicated 1113482Srekai.gonzalezalberquilla@arm.com * unmodified and in its entirety in all distributions of the software, 1213482Srekai.gonzalezalberquilla@arm.com * modified or unmodified, in source code or in binary form. 1313482Srekai.gonzalezalberquilla@arm.com * 1413482Srekai.gonzalezalberquilla@arm.com * Redistribution and use in source and binary forms, with or without 1513482Srekai.gonzalezalberquilla@arm.com * modification, are permitted provided that the following conditions are 1613482Srekai.gonzalezalberquilla@arm.com * met: redistributions of source code must retain the above copyright 1713482Srekai.gonzalezalberquilla@arm.com * notice, this list of conditions and the following disclaimer; 1813482Srekai.gonzalezalberquilla@arm.com * redistributions in binary form must reproduce the above copyright 1913482Srekai.gonzalezalberquilla@arm.com * notice, this list of conditions and the following disclaimer in the 2013482Srekai.gonzalezalberquilla@arm.com * documentation and/or other materials provided with the distribution; 2113482Srekai.gonzalezalberquilla@arm.com * neither the name of the copyright holders nor the names of its 2213482Srekai.gonzalezalberquilla@arm.com * contributors may be used to endorse or promote products derived from 2313482Srekai.gonzalezalberquilla@arm.com * this software without specific prior written permission. 2413482Srekai.gonzalezalberquilla@arm.com * 2513482Srekai.gonzalezalberquilla@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2613482Srekai.gonzalezalberquilla@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2713482Srekai.gonzalezalberquilla@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2813482Srekai.gonzalezalberquilla@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2913482Srekai.gonzalezalberquilla@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3013482Srekai.gonzalezalberquilla@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3113482Srekai.gonzalezalberquilla@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3213482Srekai.gonzalezalberquilla@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3313482Srekai.gonzalezalberquilla@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3413482Srekai.gonzalezalberquilla@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3513482Srekai.gonzalezalberquilla@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3613482Srekai.gonzalezalberquilla@arm.com * 3713482Srekai.gonzalezalberquilla@arm.com * Authors: Rekai Gonzalez-Alberquilla 3813482Srekai.gonzalezalberquilla@arm.com */ 3913482Srekai.gonzalezalberquilla@arm.com 4013482Srekai.gonzalezalberquilla@arm.com#ifndef __BASE_CIRCULAR_QUEUE_HH__ 4113482Srekai.gonzalezalberquilla@arm.com#define __BASE_CIRCULAR_QUEUE_HH__ 4213482Srekai.gonzalezalberquilla@arm.com 4313482Srekai.gonzalezalberquilla@arm.com#include <vector> 4413482Srekai.gonzalezalberquilla@arm.com 4513482Srekai.gonzalezalberquilla@arm.com/** Circular queue. 4613482Srekai.gonzalezalberquilla@arm.com * Circular queue implemented on top of a standard vector. Instead of using 4713482Srekai.gonzalezalberquilla@arm.com * a sentinel entry, we use a boolean to distinguish the case in which the 4813482Srekai.gonzalezalberquilla@arm.com * queue is full or empty. 4913482Srekai.gonzalezalberquilla@arm.com * Thus, a circular queue is represented by the 5-tuple 5013482Srekai.gonzalezalberquilla@arm.com * (Capacity, IsEmpty?, Head, Tail, Round) 5113482Srekai.gonzalezalberquilla@arm.com * Where: 5213482Srekai.gonzalezalberquilla@arm.com * - Capacity is the size of the underlying vector. 5313482Srekai.gonzalezalberquilla@arm.com * - IsEmpty? can be T or F. 5413482Srekai.gonzalezalberquilla@arm.com * - Head is the index in the vector of the first element of the queue. 5513482Srekai.gonzalezalberquilla@arm.com * - Tail is the index in the vector of the last element of the queue. 5613482Srekai.gonzalezalberquilla@arm.com * - Round is the counter of how many times the Tail has wrapped around. 5713482Srekai.gonzalezalberquilla@arm.com * A queue is empty when 5813482Srekai.gonzalezalberquilla@arm.com * Head == (Tail + 1 mod Capacity) && IsEmpty?. 5913482Srekai.gonzalezalberquilla@arm.com * Conversely, a queue if full when 6013482Srekai.gonzalezalberquilla@arm.com * Head == (Tail + 1 mod Capacity) && !IsEmpty?. 6113482Srekai.gonzalezalberquilla@arm.com * Comments may show depictions of the underlying vector in the following 6213482Srekai.gonzalezalberquilla@arm.com * format: '|' delimit the 'cells' of the underlying vector. '-' represents 6313482Srekai.gonzalezalberquilla@arm.com * an element of the vector that is out-of-bounds of the circular queue, 6413482Srekai.gonzalezalberquilla@arm.com * while 'o' represents and element that is inside the bounds. The 6513482Srekai.gonzalezalberquilla@arm.com * characters '[' and ']' are added to mark the entries that hold the head 6613482Srekai.gonzalezalberquilla@arm.com * and tail of the circular queue respectively. 6713482Srekai.gonzalezalberquilla@arm.com * E.g.: 6813482Srekai.gonzalezalberquilla@arm.com * - Empty queues of capacity 4: 6913482Srekai.gonzalezalberquilla@arm.com * (4,T,1,0,_): |-]|[-|-|-| (4,T,3,2): |-|-|-]|[-| 7013482Srekai.gonzalezalberquilla@arm.com * - Full queues of capacity 4: 7113482Srekai.gonzalezalberquilla@arm.com * (4,F,1,0,_): |o]|[o|o|o| (4,F,3,2): |o|o|o]|[o| 7213482Srekai.gonzalezalberquilla@arm.com * - Queues of capacity 4 with 2 elements: 7313482Srekai.gonzalezalberquilla@arm.com * (4,F,0,1,_): |[o|o]|-|-| (4,F,3,0): |o]|-|-|[o| 7413482Srekai.gonzalezalberquilla@arm.com * 7513482Srekai.gonzalezalberquilla@arm.com * The Round number is only relevant for checking validity of indices, 7613482Srekai.gonzalezalberquilla@arm.com * therefore it will be omitted or shown as '_' 7713482Srekai.gonzalezalberquilla@arm.com */ 7813482Srekai.gonzalezalberquilla@arm.comtemplate <typename T> 7913482Srekai.gonzalezalberquilla@arm.comclass CircularQueue : private std::vector<T> 8013482Srekai.gonzalezalberquilla@arm.com{ 8113482Srekai.gonzalezalberquilla@arm.com protected: 8213482Srekai.gonzalezalberquilla@arm.com using Base = std::vector<T>; 8313482Srekai.gonzalezalberquilla@arm.com using typename Base::reference; 8413482Srekai.gonzalezalberquilla@arm.com using typename Base::const_reference; 8513482Srekai.gonzalezalberquilla@arm.com const uint32_t _capacity; 8613482Srekai.gonzalezalberquilla@arm.com uint32_t _head; 8713482Srekai.gonzalezalberquilla@arm.com uint32_t _tail; 8813482Srekai.gonzalezalberquilla@arm.com uint32_t _empty; 8913482Srekai.gonzalezalberquilla@arm.com 9013482Srekai.gonzalezalberquilla@arm.com /** Counter for how many times the tail wraps around. 9113482Srekai.gonzalezalberquilla@arm.com * Some parts of the code rely on getting the past the end iterator, and 9213482Srekai.gonzalezalberquilla@arm.com * expect to use it after inserting on the tail. To support this without 9313482Srekai.gonzalezalberquilla@arm.com * ambiguity, we need the round number to guarantee that it did not become 9413482Srekai.gonzalezalberquilla@arm.com * a before-the-beginning iterator. 9513482Srekai.gonzalezalberquilla@arm.com */ 9613482Srekai.gonzalezalberquilla@arm.com uint32_t _round; 9713482Srekai.gonzalezalberquilla@arm.com 9813482Srekai.gonzalezalberquilla@arm.com /** General modular addition. */ 9913482Srekai.gonzalezalberquilla@arm.com static uint32_t 10013482Srekai.gonzalezalberquilla@arm.com moduloAdd(uint32_t op1, uint32_t op2, uint32_t size) 10113482Srekai.gonzalezalberquilla@arm.com { 10213482Srekai.gonzalezalberquilla@arm.com return (op1 + op2) % size; 10313482Srekai.gonzalezalberquilla@arm.com } 10413482Srekai.gonzalezalberquilla@arm.com 10513482Srekai.gonzalezalberquilla@arm.com /** General modular subtraction. */ 10613482Srekai.gonzalezalberquilla@arm.com static uint32_t 10713482Srekai.gonzalezalberquilla@arm.com moduloSub(uint32_t op1, uint32_t op2, uint32_t size) 10813482Srekai.gonzalezalberquilla@arm.com { 10913482Srekai.gonzalezalberquilla@arm.com int ret = (uint32_t)(op1 - op2) % size; 11013482Srekai.gonzalezalberquilla@arm.com return ret >= 0 ? ret : ret + size; 11113482Srekai.gonzalezalberquilla@arm.com } 11213482Srekai.gonzalezalberquilla@arm.com 11313482Srekai.gonzalezalberquilla@arm.com void increase(uint32_t& v, size_t delta = 1) 11413482Srekai.gonzalezalberquilla@arm.com { 11513482Srekai.gonzalezalberquilla@arm.com v = moduloAdd(v, delta, _capacity); 11613482Srekai.gonzalezalberquilla@arm.com } 11713482Srekai.gonzalezalberquilla@arm.com 11813482Srekai.gonzalezalberquilla@arm.com void decrease(uint32_t& v) 11913482Srekai.gonzalezalberquilla@arm.com { 12013482Srekai.gonzalezalberquilla@arm.com v = (v ? v : _capacity) - 1; 12113482Srekai.gonzalezalberquilla@arm.com } 12213482Srekai.gonzalezalberquilla@arm.com 12313482Srekai.gonzalezalberquilla@arm.com /** Iterator to the circular queue. 12413482Srekai.gonzalezalberquilla@arm.com * iterator implementation to provide the circular-ness that the 12513482Srekai.gonzalezalberquilla@arm.com * standard std::vector<T>::iterator does not implement. 12613482Srekai.gonzalezalberquilla@arm.com * Iterators to a queue are represented by a pair of a character and the 12713482Srekai.gonzalezalberquilla@arm.com * round counter. For the character, '*' denotes the element pointed to by 12813482Srekai.gonzalezalberquilla@arm.com * the iterator if it is valid. 'x' denotes the element pointed to by the 12913482Srekai.gonzalezalberquilla@arm.com * iterator when it is BTB or PTE. 13013482Srekai.gonzalezalberquilla@arm.com * E.g.: 13113482Srekai.gonzalezalberquilla@arm.com * - Iterator to the head of a queue of capacity 4 with 2 elems. 13213482Srekai.gonzalezalberquilla@arm.com * (4,F,0,1,R): |[(*,R)|o]|-|-| (4,F,3,0): |o]|-|-|[(*,R)| 13313482Srekai.gonzalezalberquilla@arm.com * - Iterator to the tail of a queue of capacity 4 with 2 elems. 13413482Srekai.gonzalezalberquilla@arm.com * (4,F,0,1,R): |[o|(*,R)]|-|-| (4,F,3,0): |(*,R)]|-|-|[o| 13513482Srekai.gonzalezalberquilla@arm.com * - Iterator to the end of a queue of capacity 4 with 2 elems. 13613482Srekai.gonzalezalberquilla@arm.com * (4,F,0,1,R): |[o|o]|(x,R)|-| (4,F,3,0): |o]|(x,R)|-|[o| 13713482Srekai.gonzalezalberquilla@arm.com */ 13813482Srekai.gonzalezalberquilla@arm.com public: 13913482Srekai.gonzalezalberquilla@arm.com struct iterator { 14013482Srekai.gonzalezalberquilla@arm.com CircularQueue* _cq; 14113482Srekai.gonzalezalberquilla@arm.com uint32_t _idx; 14213482Srekai.gonzalezalberquilla@arm.com uint32_t _round; 14313482Srekai.gonzalezalberquilla@arm.com 14413482Srekai.gonzalezalberquilla@arm.com public: 14513482Srekai.gonzalezalberquilla@arm.com iterator(CircularQueue* cq, uint32_t idx, uint32_t round) 14613482Srekai.gonzalezalberquilla@arm.com : _cq(cq), _idx(idx), _round(round) {} 14713482Srekai.gonzalezalberquilla@arm.com 14813482Srekai.gonzalezalberquilla@arm.com /** Iterator Traits */ 14913482Srekai.gonzalezalberquilla@arm.com using value_type = T; 15013482Srekai.gonzalezalberquilla@arm.com using difference_type = std::ptrdiff_t; 15113482Srekai.gonzalezalberquilla@arm.com using reference = value_type&; 15213482Srekai.gonzalezalberquilla@arm.com using const_reference = const value_type&; 15313482Srekai.gonzalezalberquilla@arm.com using pointer = value_type*; 15413482Srekai.gonzalezalberquilla@arm.com using const_pointer = const value_type*; 15513482Srekai.gonzalezalberquilla@arm.com using iterator_category = std::random_access_iterator_tag; 15613482Srekai.gonzalezalberquilla@arm.com 15713482Srekai.gonzalezalberquilla@arm.com /** Trait reference type 15813482Srekai.gonzalezalberquilla@arm.com * iterator satisfies OutputIterator, therefore reference 15913482Srekai.gonzalezalberquilla@arm.com * must be T& */ 16013482Srekai.gonzalezalberquilla@arm.com static_assert(std::is_same<reference, T&>::value, 16113482Srekai.gonzalezalberquilla@arm.com "reference type is not assignable as required"); 16213482Srekai.gonzalezalberquilla@arm.com 16313482Srekai.gonzalezalberquilla@arm.com iterator() : _cq(nullptr), _idx(0), _round(0) { } 16413482Srekai.gonzalezalberquilla@arm.com 16513482Srekai.gonzalezalberquilla@arm.com iterator(const iterator& it) 16613482Srekai.gonzalezalberquilla@arm.com : _cq(it._cq), _idx(it._idx), _round(it._round) {} 16713482Srekai.gonzalezalberquilla@arm.com 16813482Srekai.gonzalezalberquilla@arm.com iterator& 16913482Srekai.gonzalezalberquilla@arm.com operator=(const iterator& it) 17013482Srekai.gonzalezalberquilla@arm.com { 17113482Srekai.gonzalezalberquilla@arm.com _cq = it._cq; 17213482Srekai.gonzalezalberquilla@arm.com _idx = it._idx; 17313482Srekai.gonzalezalberquilla@arm.com _round = it._round; 17413482Srekai.gonzalezalberquilla@arm.com return *this; 17513482Srekai.gonzalezalberquilla@arm.com } 17613482Srekai.gonzalezalberquilla@arm.com 17713482Srekai.gonzalezalberquilla@arm.com ~iterator() { _cq = nullptr; _idx = 0; _round = 0; } 17813482Srekai.gonzalezalberquilla@arm.com 17913482Srekai.gonzalezalberquilla@arm.com /** Test dereferenceability. 18013482Srekai.gonzalezalberquilla@arm.com * An iterator is dereferenceable if it is pointing to a non-null 18113482Srekai.gonzalezalberquilla@arm.com * circular queue, it is not the past-the-end iterator and the 18213482Srekai.gonzalezalberquilla@arm.com * index is a valid index to that queue. PTE test is required to 18313482Srekai.gonzalezalberquilla@arm.com * distinguish between: 18413482Srekai.gonzalezalberquilla@arm.com * - An iterator to the first element of a full queue 18513482Srekai.gonzalezalberquilla@arm.com * (4,F,1,0): |o]|[*|o|o| 18613482Srekai.gonzalezalberquilla@arm.com * - The end() iterator of a full queue 18713482Srekai.gonzalezalberquilla@arm.com * (4,F,1,0): |o]|x[o|o|o| 18813482Srekai.gonzalezalberquilla@arm.com * Sometimes, though, users will get the PTE iterator and expect it 18913482Srekai.gonzalezalberquilla@arm.com * to work after growing the buffer on the tail, so we have to 19013482Srekai.gonzalezalberquilla@arm.com * check if the iterator is still PTE. 19113482Srekai.gonzalezalberquilla@arm.com */ 19213482Srekai.gonzalezalberquilla@arm.com bool 19313482Srekai.gonzalezalberquilla@arm.com dereferenceable() const 19413482Srekai.gonzalezalberquilla@arm.com { 19513482Srekai.gonzalezalberquilla@arm.com return _cq != nullptr && _cq->isValidIdx(_idx, _round); 19613482Srekai.gonzalezalberquilla@arm.com } 19713482Srekai.gonzalezalberquilla@arm.com 19813482Srekai.gonzalezalberquilla@arm.com /** InputIterator. */ 19913482Srekai.gonzalezalberquilla@arm.com 20013482Srekai.gonzalezalberquilla@arm.com /** Equality operator. 20113482Srekai.gonzalezalberquilla@arm.com * Two iterators must point to the same, possibly null, circular 20213482Srekai.gonzalezalberquilla@arm.com * queue and the same element on it, including PTE, to be equal. 20313482Srekai.gonzalezalberquilla@arm.com * In case the clients the the PTE iterator and then grow on the back 20413482Srekai.gonzalezalberquilla@arm.com * and expect it to work, we have to check if the PTE is still PTE 20513482Srekai.gonzalezalberquilla@arm.com */ 20613482Srekai.gonzalezalberquilla@arm.com bool operator==(const iterator& that) const 20713482Srekai.gonzalezalberquilla@arm.com { 20813482Srekai.gonzalezalberquilla@arm.com return _cq == that._cq && _idx == that._idx && 20913482Srekai.gonzalezalberquilla@arm.com _round == that._round; 21013482Srekai.gonzalezalberquilla@arm.com } 21113482Srekai.gonzalezalberquilla@arm.com 21213482Srekai.gonzalezalberquilla@arm.com /** Inequality operator. 21313482Srekai.gonzalezalberquilla@arm.com * Conversely, two iterators are different if they both point to 21413482Srekai.gonzalezalberquilla@arm.com * different circular queues or they point to different elements. 21513482Srekai.gonzalezalberquilla@arm.com */ 21613482Srekai.gonzalezalberquilla@arm.com bool operator!=(const iterator& that) 21713482Srekai.gonzalezalberquilla@arm.com { 21813482Srekai.gonzalezalberquilla@arm.com return !(*this == that); 21913482Srekai.gonzalezalberquilla@arm.com } 22013482Srekai.gonzalezalberquilla@arm.com 22113482Srekai.gonzalezalberquilla@arm.com /** Dereference operator. */ 22213482Srekai.gonzalezalberquilla@arm.com reference operator*() 22313482Srekai.gonzalezalberquilla@arm.com { 22413482Srekai.gonzalezalberquilla@arm.com /* this has to be dereferenceable. */ 22513482Srekai.gonzalezalberquilla@arm.com return (*_cq)[_idx]; 22613482Srekai.gonzalezalberquilla@arm.com } 22713482Srekai.gonzalezalberquilla@arm.com 22813482Srekai.gonzalezalberquilla@arm.com const_reference operator*() const 22913482Srekai.gonzalezalberquilla@arm.com { 23013482Srekai.gonzalezalberquilla@arm.com /* this has to be dereferenceable. */ 23113482Srekai.gonzalezalberquilla@arm.com return (*_cq)[_idx]; 23213482Srekai.gonzalezalberquilla@arm.com } 23313482Srekai.gonzalezalberquilla@arm.com 23413482Srekai.gonzalezalberquilla@arm.com /** Dereference operator. 23513482Srekai.gonzalezalberquilla@arm.com * Rely on operator* to check for dereferenceability. 23613482Srekai.gonzalezalberquilla@arm.com */ 23713482Srekai.gonzalezalberquilla@arm.com pointer operator->() 23813482Srekai.gonzalezalberquilla@arm.com { 23913482Srekai.gonzalezalberquilla@arm.com return &((*_cq)[_idx]); 24013482Srekai.gonzalezalberquilla@arm.com } 24113482Srekai.gonzalezalberquilla@arm.com 24213482Srekai.gonzalezalberquilla@arm.com const_pointer operator->() const 24313482Srekai.gonzalezalberquilla@arm.com { 24413482Srekai.gonzalezalberquilla@arm.com return &((*_cq)[_idx]); 24513482Srekai.gonzalezalberquilla@arm.com } 24613482Srekai.gonzalezalberquilla@arm.com 24713482Srekai.gonzalezalberquilla@arm.com /** Pre-increment operator. */ 24813482Srekai.gonzalezalberquilla@arm.com iterator& operator++() 24913482Srekai.gonzalezalberquilla@arm.com { 25013482Srekai.gonzalezalberquilla@arm.com /* this has to be dereferenceable. */ 25113482Srekai.gonzalezalberquilla@arm.com _cq->increase(_idx); 25213482Srekai.gonzalezalberquilla@arm.com if (_idx == 0) 25313482Srekai.gonzalezalberquilla@arm.com ++_round; 25413482Srekai.gonzalezalberquilla@arm.com return *this; 25513482Srekai.gonzalezalberquilla@arm.com } 25613482Srekai.gonzalezalberquilla@arm.com 25713482Srekai.gonzalezalberquilla@arm.com /** Post-increment operator. */ 25813482Srekai.gonzalezalberquilla@arm.com iterator 25913482Srekai.gonzalezalberquilla@arm.com operator++(int) 26013482Srekai.gonzalezalberquilla@arm.com { 26113482Srekai.gonzalezalberquilla@arm.com iterator t = *this; 26213482Srekai.gonzalezalberquilla@arm.com ++*this; 26313482Srekai.gonzalezalberquilla@arm.com return t; 26413482Srekai.gonzalezalberquilla@arm.com } 26513482Srekai.gonzalezalberquilla@arm.com 26613482Srekai.gonzalezalberquilla@arm.com /** ForwardIterator 26713482Srekai.gonzalezalberquilla@arm.com * The multipass guarantee is provided by the reliance on _idx. 26813482Srekai.gonzalezalberquilla@arm.com */ 26913482Srekai.gonzalezalberquilla@arm.com 27013482Srekai.gonzalezalberquilla@arm.com /** BidirectionalIterator requirements. */ 27113482Srekai.gonzalezalberquilla@arm.com private: 27213482Srekai.gonzalezalberquilla@arm.com /** Test decrementability. 27313482Srekai.gonzalezalberquilla@arm.com * An iterator to a non-null circular queue is not-decrementable 27413482Srekai.gonzalezalberquilla@arm.com * if it is pointing to the head element, unless the queue is full 27513482Srekai.gonzalezalberquilla@arm.com * and we are talking about the past-the-end iterator. In that case, 27613482Srekai.gonzalezalberquilla@arm.com * the iterator round equals the cq round unless the head is at the 27713482Srekai.gonzalezalberquilla@arm.com * zero position and the round is one more than the cq round. 27813482Srekai.gonzalezalberquilla@arm.com */ 27913482Srekai.gonzalezalberquilla@arm.com bool 28013482Srekai.gonzalezalberquilla@arm.com decrementable() const 28113482Srekai.gonzalezalberquilla@arm.com { 28213482Srekai.gonzalezalberquilla@arm.com return _cq && !(_idx == _cq->head() && 28313482Srekai.gonzalezalberquilla@arm.com (_cq->empty() || 28413482Srekai.gonzalezalberquilla@arm.com (_idx == 0 && _round != _cq->_round + 1) || 28513482Srekai.gonzalezalberquilla@arm.com (_idx !=0 && _round != _cq->_round))); 28613482Srekai.gonzalezalberquilla@arm.com } 28713482Srekai.gonzalezalberquilla@arm.com 28813482Srekai.gonzalezalberquilla@arm.com public: 28913482Srekai.gonzalezalberquilla@arm.com /** Pre-decrement operator. */ 29013482Srekai.gonzalezalberquilla@arm.com iterator& operator--() 29113482Srekai.gonzalezalberquilla@arm.com { 29213482Srekai.gonzalezalberquilla@arm.com /* this has to be decrementable. */ 29313482Srekai.gonzalezalberquilla@arm.com assert(decrementable()); 29413482Srekai.gonzalezalberquilla@arm.com if (_idx == 0) 29513482Srekai.gonzalezalberquilla@arm.com --_round; 29613482Srekai.gonzalezalberquilla@arm.com _cq->decrease(_idx); 29713482Srekai.gonzalezalberquilla@arm.com return *this; 29813482Srekai.gonzalezalberquilla@arm.com } 29913482Srekai.gonzalezalberquilla@arm.com 30013482Srekai.gonzalezalberquilla@arm.com /** Post-decrement operator. */ 30113482Srekai.gonzalezalberquilla@arm.com iterator operator--(int ) { iterator t = *this; --*this; return t; } 30213482Srekai.gonzalezalberquilla@arm.com 30313482Srekai.gonzalezalberquilla@arm.com /** RandomAccessIterator requirements.*/ 30413482Srekai.gonzalezalberquilla@arm.com iterator& operator+=(const difference_type& t) 30513482Srekai.gonzalezalberquilla@arm.com { 30613482Srekai.gonzalezalberquilla@arm.com assert(_cq); 30713482Srekai.gonzalezalberquilla@arm.com _round += (t + _idx) / _cq->capacity(); 30813482Srekai.gonzalezalberquilla@arm.com _idx = _cq->moduloAdd(_idx, t); 30913482Srekai.gonzalezalberquilla@arm.com return *this; 31013482Srekai.gonzalezalberquilla@arm.com } 31113482Srekai.gonzalezalberquilla@arm.com 31213482Srekai.gonzalezalberquilla@arm.com iterator& operator-=(const difference_type& t) 31313482Srekai.gonzalezalberquilla@arm.com { 31413482Srekai.gonzalezalberquilla@arm.com assert(_cq); 31513482Srekai.gonzalezalberquilla@arm.com 31613482Srekai.gonzalezalberquilla@arm.com /* C does not do euclidean division, so we have to adjust */ 31713482Srekai.gonzalezalberquilla@arm.com if (t >= 0) 31813482Srekai.gonzalezalberquilla@arm.com _round += (-t + _idx) / _cq->capacity(); 31913482Srekai.gonzalezalberquilla@arm.com else 32013482Srekai.gonzalezalberquilla@arm.com _round += (-t + _idx - _cq->capacity() + 1) / _cq->capacity(); 32113482Srekai.gonzalezalberquilla@arm.com 32213482Srekai.gonzalezalberquilla@arm.com _idx = _cq->moduloSub(_idx, t); 32313482Srekai.gonzalezalberquilla@arm.com return *this; 32413482Srekai.gonzalezalberquilla@arm.com } 32513482Srekai.gonzalezalberquilla@arm.com 32613482Srekai.gonzalezalberquilla@arm.com /** Addition operator. */ 32713482Srekai.gonzalezalberquilla@arm.com iterator operator+(const difference_type& t) 32813482Srekai.gonzalezalberquilla@arm.com { 32913482Srekai.gonzalezalberquilla@arm.com iterator ret(*this); 33013482Srekai.gonzalezalberquilla@arm.com return ret += t; 33113482Srekai.gonzalezalberquilla@arm.com } 33213482Srekai.gonzalezalberquilla@arm.com 33313482Srekai.gonzalezalberquilla@arm.com friend iterator operator+(const difference_type& t, iterator& it) 33413482Srekai.gonzalezalberquilla@arm.com { 33513482Srekai.gonzalezalberquilla@arm.com iterator ret = it; 33613482Srekai.gonzalezalberquilla@arm.com return ret += t; 33713482Srekai.gonzalezalberquilla@arm.com } 33813482Srekai.gonzalezalberquilla@arm.com 33913482Srekai.gonzalezalberquilla@arm.com /** Substraction operator. */ 34013482Srekai.gonzalezalberquilla@arm.com iterator operator-(const difference_type& t) 34113482Srekai.gonzalezalberquilla@arm.com { 34213482Srekai.gonzalezalberquilla@arm.com iterator ret(*this); 34313482Srekai.gonzalezalberquilla@arm.com return ret -= t; 34413482Srekai.gonzalezalberquilla@arm.com } 34513482Srekai.gonzalezalberquilla@arm.com 34613482Srekai.gonzalezalberquilla@arm.com friend iterator operator-(const difference_type& t, iterator& it) 34713482Srekai.gonzalezalberquilla@arm.com { 34813482Srekai.gonzalezalberquilla@arm.com iterator ret = it; 34913482Srekai.gonzalezalberquilla@arm.com return ret -= t; 35013482Srekai.gonzalezalberquilla@arm.com } 35113482Srekai.gonzalezalberquilla@arm.com 35213482Srekai.gonzalezalberquilla@arm.com /** Difference operator. 35313482Srekai.gonzalezalberquilla@arm.com * that + ret == this 35413482Srekai.gonzalezalberquilla@arm.com */ 35513482Srekai.gonzalezalberquilla@arm.com difference_type operator-(const iterator& that) 35613482Srekai.gonzalezalberquilla@arm.com { 35713482Srekai.gonzalezalberquilla@arm.com /* If a is already at the end, we can safely return 0. */ 35813482Srekai.gonzalezalberquilla@arm.com auto ret = _cq->moduloSub(this->_idx, that._idx); 35913482Srekai.gonzalezalberquilla@arm.com 36013482Srekai.gonzalezalberquilla@arm.com if (ret == 0 && this->_round != that._round) { 36113482Srekai.gonzalezalberquilla@arm.com ret += this->_round * _cq->capacity(); 36213482Srekai.gonzalezalberquilla@arm.com } 36313482Srekai.gonzalezalberquilla@arm.com return ret; 36413482Srekai.gonzalezalberquilla@arm.com } 36513482Srekai.gonzalezalberquilla@arm.com 36613482Srekai.gonzalezalberquilla@arm.com /** Index operator. 36713482Srekai.gonzalezalberquilla@arm.com * The use of * tests for dereferenceability. 36813482Srekai.gonzalezalberquilla@arm.com */ 36913482Srekai.gonzalezalberquilla@arm.com template<typename Idx> 37013482Srekai.gonzalezalberquilla@arm.com typename std::enable_if<std::is_integral<Idx>::value,reference>::type 37113482Srekai.gonzalezalberquilla@arm.com operator[](const Idx& index) { return *(*this + index); } 37213482Srekai.gonzalezalberquilla@arm.com 37313482Srekai.gonzalezalberquilla@arm.com /** Comparisons. */ 37413482Srekai.gonzalezalberquilla@arm.com bool 37513482Srekai.gonzalezalberquilla@arm.com operator<(const iterator& that) const 37613482Srekai.gonzalezalberquilla@arm.com { 37713482Srekai.gonzalezalberquilla@arm.com assert(_cq && that._cq == _cq); 37813482Srekai.gonzalezalberquilla@arm.com return (this->_round < that._round) || 37913482Srekai.gonzalezalberquilla@arm.com (this->_round == that._round && _idx < that._idx); 38013482Srekai.gonzalezalberquilla@arm.com } 38113482Srekai.gonzalezalberquilla@arm.com 38213482Srekai.gonzalezalberquilla@arm.com bool 38313482Srekai.gonzalezalberquilla@arm.com operator>(const iterator& that) const 38413482Srekai.gonzalezalberquilla@arm.com { return !(*this <= that); } 38513482Srekai.gonzalezalberquilla@arm.com 38613482Srekai.gonzalezalberquilla@arm.com bool operator>=(const iterator& that) const 38713482Srekai.gonzalezalberquilla@arm.com { return !(*this < that); } 38813482Srekai.gonzalezalberquilla@arm.com 38913482Srekai.gonzalezalberquilla@arm.com bool operator<=(const iterator& that) const 39013482Srekai.gonzalezalberquilla@arm.com { return !(that < *this); } 39113482Srekai.gonzalezalberquilla@arm.com 39213482Srekai.gonzalezalberquilla@arm.com /** OutputIterator has no extra requirements.*/ 39313482Srekai.gonzalezalberquilla@arm.com size_t idx() const { return _idx; } 39413482Srekai.gonzalezalberquilla@arm.com }; 39513482Srekai.gonzalezalberquilla@arm.com 39613482Srekai.gonzalezalberquilla@arm.com public: 39713482Srekai.gonzalezalberquilla@arm.com using typename Base::operator[]; 39813482Srekai.gonzalezalberquilla@arm.com 39913482Srekai.gonzalezalberquilla@arm.com explicit CircularQueue(uint32_t size = 0) 40013482Srekai.gonzalezalberquilla@arm.com : _capacity(size), _head(1), _tail(0), _empty(true), _round(0) 40113482Srekai.gonzalezalberquilla@arm.com { 40213482Srekai.gonzalezalberquilla@arm.com Base::resize(size); 40313482Srekai.gonzalezalberquilla@arm.com } 40413482Srekai.gonzalezalberquilla@arm.com 40513482Srekai.gonzalezalberquilla@arm.com /** 40613482Srekai.gonzalezalberquilla@arm.com * Remove all the elements in the queue. 40713482Srekai.gonzalezalberquilla@arm.com * 40813482Srekai.gonzalezalberquilla@arm.com * Note: This does not actually remove elements from the backing 40913482Srekai.gonzalezalberquilla@arm.com * store. 41013482Srekai.gonzalezalberquilla@arm.com */ 41113482Srekai.gonzalezalberquilla@arm.com void flush() 41213482Srekai.gonzalezalberquilla@arm.com { 41313482Srekai.gonzalezalberquilla@arm.com _head = 1; 41413482Srekai.gonzalezalberquilla@arm.com _round = 0; 41513482Srekai.gonzalezalberquilla@arm.com _tail = 0; 41613482Srekai.gonzalezalberquilla@arm.com _empty = true; 41713482Srekai.gonzalezalberquilla@arm.com } 41813482Srekai.gonzalezalberquilla@arm.com 41913482Srekai.gonzalezalberquilla@arm.com /** Test if the index is in the range of valid elements. */ 42013482Srekai.gonzalezalberquilla@arm.com bool isValidIdx(size_t idx) const 42113482Srekai.gonzalezalberquilla@arm.com { 42213482Srekai.gonzalezalberquilla@arm.com /* An index is invalid if: 42313482Srekai.gonzalezalberquilla@arm.com * - The queue is empty. 42413482Srekai.gonzalezalberquilla@arm.com * (6,T,3,2): |-|-|-]|[-|-|x| 42513482Srekai.gonzalezalberquilla@arm.com * - head is small than tail and: 42613482Srekai.gonzalezalberquilla@arm.com * - It is greater than both head and tail. 42713482Srekai.gonzalezalberquilla@arm.com * (6,F,1,3): |-|[o|o|o]|-|x| 42813482Srekai.gonzalezalberquilla@arm.com * - It is less than both head and tail. 42913482Srekai.gonzalezalberquilla@arm.com * (6,F,1,3): |x|[o|o|o]|-|-| 43013482Srekai.gonzalezalberquilla@arm.com * - It is greater than the tail and not than the head. 43113482Srekai.gonzalezalberquilla@arm.com * (6,F,4,1): |o|o]|-|x|[o|o| 43213482Srekai.gonzalezalberquilla@arm.com */ 43313482Srekai.gonzalezalberquilla@arm.com return !(_empty || ( 43413482Srekai.gonzalezalberquilla@arm.com (_head < _tail) && ( 43513482Srekai.gonzalezalberquilla@arm.com (_head < idx && _tail < idx) || 43613482Srekai.gonzalezalberquilla@arm.com (_head > idx && _tail > idx) 43713482Srekai.gonzalezalberquilla@arm.com )) || (_tail < idx && idx < _head)); 43813482Srekai.gonzalezalberquilla@arm.com } 43913482Srekai.gonzalezalberquilla@arm.com 44013482Srekai.gonzalezalberquilla@arm.com /** Test if the index is in the range of valid elements. 44113482Srekai.gonzalezalberquilla@arm.com * The round counter is used to disambiguate aliasing. 44213482Srekai.gonzalezalberquilla@arm.com */ 44313482Srekai.gonzalezalberquilla@arm.com bool isValidIdx(size_t idx, uint32_t round) const 44413482Srekai.gonzalezalberquilla@arm.com { 44513482Srekai.gonzalezalberquilla@arm.com /* An index is valid if: 44613482Srekai.gonzalezalberquilla@arm.com * - The queue is not empty. 44713482Srekai.gonzalezalberquilla@arm.com * - round == R and 44813482Srekai.gonzalezalberquilla@arm.com * - index <= tail (if index > tail, that would be PTE) 44913482Srekai.gonzalezalberquilla@arm.com * - Either: 45013482Srekai.gonzalezalberquilla@arm.com * - head <= index 45113482Srekai.gonzalezalberquilla@arm.com * (6,F,1,3,R): |-|[o|(*,r)|o]|-|-| 45213482Srekai.gonzalezalberquilla@arm.com * - head > tail 45313482Srekai.gonzalezalberquilla@arm.com * (6,F,5,3,R): |o|o|(*,r)|o]|-|[o| 45413482Srekai.gonzalezalberquilla@arm.com * The remaining case means the the iterator is BTB: 45513482Srekai.gonzalezalberquilla@arm.com * (6,F,3,4,R): |-|-|(x,r)|[o|o]|-| 45613482Srekai.gonzalezalberquilla@arm.com * - round + 1 == R and: 45713482Srekai.gonzalezalberquilla@arm.com * - index > tail. If index <= tail, that would be BTB: 45813482Srekai.gonzalezalberquilla@arm.com * (6,F,2,3,r): | -|- |[(*,r)|o]|-|-| 45913482Srekai.gonzalezalberquilla@arm.com * (6,F,0,1,r+1): |[o|o]| (x,r)|- |-|-| 46013482Srekai.gonzalezalberquilla@arm.com * (6,F,0,3,r+1): |[o|o | (*,r)|o]|-|-| 46113482Srekai.gonzalezalberquilla@arm.com * - index >= head. If index < head, that would be BTB: 46213482Srekai.gonzalezalberquilla@arm.com * (6,F,5,2,R): |o|o]|-|-|(x,r)|[o| 46313482Srekai.gonzalezalberquilla@arm.com * - head > tail. If head <= tail, that would be BTB: 46413482Srekai.gonzalezalberquilla@arm.com * (6,F,3,4,R): |[o|o]|(x,r)|-|-|-| 46513482Srekai.gonzalezalberquilla@arm.com * Other values of the round meand that the index is PTE or BTB 46613482Srekai.gonzalezalberquilla@arm.com */ 46713482Srekai.gonzalezalberquilla@arm.com return (!_empty && ( 46813482Srekai.gonzalezalberquilla@arm.com (round == _round && idx <= _tail && ( 46913482Srekai.gonzalezalberquilla@arm.com _head <= idx || _head > _tail)) || 47013482Srekai.gonzalezalberquilla@arm.com (round + 1 == _round && 47113482Srekai.gonzalezalberquilla@arm.com idx > _tail && 47213482Srekai.gonzalezalberquilla@arm.com idx >= _head && 47313482Srekai.gonzalezalberquilla@arm.com _head > _tail) 47413482Srekai.gonzalezalberquilla@arm.com )); 47513482Srekai.gonzalezalberquilla@arm.com } 47613482Srekai.gonzalezalberquilla@arm.com 47713482Srekai.gonzalezalberquilla@arm.com reference front() { return (*this)[_head]; } 47813482Srekai.gonzalezalberquilla@arm.com reference back() { return (*this)[_tail]; } 47913482Srekai.gonzalezalberquilla@arm.com uint32_t head() const { return _head; } 48013482Srekai.gonzalezalberquilla@arm.com uint32_t tail() const { return _tail; } 48113482Srekai.gonzalezalberquilla@arm.com size_t capacity() const { return _capacity; } 48213482Srekai.gonzalezalberquilla@arm.com 48313482Srekai.gonzalezalberquilla@arm.com uint32_t size() const 48413482Srekai.gonzalezalberquilla@arm.com { 48513482Srekai.gonzalezalberquilla@arm.com if (_empty) 48613482Srekai.gonzalezalberquilla@arm.com return 0; 48713482Srekai.gonzalezalberquilla@arm.com else if (_head <= _tail) 48813482Srekai.gonzalezalberquilla@arm.com return _tail - _head + 1; 48913482Srekai.gonzalezalberquilla@arm.com else 49013482Srekai.gonzalezalberquilla@arm.com return _capacity - _head + _tail + 1; 49113482Srekai.gonzalezalberquilla@arm.com } 49213482Srekai.gonzalezalberquilla@arm.com 49313482Srekai.gonzalezalberquilla@arm.com uint32_t moduloAdd(uint32_t s1, uint32_t s2) const 49413482Srekai.gonzalezalberquilla@arm.com { 49513482Srekai.gonzalezalberquilla@arm.com return moduloAdd(s1, s2, _capacity); 49613482Srekai.gonzalezalberquilla@arm.com } 49713482Srekai.gonzalezalberquilla@arm.com 49813482Srekai.gonzalezalberquilla@arm.com uint32_t moduloSub(uint32_t s1, uint32_t s2) const 49913482Srekai.gonzalezalberquilla@arm.com { 50013482Srekai.gonzalezalberquilla@arm.com return moduloSub(s1, s2, _capacity); 50113482Srekai.gonzalezalberquilla@arm.com } 50213482Srekai.gonzalezalberquilla@arm.com 50313482Srekai.gonzalezalberquilla@arm.com /** Circularly increase the head pointer. 50413482Srekai.gonzalezalberquilla@arm.com * By increasing the head pointer we are removing elements from 50513482Srekai.gonzalezalberquilla@arm.com * the begin of the circular queue. 50613482Srekai.gonzalezalberquilla@arm.com * Check that the queue is not empty. And set it to empty if it 50713482Srekai.gonzalezalberquilla@arm.com * had only one value prior to insertion. 50813482Srekai.gonzalezalberquilla@arm.com * 50913482Srekai.gonzalezalberquilla@arm.com * @params num_elem number of elements to remove 51013482Srekai.gonzalezalberquilla@arm.com */ 51113482Srekai.gonzalezalberquilla@arm.com void pop_front(size_t num_elem = 1) 51213482Srekai.gonzalezalberquilla@arm.com { 51313482Srekai.gonzalezalberquilla@arm.com if (num_elem == 0) return; 51413482Srekai.gonzalezalberquilla@arm.com auto hIt = begin(); 51513482Srekai.gonzalezalberquilla@arm.com hIt += num_elem; 51613482Srekai.gonzalezalberquilla@arm.com assert(hIt <= end()); 51713482Srekai.gonzalezalberquilla@arm.com _empty = hIt == end(); 51813482Srekai.gonzalezalberquilla@arm.com _head = hIt._idx; 51913482Srekai.gonzalezalberquilla@arm.com } 52013482Srekai.gonzalezalberquilla@arm.com 52113482Srekai.gonzalezalberquilla@arm.com /** Circularly decrease the tail pointer. */ 52213482Srekai.gonzalezalberquilla@arm.com void pop_back() 52313482Srekai.gonzalezalberquilla@arm.com { 52413482Srekai.gonzalezalberquilla@arm.com assert (!_empty); 52513482Srekai.gonzalezalberquilla@arm.com _empty = _head == _tail; 52613482Srekai.gonzalezalberquilla@arm.com if (_tail == 0) 52713482Srekai.gonzalezalberquilla@arm.com --_round; 52813482Srekai.gonzalezalberquilla@arm.com decrease(_tail); 52913482Srekai.gonzalezalberquilla@arm.com } 53013482Srekai.gonzalezalberquilla@arm.com 53113482Srekai.gonzalezalberquilla@arm.com /** Pushes an element at the end of the queue. */ 53213482Srekai.gonzalezalberquilla@arm.com void push_back(typename Base::value_type val) 53313482Srekai.gonzalezalberquilla@arm.com { 53413482Srekai.gonzalezalberquilla@arm.com advance_tail(); 53513482Srekai.gonzalezalberquilla@arm.com (*this)[_tail] = val; 53613482Srekai.gonzalezalberquilla@arm.com } 53713482Srekai.gonzalezalberquilla@arm.com 53813482Srekai.gonzalezalberquilla@arm.com /** Increases the tail by one. 53913482Srekai.gonzalezalberquilla@arm.com * Check for wrap-arounds to update the round counter. 54013482Srekai.gonzalezalberquilla@arm.com */ 54113482Srekai.gonzalezalberquilla@arm.com void advance_tail() 54213482Srekai.gonzalezalberquilla@arm.com { 54313482Srekai.gonzalezalberquilla@arm.com increase(_tail); 54413482Srekai.gonzalezalberquilla@arm.com if (_tail == 0) 54513482Srekai.gonzalezalberquilla@arm.com ++_round; 54613482Srekai.gonzalezalberquilla@arm.com 54713482Srekai.gonzalezalberquilla@arm.com if (_tail == _head && !_empty) 54813482Srekai.gonzalezalberquilla@arm.com increase(_head); 54913482Srekai.gonzalezalberquilla@arm.com 55013482Srekai.gonzalezalberquilla@arm.com _empty = false; 55113482Srekai.gonzalezalberquilla@arm.com } 55213482Srekai.gonzalezalberquilla@arm.com 55313482Srekai.gonzalezalberquilla@arm.com /** Increases the tail by a specified number of steps 55413482Srekai.gonzalezalberquilla@arm.com * 55513482Srekai.gonzalezalberquilla@arm.com * @param len Number of steps 55613482Srekai.gonzalezalberquilla@arm.com */ 55713482Srekai.gonzalezalberquilla@arm.com void advance_tail(uint32_t len) 55813482Srekai.gonzalezalberquilla@arm.com { 55913482Srekai.gonzalezalberquilla@arm.com for (auto idx = 0; idx < len; idx++) 56013482Srekai.gonzalezalberquilla@arm.com advance_tail(); 56113482Srekai.gonzalezalberquilla@arm.com } 56213482Srekai.gonzalezalberquilla@arm.com 56313482Srekai.gonzalezalberquilla@arm.com /** Is the queue empty? */ 56413482Srekai.gonzalezalberquilla@arm.com bool empty() const { return _empty; } 56513482Srekai.gonzalezalberquilla@arm.com 56613482Srekai.gonzalezalberquilla@arm.com /** Is the queue full? 56713482Srekai.gonzalezalberquilla@arm.com * A queue is full if the head is the 0^{th} element and the tail is 56813482Srekai.gonzalezalberquilla@arm.com * the (size-1)^{th} element, or if the head is the n^{th} element and 56913482Srekai.gonzalezalberquilla@arm.com * the tail the (n-1)^{th} element. 57013482Srekai.gonzalezalberquilla@arm.com */ 57113482Srekai.gonzalezalberquilla@arm.com bool full() const 57213482Srekai.gonzalezalberquilla@arm.com { 57313482Srekai.gonzalezalberquilla@arm.com return !_empty && 57413482Srekai.gonzalezalberquilla@arm.com (_tail + 1 == _head || (_tail + 1 == _capacity && _head == 0)); 57513482Srekai.gonzalezalberquilla@arm.com } 57613482Srekai.gonzalezalberquilla@arm.com 57713482Srekai.gonzalezalberquilla@arm.com /** Iterators. */ 57813482Srekai.gonzalezalberquilla@arm.com iterator begin() 57913482Srekai.gonzalezalberquilla@arm.com { 58013482Srekai.gonzalezalberquilla@arm.com if (_empty) 58113482Srekai.gonzalezalberquilla@arm.com return end(); 58213482Srekai.gonzalezalberquilla@arm.com else if (_head > _tail) 58313482Srekai.gonzalezalberquilla@arm.com return iterator(this, _head, _round - 1); 58413482Srekai.gonzalezalberquilla@arm.com else 58513482Srekai.gonzalezalberquilla@arm.com return iterator(this, _head, _round); 58613482Srekai.gonzalezalberquilla@arm.com } 58713482Srekai.gonzalezalberquilla@arm.com 58813482Srekai.gonzalezalberquilla@arm.com /* TODO: This should return a const_iterator. */ 58913482Srekai.gonzalezalberquilla@arm.com iterator begin() const 59013482Srekai.gonzalezalberquilla@arm.com { 59113482Srekai.gonzalezalberquilla@arm.com if (_empty) 59213482Srekai.gonzalezalberquilla@arm.com return end(); 59313482Srekai.gonzalezalberquilla@arm.com else if (_head > _tail) 59413482Srekai.gonzalezalberquilla@arm.com return iterator(const_cast<CircularQueue*>(this), _head, 59513482Srekai.gonzalezalberquilla@arm.com _round - 1); 59613482Srekai.gonzalezalberquilla@arm.com else 59713482Srekai.gonzalezalberquilla@arm.com return iterator(const_cast<CircularQueue*>(this), _head, 59813482Srekai.gonzalezalberquilla@arm.com _round); 59913482Srekai.gonzalezalberquilla@arm.com } 60013482Srekai.gonzalezalberquilla@arm.com 60113482Srekai.gonzalezalberquilla@arm.com iterator end() 60213482Srekai.gonzalezalberquilla@arm.com { 60313482Srekai.gonzalezalberquilla@arm.com auto poi = moduloAdd(_tail, 1); 60413482Srekai.gonzalezalberquilla@arm.com auto round = _round; 60513482Srekai.gonzalezalberquilla@arm.com if (poi == 0) 60613482Srekai.gonzalezalberquilla@arm.com ++round; 60713482Srekai.gonzalezalberquilla@arm.com return iterator(this, poi, round); 60813482Srekai.gonzalezalberquilla@arm.com } 60913482Srekai.gonzalezalberquilla@arm.com 61013482Srekai.gonzalezalberquilla@arm.com iterator end() const 61113482Srekai.gonzalezalberquilla@arm.com { 61213482Srekai.gonzalezalberquilla@arm.com auto poi = moduloAdd(_tail, 1); 61313482Srekai.gonzalezalberquilla@arm.com auto round = _round; 61413482Srekai.gonzalezalberquilla@arm.com if (poi == 0) 61513482Srekai.gonzalezalberquilla@arm.com ++round; 61613482Srekai.gonzalezalberquilla@arm.com return iterator(const_cast<CircularQueue*>(this), poi, round); 61713482Srekai.gonzalezalberquilla@arm.com } 61813482Srekai.gonzalezalberquilla@arm.com 61913482Srekai.gonzalezalberquilla@arm.com /** Return an iterator to an index in the vector. 62013482Srekai.gonzalezalberquilla@arm.com * This poses the problem of round determination. By convention, the round 62113482Srekai.gonzalezalberquilla@arm.com * is picked so that isValidIndex(idx, round) is true. If that is not 62213482Srekai.gonzalezalberquilla@arm.com * possible, then the round value is _round, unless _tail is at the end of 62313482Srekai.gonzalezalberquilla@arm.com * the storage, in which case the PTE wraps up and becomes _round + 1 62413482Srekai.gonzalezalberquilla@arm.com */ 62513482Srekai.gonzalezalberquilla@arm.com iterator getIterator(size_t idx) 62613482Srekai.gonzalezalberquilla@arm.com { 62713482Srekai.gonzalezalberquilla@arm.com assert(isValidIdx(idx) || moduloAdd(_tail, 1) == idx); 62813482Srekai.gonzalezalberquilla@arm.com if (_empty) 62913482Srekai.gonzalezalberquilla@arm.com return end(); 63013482Srekai.gonzalezalberquilla@arm.com 63113482Srekai.gonzalezalberquilla@arm.com uint32_t round = _round; 63213482Srekai.gonzalezalberquilla@arm.com if (idx > _tail) { 63313482Srekai.gonzalezalberquilla@arm.com if (idx >= _head && _head > _tail) { 63413482Srekai.gonzalezalberquilla@arm.com round -= 1; 63513482Srekai.gonzalezalberquilla@arm.com } 63613482Srekai.gonzalezalberquilla@arm.com } else if (idx < _head && _tail + 1 == _capacity) { 63713482Srekai.gonzalezalberquilla@arm.com round += 1; 63813482Srekai.gonzalezalberquilla@arm.com } 63913482Srekai.gonzalezalberquilla@arm.com return iterator(this, idx, round); 64013482Srekai.gonzalezalberquilla@arm.com } 64113482Srekai.gonzalezalberquilla@arm.com}; 64213482Srekai.gonzalezalberquilla@arm.com 64313482Srekai.gonzalezalberquilla@arm.com#endif /* __BASE_CIRCULARQUEUE_HH__ */ 644