zircon/system/ulib/fbl/include/fbl/intrusive_single_list.h

// Copyright 2016 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef FBL_INTRUSIVE_SINGLE_LIST_H_
#define FBL_INTRUSIVE_SINGLE_LIST_H_

#include <zircon/assert.h>

#include <cstddef>
#include <iterator>
#include <utility>

#include <fbl/intrusive_container_node_utils.h>
#include <fbl/intrusive_container_utils.h>
#include <fbl/intrusive_pointer_traits.h>

// Usage Notes:
//
// fbl::SinglyLinkedList<> is a templated intrusive container class which
// allows users to manage singly linked lists of objects.
//
// The bookkeeping storage required to exist on a list is a property of the
// objects stored on the list eliminating the need for runtime bookkeeping
// allocation/deallocation to add/remove members to/from the container.
//
// Lists store pointers to the objects, not the objects themselves, and are
// templated based on the specific type of pointer to be stored.  Supported
// pointer types are....
// 1) T*            : raw unmanaged pointers
// 2) unique_ptr<T> : unique managed pointers.
// 3) RefPtr<T>     : managed pointers to ref-counted objects.
//
// Lists of managed pointer types hold references to objects and follow the
// rules of the particular managed pointer patterns.  Destroying or clearing a
// list of managed pointers will release the references to the objects and may
// end the lifecycle of an object if the reference held by the list happened to
// be the last.
//
// Lists of unmanaged pointer types perform no lifecycle management.  It is up to
// the user of the list class to make sure that lifecycles are managed properly.
// As an added safety, a list of unmanaged pointers will ZX_ASSERT if it is
// destroyed with elements still in it.
//
// Objects may exist in multiple lists (or other containers) through the use of
// custom trait classes.  It should be noted that it is possible to make
// different types lists of unique_ptr<T> for a given T, but there is little
// point in doing so as it is impossible to exist on multiple lists at the same
// time without violating the fundamental rules of unique_ptr<T> patterns.
//
// Default traits and a helper base class are provided to make it easy to
// implement list-able objects intended to exist on only one type of list.
//
////////////////////////////////////////////////////////////////////////////////
// Example: A simple list of unmanaged pointers to Foo objects
//
// class Foo : public fbl::SinglyLinkedListable<Foo*> {
//      ...
// };
//
// void Test() {
//     fbl::SinglyLinkedList<Foo*> list;
//
//     for (size_t i = 0; SOME_NUMBER; ++i)
//         list.push_front(new Foo(...));
//
//     for (const auto& foo : list)
//         foo.print();
//
//     while (!list.is_empty())
//         delete list.pop_front();
// }
//
////////////////////////////////////////////////////////////////////////////////
// Example: A simple list of unique pointers to Foo objects
//
// class Foo : public fbl::SinglyLinkedListable<unique_ptr<Foo>> {
//      ...
// };
//
// void Test() {
//     fbl::SinglyLinkedList<unique_ptr<Foo>> list;
//
//     for (size_t i = 0; SOME_NUMBER; ++i) {
//         unique_ptr<Foo> new_foo(new Foo(...));
//         list.push_front(std::move(new_foo));
//     }
//
//     for (const auto& foo : list)
//         foo.print();
//
//     list.clear();    // Could also just let the list go out of scope.
// }
//
////////////////////////////////////////////////////////////////////////////////
// Example: A more complicated example of a list of ref-counted objects which
// can exist on 3 different types of lists at the same time.
//
// class Foo : public fbl::SinglyLinkedListable<fbl::RefPtr<Foo>>
//           , public fbl::RefCounted<Foo> {
// public:
//     using NodeState = SinglyLinkedListNodeState<fbl::RefPtr<Foo>>;
//     struct TypeATraits { static NodeState& node_state(Foo& foo) { return foo.type_a_state_; } }
//     struct TypeBTraits { static NodeState& node_state(Foo& foo) { return foo.type_b_state_; } }
//
//     /* Class implementation goes here */
//
// private:
//     friend struct TypeATraits;
//     friend struct TypeBTraits;
//     NodeState type_a_state_;
//     NodeState type_b_state_;
// };
//
// void Test() {
//     using DefaultList = fbl::SinglyLinkedList<fbl::RefPtr<Foo>>;
//     using TypeAList   = fbl::SinglyLinkedListCustomTraits<fbl::RefPtr<Foo>, Foo::TypeATraits>;
//     using TypeBList   = fbl::SinglyLinkedListCustomTraits<fbl::RefPtr<Foo>, Foo::TypeBTraits>;
//
//     DefaultList default_list;
//     TypeAList a_list;
//     TypeAList b_list;
//
//     for (size_t i = 0; i < SOME_NUMBER; ++i) {
//         fbl::RefPtr<Foo> new_foo = AdoptRef(new Foo(...));
//
//         switch (i & 0x3) {
//             case 0: break;
//             case 1: a_list.push_front(new_foo); break;
//             case 2: b_list.push_front(new_foo); break;
//             case 3:
//                 a_list.push_front(new_foo);
//                 b_list.push_front(new_foo);
//                 break;
//         }
//
//         default_list.push_front(std::move(new_foo));
//     }
//
//     // default list contains all the Foo instances we created
//     // a_list has case 1 and case 3 Foo instances
//     // b_list has case 2 and case 3 Foo instances
//     for (const auto& foo : default_list) foo.print();
//     for (const auto& foo : a_list) foo.print();
//     for (const auto& foo : b_list) foo.print();
//
//     default_list.clear();  // case 0 Foo's get cleaned up.
//     a_list.clear();        // case 1 Foo's get cleaned up.
//     b_list.clear();        // case 2 and 3 Foo's get cleaned up.
// }

