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