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 
20 namespace __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.
28 template<class Item>
29 struct IntrusiveList {
30   friend class Iterator;
31 
clearIntrusiveList32   void clear() {
33     first_ = last_ = nullptr;
34     size_ = 0;
35   }
36 
emptyIntrusiveList37   bool empty() const { return size_ == 0; }
sizeIntrusiveList38   uptr size() const { return size_; }
39 
push_backIntrusiveList40   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 
push_frontIntrusiveList53   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 
pop_frontIntrusiveList65   void pop_front() {
66     CHECK(!empty());
67     first_ = first_->next;
68     if (!first_)
69       last_ = nullptr;
70     size_--;
71   }
72 
frontIntrusiveList73   Item *front() { return first_; }
frontIntrusiveList74   const Item *front() const { return first_; }
backIntrusiveList75   Item *back() { return last_; }
backIntrusiveList76   const Item *back() const { return last_; }
77 
append_frontIntrusiveList78   void append_front(IntrusiveList<Item> *l) {
79     CHECK_NE(this, l);
80     if (l->empty())
81       return;
82     if (empty()) {
83       *this = *l;
84     } else if (!l->empty()) {
85       l->last_->next = first_;
86       first_ = l->first_;
87       size_ += l->size();
88     }
89     l->clear();
90   }
91 
append_backIntrusiveList92   void append_back(IntrusiveList<Item> *l) {
93     CHECK_NE(this, l);
94     if (l->empty())
95       return;
96     if (empty()) {
97       *this = *l;
98     } else {
99       last_->next = l->first_;
100       last_ = l->last_;
101       size_ += l->size();
102     }
103     l->clear();
104   }
105 
CheckConsistencyIntrusiveList106   void CheckConsistency() {
107     if (size_ == 0) {
108       CHECK_EQ(first_, 0);
109       CHECK_EQ(last_, 0);
110     } else {
111       uptr count = 0;
112       for (Item *i = first_; ; i = i->next) {
113         count++;
114         if (i == last_) break;
115       }
116       CHECK_EQ(size(), count);
117       CHECK_EQ(last_->next, 0);
118     }
119   }
120 
121   template<class ItemTy>
122   class IteratorBase {
123    public:
IteratorBaseIntrusiveList124     explicit IteratorBase(ItemTy *current) : current_(current) {}
125     IteratorBase &operator++() {
126       current_ = current_->next;
127       return *this;
128     }
129     bool operator!=(IteratorBase other) const {
130       return current_ != other.current_;
131     }
132     ItemTy &operator*() {
133       return *current_;
134     }
135    private:
136     ItemTy *current_;
137   };
138 
139   typedef IteratorBase<Item> Iterator;
140   typedef IteratorBase<const Item> ConstIterator;
141 
beginIntrusiveList142   Iterator begin() { return Iterator(first_); }
endIntrusiveList143   Iterator end() { return Iterator(0); }
144 
beginIntrusiveList145   ConstIterator begin() const { return ConstIterator(first_); }
endIntrusiveList146   ConstIterator end() const { return ConstIterator(0); }
147 
148 // private, don't use directly.
149   uptr size_;
150   Item *first_;
151   Item *last_;
152 };
153 
154 } // namespace __sanitizer
155 
156 #endif // SANITIZER_LIST_H
157