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