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 15 #ifndef SANITIZER_LIST_H 16 #define SANITIZER_LIST_H 17 18 #include "sanitizer_internal_defs.h" 19 20 namespace __sanitizer { 21 22 // Intrusive singly-linked list with size(), push_back(), push_front() 23 // pop_front(), append_front() and append_back(). 24 // This class should be a POD (so that it can be put into TLS) 25 // and an object with all zero fields should represent a valid empty list. 26 // This class does not have a CTOR, so clear() should be called on all 27 // non-zero-initialized objects before using. 28 template<class Item> 29 struct IntrusiveList { 30 friend class Iterator; 31 clearIntrusiveList32 void clear() { 33 first_ = last_ = nullptr; 34 size_ = 0; 35 } 36 emptyIntrusiveList37 bool empty() const { return size_ == 0; } sizeIntrusiveList38 uptr size() const { return size_; } 39 push_backIntrusiveList40 void push_back(Item *x) { 41 if (empty()) { 42 x->next = nullptr; 43 first_ = last_ = x; 44 size_ = 1; 45 } else { 46 x->next = nullptr; 47 last_->next = x; 48 last_ = x; 49 size_++; 50 } 51 } 52 push_frontIntrusiveList53 void push_front(Item *x) { 54 if (empty()) { 55 x->next = nullptr; 56 first_ = last_ = x; 57 size_ = 1; 58 } else { 59 x->next = first_; 60 first_ = x; 61 size_++; 62 } 63 } 64 pop_frontIntrusiveList65 void pop_front() { 66 CHECK(!empty()); 67 first_ = first_->next; 68 if (!first_) 69 last_ = nullptr; 70 size_--; 71 } 72 frontIntrusiveList73 Item *front() { return first_; } frontIntrusiveList74 const Item *front() const { return first_; } backIntrusiveList75 Item *back() { return last_; } backIntrusiveList76 const Item *back() const { return last_; } 77 append_frontIntrusiveList78 void append_front(IntrusiveList<Item> *l) { 79 CHECK_NE(this, l); 80 if (l->empty()) 81 return; 82 if (empty()) { 83 *this = *l; 84 } else if (!l->empty()) { 85 l->last_->next = first_; 86 first_ = l->first_; 87 size_ += l->size(); 88 } 89 l->clear(); 90 } 91 append_backIntrusiveList92 void append_back(IntrusiveList<Item> *l) { 93 CHECK_NE(this, l); 94 if (l->empty()) 95 return; 96 if (empty()) { 97 *this = *l; 98 } else { 99 last_->next = l->first_; 100 last_ = l->last_; 101 size_ += l->size(); 102 } 103 l->clear(); 104 } 105 CheckConsistencyIntrusiveList106 void CheckConsistency() { 107 if (size_ == 0) { 108 CHECK_EQ(first_, 0); 109 CHECK_EQ(last_, 0); 110 } else { 111 uptr count = 0; 112 for (Item *i = first_; ; i = i->next) { 113 count++; 114 if (i == last_) break; 115 } 116 CHECK_EQ(size(), count); 117 CHECK_EQ(last_->next, 0); 118 } 119 } 120 121 template<class ItemTy> 122 class IteratorBase { 123 public: IteratorBaseIntrusiveList124 explicit IteratorBase(ItemTy *current) : current_(current) {} 125 IteratorBase &operator++() { 126 current_ = current_->next; 127 return *this; 128 } 129 bool operator!=(IteratorBase other) const { 130 return current_ != other.current_; 131 } 132 ItemTy &operator*() { 133 return *current_; 134 } 135 private: 136 ItemTy *current_; 137 }; 138 139 typedef IteratorBase<Item> Iterator; 140 typedef IteratorBase<const Item> ConstIterator; 141 beginIntrusiveList142 Iterator begin() { return Iterator(first_); } endIntrusiveList143 Iterator end() { return Iterator(0); } 144 beginIntrusiveList145 ConstIterator begin() const { return ConstIterator(first_); } endIntrusiveList146 ConstIterator end() const { return ConstIterator(0); } 147 148 // private, don't use directly. 149 uptr size_; 150 Item *first_; 151 Item *last_; 152 }; 153 154 } // namespace __sanitizer 155 156 #endif // SANITIZER_LIST_H 157