contrib/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-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 template <class Item> struct IntrusiveList {
  20   friend class Iterator;
  21
  22   void clear() {
  23     First = Last = nullptr;
  24     Size = 0;
  25   }
  26
  27   bool empty() const { return Size == 0; }
  28   uptr size() const { return Size; }
  29
  30   void push_back(Item *X) {
  31     if (empty()) {
  32       X->Next = nullptr;
  33       First = Last = X;
  34       Size = 1;
  35     } else {
  36       X->Next = nullptr;
  37       Last->Next = X;
  38       Last = X;
  39       Size++;
  40     }
  41   }
  42
  43   void push_front(Item *X) {
  44     if (empty()) {
  45       X->Next = nullptr;
  46       First = Last = X;
  47       Size = 1;
  48     } else {
  49       X->Next = First;
  50       First = X;
  51       Size++;
  52     }
  53   }
  54
  55   void pop_front() {
  56     DCHECK(!empty());
  57     First = First->Next;
  58     if (!First)
  59       Last = nullptr;
  60     Size--;
  61   }
  62
  63   void extract(Item *Prev, Item *X) {
  64     DCHECK(!empty());
  65     DCHECK_NE(Prev, nullptr);
  66     DCHECK_NE(X, nullptr);
  67     DCHECK_EQ(Prev->Next, X);
  68     Prev->Next = X->Next;
  69     if (Last == X)
  70       Last = Prev;
  71     Size--;
  72   }
  73
  74   Item *front() { return First; }
  75   const Item *front() const { return First; }
  76   Item *back() { return Last; }
  77   const Item *back() const { return Last; }
  78
  79   void append_front(IntrusiveList<Item> *L) {
  80     DCHECK_NE(this, L);
  81     if (L->empty())
  82       return;
  83     if (empty()) {
  84       *this = *L;
  85     } else if (!L->empty()) {
  86       L->Last->Next = First;
  87       First = L->First;
  88       Size += L->size();
  89     }
  90     L->clear();
  91   }
  92
  93   void append_back(IntrusiveList<Item> *L) {
  94     DCHECK_NE(this, L);
  95     if (L->empty())
  96       return;
  97     if (empty()) {
  98       *this = *L;
  99     } else {
 100       Last->Next = L->First;
 101       Last = L->Last;
 102       Size += L->size();
 103     }
 104     L->clear();
 105   }
 106
 107   void checkConsistency() {
 108     if (Size == 0) {
 109       CHECK_EQ(First, 0);
 110       CHECK_EQ(Last, 0);
 111     } else {
 112       uptr count = 0;
 113       for (Item *I = First;; I = I->Next) {
 114         count++;
 115         if (I == Last)
 116           break;
 117       }
 118       CHECK_EQ(size(), count);
 119       CHECK_EQ(Last->Next, 0);
 120     }
 121   }
 122
 123   template <class ItemT> class IteratorBase {
 124   public:
 125     explicit IteratorBase(ItemT *CurrentItem) : Current(CurrentItem) {}
 126     IteratorBase &operator++() {
 127       Current = Current->Next;
 128       return *this;
 129     }
 130     bool operator!=(IteratorBase Other) const {
 131       return Current != Other.Current;
 132     }
 133     ItemT &operator*() { return *Current; }
 134
 135   private:
 136     ItemT *Current;
 137   };
 138
 139   typedef IteratorBase<Item> Iterator;
 140   typedef IteratorBase<const Item> ConstIterator;
 141
 142   Iterator begin() { return Iterator(First); }
 143   Iterator end() { return Iterator(nullptr); }
 144
 145   ConstIterator begin() const { return ConstIterator(First); }
 146   ConstIterator end() const { return ConstIterator(nullptr); }
 147
 148 private:
 149   uptr Size;
 150   Item *First;
 151   Item *Last;
 152 };
 153
 154 } // namespace scudo
 155
 156 #endif // SCUDO_LIST_H_