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 <utility>

#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::SinglyLinkedList<fbl::RefPtr<Foo>, Foo::TypeATraits>;
//     using TypeBList   = fbl::SinglyLinkedList<fbl::RefPtr<Foo>, Foo::TypeBTraits>;
//
//     DefaultList default_list;
//     TypeAList a_list;
//     TypeAList b_list;
//
//     for (size_t i = 0; SOME_NUMBER; ++i) {
//         RefPtr 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));
//     }
//
//     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<T>
//
// The state needed to be a member of a SinglyLinkedList<T>.  All members of a
// specific type SinglyLinkedList<T> must expose a SinglyLinkedListNodeState<T>
// to the list implementation via the supplied traits.  See
// DefaultSinglyLinkedListTraits<T>
template <typename T>
struct SinglyLinkedListNodeState {
  using PtrTraits = internal::ContainerPtrTraits<T>;
  constexpr SinglyLinkedListNodeState() {}
  ~SinglyLinkedListNodeState() {
    // Note; this ASSERT can only be enforced for lists made of managed
    // pointer types.  Lists formed from unmanaged pointers can potentially
    // leave next_ in a non-null state during destruction if the list is
    // cleared using "clear_unsafe".
    ZX_DEBUG_ASSERT(!PtrTraits::IsManaged || (next_ == nullptr));
  }

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

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

  typename PtrTraits::RawPtrType next_ = nullptr;
};

template <typename T, typename TagType>
struct SinglyLinkedListable;

// DefaultSinglyLinkedListNodeState<T>
//
// 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<T>::node_state(...).  To use
// the default traits, an object may...
//
// 1) Be friends with DefaultSinglyLinkedListTraits<T> and have a private
//    sll_node_state_ member.
// 2) Have a public sll_node_state_ member (not recommended)
// 3) Derive from SinglyLinkedListable<T> or
//    ContainableBaseClasses<SinglyLinkedListable<T, <your tag type>> [...]>
//    (easiest)
template <typename T>
struct DefaultSinglyLinkedListTraits {
 private:
  using ValueType = typename internal::ContainerPtrTraits<T>::ValueType;

  template <typename TagType>
  using NodeType = std::conditional_t<internal::has_tag_types_v<ValueType>,
                                      SinglyLinkedListable<T, TagType>, ValueType>;

 public:
  using PtrTraits = internal::ContainerPtrTraits<T>;
  template <typename TagType = DefaultObjectTag>
  static SinglyLinkedListNodeState<T>& node_state(typename PtrTraits::RefType obj) {
    using Node [[maybe_unused]] = NodeType<TagType>;
    return obj.Node::sll_node_state_;
  }
};

// SinglyLinkedListable<T>
//
// 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 T, typename TagType_ = DefaultObjectTag>
struct SinglyLinkedListable {
 public:
  using TagType = TagType_;
  bool InContainer() const {
    using Node = SinglyLinkedListable<T, TagType>;
    return Node::sll_node_state_.InContainer();
  }

 private:
  friend struct DefaultSinglyLinkedListTraits<T>;
  SinglyLinkedListNodeState<T> sll_node_state_;
};

template <typename T, typename NodeTraits_ = DefaultSinglyLinkedListTraits<T>,
          typename TagType_ = DefaultObjectTag, SizeOrder ListSizeOrder_ = SizeOrder::N>
class 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;

  template <typename NodeTraits, typename = void>
  struct AddGenericNodeState;

 public:
  // Aliases used to reduce verbosity and expose types/traits to tests
  static constexpr SizeOrder ListSizeOrder = ListSizeOrder_;
  using PtrTraits = internal::ContainerPtrTraits<T>;
  using NodeTraits = AddGenericNodeState<NodeTraits_>;
  using PtrType = typename PtrTraits::PtrType;
  using RawPtrType = typename PtrTraits::RawPtrType;
  using ValueType = typename PtrTraits::ValueType;
  using TagType = TagType_;
  using CheckerType = ::fbl::tests::intrusive_containers::SinglyLinkedListChecker;
  using ContainerType = SinglyLinkedList<T, NodeTraits_, TagType, ListSizeOrder>;

  // 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() {}

  // 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)
  SinglyLinkedList(SinglyLinkedList&& other_list) noexcept { 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 reference to an object.
  iterator make_iterator(ValueType& obj) { return iterator(&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.  It is an error to attempt to
  // push a nullptr instance of PtrType, or to attempt to push with iter ==
  // end().
  void insert_after(const iterator& iter, const PtrType& ptr) { insert_after(iter, PtrType(ptr)); }
  void 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_;
    iter_ns.next_ = PtrTraits::Leak(ptr);
    this->IncSizeTracker(1);
  }

  // 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).
  //
  // 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");
    head_ = sentinel();
    this->ResetSizeTracker();
  }

  // erase_next
  //
  // Remove the element in the list which follows iter.  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 erase 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);
  }

 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:
    iterator_impl() {}
    iterator_impl(const iterator_impl& other) { node_ = other.node_; }

    iterator_impl& operator=(const iterator_impl& other) {
      node_ = other.node_;
      return *this;
    }

    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<T, NodeTraits_, TagType, ListSizeOrder>;

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

    typename PtrTraits::RawPtrType node_ = nullptr;
  };

  template <typename BaseNodeTraits>
  struct AddGenericNodeState<BaseNodeTraits,
                             std::enable_if_t<internal::has_node_state_v<BaseNodeTraits>>>
      : public BaseNodeTraits {};

  template <typename BaseNodeTraits>
  struct AddGenericNodeState<BaseNodeTraits,
                             std::enable_if_t<!internal::has_node_state_v<BaseNodeTraits>>>
      : public BaseNodeTraits {
    static SinglyLinkedListNodeState<T>& node_state(typename PtrTraits::RefType obj) {
      return DefaultSinglyLinkedListTraits<T>::template node_state<TagType>(obj);
    }
  };

  // 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 T, typename NodeTraits = DefaultSinglyLinkedListTraits<T>,
          typename TagType = DefaultObjectTag>
using SizedSinglyLinkedList = SinglyLinkedList<T, NodeTraits, TagType, SizeOrder::Constant>;

// 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 T, typename TagType, typename NodeTraits = DefaultSinglyLinkedListTraits<T>>
using TaggedSinglyLinkedList = SinglyLinkedList<T, NodeTraits, TagType, SizeOrder::N>;

// SizedTaggedSinglyLinkedList<> is a variant of TaggedSinglyLinkedList which
// also specifies O(1) access size().
//
template <typename T, typename TagType, typename NodeTraits = DefaultSinglyLinkedListTraits<T>>
using SizedTaggedSinglyLinkedList = SinglyLinkedList<T, NodeTraits, TagType, SizeOrder::Constant>;

}  // namespace fbl

#endif  // FBL_INTRUSIVE_SINGLE_LIST_H_