1 files changed, 267 insertions, 0 deletions
diff --git a/deps/v8/src/base/threaded-list.h b/deps/v8/src/base/threaded-list.h
new file mode 100644
index 0000000000..d54bcb8f70
--- /dev/null
+++ b/deps/v8/src/base/threaded-list.h
@@ -0,0 +1,267 @@
+// 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(); }
+};
+
+// 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_) {}
+  void Add(T* v) {
+    DCHECK_NULL(*tail_);
+    DCHECK_NULL(*TLTraits::next(v));
+    *tail_ = v;
+    tail_ = TLTraits::next(v);
+  }
+
+  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;
+  }
+
+  // Reinitializing the head to a new node, this costs O(n).
+  void ReinitializeHead(T* v) {
+    head_ = v;
+    T* current = v;
+    if (current != nullptr) {  // Find tail
+      T* tmp;
+      while ((tmp = *TLTraits::next(current))) {
+        current = tmp;
+      }
+      tail_ = TLTraits::next(current);
+    } else {
+      tail_ = &head_;
+    }
+  }
+
+  void DropHead() {
+    DCHECK_NOT_NULL(head_);
+
+    T* old_head = head_;
+    head_ = *TLTraits::next(head_);
+    if (head_ == nullptr) tail_ = &head_;
+    *TLTraits::next(old_head) = nullptr;
+  }
+
+  void Append(ThreadedListBase&& list) {
+    *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;
+    }
+
+   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*;
+
+   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(&head_); }
+  Iterator end() { return Iterator(tail_); }
+
+  ConstIterator begin() const { return ConstIterator(&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;
+  }
+
+ private:
+  T* head_;
+  T** tail_;
+  DISALLOW_COPY_AND_ASSIGN(ThreadedListBase);
+};
+
+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_