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
 
// TODO: https://pwbug.dev/426012010 - Find a way to single-source this
// content on the Sphinx site without Breathe.
 
 
#include "pw_containers/internal/generic_var_len_entry_queue.h"
#include "pw_containers/internal/var_len_entry_queue_iterator.h"
#include "pw_preprocessor/util.h"
 
#ifndef __cplusplus
 
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
 
#else  // __cplusplus
 
#include <cstddef>
#include <cstdint>
 
#include "pw_bytes/span.h"
#include "pw_containers/internal/raw_storage.h"
#include "pw_span/span.h"
#include "pw_toolchain/constexpr_tag.h"
 
#endif  // __cplusplus
 
 
#define PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 (3)
 
#define _PW_VAR_QUEUE_SIZE_UINT32(max_size_bytes)      \
  (PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 + \
   ((PW_VAR_QUEUE_DATA_SIZE_BYTES(max_size_bytes) + 3 /* round up */) / 4))
 
#ifdef __cplusplus
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
    // TODO: b/513051956 - Fix `recursive class relation` error
    : public BasicInlineVarLenEntryQueue<T, containers::internal::kGenericSized>
{
 private:
  using Base =
      BasicInlineVarLenEntryQueue<T, containers::internal::kGenericSized>;
 
 public:
  using value_type = typename Base::value_type;
  using const_value_type = typename Base::const_value_type;
  using size_type = typename Base::size_type;
  using pointer = typename Base::pointer;
  using const_pointer = typename Base::const_pointer;
  using reference = typename Base::reference;
  using const_reference = typename Base::const_reference;
 
  BasicInlineVarLenEntryQueue()
      : array_{PW_VAR_QUEUE_DATA_SIZE_BYTES(kMaxSizeBytes), 0, 0} {}
 
  // 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)
      : array_{PW_VAR_QUEUE_DATA_SIZE_BYTES(kMaxSizeBytes), 0, 0} {}
 
  BasicInlineVarLenEntryQueue(const BasicInlineVarLenEntryQueue<T>& other) {
    *this = other;
  }
  BasicInlineVarLenEntryQueue(BasicInlineVarLenEntryQueue<T>&& other) {
    *this = std::move(other);
  }
  BasicInlineVarLenEntryQueue& operator=(
      const BasicInlineVarLenEntryQueue<T>& other);
  BasicInlineVarLenEntryQueue& operator=(
      BasicInlineVarLenEntryQueue<T>&& other);
 
 private:
  template <typename, size_t>
  friend class BasicInlineVarLenEntryQueue;
 
  constexpr span<uint32_t> array() { return array_; }
  constexpr span<const uint32_t> array() const { return array_; }
 
  // This class does not derive from RawStorage in order to allow this array to
  // be initialized as a constant expression.
  std::array<uint32_t, _PW_VAR_QUEUE_SIZE_UINT32(kMaxSizeBytes)> array_;
};
 
 
 
