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 
17 namespace __tsan {
18 
19 class 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.
41 template <typename Base, INode Base::*Node, typename Elem = Base>
42 class 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 
76 template <typename Base, INode Base::*Node, typename Elem>
77 IList<Base, Node, Elem>::IList() {
78   node_.next_ = node_.prev_ = &node_;
79 }
80 
81 template <typename Base, INode Base::*Node, typename Elem>
82 void IList<Base, Node, Elem>::PushFront(Elem* e) {
83   Push(e, &node_);
84 }
85 
86 template <typename Base, INode Base::*Node, typename Elem>
87 void IList<Base, Node, Elem>::PushBack(Elem* e) {
88   Push(e, node_.prev_);
89 }
90 
91 template <typename Base, INode Base::*Node, typename Elem>
92 void 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 
104 template <typename Base, INode Base::*Node, typename Elem>
105 void 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 
118 template <typename Base, INode Base::*Node, typename Elem>
119 Elem* IList<Base, Node, Elem>::PopFront() {
120   Elem* e = Front();
121   if (e)
122     Remove(e);
123   return e;
124 }
125 
126 template <typename Base, INode Base::*Node, typename Elem>
127 Elem* IList<Base, Node, Elem>::PopBack() {
128   Elem* e = Back();
129   if (e)
130     Remove(e);
131   return e;
132 }
133 
134 template <typename Base, INode Base::*Node, typename Elem>
135 Elem* IList<Base, Node, Elem>::Front() {
136   return size_ ? ToElem(node_.next_) : nullptr;
137 }
138 
139 template <typename Base, INode Base::*Node, typename Elem>
140 Elem* IList<Base, Node, Elem>::Back() {
141   return size_ ? ToElem(node_.prev_) : nullptr;
142 }
143 
144 template <typename Base, INode Base::*Node, typename Elem>
145 Elem* IList<Base, Node, Elem>::Prev(Elem* e) {
146   INode* n = ToNode(e);
147   DCHECK(n->prev_);
148   return n->prev_ != &node_ ? ToElem(n->prev_) : nullptr;
149 }
150 
151 template <typename Base, INode Base::*Node, typename Elem>
152 Elem* IList<Base, Node, Elem>::Next(Elem* e) {
153   INode* n = ToNode(e);
154   DCHECK(n->next_);
155   return n->next_ != &node_ ? ToElem(n->next_) : nullptr;
156 }
157 
158 template <typename Base, INode Base::*Node, typename Elem>
159 uptr IList<Base, Node, Elem>::Size() const {
160   return size_;
161 }
162 
163 template <typename Base, INode Base::*Node, typename Elem>
164 bool IList<Base, Node, Elem>::Empty() const {
165   return size_ == 0;
166 }
167 
168 template <typename Base, INode Base::*Node, typename Elem>
169 bool 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 
175 template <typename Base, INode Base::*Node, typename Elem>
176 INode* IList<Base, Node, Elem>::ToNode(Elem* e) {
177   return &(e->*Node);
178 }
179 
180 template <typename Base, INode Base::*Node, typename Elem>
181 Elem* 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