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
14namespace scudo {
15
16// Intrusive POD singly and doubly linked list.
17// An object with all zero fields should represent a valid empty list. clear()
18// should be called on all non-zero-initialized objects before using.
19
20template <class T> class IteratorBase {
21public:
22 explicit IteratorBase(T *CurrentT) : Current(CurrentT) {}
23 IteratorBase &operator++() {
24 Current = Current->Next;
25 return *this;
26 }
27 bool operator!=(IteratorBase Other) const { return Current != Other.Current; }
28 T &operator*() { return *Current; }
29
30private:
31 T *Current;
32};
33
34template <class T> struct IntrusiveList {
35 bool empty() const { return Size == 0; }
36 uptr size() const { return Size; }
37
38 T *front() { return First; }
39 const T *front() const { return First; }
40 T *back() { return Last; }
41 const T *back() const { return Last; }
42
43 void clear() {
44 First = Last = nullptr;
45 Size = 0;
46 }
47
48 typedef IteratorBase<T> Iterator;
49 typedef IteratorBase<const T> ConstIterator;
50
51 Iterator begin() { return Iterator(First); }
52 Iterator end() { return Iterator(nullptr); }
53
54 ConstIterator begin() const { return ConstIterator(First); }
55 ConstIterator end() const { return ConstIterator(nullptr); }
56
57 void checkConsistency() const;
58
59protected:
60 uptr Size = 0;
61 T *First = nullptr;
62 T *Last = nullptr;
63};
64
65template <class T> void IntrusiveList<T>::checkConsistency() const {
66 if (Size == 0) {
67 CHECK_EQ(First, nullptr);
68 CHECK_EQ(Last, nullptr);
69 } else {
70 uptr Count = 0;
71 for (T *I = First;; I = I->Next) {
72 Count++;
73 if (I == Last)
74 break;
75 }
76 CHECK_EQ(this->size(), Count);
77 CHECK_EQ(Last->Next, nullptr);
78 }
79}
80
81template <class T> struct SinglyLinkedList : public IntrusiveList<T> {
82 using IntrusiveList<T>::First;
83 using IntrusiveList<T>::Last;
84 using IntrusiveList<T>::Size;
85 using IntrusiveList<T>::empty;
86
87 void push_back(T *X) {
88 X->Next = nullptr;
89 if (empty())
90 First = X;
91 else
92 Last->Next = X;
93 Last = X;
94 Size++;
95 }
96
97 void push_front(T *X) {
98 if (empty())
99 Last = X;
100 X->Next = First;
101 First = X;
102 Size++;
103 }
104
105 void pop_front() {
106 DCHECK(!empty());
107 First = First->Next;
108 if (!First)
109 Last = nullptr;
110 Size--;
111 }
112
113 // Insert X next to Prev
114 void insert(T *Prev, T *X) {
115 DCHECK(!empty());
116 DCHECK_NE(Prev, nullptr);
117 DCHECK_NE(X, nullptr);
118 X->Next = Prev->Next;
119 Prev->Next = X;
120 if (Last == Prev)
121 Last = X;
122 ++Size;
123 }
124
125 void extract(T *Prev, T *X) {
126 DCHECK(!empty());
127 DCHECK_NE(Prev, nullptr);
128 DCHECK_NE(X, nullptr);
129 DCHECK_EQ(Prev->Next, X);
130 Prev->Next = X->Next;
131 if (Last == X)
132 Last = Prev;
133 Size--;
134 }
135
136 void append_back(SinglyLinkedList<T> *L) {
137 DCHECK_NE(this, L);
138 if (L->empty())
139 return;
140 if (empty()) {
141 *this = *L;
142 } else {
143 Last->Next = L->First;
144 Last = L->Last;
145 Size += L->size();
146 }
147 L->clear();
148 }
149};
150
151template <class T> struct DoublyLinkedList : IntrusiveList<T> {
152 using IntrusiveList<T>::First;
153 using IntrusiveList<T>::Last;
154 using IntrusiveList<T>::Size;
155 using IntrusiveList<T>::empty;
156
157 void push_front(T *X) {
158 X->Prev = nullptr;
159 if (empty()) {
160 Last = X;
161 } else {
162 DCHECK_EQ(First->Prev, nullptr);
163 First->Prev = X;
164 }
165 X->Next = First;
166 First = X;
167 Size++;
168 }
169
170 // Inserts X before Y.
171 void insert(T *X, T *Y) {
172 if (Y == First)
173 return push_front(X);
174 T *Prev = Y->Prev;
175 // This is a hard CHECK to ensure consistency in the event of an intentional
176 // corruption of Y->Prev, to prevent a potential write-{4,8}.
177 CHECK_EQ(Prev->Next, Y);
178 Prev->Next = X;
179 X->Prev = Prev;
180 X->Next = Y;
181 Y->Prev = X;
182 Size++;
183 }
184
185 void push_back(T *X) {
186 X->Next = nullptr;
187 if (empty()) {
188 First = X;
189 } else {
190 DCHECK_EQ(Last->Next, nullptr);
191 Last->Next = X;
192 }
193 X->Prev = Last;
194 Last = X;
195 Size++;
196 }
197
198 void pop_front() {
199 DCHECK(!empty());
200 First = First->Next;
201 if (!First)
202 Last = nullptr;
203 else
204 First->Prev = nullptr;
205 Size--;
206 }
207
208 // The consistency of the adjacent links is aggressively checked in order to
209 // catch potential corruption attempts, that could yield a mirrored
210 // write-{4,8} primitive. nullptr checks are deemed less vital.
211 void remove(T *X) {
212 T *Prev = X->Prev;
213 T *Next = X->Next;
214 if (Prev) {
215 CHECK_EQ(Prev->Next, X);
216 Prev->Next = Next;
217 }
218 if (Next) {
219 CHECK_EQ(Next->Prev, X);
220 Next->Prev = Prev;
221 }
222 if (First == X) {
223 DCHECK_EQ(Prev, nullptr);
224 First = Next;
225 } else {
226 DCHECK_NE(Prev, nullptr);
227 }
228 if (Last == X) {
229 DCHECK_EQ(Next, nullptr);
230 Last = Prev;
231 } else {
232 DCHECK_NE(Next, nullptr);
233 }
234 Size--;
235 }
236};
237
238} // namespace scudo
239
240#endif // SCUDO_LIST_H_
241

source code of compiler-rt/lib/scudo/standalone/list.h