template <typename T>
class BasicInlineVarLenEntryQueue<T, containers::internal::kGenericSized>
    : public containers::internal::GenericVarLenEntryQueue<
          BasicInlineVarLenEntryQueue<T, containers::internal::kGenericSized>,
          T> {
 private:
  using Base = containers::internal::GenericVarLenEntryQueue<
      BasicInlineVarLenEntryQueue<T, containers::internal::kGenericSized>,
      T>;
 
 public:
  using value_type = containers::internal::VarLenEntry<T>;
  using const_value_type = containers::internal::VarLenEntry<const T>;
  using size_type = std::uint32_t;
  using pointer = const value_type*;
  using const_pointer = pointer;
  using reference = const value_type&;
  using const_reference = reference;
 
  template <size_t kArraySize>
  static BasicInlineVarLenEntryQueue& Init(uint32_t (&array)[kArraySize]);
  static BasicInlineVarLenEntryQueue& Init(uint32_t array[],
                                           size_t array_size_uint32);
 
  span<const T> raw_storage() const;
 
 protected:
  constexpr BasicInlineVarLenEntryQueue() = default;
  ~BasicInlineVarLenEntryQueue() = default;
 
 private:
  static constexpr size_t kNumFields = 3;
  static constexpr size_t kBufferSize = 0;
  static constexpr size_t kHead = 1;
  static constexpr size_t kTail = 2;
 
  // GenericVarLenEntryQueue uses CRTP to encapsulate
  template <typename, typename>
  friend class containers::internal::GenericVarLenEntryQueue;
 
  size_t buffer_size() const { return array()[kBufferSize]; }
 
  size_t head() const { return array()[kHead]; }
  void set_head(size_t head) { array()[kHead] = static_cast<uint32_t>(head); }
 
  size_t tail() const { return array()[kTail]; }
  void set_tail(size_t tail) { array()[kTail] = static_cast<uint32_t>(tail); }
 
  span<T> buffer() {
    return span<T>(reinterpret_cast<T*>(array().subspan(kNumFields).data()),
                   buffer_size());
  }
 
  span<const T> buffer() const {
    return span<const T>(
        reinterpret_cast<const T*>(array().subspan(kNumFields).data()),
        buffer_size());
  }
 
  // The underlying data is not part of the generic-length queue class. It is
  // provided in the derived class from which this instance was constructed. To
  // access the data, downcast this to a BasicInlineVarLenEntryQueue with a
  // known max size, and return a pointer to the start of the array, which is
  // the same for all queues with explicit max size.
  span<uint32_t> array() {
    return static_cast<BasicInlineVarLenEntryQueue<T, 0>*>(this)->array();
  }
  span<const uint32_t> array() const {
    return static_cast<const BasicInlineVarLenEntryQueue<T, 0>*>(this)->array();
  }
};
 
template <size_t kMaxSizeBytes = containers::internal::kGenericSized>
using InlineVarLenEntryQueue =
    BasicInlineVarLenEntryQueue<std::byte, kMaxSizeBytes>;
 
// Template method implementation.
 
// BasicInlineVarLenEntryQueue<T, kMaxSizeBytes> methods.
 
template <typename T, size_t kMaxSizeBytes>
BasicInlineVarLenEntryQueue<T, kMaxSizeBytes>&
BasicInlineVarLenEntryQueue<T, kMaxSizeBytes>::operator=(
    const BasicInlineVarLenEntryQueue<T>& other) {
  PW_ASSERT(this->GetBufferSize() >= other.GetBufferSize());
  size_t array_size =
      (sizeof(uint32_t) *
       BasicInlineVarLenEntryQueue<T, kMaxSizeBytes>::kNumFields) +
      other.GetBufferSize();
  std::memcpy(this->array(), other.array(), array_size);
  return *this;
}
 
template <typename T, size_t kMaxSizeBytes>
BasicInlineVarLenEntryQueue<T, kMaxSizeBytes>&
BasicInlineVarLenEntryQueue<T, kMaxSizeBytes>::operator=(
    BasicInlineVarLenEntryQueue<T>&& other) {
  *this = other;
  other.clear();
  return *this;
}
 
// BasicInlineVarLenEntryQueue<T> methods.
 
template <typename T>
template <size_t kArraySize>
BasicInlineVarLenEntryQueue<T>& BasicInlineVarLenEntryQueue<T>::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);
}
 
template <typename T>
BasicInlineVarLenEntryQueue<T>& BasicInlineVarLenEntryQueue<T>::Init(
    uint32_t array[], size_t array_size_uint32) {
  auto array_size = static_cast<uint32_t>(array_size_uint32);
  array_size -= PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32;
  array[0] = array_size * sizeof(uint32_t);
  array[1] = 0;  // head
  array[2] = 0;  // tail
  return *(std::launder(reinterpret_cast<BasicInlineVarLenEntryQueue*>(array)));
}
 
