1//===-- sanitizer_list.h ----------------------------------------*- C++ -*-===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains implementation of a list class to be used by
10// ThreadSanitizer, etc run-times.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef SANITIZER_LIST_H
15#define SANITIZER_LIST_H
16
17#include "sanitizer_internal_defs.h"
18
19namespace __sanitizer {
20
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.
27template<class Item>
28struct IntrusiveList {
29 friend class Iterator;
30
31 void clear() {
32 first_ = last_ = nullptr;
33 size_ = 0;
34 }
35
36 bool empty() const { return size_ == 0; }
37 uptr size() const { return size_; }
38
39 void push_back(Item *x) {
40 if (empty()) {
41 x->next = nullptr;
42 first_ = last_ = x;
43 size_ = 1;
44 } else {
45 x->next = nullptr;
46 last_->next = x;
47 last_ = x;
48 size_++;
49 }
50 }
51
52 void push_front(Item *x) {
53 if (empty()) {
54 x->next = nullptr;
55 first_ = last_ = x;
56 size_ = 1;
57 } else {
58 x->next = first_;
59 first_ = x;
60 size_++;
61 }
62 }
63
64 void pop_front() {
65 CHECK(!empty());
66 first_ = first_->next;
67 if (!first_)
68 last_ = nullptr;
69 size_--;
70 }
71
72 void extract(Item *prev, Item *x) {
73 CHECK(!empty());
74 CHECK_NE(prev, nullptr);
75 CHECK_NE(x, nullptr);
76 CHECK_EQ(prev->next, x);
77 prev->next = x->next;
78 if (last_ == x)
79 last_ = prev;
80 size_--;
81 }
82
83 Item *front() { return first_; }
84 const Item *front() const { return first_; }
85 Item *back() { return last_; }
86 const Item *back() const { return last_; }
87
88 void append_front(IntrusiveList<Item> *l) {
89 CHECK_NE(this, l);
90 if (l->empty())
91 return;
92 if (empty()) {
93 *this = *l;
94 } else if (!l->empty()) {
95 l->last_->next = first_;
96 first_ = l->first_;
97 size_ += l->size();
98 }
99 l->clear();
100 }
101
102 void append_back(IntrusiveList<Item> *l) {
103 CHECK_NE(this, l);
104 if (l->empty())
105 return;
106 if (empty()) {
107 *this = *l;
108 } else {
109 last_->next = l->first_;
110 last_ = l->last_;
111 size_ += l->size();
112 }
113 l->clear();
114 }
115
116 void CheckConsistency() {
117 if (size_ == 0) {
118 CHECK_EQ(first_, 0);
119 CHECK_EQ(last_, 0);
120 } else {
121 uptr count = 0;
122 for (Item *i = first_; ; i = i->next) {
123 count++;
124 if (i == last_) break;
125 }
126 CHECK_EQ(size(), count);
127 CHECK_EQ(last_->next, 0);
128 }
129 }
130
131 template<class ItemTy>
132 class IteratorBase {
133 public:
134 explicit IteratorBase(ItemTy *current) : current_(current) {}
135 IteratorBase &operator++() {
136 current_ = current_->next;
137 return *this;
138 }
139 bool operator!=(IteratorBase other) const {
140 return current_ != other.current_;
141 }
142 ItemTy &operator*() {
143 return *current_;
144 }
145 private:
146 ItemTy *current_;
147 };
148
149 typedef IteratorBase<Item> Iterator;
150 typedef IteratorBase<const Item> ConstIterator;
151
152 Iterator begin() { return Iterator(first_); }
153 Iterator end() { return Iterator(0); }
154
155 ConstIterator begin() const { return ConstIterator(first_); }
156 ConstIterator end() const { return ConstIterator(0); }
157
158// private, don't use directly.
159 uptr size_;
160 Item *first_;
161 Item *last_;
162};
163
164} // namespace __sanitizer
165
166#endif // SANITIZER_LIST_H
167