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