function.c (assign_parm_adjust_stack_rtl): Revise STRICT_ALIGNMENT check to use targe...
[official-gcc.git] / libsanitizer / sanitizer_common / sanitizer_list.h
blobd7e8b501a6eeabaf0460cb86a3a1d23d5fd99cc6
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.
11 //===----------------------------------------------------------------------===//
13 #ifndef SANITIZER_LIST_H
14 #define SANITIZER_LIST_H
16 #include "sanitizer_internal_defs.h"
18 namespace __sanitizer {
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 {
28 friend class Iterator;
30 void clear() {
31 first_ = last_ = nullptr;
32 size_ = 0;
35 bool empty() const { return size_ == 0; }
36 uptr size() const { return size_; }
38 void push_back(Item *x) {
39 if (empty()) {
40 x->next = nullptr;
41 first_ = last_ = x;
42 size_ = 1;
43 } else {
44 x->next = nullptr;
45 last_->next = x;
46 last_ = x;
47 size_++;
51 void push_front(Item *x) {
52 if (empty()) {
53 x->next = nullptr;
54 first_ = last_ = x;
55 size_ = 1;
56 } else {
57 x->next = first_;
58 first_ = x;
59 size_++;
63 void pop_front() {
64 CHECK(!empty());
65 first_ = first_->next;
66 if (!first_)
67 last_ = nullptr;
68 size_--;
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_--;
82 Item *front() { return first_; }
83 const Item *front() const { return first_; }
84 Item *back() { return last_; }
85 const Item *back() const { return last_; }
87 void append_front(IntrusiveList<Item> *l) {
88 CHECK_NE(this, l);
89 if (l->empty())
90 return;
91 if (empty()) {
92 *this = *l;
93 } else if (!l->empty()) {
94 l->last_->next = first_;
95 first_ = l->first_;
96 size_ += l->size();
98 l->clear();
101 void append_back(IntrusiveList<Item> *l) {
102 CHECK_NE(this, l);
103 if (l->empty())
104 return;
105 if (empty()) {
106 *this = *l;
107 } else {
108 last_->next = l->first_;
109 last_ = l->last_;
110 size_ += l->size();
112 l->clear();
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;
125 CHECK_EQ(size(), count);
126 CHECK_EQ(last_->next, 0);
130 template<class ItemTy>
131 class IteratorBase {
132 public:
133 explicit IteratorBase(ItemTy *current) : current_(current) {}
134 IteratorBase &operator++() {
135 current_ = current_->next;
136 return *this;
138 bool operator!=(IteratorBase other) const {
139 return current_ != other.current_;
141 ItemTy &operator*() {
142 return *current_;
144 private:
145 ItemTy *current_;
148 typedef IteratorBase<Item> Iterator;
149 typedef IteratorBase<const Item> ConstIterator;
151 Iterator begin() { return Iterator(first_); }
152 Iterator end() { return Iterator(0); }
154 ConstIterator begin() const { return ConstIterator(first_); }
155 ConstIterator end() const { return ConstIterator(0); }
157 // private, don't use directly.
158 uptr size_;
159 Item *first_;
160 Item *last_;
163 } // namespace __sanitizer
165 #endif // SANITIZER_LIST_H