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 Item
*front() { return first_
; }
72 const Item
*front() const { return first_
; }
73 Item
*back() { return last_
; }
74 const Item
*back() const { return last_
; }
76 void append_front(IntrusiveList
<Item
> *l
) {
82 } else if (!l
->empty()) {
83 l
->last_
->next
= first_
;
90 void append_back(IntrusiveList
<Item
> *l
) {
97 last_
->next
= l
->first_
;
104 void CheckConsistency() {
110 for (Item
*i
= first_
; ; i
= i
->next
) {
112 if (i
== last_
) break;
114 CHECK_EQ(size(), count
);
115 CHECK_EQ(last_
->next
, 0);
119 template<class ItemTy
>
122 explicit IteratorBase(ItemTy
*current
) : current_(current
) {}
123 IteratorBase
&operator++() {
124 current_
= current_
->next
;
127 bool operator!=(IteratorBase other
) const {
128 return current_
!= other
.current_
;
130 ItemTy
&operator*() {
137 typedef IteratorBase
<Item
> Iterator
;
138 typedef IteratorBase
<const Item
> ConstIterator
;
140 Iterator
begin() { return Iterator(first_
); }
141 Iterator
end() { return Iterator(0); }
143 ConstIterator
begin() const { return ConstIterator(first_
); }
144 ConstIterator
end() const { return ConstIterator(0); }
146 // private, don't use directly.
152 } // namespace __sanitizer
154 #endif // SANITIZER_LIST_H