intrusive_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 <algorithm>
#include <cstddef>
#include <cstdio>
#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"
#include "pw_containers/internal/legacy_intrusive_list.h"
#include "pw_containers/intrusive_forward_list.h"
 
namespace pw {
namespace containers::future {
 
template <typename T>
class IntrusiveList {
 private:
  using ItemBase = ::pw::containers::internal::IntrusiveListItem;
 
 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::BidirectionalIterator<T, ItemBase>;
  using const_iterator = typename ::pw::containers::internal::
      BidirectionalIterator<std::add_const_t<T>, const ItemBase>;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
  constexpr IntrusiveList() { CheckItemType(); }
 
  // Intrusive lists cannot be copied, since each Item can only be in one list.
  IntrusiveList(const IntrusiveList&) = delete;
  IntrusiveList& operator=(const IntrusiveList&) = delete;
 
  IntrusiveList(IntrusiveList&&) = default;
 
  IntrusiveList& operator=(IntrusiveList&&) = default;
 
  // Constructs an IntrusiveList from an iterator over Items. The iterator may
  // dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g.
  // from std::initializer_list<Item*>).
  template <typename Iterator>
  IntrusiveList(Iterator first, Iterator last) {
    list_.assign(first, last);
  }
 
  // Constructs an IntrusiveList from a std::initializer_list of pointers to
  // items.
  IntrusiveList(std::initializer_list<Item*> items)
      : IntrusiveList(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
 
  T& front() { return *static_cast<T*>(list_.begin()); }
 
  T& back() { return *static_cast<T*>(list_.before_end()); }
 
  // Iterators
 
  iterator begin() noexcept {
    return iterator(static_cast<Item*>(list_.begin()));
  }
  const_iterator begin() const noexcept {
    return const_iterator(static_cast<const Item*>(list_.begin()));
  }
  const_iterator cbegin() const noexcept { return begin(); }
 
  iterator end() noexcept { return iterator(static_cast<Item*>(list_.end())); }
  const_iterator end() const noexcept {
    return const_iterator(static_cast<const Item*>(list_.end()));
  }
  const_iterator cend() const noexcept { return end(); }
 
  reverse_iterator rbegin() { return reverse_iterator(end()); }
  const_reverse_iterator rbegin() const {
    return const_reverse_iterator(end());
  }
  const_reverse_iterator crbegin() const {
    return const_reverse_iterator(end());
  }
 
  reverse_iterator rend() { return reverse_iterator(begin()); }
  const_reverse_iterator rend() const {
    return const_reverse_iterator(begin());
  }
  const_reverse_iterator crend() const {
    return const_reverse_iterator(begin());
  }
 
  // Capacity
 
  [[nodiscard]] bool empty() const noexcept { return list_.empty(); }
 
  size_t size() const {
    return static_cast<size_type>(std::distance(begin(), end()));
  }
 
  constexpr size_type max_size() const noexcept { return list_.max_size(); }
 
  // Modifiers
 
  void clear() { list_.clear(); }
 
  iterator insert(iterator pos, T& item) {
    return iterator(list_.insert_after((--pos).item_, item));
  }
 
  template <typename Iterator>
  iterator insert(iterator pos, Iterator first, Iterator last) {
    return iterator(list_.insert_after((--pos).item_, first, last));
  }
 
  iterator insert(iterator pos, std::initializer_list<T*> items) {
    return insert(pos, items.begin(), items.end());
  }
 
  iterator erase(T& item) { return erase(iterator(&item)); }
 
  iterator erase(iterator pos) {
    return iterator(list_.erase_after((--pos).item_));
  }
 
  iterator erase(iterator first, iterator last) {
    return iterator(list_.erase_after((--first).item_, last.item_));
  }
 
  void push_back(T& item) { list_.insert_after(list_.before_end(), item); }
 
  void pop_back() { remove(back()); }
 
  void push_front(T& item) { list_.insert_after(list_.before_begin(), item); }
 
  void pop_front() { remove(front()); }
 
  void swap(IntrusiveList<T>& other) noexcept { list_.swap(other.list_); }
 
  // Operations
 
  void merge(IntrusiveList<T>& other) {
    list_.merge(other.list_, [](const ItemBase& a, const ItemBase& b) {
      return static_cast<const T&>(a) < static_cast<const T&>(b);
    });
  }
 
  template <typename Compare>
  void merge(IntrusiveList<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(iterator pos, IntrusiveList<T>& other) {
    splice(pos, other, other.begin(), other.end());
  }
 
  void splice(iterator pos, IntrusiveList<T>& other, iterator it) {
    splice(pos, other, it, std::next(it));
  }
 
  void splice(iterator pos,
              IntrusiveList<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() { std::reverse(begin(), end()); }
 
  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) -> bool {
      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) -> bool {
      return comp(static_cast<const T&>(a), static_cast<const T&>(b));
    });
  }
 
 private:
  // 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>(),
        "IntrusiveList items must be derived from IntrusiveList<T>::Item, "
        "where T is the item or one of its bases.");
  }
 
  ::pw::containers::internal::GenericIntrusiveList<ItemBase> list_;
};
 
}  // namespace containers::future
 
// See b/362348318 and comments on `PW_CONTAINERS_USE_LEGACY_INTRUSIVE_LIST` and
// `PW_CONTAINERS_INTRUSIVE_LIST_SUPPRESS_DEPRECATION_WARNING`.
#if PW_CONTAINERS_USE_LEGACY_INTRUSIVE_LIST
#if PW_CONTAINERS_INTRUSIVE_LIST_SUPPRESS_DEPRECATION_WARNING
#define PW_CONTAINERS_INTRUSIVE_LIST_DEPRECATED
#else
#define PW_CONTAINERS_INTRUSIVE_LIST_DEPRECATED \
  [[deprecated("See b/362348318 for background and workarounds.")]]
#endif  // PW_CONTAINERS_INTRUSIVE_LIST_SUPPRESS_DEPRECATION_WARNING
 
template <typename T>
using IntrusiveList PW_CONTAINERS_INTRUSIVE_LIST_DEPRECATED =
    containers::internal::LegacyIntrusiveList<T>;
 
#else  // PW_CONTAINERS_USE_LEGACY_INTRUSIVE_LIST
 
template <typename T>
using IntrusiveList = containers::future::IntrusiveList<T>;
 
#endif  // PW_CONTAINERS_USE_LEGACY_INTRUSIVE_LIST
 
}  // namespace pw