util/ring_buffer.hpp

   1 /*
   2  * Copyright (c) 2021 Arm Limited.
   3  *
   4  * SPDX-License-Identifier: MIT
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a copy
   7  * of this software and associated documentation files (the "Software"), to
   8  * deal in the Software without restriction, including without limitation the
   9  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  10  * sell copies of the Software, and to permit persons to whom the Software is
  11  * furnished to do so, subject to the following conditions:
  12  *
  13  * The above copyright notice and this permission notice shall be included in all
  14  * copies or substantial portions of the Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22  * SOFTWARE.
  23  */
  24
  25 #include <memory>
  26 #include <array>
  27
  28 #include "optional.hpp"
  29
  30 namespace util
  31 {
  32
  33 template <typename T, std::size_t N>
  34 class ring_buffer
  35 {
  36 public:
  37    /**
  38     * @brief Return maximum capacity of the ring buffer.
  39     */
  40    constexpr std::size_t capacity()
  41    {
  42       return N;
  43    }
  44
  45    /**
  46     * @brief Return current size of the ring buffer.
  47     */
  48    std::size_t size() const
  49    {
  50       return m_size;
  51    }
  52
  53    /**
  54     * @brief Places item into next slot of the ring buffer.
  55     * @return Boolean to indicate success or failure.
  56     */
  57    template <typename U>
  58    bool push_back(U &&item)
  59    {
  60       if (size() == capacity())
  61       {
  62          return false;
  63       }
  64
  65       m_data[(m_begin + m_size) % N].set(std::forward<U>(item));
  66       ++m_size;
  67
  68       return true;
  69    }
  70
  71    /**
  72     * @brief Gets a pointer to the item at the starting index of the ring buffer.
  73     */
  74    T *front()
  75    {
  76       return get(m_begin);
  77    }
  78
  79    /**
  80     * @brief Gets a pointer to the item that was last placed into the ring buffer.
  81     */
  82    T *back()
  83    {
  84       return get((m_begin + m_size + N - 1) % N);
  85    }
  86
  87    /**
  88     * @brief Pop the front of the ring buffer.
  89     *
  90     * Item at the starting index of the ring buffer is returned. The slot is subsequently emptied. The starting index of
  91     * the ring buffer increments by 1.
  92     *
  93     * @return Item wrapped in an optional.
  94     */
  95    util::optional<T> pop_front()
  96    {
  97       if (size() == 0)
  98       {
  99          return util::optional<T>{};
 100       }
 101
 102       util::optional<T> value = std::move(m_data[m_begin]);
 103
 104       m_begin = (m_begin + 1) % N;
 105       --m_size;
 106
 107       return value;
 108    }
 109
 110 private:
 111    T *get(std::size_t index)
 112    {
 113       if (m_data[index].has_value())
 114       {
 115          return std::addressof(m_data[index].value());
 116       }
 117       else
 118       {
 119          return nullptr;
 120       }
 121    }
 122
 123    std::array<util::optional<T>, N> m_data{};
 124
 125    // Marks the start index of the ring buffer.
 126    std::size_t m_begin{};
 127
 128    // The number of entries in the ring buffer from the start index.
 129    std::size_t m_size{};
 130 };
 131
 132 } /* namespace util */