libsanitizer/tsan/tsan_ilist.h

   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