1/* 2 * Copyright (c) 2017-2018 ARM Limited 3 * All rights reserved 4 * 5 * The license below extends only to copyright in the software and shall 6 * not be construed as granting a license to any other intellectual 7 * property including but not limited to intellectual property relating 8 * to a hardware implementation of the functionality of the software 9 * licensed hereunder. You may use the software subject to the license 10 * terms below provided that you ensure that this notice is replicated 11 * unmodified and in its entirety in all distributions of the software, 12 * modified or unmodified, in source code or in binary form. 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions are 16 * met: redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer; 18 * redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution; 21 * neither the name of the copyright holders nor the names of its 22 * contributors may be used to endorse or promote products derived from 23 * this software without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36 * 37 * Authors: Rekai Gonzalez-Alberquilla 38 */ 39 40#ifndef __BASE_CIRCULAR_QUEUE_HH__ 41#define __BASE_CIRCULAR_QUEUE_HH__ 42 43#include <cassert> 44#include <cstddef> 45#include <cstdint> 46#include <iterator> 47#include <type_traits> 48#include <vector> 49 50/** Circular queue. 51 * Circular queue implemented on top of a standard vector. Instead of using 52 * a sentinel entry, we use a boolean to distinguish the case in which the 53 * queue is full or empty. 54 * Thus, a circular queue is represented by the 5-tuple 55 * (Capacity, IsEmpty?, Head, Tail, Round) 56 * Where: 57 * - Capacity is the size of the underlying vector. 58 * - IsEmpty? can be T or F. 59 * - Head is the index in the vector of the first element of the queue. 60 * - Tail is the index in the vector of the last element of the queue. 61 * - Round is the counter of how many times the Tail has wrapped around. 62 * A queue is empty when 63 * Head == (Tail + 1 mod Capacity) && IsEmpty?. 64 * Conversely, a queue if full when 65 * Head == (Tail + 1 mod Capacity) && !IsEmpty?. 66 * Comments may show depictions of the underlying vector in the following 67 * format: '|' delimit the 'cells' of the underlying vector. '-' represents 68 * an element of the vector that is out-of-bounds of the circular queue, 69 * while 'o' represents and element that is inside the bounds. The 70 * characters '[' and ']' are added to mark the entries that hold the head 71 * and tail of the circular queue respectively. 72 * E.g.: 73 * - Empty queues of capacity 4: 74 * (4,T,1,0,_): |-]|[-|-|-| (4,T,3,2): |-|-|-]|[-| 75 * - Full queues of capacity 4: 76 * (4,F,1,0,_): |o]|[o|o|o| (4,F,3,2): |o|o|o]|[o| 77 * - Queues of capacity 4 with 2 elements: 78 * (4,F,0,1,_): |[o|o]|-|-| (4,F,3,0): |o]|-|-|[o| 79 * 80 * The Round number is only relevant for checking validity of indices, 81 * therefore it will be omitted or shown as '_' 82 */ 83template <typename T> 84class CircularQueue : private std::vector<T> 85{ 86 protected: 87 using Base = std::vector<T>; 88 using typename Base::reference; 89 using typename Base::const_reference; 90 const uint32_t _capacity; 91 uint32_t _head; 92 uint32_t _tail; 93 uint32_t _empty; 94 95 /** Counter for how many times the tail wraps around. 96 * Some parts of the code rely on getting the past the end iterator, and 97 * expect to use it after inserting on the tail. To support this without 98 * ambiguity, we need the round number to guarantee that it did not become 99 * a before-the-beginning iterator. 100 */ 101 uint32_t _round; 102 103 /** General modular addition. */ 104 static uint32_t 105 moduloAdd(uint32_t op1, uint32_t op2, uint32_t size) 106 { 107 return (op1 + op2) % size; 108 } 109 110 /** General modular subtraction. */ 111 static uint32_t 112 moduloSub(uint32_t op1, uint32_t op2, uint32_t size) 113 { 114 int32_t ret = sub(op1, op2, size); 115 return ret >= 0 ? ret : ret + size; 116 } 117 118 static int32_t 119 sub(uint32_t op1, uint32_t op2, uint32_t size) 120 { 121 if (op1 > op2) 122 return (op1 - op2) % size; 123 else 124 return -((op2 - op1) % size); 125 } 126 127 void increase(uint32_t& v, size_t delta = 1) 128 { 129 v = moduloAdd(v, delta, _capacity); 130 } 131 132 void decrease(uint32_t& v) 133 { 134 v = (v ? v : _capacity) - 1; 135 } 136 137 /** Iterator to the circular queue. 138 * iterator implementation to provide the circular-ness that the 139 * standard std::vector<T>::iterator does not implement. 140 * Iterators to a queue are represented by a pair of a character and the 141 * round counter. For the character, '*' denotes the element pointed to by 142 * the iterator if it is valid. 'x' denotes the element pointed to by the 143 * iterator when it is BTB or PTE. 144 * E.g.: 145 * - Iterator to the head of a queue of capacity 4 with 2 elems. 146 * (4,F,0,1,R): |[(*,R)|o]|-|-| (4,F,3,0): |o]|-|-|[(*,R)| 147 * - Iterator to the tail of a queue of capacity 4 with 2 elems. 148 * (4,F,0,1,R): |[o|(*,R)]|-|-| (4,F,3,0): |(*,R)]|-|-|[o| 149 * - Iterator to the end of a queue of capacity 4 with 2 elems. 150 * (4,F,0,1,R): |[o|o]|(x,R)|-| (4,F,3,0): |o]|(x,R)|-|[o| 151 */ 152 public: 153 struct iterator { 154 CircularQueue* _cq; 155 uint32_t _idx; 156 uint32_t _round; 157 158 public: 159 iterator(CircularQueue* cq, uint32_t idx, uint32_t round) 160 : _cq(cq), _idx(idx), _round(round) {} 161 162 /** Iterator Traits */ 163 using value_type = T; 164 using difference_type = std::ptrdiff_t; 165 using reference = value_type&; 166 using const_reference = const value_type&; 167 using pointer = value_type*; 168 using const_pointer = const value_type*; 169 using iterator_category = std::random_access_iterator_tag; 170 171 /** Trait reference type 172 * iterator satisfies OutputIterator, therefore reference 173 * must be T& */ 174 static_assert(std::is_same<reference, T&>::value, 175 "reference type is not assignable as required"); 176 177 iterator() : _cq(nullptr), _idx(0), _round(0) { } 178 179 iterator(const iterator& it) 180 : _cq(it._cq), _idx(it._idx), _round(it._round) {} 181 182 iterator& 183 operator=(const iterator& it) 184 { 185 _cq = it._cq; 186 _idx = it._idx; 187 _round = it._round; 188 return *this; 189 } 190 191 ~iterator() { _cq = nullptr; _idx = 0; _round = 0; } 192 193 /** Test dereferenceability. 194 * An iterator is dereferenceable if it is pointing to a non-null 195 * circular queue, it is not the past-the-end iterator and the 196 * index is a valid index to that queue. PTE test is required to 197 * distinguish between: 198 * - An iterator to the first element of a full queue 199 * (4,F,1,0): |o]|[*|o|o| 200 * - The end() iterator of a full queue 201 * (4,F,1,0): |o]|x[o|o|o| 202 * Sometimes, though, users will get the PTE iterator and expect it 203 * to work after growing the buffer on the tail, so we have to 204 * check if the iterator is still PTE. 205 */ 206 bool 207 dereferenceable() const 208 { 209 return _cq != nullptr && _cq->isValidIdx(_idx, _round); 210 } 211 212 /** InputIterator. */ 213 214 /** Equality operator. 215 * Two iterators must point to the same, possibly null, circular 216 * queue and the same element on it, including PTE, to be equal. 217 * In case the clients the the PTE iterator and then grow on the back 218 * and expect it to work, we have to check if the PTE is still PTE 219 */ 220 bool operator==(const iterator& that) const 221 { 222 return _cq == that._cq && _idx == that._idx && 223 _round == that._round; 224 } 225 226 /** Inequality operator. 227 * Conversely, two iterators are different if they both point to 228 * different circular queues or they point to different elements. 229 */ 230 bool operator!=(const iterator& that) 231 { 232 return !(*this == that); 233 } 234 235 /** Dereference operator. */ 236 reference operator*() 237 { 238 /* this has to be dereferenceable. */ 239 return (*_cq)[_idx]; 240 } 241 242 const_reference operator*() const 243 { 244 /* this has to be dereferenceable. */ 245 return (*_cq)[_idx]; 246 } 247 248 /** Dereference operator. 249 * Rely on operator* to check for dereferenceability. 250 */ 251 pointer operator->() 252 { 253 return &((*_cq)[_idx]); 254 } 255 256 const_pointer operator->() const 257 { 258 return &((*_cq)[_idx]); 259 } 260 261 /** Pre-increment operator. */ 262 iterator& operator++() 263 { 264 /* this has to be dereferenceable. */ 265 _cq->increase(_idx); 266 if (_idx == 0) 267 ++_round; 268 return *this; 269 } 270 271 /** Post-increment operator. */ 272 iterator 273 operator++(int) 274 { 275 iterator t = *this; 276 ++*this; 277 return t; 278 } 279 280 /** ForwardIterator 281 * The multipass guarantee is provided by the reliance on _idx. 282 */ 283 284 /** BidirectionalIterator requirements. */ 285 private: 286 /** Test decrementability. 287 * An iterator to a non-null circular queue is not-decrementable 288 * if it is pointing to the head element, unless the queue is full 289 * and we are talking about the past-the-end iterator. In that case, 290 * the iterator round equals the cq round unless the head is at the 291 * zero position and the round is one more than the cq round. 292 */ 293 bool 294 decrementable() const 295 { 296 return _cq && !(_idx == _cq->head() && 297 (_cq->empty() || 298 (_idx == 0 && _round != _cq->_round + 1) || 299 (_idx !=0 && _round != _cq->_round))); 300 } 301 302 public: 303 /** Pre-decrement operator. */ 304 iterator& operator--() 305 { 306 /* this has to be decrementable. */ 307 assert(decrementable()); 308 if (_idx == 0) 309 --_round; 310 _cq->decrease(_idx); 311 return *this; 312 } 313 314 /** Post-decrement operator. */ 315 iterator operator--(int ) { iterator t = *this; --*this; return t; } 316 317 /** RandomAccessIterator requirements.*/ 318 iterator& operator+=(const difference_type& t) 319 { 320 assert(_cq); 321 _round += (t + _idx) / _cq->capacity(); 322 _idx = _cq->moduloAdd(_idx, t); 323 return *this; 324 } 325 326 iterator& operator-=(const difference_type& t) 327 { 328 assert(_cq); 329 330 /* C does not do euclidean division, so we have to adjust */ 331 if (t >= 0) { 332 _round += (-t + _idx) / _cq->capacity(); 333 _idx = _cq->moduloSub(_idx, t); 334 } else { 335 *this += -t; 336 } 337 return *this; 338 } 339 340 /** Addition operator. */ 341 iterator operator+(const difference_type& t) 342 { 343 iterator ret(*this); 344 return ret += t; 345 } 346 347 friend iterator operator+(const difference_type& t, iterator& it) 348 { 349 iterator ret = it; 350 return ret += t; 351 } 352 353 /** Substraction operator. */ 354 iterator operator-(const difference_type& t) 355 { 356 iterator ret(*this); 357 return ret -= t; 358 } 359 360 friend iterator operator-(const difference_type& t, iterator& it) 361 { 362 iterator ret = it; 363 return ret -= t; 364 } 365 366 /** Difference operator. 367 * that + ret == this 368 */ 369 difference_type operator-(const iterator& that) 370 { 371 /* If a is already at the end, we can safely return 0. */ 372 auto ret = _cq->sub(this->_idx, that._idx, _cq->capacity()); 373 374 if (this->_round != that._round) { 375 ret += ((this->_round - that._round) * _cq->capacity()); 376 } 377 return ret; 378 } 379 380 /** Index operator. 381 * The use of * tests for dereferenceability. 382 */ 383 template<typename Idx> 384 typename std::enable_if<std::is_integral<Idx>::value,reference>::type 385 operator[](const Idx& index) { return *(*this + index); } 386 387 /** Comparisons. */ 388 bool 389 operator<(const iterator& that) const 390 { 391 assert(_cq && that._cq == _cq); 392 return (this->_round < that._round) || 393 (this->_round == that._round && _idx < that._idx); 394 } 395 396 bool 397 operator>(const iterator& that) const 398 { return !(*this <= that); } 399 400 bool operator>=(const iterator& that) const 401 { return !(*this < that); } 402 403 bool operator<=(const iterator& that) const 404 { return !(that < *this); } 405 406 /** OutputIterator has no extra requirements.*/ 407 size_t idx() const { return _idx; } 408 }; 409 410 public: 411 using Base::operator[]; 412 413 explicit CircularQueue(uint32_t size = 0) 414 : _capacity(size), _head(1), _tail(0), _empty(true), _round(0) 415 { 416 Base::resize(size); 417 } 418 419 /** 420 * Remove all the elements in the queue. 421 * 422 * Note: This does not actually remove elements from the backing 423 * store. 424 */ 425 void flush() 426 { 427 _head = 1; 428 _round = 0; 429 _tail = 0; 430 _empty = true; 431 } 432 433 /** Test if the index is in the range of valid elements. */ 434 bool isValidIdx(size_t idx) const 435 { 436 /* An index is invalid if: 437 * - The queue is empty. 438 * (6,T,3,2): |-|-|-]|[-|-|x| 439 * - head is small than tail and: 440 * - It is greater than both head and tail. 441 * (6,F,1,3): |-|[o|o|o]|-|x| 442 * - It is less than both head and tail. 443 * (6,F,1,3): |x|[o|o|o]|-|-| 444 * - It is greater than the tail and not than the head. 445 * (6,F,4,1): |o|o]|-|x|[o|o| 446 */ 447 return !(_empty || ( 448 (_head < _tail) && ( 449 (_head < idx && _tail < idx) || 450 (_head > idx && _tail > idx) 451 )) || (_tail < idx && idx < _head)); 452 } 453 454 /** Test if the index is in the range of valid elements. 455 * The round counter is used to disambiguate aliasing. 456 */ 457 bool isValidIdx(size_t idx, uint32_t round) const 458 { 459 /* An index is valid if: 460 * - The queue is not empty. 461 * - round == R and 462 * - index <= tail (if index > tail, that would be PTE) 463 * - Either: 464 * - head <= index 465 * (6,F,1,3,R): |-|[o|(*,r)|o]|-|-| 466 * - head > tail 467 * (6,F,5,3,R): |o|o|(*,r)|o]|-|[o| 468 * The remaining case means the the iterator is BTB: 469 * (6,F,3,4,R): |-|-|(x,r)|[o|o]|-| 470 * - round + 1 == R and: 471 * - index > tail. If index <= tail, that would be BTB: 472 * (6,F,2,3,r): | -|- |[(*,r)|o]|-|-| 473 * (6,F,0,1,r+1): |[o|o]| (x,r)|- |-|-| 474 * (6,F,0,3,r+1): |[o|o | (*,r)|o]|-|-| 475 * - index >= head. If index < head, that would be BTB: 476 * (6,F,5,2,R): |o|o]|-|-|(x,r)|[o| 477 * - head > tail. If head <= tail, that would be BTB: 478 * (6,F,3,4,R): |[o|o]|(x,r)|-|-|-| 479 * Other values of the round meand that the index is PTE or BTB 480 */ 481 return (!_empty && ( 482 (round == _round && idx <= _tail && ( 483 _head <= idx || _head > _tail)) || 484 (round + 1 == _round && 485 idx > _tail && 486 idx >= _head && 487 _head > _tail) 488 )); 489 } 490 491 reference front() { return (*this)[_head]; } 492 reference back() { return (*this)[_tail]; } 493 uint32_t head() const { return _head; } 494 uint32_t tail() const { return _tail; } 495 size_t capacity() const { return _capacity; } 496 497 uint32_t size() const 498 { 499 if (_empty) 500 return 0; 501 else if (_head <= _tail) 502 return _tail - _head + 1; 503 else 504 return _capacity - _head + _tail + 1; 505 } 506 507 uint32_t moduloAdd(uint32_t s1, uint32_t s2) const 508 { 509 return moduloAdd(s1, s2, _capacity); 510 } 511 512 uint32_t moduloSub(uint32_t s1, uint32_t s2) const 513 { 514 return moduloSub(s1, s2, _capacity); 515 } 516 517 /** Circularly increase the head pointer. 518 * By increasing the head pointer we are removing elements from 519 * the begin of the circular queue. 520 * Check that the queue is not empty. And set it to empty if it 521 * had only one value prior to insertion. 522 * 523 * @params num_elem number of elements to remove 524 */ 525 void pop_front(size_t num_elem = 1) 526 { 527 if (num_elem == 0) return; 528 auto hIt = begin(); 529 hIt += num_elem; 530 assert(hIt <= end()); 531 _empty = hIt == end(); 532 _head = hIt._idx; 533 } 534 535 /** Circularly decrease the tail pointer. */ 536 void pop_back() 537 { 538 assert (!_empty); 539 _empty = _head == _tail; 540 if (_tail == 0) 541 --_round; 542 decrease(_tail); 543 } 544 545 /** Pushes an element at the end of the queue. */ 546 void push_back(typename Base::value_type val) 547 { 548 advance_tail(); 549 (*this)[_tail] = val; 550 } 551 552 /** Increases the tail by one. 553 * Check for wrap-arounds to update the round counter. 554 */ 555 void advance_tail() 556 { 557 increase(_tail); 558 if (_tail == 0) 559 ++_round; 560 561 if (_tail == _head && !_empty) 562 increase(_head); 563 564 _empty = false; 565 } 566 567 /** Increases the tail by a specified number of steps 568 * 569 * @param len Number of steps 570 */ 571 void advance_tail(uint32_t len) 572 { 573 for (auto idx = 0; idx < len; idx++) 574 advance_tail(); 575 } 576 577 /** Is the queue empty? */ 578 bool empty() const { return _empty; } 579 580 /** Is the queue full? 581 * A queue is full if the head is the 0^{th} element and the tail is 582 * the (size-1)^{th} element, or if the head is the n^{th} element and 583 * the tail the (n-1)^{th} element. 584 */ 585 bool full() const 586 { 587 return !_empty && 588 (_tail + 1 == _head || (_tail + 1 == _capacity && _head == 0)); 589 } 590 591 /** Iterators. */ 592 iterator begin() 593 { 594 if (_empty) 595 return end(); 596 else if (_head > _tail) 597 return iterator(this, _head, _round - 1); 598 else 599 return iterator(this, _head, _round); 600 } 601 602 /* TODO: This should return a const_iterator. */ 603 iterator begin() const 604 { 605 if (_empty) 606 return end(); 607 else if (_head > _tail) 608 return iterator(const_cast<CircularQueue*>(this), _head, 609 _round - 1); 610 else 611 return iterator(const_cast<CircularQueue*>(this), _head, 612 _round); 613 } 614 615 iterator end() 616 { 617 auto poi = moduloAdd(_tail, 1); 618 auto round = _round; 619 if (poi == 0) 620 ++round; 621 return iterator(this, poi, round); 622 } 623 624 iterator end() const 625 { 626 auto poi = moduloAdd(_tail, 1); 627 auto round = _round; 628 if (poi == 0) 629 ++round; 630 return iterator(const_cast<CircularQueue*>(this), poi, round); 631 } 632 633 /** Return an iterator to an index in the vector. 634 * This poses the problem of round determination. By convention, the round 635 * is picked so that isValidIndex(idx, round) is true. If that is not 636 * possible, then the round value is _round, unless _tail is at the end of 637 * the storage, in which case the PTE wraps up and becomes _round + 1 638 */ 639 iterator getIterator(size_t idx) 640 { 641 assert(isValidIdx(idx) || moduloAdd(_tail, 1) == idx); 642 if (_empty) 643 return end(); 644 645 uint32_t round = _round; 646 if (idx > _tail) { 647 if (idx >= _head && _head > _tail) { 648 round -= 1; 649 } 650 } else if (idx < _head && _tail + 1 == _capacity) { 651 round += 1; 652 } 653 return iterator(this, idx, round); 654 } 655}; 656 657#endif /* __BASE_CIRCULARQUEUE_HH__ */ 658