1 //===-- sanitizer_list.h ----------------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file contains implementation of a list class to be used by
10 // ThreadSanitizer, etc run-times.
12 //===----------------------------------------------------------------------===//
14 #ifndef SANITIZER_LIST_H
15 #define SANITIZER_LIST_H
17 #include "sanitizer_internal_defs.h"
19 namespace __sanitizer {
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.
28 struct IntrusiveList {
29 friend class Iterator;
32 first_ = last_ = nullptr;
36 bool empty() const { return size_ == 0; }
37 uptr size() const { return size_; }
39 void push_back(Item *x) {
52 void push_front(Item *x) {
66 first_ = first_->next;
72 void extract(Item *prev, Item *x) {
74 CHECK_NE(prev, nullptr);
76 CHECK_EQ(prev->next, x);
83 Item *front() { return first_; }
84 const Item *front() const { return first_; }
85 Item *back() { return last_; }
86 const Item *back() const { return last_; }
88 void append_front(IntrusiveList<Item> *l) {
94 } else if (!l->empty()) {
95 l->last_->next = first_;
102 void append_back(IntrusiveList<Item> *l) {
109 last_->next = l->first_;
116 void CheckConsistency() {
122 for (Item *i = first_; ; i = i->next) {
124 if (i == last_) break;
126 CHECK_EQ(size(), count);
127 CHECK_EQ(last_->next, 0);
131 template<class ItemTy>
134 explicit IteratorBase(ItemTy *current) : current_(current) {}
135 IteratorBase &operator++() {
136 current_ = current_->next;
139 bool operator!=(IteratorBase other) const {
140 return current_ != other.current_;
142 ItemTy &operator*() {
149 typedef IteratorBase<Item> Iterator;
150 typedef IteratorBase<const Item> ConstIterator;
152 Iterator begin() { return Iterator(first_); }
153 Iterator end() { return Iterator(0); }
155 ConstIterator begin() const { return ConstIterator(first_); }
156 ConstIterator end() const { return ConstIterator(0); }
158 // private, don't use directly.
164 } // namespace __sanitizer
166 #endif // SANITIZER_LIST_H