inline_var_len_entry_queue.h

Go to the documentation of this file.

// Copyright 2023 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
 
#ifdef __cplusplus
 
#include <cstddef>
#include <cstdint>
 
#include "pw_toolchain/constexpr_tag.h"
 
#else
 
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
 
#endif  // __cplusplus
 
#include "pw_preprocessor/util.h"
#include "pw_varint/varint.h"
 
 
#ifdef __cplusplus
extern "C" {
#endif  // __cplusplus
 
 
typedef uint32_t* pw_InlineVarLenEntryQueue_Handle;
typedef const uint32_t* pw_InlineVarLenEntryQueue_ConstHandle;
 
#define PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(variable, max_size_bytes) \
  uint32_t variable[PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 +  \
                    _PW_VAR_QUEUE_DATA_SIZE_UINT32(max_size_bytes)] = {  \
      _PW_VAR_QUEUE_DATA_SIZE_BYTES(max_size_bytes), /*head=*/0u, /*tail=*/0u}
 
#define PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 (3)
 
static inline void pw_InlineVarLenEntryQueue_Init(uint32_t array[],
                                                  size_t array_size_uint32);
 
static inline void pw_InlineVarLenEntryQueue_Clear(
    pw_InlineVarLenEntryQueue_Handle queue);
 
void pw_InlineVarLenEntryQueue_Push(pw_InlineVarLenEntryQueue_Handle queue,
                                    const void* data,
                                    uint32_t data_size_bytes);
 
bool pw_InlineVarLenEntryQueue_TryPush(pw_InlineVarLenEntryQueue_Handle queue,
                                       const void* data,
                                       const uint32_t data_size_bytes);
 
void pw_InlineVarLenEntryQueue_PushOverwrite(
    pw_InlineVarLenEntryQueue_Handle queue,
    const void* data,
    uint32_t data_size_bytes);
 
void pw_InlineVarLenEntryQueue_Pop(pw_InlineVarLenEntryQueue_Handle queue);
 
typedef struct {
  // Private: do not access these fields directly!
  pw_InlineVarLenEntryQueue_ConstHandle _pw_queue;
  uint32_t _pw_offset;
} pw_InlineVarLenEntryQueue_Iterator;
 
typedef struct {
  const uint8_t* data_1;
  uint32_t size_1;
  const uint8_t* data_2;
  uint32_t size_2;
} pw_InlineVarLenEntryQueue_Entry;
 
static inline pw_InlineVarLenEntryQueue_Iterator
pw_InlineVarLenEntryQueue_Begin(pw_InlineVarLenEntryQueue_ConstHandle queue);
 
static inline pw_InlineVarLenEntryQueue_Iterator pw_InlineVarLenEntryQueue_End(
    pw_InlineVarLenEntryQueue_ConstHandle queue);
 
void pw_InlineVarLenEntryQueue_Iterator_Advance(
    pw_InlineVarLenEntryQueue_Iterator* iterator);
 
static inline bool pw_InlineVarLenEntryQueue_Iterator_Equal(
    const pw_InlineVarLenEntryQueue_Iterator* lhs,
    const pw_InlineVarLenEntryQueue_Iterator* rhs);
 
pw_InlineVarLenEntryQueue_Entry pw_InlineVarLenEntryQueue_GetEntry(
    const pw_InlineVarLenEntryQueue_Iterator* iterator);
 
uint32_t pw_InlineVarLenEntryQueue_Entry_Copy(
    const pw_InlineVarLenEntryQueue_Entry* entry, void* dest, uint32_t count);
 
static inline uint8_t pw_InlineVarLenEntryQueue_Entry_At(
    const pw_InlineVarLenEntryQueue_Entry* entry, size_t index);
 
uint32_t pw_InlineVarLenEntryQueue_Size(
    pw_InlineVarLenEntryQueue_ConstHandle queue);
 
static inline uint32_t pw_InlineVarLenEntryQueue_MaxSize(
    pw_InlineVarLenEntryQueue_ConstHandle queue);
 
uint32_t pw_InlineVarLenEntryQueue_SizeBytes(
    pw_InlineVarLenEntryQueue_ConstHandle queue);
 
static inline uint32_t pw_InlineVarLenEntryQueue_MaxSizeBytes(
    pw_InlineVarLenEntryQueue_ConstHandle queue);
 
static inline uint32_t pw_InlineVarLenEntryQueue_RawStorageSizeBytes(
    pw_InlineVarLenEntryQueue_ConstHandle queue);
 
static inline bool pw_InlineVarLenEntryQueue_Empty(
    pw_InlineVarLenEntryQueue_ConstHandle queue);
 
 
// Implementation details.
 
#define _PW_VAR_QUEUE_DATA_SIZE_UINT32(max_size_bytes) \
  ((_PW_VAR_QUEUE_DATA_SIZE_BYTES(max_size_bytes) + 3 /* round up */) / 4)
 
#define _PW_VAR_QUEUE_DATA_SIZE_BYTES(max_size_bytes)              \
  (PW_VARINT_ENCODED_SIZE_BYTES(max_size_bytes) + max_size_bytes + \
   1 /*end byte*/)
 
#define _PW_VAR_QUEUE_ARRAY_SIZE_BYTES queue[0]
#define _PW_VAR_QUEUE_HEAD queue[1]
#define _PW_VAR_QUEUE_TAIL queue[2]  // points after the last byte
#define _PW_VAR_QUEUE_DATA ((const uint8_t*)&queue[3])
 
static inline void pw_InlineVarLenEntryQueue_Init(uint32_t array[],
                                                  size_t array_size_uint32) {
  array[0] = (uint32_t)(array_size_uint32 -
                        PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32) *
             sizeof(uint32_t);
  array[1] = 0;  // head
  array[2] = 0;  // tail
}
 
static inline void pw_InlineVarLenEntryQueue_Clear(
    pw_InlineVarLenEntryQueue_Handle queue) {
  _PW_VAR_QUEUE_HEAD = 0;  // head
  _PW_VAR_QUEUE_TAIL = 0;  // tail
}
 
static inline pw_InlineVarLenEntryQueue_Iterator
pw_InlineVarLenEntryQueue_Begin(pw_InlineVarLenEntryQueue_ConstHandle queue) {
  pw_InlineVarLenEntryQueue_Iterator begin = {queue, _PW_VAR_QUEUE_HEAD};
  return begin;
}
 
static inline pw_InlineVarLenEntryQueue_Iterator pw_InlineVarLenEntryQueue_End(
    pw_InlineVarLenEntryQueue_ConstHandle queue) {
  pw_InlineVarLenEntryQueue_Iterator end = {queue, _PW_VAR_QUEUE_TAIL};
  return end;
}
 
static inline bool pw_InlineVarLenEntryQueue_Iterator_Equal(
    const pw_InlineVarLenEntryQueue_Iterator* lhs,
    const pw_InlineVarLenEntryQueue_Iterator* rhs) {
  return lhs->_pw_offset == rhs->_pw_offset && lhs->_pw_queue == rhs->_pw_queue;
}
 
// Private function that returns a pointer to the specified index in the Entry.
static inline const uint8_t* _pw_InlineVarLenEntryQueue_Entry_GetPointer(
    const pw_InlineVarLenEntryQueue_Entry* entry, size_t index) {
  if (index < entry->size_1) {
    return &entry->data_1[index];
  }
  return &entry->data_2[index - entry->size_1];
}
 
const uint8_t* _pw_InlineVarLenEntryQueue_Entry_GetPointerChecked(
    const pw_InlineVarLenEntryQueue_Entry* entry, size_t index);
 
static inline uint8_t pw_InlineVarLenEntryQueue_Entry_At(
    const pw_InlineVarLenEntryQueue_Entry* entry, size_t index) {
  return *_pw_InlineVarLenEntryQueue_Entry_GetPointerChecked(entry, index);
}
 
static inline uint32_t pw_InlineVarLenEntryQueue_RawStorageSizeBytes(
    pw_InlineVarLenEntryQueue_ConstHandle queue) {
  return PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 * sizeof(uint32_t) +
         _PW_VAR_QUEUE_ARRAY_SIZE_BYTES;
}
 
static inline uint32_t pw_InlineVarLenEntryQueue_MaxSize(
    pw_InlineVarLenEntryQueue_ConstHandle queue) {
  return _PW_VAR_QUEUE_ARRAY_SIZE_BYTES - 1;
}
 
static inline uint32_t pw_InlineVarLenEntryQueue_MaxSizeBytes(
    pw_InlineVarLenEntryQueue_ConstHandle queue) {
  return _PW_VAR_QUEUE_ARRAY_SIZE_BYTES - 1 -
         (uint32_t)pw_varint_EncodedSizeBytes(_PW_VAR_QUEUE_ARRAY_SIZE_BYTES -
                                              1);
}
 
static inline bool pw_InlineVarLenEntryQueue_Empty(
    pw_InlineVarLenEntryQueue_ConstHandle queue) {
  return _PW_VAR_QUEUE_HEAD == _PW_VAR_QUEUE_TAIL;
}
 
// These macros are not part of the public API, so undefine them.
#undef _PW_VAR_QUEUE_ARRAY_SIZE_BYTES
#undef _PW_VAR_QUEUE_HEAD
#undef _PW_VAR_QUEUE_TAIL
#undef _PW_VAR_QUEUE_DATA
 
#ifdef __cplusplus
}  // extern "C"
 
