queue.h

// Copyright 2025 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 <utility>
 
#include "pw_allocator/allocator.h"
#include "pw_allocator/unique_ptr.h"
#include "pw_containers/deque.h"
#include "pw_containers/internal/generic_queue.h"
#include "pw_containers/storage.h"
 
namespace pw {
 
 
template <typename T, typename SizeType = uint16_t>
class Queue : public containers::internal::GenericQueue<Queue<T, SizeType>,
                                                        Deque<T, SizeType>> {
 public:
  explicit constexpr Queue(span<std::byte> unaligned_buffer) noexcept
      : Queue(Aligned::Align(unaligned_buffer)) {}
 
  template <size_t kAlignment, size_t kSizeBytes>
  explicit constexpr Queue(
      containers::Storage<kAlignment, kSizeBytes>& storage) noexcept
      : deque_(storage) {}
 
  // Disable copy and move since the queue does not own the buffer.
  Queue(const Queue&) = delete;
  Queue& operator=(const Queue&) = delete;
 
  Queue(Queue&&) = delete;
  Queue& operator=(Queue&&) = delete;
 
 private:
  template <typename, typename>
  friend class containers::internal::GenericQueue;
 
  template <typename, size_t, typename>
  friend class FixedQueue;
 
  using Aligned = typename Deque<T, SizeType>::Aligned;
 
  // Constructor for a buffer that is known to be aligned.
  explicit constexpr Queue(Aligned buffer) noexcept : deque_(buffer) {}
 
  void MoveItemsFrom(Queue& other) { deque_.MoveItemsFrom(other.deque_); }
  void MoveBufferFrom(Queue& other) { deque_.MoveBufferFrom(other.deque_); }
  void SwapValuesWith(Queue& other) { deque_.SwapValuesWith(other.deque_); }
  void SwapBufferWith(Queue& other) { deque_.SwapBufferWith(other.deque_); }
 
  T* data() { return deque_.data(); }
 
  Deque<T, SizeType>& deque() { return deque_; }
  const Deque<T, SizeType>& deque() const { return deque_; }
 
  Deque<T, SizeType> deque_;
};
 
template <typename T,
          size_t kInlineCapacity = containers::kExternalStorage,
          typename SizeType = typename Queue<T>::size_type>
class FixedQueue final : private containers::StorageBaseFor<T, kInlineCapacity>,
                         public Queue<T, SizeType> {
 public:
  constexpr FixedQueue()
      : containers::StorageBaseFor<T, kInlineCapacity>{},
        Queue<T, SizeType>(this->storage()) {}
 
  FixedQueue(const FixedQueue&) = delete;
  FixedQueue& operator=(const FixedQueue&) = delete;
 
  constexpr FixedQueue(FixedQueue&& other) noexcept : FixedQueue() {
    this->MoveItemsFrom(other);
  }
 
  constexpr FixedQueue& operator=(FixedQueue&& other) noexcept {
    this->clear();
    this->MoveItemsFrom(other);
    return *this;
  }
 
  template <size_t kOtherCapacity,
            typename = std::enable_if_t<kOtherCapacity <= kInlineCapacity>>
  FixedQueue(FixedQueue<T, kOtherCapacity>&& other) noexcept : FixedQueue() {
    this->MoveItemsFrom(other);
  }
 
  template <size_t kOtherCapacity,
            typename = std::enable_if_t<kOtherCapacity <= kInlineCapacity>>
  FixedQueue& operator=(FixedQueue<T, kOtherCapacity>&& other) noexcept {
    this->clear();
    this->MoveItemsFrom(other);
    return *this;
  }
 
  template <size_t kOtherCapacity>
  void swap(FixedQueue<T, kOtherCapacity, SizeType>& other) {
    this->SwapValuesWith(other);
  }
 
  constexpr Deallocator* deallocator() const { return nullptr; }
};
 
template <typename T, typename S>
class FixedQueue<T, containers::kExternalStorage, S> final
    : public Queue<T, S> {
 public:
  static FixedQueue Allocate(Allocator& allocator, const S capacity) {
    FixedQueue queue = TryAllocate(allocator, capacity);
    PW_ASSERT(queue.capacity() == capacity);
    return queue;
  }
 
  static FixedQueue TryAllocate(Allocator& allocator, S capacity) {
    const allocator::Layout layout = allocator::Layout::Of<T[]>(capacity);
    std::byte* array = static_cast<std::byte*>(allocator.Allocate(layout));
    if (array == nullptr) {
      return FixedQueue(Aligned(array, 0u), nullptr);
    }
    return FixedQueue(Aligned(array, layout.size()), &allocator);
  }
 
  static FixedQueue WithStorage(UniquePtr<std::byte[]>&& storage) {
    const size_t size = storage.size();
    Deallocator* deallocator = storage.deallocator();
    return FixedQueue(Aligned::Assert(storage.Release(), size), deallocator);
  }
 
  explicit constexpr FixedQueue(span<std::byte> unaligned_buffer) noexcept
      : Queue<T, S>(unaligned_buffer), deallocator_(nullptr) {}
 
  template <size_t kAlignment, size_t kSizeBytes>
  explicit constexpr FixedQueue(
      containers::Storage<kAlignment, kSizeBytes>& buffer) noexcept
      : Queue<T, S>(buffer), deallocator_(nullptr) {}
 
  FixedQueue(const FixedQueue&) = delete;
  FixedQueue& operator=(const FixedQueue&) = delete;
 
  constexpr FixedQueue(FixedQueue&& other) noexcept
      : Queue<T, S>({}),
        deallocator_(cpp20::exchange(other.deallocator_, nullptr)) {
    this->MoveBufferFrom(other);
  }
 
  constexpr FixedQueue& operator=(FixedQueue&& other) noexcept {
    if (this == &other) {
      return *this;
    }
    T* const data = this->data();
    this->MoveBufferFrom(other);
 
    if (deallocator_ != nullptr) {
      deallocator_->Deallocate(data);
    }
    deallocator_ = cpp20::exchange(other.deallocator_, nullptr);
    return *this;
  }
 
  ~FixedQueue() {
    // Clear the queue so that the base `Queue` destructor will not need to
    // access its buffer, which will be freed.
    this->clear();
    if (deallocator_ != nullptr) {
      deallocator_->Deallocate(this->data());
    }
  }
 
  void swap(FixedQueue& other) noexcept {
    this->SwapBufferWith(other);
    std::swap(deallocator_, other.deallocator_);
  }
 
  template <size_t kInlineCapacity>
  void swap(FixedQueue<T, kInlineCapacity, S>& other) {
    other.swap(*this);  // Use the swap impl for statically allocated queues.
  }
 
  constexpr Deallocator* deallocator() const { return deallocator_; }
 
 private:
  using Aligned = typename Queue<T, S>::Aligned;
 
  constexpr FixedQueue(Aligned buffer, Deallocator* deallocator)
      : Queue<T, S>(buffer), deallocator_(deallocator) {}
 
  Deallocator* deallocator_;
};
 
}  // namespace pw