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 "pw_assert/check.h" 18 19 namespace pw::intrusive_list_impl { 20 unlist(Item * prev)21void List::Item::unlist(Item* prev) { 22 if (prev == nullptr) { 23 prev = previous(); 24 } 25 // Skip over this. 26 prev->next_ = next_; 27 28 // Retain the invariant that unlisted items are self-cycles. 29 next_ = this; 30 } 31 previous()32List::Item* List::Item::previous() { 33 // Follow the cycle around to find the previous element; O(N). 34 Item* prev = next_; 35 while (prev->next_ != this) { 36 prev = prev->next_; 37 } 38 return prev; 39 } 40 insert_after(Item * pos,Item & item)41void List::insert_after(Item* pos, Item& item) { 42 PW_CHECK( 43 item.unlisted(), 44 "Cannot add an item to a pw::IntrusiveList that is already in a list"); 45 item.next_ = pos->next_; 46 pos->next_ = &item; 47 } 48 erase_after(Item * pos)49void List::erase_after(Item* pos) { pos->next_->unlist(pos); } 50 before_end()51List::Item* List::before_end() noexcept { return before_begin()->previous(); } 52 clear()53void List::clear() { 54 while (!empty()) { 55 erase_after(before_begin()); 56 } 57 } 58 remove(const Item & item_to_remove)59bool List::remove(const Item& item_to_remove) { 60 for (Item* pos = before_begin(); pos->next_ != end(); pos = pos->next_) { 61 if (pos->next_ == &item_to_remove) { 62 erase_after(pos); 63 return true; 64 } 65 } 66 return false; 67 } 68 size() const69size_t List::size() const { 70 size_t total = 0; 71 Item* item = head_.next_; 72 while (item != &head_) { 73 item = item->next_; 74 total++; 75 } 76 return total; 77 } 78 79 } // namespace pw::intrusive_list_impl 80