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