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
14 namespace 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
20 template <class T> class IteratorBase {
21 public:
IteratorBase(T * CurrentT)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
30 private:
31 T *Current;
32 };
33
34 template <class T> struct IntrusiveList {
emptyIntrusiveList35 bool empty() const { return Size == 0; }
sizeIntrusiveList36 uptr size() const { return Size; }
37
frontIntrusiveList38 T *front() { return First; }
frontIntrusiveList39 const T *front() const { return First; }
backIntrusiveList40 T *back() { return Last; }
backIntrusiveList41 const T *back() const { return Last; }
42
clearIntrusiveList43 void clear() {
44 First = Last = nullptr;
45 Size = 0;
46 }
47
48 typedef IteratorBase<T> Iterator;
49 typedef IteratorBase<const T> ConstIterator;
50
beginIntrusiveList51 Iterator begin() { return Iterator(First); }
endIntrusiveList52 Iterator end() { return Iterator(nullptr); }
53
beginIntrusiveList54 ConstIterator begin() const { return ConstIterator(First); }
endIntrusiveList55 ConstIterator end() const { return ConstIterator(nullptr); }
56
57 void checkConsistency() const;
58
59 protected:
60 uptr Size = 0;
61 T *First = nullptr;
62 T *Last = nullptr;
63 };
64
checkConsistency()65 template <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
81 template <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
push_backSinglyLinkedList87 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
push_frontSinglyLinkedList97 void push_front(T *X) {
98 if (empty())
99 Last = X;
100 X->Next = First;
101 First = X;
102 Size++;
103 }
104
pop_frontSinglyLinkedList105 void pop_front() {
106 DCHECK(!empty());
107 First = First->Next;
108 if (!First)
109 Last = nullptr;
110 Size--;
111 }
112
extractSinglyLinkedList113 void extract(T *Prev, T *X) {
114 DCHECK(!empty());
115 DCHECK_NE(Prev, nullptr);
116 DCHECK_NE(X, nullptr);
117 DCHECK_EQ(Prev->Next, X);
118 Prev->Next = X->Next;
119 if (Last == X)
120 Last = Prev;
121 Size--;
122 }
123
append_backSinglyLinkedList124 void append_back(SinglyLinkedList<T> *L) {
125 DCHECK_NE(this, L);
126 if (L->empty())
127 return;
128 if (empty()) {
129 *this = *L;
130 } else {
131 Last->Next = L->First;
132 Last = L->Last;
133 Size += L->size();
134 }
135 L->clear();
136 }
137 };
138
139 template <class T> struct DoublyLinkedList : IntrusiveList<T> {
140 using IntrusiveList<T>::First;
141 using IntrusiveList<T>::Last;
142 using IntrusiveList<T>::Size;
143 using IntrusiveList<T>::empty;
144
push_frontDoublyLinkedList145 void push_front(T *X) {
146 X->Prev = nullptr;
147 if (empty()) {
148 Last = X;
149 } else {
150 DCHECK_EQ(First->Prev, nullptr);
151 First->Prev = X;
152 }
153 X->Next = First;
154 First = X;
155 Size++;
156 }
157
158 // Inserts X before Y.
insertDoublyLinkedList159 void insert(T *X, T *Y) {
160 if (Y == First)
161 return push_front(X);
162 T *Prev = Y->Prev;
163 // This is a hard CHECK to ensure consistency in the event of an intentional
164 // corruption of Y->Prev, to prevent a potential write-{4,8}.
165 CHECK_EQ(Prev->Next, Y);
166 Prev->Next = X;
167 X->Prev = Prev;
168 X->Next = Y;
169 Y->Prev = X;
170 Size++;
171 }
172
push_backDoublyLinkedList173 void push_back(T *X) {
174 X->Next = nullptr;
175 if (empty()) {
176 First = X;
177 } else {
178 DCHECK_EQ(Last->Next, nullptr);
179 Last->Next = X;
180 }
181 X->Prev = Last;
182 Last = X;
183 Size++;
184 }
185
pop_frontDoublyLinkedList186 void pop_front() {
187 DCHECK(!empty());
188 First = First->Next;
189 if (!First)
190 Last = nullptr;
191 else
192 First->Prev = nullptr;
193 Size--;
194 }
195
196 // The consistency of the adjacent links is aggressively checked in order to
197 // catch potential corruption attempts, that could yield a mirrored
198 // write-{4,8} primitive. nullptr checks are deemed less vital.
removeDoublyLinkedList199 void remove(T *X) {
200 T *Prev = X->Prev;
201 T *Next = X->Next;
202 if (Prev) {
203 CHECK_EQ(Prev->Next, X);
204 Prev->Next = Next;
205 }
206 if (Next) {
207 CHECK_EQ(Next->Prev, X);
208 Next->Prev = Prev;
209 }
210 if (First == X) {
211 DCHECK_EQ(Prev, nullptr);
212 First = Next;
213 } else {
214 DCHECK_NE(Prev, nullptr);
215 }
216 if (Last == X) {
217 DCHECK_EQ(Next, nullptr);
218 Last = Prev;
219 } else {
220 DCHECK_NE(Next, nullptr);
221 }
222 Size--;
223 }
224 };
225
226 } // namespace scudo
227
228 #endif // SCUDO_LIST_H_
229