Kostya Serebryany | 5a2327c | 2012-07-06 09:03:45 +0000 | [diff] [blame] | 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 | //===----------------------------------------------------------------------===// |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 14 | |
Kostya Serebryany | 5a2327c | 2012-07-06 09:03:45 +0000 | [diff] [blame] | 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 { |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 30 | friend class Iterator; |
| 31 | |
Kostya Serebryany | 5a2327c | 2012-07-06 09:03:45 +0000 | [diff] [blame] | 32 | void clear() { |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 33 | first_ = last_ = nullptr; |
Kostya Serebryany | 5a2327c | 2012-07-06 09:03:45 +0000 | [diff] [blame] | 34 | size_ = 0; |
| 35 | } |
| 36 | |
| 37 | bool empty() const { return size_ == 0; } |
| 38 | uptr size() const { return size_; } |
| 39 | |
| 40 | void push_back(Item *x) { |
| 41 | if (empty()) { |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 42 | x->next = nullptr; |
Kostya Serebryany | 5a2327c | 2012-07-06 09:03:45 +0000 | [diff] [blame] | 43 | first_ = last_ = x; |
| 44 | size_ = 1; |
| 45 | } else { |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 46 | x->next = nullptr; |
Kostya Serebryany | 5a2327c | 2012-07-06 09:03:45 +0000 | [diff] [blame] | 47 | last_->next = x; |
| 48 | last_ = x; |
| 49 | size_++; |
| 50 | } |
| 51 | } |
| 52 | |
| 53 | void push_front(Item *x) { |
| 54 | if (empty()) { |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 55 | x->next = nullptr; |
Kostya Serebryany | 5a2327c | 2012-07-06 09:03:45 +0000 | [diff] [blame] | 56 | first_ = last_ = x; |
| 57 | size_ = 1; |
| 58 | } else { |
| 59 | x->next = first_; |
| 60 | first_ = x; |
| 61 | size_++; |
| 62 | } |
| 63 | } |
| 64 | |
| 65 | void pop_front() { |
| 66 | CHECK(!empty()); |
| 67 | first_ = first_->next; |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 68 | if (!first_) |
| 69 | last_ = nullptr; |
Kostya Serebryany | 5a2327c | 2012-07-06 09:03:45 +0000 | [diff] [blame] | 70 | size_--; |
| 71 | } |
| 72 | |
| 73 | Item *front() { return first_; } |
| 74 | Item *back() { return last_; } |
| 75 | |
| 76 | void append_front(IntrusiveList<Item> *l) { |
| 77 | CHECK_NE(this, l); |
Dmitry Vyukov | 312de6a | 2013-01-11 10:15:13 +0000 | [diff] [blame] | 78 | if (l->empty()) |
| 79 | return; |
Kostya Serebryany | 5a2327c | 2012-07-06 09:03:45 +0000 | [diff] [blame] | 80 | if (empty()) { |
| 81 | *this = *l; |
Kostya Serebryany | deafb6b | 2012-07-06 14:32:00 +0000 | [diff] [blame] | 82 | } else if (!l->empty()) { |
| 83 | l->last_->next = first_; |
Kostya Serebryany | 5a2327c | 2012-07-06 09:03:45 +0000 | [diff] [blame] | 84 | first_ = l->first_; |
| 85 | size_ += l->size(); |
| 86 | } |
| 87 | l->clear(); |
| 88 | } |
| 89 | |
| 90 | void append_back(IntrusiveList<Item> *l) { |
| 91 | CHECK_NE(this, l); |
Dmitry Vyukov | 312de6a | 2013-01-11 10:15:13 +0000 | [diff] [blame] | 92 | if (l->empty()) |
| 93 | return; |
Kostya Serebryany | 5a2327c | 2012-07-06 09:03:45 +0000 | [diff] [blame] | 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 | |
| 104 | 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 | |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 119 | template<class ListTy, class ItemTy> |
| 120 | class IteratorBase { |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 121 | public: |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 122 | explicit IteratorBase(ListTy *list) |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 123 | : list_(list), current_(list->first_) { } |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 124 | ItemTy *next() { |
| 125 | ItemTy *ret = current_; |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 126 | if (current_) current_ = current_->next; |
| 127 | return ret; |
| 128 | } |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 129 | bool hasNext() const { return current_ != nullptr; } |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 130 | private: |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 131 | ListTy *list_; |
| 132 | ItemTy *current_; |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 133 | }; |
| 134 | |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 135 | typedef IteratorBase<IntrusiveList<Item>, Item> Iterator; |
| 136 | typedef IteratorBase<const IntrusiveList<Item>, const Item> ConstIterator; |
| 137 | |
Kostya Serebryany | 5a2327c | 2012-07-06 09:03:45 +0000 | [diff] [blame] | 138 | // private, don't use directly. |
| 139 | uptr size_; |
| 140 | Item *first_; |
| 141 | Item *last_; |
| 142 | }; |
| 143 | |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 144 | } // namespace __sanitizer |
Kostya Serebryany | 5a2327c | 2012-07-06 09:03:45 +0000 | [diff] [blame] | 145 | |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 146 | #endif // SANITIZER_LIST_H |