namespace fbl {

// Fwd decl of classes used by tests.
namespace tests {
namespace intrusive_containers {
class SinglyLinkedListChecker;
template <typename>
class SequenceContainerTestEnvironment;
}  // namespace intrusive_containers
}  // namespace tests

// SinglyLinkedListNodeState<PtrType>
//
// PtrTypehe state needed to be a member of a SinglyLinkedList<PtrType>.  All members of a
// specific type SinglyLinkedList<PtrType> must expose a SinglyLinkedListNodeState<PtrType>
// to the list implementation via the supplied traits.  See
// DefaultSinglyLinkedListPtrTyperaits<PtrType>
template <typename PtrType_, NodeOptions Options = NodeOptions::None>
struct SinglyLinkedListNodeState
    : public internal::CommonNodeStateBase<SinglyLinkedListNodeState<PtrType_, Options>> {
 private:
  using Base = internal::CommonNodeStateBase<SinglyLinkedListNodeState<PtrType_, Options>>;

 public:
  using PtrType = PtrType_;
  using PtrTraits = internal::ContainerPtrTraits<PtrType_>;
  static constexpr NodeOptions kNodeOptions = Options;

  constexpr SinglyLinkedListNodeState() {}
  ~SinglyLinkedListNodeState() {
    ZX_DEBUG_ASSERT(IsValid());
    if constexpr (!(kNodeOptions & fbl::NodeOptions::AllowClearUnsafe)) {
      ZX_DEBUG_ASSERT(!InContainer());
    }
  }

  // Defer to CommonNodeStateBase for enforcement of the various copy/move
  // rules.  Make sure, however, that we explicitly do not allow our own default
  // construction/assignment operators change anything about our state.
  SinglyLinkedListNodeState(const SinglyLinkedListNodeState& other) : Base(other) {}
  SinglyLinkedListNodeState& operator=(const SinglyLinkedListNodeState& other) {
    this->Base::operator=(other);
    return *this;
  }
  SinglyLinkedListNodeState(SinglyLinkedListNodeState&& other) : Base(std::move(other)) {}
  SinglyLinkedListNodeState& operator=(SinglyLinkedListNodeState&& other) {
    this->Base::operator=(std::move(other));
    return *this;
  }

  bool IsValid() const { return true; }
  bool InContainer() const { return (next_ != nullptr); }

 private:
  template <typename, typename, SizeOrder, typename>
  friend class SinglyLinkedList;
  template <typename>
  friend class tests::intrusive_containers::SequenceContainerTestEnvironment;
  friend class tests::intrusive_containers::SinglyLinkedListChecker;

  typename PtrTraits::RawPtrType next_ = nullptr;
};

template <typename PtrType, NodeOptions Options, typename TagType>
struct SinglyLinkedListable;

// DefaultSinglyLinkedListNodeState<PtrType, TagType>
//
// The default implementation of traits needed to be a member of a singly linked
// list.  Any valid traits implementation must expose a static node_state method
// compatible with DefaultSinglyLinkedListTraits<PtrType, TagType>::node_state(...).
//
// To use the default traits, an object may...
//
// 1) Be friends with DefaultSinglyLinkedListTraits<PtrType, TagType> and have a
//    private sll_node_state_ member.
// 2) Have a public sll_node_state_ member (not recommended)
// 3) Derive from SinglyLinkedListable<PtrType> or
//    ContainableBaseClasses<SinglyLinkedListable<PtrType, TagType> [...]>
//    (easiest)
template <typename PtrType_, typename TagType_ = DefaultObjectTag>
struct DefaultSinglyLinkedListTraits {
 private:
  using ValueType = typename internal::ContainerPtrTraits<PtrType_>::ValueType;

