1//===-- sanitizer_list.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 contains implementation of a list class to be used by
10// ThreadSanitizer, etc run-times.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef SANITIZER_LIST_H
15#define SANITIZER_LIST_H
16
17#include "sanitizer_internal_defs.h"
18
19namespace __sanitizer {
20
21// Intrusive singly-linked list with size(), push_back(), push_front()
22// pop_front(), append_front() and append_back().
23// This class should be a POD (so that it can be put into TLS)
24// and an object with all zero fields should represent a valid empty list.
25// This class does not have a CTOR, so clear() should be called on all
26// non-zero-initialized objects before using.
27template<class Item>
28struct IntrusiveList {
29  friend class Iterator;
30
31  void clear() {
32    first_ = last_ = nullptr;
33    size_ = 0;
34  }
35
36  bool empty() const { return size_ == 0; }
37  uptr size() const { return size_; }
38
39  void push_back(Item *x) {
40    if (empty()) {
41      x->next = nullptr;
42      first_ = last_ = x;
43      size_ = 1;
44    } else {
45      x->next = nullptr;
46      last_->next = x;
47      last_ = x;
48      size_++;
49    }
50  }
51
52  void push_front(Item *x) {
53    if (empty()) {
54      x->next = nullptr;
55      first_ = last_ = x;
56      size_ = 1;
57    } else {
58      x->next = first_;
59      first_ = x;
60      size_++;
61    }
62  }
63
64  void pop_front() {
65    CHECK(!empty());
66    first_ = first_->next;
67    if (!first_)
68      last_ = nullptr;
69    size_--;
70  }
71
72  void extract(Item *prev, Item *x) {
73    CHECK(!empty());
74    CHECK_NE(prev, nullptr);
75    CHECK_NE(x, nullptr);
76    CHECK_EQ(prev->next, x);
77    prev->next = x->next;
78    if (last_ == x)
79      last_ = prev;
80    size_--;
81  }
82
83  Item *front() { return first_; }
84  const Item *front() const { return first_; }
85  Item *back() { return last_; }
86  const Item *back() const { return last_; }
87
88  void append_front(IntrusiveList<Item> *l) {
89    CHECK_NE(this, l);
90    if (l->empty())
91      return;
92    if (empty()) {
93      *this = *l;
94    } else if (!l->empty()) {
95      l->last_->next = first_;
96      first_ = l->first_;
97      size_ += l->size();
98    }
99    l->clear();
100  }
101
102  void append_back(IntrusiveList<Item> *l) {
103    CHECK_NE(this, l);
104    if (l->empty())
105      return;
106    if (empty()) {
107      *this = *l;
108    } else {
109      last_->next = l->first_;
110      last_ = l->last_;
111      size_ += l->size();
112    }
113    l->clear();
114  }
115
116  void CheckConsistency() {
117    if (size_ == 0) {
118      CHECK_EQ(first_, 0);
119      CHECK_EQ(last_, 0);
120    } else {
121      uptr count = 0;
122      for (Item *i = first_; ; i = i->next) {
123        count++;
124        if (i == last_) break;
125      }
126      CHECK_EQ(size(), count);
127      CHECK_EQ(last_->next, 0);
128    }
129  }
130
131  template<class ItemTy>
132  class IteratorBase {
133   public:
134    explicit IteratorBase(ItemTy *current) : current_(current) {}
135    IteratorBase &operator++() {
136      current_ = current_->next;
137      return *this;
138    }
139    bool operator!=(IteratorBase other) const {
140      return current_ != other.current_;
141    }
142    ItemTy &operator*() {
143      return *current_;
144    }
145   private:
146    ItemTy *current_;
147  };
148
149  typedef IteratorBase<Item> Iterator;
150  typedef IteratorBase<const Item> ConstIterator;
151
152  Iterator begin() { return Iterator(first_); }
153  Iterator end() { return Iterator(0); }
154
155  ConstIterator begin() const { return ConstIterator(first_); }
156  ConstIterator end() const { return ConstIterator(0); }
157
158// private, don't use directly.
159  uptr size_;
160  Item *first_;
161  Item *last_;
162};
163
164} // namespace __sanitizer
165
166#endif // SANITIZER_LIST_H
167