1 //===-- sanitizer_list.h ----------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains implementation of a list class to be used by
11 // ThreadSanitizer, etc run-times.
13 //===----------------------------------------------------------------------===//
15 #ifndef SANITIZER_LIST_H
16 #define SANITIZER_LIST_H
18 #include "sanitizer_internal_defs.h"
20 namespace __sanitizer {
22 // Intrusive singly-linked list with size(), push_back(), push_front()
23 // pop_front(), append_front() and append_back().
24 // This class should be a POD (so that it can be put into TLS)
25 // and an object with all zero fields should represent a valid empty list.
26 // This class does not have a CTOR, so clear() should be called on all
27 // non-zero-initialized objects before using.
29 struct IntrusiveList {
30 friend class Iterator;
33 first_ = last_ = nullptr;
37 bool empty() const { return size_ == 0; }
38 uptr size() const { return size_; }
40 void push_back(Item *x) {
53 void push_front(Item *x) {
67 first_ = first_->next;
73 void extract(Item *prev, Item *x) {
75 CHECK_NE(prev, nullptr);
77 CHECK_EQ(prev->next, x);
84 Item *front() { return first_; }
85 const Item *front() const { return first_; }
86 Item *back() { return last_; }
87 const Item *back() const { return last_; }
89 void append_front(IntrusiveList<Item> *l) {
95 } else if (!l->empty()) {
96 l->last_->next = first_;
103 void append_back(IntrusiveList<Item> *l) {
110 last_->next = l->first_;
117 void CheckConsistency() {
123 for (Item *i = first_; ; i = i->next) {
125 if (i == last_) break;
127 CHECK_EQ(size(), count);
128 CHECK_EQ(last_->next, 0);
132 template<class ItemTy>
135 explicit IteratorBase(ItemTy *current) : current_(current) {}
136 IteratorBase &operator++() {
137 current_ = current_->next;
140 bool operator!=(IteratorBase other) const {
141 return current_ != other.current_;
143 ItemTy &operator*() {
150 typedef IteratorBase<Item> Iterator;
151 typedef IteratorBase<const Item> ConstIterator;
153 Iterator begin() { return Iterator(first_); }
154 Iterator end() { return Iterator(0); }
156 ConstIterator begin() const { return ConstIterator(first_); }
157 ConstIterator end() const { return ConstIterator(0); }
159 // private, don't use directly.
165 } // namespace __sanitizer
167 #endif // SANITIZER_LIST_H