 public:
  using PtrType = PtrType_;
  using TagType = TagType_;
  using PtrTraits = internal::ContainerPtrTraits<PtrType_>;

  static auto& node_state(typename PtrTraits::RefType obj) {
    if constexpr (std::is_same_v<TagType, DefaultObjectTag>) {
      return obj.ValueType::sll_node_state_;
    } else {
      return obj.template GetContainableByTag<TagType>().sll_node_state_;
    }
  }

  using NodeState =
      std::decay_t<std::invoke_result_t<decltype(node_state), typename PtrTraits::RefType>>;
};

// SinglyLinkedListable<PtrType>
//
// A helper class which makes it simple to exist on a singly linked list.
// Simply derive your object from SinglyLinkedListable and you are done.
template <typename PtrType_, NodeOptions Options = NodeOptions::None,
          typename TagType_ = DefaultObjectTag>
struct SinglyLinkedListable {
 public:
  using PtrType = PtrType_;
  using TagType = TagType_;
  static constexpr NodeOptions kNodeOptions = Options;

  bool InContainer() const {
    using Node = SinglyLinkedListable<PtrType, Options, TagType>;
    return Node::sll_node_state_.InContainer();
  }

 private:
  friend struct DefaultSinglyLinkedListTraits<PtrType, TagType>;
  SinglyLinkedListNodeState<PtrType, Options> sll_node_state_;
};

template <typename PtrType_, typename TagType_ = DefaultObjectTag,
          SizeOrder ListSizeOrder_ = SizeOrder::N,
          typename NodeTraits_ = DefaultSinglyLinkedListTraits<PtrType_, TagType_>>
class __POINTER(PtrType_) SinglyLinkedList : private internal::SizeTracker<ListSizeOrder_> {
 private:
  // Private fwd decls of the iterator implementation.
  template <typename IterTraits>
  class iterator_impl;
  struct iterator_traits;
  struct const_iterator_traits;

 public:
  // Aliases used to reduce verbosity and expose types/traits to tests
  static constexpr SizeOrder ListSizeOrder = ListSizeOrder_;
  using PtrType = PtrType_;
  using TagType = TagType_;
  using NodeTraits = NodeTraits_;

  using PtrTraits = internal::ContainerPtrTraits<PtrType_>;
  using RawPtrType = typename PtrTraits::RawPtrType;
  using ValueType = typename PtrTraits::ValueType;
  using RefType = typename PtrTraits::RefType;
  using CheckerType = ::fbl::tests::intrusive_containers::SinglyLinkedListChecker;
  using ContainerType = SinglyLinkedList<PtrType_, TagType_, ListSizeOrder_, NodeTraits_>;

  // Declarations of the standard iterator types.
  using iterator = iterator_impl<iterator_traits>;
  using const_iterator = iterator_impl<const_iterator_traits>;

  // Singly linked lists do not support constant order erase (erase using an
  // iterator or direct object reference).
  static constexpr bool SupportsConstantOrderErase = false;
  static constexpr bool SupportsConstantOrderSize = (ListSizeOrder == SizeOrder::Constant);
  static constexpr bool IsAssociative = false;
  static constexpr bool IsSequenced = true;

