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 { clearIntrusiveList29 void clear() { 30 first_ = last_ = 0; 31 size_ = 0; 32 } 33 emptyIntrusiveList34 bool empty() const { return size_ == 0; } sizeIntrusiveList35 uptr size() const { return size_; } 36 push_backIntrusiveList37 void push_back(Item *x) { 38 if (empty()) { 39 x->next = 0; 40 first_ = last_ = x; 41 size_ = 1; 42 } else { 43 x->next = 0; 44 last_->next = x; 45 last_ = x; 46 size_++; 47 } 48 } 49 push_frontIntrusiveList50 void push_front(Item *x) { 51 if (empty()) { 52 x->next = 0; 53 first_ = last_ = x; 54 size_ = 1; 55 } else { 56 x->next = first_; 57 first_ = x; 58 size_++; 59 } 60 } 61 pop_frontIntrusiveList62 void pop_front() { 63 CHECK(!empty()); 64 first_ = first_->next; 65 if (first_ == 0) 66 last_ = 0; 67 size_--; 68 } 69 frontIntrusiveList70 Item *front() { return first_; } backIntrusiveList71 Item *back() { return last_; } 72 append_frontIntrusiveList73 void append_front(IntrusiveList<Item> *l) { 74 CHECK_NE(this, l); 75 if (l->empty()) 76 return; 77 if (empty()) { 78 *this = *l; 79 } else if (!l->empty()) { 80 l->last_->next = first_; 81 first_ = l->first_; 82 size_ += l->size(); 83 } 84 l->clear(); 85 } 86 append_backIntrusiveList87 void append_back(IntrusiveList<Item> *l) { 88 CHECK_NE(this, l); 89 if (l->empty()) 90 return; 91 if (empty()) { 92 *this = *l; 93 } else { 94 last_->next = l->first_; 95 last_ = l->last_; 96 size_ += l->size(); 97 } 98 l->clear(); 99 } 100 CheckConsistencyIntrusiveList101 void CheckConsistency() { 102 if (size_ == 0) { 103 CHECK_EQ(first_, 0); 104 CHECK_EQ(last_, 0); 105 } else { 106 uptr count = 0; 107 for (Item *i = first_; ; i = i->next) { 108 count++; 109 if (i == last_) break; 110 } 111 CHECK_EQ(size(), count); 112 CHECK_EQ(last_->next, 0); 113 } 114 } 115 116 // private, don't use directly. 117 uptr size_; 118 Item *first_; 119 Item *last_; 120 }; 121 122 } // namespace __sanitizer 123 124 #endif // SANITIZER_LIST_H 125