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 15 #include "pw_containers/intrusive_list.h" 16 17 #include <utility> 18 19 #include "pw_assert/check.h" 20 21 namespace pw::intrusive_list_impl { 22 operator =(List::Item && other)23List::Item& List::Item::operator=(List::Item&& other) { 24 // Remove `this` object from its current list. 25 if (!unlisted()) { 26 unlist(); 27 } 28 // If `other` is listed, remove it from its list and put `this` in its place. 29 if (!other.unlisted()) { 30 List::Item* prev = other.previous(); 31 other.unlist(prev); 32 List::insert_after(prev, *this); 33 } 34 return *this; 35 } 36 unlist(Item * prev)37void List::Item::unlist(Item* prev) { 38 if (prev == nullptr) { 39 prev = previous(); 40 } 41 // Skip over this. 42 prev->next_ = next_; 43 44 // Retain the invariant that unlisted items are self-cycles. 45 next_ = this; 46 } 47 previous()48List::Item* List::Item::previous() { 49 // Follow the cycle around to find the previous element; O(N). 50 Item* prev = next_; 51 while (prev->next_ != this) { 52 prev = prev->next_; 53 } 54 return prev; 55 } 56 insert_after(Item * pos,Item & item)57void List::insert_after(Item* pos, Item& item) { 58 PW_CHECK( 59 item.unlisted(), 60 "Cannot add an item to a pw::IntrusiveList that is already in a list"); 61 item.next_ = pos->next_; 62 pos->next_ = &item; 63 } 64 erase_after(Item * pos)65void List::erase_after(Item* pos) { pos->next_->unlist(pos); } 66 before_end()67List::Item* List::before_end() noexcept { return before_begin()->previous(); } 68 clear()69void List::clear() { 70 while (!empty()) { 71 erase_after(before_begin()); 72 } 73 } 74 remove(const Item & item_to_remove)75bool List::remove(const Item& item_to_remove) { 76 for (Item* pos = before_begin(); pos->next_ != end(); pos = pos->next_) { 77 if (pos->next_ == &item_to_remove) { 78 erase_after(pos); 79 return true; 80 } 81 } 82 return false; 83 } 84 size() const85size_t List::size() const { 86 size_t total = 0; 87 Item* item = head_.next_; 88 while (item != &head_) { 89 item = item->next_; 90 total++; 91 } 92 return total; 93 } 94 95 } // namespace pw::intrusive_list_impl 96