  // Default construction gives an empty list.
  constexpr SinglyLinkedList() noexcept {
    using NodeState = internal::node_state_t<NodeTraits, RefType>;

    // Make certain that the type of pointer we are expected to manage matches
    // the type of pointer that our Node type expects to manage.
    static_assert(std::is_same_v<PtrType, typename NodeState::PtrType>,
                  "SinglyLinkedList's pointer type must match its Node's pointerType");

    // SinglyLinkedList does not currently support direct remove-from-container.
    static_assert(!(NodeState::kNodeOptions & NodeOptions::AllowRemoveFromContainer),
                  "SinglyLinkedList does not support nodes which allow RemoveFromContainer.");
  }

  // Rvalue construction is permitted, but will result in the move of the list
  // contents from one instance of the list to the other (even for unmanaged
  // pointers).
  //
  // Make sure to expand our default constructor as well in order to pick up the
  // static asserts that we put there.
  SinglyLinkedList(SinglyLinkedList&& other_list) noexcept : SinglyLinkedList() {
    swap(other_list);
  }

  // Rvalue assignment is permitted for managed lists, and when the target is
  // an empty list of unmanaged pointers.  Like Rvalue construction, it will
  // result in the move of the source contents to the destination.
  SinglyLinkedList& operator=(SinglyLinkedList&& other_list) {
    ZX_DEBUG_ASSERT(PtrTraits::IsManaged || is_empty());

    clear();
    swap(other_list);

    return *this;
  }

  ~SinglyLinkedList() {
    // It is considered an error to allow a list of unmanaged pointers to
    // destruct if there are still elements in it.  Managed pointer lists
    // will automatically release their references to their elements.
    if (PtrTraits::IsManaged == false) {
      ZX_DEBUG_ASSERT(is_empty());
      if constexpr (SupportsConstantOrderSize) {
        ZX_DEBUG_ASSERT(this->SizeTrackerCount() == 0);
      }
    } else {
      clear();
    }
  }

  // Standard begin/end, cbegin/cend iterator accessors.
  iterator begin() { return iterator(head_); }
  const_iterator begin() const { return const_iterator(head_); }
  const_iterator cbegin() const { return const_iterator(head_); }

  iterator end() { return iterator(sentinel()); }
  const_iterator end() const { return const_iterator(sentinel()); }
  const_iterator cend() const { return const_iterator(sentinel()); }

  // make_iterator : Construct an iterator out of a pointer to an object.
  iterator make_iterator(ValueType& obj) {
    ZX_DEBUG_ASSERT(NodeTraits::node_state(obj).InContainer());
    return iterator(&obj);
  }
  const_iterator make_iterator(const ValueType& obj) const {
    ZX_DEBUG_ASSERT(NodeTraits::node_state(const_cast<ValueType&>(obj)).InContainer());
    return const_iterator(&const_cast<ValueType&>(obj));
  }

  // materialize_iterator : Construct an iterator out of a pointer to an object,
  // without a reference to the container.
  //
  // USE WITH CAUTION: The caller is responsible for ensuring it is safe to
  // access the container when using this iterator. In particular, static lock
  // analysis will not detect access without holding the required locks guarding
  // the container.
  static iterator materialize_iterator(ValueType& obj) {
    ZX_DEBUG_ASSERT(NodeTraits::node_state(obj).InContainer());
    return iterator(&obj);
  }
  static const_iterator materialize_iterator(const ValueType& obj) {
    ZX_DEBUG_ASSERT(NodeTraits::node_state(const_cast<ValueType&>(obj)).InContainer());
    return const_iterator(&const_cast<ValueType&>(obj));
  }

  // is_empty
  //
  // True if the list has at least one element in it, false otherwise.
  bool is_empty() const {
    ZX_DEBUG_ASSERT(head_ != nullptr);
    return internal::is_sentinel_ptr(head_);
  }

  // front
  //
  // Return a reference to the element at the front of the list without
  // removing it.  It is an error to call front on an empty list.
  typename PtrTraits::RefType front() {
    ZX_DEBUG_ASSERT(!is_empty());
    return *head_;
  }
  typename PtrTraits::ConstRefType front() const {
    ZX_DEBUG_ASSERT(!is_empty());
    return *head_;
  }