#include <cstddef>
#include <limits>
#include <type_traits>
#include <utility>
 
#include "pw_containers/internal/raw_storage.h"
#include "pw_span/span.h"
 
namespace pw {
 
// A`BasicInlineVarLenEntryQueue` with a known maximum size of a single entry.
// The member functions are immplemented in the generic-capacity base.
// TODO: b/303056683 - Add helper for calculating kMaxSizeBytes for N entries of
//     a particular size.
template <typename T,
          size_t kMaxSizeBytes = containers::internal::kGenericSized>
class BasicInlineVarLenEntryQueue
    : public BasicInlineVarLenEntryQueue<T,
                                         containers::internal::kGenericSized> {
 private:
  using Base =
      BasicInlineVarLenEntryQueue<T, containers::internal::kGenericSized>;
 
 public:
  BasicInlineVarLenEntryQueue() : Base(kMaxSizeBytes) {}
 
  // Explicit zero element constexpr constructor. Using this constructor will
  // place the entire object in .data, which will increase ROM size. Use with
  // caution if working with large capacity sizes.
  constexpr BasicInlineVarLenEntryQueue(ConstexprTag)
      : Base(kMaxSizeBytes), data_{} {}
 
  // `BasicInlineVarLenEntryQueue` is trivially copyable.
  BasicInlineVarLenEntryQueue(const BasicInlineVarLenEntryQueue&) = default;
  BasicInlineVarLenEntryQueue& operator=(const BasicInlineVarLenEntryQueue&) =
      default;
 
 private:
  static_assert(kMaxSizeBytes <=
                std::numeric_limits<typename Base::size_type>::max());
 
  using Base::Init;  // Disallow Init since the size template param is not used.
 
  uint32_t data_[_PW_VAR_QUEUE_DATA_SIZE_UINT32(kMaxSizeBytes)];
};
 
 
template <typename T>
class BasicInlineVarLenEntryQueue<T, containers::internal::kGenericSized> {
 public:
  class Entry;
 
