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_; } backIntrusiveList74 Item *back() { return last_; } 75 append_frontIntrusiveList76 void append_front(IntrusiveList<Item> *l) { 77 CHECK_NE(this, l); 78 if (l->empty()) 79 return; 80 if (empty()) { 81 *this = *l; 82 } else if (!l->empty()) { 83 l->last_->next = first_; 84 first_ = l->first_; 85 size_ += l->size(); 86 } 87 l->clear(); 88 } 89 append_backIntrusiveList90 void append_back(IntrusiveList<Item> *l) { 91 CHECK_NE(this, l); 92 if (l->empty()) 93 return; 94 if (empty()) { 95 *this = *l; 96 } else { 97 last_->next = l->first_; 98 last_ = l->last_; 99 size_ += l->size(); 100 } 101 l->clear(); 102 } 103 CheckConsistencyIntrusiveList104 void CheckConsistency() { 105 if (size_ == 0) { 106 CHECK_EQ(first_, 0); 107 CHECK_EQ(last_, 0); 108 } else { 109 uptr count = 0; 110 for (Item *i = first_; ; i = i->next) { 111 count++; 112 if (i == last_) break; 113 } 114 CHECK_EQ(size(), count); 115 CHECK_EQ(last_->next, 0); 116 } 117 } 118 119 template<class ListTy, class ItemTy> 120 class IteratorBase { 121 public: IteratorBaseIntrusiveList122 explicit IteratorBase(ListTy *list) 123 : list_(list), current_(list->first_) { } nextIntrusiveList124 ItemTy *next() { 125 ItemTy *ret = current_; 126 if (current_) current_ = current_->next; 127 return ret; 128 } hasNextIntrusiveList129 bool hasNext() const { return current_ != nullptr; } 130 private: 131 ListTy *list_; 132 ItemTy *current_; 133 }; 134 135 typedef IteratorBase<IntrusiveList<Item>, Item> Iterator; 136 typedef IteratorBase<const IntrusiveList<Item>, const Item> ConstIterator; 137 138 // private, don't use directly. 139 uptr size_; 140 Item *first_; 141 Item *last_; 142 }; 143 144 } // namespace __sanitizer 145 146 #endif // SANITIZER_LIST_H 147