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