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