circular_queue.hh revision 14036
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 4314036Sodanrc@yahoo.com.br#include <cassert> 4414036Sodanrc@yahoo.com.br#include <cstddef> 4514036Sodanrc@yahoo.com.br#include <cstdint> 4614036Sodanrc@yahoo.com.br#include <iterator> 4714036Sodanrc@yahoo.com.br#include <type_traits> 4813482Srekai.gonzalezalberquilla@arm.com#include <vector> 4913482Srekai.gonzalezalberquilla@arm.com 5013482Srekai.gonzalezalberquilla@arm.com/** Circular queue. 5113482Srekai.gonzalezalberquilla@arm.com * Circular queue implemented on top of a standard vector. Instead of using 5213482Srekai.gonzalezalberquilla@arm.com * a sentinel entry, we use a boolean to distinguish the case in which the 5313482Srekai.gonzalezalberquilla@arm.com * queue is full or empty. 5413482Srekai.gonzalezalberquilla@arm.com * Thus, a circular queue is represented by the 5-tuple 5513482Srekai.gonzalezalberquilla@arm.com * (Capacity, IsEmpty?, Head, Tail, Round) 5613482Srekai.gonzalezalberquilla@arm.com * Where: 5713482Srekai.gonzalezalberquilla@arm.com * - Capacity is the size of the underlying vector. 5813482Srekai.gonzalezalberquilla@arm.com * - IsEmpty? can be T or F. 5913482Srekai.gonzalezalberquilla@arm.com * - Head is the index in the vector of the first element of the queue. 6013482Srekai.gonzalezalberquilla@arm.com * - Tail is the index in the vector of the last element of the queue. 6113482Srekai.gonzalezalberquilla@arm.com * - Round is the counter of how many times the Tail has wrapped around. 6213482Srekai.gonzalezalberquilla@arm.com * A queue is empty when 6313482Srekai.gonzalezalberquilla@arm.com * Head == (Tail + 1 mod Capacity) && IsEmpty?. 6413482Srekai.gonzalezalberquilla@arm.com * Conversely, a queue if full when 6513482Srekai.gonzalezalberquilla@arm.com * Head == (Tail + 1 mod Capacity) && !IsEmpty?. 6613482Srekai.gonzalezalberquilla@arm.com * Comments may show depictions of the underlying vector in the following 6713482Srekai.gonzalezalberquilla@arm.com * format: '|' delimit the 'cells' of the underlying vector. '-' represents 6813482Srekai.gonzalezalberquilla@arm.com * an element of the vector that is out-of-bounds of the circular queue, 6913482Srekai.gonzalezalberquilla@arm.com * while 'o' represents and element that is inside the bounds. The 7013482Srekai.gonzalezalberquilla@arm.com * characters '[' and ']' are added to mark the entries that hold the head 7113482Srekai.gonzalezalberquilla@arm.com * and tail of the circular queue respectively. 7213482Srekai.gonzalezalberquilla@arm.com * E.g.: 7313482Srekai.gonzalezalberquilla@arm.com * - Empty queues of capacity 4: 7413482Srekai.gonzalezalberquilla@arm.com * (4,T,1,0,_): |-]|[-|-|-| (4,T,3,2): |-|-|-]|[-| 7513482Srekai.gonzalezalberquilla@arm.com * - Full queues of capacity 4: 7613482Srekai.gonzalezalberquilla@arm.com * (4,F,1,0,_): |o]|[o|o|o| (4,F,3,2): |o|o|o]|[o| 7713482Srekai.gonzalezalberquilla@arm.com * - Queues of capacity 4 with 2 elements: 7813482Srekai.gonzalezalberquilla@arm.com * (4,F,0,1,_): |[o|o]|-|-| (4,F,3,0): |o]|-|-|[o| 7913482Srekai.gonzalezalberquilla@arm.com * 8013482Srekai.gonzalezalberquilla@arm.com * The Round number is only relevant for checking validity of indices, 8113482Srekai.gonzalezalberquilla@arm.com * therefore it will be omitted or shown as '_' 8213482Srekai.gonzalezalberquilla@arm.com */ 8313482Srekai.gonzalezalberquilla@arm.comtemplate <typename T> 8413482Srekai.gonzalezalberquilla@arm.comclass CircularQueue : private std::vector<T> 8513482Srekai.gonzalezalberquilla@arm.com{ 8613482Srekai.gonzalezalberquilla@arm.com protected: 8713482Srekai.gonzalezalberquilla@arm.com using Base = std::vector<T>; 8813482Srekai.gonzalezalberquilla@arm.com using typename Base::reference; 8913482Srekai.gonzalezalberquilla@arm.com using typename Base::const_reference; 9013482Srekai.gonzalezalberquilla@arm.com const uint32_t _capacity; 9113482Srekai.gonzalezalberquilla@arm.com uint32_t _head; 9213482Srekai.gonzalezalberquilla@arm.com uint32_t _tail; 9313482Srekai.gonzalezalberquilla@arm.com uint32_t _empty; 9413482Srekai.gonzalezalberquilla@arm.com 9513482Srekai.gonzalezalberquilla@arm.com /** Counter for how many times the tail wraps around. 9613482Srekai.gonzalezalberquilla@arm.com * Some parts of the code rely on getting the past the end iterator, and 9713482Srekai.gonzalezalberquilla@arm.com * expect to use it after inserting on the tail. To support this without 9813482Srekai.gonzalezalberquilla@arm.com * ambiguity, we need the round number to guarantee that it did not become 9913482Srekai.gonzalezalberquilla@arm.com * a before-the-beginning iterator. 10013482Srekai.gonzalezalberquilla@arm.com */ 10113482Srekai.gonzalezalberquilla@arm.com uint32_t _round; 10213482Srekai.gonzalezalberquilla@arm.com 10313482Srekai.gonzalezalberquilla@arm.com /** General modular addition. */ 10413482Srekai.gonzalezalberquilla@arm.com static uint32_t 10513482Srekai.gonzalezalberquilla@arm.com moduloAdd(uint32_t op1, uint32_t op2, uint32_t size) 10613482Srekai.gonzalezalberquilla@arm.com { 10713482Srekai.gonzalezalberquilla@arm.com return (op1 + op2) % size; 10813482Srekai.gonzalezalberquilla@arm.com } 10913482Srekai.gonzalezalberquilla@arm.com 11013482Srekai.gonzalezalberquilla@arm.com /** General modular subtraction. */ 11113482Srekai.gonzalezalberquilla@arm.com static uint32_t 11213482Srekai.gonzalezalberquilla@arm.com moduloSub(uint32_t op1, uint32_t op2, uint32_t size) 11313482Srekai.gonzalezalberquilla@arm.com { 11413796Sgiacomo.travaglini@arm.com int32_t ret = sub(op1, op2, size); 11513482Srekai.gonzalezalberquilla@arm.com return ret >= 0 ? ret : ret + size; 11613482Srekai.gonzalezalberquilla@arm.com } 11713482Srekai.gonzalezalberquilla@arm.com 11813796Sgiacomo.travaglini@arm.com static int32_t 11913796Sgiacomo.travaglini@arm.com sub(uint32_t op1, uint32_t op2, uint32_t size) 12013796Sgiacomo.travaglini@arm.com { 12113796Sgiacomo.travaglini@arm.com if (op1 > op2) 12213796Sgiacomo.travaglini@arm.com return (op1 - op2) % size; 12313796Sgiacomo.travaglini@arm.com else 12413796Sgiacomo.travaglini@arm.com return -((op2 - op1) % size); 12513796Sgiacomo.travaglini@arm.com } 12613796Sgiacomo.travaglini@arm.com 12713482Srekai.gonzalezalberquilla@arm.com void increase(uint32_t& v, size_t delta = 1) 12813482Srekai.gonzalezalberquilla@arm.com { 12913482Srekai.gonzalezalberquilla@arm.com v = moduloAdd(v, delta, _capacity); 13013482Srekai.gonzalezalberquilla@arm.com } 13113482Srekai.gonzalezalberquilla@arm.com 13213482Srekai.gonzalezalberquilla@arm.com void decrease(uint32_t& v) 13313482Srekai.gonzalezalberquilla@arm.com { 13413482Srekai.gonzalezalberquilla@arm.com v = (v ? v : _capacity) - 1; 13513482Srekai.gonzalezalberquilla@arm.com } 13613482Srekai.gonzalezalberquilla@arm.com 13713482Srekai.gonzalezalberquilla@arm.com /** Iterator to the circular queue. 13813482Srekai.gonzalezalberquilla@arm.com * iterator implementation to provide the circular-ness that the 13913482Srekai.gonzalezalberquilla@arm.com * standard std::vector<T>::iterator does not implement. 14013482Srekai.gonzalezalberquilla@arm.com * Iterators to a queue are represented by a pair of a character and the 14113482Srekai.gonzalezalberquilla@arm.com * round counter. For the character, '*' denotes the element pointed to by 14213482Srekai.gonzalezalberquilla@arm.com * the iterator if it is valid. 'x' denotes the element pointed to by the 14313482Srekai.gonzalezalberquilla@arm.com * iterator when it is BTB or PTE. 14413482Srekai.gonzalezalberquilla@arm.com * E.g.: 14513482Srekai.gonzalezalberquilla@arm.com * - Iterator to the head of a queue of capacity 4 with 2 elems. 14613482Srekai.gonzalezalberquilla@arm.com * (4,F,0,1,R): |[(*,R)|o]|-|-| (4,F,3,0): |o]|-|-|[(*,R)| 14713482Srekai.gonzalezalberquilla@arm.com * - Iterator to the tail of a queue of capacity 4 with 2 elems. 14813482Srekai.gonzalezalberquilla@arm.com * (4,F,0,1,R): |[o|(*,R)]|-|-| (4,F,3,0): |(*,R)]|-|-|[o| 14913482Srekai.gonzalezalberquilla@arm.com * - Iterator to the end of a queue of capacity 4 with 2 elems. 15013482Srekai.gonzalezalberquilla@arm.com * (4,F,0,1,R): |[o|o]|(x,R)|-| (4,F,3,0): |o]|(x,R)|-|[o| 15113482Srekai.gonzalezalberquilla@arm.com */ 15213482Srekai.gonzalezalberquilla@arm.com public: 15313482Srekai.gonzalezalberquilla@arm.com struct iterator { 15413482Srekai.gonzalezalberquilla@arm.com CircularQueue* _cq; 15513482Srekai.gonzalezalberquilla@arm.com uint32_t _idx; 15613482Srekai.gonzalezalberquilla@arm.com uint32_t _round; 15713482Srekai.gonzalezalberquilla@arm.com 15813482Srekai.gonzalezalberquilla@arm.com public: 15913482Srekai.gonzalezalberquilla@arm.com iterator(CircularQueue* cq, uint32_t idx, uint32_t round) 16013482Srekai.gonzalezalberquilla@arm.com : _cq(cq), _idx(idx), _round(round) {} 16113482Srekai.gonzalezalberquilla@arm.com 16213482Srekai.gonzalezalberquilla@arm.com /** Iterator Traits */ 16313482Srekai.gonzalezalberquilla@arm.com using value_type = T; 16413482Srekai.gonzalezalberquilla@arm.com using difference_type = std::ptrdiff_t; 16513482Srekai.gonzalezalberquilla@arm.com using reference = value_type&; 16613482Srekai.gonzalezalberquilla@arm.com using const_reference = const value_type&; 16713482Srekai.gonzalezalberquilla@arm.com using pointer = value_type*; 16813482Srekai.gonzalezalberquilla@arm.com using const_pointer = const value_type*; 16913482Srekai.gonzalezalberquilla@arm.com using iterator_category = std::random_access_iterator_tag; 17013482Srekai.gonzalezalberquilla@arm.com 17113482Srekai.gonzalezalberquilla@arm.com /** Trait reference type 17213482Srekai.gonzalezalberquilla@arm.com * iterator satisfies OutputIterator, therefore reference 17313482Srekai.gonzalezalberquilla@arm.com * must be T& */ 17413482Srekai.gonzalezalberquilla@arm.com static_assert(std::is_same<reference, T&>::value, 17513482Srekai.gonzalezalberquilla@arm.com "reference type is not assignable as required"); 17613482Srekai.gonzalezalberquilla@arm.com 17713482Srekai.gonzalezalberquilla@arm.com iterator() : _cq(nullptr), _idx(0), _round(0) { } 17813482Srekai.gonzalezalberquilla@arm.com 17913482Srekai.gonzalezalberquilla@arm.com iterator(const iterator& it) 18013482Srekai.gonzalezalberquilla@arm.com : _cq(it._cq), _idx(it._idx), _round(it._round) {} 18113482Srekai.gonzalezalberquilla@arm.com 18213482Srekai.gonzalezalberquilla@arm.com iterator& 18313482Srekai.gonzalezalberquilla@arm.com operator=(const iterator& it) 18413482Srekai.gonzalezalberquilla@arm.com { 18513482Srekai.gonzalezalberquilla@arm.com _cq = it._cq; 18613482Srekai.gonzalezalberquilla@arm.com _idx = it._idx; 18713482Srekai.gonzalezalberquilla@arm.com _round = it._round; 18813482Srekai.gonzalezalberquilla@arm.com return *this; 18913482Srekai.gonzalezalberquilla@arm.com } 19013482Srekai.gonzalezalberquilla@arm.com 19113482Srekai.gonzalezalberquilla@arm.com ~iterator() { _cq = nullptr; _idx = 0; _round = 0; } 19213482Srekai.gonzalezalberquilla@arm.com 19313482Srekai.gonzalezalberquilla@arm.com /** Test dereferenceability. 19413482Srekai.gonzalezalberquilla@arm.com * An iterator is dereferenceable if it is pointing to a non-null 19513482Srekai.gonzalezalberquilla@arm.com * circular queue, it is not the past-the-end iterator and the 19613482Srekai.gonzalezalberquilla@arm.com * index is a valid index to that queue. PTE test is required to 19713482Srekai.gonzalezalberquilla@arm.com * distinguish between: 19813482Srekai.gonzalezalberquilla@arm.com * - An iterator to the first element of a full queue 19913482Srekai.gonzalezalberquilla@arm.com * (4,F,1,0): |o]|[*|o|o| 20013482Srekai.gonzalezalberquilla@arm.com * - The end() iterator of a full queue 20113482Srekai.gonzalezalberquilla@arm.com * (4,F,1,0): |o]|x[o|o|o| 20213482Srekai.gonzalezalberquilla@arm.com * Sometimes, though, users will get the PTE iterator and expect it 20313482Srekai.gonzalezalberquilla@arm.com * to work after growing the buffer on the tail, so we have to 20413482Srekai.gonzalezalberquilla@arm.com * check if the iterator is still PTE. 20513482Srekai.gonzalezalberquilla@arm.com */ 20613482Srekai.gonzalezalberquilla@arm.com bool 20713482Srekai.gonzalezalberquilla@arm.com dereferenceable() const 20813482Srekai.gonzalezalberquilla@arm.com { 20913482Srekai.gonzalezalberquilla@arm.com return _cq != nullptr && _cq->isValidIdx(_idx, _round); 21013482Srekai.gonzalezalberquilla@arm.com } 21113482Srekai.gonzalezalberquilla@arm.com 21213482Srekai.gonzalezalberquilla@arm.com /** InputIterator. */ 21313482Srekai.gonzalezalberquilla@arm.com 21413482Srekai.gonzalezalberquilla@arm.com /** Equality operator. 21513482Srekai.gonzalezalberquilla@arm.com * Two iterators must point to the same, possibly null, circular 21613482Srekai.gonzalezalberquilla@arm.com * queue and the same element on it, including PTE, to be equal. 21713482Srekai.gonzalezalberquilla@arm.com * In case the clients the the PTE iterator and then grow on the back 21813482Srekai.gonzalezalberquilla@arm.com * and expect it to work, we have to check if the PTE is still PTE 21913482Srekai.gonzalezalberquilla@arm.com */ 22013482Srekai.gonzalezalberquilla@arm.com bool operator==(const iterator& that) const 22113482Srekai.gonzalezalberquilla@arm.com { 22213482Srekai.gonzalezalberquilla@arm.com return _cq == that._cq && _idx == that._idx && 22313482Srekai.gonzalezalberquilla@arm.com _round == that._round; 22413482Srekai.gonzalezalberquilla@arm.com } 22513482Srekai.gonzalezalberquilla@arm.com 22613482Srekai.gonzalezalberquilla@arm.com /** Inequality operator. 22713482Srekai.gonzalezalberquilla@arm.com * Conversely, two iterators are different if they both point to 22813482Srekai.gonzalezalberquilla@arm.com * different circular queues or they point to different elements. 22913482Srekai.gonzalezalberquilla@arm.com */ 23013482Srekai.gonzalezalberquilla@arm.com bool operator!=(const iterator& that) 23113482Srekai.gonzalezalberquilla@arm.com { 23213482Srekai.gonzalezalberquilla@arm.com return !(*this == that); 23313482Srekai.gonzalezalberquilla@arm.com } 23413482Srekai.gonzalezalberquilla@arm.com 23513482Srekai.gonzalezalberquilla@arm.com /** Dereference operator. */ 23613482Srekai.gonzalezalberquilla@arm.com reference operator*() 23713482Srekai.gonzalezalberquilla@arm.com { 23813482Srekai.gonzalezalberquilla@arm.com /* this has to be dereferenceable. */ 23913482Srekai.gonzalezalberquilla@arm.com return (*_cq)[_idx]; 24013482Srekai.gonzalezalberquilla@arm.com } 24113482Srekai.gonzalezalberquilla@arm.com 24213482Srekai.gonzalezalberquilla@arm.com const_reference operator*() const 24313482Srekai.gonzalezalberquilla@arm.com { 24413482Srekai.gonzalezalberquilla@arm.com /* this has to be dereferenceable. */ 24513482Srekai.gonzalezalberquilla@arm.com return (*_cq)[_idx]; 24613482Srekai.gonzalezalberquilla@arm.com } 24713482Srekai.gonzalezalberquilla@arm.com 24813482Srekai.gonzalezalberquilla@arm.com /** Dereference operator. 24913482Srekai.gonzalezalberquilla@arm.com * Rely on operator* to check for dereferenceability. 25013482Srekai.gonzalezalberquilla@arm.com */ 25113482Srekai.gonzalezalberquilla@arm.com pointer operator->() 25213482Srekai.gonzalezalberquilla@arm.com { 25313482Srekai.gonzalezalberquilla@arm.com return &((*_cq)[_idx]); 25413482Srekai.gonzalezalberquilla@arm.com } 25513482Srekai.gonzalezalberquilla@arm.com 25613482Srekai.gonzalezalberquilla@arm.com const_pointer operator->() const 25713482Srekai.gonzalezalberquilla@arm.com { 25813482Srekai.gonzalezalberquilla@arm.com return &((*_cq)[_idx]); 25913482Srekai.gonzalezalberquilla@arm.com } 26013482Srekai.gonzalezalberquilla@arm.com 26113482Srekai.gonzalezalberquilla@arm.com /** Pre-increment operator. */ 26213482Srekai.gonzalezalberquilla@arm.com iterator& operator++() 26313482Srekai.gonzalezalberquilla@arm.com { 26413482Srekai.gonzalezalberquilla@arm.com /* this has to be dereferenceable. */ 26513482Srekai.gonzalezalberquilla@arm.com _cq->increase(_idx); 26613482Srekai.gonzalezalberquilla@arm.com if (_idx == 0) 26713482Srekai.gonzalezalberquilla@arm.com ++_round; 26813482Srekai.gonzalezalberquilla@arm.com return *this; 26913482Srekai.gonzalezalberquilla@arm.com } 27013482Srekai.gonzalezalberquilla@arm.com 27113482Srekai.gonzalezalberquilla@arm.com /** Post-increment operator. */ 27213482Srekai.gonzalezalberquilla@arm.com iterator 27313482Srekai.gonzalezalberquilla@arm.com operator++(int) 27413482Srekai.gonzalezalberquilla@arm.com { 27513482Srekai.gonzalezalberquilla@arm.com iterator t = *this; 27613482Srekai.gonzalezalberquilla@arm.com ++*this; 27713482Srekai.gonzalezalberquilla@arm.com return t; 27813482Srekai.gonzalezalberquilla@arm.com } 27913482Srekai.gonzalezalberquilla@arm.com 28013482Srekai.gonzalezalberquilla@arm.com /** ForwardIterator 28113482Srekai.gonzalezalberquilla@arm.com * The multipass guarantee is provided by the reliance on _idx. 28213482Srekai.gonzalezalberquilla@arm.com */ 28313482Srekai.gonzalezalberquilla@arm.com 28413482Srekai.gonzalezalberquilla@arm.com /** BidirectionalIterator requirements. */ 28513482Srekai.gonzalezalberquilla@arm.com private: 28613482Srekai.gonzalezalberquilla@arm.com /** Test decrementability. 28713482Srekai.gonzalezalberquilla@arm.com * An iterator to a non-null circular queue is not-decrementable 28813482Srekai.gonzalezalberquilla@arm.com * if it is pointing to the head element, unless the queue is full 28913482Srekai.gonzalezalberquilla@arm.com * and we are talking about the past-the-end iterator. In that case, 29013482Srekai.gonzalezalberquilla@arm.com * the iterator round equals the cq round unless the head is at the 29113482Srekai.gonzalezalberquilla@arm.com * zero position and the round is one more than the cq round. 29213482Srekai.gonzalezalberquilla@arm.com */ 29313482Srekai.gonzalezalberquilla@arm.com bool 29413482Srekai.gonzalezalberquilla@arm.com decrementable() const 29513482Srekai.gonzalezalberquilla@arm.com { 29613482Srekai.gonzalezalberquilla@arm.com return _cq && !(_idx == _cq->head() && 29713482Srekai.gonzalezalberquilla@arm.com (_cq->empty() || 29813482Srekai.gonzalezalberquilla@arm.com (_idx == 0 && _round != _cq->_round + 1) || 29913482Srekai.gonzalezalberquilla@arm.com (_idx !=0 && _round != _cq->_round))); 30013482Srekai.gonzalezalberquilla@arm.com } 30113482Srekai.gonzalezalberquilla@arm.com 30213482Srekai.gonzalezalberquilla@arm.com public: 30313482Srekai.gonzalezalberquilla@arm.com /** Pre-decrement operator. */ 30413482Srekai.gonzalezalberquilla@arm.com iterator& operator--() 30513482Srekai.gonzalezalberquilla@arm.com { 30613482Srekai.gonzalezalberquilla@arm.com /* this has to be decrementable. */ 30713482Srekai.gonzalezalberquilla@arm.com assert(decrementable()); 30813482Srekai.gonzalezalberquilla@arm.com if (_idx == 0) 30913482Srekai.gonzalezalberquilla@arm.com --_round; 31013482Srekai.gonzalezalberquilla@arm.com _cq->decrease(_idx); 31113482Srekai.gonzalezalberquilla@arm.com return *this; 31213482Srekai.gonzalezalberquilla@arm.com } 31313482Srekai.gonzalezalberquilla@arm.com 31413482Srekai.gonzalezalberquilla@arm.com /** Post-decrement operator. */ 31513482Srekai.gonzalezalberquilla@arm.com iterator operator--(int ) { iterator t = *this; --*this; return t; } 31613482Srekai.gonzalezalberquilla@arm.com 31713482Srekai.gonzalezalberquilla@arm.com /** RandomAccessIterator requirements.*/ 31813482Srekai.gonzalezalberquilla@arm.com iterator& operator+=(const difference_type& t) 31913482Srekai.gonzalezalberquilla@arm.com { 32013482Srekai.gonzalezalberquilla@arm.com assert(_cq); 32113482Srekai.gonzalezalberquilla@arm.com _round += (t + _idx) / _cq->capacity(); 32213482Srekai.gonzalezalberquilla@arm.com _idx = _cq->moduloAdd(_idx, t); 32313482Srekai.gonzalezalberquilla@arm.com return *this; 32413482Srekai.gonzalezalberquilla@arm.com } 32513482Srekai.gonzalezalberquilla@arm.com 32613482Srekai.gonzalezalberquilla@arm.com iterator& operator-=(const difference_type& t) 32713482Srekai.gonzalezalberquilla@arm.com { 32813482Srekai.gonzalezalberquilla@arm.com assert(_cq); 32913482Srekai.gonzalezalberquilla@arm.com 33013482Srekai.gonzalezalberquilla@arm.com /* C does not do euclidean division, so we have to adjust */ 33113797Sgiacomo.travaglini@arm.com if (t >= 0) { 33213482Srekai.gonzalezalberquilla@arm.com _round += (-t + _idx) / _cq->capacity(); 33313797Sgiacomo.travaglini@arm.com _idx = _cq->moduloSub(_idx, t); 33413797Sgiacomo.travaglini@arm.com } else { 33513797Sgiacomo.travaglini@arm.com *this += -t; 33613797Sgiacomo.travaglini@arm.com } 33713482Srekai.gonzalezalberquilla@arm.com return *this; 33813482Srekai.gonzalezalberquilla@arm.com } 33913482Srekai.gonzalezalberquilla@arm.com 34013482Srekai.gonzalezalberquilla@arm.com /** Addition operator. */ 34113482Srekai.gonzalezalberquilla@arm.com iterator operator+(const difference_type& t) 34213482Srekai.gonzalezalberquilla@arm.com { 34313482Srekai.gonzalezalberquilla@arm.com iterator ret(*this); 34413482Srekai.gonzalezalberquilla@arm.com return ret += t; 34513482Srekai.gonzalezalberquilla@arm.com } 34613482Srekai.gonzalezalberquilla@arm.com 34713482Srekai.gonzalezalberquilla@arm.com friend iterator operator+(const difference_type& t, iterator& it) 34813482Srekai.gonzalezalberquilla@arm.com { 34913482Srekai.gonzalezalberquilla@arm.com iterator ret = it; 35013482Srekai.gonzalezalberquilla@arm.com return ret += t; 35113482Srekai.gonzalezalberquilla@arm.com } 35213482Srekai.gonzalezalberquilla@arm.com 35313482Srekai.gonzalezalberquilla@arm.com /** Substraction operator. */ 35413482Srekai.gonzalezalberquilla@arm.com iterator operator-(const difference_type& t) 35513482Srekai.gonzalezalberquilla@arm.com { 35613482Srekai.gonzalezalberquilla@arm.com iterator ret(*this); 35713482Srekai.gonzalezalberquilla@arm.com return ret -= t; 35813482Srekai.gonzalezalberquilla@arm.com } 35913482Srekai.gonzalezalberquilla@arm.com 36013482Srekai.gonzalezalberquilla@arm.com friend iterator operator-(const difference_type& t, iterator& it) 36113482Srekai.gonzalezalberquilla@arm.com { 36213482Srekai.gonzalezalberquilla@arm.com iterator ret = it; 36313482Srekai.gonzalezalberquilla@arm.com return ret -= t; 36413482Srekai.gonzalezalberquilla@arm.com } 36513482Srekai.gonzalezalberquilla@arm.com 36613482Srekai.gonzalezalberquilla@arm.com /** Difference operator. 36713482Srekai.gonzalezalberquilla@arm.com * that + ret == this 36813482Srekai.gonzalezalberquilla@arm.com */ 36913482Srekai.gonzalezalberquilla@arm.com difference_type operator-(const iterator& that) 37013482Srekai.gonzalezalberquilla@arm.com { 37113482Srekai.gonzalezalberquilla@arm.com /* If a is already at the end, we can safely return 0. */ 37213796Sgiacomo.travaglini@arm.com auto ret = _cq->sub(this->_idx, that._idx, _cq->capacity()); 37313482Srekai.gonzalezalberquilla@arm.com 37413796Sgiacomo.travaglini@arm.com if (this->_round != that._round) { 37513796Sgiacomo.travaglini@arm.com ret += ((this->_round - that._round) * _cq->capacity()); 37613482Srekai.gonzalezalberquilla@arm.com } 37713482Srekai.gonzalezalberquilla@arm.com return ret; 37813482Srekai.gonzalezalberquilla@arm.com } 37913482Srekai.gonzalezalberquilla@arm.com 38013482Srekai.gonzalezalberquilla@arm.com /** Index operator. 38113482Srekai.gonzalezalberquilla@arm.com * The use of * tests for dereferenceability. 38213482Srekai.gonzalezalberquilla@arm.com */ 38313482Srekai.gonzalezalberquilla@arm.com template<typename Idx> 38413482Srekai.gonzalezalberquilla@arm.com typename std::enable_if<std::is_integral<Idx>::value,reference>::type 38513482Srekai.gonzalezalberquilla@arm.com operator[](const Idx& index) { return *(*this + index); } 38613482Srekai.gonzalezalberquilla@arm.com 38713482Srekai.gonzalezalberquilla@arm.com /** Comparisons. */ 38813482Srekai.gonzalezalberquilla@arm.com bool 38913482Srekai.gonzalezalberquilla@arm.com operator<(const iterator& that) const 39013482Srekai.gonzalezalberquilla@arm.com { 39113482Srekai.gonzalezalberquilla@arm.com assert(_cq && that._cq == _cq); 39213482Srekai.gonzalezalberquilla@arm.com return (this->_round < that._round) || 39313482Srekai.gonzalezalberquilla@arm.com (this->_round == that._round && _idx < that._idx); 39413482Srekai.gonzalezalberquilla@arm.com } 39513482Srekai.gonzalezalberquilla@arm.com 39613482Srekai.gonzalezalberquilla@arm.com bool 39713482Srekai.gonzalezalberquilla@arm.com operator>(const iterator& that) const 39813482Srekai.gonzalezalberquilla@arm.com { return !(*this <= that); } 39913482Srekai.gonzalezalberquilla@arm.com 40013482Srekai.gonzalezalberquilla@arm.com bool operator>=(const iterator& that) const 40113482Srekai.gonzalezalberquilla@arm.com { return !(*this < that); } 40213482Srekai.gonzalezalberquilla@arm.com 40313482Srekai.gonzalezalberquilla@arm.com bool operator<=(const iterator& that) const 40413482Srekai.gonzalezalberquilla@arm.com { return !(that < *this); } 40513482Srekai.gonzalezalberquilla@arm.com 40613482Srekai.gonzalezalberquilla@arm.com /** OutputIterator has no extra requirements.*/ 40713482Srekai.gonzalezalberquilla@arm.com size_t idx() const { return _idx; } 40813482Srekai.gonzalezalberquilla@arm.com }; 40913482Srekai.gonzalezalberquilla@arm.com 41013482Srekai.gonzalezalberquilla@arm.com public: 41113487Sgiacomo.travaglini@arm.com using Base::operator[]; 41213482Srekai.gonzalezalberquilla@arm.com 41313482Srekai.gonzalezalberquilla@arm.com explicit CircularQueue(uint32_t size = 0) 41413482Srekai.gonzalezalberquilla@arm.com : _capacity(size), _head(1), _tail(0), _empty(true), _round(0) 41513482Srekai.gonzalezalberquilla@arm.com { 41613482Srekai.gonzalezalberquilla@arm.com Base::resize(size); 41713482Srekai.gonzalezalberquilla@arm.com } 41813482Srekai.gonzalezalberquilla@arm.com 41913482Srekai.gonzalezalberquilla@arm.com /** 42013482Srekai.gonzalezalberquilla@arm.com * Remove all the elements in the queue. 42113482Srekai.gonzalezalberquilla@arm.com * 42213482Srekai.gonzalezalberquilla@arm.com * Note: This does not actually remove elements from the backing 42313482Srekai.gonzalezalberquilla@arm.com * store. 42413482Srekai.gonzalezalberquilla@arm.com */ 42513482Srekai.gonzalezalberquilla@arm.com void flush() 42613482Srekai.gonzalezalberquilla@arm.com { 42713482Srekai.gonzalezalberquilla@arm.com _head = 1; 42813482Srekai.gonzalezalberquilla@arm.com _round = 0; 42913482Srekai.gonzalezalberquilla@arm.com _tail = 0; 43013482Srekai.gonzalezalberquilla@arm.com _empty = true; 43113482Srekai.gonzalezalberquilla@arm.com } 43213482Srekai.gonzalezalberquilla@arm.com 43313482Srekai.gonzalezalberquilla@arm.com /** Test if the index is in the range of valid elements. */ 43413482Srekai.gonzalezalberquilla@arm.com bool isValidIdx(size_t idx) const 43513482Srekai.gonzalezalberquilla@arm.com { 43613482Srekai.gonzalezalberquilla@arm.com /* An index is invalid if: 43713482Srekai.gonzalezalberquilla@arm.com * - The queue is empty. 43813482Srekai.gonzalezalberquilla@arm.com * (6,T,3,2): |-|-|-]|[-|-|x| 43913482Srekai.gonzalezalberquilla@arm.com * - head is small than tail and: 44013482Srekai.gonzalezalberquilla@arm.com * - It is greater than both head and tail. 44113482Srekai.gonzalezalberquilla@arm.com * (6,F,1,3): |-|[o|o|o]|-|x| 44213482Srekai.gonzalezalberquilla@arm.com * - It is less than both head and tail. 44313482Srekai.gonzalezalberquilla@arm.com * (6,F,1,3): |x|[o|o|o]|-|-| 44413482Srekai.gonzalezalberquilla@arm.com * - It is greater than the tail and not than the head. 44513482Srekai.gonzalezalberquilla@arm.com * (6,F,4,1): |o|o]|-|x|[o|o| 44613482Srekai.gonzalezalberquilla@arm.com */ 44713482Srekai.gonzalezalberquilla@arm.com return !(_empty || ( 44813482Srekai.gonzalezalberquilla@arm.com (_head < _tail) && ( 44913482Srekai.gonzalezalberquilla@arm.com (_head < idx && _tail < idx) || 45013482Srekai.gonzalezalberquilla@arm.com (_head > idx && _tail > idx) 45113482Srekai.gonzalezalberquilla@arm.com )) || (_tail < idx && idx < _head)); 45213482Srekai.gonzalezalberquilla@arm.com } 45313482Srekai.gonzalezalberquilla@arm.com 45413482Srekai.gonzalezalberquilla@arm.com /** Test if the index is in the range of valid elements. 45513482Srekai.gonzalezalberquilla@arm.com * The round counter is used to disambiguate aliasing. 45613482Srekai.gonzalezalberquilla@arm.com */ 45713482Srekai.gonzalezalberquilla@arm.com bool isValidIdx(size_t idx, uint32_t round) const 45813482Srekai.gonzalezalberquilla@arm.com { 45913482Srekai.gonzalezalberquilla@arm.com /* An index is valid if: 46013482Srekai.gonzalezalberquilla@arm.com * - The queue is not empty. 46113482Srekai.gonzalezalberquilla@arm.com * - round == R and 46213482Srekai.gonzalezalberquilla@arm.com * - index <= tail (if index > tail, that would be PTE) 46313482Srekai.gonzalezalberquilla@arm.com * - Either: 46413482Srekai.gonzalezalberquilla@arm.com * - head <= index 46513482Srekai.gonzalezalberquilla@arm.com * (6,F,1,3,R): |-|[o|(*,r)|o]|-|-| 46613482Srekai.gonzalezalberquilla@arm.com * - head > tail 46713482Srekai.gonzalezalberquilla@arm.com * (6,F,5,3,R): |o|o|(*,r)|o]|-|[o| 46813482Srekai.gonzalezalberquilla@arm.com * The remaining case means the the iterator is BTB: 46913482Srekai.gonzalezalberquilla@arm.com * (6,F,3,4,R): |-|-|(x,r)|[o|o]|-| 47013482Srekai.gonzalezalberquilla@arm.com * - round + 1 == R and: 47113482Srekai.gonzalezalberquilla@arm.com * - index > tail. If index <= tail, that would be BTB: 47213482Srekai.gonzalezalberquilla@arm.com * (6,F,2,3,r): | -|- |[(*,r)|o]|-|-| 47313482Srekai.gonzalezalberquilla@arm.com * (6,F,0,1,r+1): |[o|o]| (x,r)|- |-|-| 47413482Srekai.gonzalezalberquilla@arm.com * (6,F,0,3,r+1): |[o|o | (*,r)|o]|-|-| 47513482Srekai.gonzalezalberquilla@arm.com * - index >= head. If index < head, that would be BTB: 47613482Srekai.gonzalezalberquilla@arm.com * (6,F,5,2,R): |o|o]|-|-|(x,r)|[o| 47713482Srekai.gonzalezalberquilla@arm.com * - head > tail. If head <= tail, that would be BTB: 47813482Srekai.gonzalezalberquilla@arm.com * (6,F,3,4,R): |[o|o]|(x,r)|-|-|-| 47913482Srekai.gonzalezalberquilla@arm.com * Other values of the round meand that the index is PTE or BTB 48013482Srekai.gonzalezalberquilla@arm.com */ 48113482Srekai.gonzalezalberquilla@arm.com return (!_empty && ( 48213482Srekai.gonzalezalberquilla@arm.com (round == _round && idx <= _tail && ( 48313482Srekai.gonzalezalberquilla@arm.com _head <= idx || _head > _tail)) || 48413482Srekai.gonzalezalberquilla@arm.com (round + 1 == _round && 48513482Srekai.gonzalezalberquilla@arm.com idx > _tail && 48613482Srekai.gonzalezalberquilla@arm.com idx >= _head && 48713482Srekai.gonzalezalberquilla@arm.com _head > _tail) 48813482Srekai.gonzalezalberquilla@arm.com )); 48913482Srekai.gonzalezalberquilla@arm.com } 49013482Srekai.gonzalezalberquilla@arm.com 49113482Srekai.gonzalezalberquilla@arm.com reference front() { return (*this)[_head]; } 49213482Srekai.gonzalezalberquilla@arm.com reference back() { return (*this)[_tail]; } 49313482Srekai.gonzalezalberquilla@arm.com uint32_t head() const { return _head; } 49413482Srekai.gonzalezalberquilla@arm.com uint32_t tail() const { return _tail; } 49513482Srekai.gonzalezalberquilla@arm.com size_t capacity() const { return _capacity; } 49613482Srekai.gonzalezalberquilla@arm.com 49713482Srekai.gonzalezalberquilla@arm.com uint32_t size() const 49813482Srekai.gonzalezalberquilla@arm.com { 49913482Srekai.gonzalezalberquilla@arm.com if (_empty) 50013482Srekai.gonzalezalberquilla@arm.com return 0; 50113482Srekai.gonzalezalberquilla@arm.com else if (_head <= _tail) 50213482Srekai.gonzalezalberquilla@arm.com return _tail - _head + 1; 50313482Srekai.gonzalezalberquilla@arm.com else 50413482Srekai.gonzalezalberquilla@arm.com return _capacity - _head + _tail + 1; 50513482Srekai.gonzalezalberquilla@arm.com } 50613482Srekai.gonzalezalberquilla@arm.com 50713482Srekai.gonzalezalberquilla@arm.com uint32_t moduloAdd(uint32_t s1, uint32_t s2) const 50813482Srekai.gonzalezalberquilla@arm.com { 50913482Srekai.gonzalezalberquilla@arm.com return moduloAdd(s1, s2, _capacity); 51013482Srekai.gonzalezalberquilla@arm.com } 51113482Srekai.gonzalezalberquilla@arm.com 51213482Srekai.gonzalezalberquilla@arm.com uint32_t moduloSub(uint32_t s1, uint32_t s2) const 51313482Srekai.gonzalezalberquilla@arm.com { 51413482Srekai.gonzalezalberquilla@arm.com return moduloSub(s1, s2, _capacity); 51513482Srekai.gonzalezalberquilla@arm.com } 51613482Srekai.gonzalezalberquilla@arm.com 51713482Srekai.gonzalezalberquilla@arm.com /** Circularly increase the head pointer. 51813482Srekai.gonzalezalberquilla@arm.com * By increasing the head pointer we are removing elements from 51913482Srekai.gonzalezalberquilla@arm.com * the begin of the circular queue. 52013482Srekai.gonzalezalberquilla@arm.com * Check that the queue is not empty. And set it to empty if it 52113482Srekai.gonzalezalberquilla@arm.com * had only one value prior to insertion. 52213482Srekai.gonzalezalberquilla@arm.com * 52313482Srekai.gonzalezalberquilla@arm.com * @params num_elem number of elements to remove 52413482Srekai.gonzalezalberquilla@arm.com */ 52513482Srekai.gonzalezalberquilla@arm.com void pop_front(size_t num_elem = 1) 52613482Srekai.gonzalezalberquilla@arm.com { 52713482Srekai.gonzalezalberquilla@arm.com if (num_elem == 0) return; 52813482Srekai.gonzalezalberquilla@arm.com auto hIt = begin(); 52913482Srekai.gonzalezalberquilla@arm.com hIt += num_elem; 53013482Srekai.gonzalezalberquilla@arm.com assert(hIt <= end()); 53113482Srekai.gonzalezalberquilla@arm.com _empty = hIt == end(); 53213482Srekai.gonzalezalberquilla@arm.com _head = hIt._idx; 53313482Srekai.gonzalezalberquilla@arm.com } 53413482Srekai.gonzalezalberquilla@arm.com 53513482Srekai.gonzalezalberquilla@arm.com /** Circularly decrease the tail pointer. */ 53613482Srekai.gonzalezalberquilla@arm.com void pop_back() 53713482Srekai.gonzalezalberquilla@arm.com { 53813482Srekai.gonzalezalberquilla@arm.com assert (!_empty); 53913482Srekai.gonzalezalberquilla@arm.com _empty = _head == _tail; 54013482Srekai.gonzalezalberquilla@arm.com if (_tail == 0) 54113482Srekai.gonzalezalberquilla@arm.com --_round; 54213482Srekai.gonzalezalberquilla@arm.com decrease(_tail); 54313482Srekai.gonzalezalberquilla@arm.com } 54413482Srekai.gonzalezalberquilla@arm.com 54513482Srekai.gonzalezalberquilla@arm.com /** Pushes an element at the end of the queue. */ 54613482Srekai.gonzalezalberquilla@arm.com void push_back(typename Base::value_type val) 54713482Srekai.gonzalezalberquilla@arm.com { 54813482Srekai.gonzalezalberquilla@arm.com advance_tail(); 54913482Srekai.gonzalezalberquilla@arm.com (*this)[_tail] = val; 55013482Srekai.gonzalezalberquilla@arm.com } 55113482Srekai.gonzalezalberquilla@arm.com 55213482Srekai.gonzalezalberquilla@arm.com /** Increases the tail by one. 55313482Srekai.gonzalezalberquilla@arm.com * Check for wrap-arounds to update the round counter. 55413482Srekai.gonzalezalberquilla@arm.com */ 55513482Srekai.gonzalezalberquilla@arm.com void advance_tail() 55613482Srekai.gonzalezalberquilla@arm.com { 55713482Srekai.gonzalezalberquilla@arm.com increase(_tail); 55813482Srekai.gonzalezalberquilla@arm.com if (_tail == 0) 55913482Srekai.gonzalezalberquilla@arm.com ++_round; 56013482Srekai.gonzalezalberquilla@arm.com 56113482Srekai.gonzalezalberquilla@arm.com if (_tail == _head && !_empty) 56213482Srekai.gonzalezalberquilla@arm.com increase(_head); 56313482Srekai.gonzalezalberquilla@arm.com 56413482Srekai.gonzalezalberquilla@arm.com _empty = false; 56513482Srekai.gonzalezalberquilla@arm.com } 56613482Srekai.gonzalezalberquilla@arm.com 56713482Srekai.gonzalezalberquilla@arm.com /** Increases the tail by a specified number of steps 56813482Srekai.gonzalezalberquilla@arm.com * 56913482Srekai.gonzalezalberquilla@arm.com * @param len Number of steps 57013482Srekai.gonzalezalberquilla@arm.com */ 57113482Srekai.gonzalezalberquilla@arm.com void advance_tail(uint32_t len) 57213482Srekai.gonzalezalberquilla@arm.com { 57313482Srekai.gonzalezalberquilla@arm.com for (auto idx = 0; idx < len; idx++) 57413482Srekai.gonzalezalberquilla@arm.com advance_tail(); 57513482Srekai.gonzalezalberquilla@arm.com } 57613482Srekai.gonzalezalberquilla@arm.com 57713482Srekai.gonzalezalberquilla@arm.com /** Is the queue empty? */ 57813482Srekai.gonzalezalberquilla@arm.com bool empty() const { return _empty; } 57913482Srekai.gonzalezalberquilla@arm.com 58013482Srekai.gonzalezalberquilla@arm.com /** Is the queue full? 58113482Srekai.gonzalezalberquilla@arm.com * A queue is full if the head is the 0^{th} element and the tail is 58213482Srekai.gonzalezalberquilla@arm.com * the (size-1)^{th} element, or if the head is the n^{th} element and 58313482Srekai.gonzalezalberquilla@arm.com * the tail the (n-1)^{th} element. 58413482Srekai.gonzalezalberquilla@arm.com */ 58513482Srekai.gonzalezalberquilla@arm.com bool full() const 58613482Srekai.gonzalezalberquilla@arm.com { 58713482Srekai.gonzalezalberquilla@arm.com return !_empty && 58813482Srekai.gonzalezalberquilla@arm.com (_tail + 1 == _head || (_tail + 1 == _capacity && _head == 0)); 58913482Srekai.gonzalezalberquilla@arm.com } 59013482Srekai.gonzalezalberquilla@arm.com 59113482Srekai.gonzalezalberquilla@arm.com /** Iterators. */ 59213482Srekai.gonzalezalberquilla@arm.com iterator begin() 59313482Srekai.gonzalezalberquilla@arm.com { 59413482Srekai.gonzalezalberquilla@arm.com if (_empty) 59513482Srekai.gonzalezalberquilla@arm.com return end(); 59613482Srekai.gonzalezalberquilla@arm.com else if (_head > _tail) 59713482Srekai.gonzalezalberquilla@arm.com return iterator(this, _head, _round - 1); 59813482Srekai.gonzalezalberquilla@arm.com else 59913482Srekai.gonzalezalberquilla@arm.com return iterator(this, _head, _round); 60013482Srekai.gonzalezalberquilla@arm.com } 60113482Srekai.gonzalezalberquilla@arm.com 60213482Srekai.gonzalezalberquilla@arm.com /* TODO: This should return a const_iterator. */ 60313482Srekai.gonzalezalberquilla@arm.com iterator begin() const 60413482Srekai.gonzalezalberquilla@arm.com { 60513482Srekai.gonzalezalberquilla@arm.com if (_empty) 60613482Srekai.gonzalezalberquilla@arm.com return end(); 60713482Srekai.gonzalezalberquilla@arm.com else if (_head > _tail) 60813482Srekai.gonzalezalberquilla@arm.com return iterator(const_cast<CircularQueue*>(this), _head, 60913482Srekai.gonzalezalberquilla@arm.com _round - 1); 61013482Srekai.gonzalezalberquilla@arm.com else 61113482Srekai.gonzalezalberquilla@arm.com return iterator(const_cast<CircularQueue*>(this), _head, 61213482Srekai.gonzalezalberquilla@arm.com _round); 61313482Srekai.gonzalezalberquilla@arm.com } 61413482Srekai.gonzalezalberquilla@arm.com 61513482Srekai.gonzalezalberquilla@arm.com iterator end() 61613482Srekai.gonzalezalberquilla@arm.com { 61713482Srekai.gonzalezalberquilla@arm.com auto poi = moduloAdd(_tail, 1); 61813482Srekai.gonzalezalberquilla@arm.com auto round = _round; 61913482Srekai.gonzalezalberquilla@arm.com if (poi == 0) 62013482Srekai.gonzalezalberquilla@arm.com ++round; 62113482Srekai.gonzalezalberquilla@arm.com return iterator(this, poi, round); 62213482Srekai.gonzalezalberquilla@arm.com } 62313482Srekai.gonzalezalberquilla@arm.com 62413482Srekai.gonzalezalberquilla@arm.com iterator end() const 62513482Srekai.gonzalezalberquilla@arm.com { 62613482Srekai.gonzalezalberquilla@arm.com auto poi = moduloAdd(_tail, 1); 62713482Srekai.gonzalezalberquilla@arm.com auto round = _round; 62813482Srekai.gonzalezalberquilla@arm.com if (poi == 0) 62913482Srekai.gonzalezalberquilla@arm.com ++round; 63013482Srekai.gonzalezalberquilla@arm.com return iterator(const_cast<CircularQueue*>(this), poi, round); 63113482Srekai.gonzalezalberquilla@arm.com } 63213482Srekai.gonzalezalberquilla@arm.com 63313482Srekai.gonzalezalberquilla@arm.com /** Return an iterator to an index in the vector. 63413482Srekai.gonzalezalberquilla@arm.com * This poses the problem of round determination. By convention, the round 63513482Srekai.gonzalezalberquilla@arm.com * is picked so that isValidIndex(idx, round) is true. If that is not 63613482Srekai.gonzalezalberquilla@arm.com * possible, then the round value is _round, unless _tail is at the end of 63713482Srekai.gonzalezalberquilla@arm.com * the storage, in which case the PTE wraps up and becomes _round + 1 63813482Srekai.gonzalezalberquilla@arm.com */ 63913482Srekai.gonzalezalberquilla@arm.com iterator getIterator(size_t idx) 64013482Srekai.gonzalezalberquilla@arm.com { 64113482Srekai.gonzalezalberquilla@arm.com assert(isValidIdx(idx) || moduloAdd(_tail, 1) == idx); 64213482Srekai.gonzalezalberquilla@arm.com if (_empty) 64313482Srekai.gonzalezalberquilla@arm.com return end(); 64413482Srekai.gonzalezalberquilla@arm.com 64513482Srekai.gonzalezalberquilla@arm.com uint32_t round = _round; 64613482Srekai.gonzalezalberquilla@arm.com if (idx > _tail) { 64713482Srekai.gonzalezalberquilla@arm.com if (idx >= _head && _head > _tail) { 64813482Srekai.gonzalezalberquilla@arm.com round -= 1; 64913482Srekai.gonzalezalberquilla@arm.com } 65013482Srekai.gonzalezalberquilla@arm.com } else if (idx < _head && _tail + 1 == _capacity) { 65113482Srekai.gonzalezalberquilla@arm.com round += 1; 65213482Srekai.gonzalezalberquilla@arm.com } 65313482Srekai.gonzalezalberquilla@arm.com return iterator(this, idx, round); 65413482Srekai.gonzalezalberquilla@arm.com } 65513482Srekai.gonzalezalberquilla@arm.com}; 65613482Srekai.gonzalezalberquilla@arm.com 65713482Srekai.gonzalezalberquilla@arm.com#endif /* __BASE_CIRCULARQUEUE_HH__ */ 658