1//===-- list.h --------------------------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef SCUDO_LIST_H_
10#define SCUDO_LIST_H_
11
12#include "internal_defs.h"
13#include "type_traits.h"
14
15namespace scudo {
16
17// Intrusive POD singly and doubly linked list.
18// An object with all zero fields should represent a valid empty list. clear()
19// should be called on all non-zero-initialized objects before using.
20//
21// The intrusive list requires the member `Next` (and `Prev` if doubly linked
22// list)` defined in the node type. The type of `Next`/`Prev` can be a pointer
23// or an index to an array. For example, if the storage of the nodes is an
24// array, instead of using a pointer type, linking with an index type can save
25// some space.
26//
27// There are two things to be noticed while using an index type,
28// 1. Call init() to set up the base address of the array.
29// 2. Define `EndOfListVal` as the nil of the list.
30
31template <class T, bool LinkWithPtr = isPointer<decltype(T::Next)>::value>
32class LinkOp {
33public:
34 LinkOp() = default;
35 LinkOp(UNUSED T *BaseT, UNUSED uptr BaseSize) {}
36 void init(UNUSED T *LinkBase, UNUSED uptr Size) {}
37 T *getBase() const { return nullptr; }
38 uptr getSize() const { return 0; }
39
40 T *getNext(T *X) const { return X->Next; }
41 void setNext(T *X, T *Next) const { X->Next = Next; }
42
43 T *getPrev(T *X) const { return X->Prev; }
44 void setPrev(T *X, T *Prev) const { X->Prev = Prev; }
45
46 T *getEndOfListVal() const { return nullptr; }
47};
48
49template <class T> class LinkOp<T, /*LinkWithPtr=*/false> {
50public:
51 using LinkTy = typename assertSameType<
52 typename removeConst<decltype(T::Next)>::type,
53 typename removeConst<decltype(T::EndOfListVal)>::type>::type;
54
55 LinkOp() = default;
56 LinkOp(T *BaseT, uptr BaseSize)
57 : Base(BaseT), Size(static_cast<LinkTy>(BaseSize)) {}
58 void init(T *LinkBase, uptr BaseSize) {
59 Base = LinkBase;
60 Size = static_cast<LinkTy>(BaseSize);
61 }
62 T *getBase() const { return Base; }
63 LinkTy getSize() const { return Size; }
64
65 T *getNext(T *X) const {
66 DCHECK_NE(getBase(), nullptr);
67 if (X->Next == getEndOfListVal())
68 return nullptr;
69 DCHECK_LT(X->Next, Size);
70 return &Base[X->Next];
71 }
72 // Set `X->Next` to `Next`.
73 void setNext(T *X, T *Next) const {
74 if (Next == nullptr) {
75 X->Next = getEndOfListVal();
76 } else {
77 assertElementInRange(X: Next);
78 X->Next = static_cast<LinkTy>(Next - Base);
79 }
80 }
81
82 T *getPrev(T *X) const {
83 DCHECK_NE(getBase(), nullptr);
84 if (X->Prev == getEndOfListVal())
85 return nullptr;
86 DCHECK_LT(X->Prev, Size);
87 return &Base[X->Prev];
88 }
89 // Set `X->Prev` to `Prev`.
90 void setPrev(T *X, T *Prev) const {
91 if (Prev == nullptr) {
92 X->Prev = getEndOfListVal();
93 } else {
94 assertElementInRange(X: Prev);
95 X->Prev = static_cast<LinkTy>(Prev - Base);
96 }
97 }
98
99 LinkTy getEndOfListVal() const { return T::EndOfListVal; }
100
101private:
102 void assertElementInRange(T *X) const {
103 DCHECK_GE(reinterpret_cast<uptr>(X), reinterpret_cast<uptr>(Base));
104 DCHECK_LE(static_cast<LinkTy>(X - Base), Size);
105 }
106
107protected:
108 T *Base = nullptr;
109 LinkTy Size = 0;
110};
111
112template <class T> class IteratorBase : public LinkOp<T> {
113public:
114 IteratorBase(const LinkOp<T> &Link, T *CurrentT)
115 : LinkOp<T>(Link), Current(CurrentT) {}
116
117 IteratorBase &operator++() {
118 Current = this->getNext(Current);
119 return *this;
120 }
121 bool operator!=(IteratorBase Other) const { return Current != Other.Current; }
122 T &operator*() { return *Current; }
123
124private:
125 T *Current;
126};
127
128template <class T> struct IntrusiveList : public LinkOp<T> {
129 IntrusiveList() = default;
130 void init(T *Base, uptr BaseSize) { LinkOp<T>::init(Base, BaseSize); }
131
132 bool empty() const { return Size == 0; }
133 uptr size() const { return Size; }
134
135 T *front() { return First; }
136 const T *front() const { return First; }
137 T *back() { return Last; }
138 const T *back() const { return Last; }
139
140 void clear() {
141 First = Last = nullptr;
142 Size = 0;
143 }
144
145 typedef IteratorBase<T> Iterator;
146 typedef IteratorBase<const T> ConstIterator;
147
148 Iterator begin() {
149 return Iterator(LinkOp<T>(this->getBase(), this->getSize()), First);
150 }
151 Iterator end() {
152 return Iterator(LinkOp<T>(this->getBase(), this->getSize()), nullptr);
153 }
154
155 ConstIterator begin() const {
156 return ConstIterator(LinkOp<const T>(this->getBase(), this->getSize()),
157 First);
158 }
159 ConstIterator end() const {
160 return ConstIterator(LinkOp<const T>(this->getBase(), this->getSize()),
161 nullptr);
162 }
163
164 void checkConsistency() const;
165
166protected:
167 uptr Size = 0;
168 T *First = nullptr;
169 T *Last = nullptr;
170};
171
172template <class T> void IntrusiveList<T>::checkConsistency() const {
173 if (Size == 0) {
174 CHECK_EQ(First, nullptr);
175 CHECK_EQ(Last, nullptr);
176 } else {
177 uptr Count = 0;
178 for (T *I = First;; I = this->getNext(I)) {
179 Count++;
180 if (I == Last)
181 break;
182 }
183 CHECK_EQ(this->size(), Count);
184 CHECK_EQ(this->getNext(Last), nullptr);
185 }
186}
187
188template <class T> struct SinglyLinkedList : public IntrusiveList<T> {
189 using IntrusiveList<T>::First;
190 using IntrusiveList<T>::Last;
191 using IntrusiveList<T>::Size;
192 using IntrusiveList<T>::empty;
193 using IntrusiveList<T>::setNext;
194 using IntrusiveList<T>::getNext;
195 using IntrusiveList<T>::getEndOfListVal;
196
197 void push_back(T *X) {
198 setNext(X, nullptr);
199 if (empty())
200 First = X;
201 else
202 setNext(Last, X);
203 Last = X;
204 Size++;
205 }
206
207 void push_front(T *X) {
208 if (empty())
209 Last = X;
210 setNext(X, First);
211 First = X;
212 Size++;
213 }
214
215 void pop_front() {
216 DCHECK(!empty());
217 First = getNext(First);
218 if (!First)
219 Last = nullptr;
220 Size--;
221 }
222
223 // Insert X next to Prev
224 void insert(T *Prev, T *X) {
225 DCHECK(!empty());
226 DCHECK_NE(Prev, nullptr);
227 DCHECK_NE(X, nullptr);
228 setNext(X, getNext(Prev));
229 setNext(Prev, X);
230 if (Last == Prev)
231 Last = X;
232 ++Size;
233 }
234
235 void extract(T *Prev, T *X) {
236 DCHECK(!empty());
237 DCHECK_NE(Prev, nullptr);
238 DCHECK_NE(X, nullptr);
239 DCHECK_EQ(getNext(Prev), X);
240 setNext(Prev, getNext(X));
241 if (Last == X)
242 Last = Prev;
243 Size--;
244 }
245
246 void append_back(SinglyLinkedList<T> *L) {
247 DCHECK_NE(this, L);
248 if (L->empty())
249 return;
250 if (empty()) {
251 *this = *L;
252 } else {
253 setNext(Last, L->First);
254 Last = L->Last;
255 Size += L->size();
256 }
257 L->clear();
258 }
259};
260
261template <class T> struct DoublyLinkedList : IntrusiveList<T> {
262 using IntrusiveList<T>::First;
263 using IntrusiveList<T>::Last;
264 using IntrusiveList<T>::Size;
265 using IntrusiveList<T>::empty;
266 using IntrusiveList<T>::setNext;
267 using IntrusiveList<T>::getNext;
268 using IntrusiveList<T>::setPrev;
269 using IntrusiveList<T>::getPrev;
270 using IntrusiveList<T>::getEndOfListVal;
271
272 void push_front(T *X) {
273 setPrev(X, nullptr);
274 if (empty()) {
275 Last = X;
276 } else {
277 DCHECK_EQ(getPrev(First), nullptr);
278 setPrev(First, X);
279 }
280 setNext(X, First);
281 First = X;
282 Size++;
283 }
284
285 // Inserts X before Y.
286 void insert(T *X, T *Y) {
287 if (Y == First)
288 return push_front(X);
289 T *Prev = getPrev(Y);
290 // This is a hard CHECK to ensure consistency in the event of an intentional
291 // corruption of Y->Prev, to prevent a potential write-{4,8}.
292 CHECK_EQ(getNext(Prev), Y);
293 setNext(Prev, X);
294 setPrev(X, Prev);
295 setNext(X, Y);
296 setPrev(Y, X);
297 Size++;
298 }
299
300 void push_back(T *X) {
301 setNext(X, nullptr);
302 if (empty()) {
303 First = X;
304 } else {
305 DCHECK_EQ(getNext(Last), nullptr);
306 setNext(Last, X);
307 }
308 setPrev(X, Last);
309 Last = X;
310 Size++;
311 }
312
313 void pop_front() {
314 DCHECK(!empty());
315 First = getNext(First);
316 if (!First)
317 Last = nullptr;
318 else
319 setPrev(First, nullptr);
320 Size--;
321 }
322
323 // The consistency of the adjacent links is aggressively checked in order to
324 // catch potential corruption attempts, that could yield a mirrored
325 // write-{4,8} primitive. nullptr checks are deemed less vital.
326 void remove(T *X) {
327 T *Prev = getPrev(X);
328 T *Next = getNext(X);
329 if (Prev) {
330 CHECK_EQ(getNext(Prev), X);
331 setNext(Prev, Next);
332 }
333 if (Next) {
334 CHECK_EQ(getPrev(Next), X);
335 setPrev(Next, Prev);
336 }
337 if (First == X) {
338 DCHECK_EQ(Prev, nullptr);
339 First = Next;
340 } else {
341 DCHECK_NE(Prev, nullptr);
342 }
343 if (Last == X) {
344 DCHECK_EQ(Next, nullptr);
345 Last = Prev;
346 } else {
347 DCHECK_NE(Next, nullptr);
348 }
349 Size--;
350 }
351};
352
353} // namespace scudo
354
355#endif // SCUDO_LIST_H_
356