356 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef SCUDO_LIST_H_10#define SCUDO_LIST_H_11 12#include "internal_defs.h"13#include "type_traits.h"14 15namespace scudo {16 17// Intrusive POD singly and doubly linked list.18// An object with all zero fields should represent a valid empty list. clear()19// should be called on all non-zero-initialized objects before using.20//21// The intrusive list requires the member `Next` (and `Prev` if doubly linked22// list)` defined in the node type. The type of `Next`/`Prev` can be a pointer23// or an index to an array. For example, if the storage of the nodes is an24// array, instead of using a pointer type, linking with an index type can save25// some space.26//27// There are two things to be noticed while using an index type,28// 1. Call init() to set up the base address of the array.29// 2. Define `EndOfListVal` as the nil of the list.30 31template <class T, bool LinkWithPtr = isPointer<decltype(T::Next)>::value>32class LinkOp {33public:34 LinkOp() = default;35 LinkOp(UNUSED T *BaseT, UNUSED uptr BaseSize) {}36 void init(UNUSED T *LinkBase, UNUSED uptr Size) {}37 T *getBase() const { return nullptr; }38 uptr getSize() const { return 0; }39 40 T *getNext(T *X) const { return X->Next; }41 void setNext(T *X, T *Next) const { X->Next = Next; }42 43 T *getPrev(T *X) const { return X->Prev; }44 void setPrev(T *X, T *Prev) const { X->Prev = Prev; }45 46 T *getEndOfListVal() const { return nullptr; }47};48 49template <class T> class LinkOp<T, /*LinkWithPtr=*/false> {50public:51 using LinkTy = typename assertSameType<52 typename removeConst<decltype(T::Next)>::type,53 typename removeConst<decltype(T::EndOfListVal)>::type>::type;54 55 LinkOp() = default;56 LinkOp(T *BaseT, uptr BaseSize)57 : Base(BaseT), Size(static_cast<LinkTy>(BaseSize)) {}58 void init(T *LinkBase, uptr BaseSize) {59 Base = LinkBase;60 Size = static_cast<LinkTy>(BaseSize);61 }62 T *getBase() const { return Base; }63 LinkTy getSize() const { return Size; }64 65 T *getNext(T *X) const {66 DCHECK_NE(getBase(), nullptr);67 if (X->Next == getEndOfListVal())68 return nullptr;69 DCHECK_LT(X->Next, Size);70 return &Base[X->Next];71 }72 // Set `X->Next` to `Next`.73 void setNext(T *X, T *Next) const {74 if (Next == nullptr) {75 X->Next = getEndOfListVal();76 } else {77 assertElementInRange(Next);78 X->Next = static_cast<LinkTy>(Next - Base);79 }80 }81 82 T *getPrev(T *X) const {83 DCHECK_NE(getBase(), nullptr);84 if (X->Prev == getEndOfListVal())85 return nullptr;86 DCHECK_LT(X->Prev, Size);87 return &Base[X->Prev];88 }89 // Set `X->Prev` to `Prev`.90 void setPrev(T *X, T *Prev) const {91 if (Prev == nullptr) {92 X->Prev = getEndOfListVal();93 } else {94 assertElementInRange(Prev);95 X->Prev = static_cast<LinkTy>(Prev - Base);96 }97 }98 99 LinkTy getEndOfListVal() const { return T::EndOfListVal; }100 101private:102 void assertElementInRange(T *X) const {103 DCHECK_GE(reinterpret_cast<uptr>(X), reinterpret_cast<uptr>(Base));104 DCHECK_LE(static_cast<LinkTy>(X - Base), Size);105 }106 107protected:108 T *Base = nullptr;109 LinkTy Size = 0;110};111 112template <class T> class IteratorBase : public LinkOp<T> {113public:114 IteratorBase(const LinkOp<T> &Link, T *CurrentT)115 : LinkOp<T>(Link), Current(CurrentT) {}116 117 IteratorBase &operator++() {118 Current = this->getNext(Current);119 return *this;120 }121 bool operator!=(IteratorBase Other) const { return Current != Other.Current; }122 T &operator*() { return *Current; }123 124private:125 T *Current;126};127 128template <class T> struct IntrusiveList : public LinkOp<T> {129 IntrusiveList() = default;130 void init(T *Base, uptr BaseSize) { LinkOp<T>::init(Base, BaseSize); }131 132 bool empty() const { return Size == 0; }133 uptr size() const { return Size; }134 135 T *front() { return First; }136 const T *front() const { return First; }137 T *back() { return Last; }138 const T *back() const { return Last; }139 140 void clear() {141 First = Last = nullptr;142 Size = 0;143 }144 145 typedef IteratorBase<T> Iterator;146 typedef IteratorBase<const T> ConstIterator;147 148 Iterator begin() {149 return Iterator(LinkOp<T>(this->getBase(), this->getSize()), First);150 }151 Iterator end() {152 return Iterator(LinkOp<T>(this->getBase(), this->getSize()), nullptr);153 }154 155 ConstIterator begin() const {156 return ConstIterator(LinkOp<const T>(this->getBase(), this->getSize()),157 First);158 }159 ConstIterator end() const {160 return ConstIterator(LinkOp<const T>(this->getBase(), this->getSize()),161 nullptr);162 }163 164 void checkConsistency() const;165 166protected:167 uptr Size = 0;168 T *First = nullptr;169 T *Last = nullptr;170};171 172template <class T> void IntrusiveList<T>::checkConsistency() const {173 if (Size == 0) {174 CHECK_EQ(First, nullptr);175 CHECK_EQ(Last, nullptr);176 } else {177 uptr Count = 0;178 for (T *I = First;; I = this->getNext(I)) {179 Count++;180 if (I == Last)181 break;182 }183 CHECK_EQ(this->size(), Count);184 CHECK_EQ(this->getNext(Last), nullptr);185 }186}187 188template <class T> struct SinglyLinkedList : public IntrusiveList<T> {189 using IntrusiveList<T>::First;190 using IntrusiveList<T>::Last;191 using IntrusiveList<T>::Size;192 using IntrusiveList<T>::empty;193 using IntrusiveList<T>::setNext;194 using IntrusiveList<T>::getNext;195 using IntrusiveList<T>::getEndOfListVal;196 197 void push_back(T *X) {198 setNext(X, nullptr);199 if (empty())200 First = X;201 else202 setNext(Last, X);203 Last = X;204 Size++;205 }206 207 void push_front(T *X) {208 if (empty())209 Last = X;210 setNext(X, First);211 First = X;212 Size++;213 }214 215 void pop_front() {216 DCHECK(!empty());217 First = getNext(First);218 if (!First)219 Last = nullptr;220 Size--;221 }222 223 // Insert X next to Prev224 void insert(T *Prev, T *X) {225 DCHECK(!empty());226 DCHECK_NE(Prev, nullptr);227 DCHECK_NE(X, nullptr);228 setNext(X, getNext(Prev));229 setNext(Prev, X);230 if (Last == Prev)231 Last = X;232 ++Size;233 }234 235 void extract(T *Prev, T *X) {236 DCHECK(!empty());237 DCHECK_NE(Prev, nullptr);238 DCHECK_NE(X, nullptr);239 DCHECK_EQ(getNext(Prev), X);240 setNext(Prev, getNext(X));241 if (Last == X)242 Last = Prev;243 Size--;244 }245 246 void append_back(SinglyLinkedList<T> *L) {247 DCHECK_NE(this, L);248 if (L->empty())249 return;250 if (empty()) {251 *this = *L;252 } else {253 setNext(Last, L->First);254 Last = L->Last;255 Size += L->size();256 }257 L->clear();258 }259};260 261template <class T> struct DoublyLinkedList : IntrusiveList<T> {262 using IntrusiveList<T>::First;263 using IntrusiveList<T>::Last;264 using IntrusiveList<T>::Size;265 using IntrusiveList<T>::empty;266 using IntrusiveList<T>::setNext;267 using IntrusiveList<T>::getNext;268 using IntrusiveList<T>::setPrev;269 using IntrusiveList<T>::getPrev;270 using IntrusiveList<T>::getEndOfListVal;271 272 void push_front(T *X) {273 setPrev(X, nullptr);274 if (empty()) {275 Last = X;276 } else {277 DCHECK_EQ(getPrev(First), nullptr);278 setPrev(First, X);279 }280 setNext(X, First);281 First = X;282 Size++;283 }284 285 // Inserts X before Y.286 void insert(T *X, T *Y) {287 if (Y == First)288 return push_front(X);289 T *Prev = getPrev(Y);290 // This is a hard CHECK to ensure consistency in the event of an intentional291 // corruption of Y->Prev, to prevent a potential write-{4,8}.292 CHECK_EQ(getNext(Prev), Y);293 setNext(Prev, X);294 setPrev(X, Prev);295 setNext(X, Y);296 setPrev(Y, X);297 Size++;298 }299 300 void push_back(T *X) {301 setNext(X, nullptr);302 if (empty()) {303 First = X;304 } else {305 DCHECK_EQ(getNext(Last), nullptr);306 setNext(Last, X);307 }308 setPrev(X, Last);309 Last = X;310 Size++;311 }312 313 void pop_front() {314 DCHECK(!empty());315 First = getNext(First);316 if (!First)317 Last = nullptr;318 else319 setPrev(First, nullptr);320 Size--;321 }322 323 // The consistency of the adjacent links is aggressively checked in order to324 // catch potential corruption attempts, that could yield a mirrored325 // write-{4,8} primitive. nullptr checks are deemed less vital.326 void remove(T *X) {327 T *Prev = getPrev(X);328 T *Next = getNext(X);329 if (Prev) {330 CHECK_EQ(getNext(Prev), X);331 setNext(Prev, Next);332 }333 if (Next) {334 CHECK_EQ(getPrev(Next), X);335 setPrev(Next, Prev);336 }337 if (First == X) {338 DCHECK_EQ(Prev, nullptr);339 First = Next;340 } else {341 DCHECK_NE(Prev, nullptr);342 }343 if (Last == X) {344 DCHECK_EQ(Next, nullptr);345 Last = Prev;346 } else {347 DCHECK_NE(Next, nullptr);348 }349 Size--;350 }351};352 353} // namespace scudo354 355#endif // SCUDO_LIST_H_356