V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
threaded-list.h
1 // Copyright 2018 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #ifndef V8_BASE_THREADED_LIST_H_
6 #define V8_BASE_THREADED_LIST_H_
7 
8 #include <iterator>
9 
10 #include "src/base/compiler-specific.h"
11 #include "src/base/macros.h"
12 
13 namespace v8 {
14 namespace base {
15 
16 template <typename T>
18  static T** next(T* t) { return t->next(); }
19  static T** start(T** t) { return t; }
20  static T* const* start(T* const* t) { return t; }
21 };
22 
23 // Represents a linked list that threads through the nodes in the linked list.
24 // Entries in the list are pointers to nodes. By default nodes need to have a
25 // T** next() method that returns the location where the next value is stored.
26 // The default can be overwritten by providing a ThreadedTraits class.
27 template <typename T, typename BaseClass,
28  typename TLTraits = ThreadedListTraits<T>>
29 class ThreadedListBase final : public BaseClass {
30  public:
31  ThreadedListBase() : head_(nullptr), tail_(&head_) {}
32  void Add(T* v) {
33  DCHECK_NULL(*tail_);
34  DCHECK_NULL(*TLTraits::next(v));
35  *tail_ = v;
36  tail_ = TLTraits::next(v);
37  }
38 
39  void AddFront(T* v) {
40  DCHECK_NULL(*TLTraits::next(v));
41  DCHECK_NOT_NULL(v);
42  T** const next = TLTraits::next(v);
43 
44  *next = head_;
45  if (head_ == nullptr) tail_ = next;
46  head_ = v;
47  }
48 
49  void DropHead() {
50  DCHECK_NOT_NULL(head_);
51 
52  T* old_head = head_;
53  head_ = *TLTraits::next(head_);
54  if (head_ == nullptr) tail_ = &head_;
55  *TLTraits::next(old_head) = nullptr;
56  }
57 
58  bool Contains(T* v) {
59  for (Iterator it = begin(); it != end(); ++it) {
60  if (*it == v) return true;
61  }
62  return false;
63  }
64 
65  void Append(ThreadedListBase&& list) {
66  if (list.is_empty()) return;
67 
68  *tail_ = list.head_;
69  tail_ = list.tail_;
70  list.Clear();
71  }
72 
73  void Prepend(ThreadedListBase&& list) {
74  if (list.head_ == nullptr) return;
75 
76  T* new_head = list.head_;
77  *list.tail_ = head_;
78  if (head_ == nullptr) {
79  tail_ = list.tail_;
80  }
81  head_ = new_head;
82  list.Clear();
83  }
84 
85  void Clear() {
86  head_ = nullptr;
87  tail_ = &head_;
88  }
89 
90  ThreadedListBase& operator=(ThreadedListBase&& other) V8_NOEXCEPT {
91  head_ = other.head_;
92  tail_ = other.head_ ? other.tail_ : &head_;
93 #ifdef DEBUG
94  other.Clear();
95 #endif
96  return *this;
97  }
98 
99  ThreadedListBase(ThreadedListBase&& other) V8_NOEXCEPT
100  : head_(other.head_),
101  tail_(other.head_ ? other.tail_ : &head_) {
102 #ifdef DEBUG
103  other.Clear();
104 #endif
105  }
106 
107  bool Remove(T* v) {
108  T* current = first();
109  if (current == v) {
110  DropHead();
111  return true;
112  }
113 
114  while (current != nullptr) {
115  T* next = *TLTraits::next(current);
116  if (next == v) {
117  *TLTraits::next(current) = *TLTraits::next(next);
118  *TLTraits::next(next) = nullptr;
119 
120  if (TLTraits::next(next) == tail_) {
121  tail_ = TLTraits::next(current);
122  }
123  return true;
124  }
125  current = next;
126  }
127  return false;
128  }
129 
130  class Iterator final {
131  public:
132  using iterator_category = std::forward_iterator_tag;
133  using difference_type = std::ptrdiff_t;
134  using value_type = T*;
135  using reference = value_type;
136  using pointer = value_type*;
137 
138  public:
139  Iterator& operator++() {
140  entry_ = TLTraits::next(*entry_);
141  return *this;
142  }
143  bool operator==(const Iterator& other) const {
144  return entry_ == other.entry_;
145  }
146  bool operator!=(const Iterator& other) const {
147  return entry_ != other.entry_;
148  }
149  T*& operator*() { return *entry_; }
150  T* operator->() { return *entry_; }
151  Iterator& operator=(T* entry) {
152  T* next = *TLTraits::next(*entry_);
153  *TLTraits::next(entry) = next;
154  *entry_ = entry;
155  return *this;
156  }
157 
158  Iterator() : entry_(nullptr) {}
159 
160  private:
161  explicit Iterator(T** entry) : entry_(entry) {}
162 
163  T** entry_;
164 
165  friend class ThreadedListBase;
166  };
167 
168  class ConstIterator final {
169  public:
170  using iterator_category = std::forward_iterator_tag;
171  using difference_type = std::ptrdiff_t;
172  using value_type = T*;
173  using reference = const value_type;
174  using pointer = const value_type*;
175 
176  public:
177  ConstIterator& operator++() {
178  entry_ = TLTraits::next(*entry_);
179  return *this;
180  }
181  bool operator==(const ConstIterator& other) const {
182  return entry_ == other.entry_;
183  }
184  bool operator!=(const ConstIterator& other) const {
185  return entry_ != other.entry_;
186  }
187  const T* operator*() const { return *entry_; }
188 
189  private:
190  explicit ConstIterator(T* const* entry) : entry_(entry) {}
191 
192  T* const* entry_;
193 
194  friend class ThreadedListBase;
195  };
196 
197  Iterator begin() { return Iterator(TLTraits::start(&head_)); }
198  Iterator end() { return Iterator(tail_); }
199 
200  ConstIterator begin() const { return ConstIterator(TLTraits::start(&head_)); }
201  ConstIterator end() const { return ConstIterator(tail_); }
202 
203  // Rewinds the list's tail to the reset point, i.e., cutting of the rest of
204  // the list, including the reset_point.
205  void Rewind(Iterator reset_point) {
206  tail_ = reset_point.entry_;
207  *tail_ = nullptr;
208  }
209 
210  // Moves the tail of the from_list, starting at the from_location, to the end
211  // of this list.
212  void MoveTail(ThreadedListBase* from_list, Iterator from_location) {
213  if (from_list->end() != from_location) {
214  DCHECK_NULL(*tail_);
215  *tail_ = *from_location;
216  tail_ = from_list->tail_;
217  from_list->Rewind(from_location);
218  }
219  }
220 
221  bool is_empty() const { return head_ == nullptr; }
222 
223  T* first() const { return head_; }
224 
225  // Slow. For testing purposes.
226  int LengthForTest() {
227  int result = 0;
228  for (Iterator t = begin(); t != end(); ++t) ++result;
229  return result;
230  }
231 
232  T* AtForTest(int i) {
233  Iterator t = begin();
234  while (i-- > 0) ++t;
235  return *t;
236  }
237 
238  bool Verify() {
239  T* last = this->first();
240  if (last == nullptr) {
241  CHECK_EQ(&head_, tail_);
242  } else {
243  while (*TLTraits::next(last) != nullptr) {
244  last = *TLTraits::next(last);
245  }
246  CHECK_EQ(TLTraits::next(last), tail_);
247  }
248  return true;
249  }
250 
251  private:
252  T* head_;
253  T** tail_;
254  DISALLOW_COPY_AND_ASSIGN(ThreadedListBase);
255 };
256 
257 struct EmptyBase {};
258 
259 template <typename T, typename TLTraits = ThreadedListTraits<T>>
261 
262 } // namespace base
263 } // namespace v8
264 
265 #endif // V8_BASE_THREADED_LIST_H_
Definition: libplatform.h:13