  using value_type = Entry;
  using size_type = std::uint32_t;
  using pointer = const value_type*;
  using const_pointer = pointer;
  using reference = const value_type&;
  using const_reference = reference;
 
  // Refers to an entry in-place in the queue. Entries may not be contiguous.
  class iterator;
 
  // Currently, iterators provide read-only access.
  // TODO: b/303046109 - Provide a non-const iterator.
  using const_iterator = iterator;
 
  template <size_t kArraySize>
  static BasicInlineVarLenEntryQueue& Init(uint32_t (&array)[kArraySize]) {
    static_assert(
        kArraySize > PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32,
        "InlineVarLenEntryQueue must be backed by an array with more than "
        "PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 (3) elements");
    return Init(array, kArraySize);
  }
 
  static BasicInlineVarLenEntryQueue& Init(uint32_t array[],
                                           size_t array_size_uint32) {
    pw_InlineVarLenEntryQueue_Init(array, array_size_uint32);
    return *std::launder(reinterpret_cast<BasicInlineVarLenEntryQueue*>(array));
  }
 
  Entry front() const { return *begin(); }
 
  const_iterator begin() const {
    return const_iterator(pw_InlineVarLenEntryQueue_Begin(array_));
  }
  const_iterator cbegin() const { return begin(); }
 
