190 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file is a part of ThreadSanitizer (TSan), a race detector.10//11//===----------------------------------------------------------------------===//12#ifndef TSAN_ILIST_H13#define TSAN_ILIST_H14 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 using38// different INode fields.39// The optional Elem template argument allows to specify node MDT40// (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 __tsan188 189#endif190