intrusive_list.h

// Copyright 2024 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 <limits>
#include <type_traits>
 
#include "pw_containers/internal/intrusive_item.h"
#include "pw_containers/internal/intrusive_list_item.h"
 
namespace pw::containers::internal {
 
template <typename Item>
class GenericIntrusiveList {
 public:
  static_assert(std::is_same_v<Item, IntrusiveForwardListItem> ||
                std::is_same_v<Item, IntrusiveListItem>);
 
  constexpr GenericIntrusiveList() : head_() {}
 
  template <typename Iterator>
  GenericIntrusiveList(Iterator first, Iterator last) : GenericIntrusiveList() {
    insert_after(&head_, first, last);
  }
 
  // Intrusive lists cannot be copied, since each Item can only be in one list.
  GenericIntrusiveList(const GenericIntrusiveList&) = delete;
  GenericIntrusiveList& operator=(const GenericIntrusiveList&) = delete;
 
  // Moves the other list's contents into this list.
  GenericIntrusiveList(GenericIntrusiveList&& other) {
    head_.replace(other.head_);
  }
 
  // Clears this list and moves the other list's contents into it.
  GenericIntrusiveList& operator=(GenericIntrusiveList&& other) {
    clear();
    head_.replace(other.head_);
    return *this;
  }
 
  ~GenericIntrusiveList() { CheckIntrusiveContainerIsEmpty(empty()); }
 
  template <typename Iterator>
  void assign(Iterator first, Iterator last) {
    clear();
    insert_after(&head_, first, last);
  }
 
  // Iterators
 
  constexpr Item* before_begin() noexcept { return &head_; }
  constexpr const Item* before_begin() const noexcept { return &head_; }
 
  constexpr Item* begin() noexcept { return head_.next_; }
  constexpr const Item* begin() const noexcept { return head_.next_; }
 
  Item* before_end() noexcept { return before_begin()->previous(); }
 
  constexpr Item* end() noexcept { return &head_; }
  constexpr const Item* end() const noexcept { return &head_; }
 
  // Capacity
 
  bool empty() const noexcept { return begin() == end(); }
 
  constexpr size_t max_size() const noexcept {
    return std::numeric_limits<ptrdiff_t>::max();
  }
 
  // Modifiers
 
  void clear() {
    while (!empty()) {
      erase_after(before_begin());
    }
  }
 
  static Item* insert_after(Item* prev, Item& item) {
    CheckIntrusiveItemIsUncontained(item.unlisted());
    item.next_ = prev->next_;
    item.set_previous(prev);
    prev->next_ = &item;
    item.next_->set_previous(&item);
    return &item;
  }
 
  template <typename Iterator>
  static Item* insert_after(Item* prev, Iterator first, Iterator last) {
    for (Iterator it = first; it != last; ++it) {
      prev = insert_after(prev, *(FromIterator(it)));
    }
    return prev;
  }
 
  static Item* erase_after(Item* item) {
    item->next_->unlist(item);
    return item->next_;
  }
 
  static Item* erase_after(Item* first, Item* last) {
    while (first->next_ != last) {
      erase_after(first);
    }
    return last;
  }
 
  // Exchanges this list's items with the `other` list's items. O(1) for
  // IntrusiveList, O(n) for IntrusiveForwardList.
  void swap(GenericIntrusiveList<Item>& other) {
    Item tmp;
    tmp.replace(head_);
    head_.replace(other.head_);
    other.head_.replace(tmp);
  }
 
  // Operations
 
  template <typename Compare>
  void merge(GenericIntrusiveList<Item>& other, Compare comp) {
    Item* prev = before_begin();
    Item* item = begin();
    Item* other_item = other.begin();
    while (!other.empty()) {
      if (item == end() || !comp(*item, *other_item)) {
        Item* tmp = other_item;
        other_item = other.erase_after(other.before_begin());
        prev = insert_after(prev, *tmp);
      } else {
        prev = item;
        item = item->next_;
      }
    }
  }
 
  static void splice_after(Item* pos,
                           GenericIntrusiveList<Item>& other,
                           Item* first,
                           Item* last) {
    // Return if the range is empty, unless it is from before_begin to end.
    if (first == last && first != &other.head_) {
      return;
    }
    Item* first_next = first->next_;
    if (first_next == last) {
      return;
    }
    Item* last_prev = last->previous();
    Item* pos_next = pos->next_;
 
    first->next_ = last;
    last->set_previous(first);
 
    pos->next_ = first_next;
    first_next->set_previous(pos);
 
    pos_next->set_previous(last_prev);
    last_prev->next_ = pos_next;
  }
 
  // 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 Item& item_to_remove) {
    return remove_if(
               [&item_to_remove](const Item& item) -> bool {
                 return &item_to_remove == &item;
               },
               1) != 0;
  }
 
  template <typename UnaryPredicate>
  size_t remove_if(UnaryPredicate pred,
                   size_t max = std::numeric_limits<size_t>::max()) {
    size_t removed = 0;
    Item* prev = before_begin();
    while (true) {
      Item* item = prev->next_;
      if (item == end()) {
        break;
      }
      if (pred(*item)) {
        erase_after(prev);
        ++removed;
        if (removed == max) {
          break;
        }
      } else {
        prev = item;
      }
    }
    return removed;
  }
 
  void reverse() {
    GenericIntrusiveList<Item> list;
    while (!empty()) {
      Item* item = begin();
      erase_after(before_begin());
      list.insert_after(list.before_begin(), *item);
    }
    splice_after(before_begin(), list, list.before_begin(), list.end());
  }
 
  template <typename BinaryPredicate>
  size_t unique(BinaryPredicate pred) {
    if (empty()) {
      return 0;
    }
    size_t removed = 0;
    Item* prev = begin();
    while (true) {
      Item* item = prev->next_;
      if (item == end()) {
        break;
      }
      if (pred(*prev, *item)) {
        erase_after(prev);
        ++removed;
      } else {
        prev = item;
      }
    }
    return removed;
  }
 
  template <typename Compare>
  void sort(Compare comp) {
    Item* mid = begin();
    bool even = true;
    for (Item* item = begin(); item != end(); item = item->next_) {
      even = !even;
      if (even) {
        mid = mid->next_;
      }
    }
 
    // Partition the list.
    GenericIntrusiveList<Item> tmp;
    tmp.splice_after(tmp.before_begin(), *this, before_begin(), mid);
 
    // Check if trivially sorted.
    if (tmp.empty()) {
      return;
    }
 
    // Sort the sublists.
    tmp.sort(comp);
    sort(comp);
 
    // Merge the sublists.
    merge(tmp, comp);
  }
 
 private:
  template <typename Iterator>
  static Item* FromIterator(Iterator& it) {
    if constexpr (std::is_pointer<std::remove_reference_t<decltype(*it)>>()) {
      return *it;
    } else {
      return &(*it);
    }
  }
 
  // Use an Item for the head pointer. This gives simpler logic for inserting
  // elements compared to using an Item*. It also makes it possible to use
  // &head_ for end(), rather than nullptr. This makes end() unique for each
  // List and ensures that items already in a list cannot be added to another.
  Item head_;
};
 
}  // namespace pw::containers::internal