  // push_front
  //
  // Push an element onto the front of the lists.  Lvalue and Rvalue
  // versions are supplied in order to support move semantics.  It
  // is an error to attempt to push a nullptr instance of PtrType.
  void push_front(const PtrType& ptr) { push_front(PtrType(ptr)); }
  void push_front(PtrType&& ptr) {
    ZX_DEBUG_ASSERT(ptr != nullptr);

    auto& ptr_ns = NodeTraits::node_state(*ptr);
    ZX_DEBUG_ASSERT(!ptr_ns.InContainer());

    ptr_ns.next_ = head_;
    head_ = PtrTraits::Leak(ptr);
    this->IncSizeTracker(1);
  }

  // insert_after
  //
  // Insert an element after iter in the list, returning an iterator to the
  // newly-created element. It is an error to attempt to push a nullptr
  // instance of PtrType, or to attempt to push with iter == end().
  iterator insert_after(const iterator& iter, const PtrType& ptr) {
    return insert_after(iter, PtrType(ptr));
  }
  iterator insert_after(const iterator& iter, PtrType&& ptr) {
    ZX_DEBUG_ASSERT(iter.IsValid());
    ZX_DEBUG_ASSERT(ptr != nullptr);

    auto& iter_ns = NodeTraits::node_state(*iter.node_);
    auto& ptr_ns = NodeTraits::node_state(*ptr);
    ZX_DEBUG_ASSERT(!ptr_ns.InContainer());

    ptr_ns.next_ = iter_ns.next_;
    auto* new_item = PtrTraits::Leak(ptr);
    iter_ns.next_ = new_item;
    this->IncSizeTracker(1);

    // Return an iterator to the new element.
    return make_iterator(*new_item);
  }

  // pop_front
  //
  // Removes the head of the list and transfer the pointer to the
  // caller.  If the list is empty, return a nullptr instance of
  // PtrType.
  PtrType pop_front() {
    if (is_empty())
      return PtrType(nullptr);

    auto& head_ns = NodeTraits::node_state(*head_);
    PtrType ret = PtrTraits::Reclaim(head_);

    head_ = head_ns.next_;
    head_ns.next_ = nullptr;
    this->DecSizeTracker(1);

    return ret;
  }

  // clear
  //
  // Clear out the list, unlinking all of the elements in the process.  For
  // managed pointer types, this will release all references held by the list
  // to the objects which were in it.
  void clear() {
    while (!is_empty()) {
      auto& head_ns = NodeTraits::node_state(*head_);
      RawPtrType tmp = head_;
      head_ = head_ns.next_;
      head_ns.next_ = nullptr;
      PtrTraits::Reclaim(tmp);
    }
    this->ResetSizeTracker();
  }

  // clear_unsafe
  //
  // A special clear operation which just resets the internal container
  // structure, but leaves all of the node-state(s) of the current element(s)
  // alone.
  //
  // Only usable with containers of unmanaged pointers (Very Bad things can
  // happen if you try this with containers of managed pointers) whose nodes
  // have the NodeOptions::AllowClearUnsafe option set.
  //
  // Note: While this can be useful in special cases (such as resetting a free
  // list for a pool/slab allocator during destruction), you normally do not
  // want this behavior.  Think carefully before calling this!
  void clear_unsafe() {
    static_assert(PtrTraits::IsManaged == false,
                  "clear_unsafe is not allowed for containers of managed pointers");
    static_assert(NodeTraits::NodeState::kNodeOptions & NodeOptions::AllowClearUnsafe,
                  "Container does not support clear_unsafe.  Consider adding "
                  "NodeOptions::AllowClearUnsafe to your node storage.");

    head_ = sentinel();
    this->ResetSizeTracker();
  }

  // erase_next
  //
  // Remove the element in the list which follows iter and return a pointer to
  // the removed element.  If there is no element in the list which follows
  // iter, return a nullptr instance of PtrType.  It is an error to attempt to
  // erase_next an invalid iterator (either an uninitialized iterator, or an
  // iterator which is equal to end())
  PtrType erase_next(const iterator& iter) {
    ZX_DEBUG_ASSERT(iter.IsValid());
    auto& iter_ns = NodeTraits::node_state(*iter);

    if (internal::is_sentinel_ptr(iter_ns.next_))
      return PtrType(nullptr);

    auto& next_ns = NodeTraits::node_state(*iter_ns.next_);

    PtrType ret = PtrTraits::Reclaim(iter_ns.next_);
    iter_ns.next_ = next_ns.next_;
    next_ns.next_ = nullptr;
    this->DecSizeTracker(1);
    return ret;
  }

