pw_containers/public/pw_containers/intrusive_list.h

// Copyright 2020 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 <type_traits>

#include "pw_containers/internal/intrusive_list_impl.h"

namespace pw {

// IntrusiveList provides singly-linked list functionality for derived
// class items. IntrusiveList<T> is a handle to access and manipulate the
// list, and IntrusiveList<T>::Item is a base class items must inherit
// from. An instantiation of the derived class becomes a list item when inserted
// into a IntrusiveList.
//
// This has two important ramifications:
//
// - An instantiated IntrusiveList::Item must remain in scope for the
//   lifetime of the IntrusiveList it has been added to.
// - A linked list item CANNOT be included in two lists, as it is part of a
//   preexisting list and adding it to another implicitly breaks correctness of
//   the first list.
//
// Usage:
//
//   class TestItem
//      : public containers::IntrusiveList<TestItem>::Item {}
//
//   containers::IntrusiveList<TestItem> test_items;
//
//   auto item = TestItem();
//   test_items.push_back(item);
//
//   for (auto& test_item : test_items) {
//     // Do a thing.
//   }
template <typename T>
class IntrusiveList {
 public:
  class Item : public intrusive_list_impl::List::Item {
   public:
    constexpr Item() = default;
  };

  using element_type = T;
  using value_type = std::remove_cv_t<T>;
  using pointer = T*;
  using reference = T&;
  using iterator = intrusive_list_impl::Iterator<T, Item>;
  using const_iterator =
      intrusive_list_impl::Iterator<std::add_const_t<T>, const Item>;

  [[nodiscard]] bool empty() const noexcept { return list_.begin() == nullptr; }

  void push_back(T& item) { list_.push_back(item); }

  void push_front(T& item) { list_.push_front(item); }

  iterator insert_after(iterator pos, T& item) {
    return iterator(static_cast<Item*>(&list_.insert_after(&(*pos), item)));
  }

  void pop_front() { list_.pop_front(); }

  void clear() { list_.clear(); }

  T& front() { return *static_cast<T*>(list_.begin()); }

  iterator begin() noexcept {
    return iterator(static_cast<Item*>(list_.begin()));
  }
  const_iterator begin() const noexcept {
    return const_iterator(static_cast<const Item*>(list_.cbegin()));
  }
  const_iterator cbegin() const noexcept {
    return const_iterator(static_cast<const Item*>(list_.cbegin()));
  }

  iterator end() noexcept { return iterator(); }
  const_iterator end() const noexcept { return const_iterator(); }
  const_iterator cend() const noexcept { return const_iterator(); }

 private:
  intrusive_list_impl::List list_;
};

}  // namespace pw