circular_queue.hh revision 13487:ed055875261d
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 int ret = (uint32_t)(op1 - op2) % size; 110 return ret >= 0 ? ret : ret + size; 111 } 112 113 void increase(uint32_t& v, size_t delta = 1) 114 { 115 v = moduloAdd(v, delta, _capacity); 116 } 117 118 void decrease(uint32_t& v) 119 { 120 v = (v ? v : _capacity) - 1; 121 } 122 123 /** Iterator to the circular queue. 124 * iterator implementation to provide the circular-ness that the 125 * standard std::vector<T>::iterator does not implement. 126 * Iterators to a queue are represented by a pair of a character and the 127 * round counter. For the character, '*' denotes the element pointed to by 128 * the iterator if it is valid. 'x' denotes the element pointed to by the 129 * iterator when it is BTB or PTE. 130 * E.g.: 131 * - Iterator to the head of a queue of capacity 4 with 2 elems. 132 * (4,F,0,1,R): |[(*,R)|o]|-|-| (4,F,3,0): |o]|-|-|[(*,R)| 133 * - Iterator to the tail of a queue of capacity 4 with 2 elems. 134 * (4,F,0,1,R): |[o|(*,R)]|-|-| (4,F,3,0): |(*,R)]|-|-|[o| 135 * - Iterator to the end of a queue of capacity 4 with 2 elems. 136 * (4,F,0,1,R): |[o|o]|(x,R)|-| (4,F,3,0): |o]|(x,R)|-|[o| 137 */ 138 public: 139 struct iterator { 140 CircularQueue* _cq; 141 uint32_t _idx; 142 uint32_t _round; 143 144 public: 145 iterator(CircularQueue* cq, uint32_t idx, uint32_t round) 146 : _cq(cq), _idx(idx), _round(round) {} 147 148 /** Iterator Traits */ 149 using value_type = T; 150 using difference_type = std::ptrdiff_t; 151 using reference = value_type&; 152 using const_reference = const value_type&; 153 using pointer = value_type*; 154 using const_pointer = const value_type*; 155 using iterator_category = std::random_access_iterator_tag; 156 157 /** Trait reference type 158 * iterator satisfies OutputIterator, therefore reference 159 * must be T& */ 160 static_assert(std::is_same<reference, T&>::value, 161 "reference type is not assignable as required"); 162 163 iterator() : _cq(nullptr), _idx(0), _round(0) { } 164 165 iterator(const iterator& it) 166 : _cq(it._cq), _idx(it._idx), _round(it._round) {} 167 168 iterator& 169 operator=(const iterator& it) 170 { 171 _cq = it._cq; 172 _idx = it._idx; 173 _round = it._round; 174 return *this; 175 } 176 177 ~iterator() { _cq = nullptr; _idx = 0; _round = 0; } 178 179 /** Test dereferenceability. 180 * An iterator is dereferenceable if it is pointing to a non-null 181 * circular queue, it is not the past-the-end iterator and the 182 * index is a valid index to that queue. PTE test is required to 183 * distinguish between: 184 * - An iterator to the first element of a full queue 185 * (4,F,1,0): |o]|[*|o|o| 186 * - The end() iterator of a full queue 187 * (4,F,1,0): |o]|x[o|o|o| 188 * Sometimes, though, users will get the PTE iterator and expect it 189 * to work after growing the buffer on the tail, so we have to 190 * check if the iterator is still PTE. 191 */ 192 bool 193 dereferenceable() const 194 { 195 return _cq != nullptr && _cq->isValidIdx(_idx, _round); 196 } 197 198 /** InputIterator. */ 199 200 /** Equality operator. 201 * Two iterators must point to the same, possibly null, circular 202 * queue and the same element on it, including PTE, to be equal. 203 * In case the clients the the PTE iterator and then grow on the back 204 * and expect it to work, we have to check if the PTE is still PTE 205 */ 206 bool operator==(const iterator& that) const 207 { 208 return _cq == that._cq && _idx == that._idx && 209 _round == that._round; 210 } 211 212 /** Inequality operator. 213 * Conversely, two iterators are different if they both point to 214 * different circular queues or they point to different elements. 215 */ 216 bool operator!=(const iterator& that) 217 { 218 return !(*this == that); 219 } 220 221 /** Dereference operator. */ 222 reference operator*() 223 { 224 /* this has to be dereferenceable. */ 225 return (*_cq)[_idx]; 226 } 227 228 const_reference operator*() const 229 { 230 /* this has to be dereferenceable. */ 231 return (*_cq)[_idx]; 232 } 233 234 /** Dereference operator. 235 * Rely on operator* to check for dereferenceability. 236 */ 237 pointer operator->() 238 { 239 return &((*_cq)[_idx]); 240 } 241 242 const_pointer operator->() const 243 { 244 return &((*_cq)[_idx]); 245 } 246 247 /** Pre-increment operator. */ 248 iterator& operator++() 249 { 250 /* this has to be dereferenceable. */ 251 _cq->increase(_idx); 252 if (_idx == 0) 253 ++_round; 254 return *this; 255 } 256 257 /** Post-increment operator. */ 258 iterator 259 operator++(int) 260 { 261 iterator t = *this; 262 ++*this; 263 return t; 264 } 265 266 /** ForwardIterator 267 * The multipass guarantee is provided by the reliance on _idx. 268 */ 269 270 /** BidirectionalIterator requirements. */ 271 private: 272 /** Test decrementability. 273 * An iterator to a non-null circular queue is not-decrementable 274 * if it is pointing to the head element, unless the queue is full 275 * and we are talking about the past-the-end iterator. In that case, 276 * the iterator round equals the cq round unless the head is at the 277 * zero position and the round is one more than the cq round. 278 */ 279 bool 280 decrementable() const 281 { 282 return _cq && !(_idx == _cq->head() && 283 (_cq->empty() || 284 (_idx == 0 && _round != _cq->_round + 1) || 285 (_idx !=0 && _round != _cq->_round))); 286 } 287 288 public: 289 /** Pre-decrement operator. */ 290 iterator& operator--() 291 { 292 /* this has to be decrementable. */ 293 assert(decrementable()); 294 if (_idx == 0) 295 --_round; 296 _cq->decrease(_idx); 297 return *this; 298 } 299 300 /** Post-decrement operator. */ 301 iterator operator--(int ) { iterator t = *this; --*this; return t; } 302 303 /** RandomAccessIterator requirements.*/ 304 iterator& operator+=(const difference_type& t) 305 { 306 assert(_cq); 307 _round += (t + _idx) / _cq->capacity(); 308 _idx = _cq->moduloAdd(_idx, t); 309 return *this; 310 } 311 312 iterator& operator-=(const difference_type& t) 313 { 314 assert(_cq); 315 316 /* C does not do euclidean division, so we have to adjust */ 317 if (t >= 0) 318 _round += (-t + _idx) / _cq->capacity(); 319 else 320 _round += (-t + _idx - _cq->capacity() + 1) / _cq->capacity(); 321 322 _idx = _cq->moduloSub(_idx, t); 323 return *this; 324 } 325 326 /** Addition operator. */ 327 iterator operator+(const difference_type& t) 328 { 329 iterator ret(*this); 330 return ret += t; 331 } 332 333 friend iterator operator+(const difference_type& t, iterator& it) 334 { 335 iterator ret = it; 336 return ret += t; 337 } 338 339 /** Substraction operator. */ 340 iterator operator-(const difference_type& t) 341 { 342 iterator ret(*this); 343 return ret -= t; 344 } 345 346 friend iterator operator-(const difference_type& t, iterator& it) 347 { 348 iterator ret = it; 349 return ret -= t; 350 } 351 352 /** Difference operator. 353 * that + ret == this 354 */ 355 difference_type operator-(const iterator& that) 356 { 357 /* If a is already at the end, we can safely return 0. */ 358 auto ret = _cq->moduloSub(this->_idx, that._idx); 359 360 if (ret == 0 && this->_round != that._round) { 361 ret += this->_round * _cq->capacity(); 362 } 363 return ret; 364 } 365 366 /** Index operator. 367 * The use of * tests for dereferenceability. 368 */ 369 template<typename Idx> 370 typename std::enable_if<std::is_integral<Idx>::value,reference>::type 371 operator[](const Idx& index) { return *(*this + index); } 372 373 /** Comparisons. */ 374 bool 375 operator<(const iterator& that) const 376 { 377 assert(_cq && that._cq == _cq); 378 return (this->_round < that._round) || 379 (this->_round == that._round && _idx < that._idx); 380 } 381 382 bool 383 operator>(const iterator& that) const 384 { return !(*this <= that); } 385 386 bool operator>=(const iterator& that) const 387 { return !(*this < that); } 388 389 bool operator<=(const iterator& that) const 390 { return !(that < *this); } 391 392 /** 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