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 { 29 friend class Iterator; 30 clearIntrusiveList31 void clear() { 32 first_ = last_ = 0; 33 size_ = 0; 34 } 35 emptyIntrusiveList36 bool empty() const { return size_ == 0; } sizeIntrusiveList37 uptr size() const { return size_; } 38 push_backIntrusiveList39 void push_back(Item *x) { 40 if (empty()) { 41 x->next = 0; 42 first_ = last_ = x; 43 size_ = 1; 44 } else { 45 x->next = 0; 46 last_->next = x; 47 last_ = x; 48 size_++; 49 } 50 } 51 push_frontIntrusiveList52 void push_front(Item *x) { 53 if (empty()) { 54 x->next = 0; 55 first_ = last_ = x; 56 size_ = 1; 57 } else { 58 x->next = first_; 59 first_ = x; 60 size_++; 61 } 62 } 63 pop_frontIntrusiveList64 void pop_front() { 65 CHECK(!empty()); 66 first_ = first_->next; 67 if (first_ == 0) 68 last_ = 0; 69 size_--; 70 } 71 frontIntrusiveList72 Item *front() { return first_; } backIntrusiveList73 Item *back() { return last_; } 74 append_frontIntrusiveList75 void append_front(IntrusiveList<Item> *l) { 76 CHECK_NE(this, l); 77 if (l->empty()) 78 return; 79 if (empty()) { 80 *this = *l; 81 } else if (!l->empty()) { 82 l->last_->next = first_; 83 first_ = l->first_; 84 size_ += l->size(); 85 } 86 l->clear(); 87 } 88 append_backIntrusiveList89 void append_back(IntrusiveList<Item> *l) { 90 CHECK_NE(this, l); 91 if (l->empty()) 92 return; 93 if (empty()) { 94 *this = *l; 95 } else { 96 last_->next = l->first_; 97 last_ = l->last_; 98 size_ += l->size(); 99 } 100 l->clear(); 101 } 102 CheckConsistencyIntrusiveList103 void CheckConsistency() { 104 if (size_ == 0) { 105 CHECK_EQ(first_, 0); 106 CHECK_EQ(last_, 0); 107 } else { 108 uptr count = 0; 109 for (Item *i = first_; ; i = i->next) { 110 count++; 111 if (i == last_) break; 112 } 113 CHECK_EQ(size(), count); 114 CHECK_EQ(last_->next, 0); 115 } 116 } 117 118 class Iterator { 119 public: IteratorIntrusiveList120 explicit Iterator(IntrusiveList<Item> *list) 121 : list_(list), current_(list->first_) { } nextIntrusiveList122 Item *next() { 123 Item *ret = current_; 124 if (current_) current_ = current_->next; 125 return ret; 126 } hasNextIntrusiveList127 bool hasNext() const { return current_ != 0; } 128 private: 129 IntrusiveList<Item> *list_; 130 Item *current_; 131 }; 132 133 // private, don't use directly. 134 uptr size_; 135 Item *first_; 136 Item *last_; 137 }; 138 139 } // namespace __sanitizer 140 141 #endif // SANITIZER_LIST_H 142