  // swap
  //
  // swaps the contest of two lists.
  void swap(SinglyLinkedList& other) {
    auto tmp = head_;
    head_ = other.head_;
    other.head_ = tmp;
    this->SwapSizeTracker(other);
  }

  // size_slow
  //
  // count the elements in the list in O(n) fashion
  size_t size_slow() const {
    // It is illegal to call this if the user requested constant order size
    // operations.
    static_assert(
        ListSizeOrder == SizeOrder::N,
        "size_slow is only allowed when using a list which has O(N) size!  Use size() instead.");

    size_t size = 0;

    for (auto iter = cbegin(); iter != cend(); ++iter)
      size++;

    return size;
  }

  // size : Only allowed when the user has selected an SizeOrder::Constant for this list.
  size_t size() const {
    static_assert(
        ListSizeOrder == SizeOrder::Constant,
        "size is only allowed when using a list which has O(1) size!  Use size_slow() instead.");
    return this->SizeTrackerCount();
  }

  // erase_if
  //
  // Find the first member of the list which satisfies the predicate given by
  // 'fn' and remove it from the list, returning a referenced pointer to the
  // removed element.  Return nullptr if no member satisfies the predicate.
  template <typename UnaryFn>
  PtrType erase_if(UnaryFn fn) {
    using ConstRefType = typename PtrTraits::ConstRefType;

    if (is_empty())
      return PtrType(nullptr);

    auto iter = begin();
    if (fn(static_cast<ConstRefType>(*iter)))
      return pop_front();

    for (auto prev = iter++; iter != end(); prev = iter++) {
      if (fn(static_cast<ConstRefType>(*iter)))
        return erase_next(prev);
    }

    return PtrType(nullptr);
  }

  // find_if
  //
  // Find the first member of the list which satisfies the predicate given by
  // 'fn' and return an iterator in the list which refers to it.  Return end()
  // if no member satisfies the predicate.
  template <typename UnaryFn>
  const_iterator find_if(UnaryFn fn) const {
    for (auto iter = begin(); iter.IsValid(); ++iter) {
      if (fn(*iter))
        return iter;
    }

    return end();
  }

  template <typename UnaryFn>
  iterator find_if(UnaryFn fn) {
    const_iterator citer = const_cast<const ContainerType*>(this)->find_if(fn);
    return iterator(citer.node_);
  }

  // replace_if (copy)
  //
  // Find the first member of the list which satisfies the predicate given by
  // 'fn' and replace it in the list, returning a referenced pointer to the
  // replaced element.  If no member satisfies the predicate, simply return
  // nullptr instead.
  template <typename UnaryFn>
  PtrType replace_if(UnaryFn fn, const PtrType& ptr) {
    using ConstRefType = typename PtrTraits::ConstRefType;
    ZX_DEBUG_ASSERT(ptr != nullptr);

    auto& ptr_ns = NodeTraits::node_state(*ptr);
    ZX_DEBUG_ASSERT(!ptr_ns.InContainer());

    auto iter = begin();
    if (iter.IsValid()) {
      RawPtrType* prev_next_ptr = &head_;

      while (iter.IsValid()) {
        auto& iter_ns = NodeTraits::node_state(*iter);

        if (fn(static_cast<ConstRefType>(*iter))) {
          PtrType new_ref = ptr;
          RawPtrType replaced;

          replaced = *prev_next_ptr;
          *prev_next_ptr = PtrTraits::Leak(new_ref);
          ptr_ns.next_ = iter_ns.next_;
          iter_ns.next_ = nullptr;

          return PtrTraits::Reclaim(replaced);
        }

        prev_next_ptr = &iter_ns.next_;
        ++iter;
      }
    }

    return nullptr;
  }

