1 //===-- sanitizer_list.h ----------------------------------------*- C++ -*-===//
3 // This file is distributed under the University of Illinois Open Source
4 // License. See LICENSE.TXT for details.
6 //===----------------------------------------------------------------------===//
8 // This file contains implementation of a list class to be used by
9 // ThreadSanitizer, etc run-times.
11 //===----------------------------------------------------------------------===//
13 #ifndef SANITIZER_LIST_H
14 #define SANITIZER_LIST_H
16 #include "sanitizer_internal_defs.h"
18 namespace __sanitizer
{
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.
27 struct IntrusiveList
{
28 friend class Iterator
;
31 first_
= last_
= nullptr;
35 bool empty() const { return size_
== 0; }
36 uptr
size() const { return size_
; }
38 void push_back(Item
*x
) {
51 void push_front(Item
*x
) {
65 first_
= first_
->next
;
71 void extract(Item
*prev
, Item
*x
) {
73 CHECK_NE(prev
, nullptr);
75 CHECK_EQ(prev
->next
, x
);
82 Item
*front() { return first_
; }
83 const Item
*front() const { return first_
; }
84 Item
*back() { return last_
; }
85 const Item
*back() const { return last_
; }
87 void append_front(IntrusiveList
<Item
> *l
) {
93 } else if (!l
->empty()) {
94 l
->last_
->next
= first_
;
101 void append_back(IntrusiveList
<Item
> *l
) {
108 last_
->next
= l
->first_
;
115 void CheckConsistency() {
121 for (Item
*i
= first_
; ; i
= i
->next
) {
123 if (i
== last_
) break;
125 CHECK_EQ(size(), count
);
126 CHECK_EQ(last_
->next
, 0);
130 template<class ItemTy
>
133 explicit IteratorBase(ItemTy
*current
) : current_(current
) {}
134 IteratorBase
&operator++() {
135 current_
= current_
->next
;
138 bool operator!=(IteratorBase other
) const {
139 return current_
!= other
.current_
;
141 ItemTy
&operator*() {
148 typedef IteratorBase
<Item
> Iterator
;
149 typedef IteratorBase
<const Item
> ConstIterator
;
151 Iterator
begin() { return Iterator(first_
); }
152 Iterator
end() { return Iterator(0); }
154 ConstIterator
begin() const { return ConstIterator(first_
); }
155 ConstIterator
end() const { return ConstIterator(0); }
157 // private, don't use directly.
163 } // namespace __sanitizer
165 #endif // SANITIZER_LIST_H