src/Common/RingBuffer.h

   1 /* Copyright (C) 2006 - 2014 Jan Kundrát <jkt@flaska.net>
   2
   3    This file is part of the Trojita Qt IMAP e-mail client,
   4    http://trojita.flaska.net/
   5
   6    This program is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU General Public License as
   8    published by the Free Software Foundation; either version 2 of
   9    the License or (at your option) version 3 or any later version
  10    accepted by the membership of KDE e.V. (or its successor approved
  11    by the membership of KDE e.V.), which shall act as a proxy
  12    defined in Section 14 of version 3 of the license.
  13
  14    This program is distributed in the hope that it will be useful,
  15    but WITHOUT ANY WARRANTY; without even the implied warranty of
  16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17    GNU General Public License for more details.
  18
  19    You should have received a copy of the GNU General Public License
  20    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  21 */
  22 #ifndef TROJITA_RINGBUFFER_H
  23 #define TROJITA_RINGBUFFER_H
  24
  25 #include <QVector>
  26
  27 namespace Common
  28 {
  29
  30 /** @short Circular buffer holding a number of items
  31
  32 This class holds a fixed number of items. Use the append() function to put stuff into it. When you want to retrieve them,
  33 obtain an iterator by calling begin(). The returned iterator will cease to be valid immediately after modifying the ring
  34 buffer. Iteration has to be performed by comparing the current value of an iterator for equivalence against the
  35 container's end(), and incrementing the iterator. Any other form is not supported.
  36
  37 Invalidated iterators will likely not get caught.
  38 */
  39 template<typename T>
  40 class RingBuffer
  41 {
  42 public:
  43     /** @short Constat iterator fro visiting the items after each other, starting at the oldest one
  44
  45     The iterator itself is linear, ie. it won't wrap. It will however
  46     */
  47     class const_iterator
  48     {
  49         const RingBuffer<T> *container_;
  50         int offset_;
  51     public:
  52         /** @short Dereference the iterator */
  53         const T &operator*() const
  54         {
  55             // It has to point to a correct offset
  56             Q_ASSERT(offset_ >= 0 && offset_ < container_->buf_.size());
  57             int pos = container_->wrapped_ ?
  58                       // It got wrapped, so we have to get wrapped past the end, too, and start at the oldest one
  59                       (container_->appendPos_ + offset_) % container_->buf_.size() :
  60                       // It isn't full yet
  61                       offset_;
  62             return container_->buf_[pos];
  63         }
  64
  65         const T *operator->() const
  66         {
  67             return &operator*();
  68         }
  69
  70         /** @short Increment the iterator */
  71         const_iterator &operator++()
  72         {
  73             ++offset_;
  74             // Allow incrementing to the end, ie. one past the last item
  75             Q_ASSERT(offset_ <= container_->buf_.size());
  76             return *this;
  77         }
  78
  79         /** @short Compare two iterators from the same container for equality */
  80         bool operator==(const const_iterator &other) const
  81         {
  82             Q_ASSERT(container_ == other.container_);
  83             return offset_ == other.offset_;
  84         }
  85
  86         /** @short Compare two iterators from the same container for inqeuality */
  87         bool operator!=(const const_iterator &other) const
  88         {
  89             return !(*this == other);
  90         }
  91     private:
  92         friend class RingBuffer<T>;
  93         const_iterator(const RingBuffer<T> *container, int offset): container_(container), offset_(offset)
  94         {
  95         }
  96     };
  97
  98     /** @short Instantiate a ring buffer holding size elements */
  99     RingBuffer(const int size): buf_(size), appendPos_(0), wrapped_(false), skipped_(0)
 100     {
 101         Q_ASSERT(size >= 1);
 102     }
 103
 104     /** @short Return an interator pointing to the oldest item in the container */
 105     const_iterator begin() const
 106     {
 107         return const_iterator(this, 0);
 108     }
 109
 110     /** @short Return an interator pointing to one item past the recent addition */
 111     const_iterator end() const
 112     {
 113         return const_iterator(this, wrapped_ ?  buf_.size() : appendPos_);
 114     }
 115
 116     /** @short Append an item to the container. Oldest item could get overwritten. */
 117     void append(const T &what)
 118     {
 119         if (appendPos_ == buf_.size()) {
 120             wrapped_ = true;
 121             appendPos_ = 0;
 122         }
 123         if (wrapped_)
 124             ++skipped_;
 125         buf_[appendPos_] = what;
 126         ++appendPos_;
 127     }
 128
 129     /** @short Remove all items from the container */
 130     void clear()
 131     {
 132         buf_ = QVector<T>(buf_.size());
 133         wrapped_ = false;
 134         appendPos_ = 0;
 135         skipped_ = 0;
 136     }
 137
 138     /** @short How many items were overwritten */
 139     uint skippedCount() const
 140     {
 141         return skipped_;
 142     }
 143
 144 private:
 145     QVector<T> buf_;
 146     int appendPos_;
 147     bool wrapped_;
 148     uint skipped_;
 149 };
 150
 151 }
 152
 153 #endif // TROJITA_RINGBUFFER_H