  // replace_if (move)
  //
  // Same as the copy version, except that if no member satisfies the
  // predicate, the original reference is returned instead of nullptr.
  template <typename UnaryFn>
  PtrType replace_if(UnaryFn fn, PtrType&& ptr) {
    using ConstRefType = typename PtrTraits::ConstRefType;
    ZX_DEBUG_ASSERT(ptr != nullptr);

    auto& ptr_ns = NodeTraits::node_state(*ptr);
    ZX_DEBUG_ASSERT(!ptr_ns.InContainer());

    auto iter = begin();
    if (iter.IsValid()) {
      RawPtrType* prev_next_ptr = &head_;

      while (iter.IsValid()) {
        auto& iter_ns = NodeTraits::node_state(*iter);

        if (fn(static_cast<ConstRefType>(*iter))) {
          RawPtrType replaced;

          replaced = *prev_next_ptr;
          *prev_next_ptr = PtrTraits::Leak(ptr);
          ptr_ns.next_ = iter_ns.next_;
          iter_ns.next_ = nullptr;

          return PtrTraits::Reclaim(replaced);
        }

        prev_next_ptr = &iter_ns.next_;
        ++iter;
      }
    }

    return std::move(ptr);
  }

  // Split the list immediately after |iter|, returning the remainder of the
  // list in a new list instance.
  //
  // |iter| *must* refer to a member of the list being split.  Attempt to split
  // list A with an iterator to an element which is a member of list B will
  // result in undefined behavior which may not be detectable at runtime.
  ContainerType split_after(const iterator& iter) {
    if (!iter.IsValid()) {
      // iter must refer to a member of this list, therefore it must be valid.
      // DEBUG_ASSERT if it is not, or return an empty list in a release build.
      ZX_DEBUG_ASSERT(false);
      return {};
    }
    return split_after(*iter.node_);
  }

  // Alternate form of split_after which uses an object reference instead of an
  // iterator to determine the split point.  Just like the iterator form of
  // split_after, |obj| *must* be a member of the list being split.
  ContainerType split_after(ValueType& obj) {
    static_assert(ListSizeOrder == SizeOrder::N,
                  "split_after is not allowed for SizedSinglyLinkedLists");
    auto& A_ns = NodeTraits::node_state(obj);

    // If this is element is already the tail of the list, or if it is an
    // illegal split in a release build, simply return an empty list.
    if (!A_ns.InContainer()) {
      ZX_DEBUG_ASSERT(false);
      return {};
    }

    if (internal::is_sentinel_ptr(A_ns.next_)) {
      // Since this node is at the end of the list, we can sanity check to make
      // sure that obj was actually a member of this list.
      ZX_DEBUG_ASSERT(A_ns.next_ == sentinel());
      return {};
    }

    // At this point in time, we know that we have at least 2 nodes in the list
    // we are splitting.  Let A be |obj|, and B be the node immediately after A.
    //
    // We have 2 pointers we need to update in total.
    //
    // ret.head : needs to point to B, which is the new head of ret
    // A.next   : A is the new tail.  Next becomes this.sentinel();
    //
    // Thankfully, singly linked lists do not support reverse iteration, which
    // means that their sentinels are all the same.  This means that we don't
    // actually have to go and fixup ret.tail.next (which would force an O(n)
    // operation to find the tail).
    ContainerType ret;

    ret.head_ = A_ns.next_;
    A_ns.next_ = this->sentinel();

    return ret;
  }

 private:
  // The traits of a non-const iterator
  struct iterator_traits {
    using RefType = typename PtrTraits::RefType;
    using RawPtrType = typename PtrTraits::RawPtrType;
  };

  // The traits of a const iterator
  struct const_iterator_traits {
    using RefType = typename PtrTraits::ConstRefType;
    using RawPtrType = typename PtrTraits::ConstRawPtrType;
  };

  // The shared implementation of the iterator
  template <class IterTraits>
  class iterator_impl {
   public:
    using value_type = ValueType;
    using reference = typename IterTraits::RefType;
    using pointer = typename IterTraits::RawPtrType;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::forward_iterator_tag;

    iterator_impl() = default;
    iterator_impl(const iterator_impl& other) = default;
    iterator_impl& operator=(const iterator_impl& other) = default;

    bool IsValid() const { return (node_ != nullptr) && !internal::is_sentinel_ptr(node_); }
    bool operator==(const iterator_impl& other) const { return node_ == other.node_; }
    bool operator!=(const iterator_impl& other) const { return node_ != other.node_; }

