intrusive_forward_list.h

// Copyright 2021 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 <initializer_list>
#include <iterator>
#include <limits>
#include <type_traits>
 
#include "pw_containers/config.h"
#include "pw_containers/internal/intrusive_item.h"
#include "pw_containers/internal/intrusive_list.h"
#include "pw_containers/internal/intrusive_list_item.h"
#include "pw_containers/internal/intrusive_list_iterator.h"
 
 
namespace pw {
namespace containers {
namespace internal {
 
// Forward declaration for friending.
//
// The LegacyIntrusiveList has methods that run in O(n) time and have no
// analogue in `std::forward_list`. If any of these behaviors are needed,
// callers should consider whether a doubly-linked list is more appropriate,
// or whether they should provide the functionality themselves, e.g. by
// tracking size explicitly.
template <typename>
class LegacyIntrusiveList;
 
}  // namespace internal
 
template <typename T>
void PushBackSlow(IntrusiveForwardList<T>& forward_list, T& item) {
  forward_list.list().push_back(item);
}
 
}  // namespace containers
 
template <typename T>
class IntrusiveForwardList {
 private:
  using ItemBase = ::pw::containers::internal::IntrusiveForwardListItem;
 
 public:
  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*;
 
  class Item : public ItemBase {
   protected:
    constexpr explicit Item() = default;
 
   private:
    // IntrusiveItem is used to ensure T inherits from this container's Item
    // type. See also `CheckItemType`.
    template <typename, typename, bool>
    friend struct containers::internal::IntrusiveItem;
    using ItemType = T;
  };
 
  using iterator =
      typename ::pw::containers::internal::ForwardIterator<T, ItemBase>;
  using const_iterator =
      typename ::pw::containers::internal::ForwardIterator<std::add_const_t<T>,
                                                           const ItemBase>;
 
  constexpr IntrusiveForwardList() = default;
 
  // Intrusive lists cannot be copied, since each Item can only be in one list.
  IntrusiveForwardList(const IntrusiveForwardList&) = delete;
  IntrusiveForwardList& operator=(const IntrusiveForwardList&) = delete;
 
  IntrusiveForwardList(IntrusiveForwardList&&) = default;
 
  IntrusiveForwardList& operator=(IntrusiveForwardList&&) = default;
 
  template <typename Iterator>
  IntrusiveForwardList(Iterator first, Iterator last) {
    list().assign(first, last);
  }
 
  IntrusiveForwardList(std::initializer_list<Item*> items)
      : IntrusiveForwardList(items.begin(), items.end()) {}
 
  template <typename Iterator>
  void assign(Iterator first, Iterator last) {
    list().assign(first, last);
  }
 
  void assign(std::initializer_list<T*> items) {
    list().assign(items.begin(), items.end());
  }
 
  // Element access
 
  reference front() { return *static_cast<T*>(list().begin()); }
  const_reference front() const {
    return *static_cast<const T*>(list().begin());
  }
 
  // Iterators
 
  iterator before_begin() noexcept { return iterator(list().before_begin()); }
  const_iterator before_begin() const noexcept {
    return const_iterator(list().before_begin());
  }
  const_iterator cbefore_begin() const noexcept { return before_begin(); }
 
  iterator begin() noexcept { return iterator(list().begin()); }
  const_iterator begin() const noexcept {
    return const_iterator(list().begin());
  }
  const_iterator cbegin() const noexcept { return begin(); }
 
  iterator end() noexcept { return iterator(list().end()); }
  const_iterator end() const noexcept { return const_iterator(list().end()); }
  const_iterator cend() const noexcept { return end(); }
 
  // Capacity
 
  [[nodiscard]] bool empty() const noexcept { return list().empty(); }
 
  constexpr size_type max_size() const noexcept {
    return std::numeric_limits<difference_type>::max();
  }
 
  // Modifiers
 
  void clear() { list().clear(); }
 
  iterator insert_after(iterator pos, T& item) {
    return iterator(list().insert_after(pos.item_, item));
  }
 
