]>
Commit | Line | Data |
---|---|---|
f35db108 WM |
1 | //===-- sanitizer_list.h ----------------------------------------*- C++ -*-===// |
2 | // | |
3 | // This file is distributed under the University of Illinois Open Source | |
4 | // License. See LICENSE.TXT for details. | |
5 | // | |
6 | //===----------------------------------------------------------------------===// | |
7 | // | |
8 | // This file contains implementation of a list class to be used by | |
9 | // ThreadSanitizer, etc run-times. | |
10 | // | |
11 | //===----------------------------------------------------------------------===// | |
696d846a | 12 | |
f35db108 WM |
13 | #ifndef SANITIZER_LIST_H |
14 | #define SANITIZER_LIST_H | |
15 | ||
16 | #include "sanitizer_internal_defs.h" | |
17 | ||
18 | namespace __sanitizer { | |
19 | ||
20 | // Intrusive singly-linked list with size(), push_back(), push_front() | |
21 | // pop_front(), append_front() and append_back(). | |
22 | // This class should be a POD (so that it can be put into TLS) | |
23 | // and an object with all zero fields should represent a valid empty list. | |
24 | // This class does not have a CTOR, so clear() should be called on all | |
25 | // non-zero-initialized objects before using. | |
26 | template<class Item> | |
27 | struct IntrusiveList { | |
dee5ea7a KS |
28 | friend class Iterator; |
29 | ||
f35db108 | 30 | void clear() { |
696d846a | 31 | first_ = last_ = nullptr; |
f35db108 WM |
32 | size_ = 0; |
33 | } | |
34 | ||
35 | bool empty() const { return size_ == 0; } | |
36 | uptr size() const { return size_; } | |
37 | ||
38 | void push_back(Item *x) { | |
39 | if (empty()) { | |
696d846a | 40 | x->next = nullptr; |
f35db108 WM |
41 | first_ = last_ = x; |
42 | size_ = 1; | |
43 | } else { | |
696d846a | 44 | x->next = nullptr; |
f35db108 WM |
45 | last_->next = x; |
46 | last_ = x; | |
47 | size_++; | |
48 | } | |
49 | } | |
50 | ||
51 | void push_front(Item *x) { | |
52 | if (empty()) { | |
696d846a | 53 | x->next = nullptr; |
f35db108 WM |
54 | first_ = last_ = x; |
55 | size_ = 1; | |
56 | } else { | |
57 | x->next = first_; | |
58 | first_ = x; | |
59 | size_++; | |
60 | } | |
61 | } | |
62 | ||
63 | void pop_front() { | |
64 | CHECK(!empty()); | |
65 | first_ = first_->next; | |
696d846a MO |
66 | if (!first_) |
67 | last_ = nullptr; | |
f35db108 WM |
68 | size_--; |
69 | } | |
70 | ||
5d3805fc JJ |
71 | void extract(Item *prev, Item *x) { |
72 | CHECK(!empty()); | |
73 | CHECK_NE(prev, nullptr); | |
74 | CHECK_NE(x, nullptr); | |
75 | CHECK_EQ(prev->next, x); | |
76 | prev->next = x->next; | |
77 | if (last_ == x) | |
78 | last_ = prev; | |
79 | size_--; | |
80 | } | |
81 | ||
f35db108 | 82 | Item *front() { return first_; } |
10189819 | 83 | const Item *front() const { return first_; } |
f35db108 | 84 | Item *back() { return last_; } |
10189819 | 85 | const Item *back() const { return last_; } |
f35db108 WM |
86 | |
87 | void append_front(IntrusiveList<Item> *l) { | |
88 | CHECK_NE(this, l); | |
2660d12d KS |
89 | if (l->empty()) |
90 | return; | |
f35db108 WM |
91 | if (empty()) { |
92 | *this = *l; | |
93 | } else if (!l->empty()) { | |
94 | l->last_->next = first_; | |
95 | first_ = l->first_; | |
96 | size_ += l->size(); | |
97 | } | |
98 | l->clear(); | |
99 | } | |
100 | ||
101 | void append_back(IntrusiveList<Item> *l) { | |
102 | CHECK_NE(this, l); | |
2660d12d KS |
103 | if (l->empty()) |
104 | return; | |
f35db108 WM |
105 | if (empty()) { |
106 | *this = *l; | |
107 | } else { | |
108 | last_->next = l->first_; | |
109 | last_ = l->last_; | |
110 | size_ += l->size(); | |
111 | } | |
112 | l->clear(); | |
113 | } | |
114 | ||
115 | void CheckConsistency() { | |
116 | if (size_ == 0) { | |
117 | CHECK_EQ(first_, 0); | |
118 | CHECK_EQ(last_, 0); | |
119 | } else { | |
120 | uptr count = 0; | |
121 | for (Item *i = first_; ; i = i->next) { | |
122 | count++; | |
123 | if (i == last_) break; | |
124 | } | |
125 | CHECK_EQ(size(), count); | |
126 | CHECK_EQ(last_->next, 0); | |
127 | } | |
128 | } | |
129 | ||
10189819 | 130 | template<class ItemTy> |
696d846a | 131 | class IteratorBase { |
dee5ea7a | 132 | public: |
10189819 MO |
133 | explicit IteratorBase(ItemTy *current) : current_(current) {} |
134 | IteratorBase &operator++() { | |
135 | current_ = current_->next; | |
136 | return *this; | |
137 | } | |
138 | bool operator!=(IteratorBase other) const { | |
139 | return current_ != other.current_; | |
140 | } | |
141 | ItemTy &operator*() { | |
142 | return *current_; | |
dee5ea7a | 143 | } |
dee5ea7a | 144 | private: |
696d846a | 145 | ItemTy *current_; |
dee5ea7a KS |
146 | }; |
147 | ||
10189819 MO |
148 | typedef IteratorBase<Item> Iterator; |
149 | typedef IteratorBase<const Item> ConstIterator; | |
150 | ||
151 | Iterator begin() { return Iterator(first_); } | |
152 | Iterator end() { return Iterator(0); } | |
153 | ||
154 | ConstIterator begin() const { return ConstIterator(first_); } | |
155 | ConstIterator end() const { return ConstIterator(0); } | |
696d846a | 156 | |
f35db108 WM |
157 | // private, don't use directly. |
158 | uptr size_; | |
159 | Item *first_; | |
160 | Item *last_; | |
161 | }; | |
162 | ||
696d846a | 163 | } // namespace __sanitizer |
f35db108 | 164 | |
696d846a | 165 | #endif // SANITIZER_LIST_H |