1 //===-- sanitizer_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 // This file contains implementation of a list class to be used by
10 // ThreadSanitizer, etc run-times.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef SANITIZER_LIST_H
15 #define SANITIZER_LIST_H
16 
17 #include "sanitizer_internal_defs.h"
18 
19 namespace __sanitizer {
20 
21 // Intrusive singly-linked list with size(), push_back(), push_front()
22 // pop_front(), append_front() and append_back().
23 // This class should be a POD (so that it can be put into TLS)
24 // and an object with all zero fields should represent a valid empty list.
25 // This class does not have a CTOR, so clear() should be called on all
26 // non-zero-initialized objects before using.
27 template<class Item>
28 struct IntrusiveList {
29   friend class Iterator;
30 
clearIntrusiveList31   void clear() {
32     first_ = last_ = nullptr;
33     size_ = 0;
34   }
35 
emptyIntrusiveList36   bool empty() const { return size_ == 0; }
sizeIntrusiveList37   uptr size() const { return size_; }
38 
push_backIntrusiveList39   void push_back(Item *x) {
40     if (empty()) {
41       x->next = nullptr;
42       first_ = last_ = x;
43       size_ = 1;
44     } else {
45       x->next = nullptr;
46       last_->next = x;
47       last_ = x;
48       size_++;
49     }
50   }
51 
push_frontIntrusiveList52   void push_front(Item *x) {
53     if (empty()) {
54       x->next = nullptr;
55       first_ = last_ = x;
56       size_ = 1;
57     } else {
58       x->next = first_;
59       first_ = x;
60       size_++;
61     }
62   }
63 
pop_frontIntrusiveList64   void pop_front() {
65     CHECK(!empty());
66     first_ = first_->next;
67     if (!first_)
68       last_ = nullptr;
69     size_--;
70   }
71 
extractIntrusiveList72   void extract(Item *prev, Item *x) {
73     CHECK(!empty());
74     CHECK_NE(prev, nullptr);
75     CHECK_NE(x, nullptr);
76     CHECK_EQ(prev->next, x);
77     prev->next = x->next;
78     if (last_ == x)
79       last_ = prev;
80     size_--;
81   }
82 
frontIntrusiveList83   Item *front() { return first_; }
frontIntrusiveList84   const Item *front() const { return first_; }
backIntrusiveList85   Item *back() { return last_; }
backIntrusiveList86   const Item *back() const { return last_; }
87 
append_frontIntrusiveList88   void append_front(IntrusiveList<Item> *l) {
89     CHECK_NE(this, l);
90     if (l->empty())
91       return;
92     if (empty()) {
93       *this = *l;
94     } else if (!l->empty()) {
95       l->last_->next = first_;
96       first_ = l->first_;
97       size_ += l->size();
98     }
99     l->clear();
100   }
101 
append_backIntrusiveList102   void append_back(IntrusiveList<Item> *l) {
103     CHECK_NE(this, l);
104     if (l->empty())
105       return;
106     if (empty()) {
107       *this = *l;
108     } else {
109       last_->next = l->first_;
110       last_ = l->last_;
111       size_ += l->size();
112     }
113     l->clear();
114   }
115 
CheckConsistencyIntrusiveList116   void CheckConsistency() {
117     if (size_ == 0) {
118       CHECK_EQ(first_, 0);
119       CHECK_EQ(last_, 0);
120     } else {
121       uptr count = 0;
122       for (Item *i = first_; ; i = i->next) {
123         count++;
124         if (i == last_) break;
125       }
126       CHECK_EQ(size(), count);
127       CHECK_EQ(last_->next, 0);
128     }
129   }
130 
131   template<class ItemTy>
132   class IteratorBase {
133    public:
IteratorBaseIntrusiveList134     explicit IteratorBase(ItemTy *current) : current_(current) {}
135     IteratorBase &operator++() {
136       current_ = current_->next;
137       return *this;
138     }
139     bool operator!=(IteratorBase other) const {
140       return current_ != other.current_;
141     }
142     ItemTy &operator*() {
143       return *current_;
144     }
145    private:
146     ItemTy *current_;
147   };
148 
149   typedef IteratorBase<Item> Iterator;
150   typedef IteratorBase<const Item> ConstIterator;
151 
beginIntrusiveList152   Iterator begin() { return Iterator(first_); }
endIntrusiveList153   Iterator end() { return Iterator(0); }
154 
beginIntrusiveList155   ConstIterator begin() const { return ConstIterator(first_); }
endIntrusiveList156   ConstIterator end() const { return ConstIterator(0); }
157 
158 // private, don't use directly.
159   uptr size_;
160   Item *first_;
161   Item *last_;
162 };
163 
164 } // namespace __sanitizer
165 
166 #endif // SANITIZER_LIST_H
167