]>
Commit | Line | Data |
---|---|---|
f35db108 WM |
1 | //===-- sanitizer_list.h ----------------------------------------*- C++ -*-===// |
2 | // | |
b667dd70 ML |
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 | |
f35db108 WM |
6 | // |
7 | //===----------------------------------------------------------------------===// | |
8 | // | |
9 | // This file contains implementation of a list class to be used by | |
10 | // ThreadSanitizer, etc run-times. | |
11 | // | |
12 | //===----------------------------------------------------------------------===// | |
696d846a | 13 | |
f35db108 WM |
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 { | |
dee5ea7a KS |
29 | friend class Iterator; |
30 | ||
f35db108 | 31 | void clear() { |
696d846a | 32 | first_ = last_ = nullptr; |
f35db108 WM |
33 | size_ = 0; |
34 | } | |
35 | ||
36 | bool empty() const { return size_ == 0; } | |
37 | uptr size() const { return size_; } | |
38 | ||
39 | void push_back(Item *x) { | |
40 | if (empty()) { | |
696d846a | 41 | x->next = nullptr; |
f35db108 WM |
42 | first_ = last_ = x; |
43 | size_ = 1; | |
44 | } else { | |
696d846a | 45 | x->next = nullptr; |
f35db108 WM |
46 | last_->next = x; |
47 | last_ = x; | |
48 | size_++; | |
49 | } | |
50 | } | |
51 | ||
52 | void push_front(Item *x) { | |
53 | if (empty()) { | |
696d846a | 54 | x->next = nullptr; |
f35db108 WM |
55 | first_ = last_ = x; |
56 | size_ = 1; | |
57 | } else { | |
58 | x->next = first_; | |
59 | first_ = x; | |
60 | size_++; | |
61 | } | |
62 | } | |
63 | ||
64 | void pop_front() { | |
65 | CHECK(!empty()); | |
66 | first_ = first_->next; | |
696d846a MO |
67 | if (!first_) |
68 | last_ = nullptr; | |
f35db108 WM |
69 | size_--; |
70 | } | |
71 | ||
5d3805fc JJ |
72 | 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 | ||
f35db108 | 83 | Item *front() { return first_; } |
10189819 | 84 | const Item *front() const { return first_; } |
f35db108 | 85 | Item *back() { return last_; } |
10189819 | 86 | const Item *back() const { return last_; } |
f35db108 WM |
87 | |
88 | void append_front(IntrusiveList<Item> *l) { | |
89 | CHECK_NE(this, l); | |
2660d12d KS |
90 | if (l->empty()) |
91 | return; | |
f35db108 WM |
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 | ||
102 | void append_back(IntrusiveList<Item> *l) { | |
103 | CHECK_NE(this, l); | |
2660d12d KS |
104 | if (l->empty()) |
105 | return; | |
f35db108 WM |
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 | ||
116 | 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 | ||
10189819 | 131 | template<class ItemTy> |
696d846a | 132 | class IteratorBase { |
dee5ea7a | 133 | public: |
10189819 MO |
134 | 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_; | |
dee5ea7a | 144 | } |
dee5ea7a | 145 | private: |
696d846a | 146 | ItemTy *current_; |
dee5ea7a KS |
147 | }; |
148 | ||
10189819 MO |
149 | typedef IteratorBase<Item> Iterator; |
150 | typedef IteratorBase<const Item> ConstIterator; | |
151 | ||
152 | Iterator begin() { return Iterator(first_); } | |
153 | Iterator end() { return Iterator(0); } | |
154 | ||
155 | ConstIterator begin() const { return ConstIterator(first_); } | |
156 | ConstIterator end() const { return ConstIterator(0); } | |
696d846a | 157 | |
f35db108 WM |
158 | // private, don't use directly. |
159 | uptr size_; | |
160 | Item *first_; | |
161 | Item *last_; | |
162 | }; | |
163 | ||
696d846a | 164 | } // namespace __sanitizer |
f35db108 | 165 | |
696d846a | 166 | #endif // SANITIZER_LIST_H |