  const_iterator end() const {
    return const_iterator(pw_InlineVarLenEntryQueue_End(array_));
  }
  const_iterator cend() const { return end(); }
 
  [[nodiscard]] bool empty() const {
    return pw_InlineVarLenEntryQueue_Empty(array_);
  }
 
  size_type size() const { return pw_InlineVarLenEntryQueue_Size(array_); }
 
  size_type max_size() const {
    return pw_InlineVarLenEntryQueue_MaxSize(array_);
  }
 
  size_type size_bytes() const {
    return pw_InlineVarLenEntryQueue_SizeBytes(array_);
  }
 
  size_type max_size_bytes() const {
    return pw_InlineVarLenEntryQueue_MaxSizeBytes(array_);
  }
 
  span<const T> raw_storage() const {
    return span<const T>(reinterpret_cast<const T*>(array_),
                         pw_InlineVarLenEntryQueue_RawStorageSizeBytes(array_));
  }
 
  void clear() { pw_InlineVarLenEntryQueue_Clear(array_); }
 
  void push(span<const T> value) {
    pw_InlineVarLenEntryQueue_Push(
        array_, value.data(), static_cast<size_type>(value.size()));
  }
 
  [[nodiscard]] bool try_push(span<const T> value) {
    return pw_InlineVarLenEntryQueue_TryPush(
        array_, value.data(), static_cast<size_type>(value.size()));
  }
 
  void push_overwrite(span<const T> value) {
    pw_InlineVarLenEntryQueue_PushOverwrite(
        array_, value.data(), static_cast<size_type>(value.size()));
  }
 
  void pop() { pw_InlineVarLenEntryQueue_Pop(array_); }
 
 protected:
  constexpr BasicInlineVarLenEntryQueue(uint32_t max_size_bytes)
      : array_{_PW_VAR_QUEUE_DATA_SIZE_BYTES(max_size_bytes), 0, 0} {}
 
  // Polymorphic-sized queues cannot be destroyed directly due to the lack of a
  // virtual destructor.
  ~BasicInlineVarLenEntryQueue() = default;
 
  BasicInlineVarLenEntryQueue(const BasicInlineVarLenEntryQueue&) = default;
  BasicInlineVarLenEntryQueue& operator=(const BasicInlineVarLenEntryQueue&) =
      default;
 
 private:
  static_assert(std::is_integral_v<T> || std::is_same_v<T, std::byte>);
  static_assert(sizeof(T) == sizeof(std::byte));
 
  uint32_t array_[PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32];
};
 
template <typename T>
class BasicInlineVarLenEntryQueue<T>::Entry {
 public:
  using value_type = T;
  using size_type = std::uint32_t;
  using pointer = const T*;
  using const_pointer = pointer;
  using reference = const T&;
  using const_reference = reference;
 
  class iterator {
   public:
    using difference_type = std::ptrdiff_t;
    using value_type = T;
    using pointer = const T*;
    using reference = const T&;
    using iterator_category = std::forward_iterator_tag;
 
    constexpr iterator() : entry_(nullptr), index_(0) {}
 
    constexpr iterator(const iterator&) = default;
    constexpr iterator& operator=(const iterator&) = default;
 
    constexpr iterator& operator++() {
      index_ += 1;
      return *this;
    }
    constexpr iterator operator++(int) {
      iterator previous_value(*this);
      operator++();
      return previous_value;
    }
 
    reference operator*() const { return *GetIndex(*entry_, index_); }
    pointer operator->() const { return GetIndex(*entry_, index_); }
 
    bool operator==(const iterator& rhs) const {
      return entry_->data_1 == rhs.entry_->data_1 && index_ == rhs.index_;
    }
    bool operator!=(const iterator& rhs) const { return !(*this == rhs); }
 
   private:
    friend class Entry;
 
    constexpr iterator(const pw_InlineVarLenEntryQueue_Entry& entry,
                       size_t index)
        : entry_(&entry), index_(index) {}
 
