1// Copyright (c) 2019, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_INTRUSIVE_DLIST_H_
6#define RUNTIME_VM_INTRUSIVE_DLIST_H_
7
8#include "platform/assert.h"
9#include "platform/globals.h"
10
11namespace dart {
12
13// Abstraction for "intrusive" doubly-linked list in a type-safe way in C++.
14//
15// By "intrusive" we mean that a class Item containing various field members
16// has also next/previous pointers to the next/previous Item.
17//
18// To change a class Item to be part of such a doubly-linked list, one only
19// needs to inherit from IntrusiveDListEntry<Item> (in addition to the normal
20// base class).
21//
22// To change a class Item to be part of multiple doubly-linked lists, one can
23// inherit multiple times from IntrusiveDListEntry<Item, N>, each time with a
24// different value for <N>.
25//
26// To insert an object into a list, one uses a IntrusiveDList<Item, N>. It
27// provides support for insertion/iteration/deletion.
28//
29// Usage example:
30//
31// class Base {
32// <arbitrary state here>
33// };
34//
35// class Item : public Base,
36// public IntrusiveDListEntry<Item>,
37// public IntrusiveDListEntry<Item, 2> {
38// <arbitrary state here>
39// };
40//
41// Item a1, a2, a3;
42//
43// IntrusiveDList<Item> all;
44// all.Append(a2);
45// all.Prepend(a1);
46// all.Append(a3);
47//
48// IntrusiveDList<Item, 2> idle, ready;
49// idle.Append(a1);
50// ready.Append(a2);
51// ready.Append(a3);
52//
53
54template <typename T, int N>
55class IntrusiveDList;
56
57template <typename T, int N = 1>
58class IntrusiveDListEntry {
59 public:
60 IntrusiveDListEntry() {}
61
62 ~IntrusiveDListEntry() {
63 // Either this is an unlinked entry or a head/anchor.
64 ASSERT((next_ == nullptr && prev_ == nullptr) ||
65 (next_ == this && prev_ == this));
66 }
67
68 private:
69 void MakeHead() {
70 ASSERT(next_ == nullptr && prev_ == nullptr);
71 next_ = prev_ = this;
72 }
73
74 // This uses the C++ compiler's ability to convert between classes inside a
75 // (possibly multi-) inheritance hierarchy.
76 //
77 // The non-typesafe C equivalent of this is:
78 //
79 // ((uint8*)this) - offsetof(ContainerType, list_entry);
80 //
81 T* container() { return static_cast<T*>(this); }
82
83 void Append(IntrusiveDListEntry<T, N>* entry) {
84 ASSERT(entry->next_ == nullptr && entry->prev_ == nullptr);
85 entry->next_ = next_;
86 entry->prev_ = this;
87 next_ = entry;
88 entry->next_->prev_ = entry;
89 }
90
91 void Prepend(IntrusiveDListEntry<T, N>* entry) {
92 ASSERT(entry->next_ == nullptr && entry->prev_ == nullptr);
93 entry->next_ = this;
94 entry->prev_ = prev_;
95 prev_ = entry;
96 entry->prev_->next_ = entry;
97 }
98
99 void Remove() {
100 ASSERT(prev_->next_ == this);
101 ASSERT(next_->prev_ == this);
102 ASSERT(prev_ != this && next_ != this);
103
104 prev_->next_ = next_;
105 next_->prev_ = prev_;
106
107 next_ = nullptr;
108 prev_ = nullptr;
109 }
110
111 bool IsEmpty() const {
112 bool result = next_ == this;
113 ASSERT(result == (prev_ == this));
114 return result;
115 }
116
117 bool IsLinked() const {
118 ASSERT((next_ == nullptr) == (prev_ == nullptr));
119 return next_ != nullptr;
120 }
121
122 IntrusiveDListEntry<T, N>* Prev() const { return prev_; }
123
124 IntrusiveDListEntry<T, N>* Next() const { return next_; }
125
126 friend class IntrusiveDList<T, N>;
127
128 IntrusiveDListEntry<T, N>* next_ = nullptr;
129 IntrusiveDListEntry<T, N>* prev_ = nullptr;
130
131 DISALLOW_COPY_AND_ASSIGN(IntrusiveDListEntry);
132};
133
134template <typename T, int N = 1>
135class IntrusiveDList {
136 public:
137 typedef IntrusiveDListEntry<T, N> Entry;
138
139 template <typename ContainerType, int I = 1>
140 class Iterator {
141 public:
142 Iterator(IntrusiveDList<ContainerType, I>* head,
143 IntrusiveDListEntry<ContainerType, I>* entry)
144 : head_(head), entry_(entry) {}
145
146 inline ContainerType* operator->() const { return entry_->container(); }
147
148 inline ContainerType* operator*() const { return entry_->container(); }
149
150 inline bool operator==(const Iterator<ContainerType, I>& other) const {
151 return entry_ == other.entry_;
152 }
153
154 inline bool operator!=(const Iterator<ContainerType, I>& other) const {
155 return !(*this == other);
156 }
157
158 inline Iterator<ContainerType, I>& operator++() {
159 entry_ = entry_->Next();
160 return *this;
161 }
162
163 inline Iterator<ContainerType, I>& operator--() {
164 entry_ = entry_->Prev();
165 return *this;
166 }
167
168 private:
169 friend IntrusiveDList;
170
171 IntrusiveDList<ContainerType, I>* head_;
172 IntrusiveDListEntry<ContainerType, I>* entry_;
173 };
174
175 inline IntrusiveDList() { head_.MakeHead(); }
176
177 inline void Append(T* a) { head_.Prepend(convert(a)); }
178
179 inline void Prepend(T* a) { head_.Append(convert(a)); }
180
181 // NOTE: This function only checks whether [a] is linked inside *a*
182 // [IntrusiveDList].
183 inline bool IsInList(T* a) const { return convert(a)->IsLinked(); }
184
185 inline void Remove(T* a) { convert(a)->Remove(); }
186
187 inline bool IsEmpty() const { return head_.IsEmpty(); }
188
189 inline T* First() const {
190 ASSERT(!IsEmpty());
191 return head_.Next()->container();
192 }
193
194 inline T* Last() const {
195 ASSERT(!IsEmpty());
196 return head_.Prev()->container();
197 }
198
199 inline T* RemoveFirst() {
200 ASSERT(!IsEmpty());
201 auto entry = head_.Next();
202 T* container = entry->container();
203 entry->Remove();
204 return container;
205 }
206
207 inline T* RemoveLast() {
208 ASSERT(!IsEmpty());
209 auto entry = head_.Prev();
210 T* container = entry->container();
211 entry->Remove();
212 return container;
213 }
214
215 inline Iterator<T, N> Begin() { return Iterator<T, N>(this, head_.Next()); }
216
217 inline Iterator<T, N> End() { return Iterator<T, N>(this, &head_); }
218
219 inline Iterator<T, N> begin() { return Begin(); }
220
221 inline Iterator<T, N> end() { return End(); }
222
223 inline Iterator<T, N> Erase(const Iterator<T, N>& iterator) {
224 ASSERT(iterator.head_ == this);
225 Iterator<T, N> next(this, iterator.entry_->Next());
226 iterator.entry_->Remove();
227 return next;
228 }
229
230 bool ContainsForDebugging(const T* a) {
231 for (auto entry : *this) {
232 if (entry == a) return true;
233 }
234 return false;
235 }
236
237 void AppendList(IntrusiveDList<T, N>* other) {
238 if (other->IsEmpty()) return;
239
240 auto other_first = other->head_.Next();
241 auto other_last = other->head_.Prev();
242 other->head_.next_ = &other->head_;
243 other->head_.prev_ = &other->head_;
244
245 auto prev = head_.prev_;
246
247 prev->next_ = other_first;
248 other_first->prev_ = prev;
249
250 other_last->next_ = &head_;
251 head_.prev_ = other_last;
252 }
253
254 private:
255 Entry head_;
256
257 Entry* convert(T* entry) const { return static_cast<Entry*>(entry); }
258};
259
260} // namespace dart.
261
262#endif // RUNTIME_VM_INTRUSIVE_DLIST_H_
263