list.h revision 351282 
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
14namespace 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.
19template <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
148private:
149  uptr Size;
150  Item *First;
151  Item *Last;
152};
153
154} // namespace scudo
155
156#endif // SCUDO_LIST_H_
157