compiler-rt/lib/scudo/standalone/list.h

   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   // Insert X next to Prev
 114   void insert(T *Prev, T *X) {
 115     DCHECK(!empty());
 116     DCHECK_NE(Prev, nullptr);
 117     DCHECK_NE(X, nullptr);
 118     X->Next = Prev->Next;
 119     Prev->Next = X;
 120     if (Last == Prev)
 121       Last = X;
 122     ++Size;
 123   }
 124
 125   void extract(T *Prev, T *X) {
 126     DCHECK(!empty());
 127     DCHECK_NE(Prev, nullptr);
 128     DCHECK_NE(X, nullptr);
 129     DCHECK_EQ(Prev->Next, X);
 130     Prev->Next = X->Next;
 131     if (Last == X)
 132       Last = Prev;
 133     Size--;
 134   }
 135
 136   void append_back(SinglyLinkedList<T> *L) {
 137     DCHECK_NE(this, L);
 138     if (L->empty())
 139       return;
 140     if (empty()) {
 141       *this = *L;
 142     } else {
 143       Last->Next = L->First;
 144       Last = L->Last;
 145       Size += L->size();
 146     }
 147     L->clear();
 148   }
 149 };
 150
 151 template <class T> struct DoublyLinkedList : IntrusiveList<T> {
 152   using IntrusiveList<T>::First;
 153   using IntrusiveList<T>::Last;
 154   using IntrusiveList<T>::Size;
 155   using IntrusiveList<T>::empty;
 156
 157   void push_front(T *X) {
 158     X->Prev = nullptr;
 159     if (empty()) {
 160       Last = X;
 161     } else {
 162       DCHECK_EQ(First->Prev, nullptr);
 163       First->Prev = X;
 164     }
 165     X->Next = First;
 166     First = X;
 167     Size++;
 168   }
 169
 170   // Inserts X before Y.
 171   void insert(T *X, T *Y) {
 172     if (Y == First)
 173       return push_front(X);
 174     T *Prev = Y->Prev;
 175     // This is a hard CHECK to ensure consistency in the event of an intentional
 176     // corruption of Y->Prev, to prevent a potential write-{4,8}.
 177     CHECK_EQ(Prev->Next, Y);
 178     Prev->Next = X;
 179     X->Prev = Prev;
 180     X->Next = Y;
 181     Y->Prev = X;
 182     Size++;
 183   }
 184
 185   void push_back(T *X) {
 186     X->Next = nullptr;
 187     if (empty()) {
 188       First = X;
 189     } else {
 190       DCHECK_EQ(Last->Next, nullptr);
 191       Last->Next = X;
 192     }
 193     X->Prev = Last;
 194     Last = X;
 195     Size++;
 196   }
 197
 198   void pop_front() {
 199     DCHECK(!empty());
 200     First = First->Next;
 201     if (!First)
 202       Last = nullptr;
 203     else
 204       First->Prev = nullptr;
 205     Size--;
 206   }
 207
 208   // The consistency of the adjacent links is aggressively checked in order to
 209   // catch potential corruption attempts, that could yield a mirrored
 210   // write-{4,8} primitive. nullptr checks are deemed less vital.
 211   void remove(T *X) {
 212     T *Prev = X->Prev;
 213     T *Next = X->Next;
 214     if (Prev) {
 215       CHECK_EQ(Prev->Next, X);
 216       Prev->Next = Next;
 217     }
 218     if (Next) {
 219       CHECK_EQ(Next->Prev, X);
 220       Next->Prev = Prev;
 221     }
 222     if (First == X) {
 223       DCHECK_EQ(Prev, nullptr);
 224       First = Next;
 225     } else {
 226       DCHECK_NE(Prev, nullptr);
 227     }
 228     if (Last == X) {
 229       DCHECK_EQ(Next, nullptr);
 230       Last = Prev;
 231     } else {
 232       DCHECK_NE(Next, nullptr);
 233     }
 234     Size--;
 235   }
 236 };
 237
 238 } // namespace scudo
 239
 240 #endif // SCUDO_LIST_H_