  template <typename Iterator>
  iterator insert_after(iterator pos, Iterator first, Iterator last) {
    return iterator(list().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(list().erase_after(pos.item_));
  }
 
  iterator erase_after(iterator first, iterator last) {
    return iterator(list().erase_after(first.item_, last.item_));
  }
 
  void push_front(T& item) { list().push_front(item); }
 
  void pop_front() { list().pop_front(); }
 
  void swap(IntrusiveForwardList<T>& other) noexcept {
    list().swap(other.list());
  }
 
  // Operations
 
  void merge(IntrusiveForwardList<T>& other) {
    list().merge(other.list(),
                 [](const ItemBase& a, const ItemBase& b) -> bool {
                   return static_cast<const T&>(a) < static_cast<const T&>(b);
                 });
  }
 
  template <typename Compare>
  void merge(IntrusiveForwardList<T>& other, Compare comp) {
    list().merge(other.list(), [comp](const ItemBase& a, const ItemBase& b) {
      return comp(static_cast<const T&>(a), static_cast<const T&>(b));
    });
  }
 
  void splice_after(iterator pos, IntrusiveForwardList<T>& other) {
    splice_after(pos, other, other.before_begin(), other.end());
  }
 
  void splice_after(iterator pos, IntrusiveForwardList<T>& other, iterator it) {
    splice_after(pos, other, it, std::next(std::next(it)));
  }
 
  void splice_after(iterator pos,
                    IntrusiveForwardList<T>& other,
                    iterator first,
                    iterator last) {
    list().splice_after(pos.item_, other.list(), first.item_, last.item_);
  }
 
  bool remove(const T& item) { return list().remove(item); }
 
  template <typename UnaryPredicate>
  size_type remove_if(UnaryPredicate pred) {
    return list().remove_if([pred](const ItemBase& item) -> bool {
      return pred(static_cast<const T&>(item));
    });
  }
 
  void reverse() { list().reverse(); }
 
  size_type unique() {
    return list().unique([](const ItemBase& a, const ItemBase& b) -> bool {
      return static_cast<const T&>(a) == static_cast<const T&>(b);
    });
  }
 
  template <typename BinaryPredicate>
  size_type unique(BinaryPredicate pred) {
    return list().unique([pred](const ItemBase& a, const ItemBase& b) {
      return pred(static_cast<const T&>(a), static_cast<const T&>(b));
    });
  }
 
  void sort() {
    list().sort([](const ItemBase& a, const ItemBase& b) -> bool {
      return static_cast<const T&>(a) < static_cast<const T&>(b);
    });
  }
 
  template <typename Compare>
  void sort(Compare comp) {
    list().sort([comp](const ItemBase& a, const ItemBase& b) {
      return comp(static_cast<const T&>(a), static_cast<const T&>(b));
    });
  }
 
 private:
  template <typename>
  friend class containers::internal::LegacyIntrusiveList;
 
  friend void containers::PushBackSlow<T>(IntrusiveForwardList<T>&, T&);
 
  // Check that T is an Item in a function, since the class T will not be fully
  // defined when the IntrusiveList<T> class is instantiated.
  static constexpr void CheckItemType() {
    using IntrusiveItemType =
        typename containers::internal::IntrusiveItem<ItemBase, T>::Type;
    static_assert(
        std::is_base_of<IntrusiveItemType, T>(),
        "IntrusiveForwardList items must be derived from "
        "IntrusiveForwardList<T>::Item, where T is the item or one of its "
        "bases.");
  }
 
  // The generic list is accessed through this function to ensure
  // CheckItemType() is instantiated. CheckItemType() is not instantiated in the
  // constructor to allow constructing lists of forward declared items.
  constexpr auto& list() {
    CheckItemType();
    return generic_list_;
  }
 
  constexpr const auto& list() const {
    CheckItemType();
    return generic_list_;
  }
 
  containers::internal::GenericIntrusiveList<ItemBase> generic_list_;
};
 
template <typename T>
class IntrusiveForwardListItem final
    : public IntrusiveForwardList<IntrusiveForwardListItem<T>>::Item {
 public:
  using element_type = T;
  using value_type = std::remove_cv_t<element_type>;
  using reference = value_type&;
  using const_reference = const value_type&;
 
  template <typename... Args>
  IntrusiveForwardListItem(Args&&... args)
      : item_(std::forward<Args>(args)...) {}
 
  reference item() { return item_; }
  const_reference item() const { return item_; }
 
 private:
  element_type item_;
};
 
}  // namespace pw