    // Prefix
    iterator_impl& operator++() {
      if (!IsValid())
        return *this;

      node_ = NodeTraits::node_state(*node_).next_;

      return *this;
    }

    // Postfix
    iterator_impl operator++(int) {
      iterator_impl ret(*this);
      ++(*this);
      return ret;
    }

    typename PtrTraits::PtrType CopyPointer() const {
      return IsValid() ? PtrTraits::Copy(node_) : nullptr;
    }

    typename IterTraits::RefType operator*() const {
      ZX_DEBUG_ASSERT(IsValid());
      return *node_;
    }

    typename IterTraits::RawPtrType operator->() const {
      ZX_DEBUG_ASSERT(IsValid());
      return node_;
    }

   private:
    friend class SinglyLinkedList<PtrType_, TagType_, ListSizeOrder_, NodeTraits_>;

    explicit iterator_impl(typename IterTraits::RawPtrType node)
        : node_(const_cast<typename PtrTraits::RawPtrType>(node)) {}

    typename PtrTraits::RawPtrType node_ = nullptr;
  };

  // The test framework's 'checker' class is our friend.
  friend CheckerType;

  // move semantics only
  SinglyLinkedList(const SinglyLinkedList&) = delete;
  SinglyLinkedList& operator=(const SinglyLinkedList&) = delete;

  // Note: the sentinel value we use for singly linked list is a bit different
  // from the sentinel value we use for everything else.  Instead of being the
  // this pointer of the container with the sentinel bit set, the sentinel is
  // just the bit with nothing else (aka; nullptr | kContainerSentinelBit).
  //
  // The reasons which drive this decision are as follows.
  // 1) When swapping lists, if the sentinel value was list specific, we would
  //    need to update the sentinel values at the end of each list.  This would
  //    be an O(n) operation for a SLL, whereas it is an O(1) operation for
  //    every other container.
  // 2) The sentinel value used by a list cannot simply be nullptr, or the
  //    node state for an element which is list-able would not be able to
  //    distinguish between an element which was not InContainer() and one
  //    which was InContainer, but located at the end of the list.
  constexpr RawPtrType sentinel() const { return internal::make_sentinel<RawPtrType>(nullptr); }

  // State consists of just a head pointer.
  RawPtrType head_ = sentinel();
};

// SizedSinglyLinkedList<> is an alias for a SinglyLinkedList<> which keeps
// track of it's size internally so that it may be accessed in O(1) time.
//
template <typename PtrType, typename TagType = DefaultObjectTag,
          typename NodeTraits = DefaultSinglyLinkedListTraits<PtrType, TagType>>
using SizedSinglyLinkedList = SinglyLinkedList<PtrType, TagType, SizeOrder::Constant, NodeTraits>;

// SinglyLinkedListCustomTraits<> is an alias for a SinglyLinkedList<> which makes is easier to
// define a SinglyLinkedList which uses custom node traits.  It defaults to O(n) size, and will not
// allow users to use a non-default object tag, since lists which use custom node traits are
// required to use the default tag.
//
template <typename PtrType, typename NodeTraits, SizeOrder ListSizeOrder = SizeOrder::N>
using SinglyLinkedListCustomTraits =
    SinglyLinkedList<PtrType, DefaultObjectTag, ListSizeOrder, NodeTraits>;

// TaggedSinglyLinkedList<> is intended for use with ContainableBaseClasses<>.
//
// For an easy way to allow instances of your class to live in multiple
// intrusive containers at once, simply derive from
// ContainableBaseClasses<YourContainables<PtrType, TagType>...> and then use
// this template instead of SinglyLinkedList<> as the container, passing the same tag
// type you used earlier as the third parameter.
//
// See comments on ContainableBaseClasses<> in fbl/intrusive_container_utils.h
// for more details.
//
template <typename PtrType, typename TagType>
using TaggedSinglyLinkedList = SinglyLinkedList<PtrType, TagType, SizeOrder::N,
                                                DefaultSinglyLinkedListTraits<PtrType, TagType>>;

template <typename PtrType, typename TagType, NodeOptions Options = NodeOptions::None>
using TaggedSinglyLinkedListable = SinglyLinkedListable<PtrType, Options, TagType>;

}  // namespace fbl

#endif  // FBL_INTRUSIVE_SINGLE_LIST_H_