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-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;
23 First = Last = nullptr;
27 bool empty() const { return Size == 0; }
28 uptr size() const { return Size; }
30 void push_back(Item *X) {
43 void push_front(Item *X) {
63 void extract(Item *Prev, Item *X) {
65 DCHECK_NE(Prev, nullptr);
66 DCHECK_NE(X, nullptr);
67 DCHECK_EQ(Prev->Next, X);
74 Item *front() { return First; }
75 const Item *front() const { return First; }
76 Item *back() { return Last; }
77 const Item *back() const { return Last; }
79 void append_front(IntrusiveList<Item> *L) {
85 } else if (!L->empty()) {
86 L->Last->Next = First;
93 void append_back(IntrusiveList<Item> *L) {
100 Last->Next = L->First;
107 void checkConsistency() {
113 for (Item *I = First;; I = I->Next) {
118 CHECK_EQ(size(), count);
119 CHECK_EQ(Last->Next, 0);
123 template <class ItemT> class IteratorBase {
125 explicit IteratorBase(ItemT *CurrentItem) : Current(CurrentItem) {}
126 IteratorBase &operator++() {
127 Current = Current->Next;
130 bool operator!=(IteratorBase Other) const {
131 return Current != Other.Current;
133 ItemT &operator*() { return *Current; }
139 typedef IteratorBase<Item> Iterator;
140 typedef IteratorBase<const Item> ConstIterator;
142 Iterator begin() { return Iterator(First); }
143 Iterator end() { return Iterator(nullptr); }
145 ConstIterator begin() const { return ConstIterator(First); }
146 ConstIterator end() const { return ConstIterator(nullptr); }
156 #endif // SCUDO_LIST_H_