sanitizer_list.h revision 1.1.1.4 
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  Item *front() { return first_; }
72  const Item *front() const { return first_; }
73  Item *back() { return last_; }
74  const Item *back() const { 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 ItemTy>
120  class IteratorBase {
121   public:
122    explicit IteratorBase(ItemTy *current) : current_(current) {}
123    IteratorBase &operator++() {
124      current_ = current_->next;
125      return *this;
126    }
127    bool operator!=(IteratorBase other) const {
128      return current_ != other.current_;
129    }
130    ItemTy &operator*() {
131      return *current_;
132    }
133   private:
134    ItemTy *current_;
135  };
136
137  typedef IteratorBase<Item> Iterator;
138  typedef IteratorBase<const Item> ConstIterator;
139
140  Iterator begin() { return Iterator(first_); }
141  Iterator end() { return Iterator(0); }
142
143  ConstIterator begin() const { return ConstIterator(first_); }
144  ConstIterator end() const { return ConstIterator(0); }
145
146// private, don't use directly.
147  uptr size_;
148  Item *first_;
149  Item *last_;
150};
151
152} // namespace __sanitizer
153
154#endif // SANITIZER_LIST_H
155