1//===-- tsan_ilist.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 is a part of ThreadSanitizer (TSan), a race detector.
10//
11//===----------------------------------------------------------------------===//
12#ifndef TSAN_ILIST_H
13#define TSAN_ILIST_H
14
15#include "sanitizer_common/sanitizer_internal_defs.h"
16
17namespace __tsan {
18
19class INode {
20 public:
21 INode() = default;
22
23 private:
24 INode* next_ = nullptr;
25 INode* prev_ = nullptr;
26
27 template <typename Base, INode Base::*Node, typename Elem>
28 friend class IList;
29 INode(const INode&) = delete;
30 void operator=(const INode&) = delete;
31};
32
33// Intrusive doubly-linked list.
34//
35// The node class (MyNode) needs to include "INode foo" field,
36// then the list can be declared as IList<MyNode, &MyNode::foo>.
37// This design allows to link MyNode into multiple lists using
38// different INode fields.
39// The optional Elem template argument allows to specify node MDT
40// (most derived type) if it's different from MyNode.
41template <typename Base, INode Base::*Node, typename Elem = Base>
42class IList {
43 public:
44 IList();
45
46 void PushFront(Elem* e);
47 void PushBack(Elem* e);
48 void Remove(Elem* e);
49
50 Elem* PopFront();
51 Elem* PopBack();
52 Elem* Front();
53 Elem* Back();
54
55 // Prev links point towards front of the queue.
56 Elem* Prev(Elem* e);
57 // Next links point towards back of the queue.
58 Elem* Next(Elem* e);
59
60 uptr Size() const;
61 bool Empty() const;
62 bool Queued(Elem* e) const;
63
64 private:
65 INode node_;
66 uptr size_ = 0;
67
68 void Push(Elem* e, INode* after);
69 static INode* ToNode(Elem* e);
70 static Elem* ToElem(INode* n);
71
72 IList(const IList&) = delete;
73 void operator=(const IList&) = delete;
74};
75
76template <typename Base, INode Base::*Node, typename Elem>
77IList<Base, Node, Elem>::IList() {
78 node_.next_ = node_.prev_ = &node_;
79}
80
81template <typename Base, INode Base::*Node, typename Elem>
82void IList<Base, Node, Elem>::PushFront(Elem* e) {
83 Push(e, after: &node_);
84}
85
86template <typename Base, INode Base::*Node, typename Elem>
87void IList<Base, Node, Elem>::PushBack(Elem* e) {
88 Push(e, after: node_.prev_);
89}
90
91template <typename Base, INode Base::*Node, typename Elem>
92void IList<Base, Node, Elem>::Push(Elem* e, INode* after) {
93 INode* n = ToNode(e);
94 DCHECK_EQ(n->next_, nullptr);
95 DCHECK_EQ(n->prev_, nullptr);
96 INode* next = after->next_;
97 n->next_ = next;
98 n->prev_ = after;
99 next->prev_ = n;
100 after->next_ = n;
101 size_++;
102}
103
104template <typename Base, INode Base::*Node, typename Elem>
105void IList<Base, Node, Elem>::Remove(Elem* e) {
106 INode* n = ToNode(e);
107 INode* next = n->next_;
108 INode* prev = n->prev_;
109 DCHECK(next);
110 DCHECK(prev);
111 DCHECK(size_);
112 next->prev_ = prev;
113 prev->next_ = next;
114 n->prev_ = n->next_ = nullptr;
115 size_--;
116}
117
118template <typename Base, INode Base::*Node, typename Elem>
119Elem* IList<Base, Node, Elem>::PopFront() {
120 Elem* e = Front();
121 if (e)
122 Remove(e);
123 return e;
124}
125
126template <typename Base, INode Base::*Node, typename Elem>
127Elem* IList<Base, Node, Elem>::PopBack() {
128 Elem* e = Back();
129 if (e)
130 Remove(e);
131 return e;
132}
133
134template <typename Base, INode Base::*Node, typename Elem>
135Elem* IList<Base, Node, Elem>::Front() {
136 return size_ ? ToElem(n: node_.next_) : nullptr;
137}
138
139template <typename Base, INode Base::*Node, typename Elem>
140Elem* IList<Base, Node, Elem>::Back() {
141 return size_ ? ToElem(n: node_.prev_) : nullptr;
142}
143
144template <typename Base, INode Base::*Node, typename Elem>
145Elem* IList<Base, Node, Elem>::Prev(Elem* e) {
146 INode* n = ToNode(e);
147 DCHECK(n->prev_);
148 return n->prev_ != &node_ ? ToElem(n: n->prev_) : nullptr;
149}
150
151template <typename Base, INode Base::*Node, typename Elem>
152Elem* IList<Base, Node, Elem>::Next(Elem* e) {
153 INode* n = ToNode(e);
154 DCHECK(n->next_);
155 return n->next_ != &node_ ? ToElem(n: n->next_) : nullptr;
156}
157
158template <typename Base, INode Base::*Node, typename Elem>
159uptr IList<Base, Node, Elem>::Size() const {
160 return size_;
161}
162
163template <typename Base, INode Base::*Node, typename Elem>
164bool IList<Base, Node, Elem>::Empty() const {
165 return size_ == 0;
166}
167
168template <typename Base, INode Base::*Node, typename Elem>
169bool IList<Base, Node, Elem>::Queued(Elem* e) const {
170 INode* n = ToNode(e);
171 DCHECK_EQ(!n->next_, !n->prev_);
172 return n->next_;
173}
174
175template <typename Base, INode Base::*Node, typename Elem>
176INode* IList<Base, Node, Elem>::ToNode(Elem* e) {
177 return &(e->*Node);
178}
179
180template <typename Base, INode Base::*Node, typename Elem>
181Elem* IList<Base, Node, Elem>::ToElem(INode* n) {
182 return static_cast<Elem*>(reinterpret_cast<Base*>(
183 reinterpret_cast<uptr>(n) -
184 reinterpret_cast<uptr>(&(reinterpret_cast<Elem*>(0)->*Node))));
185}
186
187} // namespace __tsan
188
189#endif
190