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, &node_); 84} 85 86template <typename Base, INode Base::*Node, typename Elem> 87void IList<Base, Node, Elem>::PushBack(Elem* e) { 88 Push(e, 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(node_.next_) : nullptr; 137} 138 139template <typename Base, INode Base::*Node, typename Elem> 140Elem* IList<Base, Node, Elem>::Back() { 141 return size_ ? ToElem(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->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->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