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