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