intrusive_queue.h

// Copyright 2026 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 <initializer_list>
#include <iterator>
#include <type_traits>
#include <utility>
 
#include "pw_containers/internal/intrusive_queue.h"
#include "pw_containers/intrusive_forward_list.h"
 
namespace pw {
 
template <typename T>
class IntrusiveQueue {
 private:
  using ItemBase = containers::internal::IntrusiveQueueItem;
 
 public:
  class Item : public ItemBase {
   protected:
    constexpr explicit Item() = default;
 
   private:
    template <typename, typename, bool>
    friend struct containers::internal::IntrusiveItem;
    using ItemType = T;
  };
 
  using element_type = T;
  using value_type = std::remove_cv_t<element_type>;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;
  using reference = value_type&;
  using const_reference = const value_type&;
  using pointer = element_type*;
  using const_pointer = const element_type*;
 
  using iterator = typename containers::internal::ForwardIterator<T, ItemBase>;
  using const_iterator =
      typename containers::internal::ForwardIterator<std::add_const_t<T>,
                                                     const ItemBase>;
 
  constexpr IntrusiveQueue() = default;
 
  // Intrusive queues cannot be copied.
  IntrusiveQueue(const IntrusiveQueue&) = delete;
  IntrusiveQueue& operator=(const IntrusiveQueue&) = delete;
 
  IntrusiveQueue(IntrusiveQueue&&) = default;
 
  IntrusiveQueue& operator=(IntrusiveQueue&&) = default;
 
  template <typename Iterator>
  IntrusiveQueue(Iterator first, Iterator last) {
    assign(first, last);
  }
 
  IntrusiveQueue(std::initializer_list<T*> items) {
    assign(items.begin(), items.end());
  }
 
  template <typename Iterator>
  void assign(Iterator first, Iterator last) {
    CheckItemType();
    generic_queue_.assign(first, last);
  }
 
  void assign(std::initializer_list<T*> items) {
    assign(items.begin(), items.end());
  }
 
  // Iterators
 
  iterator before_begin() noexcept {
    return iterator(generic_queue_.before_begin());
  }
  const_iterator before_begin() const noexcept {
    return const_iterator(generic_queue_.before_begin());
  }
  const_iterator cbefore_begin() const noexcept { return before_begin(); }
 
  iterator begin() noexcept { return iterator(generic_queue_.begin()); }
  const_iterator begin() const noexcept {
    return const_iterator(generic_queue_.begin());
  }
  const_iterator cbegin() const noexcept { return begin(); }
 
  iterator end() noexcept { return iterator(generic_queue_.end()); }
  const_iterator end() const noexcept {
    return const_iterator(generic_queue_.end());
  }
  const_iterator cend() const noexcept { return end(); }
 
  // Element access
 
  reference front() { return *static_cast<T*>(generic_queue_.begin()); }
  const_reference front() const {
    return *static_cast<const T*>(generic_queue_.begin());
  }
 
  reference back() { return *static_cast<T*>(generic_queue_.tail()); }
  const_reference back() const {
    return *static_cast<const T*>(generic_queue_.tail());
  }
 
  // Capacity
 
  [[nodiscard]] bool empty() const noexcept { return generic_queue_.empty(); }
  constexpr size_type max_size() const noexcept {
    return std::numeric_limits<difference_type>::max();
  }
 
  // Modifiers
 
  void clear() { generic_queue_.clear(); }
 
  void push_front(T& item) { generic_queue_.push_front(item); }
 
  void pop_front() { generic_queue_.pop_front(); }
 
  void push_back(T& item) { generic_queue_.push_back(item); }
 
  iterator insert_after(iterator pos, T& item) {
    return iterator(generic_queue_.insert_after(pos.item_, item));
  }
 
  template <typename Iterator>
  iterator insert_after(iterator pos, Iterator first, Iterator last) {
    return iterator(generic_queue_.insert_after(pos.item_, first, last));
  }
 
  iterator insert_after(iterator pos, std::initializer_list<T*> items) {
    return insert_after(pos, items.begin(), items.end());
  }
 
  iterator erase_after(iterator pos) {
    return iterator(generic_queue_.erase_after(pos.item_));
  }
 
  iterator erase_after(iterator first, iterator last) {
    return iterator(generic_queue_.erase_after(first.item_, last.item_));
  }
 
  bool remove(const T& item_to_remove) {
    return generic_queue_.remove(item_to_remove);
  }
 
  template <typename UnaryPredicate>
  size_type remove_if(UnaryPredicate&& pred) {
    return generic_queue_.remove_if<T>(std::forward<UnaryPredicate>(pred));
  }
 
  void swap(IntrusiveQueue<T>& other) noexcept {
    generic_queue_.swap(other.generic_queue_);
  }
 
 private:
  // Check that T is an Item in a function, since the class T will not be fully
  // defined when the IntrusiveQueue<T> class is instantiated.
  static constexpr void CheckItemType() {
    using IntrusiveItemType =
        typename containers::internal::IntrusiveItem<ItemBase, T>::Type;
    static_assert(
        std::is_base_of_v<IntrusiveItemType, T>,
        "IntrusiveQueue items must be derived from IntrusiveQueue<T>::Item, "
        "where T is the item or one of its bases.");
  }
 
  containers::internal::GenericIntrusiveQueue generic_queue_;
};
 
}  // namespace pw