list.h revision 360784 
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;
61  T *First;
62  T *Last;
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  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
139template <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