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, nullptr); 110 CHECK_EQ(Last, nullptr); 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, nullptr); 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_ 157