Line data Source code
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 {
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 32285728 : ThreadedListBase() : head_(nullptr), tail_(&head_) {}
32 4036210 : void Add(T* v) {
33 : DCHECK_NULL(*tail_);
34 : DCHECK_NULL(*TLTraits::next(v));
35 112513170 : *tail_ = v;
36 112513170 : tail_ = TLTraits::next(v);
37 4036210 : }
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 1 : *next = head_;
45 2 : if (head_ == nullptr) tail_ = next;
46 2 : head_ = v;
47 : }
48 :
49 3681 : void DropHead() {
50 : DCHECK_NOT_NULL(head_);
51 :
52 3681 : T* old_head = head_;
53 3685 : head_ = *TLTraits::next(head_);
54 3685 : if (head_ == nullptr) tail_ = &head_;
55 3685 : *TLTraits::next(old_head) = nullptr;
56 3681 : }
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 868 : if (list.is_empty()) return;
67 :
68 868 : *tail_ = list.head_;
69 868 : tail_ = list.tail_;
70 : list.Clear();
71 : }
72 :
73 : void Prepend(ThreadedListBase&& list) {
74 3562119 : if (list.head_ == nullptr) return;
75 :
76 : T* new_head = list.head_;
77 3562105 : *list.tail_ = head_;
78 3562105 : if (head_ == nullptr) {
79 1135705 : tail_ = list.tail_;
80 : }
81 3562105 : head_ = new_head;
82 : list.Clear();
83 : }
84 :
85 : void Clear() {
86 20776088 : head_ = nullptr;
87 20776088 : tail_ = &head_;
88 : }
89 :
90 : ThreadedListBase& operator=(ThreadedListBase&& other) V8_NOEXCEPT {
91 2504746 : head_ = other.head_;
92 2504746 : 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 4 : tail_(other.head_ ? other.tail_ : &head_) {
102 : #ifdef DEBUG
103 : other.Clear();
104 : #endif
105 : }
106 :
107 3687 : bool Remove(T* v) {
108 : T* current = first();
109 3687 : if (current == v) {
110 3681 : DropHead();
111 3684 : return true;
112 : }
113 :
114 4 : while (current != nullptr) {
115 3 : T* next = *TLTraits::next(current);
116 3 : if (next == v) {
117 2 : *TLTraits::next(current) = *TLTraits::next(next);
118 2 : *TLTraits::next(next) = nullptr;
119 :
120 2 : if (TLTraits::next(next) == tail_) {
121 1 : 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 22282873 : Iterator& operator++() {
140 104858858 : entry_ = TLTraits::next(*entry_);
141 22282873 : return *this;
142 : }
143 : bool operator==(const Iterator& other) const {
144 : return entry_ == other.entry_;
145 : }
146 11824304 : bool operator!=(const Iterator& other) const {
147 34997313 : return entry_ != other.entry_;
148 : }
149 : T*& operator*() { return *entry_; }
150 13906641 : 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 2564851 : 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 60793 : 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 60790 : 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 22743902 : Iterator begin() { return Iterator(TLTraits::start(&head_)); }
198 20634972 : Iterator end() { return Iterator(tail_); }
199 :
200 37931 : 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 139468 : tail_ = reset_point.entry_;
207 139468 : *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 267036 : if (from_list->end() != from_location) {
214 : DCHECK_NULL(*tail_);
215 5446 : *tail_ = *from_location;
216 5446 : 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 747 : for (Iterator t = begin(); t != end(); ++t) ++result;
229 : return result;
230 : }
231 :
232 : T* AtForTest(int i) {
233 : Iterator t = begin();
234 2243 : while (i-- > 0) ++t;
235 436 : return *t;
236 : }
237 :
238 97 : bool Verify() {
239 : T* last = this->first();
240 97 : if (last == nullptr) {
241 6 : CHECK_EQ(&head_, tail_);
242 : } else {
243 365 : while (*TLTraits::next(last) != nullptr) {
244 : last = *TLTraits::next(last);
245 : }
246 182 : CHECK_EQ(TLTraits::next(last), tail_);
247 : }
248 97 : 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>>
260 : using ThreadedList = ThreadedListBase<T, EmptyBase, TLTraits>;
261 :
262 : } // namespace base
263 : } // namespace v8
264 :
265 : #endif // V8_BASE_THREADED_LIST_H_
|
