1 //===-- sanitizer_list.h ----------------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file contains implementation of a list class to be used by 10 // ThreadSanitizer, etc run-times. 11 // 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_ = nullptr; 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 = nullptr; 42 first_ = last_ = x; 43 size_ = 1; 44 } else { 45 x->next = nullptr; 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 = nullptr; 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_) 68 last_ = nullptr; 69 size_--; 70 } 71 extractIntrusiveList72 void extract(Item *prev, Item *x) { 73 CHECK(!empty()); 74 CHECK_NE(prev, nullptr); 75 CHECK_NE(x, nullptr); 76 CHECK_EQ(prev->next, x); 77 prev->next = x->next; 78 if (last_ == x) 79 last_ = prev; 80 size_--; 81 } 82 frontIntrusiveList83 Item *front() { return first_; } frontIntrusiveList84 const Item *front() const { return first_; } backIntrusiveList85 Item *back() { return last_; } backIntrusiveList86 const Item *back() const { return last_; } 87 append_frontIntrusiveList88 void append_front(IntrusiveList<Item> *l) { 89 CHECK_NE(this, l); 90 if (l->empty()) 91 return; 92 if (empty()) { 93 *this = *l; 94 } else if (!l->empty()) { 95 l->last_->next = first_; 96 first_ = l->first_; 97 size_ += l->size(); 98 } 99 l->clear(); 100 } 101 append_backIntrusiveList102 void append_back(IntrusiveList<Item> *l) { 103 CHECK_NE(this, l); 104 if (l->empty()) 105 return; 106 if (empty()) { 107 *this = *l; 108 } else { 109 last_->next = l->first_; 110 last_ = l->last_; 111 size_ += l->size(); 112 } 113 l->clear(); 114 } 115 CheckConsistencyIntrusiveList116 void CheckConsistency() { 117 if (size_ == 0) { 118 CHECK_EQ(first_, 0); 119 CHECK_EQ(last_, 0); 120 } else { 121 uptr count = 0; 122 for (Item *i = first_; ; i = i->next) { 123 count++; 124 if (i == last_) break; 125 } 126 CHECK_EQ(size(), count); 127 CHECK_EQ(last_->next, 0); 128 } 129 } 130 131 template<class ItemTy> 132 class IteratorBase { 133 public: IteratorBaseIntrusiveList134 explicit IteratorBase(ItemTy *current) : current_(current) {} 135 IteratorBase &operator++() { 136 current_ = current_->next; 137 return *this; 138 } 139 bool operator!=(IteratorBase other) const { 140 return current_ != other.current_; 141 } 142 ItemTy &operator*() { 143 return *current_; 144 } 145 private: 146 ItemTy *current_; 147 }; 148 149 typedef IteratorBase<Item> Iterator; 150 typedef IteratorBase<const Item> ConstIterator; 151 beginIntrusiveList152 Iterator begin() { return Iterator(first_); } endIntrusiveList153 Iterator end() { return Iterator(0); } 154 beginIntrusiveList155 ConstIterator begin() const { return ConstIterator(first_); } endIntrusiveList156 ConstIterator end() const { return ConstIterator(0); } 157 158 // private, don't use directly. 159 uptr size_; 160 Item *first_; 161 Item *last_; 162 }; 163 164 } // namespace __sanitizer 165 166 #endif // SANITIZER_LIST_H 167