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