• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
19 namespace __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.
27 template<class Item>
28 struct IntrusiveList {
clearIntrusiveList29   void clear() {
30     first_ = last_ = 0;
31     size_ = 0;
32   }
33 
emptyIntrusiveList34   bool empty() const { return size_ == 0; }
sizeIntrusiveList35   uptr size() const { return size_; }
36 
push_backIntrusiveList37   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 
push_frontIntrusiveList50   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 
pop_frontIntrusiveList62   void pop_front() {
63     CHECK(!empty());
64     first_ = first_->next;
65     if (first_ == 0)
66       last_ = 0;
67     size_--;
68   }
69 
frontIntrusiveList70   Item *front() { return first_; }
backIntrusiveList71   Item *back() { return last_; }
72 
append_frontIntrusiveList73   void append_front(IntrusiveList<Item> *l) {
74     CHECK_NE(this, l);
75     if (l->empty())
76       return;
77     if (empty()) {
78       *this = *l;
79     } else if (!l->empty()) {
80       l->last_->next = first_;
81       first_ = l->first_;
82       size_ += l->size();
83     }
84     l->clear();
85   }
86 
append_backIntrusiveList87   void append_back(IntrusiveList<Item> *l) {
88     CHECK_NE(this, l);
89     if (l->empty())
90       return;
91     if (empty()) {
92       *this = *l;
93     } else {
94       last_->next = l->first_;
95       last_ = l->last_;
96       size_ += l->size();
97     }
98     l->clear();
99   }
100 
CheckConsistencyIntrusiveList101   void CheckConsistency() {
102     if (size_ == 0) {
103       CHECK_EQ(first_, 0);
104       CHECK_EQ(last_, 0);
105     } else {
106       uptr count = 0;
107       for (Item *i = first_; ; i = i->next) {
108         count++;
109         if (i == last_) break;
110       }
111       CHECK_EQ(size(), count);
112       CHECK_EQ(last_->next, 0);
113     }
114   }
115 
116 // private, don't use directly.
117   uptr size_;
118   Item *first_;
119   Item *last_;
120 };
121 
122 }  // namespace __sanitizer
123 
124 #endif  // SANITIZER_LIST_H
125