1 // Copyright 2020 The Pigweed Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 4 // use this file except in compliance with the License. You may obtain a copy of 5 // the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 12 // License for the specific language governing permissions and limitations under 13 // the License. 14 #pragma once 15 16 #include "pw_containers/intrusive_forward_list.h" 17 18 namespace pw::containers::internal { 19 20 /// The class named `IntrusiveList<T>` was originally singly-linked and much 21 /// closer to `IntrusiveForwardList<T>`. This class represents the original 22 /// behavior of that class in the following ways: 23 /// 24 /// * Items automatically unlist themselves on destruction. 25 /// * Items may be made movable. 26 /// * Lists automatically clear themselves on destruction. 27 /// * `size`, `back`, and `push_back` methods are provided, despite being O(n). 28 /// 29 /// TODO(b/362348318): This class is deprecated and not used for new code. 30 template <typename T> 31 class LegacyIntrusiveList : public IntrusiveForwardList<T> { 32 private: 33 using Base = IntrusiveForwardList<T>; 34 35 public: 36 class Item : public Base::Item { 37 public: ~Item()38 ~Item() { Base::Item::unlist(); } 39 40 protected: 41 constexpr explicit Item() = default; 42 Item(Item && other)43 Item(Item&& other) : Item() { *this = std::move(other); } 44 Item& operator=(Item&& other) { 45 Base::replace(other); 46 return *this; 47 } 48 }; 49 50 constexpr LegacyIntrusiveList() = default; 51 52 template <typename Iterator> LegacyIntrusiveList(Iterator first,Iterator last)53 LegacyIntrusiveList(Iterator first, Iterator last) : Base(first, last) {} 54 LegacyIntrusiveList(std::initializer_list<Item * > items)55 LegacyIntrusiveList(std::initializer_list<Item*> items) 56 : Base(items.begin(), items.end()) {} 57 ~LegacyIntrusiveList()58 ~LegacyIntrusiveList() { 59 // The legacy intrusive list unlisted the sentinel item on destruction. 60 Base::clear(); 61 } 62 63 /// Returns a reference to the last element in the list. 64 /// 65 /// Undefined behavior if empty(). Runs in O(n) time. back()66 T& back() { return *static_cast<T*>(Base::list_.before_end()); } 67 68 /// Returns the number of items in the list. 69 /// 70 /// Runs in O(n) time. size()71 size_t size() const { 72 return static_cast<size_t>(std::distance(Base::begin(), Base::end())); 73 } 74 75 /// Inserts an item at the end of the list. 76 /// 77 /// Runs in O(n) time. push_back(T & item)78 void push_back(T& item) { 79 Base::list_.insert_after(Base::list_.before_end(), item); 80 } 81 }; 82 83 } // namespace pw::containers::internal 84