third_party/pigweed/repo/pw_containers/intrusive_list.cc

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