text: // Copyright 2020 The Pigweed Authors
  //
  // Licensed under the Apache License, Version 2.0 (the "License"); you may not
  // use this file except in compliance with the License. You may obtain a copy of
  // the License at
  //
  //     https://www.apache.org/licenses/LICENSE-2.0
  //
  // Unless required by applicable law or agreed to in writing, software
  // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  // License for the specific language governing permissions and limitations under
  // the License.
  #pragma once
  
  #include <cstddef>
  #include <span>
  
  #include "pw_containers/intrusive_list.h"
  #include "pw_status/status.h"
  
  namespace pw {
  namespace ring_buffer {
  
  // A circular ring buffer for arbitrary length data entries. Each PushBack()
  // produces a buffer entry. Each entry consists of a preamble followed by an
  // arbitrary length data chunk. The preamble is comprised of an optional user
  // preamble byte and an always present varint. The varint encodes the number of
  // bytes in the data chunk. This is a FIFO queue, with the oldest entries at
  // the 'front' (to be processed by readers) and the newest entries at the 'back'
  // (where the writer pushes to).
  //
  // The ring buffer supports multiple readers, which can be attached/detached
  // from the buffer. Each reader has its own read pointer and can peek and pop
  // the entry at the head. Entries are not bumped out from the buffer until all
  // readers have moved past that entry, or if the buffer is at capacity and space
  // is needed to push a new entry. When making space, the buffer will push slow
  // readers forward to the new oldest entry. Entries are internally wrapped
  // around as needed.
  class PrefixedEntryRingBufferMulti {
   public:
    typedef Status (*ReadOutput)(std::span<const std::byte>);
  
    // A reader that provides a single-reader interface into the multi-reader ring
    // buffer it has been attached to via AttachReader(). Readers maintain their
    // read position in the ring buffer as well as the remaining count of entries
    // from that position. Readers are only able to consume entries that were
    // pushed after the attach operation.
    //
    // Readers can peek and pop entries similar to the single-reader interface.
    // When popping entries, although the reader moves forward and drops the
    // entry, the entry is not removed from the ring buffer until all other
    // attached readers have moved past that entry.
    //
    // When the attached ring buffer needs to make space, it may push the reader
    // index forward. Users of this class should consider the possibility of data
    // loss if they read slower than the writer.
    class Reader : public IntrusiveList<Reader>::Item {
     public:
      constexpr Reader() : buffer(nullptr), read_idx(0), entry_count(0) {}
  
      // TODO(pwbug/344): Add locking to the internal functions. Who owns the
      // lock? This class? Does this class need a lock if it's not a multi-reader?
      // (One doesn't exist today but presumably nothing prevents push + pop
      // operations from happening on two different threads).
  
      // Read the oldest stored data chunk of data from the ring buffer to
      // the provided destination std::span. The number of bytes read is written
      // to bytes_read
      //
      // Return values:
      // OK - Data successfully read from the ring buffer.
      // FAILED_PRECONDITION - Buffer not initialized.
      // OUT_OF_RANGE - No entries in ring buffer to read.
      // RESOURCE_EXHAUSTED - Destination data std::span was smaller number of
      // bytes than the data size of the data chunk being read.  Available
      // destination bytes were filled, remaining bytes of the data chunk were
      // ignored.
      Status PeekFront(std::span<std::byte> data, size_t* bytes_read_out) {
        return buffer->InternalPeekFront(*this, data, bytes_read_out);
      }
  
      Status PeekFront(ReadOutput output) {
        return buffer->InternalPeekFront(*this, output);
      }
  
      // Same as PeekFront but includes the entry's preamble of optional user
      // value and the varint of the data size.
      // TODO(pwbug/341): Move all other APIs to passing bytes_read by reference,
      // as it is required to determine the length populated in the span.
      Status PeekFrontWithPreamble(std::span<std::byte> data,
                                   uint32_t& user_preamble_out,
                                   size_t& entry_bytes_read_out);
  
      Status PeekFrontWithPreamble(std::span<std::byte> data,
                                   size_t* bytes_read_out) {
        return buffer->InternalPeekFrontWithPreamble(*this, data, bytes_read_out);
      }
  
      Status PeekFrontWithPreamble(ReadOutput output) {
        return buffer->InternalPeekFrontWithPreamble(*this, output);
      }
  
      // Pop and discard the oldest stored data chunk of data from the ring
      // buffer.
      //
      // Return values:
      // OK - Data successfully read from the ring buffer.
      // FAILED_PRECONDITION - Buffer not initialized.
      // OUT_OF_RANGE - No entries in ring buffer to pop.
      Status PopFront() { return buffer->InternalPopFront(*this); }
  
      // Get the size in bytes of the next chunk, not including preamble, to be
      // read.
      size_t FrontEntryDataSizeBytes() {
        return buffer->InternalFrontEntryDataSizeBytes(*this);
      }
  
      // Get the size in bytes of the next chunk, including preamble and data
      // chunk, to be read.
      size_t FrontEntryTotalSizeBytes() {
        return buffer->InternalFrontEntryTotalSizeBytes(*this);
      }
  
      // Get the number of variable-length entries currently in the ring buffer.
      //
      // Return value:
      // Entry count.
      size_t EntryCount() { return entry_count; }
  
     protected:
      friend PrefixedEntryRingBufferMulti;
  
      PrefixedEntryRingBufferMulti* buffer;
      size_t read_idx;
      size_t entry_count;
    };
  
    // TODO(pwbug/340): Consider changing bool to an enum, to explicitly enumerate
    // what this variable means in clients.
    PrefixedEntryRingBufferMulti(bool user_preamble = false)
        : buffer_(nullptr),
          buffer_bytes_(0),
          write_idx_(0),
          user_preamble_(user_preamble) {}
  
    // Set the raw buffer to be used by the ring buffer.
    //
    // Return values:
    // OK - successfully set the raw buffer.
    // INVALID_ARGUMENT - Argument was nullptr, size zero, or too large.
    Status SetBuffer(std::span<std::byte> buffer);
  
    // Attach reader to the ring buffer. Readers can only be attached to one
    // ring buffer at a time.
    //
    // Return values:
    // OK - Successfully configured reader for ring buffer.
    // INVALID_ARGUMENT - Argument was already attached to another ring buffer.
    Status AttachReader(Reader& reader);
  
    // Detach reader from the ring buffer. Readers can only be detached if they
    // were previously attached.
    //
    // Return values:
    // OK - Successfully removed reader for ring buffer.
    // INVALID_ARGUMENT - Argument was not previously attached to this ring
    // buffer.
    Status DetachReader(Reader& reader);
  
    // Removes all data from the ring buffer.
    void Clear();
  
    // Write a chunk of data to the ring buffer. If available space is less than
    // size of data chunk to be written then silently pop and discard oldest
    // stored data chunks until space is available.
    //
    // Preamble argument is a caller-provided value prepended to the front of the
    // entry. It is only used if user_preamble was set at class construction
    // time. It is varint-encoded before insertion into the buffer.
    //
    // Return values:
    // OK - Data successfully written to the ring buffer.
    // INVALID_ARGUMENT - Size of data to write is zero bytes
    // FAILED_PRECONDITION - Buffer not initialized.
    // OUT_OF_RANGE - Size of data is greater than buffer size.
    Status PushBack(std::span<const std::byte> data,
                    uint32_t user_preamble_data = 0) {
      return InternalPushBack(data, user_preamble_data, true);
    }
  
    // [Deprecated] An implementation of PushBack that accepts a single-byte as
    // preamble data. Clients should migrate to passing uint32_t preamble data.
    Status PushBack(std::span<const std::byte> data,
                    std::byte user_preamble_data) {
      return PushBack(data, static_cast<uint32_t>(user_preamble_data));
    }
  
    // Write a chunk of data to the ring buffer if there is space available.
    //
    // Preamble argument is a caller-provided value prepended to the front of the
    // entry. It is only used if user_preamble was set at class construction
    // time. It is varint-encoded before insertion into the buffer.
    //
    // Return values:
    // OK - Data successfully written to the ring buffer.
    // INVALID_ARGUMENT - Size of data to write is zero bytes
    // FAILED_PRECONDITION - Buffer not initialized.
    // OUT_OF_RANGE - Size of data is greater than buffer size.
    // RESOURCE_EXHAUSTED - The ring buffer doesn't have space for the data
    // without popping off existing elements.
    Status TryPushBack(std::span<const std::byte> data,
                       uint32_t user_preamble_data = 0) {
      return InternalPushBack(data, user_preamble_data, false);
    }
  
    // [Deprecated] An implementation of TryPushBack that accepts a single-byte as
    // preamble data. Clients should migrate to passing uint32_t preamble data.
    Status TryPushBack(std::span<const std::byte> data,
                       std::byte user_preamble_data) {
      return TryPushBack(data, static_cast<uint32_t>(user_preamble_data));
    }
  
    // Get the size in bytes of all the current entries in the ring buffer,
    // including preamble and data chunk.
    size_t TotalUsedBytes() { return buffer_bytes_ - RawAvailableBytes(); }
  
    // Dering the buffer by reordering entries internally in the buffer by
    // rotating to have the oldest entry is at the lowest address/index with
    // newest entry at the highest address.
    //
    // Return values:
    // OK - Buffer data successfully deringed.
    // FAILED_PRECONDITION - Buffer not initialized, or no readers attached.
    Status Dering();
  
   protected:
    // Read the oldest stored data chunk of data from the ring buffer to
    // the provided destination std::span. The number of bytes read is written to
    // `bytes_read_out`.
    //
    // Return values:
    // OK - Data successfully read from the ring buffer.
    // FAILED_PRECONDITION - Buffer not initialized.
    // OUT_OF_RANGE - No entries in ring buffer to read.
    // RESOURCE_EXHAUSTED - Destination data std::span was smaller number of bytes
    // than the data size of the data chunk being read.  Available destination
    // bytes were filled, remaining bytes of the data chunk were ignored.
    Status InternalPeekFront(Reader& reader,
                             std::span<std::byte> data,
                             size_t* bytes_read_out);
    Status InternalPeekFront(Reader& reader, ReadOutput output);
  
    // Same as Read but includes the entry's preamble of optional user value and
    // the varint of the data size
    Status InternalPeekFrontWithPreamble(Reader& reader,
                                         std::span<std::byte> data,
                                         size_t* bytes_read_out);
    Status InternalPeekFrontWithPreamble(Reader& reader, ReadOutput output);
  
    // Pop and discard the oldest stored data chunk of data from the ring buffer.
    //
    // Return values:
    // OK - Data successfully read from the ring buffer.
    // FAILED_PRECONDITION - Buffer not initialized.
    // OUT_OF_RANGE - No entries in ring buffer to pop.
    Status InternalPopFront(Reader& reader);
  
    // Get the size in bytes of the next chunk, not including preamble, to be
    // read.
    size_t InternalFrontEntryDataSizeBytes(Reader& reader);
  
    // Get the size in bytes of the next chunk, including preamble and data
    // chunk, to be read.
    size_t InternalFrontEntryTotalSizeBytes(Reader& reader);
  
    // Internal version of Read used by all the public interface versions. T
    // should be of type ReadOutput.
    template <typename T>
    Status InternalRead(Reader& reader,
                        T read_output,
                        bool include_preamble_in_output,
                        uint32_t* user_preamble_out = nullptr);
  
   private:
    struct EntryInfo {
      size_t preamble_bytes;
      uint32_t user_preamble;
      size_t data_bytes;
    };
  
    // Push back implementation, which optionally discards front elements to fit
    // the incoming element.
    Status InternalPushBack(std::span<const std::byte> data,
                            uint32_t user_preamble_data,
                            bool pop_front_if_needed);
  
    // Internal function to pop all of the slowest readers. This function may pop
    // multiple readers if multiple are slow.
    //
    // Precondition: This function requires that at least one reader is attached
    // and has at least one entry to pop.
    void InternalPopFrontAll();
  
    // Returns the slowest reader in the list.
    //
    // Precondition: This function requires that at least one reader is attached.
    Reader& GetSlowestReader();
  
    // Get info struct with the size of the preamble and data chunk for the next
    // entry to be read.
    EntryInfo FrontEntryInfo(Reader& reader);
  
    // Get the raw number of available bytes free in the ring buffer. This is
    // not available bytes for data, since there is a variable size preamble for
    // each entry.
    size_t RawAvailableBytes();
  
    // Do the basic write of the specified number of bytes starting at the last
    // write index of the ring buffer to the destination, handing any wrap-around
    // of the ring buffer. This is basic, raw operation with no safety checks.
    void RawWrite(std::span<const std::byte> source);
  
    // Do the basic read of the specified number of bytes starting at the given
    // index of the ring buffer to the destination, handing any wrap-around of
    // the ring buffer. This is basic, raw operation with no safety checks.
    void RawRead(std::byte* destination, size_t source_idx, size_t length_bytes);
  
    size_t IncrementIndex(size_t index, size_t count);
  
    std::byte* buffer_;
    size_t buffer_bytes_;
  
    size_t write_idx_;
    const bool user_preamble_;
  
    // List of attached readers.
    IntrusiveList<Reader> readers_;
  
    // Maximum bufer size allowed. Restricted to this to allow index aliasing to
    // not overflow.
    static constexpr size_t kMaxBufferBytes =
        std::numeric_limits<size_t>::max() / 2;
  };
  
  class PrefixedEntryRingBuffer : public PrefixedEntryRingBufferMulti,
                                  public PrefixedEntryRingBufferMulti::Reader {
   public:
    PrefixedEntryRingBuffer(bool user_preamble = false)
        : PrefixedEntryRingBufferMulti(user_preamble) {
      AttachReader(*this);
    }
  };
  
  }  // namespace ring_buffer
  }  // namespace pw
  