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:
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 {
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 
59 protected:
60   uptr Size = 0;
61   T *First = nullptr;
62   T *Last = nullptr;
63 };
64 
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 
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   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 
124   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 
145   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.
159   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 
173   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 
186   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.
199   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