blob: 56417a51888652e7560144aaa641e7fdf2ca6b03 [file] [log] [blame] [edit]
// 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_DOUBLE_LIST_H_
#define FBL_INTRUSIVE_DOUBLE_LIST_H_
#include <zircon/assert.h>
#include <utility>
#include <fbl/algorithm.h>
#include <fbl/intrusive_container_node_utils.h>
#include <fbl/intrusive_container_utils.h>
#include <fbl/intrusive_pointer_traits.h>
// Usage and Implementation Notes:
//
// fbl::DoublyLinkedList<> is a templated intrusive container class which
// allows users to manage doubly linked lists of objects.
//
// fbl::DoublyLinkedList<> follows the same patterns as
// fbl::SinglyLinkedList<> and implements a superset of the functionality
// (including support for managed pointer types). Please refer to the "Usage
// Notes" section of fbl/intrusive_single_list.h for details.
//
// Additional functionality provided by a DoublyLinkedList<> includes...
// ++ O(1) push_back/pop_back/back (in addition to push_front/pop_front/front)
// ++ The ability to "insert" in addition to "insert_after"
// ++ The ability to "erase" in addition to "erase_next"
// ++ Support for bidirectional iteration.
//
// Under the hood, the state of a DoublyLinkedList<> contains a single raw
// pointer to the object which is the head of the list, or nullptr if the list
// is empty. Each object on the list has a DoublyLinkedListNodeState<> which
// contains one raw pointer (prev) and one managed pointer (next) which are
// arranged in a ring. The tail of a non-empty list can be found in O(1) time
// by following the prev pointer of the head node of the list.
namespace fbl {
// Fwd decl of sanity checker class used by tests.
namespace tests {
namespace intrusive_containers {
class DoublyLinkedListChecker;
template <typename>
class SequenceContainerTestEnvironment;
} // namespace intrusive_containers
} // namespace tests
// fwd decl of the list base class.
namespace internal {
template <typename PtrType>
class DoublyLinkedListBase;
}
template <typename PtrType_, NodeOptions Options = NodeOptions::None>
struct DoublyLinkedListNodeState
: public internal::CommonNodeStateBase<DoublyLinkedListNodeState<PtrType_, Options>> {
private:
using Base = internal::CommonNodeStateBase<DoublyLinkedListNodeState<PtrType_, Options>>;
public:
using PtrType = PtrType_;
using PtrTraits = internal::ContainerPtrTraits<PtrType>;
static constexpr NodeOptions kNodeOptions = Options;
constexpr DoublyLinkedListNodeState() {}
~DoublyLinkedListNodeState() {
ZX_DEBUG_ASSERT(IsValid());
if constexpr (!(kNodeOptions & fbl::NodeOptions::AllowClearUnsafe)) {
ZX_DEBUG_ASSERT(!InContainer());
}
}
bool IsValid() const { return ((next_ == nullptr) == (prev_ == nullptr)); }
bool InContainer() const { return (next_ != nullptr); }
template <typename NodeTraits>
PtrType_ RemoveFromContainer() {
static_assert(kNodeOptions & NodeOptions::AllowRemoveFromContainer,
"Node does not support direct RemoveFromContainer operations");
return internal::DoublyLinkedListBase<PtrType_>::template internal_erase<NodeTraits>(*this);
}
// 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.
DoublyLinkedListNodeState(const DoublyLinkedListNodeState& other) : Base(other) {}
DoublyLinkedListNodeState& operator=(const DoublyLinkedListNodeState& other) {
this->Base::operator=(other);
return *this;
}
DoublyLinkedListNodeState(DoublyLinkedListNodeState&& other) : Base(std::move(other)) {}
DoublyLinkedListNodeState& operator=(DoublyLinkedListNodeState&& other) {
this->Base::operator=(std::move(other));
return *this;
}
private:
template <typename, typename, SizeOrder, typename>
friend class DoublyLinkedList;
template <typename>
friend class internal::DoublyLinkedListBase;
template <typename>
friend class tests::intrusive_containers::SequenceContainerTestEnvironment;
friend class tests::intrusive_containers::DoublyLinkedListChecker;
typename PtrTraits::RawPtrType next_ = nullptr;
typename PtrTraits::RawPtrType prev_ = nullptr;
};
template <typename PtrType, NodeOptions Options, typename TagType>
struct DoublyLinkedListable;
template <typename PtrType_, typename TagType_>
struct DefaultDoublyLinkedListTraits {
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::dll_node_state_;
} else {
return obj.template GetContainableByTag<TagType>().dll_node_state_;
}
}
using NodeState =
std::decay_t<std::invoke_result_t<decltype(node_state), typename PtrTraits::RefType>>;
};
template <typename PtrType_, NodeOptions Options = NodeOptions::None,
typename TagType_ = DefaultObjectTag>
struct DoublyLinkedListable {
public:
using PtrType = PtrType_;
using TagType = TagType_;
static constexpr NodeOptions kNodeOptions = Options;
bool InContainer() const {
using Node = DoublyLinkedListable<PtrType, Options, TagType>;
return Node::dll_node_state_.InContainer();
}
PtrType RemoveFromContainer() {
using ListTraits = DefaultDoublyLinkedListTraits<PtrType, TagType_>;
return dll_node_state_.template RemoveFromContainer<ListTraits>();
}
private:
friend struct DefaultDoublyLinkedListTraits<PtrType, TagType>;
DoublyLinkedListNodeState<PtrType, Options> dll_node_state_;
};
namespace internal {
template <typename PtrType_>
class DoublyLinkedListBase {
public:
constexpr DoublyLinkedListBase() = default;
~DoublyLinkedListBase() {}
using PtrType = PtrType_;
using PtrTraits = internal::ContainerPtrTraits<PtrType>;
using RawPtrType = typename PtrTraits::RawPtrType;
protected:
template <typename, NodeOptions>
friend struct ::fbl::DoublyLinkedListNodeState;
template <typename NodeTraits, typename NodeStateType>
static PtrType internal_erase(NodeStateType& node_ns) {
// No one should be calling internal erase with an invalid node state, or a
// node state which is not in-container.
ZX_DEBUG_ASSERT(node_ns.IsValid() && node_ns.InContainer());
// Fetch the previous node's node state (this may be our own in the case
// that we are the only element on the list)
auto& prev_node_ns = NodeTraits::node_state(*node_ns.prev_);
// Find the prev pointer we need to update. If we are removing the tail
// of the list, the prev pointer is head_'s prev pointer. Otherwise, it
// is the prev pointer of the node which currently follows "next_"
auto& tgt_prev = internal::is_sentinel_ptr(node_ns.next_)
? NodeTraits::node_state(*head_from_sentinel(node_ns.next_)).prev_
: NodeTraits::node_state(*node_ns.next_).prev_;
// Find the next pointer we need to update. If the next_ pointer of the
// previous node state is a sentinel, removing the head of the list and the
// next_ pointer we need to update is actually the head_ for the list.
// Otherwise, it is simply the next_ pointer of the previous node state.
auto& tgt_next = internal::is_sentinel_ptr(prev_node_ns.next_)
? head_from_sentinel(prev_node_ns.next_)
: prev_node_ns.next_;
RawPtrType erased = tgt_next;
tgt_prev = node_ns.prev_;
tgt_next = node_ns.next_;
node_ns.prev_ = nullptr;
node_ns.next_ = nullptr;
return PtrTraits::Reclaim(erased);
}
constexpr RawPtrType sentinel() const { return internal::make_sentinel<RawPtrType>(this); }
// State consists of a raw pointer to the head of the list. Initially, this
// is set to the special sentinel value, which allows iterators set to
// this->end() to back up to the tail of the list.
RawPtrType head_ = sentinel();
private:
// Fetch a reference to the head_ member the list referenced by a sentinel
// value.
static RawPtrType& head_from_sentinel(RawPtrType node) {
return internal::unmake_sentinel<DoublyLinkedListBase<PtrType_>*>(node)->head_;
}
};
} // namespace internal
template <typename PtrType_, typename TagType_ = DefaultObjectTag,
SizeOrder ListSizeOrder_ = SizeOrder::N,
typename NodeTraits_ = DefaultDoublyLinkedListTraits<PtrType_, TagType_>>
class __POINTER(PtrType_) DoublyLinkedList : public internal::DoublyLinkedListBase<PtrType_>,
private internal::SizeTracker<ListSizeOrder_> {
private:
using Base = internal::DoublyLinkedListBase<PtrType_>;
// 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 typename Base::PtrType;
using TagType = TagType_;
using NodeTraits = NodeTraits_;
using typename Base::PtrTraits;
using typename Base::RawPtrType;
using ValueType = typename PtrTraits::ValueType;
using RefType = typename PtrTraits::RefType;
using CheckerType = ::fbl::tests::intrusive_containers::DoublyLinkedListChecker;
using ContainerType = DoublyLinkedList<PtrType_, TagType_, ListSizeOrder_, NodeTraits_>;
// Declarations of the standard iterator types.
using iterator = iterator_impl<iterator_traits>;
using const_iterator = iterator_impl<const_iterator_traits>;
// Doubly linked lists support constant order erase (erase using an iterator
// or direct object reference).
static constexpr bool SupportsConstantOrderErase = true;
static constexpr bool SupportsConstantOrderSize = (ListSizeOrder == SizeOrder::Constant);
static constexpr bool IsAssociative = false;
static constexpr bool IsSequenced = true;
// Default construction gives an empty list.
constexpr DoublyLinkedList() 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>,
"DoublyLinkedList's pointer type must match its Node's pointer type");
// Direct remove-from-container is only allowed if this list does not keep
// track of it's size.
static_assert((ListSizeOrder == SizeOrder::N) ||
!(NodeState::kNodeOptions & NodeOptions::AllowRemoveFromContainer),
"Nodes which allow RemoveFromContainer may not be used with DoublyLinkedLists "
"that track size");
}
// 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)
DoublyLinkedList(DoublyLinkedList&& other_list) noexcept : DoublyLinkedList() {
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.
DoublyLinkedList& operator=(DoublyLinkedList&& other_list) {
ZX_DEBUG_ASSERT(PtrTraits::IsManaged || is_empty());
clear();
swap(other_list);
return *this;
}
~DoublyLinkedList() {
// 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) { return iterator(&obj); }
const_iterator make_iterator(const ValueType& obj) const {
return const_iterator(&const_cast<ValueType&>(obj));
}
// is_empty : False if the list has at least one element in it, true 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_;
}
// back
//
// Return a reference to the element at the back of the list without
// removing it. It is an error to call back on an empty list.
typename PtrTraits::RefType back() {
ZX_DEBUG_ASSERT(!is_empty());
return *(NodeTraits::node_state(*head_).prev_);
}
typename PtrTraits::ConstRefType back() const {
ZX_DEBUG_ASSERT(!is_empty());
return *(NodeTraits::node_state(*head_).prev_);
}
// push_front : Push an element onto the front of the list.
void push_front(const PtrType& ptr) { push_front(PtrType(ptr)); }
void push_front(PtrType&& ptr) { internal_insert(head_, std::move(ptr)); }
// push_back : Push an element onto the end of the list.
void push_back(const PtrType& ptr) { push_back(PtrType(ptr)); }
void push_back(PtrType&& ptr) { internal_insert(sentinel(), std::move(ptr)); }
// insert : Insert an element before iter in the list.
void insert(const iterator& iter, const PtrType& ptr) { insert(iter, PtrType(ptr)); }
void insert(const iterator& iter, PtrType&& ptr) { internal_insert(iter.node_, std::move(ptr)); }
void insert(ValueType& before, const PtrType& ptr) { insert(before, PtrType(ptr)); }
void insert(ValueType& before, PtrType&& ptr) { internal_insert(&before, std::move(ptr)); }
// splice : Splice another list before iter in this list.
void splice(const iterator& iter, DoublyLinkedList& other_list) {
auto before = iter.node_;
ZX_DEBUG_ASSERT(before != nullptr);
ZX_DEBUG_ASSERT(head_ != nullptr);
if (other_list.is_empty()) {
return;
}
if (is_empty()) {
ZX_DEBUG_ASSERT(before == sentinel());
ZX_DEBUG_ASSERT(before == head_);
swap(other_list);
return;
}
// If we are being inserted before the sentinel, the we are the new
// tail, and the node_state which contains the prev pointer we need to
// update is head's. Otherwise, it is the node_state of the node we are
// being inserted before.
auto& prev_ns = NodeTraits::node_state(internal::is_sentinel_ptr(before) ? *head_ : *before);
auto& tgt_prev = prev_ns.prev_;
// If we are being inserted before the head, then we need to update the
// head pointer. Otherwise, we need to update the next pointer of the
// node which is about to come before us.
auto& tgt_next = (head_ == before) ? head_
: internal::is_sentinel_ptr(before) ? NodeTraits::node_state(*tail()).next_
: NodeTraits::node_state(*tgt_prev).next_;
auto& other_head_ns = NodeTraits::node_state(*other_list.head_);
auto other_tail = other_list.tail();
auto& other_tail_ns = NodeTraits::node_state(*other_tail);
// Update the prev pointers.
other_head_ns.prev_ = tgt_prev;
tgt_prev = other_tail;
// Update the next pointers.
other_tail_ns.next_ = tgt_next;
tgt_next = other_list.head_;
// Mark the other list as being empty now by replacing its head pointer
// with its sentinel value.
other_list.head_ = other_list.sentinel();
// Update our count bookkeeping. Note: don't attempt to access
// SizeTrackerCount() unless we are a list which supports constant order
// size. The method will not exist when we have O(N) access to our size.
if constexpr (ListSizeOrder == SizeOrder::Constant) {
this->IncSizeTracker(other_list.SizeTrackerCount());
other_list.ResetSizeTracker();
}
}
// 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 SizedDoublyLinkedLists");
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 5 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();
// B.prev : B is the new head of ret. Its prev points to ret.tail
// this.head.prev : A is the new tail of this. this.head.prev needs to point to it.
// this.tail.next : this.tail is now ret.tail, so this.tail.next = ret.sentinel()
ContainerType ret;
auto& B_ns = NodeTraits::node_state(*A_ns.next_);
auto& head_ns = NodeTraits::node_state(*head_);
auto& tail_ns = NodeTraits::node_state(*head_ns.prev_);
ret.head_ = A_ns.next_;
A_ns.next_ = this->sentinel();
B_ns.prev_ = head_ns.prev_;
head_ns.prev_ = &obj;
tail_ns.next_ = ret.sentinel();
return ret;
}
// insert_after : Insert an element after iter in the list.
//
// Note: 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());
auto& ns = NodeTraits::node_state(*iter.node_);
internal_insert(ns.next_, std::move(ptr));
}
// pop_front and pop_back
//
// Removes either the head or the tail of the list and transfers the pointer
// to the caller. If the list is empty, return a nullptr instance of
// PtrType.
PtrType pop_front() { return internal_erase(head_); }
PtrType pop_back() { return internal_erase(tail()); }
// erase
//
// Remove the element at the provided iterator and return a pointer to the
// removed element. If there is no element in the list at this position
// (iter is end()), return a nullptr instance of PtrType. It is an error to
// attempt to use an iterator from a different instance of this list type to
// attempt to erase a node.
PtrType erase(ValueType& obj) { return internal_erase(&obj); }
PtrType erase(const iterator& iter) { return internal_erase(iter.node_); }
// 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()) It is an error to attempt to use an
// iterator from a different instance of this list type to attempt to erase
// a node.
PtrType erase_next(const iterator& iter) {
ZX_DEBUG_ASSERT(iter.IsValid());
auto& ns = NodeTraits::node_state(*iter.node_);
if (internal::is_sentinel_ptr(ns.next_)) {
ZX_DEBUG_ASSERT(sentinel() == ns.next_);
return PtrType(nullptr);
}
return internal_erase(ns.next_);
}
// 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_);
// Reclaim our pointer so that it will release its reference when it
// goes out of scope a the end of the loop. Note, this needs to be
// flagged as UNUSED because for unmanaged pointer types, nothing
// happens when the pointer goes out of scope.
__UNUSED auto tmp = PtrTraits::Reclaim(head_);
head_ = head_ns.next_;
head_ns.next_ = nullptr;
head_ns.prev_ = nullptr;
}
// Update our count bookkeeping.
this->ResetSizeTracker();
}
// clear_unsafe
//
// See comments in fbl/intrusive_single_list.h
// 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();
// Update our count bookkeeping.
this->ResetSizeTracker();
}
// swap : swaps the contest of two lists.
void swap(DoublyLinkedList& other) {
internal::Swap(head_, other.head_);
RawPtrType& sentinel_ptr = is_empty() ? head_ : NodeTraits::node_state(*tail()).next_;
RawPtrType& other_sentinel_ptr =
other.is_empty() ? other.head_ : NodeTraits::node_state(*other.tail()).next_;
sentinel_ptr = sentinel();
other_sentinel_ptr = other.sentinel();
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 element satisfies the predicate.
template <typename UnaryFn>
PtrType erase_if(UnaryFn fn) {
for (auto iter = begin(); iter != end(); ++iter)
if (fn(static_cast<typename PtrTraits::ConstRefType>(*iter)))
return erase(iter);
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) {
iterator iter = find_if(fn);
if (!iter.IsValid())
return nullptr;
return internal_swap(*iter, PtrType(ptr));
}
// 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) {
iterator iter = find_if(fn);
if (!iter.IsValid())
return std::move(ptr);
return internal_swap(*iter, std::move(ptr));
}
// replace (copy and move)
//
// Replaces the target member of the list with the given replacement.
PtrType replace(typename PtrTraits::RefType target, PtrType replacement) {
return internal_swap(target, std::move(replacement));
}
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 !internal::is_sentinel_ptr(node_) && (node_ != nullptr); }
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()) {
auto& ns = NodeTraits::node_state(*node_);
node_ = ns.next_;
ZX_DEBUG_ASSERT(node_ != nullptr);
}
return *this;
}
iterator_impl& operator--() {
if (node_) {
if (internal::is_sentinel_ptr(node_)) {
auto list = unmake_sentinel(node_);
node_ = list->tail();
} else {
auto& ns = NodeTraits::node_state(*node_);
node_ = ns.prev_;
ZX_DEBUG_ASSERT(node_ != nullptr);
// If backing up would put us at a node whose next pointer
// is a sentinel, the we have looped around the start of the
// list and are currently pointed at the tail of the list.
// Reset our internal pointer to point to the sentinel value
// instead.
auto& new_ns = NodeTraits::node_state(*node_);
if (internal::is_sentinel_ptr(new_ns.next_))
node_ = new_ns.next_;
}
}
return *this;
}
// Postfix
iterator_impl operator++(int) {
iterator_impl ret(*this);
++(*this);
return ret;
}
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 DoublyLinkedList<PtrType_, TagType_, ListSizeOrder_, NodeTraits_>;
using ListType = const DoublyLinkedList<PtrType_, TagType_, ListSizeOrder_, NodeTraits_>;
iterator_impl(const typename PtrTraits::RawPtrType node)
: node_(const_cast<typename PtrTraits::RawPtrType>(node)) {}
const ListType* unmake_sentinel(typename PtrTraits::RawPtrType p) {
return static_cast<const ListType*>(internal::unmake_sentinel<typename ListType::Base*>(p));
}
typename PtrTraits::RawPtrType node_ = nullptr;
};
// The test framework's 'checker' class is our friend.
friend CheckerType;
// move semantics only
DoublyLinkedList(const DoublyLinkedList&) = delete;
DoublyLinkedList& operator=(const DoublyLinkedList&) = delete;
constexpr RawPtrType sentinel() const { return internal::make_sentinel<RawPtrType>(this); }
void internal_insert(RawPtrType before, PtrType&& ptr) {
ZX_DEBUG_ASSERT(ptr != nullptr);
ZX_DEBUG_ASSERT(before != nullptr);
ZX_DEBUG_ASSERT(head_ != nullptr);
auto& ptr_ns = NodeTraits::node_state(*ptr);
ZX_DEBUG_ASSERT((ptr_ns.prev_ == nullptr) && (ptr_ns.next_ == nullptr));
// No matter what happens, we are going to be 1 larger after this operation.
this->IncSizeTracker(1);
// Handle the (slightly) special case of an empty list.
if (is_empty()) {
ZX_DEBUG_ASSERT(before == sentinel());
ZX_DEBUG_ASSERT(before == head_);
ptr_ns.prev_ = PtrTraits::Leak(ptr);
ptr_ns.next_ = head_;
head_ = ptr_ns.prev_;
return;
}
// If we are being inserted before the sentinel, the we are the new
// tail, and the node_state which contains the prev pointer we need to
// update is head's. Otherwise, it is the node_state of the node we are
// being inserted before.
auto& prev_ns = NodeTraits::node_state(internal::is_sentinel_ptr(before) ? *head_ : *before);
auto& tgt_prev = prev_ns.prev_;
// If we are being inserted before the head, then we need to update the
// managed head pointer. Otherwise, we need to update the next pointer
// of the node which is about to come before us.
auto& tgt_next = (head_ == before) ? head_
: internal::is_sentinel_ptr(before) ? NodeTraits::node_state(*tail()).next_
: NodeTraits::node_state(*tgt_prev).next_;
// Update the pointers in the inserted node.
ptr_ns.next_ = tgt_next;
ptr_ns.prev_ = tgt_prev;
// Update the pointers which should now point to the inserted node.
tgt_next = PtrTraits::GetRaw(ptr);
tgt_prev = PtrTraits::Leak(ptr);
}
PtrType internal_erase(RawPtrType node) {
if (!node || internal::is_sentinel_ptr(node)) {
return PtrType(nullptr);
}
// No matter what happens after this, we are going to be 1 smaller after this operation.
this->DecSizeTracker(1);
// Defer to our base implementation in order to remove this node.
return Base::template internal_erase<NodeTraits>(NodeTraits::node_state(*node));
}
PtrType internal_swap(typename PtrTraits::RefType node, PtrType&& ptr) {
ZX_DEBUG_ASSERT(ptr != nullptr);
auto& ptr_ns = NodeTraits::node_state(*ptr);
ZX_DEBUG_ASSERT(!ptr_ns.InContainer());
auto& node_ns = NodeTraits::node_state(node);
ZX_DEBUG_ASSERT(node_ns.InContainer());
// Handle the case of there being only a single node in the list.
ZX_DEBUG_ASSERT(internal::valid_sentinel_ptr(head_));
if (internal::is_sentinel_ptr(NodeTraits::node_state(*head_).next_)) {
ZX_DEBUG_ASSERT(head_ == &node);
ZX_DEBUG_ASSERT(internal::is_sentinel_ptr(node_ns.next_));
ZX_DEBUG_ASSERT(&node == node_ns.prev_);
ptr_ns.next_ = node_ns.next_;
ptr_ns.prev_ = PtrTraits::GetRaw(ptr);
node_ns.next_ = nullptr;
node_ns.prev_ = nullptr;
head_ = PtrTraits::Leak(ptr);
return PtrTraits::Reclaim(&node);
}
// Find the prev pointer we need to update. If we are swapping the tail
// of the list, the prev pointer is head_'s prev pointer. Otherwise, it
// is the prev pointer of the node which currently follows "ptr".
auto& tgt_prev = internal::is_sentinel_ptr(node_ns.next_)
? NodeTraits::node_state(*head_).prev_
: NodeTraits::node_state(*node_ns.next_).prev_;
// Find the next pointer we need to update. If we are swapping the
// head of the list, this is head_. Otherwise it is the next pointer of
// the node which comes before us in the list.
auto& tgt_next = (head_ == &node) ? head_ : NodeTraits::node_state(*node_ns.prev_).next_;
tgt_next = PtrTraits::Leak(ptr);
tgt_prev = tgt_next;
internal::Swap(ptr_ns.next_, node_ns.next_);
internal::Swap(ptr_ns.prev_, node_ns.prev_);
return PtrTraits::Reclaim(&node);
}
RawPtrType tail() const {
ZX_DEBUG_ASSERT(head_ != nullptr);
if (internal::is_sentinel_ptr(head_))
return head_;
return NodeTraits::node_state(*head_).prev_;
}
using Base::head_;
using Base::sentinel;
};
// SizedDoublyLinkedList<> is an alias for a DoublyLinkedList<> 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 = DefaultDoublyLinkedListTraits<PtrType, TagType>>
using SizedDoublyLinkedList = DoublyLinkedList<PtrType, TagType, SizeOrder::Constant, NodeTraits>;
// DoublyLinkedListCustomTraits<> is an alias for a DoublyLinkedList<> which makes is easier to
// define a DoublyLinkedList 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 DoublyLinkedListCustomTraits =
DoublyLinkedList<PtrType, DefaultObjectTag, ListSizeOrder, NodeTraits>;
// TaggedDoublyLinkedList<> 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 DoublyLinkedList<> 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 TaggedDoublyLinkedList = DoublyLinkedList<PtrType, TagType, SizeOrder::N,
DefaultDoublyLinkedListTraits<PtrType, TagType>>;
template <typename PtrType, typename TagType, NodeOptions Options = NodeOptions::None>
using TaggedDoublyLinkedListable = DoublyLinkedListable<PtrType, Options, TagType>;
} // namespace fbl
#endif // FBL_INTRUSIVE_DOUBLE_LIST_H_