circular_queue.hh revision 13487:ed055875261d
16899SN/A/* 26899SN/A * Copyright (c) 2017-2018 ARM Limited 36899SN/A * All rights reserved 46899SN/A * 56899SN/A * The license below extends only to copyright in the software and shall 66899SN/A * not be construed as granting a license to any other intellectual 76899SN/A * property including but not limited to intellectual property relating 86899SN/A * to a hardware implementation of the functionality of the software 96899SN/A * licensed hereunder. You may use the software subject to the license 106899SN/A * terms below provided that you ensure that this notice is replicated 116899SN/A * unmodified and in its entirety in all distributions of the software, 126899SN/A * modified or unmodified, in source code or in binary form. 136899SN/A * 146899SN/A * Redistribution and use in source and binary forms, with or without 156899SN/A * modification, are permitted provided that the following conditions are 166899SN/A * met: redistributions of source code must retain the above copyright 176899SN/A * notice, this list of conditions and the following disclaimer; 186899SN/A * redistributions in binary form must reproduce the above copyright 196899SN/A * notice, this list of conditions and the following disclaimer in the 206899SN/A * documentation and/or other materials provided with the distribution; 216899SN/A * neither the name of the copyright holders nor the names of its 226899SN/A * contributors may be used to endorse or promote products derived from 236899SN/A * this software without specific prior written permission. 246899SN/A * 256899SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 266899SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 276899SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 286899SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 296899SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3010348Sandreas.hansson@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 317632SBrad.Beckmann@amd.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 328232Snate@binkert.org * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 337053SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 346899SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 357053SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 367053SN/A * 3711025Snilay@cs.wisc.edu * Authors: Rekai Gonzalez-Alberquilla 3811025Snilay@cs.wisc.edu */ 398932SBrad.Beckmann@amd.com 408932SBrad.Beckmann@amd.com#ifndef __BASE_CIRCULAR_QUEUE_HH__ 416899SN/A#define __BASE_CIRCULAR_QUEUE_HH__ 427053SN/A 436899SN/A#include <vector> 447053SN/A 457053SN/A/** Circular queue. 467053SN/A * Circular queue implemented on top of a standard vector. Instead of using 477053SN/A * a sentinel entry, we use a boolean to distinguish the case in which the 4810348Sandreas.hansson@arm.com * queue is full or empty. 4910348Sandreas.hansson@arm.com * Thus, a circular queue is represented by the 5-tuple 507053SN/A * (Capacity, IsEmpty?, Head, Tail, Round) 516899SN/A * Where: 526899SN/A * - Capacity is the size of the underlying vector. 537053SN/A * - IsEmpty? can be T or F. 547053SN/A * - Head is the index in the vector of the first element of the queue. 556899SN/A * - Tail is the index in the vector of the last element of the queue. 567053SN/A * - Round is the counter of how many times the Tail has wrapped around. 577053SN/A * A queue is empty when 586899SN/A * Head == (Tail + 1 mod Capacity) && IsEmpty?. 597053SN/A * Conversely, a queue if full when 6010348Sandreas.hansson@arm.com * Head == (Tail + 1 mod Capacity) && !IsEmpty?. 617053SN/A * Comments may show depictions of the underlying vector in the following 627053SN/A * format: '|' delimit the 'cells' of the underlying vector. '-' represents 636899SN/A * an element of the vector that is out-of-bounds of the circular queue, 6410348Sandreas.hansson@arm.com * while 'o' represents and element that is inside the bounds. The 658184Ssomayeh@cs.wisc.edu * characters '[' and ']' are added to mark the entries that hold the head 668184Ssomayeh@cs.wisc.edu * and tail of the circular queue respectively. 678184Ssomayeh@cs.wisc.edu * E.g.: 687053SN/A * - Empty queues of capacity 4: 697053SN/A * (4,T,1,0,_): |-]|[-|-|-| (4,T,3,2): |-|-|-]|[-| 707053SN/A * - Full queues of capacity 4: 717053SN/A * (4,F,1,0,_): |o]|[o|o|o| (4,F,3,2): |o|o|o]|[o| 727053SN/A * - Queues of capacity 4 with 2 elements: 737053SN/A * (4,F,0,1,_): |[o|o]|-|-| (4,F,3,0): |o]|-|-|[o| 747053SN/A * 757053SN/A * The Round number is only relevant for checking validity of indices, 767053SN/A * therefore it will be omitted or shown as '_' 776899SN/A */ 786899SN/Atemplate <typename T> 797053SN/Aclass CircularQueue : private std::vector<T> 807053SN/A{ 816899SN/A protected: 827053SN/A using Base = std::vector<T>; 836899SN/A using typename Base::reference; 8410348Sandreas.hansson@arm.com using typename Base::const_reference; 858950Sandreas.hansson@arm.com const uint32_t _capacity; 866899SN/A uint32_t _head; 877053SN/A uint32_t _tail; 887053SN/A uint32_t _empty; 896899SN/A 907053SN/A /** Counter for how many times the tail wraps around. 916899SN/A * Some parts of the code rely on getting the past the end iterator, and 927053SN/A * expect to use it after inserting on the tail. To support this without 9310348Sandreas.hansson@arm.com * ambiguity, we need the round number to guarantee that it did not become 947053SN/A * a before-the-beginning iterator. 957053SN/A */ 968932SBrad.Beckmann@amd.com uint32_t _round; 9711266SBrad.Beckmann@amd.com 9811266SBrad.Beckmann@amd.com /** General modular addition. */ 9911266SBrad.Beckmann@amd.com static uint32_t 1007053SN/A moduloAdd(uint32_t op1, uint32_t op2, uint32_t size) 1017053SN/A { 1027053SN/A return (op1 + op2) % size; 1037053SN/A } 1047053SN/A 1056899SN/A /** General modular subtraction. */ 1066899SN/A static uint32_t 1077568SN/A moduloSub(uint32_t op1, uint32_t op2, uint32_t size) 10811025Snilay@cs.wisc.edu { 10911025Snilay@cs.wisc.edu int ret = (uint32_t)(op1 - op2) % size; 1108190SLisa.Hsu@amd.com return ret >= 0 ? ret : ret + size; 1117568SN/A } 1128949Sandreas.hansson@arm.com 11310562Sandreas.hansson@arm.com void increase(uint32_t& v, size_t delta = 1) 11410562Sandreas.hansson@arm.com { 11510562Sandreas.hansson@arm.com v = moduloAdd(v, delta, _capacity); 11610566Sandreas.hansson@arm.com } 11710562Sandreas.hansson@arm.com 1186899SN/A void decrease(uint32_t& v) 1197053SN/A { 1207053SN/A v = (v ? v : _capacity) - 1; 1219542Sandreas.hansson@arm.com } 1226899SN/A 1238975Sandreas.hansson@arm.com /** Iterator to the circular queue. 1247053SN/A * iterator implementation to provide the circular-ness that the 1257053SN/A * standard std::vector<T>::iterator does not implement. 1267053SN/A * Iterators to a queue are represented by a pair of a character and the 1279542Sandreas.hansson@arm.com * round counter. For the character, '*' denotes the element pointed to by 1287053SN/A * the iterator if it is valid. 'x' denotes the element pointed to by the 1297053SN/A * iterator when it is BTB or PTE. 1306899SN/A * E.g.: 1317053SN/A * - Iterator to the head of a queue of capacity 4 with 2 elems. 1327053SN/A * (4,F,0,1,R): |[(*,R)|o]|-|-| (4,F,3,0): |o]|-|-|[(*,R)| 1337053SN/A * - Iterator to the tail of a queue of capacity 4 with 2 elems. 1346899SN/A * (4,F,0,1,R): |[o|(*,R)]|-|-| (4,F,3,0): |(*,R)]|-|-|[o| 1356899SN/A * - Iterator to the end of a queue of capacity 4 with 2 elems. 1367053SN/A * (4,F,0,1,R): |[o|o]|(x,R)|-| (4,F,3,0): |o]|(x,R)|-|[o| 1378184Ssomayeh@cs.wisc.edu */ 1388184Ssomayeh@cs.wisc.edu public: 1398184Ssomayeh@cs.wisc.edu struct iterator { 1408184Ssomayeh@cs.wisc.edu CircularQueue* _cq; 1418184Ssomayeh@cs.wisc.edu uint32_t _idx; 14210348Sandreas.hansson@arm.com uint32_t _round; 1438950Sandreas.hansson@arm.com 1448184Ssomayeh@cs.wisc.edu public: 1458184Ssomayeh@cs.wisc.edu iterator(CircularQueue* cq, uint32_t idx, uint32_t round) 1468184Ssomayeh@cs.wisc.edu : _cq(cq), _idx(idx), _round(round) {} 14711025Snilay@cs.wisc.edu 14811025Snilay@cs.wisc.edu /** Iterator Traits */ 1498184Ssomayeh@cs.wisc.edu using value_type = T; 1508184Ssomayeh@cs.wisc.edu using difference_type = std::ptrdiff_t; 1518184Ssomayeh@cs.wisc.edu using reference = value_type&; 1528184Ssomayeh@cs.wisc.edu using const_reference = const value_type&; 1538184Ssomayeh@cs.wisc.edu using pointer = value_type*; 1548949Sandreas.hansson@arm.com using const_pointer = const value_type*; 1558184Ssomayeh@cs.wisc.edu using iterator_category = std::random_access_iterator_tag; 1568184Ssomayeh@cs.wisc.edu 1578184Ssomayeh@cs.wisc.edu /** Trait reference type 1589542Sandreas.hansson@arm.com * iterator satisfies OutputIterator, therefore reference 1598184Ssomayeh@cs.wisc.edu * must be T& */ 1608975Sandreas.hansson@arm.com static_assert(std::is_same<reference, T&>::value, 1618184Ssomayeh@cs.wisc.edu "reference type is not assignable as required"); 1628184Ssomayeh@cs.wisc.edu 1638184Ssomayeh@cs.wisc.edu iterator() : _cq(nullptr), _idx(0), _round(0) { } 1648184Ssomayeh@cs.wisc.edu 1658184Ssomayeh@cs.wisc.edu iterator(const iterator& it) 1667053SN/A : _cq(it._cq), _idx(it._idx), _round(it._round) {} 1676899SN/A 1687053SN/A iterator& 1697053SN/A operator=(const iterator& it) 1706899SN/A { 17110348Sandreas.hansson@arm.com _cq = it._cq; 1728950Sandreas.hansson@arm.com _idx = it._idx; 1736899SN/A _round = it._round; 1747053SN/A return *this; 1756899SN/A } 1767053SN/A 17711025Snilay@cs.wisc.edu ~iterator() { _cq = nullptr; _idx = 0; _round = 0; } 1786899SN/A 1797053SN/A /** Test dereferenceability. 18011025Snilay@cs.wisc.edu * An iterator is dereferenceable if it is pointing to a non-null 18111025Snilay@cs.wisc.edu * circular queue, it is not the past-the-end iterator and the 1826899SN/A * index is a valid index to that queue. PTE test is required to 1838190SLisa.Hsu@amd.com * distinguish between: 1847053SN/A * - An iterator to the first element of a full queue 1857053SN/A * (4,F,1,0): |o]|[*|o|o| 1867053SN/A * - The end() iterator of a full queue 1877053SN/A * (4,F,1,0): |o]|x[o|o|o| 1887053SN/A * Sometimes, though, users will get the PTE iterator and expect it 1897053SN/A * to work after growing the buffer on the tail, so we have to 1906899SN/A * check if the iterator is still PTE. 1917053SN/A */ 1926899SN/A bool 1938949Sandreas.hansson@arm.com dereferenceable() const 19410566Sandreas.hansson@arm.com { 1957053SN/A return _cq != nullptr && _cq->isValidIdx(_idx, _round); 1967053SN/A } 1976899SN/A 19811266SBrad.Beckmann@amd.com /** InputIterator. */ 19910563Sandreas.hansson@arm.com 2006899SN/A /** Equality operator. 2017053SN/A * Two iterators must point to the same, possibly null, circular 2027053SN/A * queue and the same element on it, including PTE, to be equal. 2039542Sandreas.hansson@arm.com * In case the clients the the PTE iterator and then grow on the back 2046899SN/A * and expect it to work, we have to check if the PTE is still PTE 2058975Sandreas.hansson@arm.com */ 2067053SN/A bool operator==(const iterator& that) const 2077053SN/A { 2087053SN/A return _cq == that._cq && _idx == that._idx && 2097053SN/A _round == that._round; 21011266SBrad.Beckmann@amd.com } 2117053SN/A 2127053SN/A /** Inequality operator. 2137053SN/A * Conversely, two iterators are different if they both point to 2147053SN/A * different circular queues or they point to different elements. 2159542Sandreas.hansson@arm.com */ 2167053SN/A bool operator!=(const iterator& that) 2177053SN/A { 2187053SN/A return !(*this == that); 2197053SN/A } 2207053SN/A 2217053SN/A /** Dereference operator. */ 2227053SN/A reference operator*() 2236899SN/A { 2246899SN/A /* this has to be dereferenceable. */ 2256899SN/A return (*_cq)[_idx]; 2267053SN/A } 2277053SN/A 2286899SN/A const_reference operator*() const 2297053SN/A { 2307053SN/A /* this has to be dereferenceable. */ 2316899SN/A return (*_cq)[_idx]; 23210348Sandreas.hansson@arm.com } 2338950Sandreas.hansson@arm.com 2346899SN/A /** Dereference operator. 2357053SN/A * Rely on operator* to check for dereferenceability. 2366899SN/A */ 2378932SBrad.Beckmann@amd.com pointer operator->() 23811266SBrad.Beckmann@amd.com { 23911266SBrad.Beckmann@amd.com return &((*_cq)[_idx]); 24011266SBrad.Beckmann@amd.com } 2417053SN/A 2427053SN/A const_pointer operator->() const 2436899SN/A { 2447568SN/A return &((*_cq)[_idx]); 24511025Snilay@cs.wisc.edu } 24611025Snilay@cs.wisc.edu 2477568SN/A /** Pre-increment operator. */ 2488190SLisa.Hsu@amd.com iterator& operator++() 2498949Sandreas.hansson@arm.com { 2509208Snilay@cs.wisc.edu /* this has to be dereferenceable. */ 25110566Sandreas.hansson@arm.com _cq->increase(_idx); 2526899SN/A if (_idx == 0) 25311266SBrad.Beckmann@amd.com ++_round; 25411266SBrad.Beckmann@amd.com return *this; 2557053SN/A } 2567053SN/A 2579542Sandreas.hansson@arm.com /** Post-increment operator. */ 2586899SN/A iterator 2598975Sandreas.hansson@arm.com operator++(int) 2607053SN/A { 2617053SN/A iterator t = *this; 2627053SN/A ++*this; 2637053SN/A return t; 26411266SBrad.Beckmann@amd.com } 2657053SN/A 2667053SN/A /** ForwardIterator 2677053SN/A * The multipass guarantee is provided by the reliance on _idx. 2687053SN/A */ 2699542Sandreas.hansson@arm.com 2707053SN/A /** BidirectionalIterator requirements. */ 2717053SN/A private: 2726899SN/A /** Test decrementability. 2737053SN/A * An iterator to a non-null circular queue is not-decrementable 2747053SN/A * if it is pointing to the head element, unless the queue is full 2757053SN/A * and we are talking about the past-the-end iterator. In that case, 2767053SN/A * the iterator round equals the cq round unless the head is at the 2777053SN/A * zero position and the round is one more than the cq round. 2786899SN/A */ 2796899SN/A bool 2807053SN/A decrementable() const 28110302Snilay@cs.wisc.edu { 2826899SN/A return _cq && !(_idx == _cq->head() && 28311025Snilay@cs.wisc.edu (_cq->empty() || 2846899SN/A (_idx == 0 && _round != _cq->_round + 1) || 2857053SN/A (_idx !=0 && _round != _cq->_round))); 2867053SN/A } 2876899SN/A 28811025Snilay@cs.wisc.edu public: 2897053SN/A /** Pre-decrement operator. */ 2907053SN/A iterator& operator--() 2917053SN/A { 2926899SN/A /* this has to be decrementable. */ 2936899SN/A assert(decrementable()); 2947053SN/A if (_idx == 0) 2957053SN/A --_round; 2967053SN/A _cq->decrease(_idx); 2977053SN/A return *this; 2987053SN/A } 2997053SN/A 3007053SN/A /** Post-decrement operator. */ 3017053SN/A iterator operator--(int ) { iterator t = *this; --*this; return t; } 30211266SBrad.Beckmann@amd.com 3037053SN/A /** RandomAccessIterator requirements.*/ 3047053SN/A iterator& operator+=(const difference_type& t) 30511266SBrad.Beckmann@amd.com { 30611266SBrad.Beckmann@amd.com assert(_cq); 3077053SN/A _round += (t + _idx) / _cq->capacity(); 3087053SN/A _idx = _cq->moduloAdd(_idx, t); 3097053SN/A return *this; 3107053SN/A } 3117053SN/A 3127053SN/A iterator& operator-=(const difference_type& t) 3137053SN/A { 3149208Snilay@cs.wisc.edu assert(_cq); 3157805Snilay@cs.wisc.edu 3167805Snilay@cs.wisc.edu /* C does not do euclidean division, so we have to adjust */ 3177805Snilay@cs.wisc.edu if (t >= 0) 3187805Snilay@cs.wisc.edu _round += (-t + _idx) / _cq->capacity(); 3197805Snilay@cs.wisc.edu else 3209475Snilay@cs.wisc.edu _round += (-t + _idx - _cq->capacity() + 1) / _cq->capacity(); 3217053SN/A 3227053SN/A _idx = _cq->moduloSub(_idx, t); 3237053SN/A return *this; 3247053SN/A } 3256899SN/A 3267053SN/A /** Addition operator. */ 3277053SN/A iterator operator+(const difference_type& t) 3286899SN/A { 3297053SN/A iterator ret(*this); 33011266SBrad.Beckmann@amd.com return ret += t; 3317053SN/A } 3327053SN/A 3337053SN/A friend iterator operator+(const difference_type& t, iterator& it) 3347805Snilay@cs.wisc.edu { 3359475Snilay@cs.wisc.edu iterator ret = it; 3367053SN/A return ret += t; 3377053SN/A } 3387053SN/A 33911025Snilay@cs.wisc.edu /** Substraction operator. */ 3407053SN/A iterator operator-(const difference_type& t) 3417053SN/A { 3426899SN/A iterator ret(*this); 3436899SN/A return ret -= t; 3447053SN/A } 34511025Snilay@cs.wisc.edu 3466899SN/A friend iterator operator-(const difference_type& t, iterator& it) 3477053SN/A { 3487053SN/A iterator ret = it; 3497053SN/A return ret -= t; 35011266SBrad.Beckmann@amd.com } 3517053SN/A 3526899SN/A /** Difference operator. 3536899SN/A * that + ret == this 3547053SN/A */ 3557053SN/A difference_type operator-(const iterator& that) 3566899SN/A { 3577053SN/A /* If a is already at the end, we can safely return 0. */ 35810348Sandreas.hansson@arm.com auto ret = _cq->moduloSub(this->_idx, that._idx); 3597053SN/A 3606899SN/A if (ret == 0 && this->_round != that._round) { 3616899SN/A ret += this->_round * _cq->capacity(); 3627053SN/A } 3637053SN/A return ret; 3646899SN/A } 3657053SN/A 3667053SN/A /** Index operator. 36710348Sandreas.hansson@arm.com * The use of * tests for dereferenceability. 36811266SBrad.Beckmann@amd.com */ 36911266SBrad.Beckmann@amd.com template<typename Idx> 3707053SN/A typename std::enable_if<std::is_integral<Idx>::value,reference>::type 3716899SN/A operator[](const Idx& index) { return *(*this + index); } 3726899SN/A 3737053SN/A /** Comparisons. */ 3747055SN/A bool 3756899SN/A operator<(const iterator& that) const 3767053SN/A { 3777053SN/A assert(_cq && that._cq == _cq); 3787053SN/A return (this->_round < that._round) || 3797053SN/A (this->_round == that._round && _idx < that._idx); 3807053SN/A } 3817053SN/A 3827055SN/A bool 3836899SN/A operator>(const iterator& that) const 3846899SN/A { return !(*this <= that); } 3857053SN/A 3867053SN/A bool operator>=(const iterator& that) const 3876899SN/A { return !(*this < that); } 3887053SN/A 3897053SN/A bool operator<=(const iterator& that) const 39011025Snilay@cs.wisc.edu { return !(that < *this); } 3917053SN/A 3926899SN/A /** OutputIterator has no extra requirements.*/ 393 size_t idx() const { return _idx; } 394 }; 395 396 public: 397 using Base::operator[]; 398 399 explicit CircularQueue(uint32_t size = 0) 400 : _capacity(size), _head(1), _tail(0), _empty(true), _round(0) 401 { 402 Base::resize(size); 403 } 404 405 /** 406 * Remove all the elements in the queue. 407 * 408 * Note: This does not actually remove elements from the backing 409 * store. 410 */ 411 void flush() 412 { 413 _head = 1; 414 _round = 0; 415 _tail = 0; 416 _empty = true; 417 } 418 419 /** Test if the index is in the range of valid elements. */ 420 bool isValidIdx(size_t idx) const 421 { 422 /* An index is invalid if: 423 * - The queue is empty. 424 * (6,T,3,2): |-|-|-]|[-|-|x| 425 * - head is small than tail and: 426 * - It is greater than both head and tail. 427 * (6,F,1,3): |-|[o|o|o]|-|x| 428 * - It is less than both head and tail. 429 * (6,F,1,3): |x|[o|o|o]|-|-| 430 * - It is greater than the tail and not than the head. 431 * (6,F,4,1): |o|o]|-|x|[o|o| 432 */ 433 return !(_empty || ( 434 (_head < _tail) && ( 435 (_head < idx && _tail < idx) || 436 (_head > idx && _tail > idx) 437 )) || (_tail < idx && idx < _head)); 438 } 439 440 /** Test if the index is in the range of valid elements. 441 * The round counter is used to disambiguate aliasing. 442 */ 443 bool isValidIdx(size_t idx, uint32_t round) const 444 { 445 /* An index is valid if: 446 * - The queue is not empty. 447 * - round == R and 448 * - index <= tail (if index > tail, that would be PTE) 449 * - Either: 450 * - head <= index 451 * (6,F,1,3,R): |-|[o|(*,r)|o]|-|-| 452 * - head > tail 453 * (6,F,5,3,R): |o|o|(*,r)|o]|-|[o| 454 * The remaining case means the the iterator is BTB: 455 * (6,F,3,4,R): |-|-|(x,r)|[o|o]|-| 456 * - round + 1 == R and: 457 * - index > tail. If index <= tail, that would be BTB: 458 * (6,F,2,3,r): | -|- |[(*,r)|o]|-|-| 459 * (6,F,0,1,r+1): |[o|o]| (x,r)|- |-|-| 460 * (6,F,0,3,r+1): |[o|o | (*,r)|o]|-|-| 461 * - index >= head. If index < head, that would be BTB: 462 * (6,F,5,2,R): |o|o]|-|-|(x,r)|[o| 463 * - head > tail. If head <= tail, that would be BTB: 464 * (6,F,3,4,R): |[o|o]|(x,r)|-|-|-| 465 * Other values of the round meand that the index is PTE or BTB 466 */ 467 return (!_empty && ( 468 (round == _round && idx <= _tail && ( 469 _head <= idx || _head > _tail)) || 470 (round + 1 == _round && 471 idx > _tail && 472 idx >= _head && 473 _head > _tail) 474 )); 475 } 476 477 reference front() { return (*this)[_head]; } 478 reference back() { return (*this)[_tail]; } 479 uint32_t head() const { return _head; } 480 uint32_t tail() const { return _tail; } 481 size_t capacity() const { return _capacity; } 482 483 uint32_t size() const 484 { 485 if (_empty) 486 return 0; 487 else if (_head <= _tail) 488 return _tail - _head + 1; 489 else 490 return _capacity - _head + _tail + 1; 491 } 492 493 uint32_t moduloAdd(uint32_t s1, uint32_t s2) const 494 { 495 return moduloAdd(s1, s2, _capacity); 496 } 497 498 uint32_t moduloSub(uint32_t s1, uint32_t s2) const 499 { 500 return moduloSub(s1, s2, _capacity); 501 } 502 503 /** Circularly increase the head pointer. 504 * By increasing the head pointer we are removing elements from 505 * the begin of the circular queue. 506 * Check that the queue is not empty. And set it to empty if it 507 * had only one value prior to insertion. 508 * 509 * @params num_elem number of elements to remove 510 */ 511 void pop_front(size_t num_elem = 1) 512 { 513 if (num_elem == 0) return; 514 auto hIt = begin(); 515 hIt += num_elem; 516 assert(hIt <= end()); 517 _empty = hIt == end(); 518 _head = hIt._idx; 519 } 520 521 /** Circularly decrease the tail pointer. */ 522 void pop_back() 523 { 524 assert (!_empty); 525 _empty = _head == _tail; 526 if (_tail == 0) 527 --_round; 528 decrease(_tail); 529 } 530 531 /** Pushes an element at the end of the queue. */ 532 void push_back(typename Base::value_type val) 533 { 534 advance_tail(); 535 (*this)[_tail] = val; 536 } 537 538 /** Increases the tail by one. 539 * Check for wrap-arounds to update the round counter. 540 */ 541 void advance_tail() 542 { 543 increase(_tail); 544 if (_tail == 0) 545 ++_round; 546 547 if (_tail == _head && !_empty) 548 increase(_head); 549 550 _empty = false; 551 } 552 553 /** Increases the tail by a specified number of steps 554 * 555 * @param len Number of steps 556 */ 557 void advance_tail(uint32_t len) 558 { 559 for (auto idx = 0; idx < len; idx++) 560 advance_tail(); 561 } 562 563 /** Is the queue empty? */ 564 bool empty() const { return _empty; } 565 566 /** Is the queue full? 567 * A queue is full if the head is the 0^{th} element and the tail is 568 * the (size-1)^{th} element, or if the head is the n^{th} element and 569 * the tail the (n-1)^{th} element. 570 */ 571 bool full() const 572 { 573 return !_empty && 574 (_tail + 1 == _head || (_tail + 1 == _capacity && _head == 0)); 575 } 576 577 /** Iterators. */ 578 iterator begin() 579 { 580 if (_empty) 581 return end(); 582 else if (_head > _tail) 583 return iterator(this, _head, _round - 1); 584 else 585 return iterator(this, _head, _round); 586 } 587 588 /* TODO: This should return a const_iterator. */ 589 iterator begin() const 590 { 591 if (_empty) 592 return end(); 593 else if (_head > _tail) 594 return iterator(const_cast<CircularQueue*>(this), _head, 595 _round - 1); 596 else 597 return iterator(const_cast<CircularQueue*>(this), _head, 598 _round); 599 } 600 601 iterator end() 602 { 603 auto poi = moduloAdd(_tail, 1); 604 auto round = _round; 605 if (poi == 0) 606 ++round; 607 return iterator(this, poi, round); 608 } 609 610 iterator end() const 611 { 612 auto poi = moduloAdd(_tail, 1); 613 auto round = _round; 614 if (poi == 0) 615 ++round; 616 return iterator(const_cast<CircularQueue*>(this), poi, round); 617 } 618 619 /** Return an iterator to an index in the vector. 620 * This poses the problem of round determination. By convention, the round 621 * is picked so that isValidIndex(idx, round) is true. If that is not 622 * possible, then the round value is _round, unless _tail is at the end of 623 * the storage, in which case the PTE wraps up and becomes _round + 1 624 */ 625 iterator getIterator(size_t idx) 626 { 627 assert(isValidIdx(idx) || moduloAdd(_tail, 1) == idx); 628 if (_empty) 629 return end(); 630 631 uint32_t round = _round; 632 if (idx > _tail) { 633 if (idx >= _head && _head > _tail) { 634 round -= 1; 635 } 636 } else if (idx < _head && _tail + 1 == _capacity) { 637 round += 1; 638 } 639 return iterator(this, idx, round); 640 } 641}; 642 643#endif /* __BASE_CIRCULARQUEUE_HH__ */ 644