blob: 4e8d25ea7ac8d180df848e68a7cd31f1903b19c1 [file] [log] [blame]
// 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.
#pragma once
#include <zircon/assert.h>
#include <fbl/intrusive_pointer_traits.h>
#include <fbl/macros.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 utils/intrusive_single_list.h for details.
//
// Additional functionality provided by a DoublyLinkedList<> includes...
// ++ O(k) 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(k) 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;
} // namespace tests
} // namespace intrusive_containers
template <typename T>
struct DoublyLinkedListNodeState {
using PtrTraits = internal::ContainerPtrTraits<T>;
typename PtrTraits::PtrType next_ = nullptr;
typename PtrTraits::RawPtrType prev_ = nullptr;
bool IsValid() const { return ((next_ == nullptr) == (prev_ == nullptr)); }
bool InContainer() const { return ((next_ != nullptr) && (prev_ != nullptr)); }
};
template <typename T>
struct DefaultDoublyLinkedListTraits {
using PtrTraits = internal::ContainerPtrTraits<T>;
static DoublyLinkedListNodeState<T>& node_state(typename PtrTraits::RefType obj) {
return obj.dll_node_state_;
}
};
template <typename T>
struct DoublyLinkedListable {
public:
bool InContainer() const { return dll_node_state_.InContainer(); }
private:
friend struct DefaultDoublyLinkedListTraits<T>;
DoublyLinkedListNodeState<T> dll_node_state_;
};
template <typename T, typename _NodeTraits = DefaultDoublyLinkedListTraits<T>>
class DoublyLinkedList {
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
using PtrTraits = internal::ContainerPtrTraits<T>;
using NodeTraits = _NodeTraits;
using NodeState = DoublyLinkedListNodeState<T>;
using PtrType = typename PtrTraits::PtrType;
using RawPtrType = typename PtrTraits::RawPtrType;
using RawPtrTraits = internal::ContainerPtrTraits<RawPtrType>;
using ValueType = typename PtrTraits::ValueType;
using CheckerType = ::fbl::tests::intrusive_containers::DoublyLinkedListChecker;
using ContainerType = DoublyLinkedList<T, 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 = false;
static constexpr bool IsAssociative = false;
static constexpr bool IsSequenced = true;
// Default construction gives an empty list.
constexpr DoublyLinkedList() { }
// 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<T, NodeTraits>&& other_list) {
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.
ZX_DEBUG_ASSERT(PtrTraits::IsManaged || is_empty());
clear();
PtrTraits::DetachSentinel(head_);
}
// Standard begin/end, cbegin/cend iterator accessors.
iterator begin() { return iterator(PtrTraits::GetRaw(head_)); }
const_iterator begin() const { return const_iterator(PtrTraits::GetRaw(head_)); }
const_iterator cbegin() const { return const_iterator(PtrTraits::GetRaw(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); }
// is_empty : True if the list has at least one element in it, false otherwise.
bool is_empty() const { return PtrTraits::IsSentinel(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(PtrTraits::GetRaw(head_), fbl::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(), fbl::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_, fbl::move(ptr));
}
void insert(ValueType& before, const PtrType& ptr) { insert(before, PtrType(ptr)); }
void insert(ValueType& before, PtrType&& ptr) {
internal_insert(&before, fbl::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 == PtrTraits::GetRaw(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(PtrTraits::IsSentinel(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 = (PtrTraits::GetRaw(head_) == before)
? head_
: PtrTraits::IsSentinel(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.
PtrTraits::DetachSentinel(other_tail_ns.next_);
other_tail_ns.next_ = PtrTraits::Take(tgt_next);
tgt_next = PtrTraits::Take(other_list.head_);
other_list.head_ = PtrTraits::MakeSentinel(&other_list);
}
// 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(PtrTraits::GetRaw(ns.next_), fbl::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(PtrTraits::GetRaw(head_)); }
PtrType pop_back() { return internal_erase(tail()); }
// erase and erase_next
//
// Erase the element either at the provided iterator, or immediately after
// the provided iterator. Remove the element in the list either at iter, or
// which follows iter. 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_); }
PtrType erase_next(const iterator& iter) {
if (!iter.IsValid())
return PtrType(nullptr);
auto& ns = NodeTraits::node_state(*iter.node_);
if (PtrTraits::IsSentinel(ns.next_)) {
ZX_DEBUG_ASSERT(sentinel() == PtrTraits::GetRaw(ns.next_));
return PtrType(nullptr);
}
return internal_erase(PtrTraits::GetRaw(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_);
PtrTraits::Swap(head_, head_ns.next_);
head_ns.prev_ = nullptr;
PtrTraits::Take(head_ns.next_);
}
}
// 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");
head_ = PtrTraits::MakeSentinel(sentinel());
}
// swap : swaps the contest of two lists.
void swap(DoublyLinkedList<T, NodeTraits>& other) {
PtrTraits::Swap(head_, other.head_);
PtrType& sentinel_ptr = is_empty() ? head_ : NodeTraits::node_state(*tail()).next_;
PtrType& other_sentinel_ptr = other.is_empty()
? other.head_
: NodeTraits::node_state(*other.tail()).next_;
PtrTraits::Swap(sentinel_ptr, other_sentinel_ptr);
}
// size_slow : count the elements in the list in O(n) fashion
size_t size_slow() const {
size_t size = 0;
for (auto iter = cbegin(); iter != cend(); ++iter) {
size++;
}
return size;
}
// 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 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 fbl::move(ptr);
return internal_swap(*iter, fbl::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, fbl::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 !PtrTraits::IsSentinel(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_ = PtrTraits::GetRaw(ns.next_);
ZX_DEBUG_ASSERT(node_ != nullptr);
}
return *this;
}
iterator_impl& operator--() {
if (node_) {
if (PtrTraits::IsSentinel(node_)) {
ListPtrType list = GetList();
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 (PtrTraits::IsSentinel(new_ns.next_))
node_ = PtrTraits::GetRaw(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<T, NodeTraits>;
using ListPtrType = const DoublyLinkedList<T, NodeTraits>*;
iterator_impl(const typename PtrTraits::RawPtrType node)
: node_(const_cast<typename PtrTraits::RawPtrType>(node)) { }
ListPtrType GetList() const {
return reinterpret_cast<ListPtrType>(
reinterpret_cast<uintptr_t>(node_) & ~internal::kContainerSentinelBit);
}
typename PtrTraits::RawPtrType node_ = nullptr;
};
// The test framework's 'checker' class is our friend.
friend CheckerType;
// move semantics only
DISALLOW_COPY_AND_ASSIGN_ALLOW_MOVE(DoublyLinkedList);
constexpr RawPtrType sentinel() const {
return reinterpret_cast<RawPtrType>(
reinterpret_cast<uintptr_t>(this) | internal::kContainerSentinelBit);
}
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));
// Handle the (slightly) special case of an empty list.
if (is_empty()) {
ZX_DEBUG_ASSERT(before == sentinel());
ZX_DEBUG_ASSERT(before == PtrTraits::GetRaw(head_));
ptr_ns.prev_ = PtrTraits::GetRaw(ptr);
ptr_ns.next_ = fbl::move(head_);
head_ = fbl::move(ptr);
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(PtrTraits::IsSentinel(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 = (PtrTraits::GetRaw(head_) == before)
? head_
: PtrTraits::IsSentinel(before) ? NodeTraits::node_state(*tail()).next_
: NodeTraits::node_state(*tgt_prev).next_;
// Update the prev pointers.
ptr_ns.prev_ = tgt_prev;
tgt_prev = PtrTraits::GetRaw(ptr);
// Update the next pointers.
ptr_ns.next_ = fbl::move(tgt_next);
tgt_next = fbl::move(ptr);
}
PtrType internal_erase(RawPtrType node) {
if (!node || PtrTraits::IsSentinel(node))
return PtrType(nullptr);
auto& node_ns = NodeTraits::node_state(*node);
ZX_DEBUG_ASSERT((node_ns.prev_ != nullptr) && (node_ns.next_ != nullptr));
// 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 "ptr".
auto& tgt_prev = PtrTraits::IsSentinel(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 removing 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 = PtrTraits::GetRaw(head_) == node
? head_
: NodeTraits::node_state(*node_ns.prev_).next_;
tgt_prev = node_ns.prev_;
node_ns.prev_ = nullptr;
PtrTraits::Swap(tgt_next, node_ns.next_);
return PtrTraits::Take(node_ns.next_);
}
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(PtrTraits::IsValid(head_));
if (PtrTraits::IsSentinel(NodeTraits::node_state(*head_).next_)) {
ZX_DEBUG_ASSERT(PtrTraits::GetRaw(head_) == &node);
ZX_DEBUG_ASSERT(PtrTraits::IsSentinel(node_ns.next_));
ZX_DEBUG_ASSERT(&node == node_ns.prev_);
ptr_ns.prev_ = PtrTraits::GetRaw(ptr);
node_ns.prev_ = nullptr;
PtrTraits::Swap(ptr_ns.next_, node_ns.next_);
PtrTraits::Swap(head_, ptr);
return fbl::move(ptr);
}
// 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 = PtrTraits::IsSentinel(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 = PtrTraits::GetRaw(head_) == &node
? head_
: NodeTraits::node_state(*node_ns.prev_).next_;
PtrTraits::Swap(ptr_ns.next_, node_ns.next_);
RawPtrTraits::Swap(ptr_ns.prev_, node_ns.prev_);
tgt_prev = PtrTraits::GetRaw(ptr);
PtrTraits::Swap(tgt_next, ptr);
return fbl::move(ptr);
}
RawPtrType tail() const {
ZX_DEBUG_ASSERT(head_ != nullptr);
if (PtrTraits::IsSentinel(head_))
return PtrTraits::GetRaw(head_);
return NodeTraits::node_state(*head_).prev_;
}
// State consists of managed 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.
PtrType head_ = PtrTraits::MakeSentinel(this);
};
// Explicit declaration of constexpr storage.
template <typename T, typename NodeTraits>
constexpr bool DoublyLinkedList<T, NodeTraits>::SupportsConstantOrderErase;
template <typename T, typename NodeTraits>
constexpr bool DoublyLinkedList<T, NodeTraits>::SupportsConstantOrderSize;
template <typename T, typename NodeTraits>
constexpr bool DoublyLinkedList<T, NodeTraits>::IsAssociative;
template <typename T, typename NodeTraits>
constexpr bool DoublyLinkedList<T, NodeTraits>::IsSequenced;
} // namespace fbl