| // 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_ |