src/base/threaded-list.h

// Copyright 2018 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_THREADED_LIST_H_
#define V8_BASE_THREADED_LIST_H_

#include <iterator>

#include "src/base/compiler-specific.h"
#include "src/base/macros.h"

namespace v8 {
namespace base {

template <typename T>
struct ThreadedListTraits {
  static T** next(T* t) { return t->next(); }
  static T** start(T** t) { return t; }
  static T* const* start(T* const* t) { return t; }
};

// Represents a linked list that threads through the nodes in the linked list.
// Entries in the list are pointers to nodes. By default nodes need to have a
// T** next() method that returns the location where the next value is stored.
// The default can be overwritten by providing a ThreadedTraits class.
template <typename T, typename BaseClass,
          typename TLTraits = ThreadedListTraits<T>>
class ThreadedListBase final : public BaseClass {
 public:
  ThreadedListBase() : head_(nullptr), tail_(&head_) {}
  ThreadedListBase(const ThreadedListBase&) = delete;
  ThreadedListBase& operator=(const ThreadedListBase&) = delete;

  void Add(T* v) {
    DCHECK_NULL(*tail_);
    DCHECK_NULL(*TLTraits::next(v));
    *tail_ = v;
    tail_ = TLTraits::next(v);
    // Check that only one element was added (and that hasn't created a cycle).
    DCHECK_NULL(*tail_);
  }

  void AddFront(T* v) {
    DCHECK_NULL(*TLTraits::next(v));
    DCHECK_NOT_NULL(v);
    T** const next = TLTraits::next(v);

    *next = head_;
    if (head_ == nullptr) tail_ = next;
    head_ = v;
  }

  void DropHead() {
    DCHECK_NOT_NULL(head_);

    T* old_head = head_;
    head_ = *TLTraits::next(head_);
    if (head_ == nullptr) tail_ = &head_;
    *TLTraits::next(old_head) = nullptr;
  }

  bool Contains(T* v) {
    for (Iterator it = begin(); it != end(); ++it) {
      if (*it == v) return true;
    }
    return false;
  }

  void Append(ThreadedListBase&& list) {
    if (list.is_empty()) return;

    *tail_ = list.head_;
    tail_ = list.tail_;
    list.Clear();
  }

  void Prepend(ThreadedListBase&& list) {
    if (list.head_ == nullptr) return;

    T* new_head = list.head_;
    *list.tail_ = head_;
    if (head_ == nullptr) {
      tail_ = list.tail_;
    }
    head_ = new_head;
    list.Clear();
  }

  void Clear() {
    head_ = nullptr;
    tail_ = &head_;
  }

  ThreadedListBase& operator=(ThreadedListBase&& other) V8_NOEXCEPT {
    head_ = other.head_;
    tail_ = other.head_ ? other.tail_ : &head_;
#ifdef DEBUG
    other.Clear();
#endif
    return *this;
  }

  ThreadedListBase(ThreadedListBase&& other) V8_NOEXCEPT
      : head_(other.head_),
        tail_(other.head_ ? other.tail_ : &head_) {
#ifdef DEBUG
    other.Clear();
#endif
  }

  bool Remove(T* v) {
    T* current = first();
    if (current == v) {
      DropHead();
      return true;
    }

    while (current != nullptr) {
      T* next = *TLTraits::next(current);
      if (next == v) {
        *TLTraits::next(current) = *TLTraits::next(next);
        *TLTraits::next(next) = nullptr;

        if (TLTraits::next(next) == tail_) {
          tail_ = TLTraits::next(current);
        }
        return true;
      }
      current = next;
    }
    return false;
  }

  class Iterator final {
   public:
    using iterator_category = std::forward_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using value_type = T*;
    using reference = value_type;
    using pointer = value_type*;

