sanitizer_list.h revision 1.1.1.3 
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  Item *back() { return last_; }
73
74  void append_front(IntrusiveList<Item> *l) {
75    CHECK_NE(this, l);
76    if (l->empty())
77      return;
78    if (empty()) {
79      *this = *l;
80    } else if (!l->empty()) {
81      l->last_->next = first_;
82      first_ = l->first_;
83      size_ += l->size();
84    }
85    l->clear();
86  }
87
88  void append_back(IntrusiveList<Item> *l) {
89    CHECK_NE(this, l);
90    if (l->empty())
91      return;
92    if (empty()) {
93      *this = *l;
94    } else {
95      last_->next = l->first_;
96      last_ = l->last_;
97      size_ += l->size();
98    }
99    l->clear();
100  }
101
102  void CheckConsistency() {
103    if (size_ == 0) {
104      CHECK_EQ(first_, 0);
105      CHECK_EQ(last_, 0);
106    } else {
107      uptr count = 0;
108      for (Item *i = first_; ; i = i->next) {
109        count++;
110        if (i == last_) break;
111      }
112      CHECK_EQ(size(), count);
113      CHECK_EQ(last_->next, 0);
114    }
115  }
116
117  template<class ListTy, class ItemTy>
118  class IteratorBase {
119   public:
120    explicit IteratorBase(ListTy *list)
121        : list_(list), current_(list->first_) { }
122    ItemTy *next() {
123      ItemTy *ret = current_;
124      if (current_) current_ = current_->next;
125      return ret;
126    }
127    bool hasNext() const { return current_ != nullptr; }
128   private:
129    ListTy *list_;
130    ItemTy *current_;
131  };
132
133  typedef IteratorBase<IntrusiveList<Item>, Item> Iterator;
134  typedef IteratorBase<const IntrusiveList<Item>, const Item> ConstIterator;
135
136// private, don't use directly.
137  uptr size_;
138  Item *first_;
139  Item *last_;
140};
141
142} // namespace __sanitizer
143
144#endif // SANITIZER_LIST_H
145