    const pw_InlineVarLenEntryQueue_Entry* entry_;
    size_t index_;
  };
 
  // TODO: b/303046109 - Provide mutable access to Entry contents.
  using const_iterator = iterator;
 
  constexpr Entry(const Entry&) = default;
  constexpr Entry& operator=(const Entry&) = default;
 
  const_reference at(size_t index) const {
    return *reinterpret_cast<const T*>(
        _pw_InlineVarLenEntryQueue_Entry_GetPointerChecked(&entry_, index));
  }
 
  const_reference operator[](size_t index) const {
    return *GetIndex(entry_, index);
  }
 
  const_reference front() const { return *entry_.data_1; }
  const_reference back() const { *GetIndex(entry_, size() - 1); }
 
  std::pair<span<const value_type>, span<const value_type>> contiguous_data()
      const {
    return std::make_pair(
        span(reinterpret_cast<const_pointer>(entry_.data_1), entry_.size_1),
        span(reinterpret_cast<const_pointer>(entry_.data_2), entry_.size_2));
  }
 
  size_type copy(T* dest, size_type count) const {
    return pw_InlineVarLenEntryQueue_Entry_Copy(&entry_, dest, count);
  }
 
  const_iterator begin() const { return const_iterator(entry_, 0); }
  const_iterator cbegin() const { return begin(); }
 
  const_iterator end() const { return const_iterator(entry_, size()); }
  const_iterator cend() const { return cend(); }
 
  [[nodiscard]] bool empty() const { return size() == 0; }
 
  size_type size() const { return entry_.size_1 + entry_.size_2; }
 
 private:
  friend class BasicInlineVarLenEntryQueue;
 
  static const T* GetIndex(const pw_InlineVarLenEntryQueue_Entry& entry,
                           size_t index) {
    return reinterpret_cast<const T*>(
        _pw_InlineVarLenEntryQueue_Entry_GetPointer(&entry, index));
  }
 
  explicit constexpr Entry(const pw_InlineVarLenEntryQueue_Entry& entry)
      : entry_(entry) {}
 
  constexpr Entry() : entry_{} {}
 
  pw_InlineVarLenEntryQueue_Entry entry_;
};
 
template <typename T>
class BasicInlineVarLenEntryQueue<T>::iterator {
 public:
  using difference_type = std::ptrdiff_t;
  using value_type = Entry;
  using pointer = const Entry*;
  using reference = const Entry&;
  using iterator_category = std::forward_iterator_tag;
 
  constexpr iterator() : iterator_{}, entry_{} {}
 
  constexpr iterator(const iterator&) = default;
  constexpr iterator& operator=(const iterator&) = default;
 
  iterator& operator++() {
    pw_InlineVarLenEntryQueue_Iterator_Advance(&iterator_);
    entry_.entry_.data_1 = nullptr;  // mark the entry as unloaded
    return *this;
  }
  iterator operator++(int) {
    iterator previous_value(*this);
    operator++();
    return previous_value;
  }
 
  reference operator*() const {
    LoadEntry();
    return entry_;
  }
  pointer operator->() const {
    LoadEntry();
    return &entry_;
  }
 
  bool operator==(const iterator& rhs) const {
    return pw_InlineVarLenEntryQueue_Iterator_Equal(&iterator_, &rhs.iterator_);
  }
  bool operator!=(const iterator& rhs) const { return !(*this == rhs); }
 
 private:
  friend class BasicInlineVarLenEntryQueue;
 
  explicit constexpr iterator(const pw_InlineVarLenEntryQueue_Iterator& it)
      : iterator_(it) {}
 
  void LoadEntry() const {
    if (entry_.entry_.data_1 == nullptr) {
      entry_.entry_ = pw_InlineVarLenEntryQueue_GetEntry(&iterator_);
    }
  }
 
  pw_InlineVarLenEntryQueue_Iterator iterator_;
  mutable Entry entry_;
};
 
template <size_t kMaxSizeBytes = containers::internal::kGenericSized>
using InlineVarLenEntryQueue =
    BasicInlineVarLenEntryQueue<std::byte, kMaxSizeBytes>;
 
 
}  // namespace pw
 
#endif  // __cplusplus