   public:
    Iterator& operator++() {
      entry_ = TLTraits::next(*entry_);
      return *this;
    }
    bool operator==(const Iterator& other) const {
      return entry_ == other.entry_;
    }
    bool operator!=(const Iterator& other) const {
      return entry_ != other.entry_;
    }
    T*& operator*() { return *entry_; }
    T* operator->() { return *entry_; }
    Iterator& operator=(T* entry) {
      T* next = *TLTraits::next(*entry_);
      *TLTraits::next(entry) = next;
      *entry_ = entry;
      return *this;
    }

    bool is_null() { return entry_ == nullptr; }

    void InsertBefore(T* value) {
      T* old_entry_value = *entry_;
      *entry_ = value;
      entry_ = TLTraits::next(value);
      *entry_ = old_entry_value;
    }

    Iterator() : entry_(nullptr) {}

   private:
    explicit Iterator(T** entry) : entry_(entry) {}

    T** entry_;

    friend class ThreadedListBase;
  };

  class ConstIterator final {
   public:
    using iterator_category = std::forward_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using value_type = T*;
    using reference = const value_type;
    using pointer = const value_type*;

    // Allow implicit conversion to const iterator.
    // NOLINTNEXTLINE
    ConstIterator(Iterator& iterator) : entry_(iterator.entry_) {}

   public:
    ConstIterator& operator++() {
      entry_ = TLTraits::next(*entry_);
      return *this;
    }
    bool operator==(const ConstIterator& other) const {
      return entry_ == other.entry_;
    }
    bool operator!=(const ConstIterator& other) const {
      return entry_ != other.entry_;
    }
    const T* operator*() const { return *entry_; }

   private:
    explicit ConstIterator(T* const* entry) : entry_(entry) {}

    T* const* entry_;

    friend class ThreadedListBase;
  };

  Iterator begin() { return Iterator(TLTraits::start(&head_)); }
  Iterator end() { return Iterator(tail_); }

  ConstIterator begin() const { return ConstIterator(TLTraits::start(&head_)); }
  ConstIterator end() const { return ConstIterator(tail_); }

  // Rewinds the list's tail to the reset point, i.e., cutting of the rest of
  // the list, including the reset_point.
  void Rewind(Iterator reset_point) {
    tail_ = reset_point.entry_;
    *tail_ = nullptr;
  }

  // Moves the tail of the from_list, starting at the from_location, to the end
  // of this list.
  void MoveTail(ThreadedListBase* from_list, Iterator from_location) {
    if (from_list->end() != from_location) {
      DCHECK_NULL(*tail_);
      *tail_ = *from_location;
      tail_ = from_list->tail_;
      from_list->Rewind(from_location);
    }
  }

  bool is_empty() const { return head_ == nullptr; }

  T* first() const { return head_; }

  // Slow. For testing purposes.
  int LengthForTest() {
    int result = 0;
    for (Iterator t = begin(); t != end(); ++t) ++result;
    return result;
  }

  T* AtForTest(int i) {
    Iterator t = begin();
    while (i-- > 0) ++t;
    return *t;
  }

  bool Verify() {
    T* last = this->first();
    if (last == nullptr) {
      CHECK_EQ(&head_, tail_);
    } else {
      while (*TLTraits::next(last) != nullptr) {
        last = *TLTraits::next(last);
      }
      CHECK_EQ(TLTraits::next(last), tail_);
    }
    return true;
  }

  void RevalidateTail() {
    T* last = *tail_;
    if (last != nullptr) {
      while (*TLTraits::next(last) != nullptr) {
        last = *TLTraits::next(last);
      }
      tail_ = TLTraits::next(last);
    }
    SLOW_DCHECK(Verify());
  }

 private:
  T* head_;
  T** tail_;
};

struct EmptyBase {};

template <typename T, typename TLTraits = ThreadedListTraits<T>>
using ThreadedList = ThreadedListBase<T, EmptyBase, TLTraits>;

}  // namespace base
}  // namespace v8

#endif  // V8_BASE_THREADED_LIST_H_