1351282Sdim//===-- list.h --------------------------------------------------*- C++ -*-===// 2351282Sdim// 3351282Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4351282Sdim// See https://llvm.org/LICENSE.txt for license information. 5351282Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6351282Sdim// 7351282Sdim//===----------------------------------------------------------------------===// 8351282Sdim 9351282Sdim#ifndef SCUDO_LIST_H_ 10351282Sdim#define SCUDO_LIST_H_ 11351282Sdim 12351282Sdim#include "internal_defs.h" 13351282Sdim 14351282Sdimnamespace scudo { 15351282Sdim 16360784Sdim// Intrusive POD singly and doubly linked list. 17351282Sdim// An object with all zero fields should represent a valid empty list. clear() 18351282Sdim// should be called on all non-zero-initialized objects before using. 19351282Sdim 20360784Sdimtemplate <class T> class IteratorBase { 21360784Sdimpublic: 22360784Sdim explicit IteratorBase(T *CurrentT) : Current(CurrentT) {} 23360784Sdim IteratorBase &operator++() { 24360784Sdim Current = Current->Next; 25360784Sdim return *this; 26360784Sdim } 27360784Sdim bool operator!=(IteratorBase Other) const { return Current != Other.Current; } 28360784Sdim T &operator*() { return *Current; } 29360784Sdim 30360784Sdimprivate: 31360784Sdim T *Current; 32360784Sdim}; 33360784Sdim 34360784Sdimtemplate <class T> struct IntrusiveList { 35360784Sdim bool empty() const { return Size == 0; } 36360784Sdim uptr size() const { return Size; } 37360784Sdim 38360784Sdim T *front() { return First; } 39360784Sdim const T *front() const { return First; } 40360784Sdim T *back() { return Last; } 41360784Sdim const T *back() const { return Last; } 42360784Sdim 43351282Sdim void clear() { 44351282Sdim First = Last = nullptr; 45351282Sdim Size = 0; 46351282Sdim } 47351282Sdim 48360784Sdim typedef IteratorBase<T> Iterator; 49360784Sdim typedef IteratorBase<const T> ConstIterator; 50351282Sdim 51360784Sdim Iterator begin() { return Iterator(First); } 52360784Sdim Iterator end() { return Iterator(nullptr); } 53360784Sdim 54360784Sdim ConstIterator begin() const { return ConstIterator(First); } 55360784Sdim ConstIterator end() const { return ConstIterator(nullptr); } 56360784Sdim 57360784Sdim void checkConsistency() const; 58360784Sdim 59360784Sdimprotected: 60360784Sdim uptr Size; 61360784Sdim T *First; 62360784Sdim T *Last; 63360784Sdim}; 64360784Sdim 65360784Sdimtemplate <class T> void IntrusiveList<T>::checkConsistency() const { 66360784Sdim if (Size == 0) { 67360784Sdim CHECK_EQ(First, nullptr); 68360784Sdim CHECK_EQ(Last, nullptr); 69360784Sdim } else { 70360784Sdim uptr Count = 0; 71360784Sdim for (T *I = First;; I = I->Next) { 72360784Sdim Count++; 73360784Sdim if (I == Last) 74360784Sdim break; 75351282Sdim } 76360784Sdim CHECK_EQ(this->size(), Count); 77360784Sdim CHECK_EQ(Last->Next, nullptr); 78351282Sdim } 79360784Sdim} 80351282Sdim 81360784Sdimtemplate <class T> struct SinglyLinkedList : public IntrusiveList<T> { 82360784Sdim using IntrusiveList<T>::First; 83360784Sdim using IntrusiveList<T>::Last; 84360784Sdim using IntrusiveList<T>::Size; 85360784Sdim using IntrusiveList<T>::empty; 86360784Sdim 87360784Sdim void push_back(T *X) { 88360784Sdim X->Next = nullptr; 89360784Sdim if (empty()) 90351282Sdim First = X; 91360784Sdim else 92360784Sdim Last->Next = X; 93360784Sdim Last = X; 94360784Sdim Size++; 95351282Sdim } 96351282Sdim 97360784Sdim void push_front(T *X) { 98360784Sdim if (empty()) 99360784Sdim Last = X; 100360784Sdim X->Next = First; 101360784Sdim First = X; 102360784Sdim Size++; 103360784Sdim } 104360784Sdim 105351282Sdim void pop_front() { 106351282Sdim DCHECK(!empty()); 107351282Sdim First = First->Next; 108351282Sdim if (!First) 109351282Sdim Last = nullptr; 110351282Sdim Size--; 111351282Sdim } 112351282Sdim 113360784Sdim void extract(T *Prev, T *X) { 114351282Sdim DCHECK(!empty()); 115351282Sdim DCHECK_NE(Prev, nullptr); 116351282Sdim DCHECK_NE(X, nullptr); 117351282Sdim DCHECK_EQ(Prev->Next, X); 118351282Sdim Prev->Next = X->Next; 119351282Sdim if (Last == X) 120351282Sdim Last = Prev; 121351282Sdim Size--; 122351282Sdim } 123351282Sdim 124360784Sdim void append_back(SinglyLinkedList<T> *L) { 125351282Sdim DCHECK_NE(this, L); 126351282Sdim if (L->empty()) 127351282Sdim return; 128351282Sdim if (empty()) { 129351282Sdim *this = *L; 130360784Sdim } else { 131360784Sdim Last->Next = L->First; 132360784Sdim Last = L->Last; 133351282Sdim Size += L->size(); 134351282Sdim } 135351282Sdim L->clear(); 136351282Sdim } 137360784Sdim}; 138351282Sdim 139360784Sdimtemplate <class T> struct DoublyLinkedList : IntrusiveList<T> { 140360784Sdim using IntrusiveList<T>::First; 141360784Sdim using IntrusiveList<T>::Last; 142360784Sdim using IntrusiveList<T>::Size; 143360784Sdim using IntrusiveList<T>::empty; 144360784Sdim 145360784Sdim void push_front(T *X) { 146360784Sdim X->Prev = nullptr; 147351282Sdim if (empty()) { 148360784Sdim Last = X; 149351282Sdim } else { 150360784Sdim DCHECK_EQ(First->Prev, nullptr); 151360784Sdim First->Prev = X; 152351282Sdim } 153360784Sdim X->Next = First; 154360784Sdim First = X; 155360784Sdim Size++; 156351282Sdim } 157351282Sdim 158360784Sdim // Inserts X before Y. 159360784Sdim void insert(T *X, T *Y) { 160360784Sdim if (Y == First) 161360784Sdim return push_front(X); 162360784Sdim T *Prev = Y->Prev; 163360784Sdim // This is a hard CHECK to ensure consistency in the event of an intentional 164360784Sdim // corruption of Y->Prev, to prevent a potential write-{4,8}. 165360784Sdim CHECK_EQ(Prev->Next, Y); 166360784Sdim Prev->Next = X; 167360784Sdim X->Prev = Prev; 168360784Sdim X->Next = Y; 169360784Sdim Y->Prev = X; 170360784Sdim Size++; 171360784Sdim } 172360784Sdim 173360784Sdim void push_back(T *X) { 174360784Sdim X->Next = nullptr; 175360784Sdim if (empty()) { 176360784Sdim First = X; 177351282Sdim } else { 178360784Sdim DCHECK_EQ(Last->Next, nullptr); 179360784Sdim Last->Next = X; 180351282Sdim } 181360784Sdim X->Prev = Last; 182360784Sdim Last = X; 183360784Sdim Size++; 184351282Sdim } 185351282Sdim 186360784Sdim void pop_front() { 187360784Sdim DCHECK(!empty()); 188360784Sdim First = First->Next; 189360784Sdim if (!First) 190360784Sdim Last = nullptr; 191360784Sdim else 192360784Sdim First->Prev = nullptr; 193360784Sdim Size--; 194360784Sdim } 195360784Sdim 196360784Sdim // The consistency of the adjacent links is aggressively checked in order to 197360784Sdim // catch potential corruption attempts, that could yield a mirrored 198360784Sdim // write-{4,8} primitive. nullptr checks are deemed less vital. 199360784Sdim void remove(T *X) { 200360784Sdim T *Prev = X->Prev; 201360784Sdim T *Next = X->Next; 202360784Sdim if (Prev) { 203360784Sdim CHECK_EQ(Prev->Next, X); 204360784Sdim Prev->Next = Next; 205351282Sdim } 206360784Sdim if (Next) { 207360784Sdim CHECK_EQ(Next->Prev, X); 208360784Sdim Next->Prev = Prev; 209351282Sdim } 210360784Sdim if (First == X) { 211360784Sdim DCHECK_EQ(Prev, nullptr); 212360784Sdim First = Next; 213360784Sdim } else { 214360784Sdim DCHECK_NE(Prev, nullptr); 215360784Sdim } 216360784Sdim if (Last == X) { 217360784Sdim DCHECK_EQ(Next, nullptr); 218360784Sdim Last = Prev; 219360784Sdim } else { 220360784Sdim DCHECK_NE(Next, nullptr); 221360784Sdim } 222360784Sdim Size--; 223360784Sdim } 224351282Sdim}; 225351282Sdim 226351282Sdim} // namespace scudo 227351282Sdim 228351282Sdim#endif // SCUDO_LIST_H_ 229