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