| // Copyright 2021 The Pigweed Authors |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); you may not |
| // use this file except in compliance with the License. You may obtain a copy of |
| // the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT |
| // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the |
| // License for the specific language governing permissions and limitations under |
| // the License. |
| #pragma once |
| |
| #include <cstddef> |
| #include <initializer_list> |
| #include <type_traits> |
| |
| #include "pw_containers/internal/intrusive_list_impl.h" |
| |
| namespace pw { |
| |
| // IntrusiveList provides singly-linked list functionality for derived |
| // class items. IntrusiveList<T> is a handle to access and manipulate the |
| // list, and IntrusiveList<T>::Item is a base class items must inherit |
| // from. An instantiation of the derived class becomes a list item when inserted |
| // into a IntrusiveList. |
| // |
| // This has two important ramifications: |
| // |
| // - An instantiated IntrusiveList::Item must remain in scope for the |
| // lifetime of the IntrusiveList it has been added to. |
| // - A linked list item CANNOT be included in two lists, as it is part of a |
| // preexisting list and adding it to another implicitly breaks correctness of |
| // the first list. |
| // |
| // Usage: |
| // |
| // class TestItem |
| // : public IntrusiveList<TestItem>::Item {} |
| // |
| // IntrusiveList<TestItem> test_items; |
| // |
| // auto item = TestItem(); |
| // test_items.push_back(item); |
| // |
| // for (auto& test_item : test_items) { |
| // // Do a thing. |
| // } |
| // |
| template <typename T> |
| class IntrusiveList { |
| public: |
| class Item : public intrusive_list_impl::List::Item { |
| protected: |
| constexpr Item() = default; |
| |
| private: |
| // GetListElementTypeFromItem is used to find the element type from an item. |
| // It is used to ensure list items inherit from the correct Item type. |
| template <typename, bool> |
| friend struct intrusive_list_impl::GetListElementTypeFromItem; |
| |
| using PwIntrusiveListElementType = T; |
| }; |
| |
| using element_type = T; |
| using value_type = std::remove_cv_t<T>; |
| using pointer = T*; |
| using reference = T&; |
| using iterator = intrusive_list_impl::Iterator<T, Item>; |
| using const_iterator = |
| intrusive_list_impl::Iterator<std::add_const_t<T>, const Item>; |
| |
| constexpr IntrusiveList() { CheckItemType(); } |
| |
| // Constructs an IntrusiveList from an iterator over Items. The iterator may |
| // dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g. |
| // from std::initializer_list<Item*>). |
| template <typename Iterator> |
| IntrusiveList(Iterator first, Iterator last) : list_(first, last) { |
| CheckItemType(); |
| } |
| |
| // Constructs an IntrusiveList from a std::initializer_list of pointers to |
| // items. |
| IntrusiveList(std::initializer_list<Item*> items) |
| : IntrusiveList(items.begin(), items.end()) {} |
| |
| template <typename Iterator> |
| void assign(Iterator first, Iterator last) { |
| list_.assign(first, last); |
| } |
| |
| void assign(std::initializer_list<Item*> items) { |
| list_.assign(items.begin(), items.end()); |
| } |
| |
| [[nodiscard]] bool empty() const noexcept { return list_.empty(); } |
| |
| void push_front(T& item) { list_.insert_after(list_.before_begin(), item); } |
| |
| void push_back(T& item) { list_.insert_after(list_.before_end(), item); } |
| |
| iterator insert_after(iterator pos, T& item) { |
| list_.insert_after(&(*pos), item); |
| return iterator(&item); |
| } |
| |
| // Removes the first item in the list. The list must not be empty. |
| void pop_front() { list_.erase_after(list_.before_begin()); } |
| |
| // Removes the item following pos from the list. The item is not destructed. |
| iterator erase_after(iterator pos) { |
| list_.erase_after(&(*pos)); |
| return ++pos; |
| } |
| |
| // Removes all items from the list. The items themselves are not destructed. |
| void clear() { list_.clear(); } |
| |
| // Removes this specific item from the list, if it is present. Finds the item |
| // by identity (address comparison) rather than value equality. Returns true |
| // if the item was removed; false if it was not present. |
| bool remove(const T& item) { return list_.remove(item); } |
| |
| // Reference to the first element in the list. Undefined behavior if empty(). |
| T& front() { return *static_cast<T*>(list_.begin()); } |
| |
| // Reference to the last element in the list. Undefined behavior if empty(). |
| T& back() { return *static_cast<T*>(list_.before_end()); } |
| |
| // As in std::forward_list, returns the iterator before the begin() iterator. |
| iterator before_begin() noexcept { |
| return iterator(static_cast<Item*>(list_.before_begin())); |
| } |
| const_iterator before_begin() const noexcept { |
| return const_iterator(static_cast<const Item*>(list_.before_begin())); |
| } |
| const_iterator cbefore_begin() const noexcept { return before_begin(); } |
| |
| iterator begin() noexcept { |
| return iterator(static_cast<Item*>(list_.begin())); |
| } |
| const_iterator begin() const noexcept { |
| return const_iterator(static_cast<const Item*>(list_.begin())); |
| } |
| const_iterator cbegin() const noexcept { return begin(); } |
| |
| iterator end() noexcept { return iterator(static_cast<Item*>(list_.end())); } |
| const_iterator end() const noexcept { |
| return const_iterator(static_cast<const Item*>(list_.end())); |
| } |
| const_iterator cend() const noexcept { return end(); } |
| |
| // Operation is O(size). |
| size_t size() const { return list_.size(); } |
| |
| private: |
| // Check that T is an Item in a function, since the class T will not be fully |
| // defined when the IntrusiveList<T> class is instantiated. |
| static constexpr void CheckItemType() { |
| static_assert( |
| std::is_base_of<intrusive_list_impl::ElementTypeFromItem<T>, T>(), |
| "IntrusiveList items must be derived from IntrusiveList<T>::Item, " |
| "where T is the item or one of its bases."); |
| } |
| |
| intrusive_list_impl::List list_; |
| }; |
| |
| } // namespace pw |