src/base/circular_queue.hh

   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
  38 #ifndef __BASE_CIRCULAR_QUEUE_HH__
  39 #define __BASE_CIRCULAR_QUEUE_HH__
  40
  41 #include <cassert>
  42 #include <cstddef>
  43 #include <cstdint>
  44 #include <iterator>
  45 #include <type_traits>
  46 #include <vector>
  47
  48 /** Circular queue.
  49  * Circular queue implemented in a standard vector. All indices are
  50  * monotonically increasing, and modulo is used at access time to alias them
  51  * down to the actual storage.
  52  *
  53  * The queue keeps track of two pieces of state, a head index, which is the
  54  * index of the next element to come out of the queue, and a size which is how
  55  * many valid elements are currently in the queue. Size can increase to, but
  56  * never exceed, the capacity of the queue.
  57  *
  58  * In theory the index may overflow at some point, but since it's a 64 bit
  59  * value that would take a very long time.
  60  *
  61  * @tparam T Type of the elements in the queue
  62  *
  63  * @ingroup api_base_utils
  64  */
  65 template <typename T>
  66 class CircularQueue
  67 {
  68   protected:
  69     std::vector<T> data;
  70
  71     using reference = typename std::vector<T>::reference;
  72     using const_reference = typename std::vector<T>::const_reference;
  73     const size_t _capacity;
  74     size_t _size = 0;
  75     size_t _head = 1;
  76
  77     /** Iterator to the circular queue.
  78      * iterator implementation to provide wrap around indexing which the
  79      * vector iterator does not.
  80      */
  81   public:
  82     struct iterator
  83     {
  84       public:
  85         CircularQueue* _cq = nullptr;
  86         size_t _idx = 0;
  87
  88         /**
  89          * @ingroup api_base_utils
  90          */
  91         iterator(CircularQueue* cq, size_t idx) : _cq(cq), _idx(idx) {}
  92         iterator() = default;
  93
  94         /**
  95          * Iterator Traits
  96          *
  97          * @ingroup api_base_utils
  98          * @{
  99          */
 100         using value_type = T;
 101         using difference_type = std::ptrdiff_t;
 102         using reference = value_type&;
 103         using const_reference = const value_type&;
 104         using pointer = value_type*;
 105         using const_pointer = const value_type*;
 106         using iterator_category = std::random_access_iterator_tag;
 107         /** @} */ // end of api_base_utils
 108
 109         /** Trait reference type
 110          * iterator satisfies OutputIterator, therefore reference
 111          * must be T& */
 112         static_assert(std::is_same<reference, T&>::value,
 113                 "reference type is not assignable as required");
 114
 115         /**
 116          * @ingroup api_base_utils
 117          */
 118         iterator(const iterator& it) : _cq(it._cq), _idx(it._idx) {}
 119
 120         /**
 121          * @ingroup api_base_utils
 122          */
 123         iterator&
 124         operator=(const iterator& it)
 125         {
 126             _cq = it._cq;
 127             _idx = it._idx;
 128             return *this;
 129         }
 130
 131         /**
 132          * Test dereferenceability.
 133          * An iterator is dereferenceable if it is pointing to a non-null
 134          * circular queue, and the index is within the current range of the
 135          * queue.
 136          *
 137          * @ingroup api_base_utils
 138          */
 139         bool
 140         dereferenceable() const
 141         {
 142             return _cq != nullptr && _cq->isValidIdx(_idx);
 143         }
 144
 145         /** InputIterator. */
 146
 147         /**
 148          * Equality operator.
 149          * Two iterators must point to the same, possibly null, circular
 150          * queue and the same element on it to be equal.
 151          *
 152          * @ingroup api_base_utils
 153          */
 154         bool
 155         operator==(const iterator& that) const
 156         {
 157             return _cq == that._cq && _idx == that._idx;
 158         }
 159
 160         /**
 161          * Inequality operator.
 162          * Conversely, two iterators are different if they both point to
 163          * different circular queues or they point to different elements.
 164          *
 165          * @ingroup api_base_utils
 166          */
 167         bool operator!=(const iterator& that) { return !(*this == that); }
 168
 169         /**
 170          * Dereference operator.
 171          *
 172          * @ingroup api_base_utils
 173          */
 174         reference
 175         operator*()
 176         {
 177             // This has to be dereferenceable.
 178             return (*_cq)[_idx];
 179         }
 180
 181         /**
 182          * @ingroup api_base_utils
 183          */
 184         const_reference
 185         operator*() const
 186         {
 187             // This has to be dereferenceable.
 188             return (*_cq)[_idx];
 189         }
 190
 191         /**
 192          * Dereference operator.
 193          * Rely on operator* to check for dereferenceability.
 194          *
 195          * @ingroup api_base_utils
 196          */
 197         pointer operator->() { return &**this; }
 198
 199         /**
 200          * @ingroup api_base_utils
 201          */
 202         const_pointer operator->() const { return &**this; }
 203
 204         /**
 205          * Pre-increment operator.
 206          *
 207          * @ingroup api_base_utils
 208          */
 209         iterator&
 210         operator++()
 211         {
 212             ++_idx;
 213             return *this;
 214         }
 215
 216         /**
 217          * Post-increment operator.
 218          *
 219          * @ingroup api_base_utils
 220          */
 221         iterator
 222         operator++(int)
 223         {
 224             iterator t = *this;
 225             ++*this;
 226             return t;
 227         }
 228
 229         /** ForwardIterator
 230          * The multipass guarantee is provided by the reliance on _idx.
 231          */
 232
 233         /** BidirectionalIterator requirements. */
 234       public:
 235         /**
 236          * Pre-decrement operator.
 237          *
 238          * @ingroup api_base_utils
 239          */
 240         iterator&
 241         operator--()
 242         {
 243             /* this has to be decrementable. */
 244             assert(_cq && _idx > _cq->head());
 245             --_idx;
 246             return *this;
 247         }
 248
 249         /**
 250          * Post-decrement operator.
 251          *
 252          * @ingroup api_base_utils
 253          */
 254         iterator
 255         operator--(int)
 256         {
 257             iterator t = *this;
 258             --*this;
 259             return t;
 260         }
 261
 262         /**
 263          * RandomAccessIterator requirements.
 264          *
 265          * @ingroup api_base_utils
 266          */
 267         iterator&
 268         operator+=(const difference_type& t)
 269         {
 270             _idx += t;
 271             return *this;
 272         }
 273
 274         /**
 275          * @ingroup api_base_utils
 276          */
 277         iterator&
 278         operator-=(const difference_type& t)
 279         {
 280             assert(_cq && _idx >= _cq->head() + t);
 281             _idx -= t;
 282             return *this;
 283         }
 284
 285         /**
 286          * Addition operator.
 287          *
 288          * @ingroup api_base_utils
 289          */
 290         iterator
 291         operator+(const difference_type& t)
 292         {
 293             iterator ret(*this);
 294             return ret += t;
 295         }
 296
 297         /**
 298          * @ingroup api_base_utils
 299          */
 300         friend iterator
 301         operator+(const difference_type& t, iterator& it)
 302         {
 303             iterator ret = it;
 304             return ret += t;
 305         }
 306
 307         /**
 308          * Substraction operator.
 309          *
 310          * @ingroup api_base_utils
 311          */
 312         iterator
 313         operator-(const difference_type& t)
 314         {
 315             iterator ret(*this);
 316             return ret -= t;
 317         }
 318
 319         /**
 320          * @ingroup api_base_utils
 321          */
 322         friend iterator
 323         operator-(const difference_type& t, iterator& it)
 324         {
 325             iterator ret = it;
 326             return ret -= t;
 327         }
 328
 329         /**
 330          * Difference operator.
 331          * that + ret == this
 332          *
 333          * @ingroup api_base_utils
 334          */
 335         difference_type
 336         operator-(const iterator& that)
 337         {
 338             return (ssize_t)_idx - (ssize_t)that._idx;
 339         }
 340
 341         /**
 342          * Index operator.
 343          * The use of * tests for dereferenceability.
 344          *
 345          * @ingroup api_base_utils
 346          */
 347         template<typename Idx>
 348         typename std::enable_if_t<std::is_integral<Idx>::value, reference>
 349         operator[](const Idx& index)
 350         {
 351             return *(*this + index);
 352         }
 353
 354         /**
 355          * Comparisons.
 356          *
 357          * @ingroup api_base_utils
 358          */
 359         bool
 360         operator<(const iterator& that) const
 361         {
 362             return _idx < that._idx;
 363         }
 364
 365         /**
 366          * @ingroup api_base_utils
 367          */
 368         bool operator>(const iterator& that) const { return !(*this <= that); }
 369
 370         /**
 371          * @ingroup api_base_utils
 372          */
 373         bool operator>=(const iterator& that) const { return !(*this < that); }
 374
 375         /**
 376          * @ingroup api_base_utils
 377          */
 378         bool operator<=(const iterator& that) const { return !(that < *this); }
 379
 380         /**
 381          * OutputIterator has no extra requirements.
 382          */
 383         size_t idx() const { return _idx; }
 384     };
 385
 386   public:
 387     /**
 388      * @ingroup api_base_utils
 389      */
 390     template <typename Idx>
 391     typename std::enable_if_t<std::is_integral<Idx>::value, reference>
 392     operator[](const Idx& index)
 393     {
 394         assert(index >= 0);
 395         return data[index % _capacity];
 396     }
 397
 398     template <typename Idx>
 399     typename std::enable_if_t<std::is_integral<Idx>::value, const_reference>
 400     operator[](const Idx& index) const
 401     {
 402         assert(index >= 0);
 403         return data[index % _capacity];
 404     }
 405
 406     /**
 407      * @ingroup api_base_utils
 408      */
 409     explicit CircularQueue(size_t size=0) : data(size), _capacity(size) {}
 410
 411     /**
 412      * Remove all the elements in the queue.
 413      *
 414      * Note: This does not actually remove elements from the backing
 415      * store.
 416      *
 417      * @ingroup api_base_utils
 418      */
 419     void
 420     flush()
 421     {
 422         _head = 1;
 423         _size = 0;
 424     }
 425
 426     /**
 427      * Test if the index is in the range of valid elements.
 428      */
 429     bool
 430     isValidIdx(size_t idx) const
 431     {
 432         return _head <= idx && idx < (_head + _size);
 433     }
 434
 435     /**
 436      * @ingroup api_base_utils
 437      */
 438     reference front() { return (*this)[head()]; }
 439
 440     /**
 441      * @ingroup api_base_utils
 442      */
 443     reference back() { return (*this)[tail()]; }
 444
 445     /**
 446      * @ingroup api_base_utils
 447      */
 448     size_t head() const { return _head; }
 449
 450     /**
 451      * @ingroup api_base_utils
 452      */
 453     size_t tail() const { return _head + _size - 1; }
 454
 455     /**
 456      * @ingroup api_base_utils
 457      */
 458     size_t capacity() const { return _capacity; }
 459
 460     /**
 461      * @ingroup api_base_utils
 462      */
 463     size_t size() const { return _size; }
 464
 465     /** Circularly increase the head pointer.
 466      * By increasing the head pointer we are removing elements from
 467      * the begin of the circular queue.
 468      *
 469      * @params num_elem number of elements to remove
 470      *
 471      * @ingroup api_base_utils
 472      */
 473     void
 474     pop_front(size_t num_elem=1)
 475     {
 476         assert(num_elem <= size());
 477         _head += num_elem;
 478         _size -= num_elem;
 479     }
 480
 481     /**
 482      * Circularly decrease the tail pointer.
 483      *
 484      * @ingroup api_base_utils
 485      */
 486     void
 487     pop_back()
 488     {
 489         assert(!empty());
 490         --_size;
 491     }
 492
 493     /**
 494      * Pushes an element at the end of the queue.
 495      *
 496      * @ingroup api_base_utils
 497      */
 498     void
 499     push_back(typename std::vector<T>::value_type val)
 500     {
 501         advance_tail();
 502         back() = val;
 503     }
 504
 505     /**
 506      * Increases the tail by one. This may overwrite the head if the queue is
 507      * full.
 508      *
 509      * @ingroup api_base_utils
 510      */
 511     void
 512     advance_tail()
 513     {
 514         if (full())
 515             ++_head;
 516         else
 517             ++_size;
 518     }
 519
 520     /**
 521      * Increases the tail by a specified number of steps. This may overwrite
 522      * one or more entries starting at the head if the queue is full.
 523      *
 524      * @param len Number of steps
 525      *
 526      * @ingroup api_base_utils
 527      */
 528     void
 529     advance_tail(size_t len)
 530     {
 531         size_t remaining = _capacity - _size;
 532         if (len > remaining) {
 533             size_t overflow = len - remaining;
 534             _head += overflow;
 535             len -= overflow;
 536         }
 537         _size += len;
 538     }
 539
 540     /**
 541      * Is the queue empty?
 542      *
 543      * @ingroup api_base_utils
 544      */
 545     bool empty() const { return _size == 0; }
 546
 547     /**
 548      * Is the queue full?
 549      * A queue is full if the head is the 0^{th} element and the tail is
 550      * the (size-1)^{th} element, or if the head is the n^{th} element and
 551      * the tail the (n-1)^{th} element.
 552      *
 553      * @ingroup api_base_utils
 554      */
 555     bool full() const { return _size == _capacity; }
 556
 557     /**
 558      * Iterators.
 559      *
 560      * @ingroup api_base_utils
 561      */
 562     iterator begin() { return iterator(this, _head); }
 563
 564     /* TODO: This should return a const_iterator. */
 565     /**
 566      * @ingroup api_base_utils
 567      */
 568     iterator
 569     begin() const
 570     {
 571         return iterator(const_cast<CircularQueue*>(this), _head);
 572     }
 573
 574     /**
 575      * @ingroup api_base_utils
 576      */
 577     iterator end() { return iterator(this, tail() + 1); }
 578
 579     /**
 580      * @ingroup api_base_utils
 581      */
 582     iterator
 583     end() const
 584     {
 585         return iterator(const_cast<CircularQueue*>(this), tail() + 1);
 586     }
 587
 588     /** Return an iterator to an index in the queue. */
 589     iterator getIterator(size_t idx) { return iterator(this, idx); }
 590 };
 591
 592 #endif /* __BASE_CIRCULARQUEUE_HH__ */