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  void clear() {
30    first_ = last_ = 0;
31    size_ = 0;
32  }
33
34  bool empty() const { return size_ == 0; }
35  uptr size() const { return size_; }
36
37  void push_back(Item *x) {
38    if (empty()) {
39      x->next = 0;
40      first_ = last_ = x;
41      size_ = 1;
42    } else {
43      x->next = 0;
44      last_->next = x;
45      last_ = x;
46      size_++;
47    }
48  }
49
50  void push_front(Item *x) {
51    if (empty()) {
52      x->next = 0;
53      first_ = last_ = x;
54      size_ = 1;
55    } else {
56      x->next = first_;
57      first_ = x;
58      size_++;
59    }
60  }
61
62  void pop_front() {
63    CHECK(!empty());
64    first_ = first_->next;
65    if (first_ == 0)
66      last_ = 0;
67    size_--;
68  }
69
70  Item *front() { return first_; }
71  Item *back() { return last_; }
72
73  void append_front(IntrusiveList<Item> *l) {
74    CHECK_NE(this, l);
75    if (empty()) {
76      *this = *l;
77    } else if (!l->empty()) {
78      l->last_->next = first_;
79      first_ = l->first_;
80      size_ += l->size();
81    }
82    l->clear();
83  }
84
85  void append_back(IntrusiveList<Item> *l) {
86    CHECK_NE(this, l);
87    if (empty()) {
88      *this = *l;
89    } else {
90      last_->next = l->first_;
91      last_ = l->last_;
92      size_ += l->size();
93    }
94    l->clear();
95  }
96
97  void CheckConsistency() {
98    if (size_ == 0) {
99      CHECK_EQ(first_, 0);
100      CHECK_EQ(last_, 0);
101    } else {
102      uptr count = 0;
103      for (Item *i = first_; ; i = i->next) {
104        count++;
105        if (i == last_) break;
106      }
107      CHECK_EQ(size(), count);
108      CHECK_EQ(last_->next, 0);
109    }
110  }
111
112// private, don't use directly.
113  uptr size_;
114  Item *first_;
115  Item *last_;
116};
117
118}  // namespace __sanitizer
119
120#endif  // SANITIZER_LIST_H
121