1 //===-- list.h --------------------------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
12 #include "internal_defs.h"
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.
20 template <class T> class IteratorBase {
22 explicit IteratorBase(T *CurrentT) : Current(CurrentT) {}
23 IteratorBase &operator++() {
24 Current = Current->Next;
27 bool operator!=(IteratorBase Other) const { return Current != Other.Current; }
28 T &operator*() { return *Current; }
34 template <class T> struct IntrusiveList {
35 bool empty() const { return Size == 0; }
36 uptr size() const { return Size; }
38 T *front() { return First; }
39 const T *front() const { return First; }
40 T *back() { return Last; }
41 const T *back() const { return Last; }
44 First = Last = nullptr;
48 typedef IteratorBase<T> Iterator;
49 typedef IteratorBase<const T> ConstIterator;
51 Iterator begin() { return Iterator(First); }
52 Iterator end() { return Iterator(nullptr); }
54 ConstIterator begin() const { return ConstIterator(First); }
55 ConstIterator end() const { return ConstIterator(nullptr); }
57 void checkConsistency() const;
65 template <class T> void IntrusiveList<T>::checkConsistency() const {
67 CHECK_EQ(First, nullptr);
68 CHECK_EQ(Last, nullptr);
71 for (T *I = First;; I = I->Next) {
76 CHECK_EQ(this->size(), Count);
77 CHECK_EQ(Last->Next, nullptr);
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;
87 void push_back(T *X) {
97 void push_front(T *X) {
113 void extract(T *Prev, T *X) {
115 DCHECK_NE(Prev, nullptr);
116 DCHECK_NE(X, nullptr);
117 DCHECK_EQ(Prev->Next, X);
118 Prev->Next = X->Next;
124 void append_back(SinglyLinkedList<T> *L) {
131 Last->Next = L->First;
139 template <class T> struct DoublyLinkedList : IntrusiveList<T> {
140 using IntrusiveList<T>::First;
141 using IntrusiveList<T>::Last;
142 using IntrusiveList<T>::Size;
143 using IntrusiveList<T>::empty;
145 void push_front(T *X) {
150 DCHECK_EQ(First->Prev, nullptr);
158 // Inserts X before Y.
159 void insert(T *X, T *Y) {
161 return push_front(X);
163 // This is a hard CHECK to ensure consistency in the event of an intentional
164 // corruption of Y->Prev, to prevent a potential write-{4,8}.
165 CHECK_EQ(Prev->Next, Y);
173 void push_back(T *X) {
178 DCHECK_EQ(Last->Next, nullptr);
192 First->Prev = nullptr;
196 // The consistency of the adjacent links is aggressively checked in order to
197 // catch potential corruption attempts, that could yield a mirrored
198 // write-{4,8} primitive. nullptr checks are deemed less vital.
203 CHECK_EQ(Prev->Next, X);
207 CHECK_EQ(Next->Prev, X);
211 DCHECK_EQ(Prev, nullptr);
214 DCHECK_NE(Prev, nullptr);
217 DCHECK_EQ(Next, nullptr);
220 DCHECK_NE(Next, nullptr);
228 #endif // SCUDO_LIST_H_