• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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>
17 struct ThreadedListTraits {
nextThreadedListTraits18   static T** next(T* t) { return t->next(); }
startThreadedListTraits19   static T** start(T** t) { return t; }
startThreadedListTraits20   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:
ThreadedListBase()31   ThreadedListBase() : head_(nullptr), tail_(&head_) {}
32   ThreadedListBase(const ThreadedListBase&) = delete;
33   ThreadedListBase& operator=(const ThreadedListBase&) = delete;
34 
Add(T * v)35   void Add(T* v) {
36     DCHECK_NULL(*tail_);
37     DCHECK_NULL(*TLTraits::next(v));
38     *tail_ = v;
39     tail_ = TLTraits::next(v);
40     // Check that only one element was added (and that hasn't created a cycle).
41     DCHECK_NULL(*tail_);
42   }
43 
AddFront(T * v)44   void AddFront(T* v) {
45     DCHECK_NULL(*TLTraits::next(v));
46     DCHECK_NOT_NULL(v);
47     T** const next = TLTraits::next(v);
48 
49     *next = head_;
50     if (head_ == nullptr) tail_ = next;
51     head_ = v;
52   }
53 
DropHead()54   void DropHead() {
55     DCHECK_NOT_NULL(head_);
56 
57     T* old_head = head_;
58     head_ = *TLTraits::next(head_);
59     if (head_ == nullptr) tail_ = &head_;
60     *TLTraits::next(old_head) = nullptr;
61   }
62 
Contains(T * v)63   bool Contains(T* v) {
64     for (Iterator it = begin(); it != end(); ++it) {
65       if (*it == v) return true;
66     }
67     return false;
68   }
69 
Append(ThreadedListBase && list)70   void Append(ThreadedListBase&& list) {
71     if (list.is_empty()) return;
72 
73     *tail_ = list.head_;
74     tail_ = list.tail_;
75     list.Clear();
76   }
77 
Prepend(ThreadedListBase && list)78   void Prepend(ThreadedListBase&& list) {
79     if (list.head_ == nullptr) return;
80 
81     T* new_head = list.head_;
82     *list.tail_ = head_;
83     if (head_ == nullptr) {
84       tail_ = list.tail_;
85     }
86     head_ = new_head;
87     list.Clear();
88   }
89 
Clear()90   void Clear() {
91     head_ = nullptr;
92     tail_ = &head_;
93   }
94 
95   ThreadedListBase& operator=(ThreadedListBase&& other) V8_NOEXCEPT {
96     head_ = other.head_;
97     tail_ = other.head_ ? other.tail_ : &head_;
98 #ifdef DEBUG
99     other.Clear();
100 #endif
101     return *this;
102   }
103 
ThreadedListBase(ThreadedListBase && other)104   ThreadedListBase(ThreadedListBase&& other) V8_NOEXCEPT
105       : head_(other.head_),
106         tail_(other.head_ ? other.tail_ : &head_) {
107 #ifdef DEBUG
108     other.Clear();
109 #endif
110   }
111 
Remove(T * v)112   bool Remove(T* v) {
113     T* current = first();
114     if (current == v) {
115       DropHead();
116       return true;
117     }
118 
119     while (current != nullptr) {
120       T* next = *TLTraits::next(current);
121       if (next == v) {
122         *TLTraits::next(current) = *TLTraits::next(next);
123         *TLTraits::next(next) = nullptr;
124 
125         if (TLTraits::next(next) == tail_) {
126           tail_ = TLTraits::next(current);
127         }
128         return true;
129       }
130       current = next;
131     }
132     return false;
133   }
134 
135   class Iterator final {
136    public:
137     using iterator_category = std::forward_iterator_tag;
138     using difference_type = std::ptrdiff_t;
139     using value_type = T*;
140     using reference = value_type;
141     using pointer = value_type*;
142 
143    public:
144     Iterator& operator++() {
145       entry_ = TLTraits::next(*entry_);
146       return *this;
147     }
148     bool operator==(const Iterator& other) const {
149       return entry_ == other.entry_;
150     }
151     bool operator!=(const Iterator& other) const {
152       return entry_ != other.entry_;
153     }
154     T*& operator*() { return *entry_; }
155     T* operator->() { return *entry_; }
156     Iterator& operator=(T* entry) {
157       T* next = *TLTraits::next(*entry_);
158       *TLTraits::next(entry) = next;
159       *entry_ = entry;
160       return *this;
161     }
162 
Iterator()163     Iterator() : entry_(nullptr) {}
164 
165    private:
Iterator(T ** entry)166     explicit Iterator(T** entry) : entry_(entry) {}
167 
168     T** entry_;
169 
170     friend class ThreadedListBase;
171   };
172 
173   class ConstIterator final {
174    public:
175     using iterator_category = std::forward_iterator_tag;
176     using difference_type = std::ptrdiff_t;
177     using value_type = T*;
178     using reference = const value_type;
179     using pointer = const value_type*;
180 
181    public:
182     ConstIterator& operator++() {
183       entry_ = TLTraits::next(*entry_);
184       return *this;
185     }
186     bool operator==(const ConstIterator& other) const {
187       return entry_ == other.entry_;
188     }
189     bool operator!=(const ConstIterator& other) const {
190       return entry_ != other.entry_;
191     }
192     const T* operator*() const { return *entry_; }
193 
194    private:
ConstIterator(T * const * entry)195     explicit ConstIterator(T* const* entry) : entry_(entry) {}
196 
197     T* const* entry_;
198 
199     friend class ThreadedListBase;
200   };
201 
begin()202   Iterator begin() { return Iterator(TLTraits::start(&head_)); }
end()203   Iterator end() { return Iterator(tail_); }
204 
begin()205   ConstIterator begin() const { return ConstIterator(TLTraits::start(&head_)); }
end()206   ConstIterator end() const { return ConstIterator(tail_); }
207 
208   // Rewinds the list's tail to the reset point, i.e., cutting of the rest of
209   // the list, including the reset_point.
Rewind(Iterator reset_point)210   void Rewind(Iterator reset_point) {
211     tail_ = reset_point.entry_;
212     *tail_ = nullptr;
213   }
214 
215   // Moves the tail of the from_list, starting at the from_location, to the end
216   // of this list.
MoveTail(ThreadedListBase * from_list,Iterator from_location)217   void MoveTail(ThreadedListBase* from_list, Iterator from_location) {
218     if (from_list->end() != from_location) {
219       DCHECK_NULL(*tail_);
220       *tail_ = *from_location;
221       tail_ = from_list->tail_;
222       from_list->Rewind(from_location);
223     }
224   }
225 
is_empty()226   bool is_empty() const { return head_ == nullptr; }
227 
first()228   T* first() const { return head_; }
229 
230   // Slow. For testing purposes.
LengthForTest()231   int LengthForTest() {
232     int result = 0;
233     for (Iterator t = begin(); t != end(); ++t) ++result;
234     return result;
235   }
236 
AtForTest(int i)237   T* AtForTest(int i) {
238     Iterator t = begin();
239     while (i-- > 0) ++t;
240     return *t;
241   }
242 
Verify()243   bool Verify() {
244     T* last = this->first();
245     if (last == nullptr) {
246       CHECK_EQ(&head_, tail_);
247     } else {
248       while (*TLTraits::next(last) != nullptr) {
249         last = *TLTraits::next(last);
250       }
251       CHECK_EQ(TLTraits::next(last), tail_);
252     }
253     return true;
254   }
255 
256  private:
257   T* head_;
258   T** tail_;
259 };
260 
261 struct EmptyBase {};
262 
263 template <typename T, typename TLTraits = ThreadedListTraits<T>>
264 using ThreadedList = ThreadedListBase<T, EmptyBase, TLTraits>;
265 
266 }  // namespace base
267 }  // namespace v8
268 
269 #endif  // V8_BASE_THREADED_LIST_H_
270