template <typename T>
span<const T> BasicInlineVarLenEntryQueue<T>::raw_storage() const {
  size_t raw_size = (kNumFields * sizeof(uint32_t)) + buffer_size();
  return span<const T>(reinterpret_cast<const T*>(array().data()), raw_size);
}
 
}  // namespace pw
 
#define _PW_VAR_QUEUE_CHECK_SIZE(max_size_bytes)                      \
  static_assert(sizeof(pw::InlineVarLenEntryQueue<max_size_bytes>) == \
                _PW_VAR_QUEUE_SIZE_UINT32(max_size_bytes) * sizeof(uint32_t));
 
#else  // !defined(__cplusplus)
 
#define _PW_VAR_QUEUE_CHECK_SIZE(max_size_bytes)
 
#endif  // __cplusplus
 
PW_EXTERN_C_START
 
 
#define PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(variable, max_size_bytes) \
  _PW_VAR_QUEUE_CHECK_SIZE(max_size_bytes)                               \
  uint32_t variable[_PW_VAR_QUEUE_SIZE_UINT32(max_size_bytes)] = {       \
      PW_VAR_QUEUE_DATA_SIZE_BYTES(max_size_bytes), /*head=*/0u, /*tail=*/0u}
 
typedef uint32_t* pw_InlineVarLenEntryQueue_Handle;
typedef const uint32_t* pw_InlineVarLenEntryQueue_ConstHandle;
 
void pw_InlineVarLenEntryQueue_Init(uint32_t array[], size_t array_size_uint32);
 
pw_InlineVarLenEntryQueue_Iterator pw_InlineVarLenEntryQueue_Begin(
    pw_InlineVarLenEntryQueue_Handle queue);
 
pw_InlineVarLenEntryQueue_ConstIterator pw_InlineVarLenEntryQueue_ConstBegin(
    pw_InlineVarLenEntryQueue_ConstHandle queue);
 
pw_InlineVarLenEntryQueue_Iterator pw_InlineVarLenEntryQueue_End(
    pw_InlineVarLenEntryQueue_Handle queue);
 
pw_InlineVarLenEntryQueue_ConstIterator pw_InlineVarLenEntryQueue_ConstEnd(
    pw_InlineVarLenEntryQueue_ConstHandle queue);
 
bool pw_InlineVarLenEntryQueue_Empty(
    pw_InlineVarLenEntryQueue_ConstHandle queue);
 
uint32_t pw_InlineVarLenEntryQueue_Size(
    pw_InlineVarLenEntryQueue_ConstHandle queue);
 
uint32_t pw_InlineVarLenEntryQueue_MaxSize(
    pw_InlineVarLenEntryQueue_ConstHandle queue);
 
uint32_t pw_InlineVarLenEntryQueue_SizeBytes(
    pw_InlineVarLenEntryQueue_ConstHandle queue);
 
uint32_t pw_InlineVarLenEntryQueue_MaxSizeBytes(
    pw_InlineVarLenEntryQueue_ConstHandle 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);
 
void pw_InlineVarLenEntryQueue_Clear(pw_InlineVarLenEntryQueue_Handle queue);
 
uint32_t pw_InlineVarLenEntryQueue_RawStorageSizeBytes(
    pw_InlineVarLenEntryQueue_ConstHandle queue);
 
void pw_InlineVarLenEntryQueue_CopyEntries(
    pw_InlineVarLenEntryQueue_ConstHandle from,
    pw_InlineVarLenEntryQueue_Handle to);
 
void pw_InlineVarLenEntryQueue_CopyEntriesOverwrite(
    pw_InlineVarLenEntryQueue_ConstHandle from,
    pw_InlineVarLenEntryQueue_Handle to);
 
void pw_InlineVarLenEntryQueue_MoveEntries(
    pw_InlineVarLenEntryQueue_Handle from, pw_InlineVarLenEntryQueue_Handle to);
 
void pw_InlineVarLenEntryQueue_MoveEntriesOverwrite(
    pw_InlineVarLenEntryQueue_Handle from, pw_InlineVarLenEntryQueue_Handle to);
 
 
PW_EXTERN_C_END