xref: /llvm-project/compiler-rt/lib/scudo/standalone/list.h (revision 5a930339a5330dbab23d9eac28a609df9aa9c3fc)
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 
15 namespace 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 
31 template <class T, bool LinkWithPtr = isPointer<decltype(T::Next)>::value>
32 class LinkOp {
33 public:
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 
49 template <class T> class LinkOp<T, /*LinkWithPtr=*/false> {
50 public:
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(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(Prev);
95       X->Prev = static_cast<LinkTy>(Prev - Base);
96     }
97   }
98 
99   LinkTy getEndOfListVal() const { return T::EndOfListVal; }
100 
101 private:
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 
107 protected:
108   T *Base = nullptr;
109   LinkTy Size = 0;
110 };
111 
112 template <class T> class IteratorBase : public LinkOp<T> {
113 public:
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 
124 private:
125   T *Current;
126 };
127 
128 template <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 
166 protected:
167   uptr Size = 0;
168   T *First = nullptr;
169   T *Last = nullptr;
170 };
171 
172 template <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 
188 template <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 
261 template <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