chromium/v8/src/base/doubly-threaded-list.h

// Copyright 2023 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_BASE_DOUBLY_THREADED_LIST_H_
#define V8_BASE_DOUBLY_THREADED_LIST_H_

#include "src/base/compiler-specific.h"
#include "src/base/iterator.h"
#include "src/base/logging.h"

namespace v8::base {

template <typename T>
struct DoublyThreadedListTraits { … };

// `DoublyThreadedList` is an intrusive doubly-linked list that threads through
// its nodes, somewhat like `v8::base::ThreadedList`.
//
// Of interest is the fact that instead of having regular next/prev pointers,
// nodes have a regular "next" pointer, but their "prev" pointer contains the
// address of the "next" of the previous element. This way, removing an element
// doesn't require special treatment for the head of the list, and does not
// even require to know the head of the list.
template <class T, class DTLTraits = DoublyThreadedListTraits<T>>
class DoublyThreadedList {
 public:
  // Since C++17, it is possible to have a sentinel end-iterator that is not an
  // iterator itself.
  class end_iterator {};

  class iterator : public base::iterator<std::forward_iterator_tag, T> {
   public:
    explicit iterator(T head) : curr_(head) {}

    T operator*() { return curr_; }

    iterator& operator++() {
      DCHECK(DTLTraits::non_empty(curr_));
      curr_ = *DTLTraits::next(curr_);
      return *this;
    }

    iterator operator++(int) {
      DCHECK(DTLTraits::non_empty(curr_));
      iterator tmp(*this);
      operator++();
      return tmp;
    }

    bool operator==(end_iterator) { return !DTLTraits::non_empty(curr_); }
    bool operator!=(end_iterator) { return DTLTraits::non_empty(curr_); }

   private:
    friend DoublyThreadedList;
    T curr_;
  };

  // Removes `x` from the list. Iterators that are currently on `x` are
  // invalidated. To remove while iterating, use RemoveAt.
  static void Remove(T x) { … }

  DoublyThreadedList() = default;

  // Defining move constructor so that when resizing container, the prev pointer
  // of the next(head_) doesn't point to the old head_ but rather to the new
  // one.
  DoublyThreadedList(DoublyThreadedList&& other) V8_NOEXCEPT { … }

  // Add `x` at the beginning of the list. `x` will not be visible to any
  // existing iterator. Does not invalidate any existing iterator.
  void PushFront(T x) { … }

  T Front() const { … }

  void PopFront() { … }

  bool empty() const { … }

  iterator begin() const { … }
  end_iterator end() const { … }

  // Removes the element at `it`, and make `it` point to the next element.
  // Iterators on the same element as `it` are invalidated. Other iterators are
  // not affected.
  iterator RemoveAt(iterator& it) { … }

  bool ContainsSlow(T needle) const { … }

 private:
  static bool empty(T x) { … }
  T head_{};
};

}  // namespace v8::base

#endif  // V8_BASE_DOUBLY_THREADED_LIST_H_