1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef BASE_OBSERVER_LIST_H_ 6 #define BASE_OBSERVER_LIST_H_ 7 8 #include <stddef.h> 9 10 #include <algorithm> 11 #include <iterator> 12 #include <limits> 13 #include <utility> 14 #include <vector> 15 16 #include "base/gtest_prod_util.h" 17 #include "base/logging.h" 18 #include "base/macros.h" 19 #include "base/memory/weak_ptr.h" 20 #include "base/stl_util.h" 21 22 /////////////////////////////////////////////////////////////////////////////// 23 // 24 // OVERVIEW: 25 // 26 // A list of observers. Unlike a standard vector or list, this container can 27 // be modified during iteration without invalidating the iterator. So, it 28 // safely handles the case of an observer removing itself or other observers 29 // from the list while observers are being notified. 30 // 31 // 32 // WARNING: 33 // 34 // ObserverList is not thread-compatible. Iterating on the same ObserverList 35 // simultaneously in different threads is not safe, even when the ObserverList 36 // itself is not modified. 37 // 38 // For a thread-safe observer list, see ObserverListThreadSafe. 39 // 40 // 41 // TYPICAL USAGE: 42 // 43 // class MyWidget { 44 // public: 45 // ... 46 // 47 // class Observer { 48 // public: 49 // virtual void OnFoo(MyWidget* w) = 0; 50 // virtual void OnBar(MyWidget* w, int x, int y) = 0; 51 // }; 52 // 53 // void AddObserver(Observer* obs) { 54 // observers_.AddObserver(obs); 55 // } 56 // 57 // void RemoveObserver(const Observer* obs) { 58 // observers_.RemoveObserver(obs); 59 // } 60 // 61 // void NotifyFoo() { 62 // for (Observer& obs : observers_) 63 // obs.OnFoo(this); 64 // } 65 // 66 // void NotifyBar(int x, int y) { 67 // for (Observer& obs : observers_) 68 // obs.OnBar(this, x, y); 69 // } 70 // 71 // private: 72 // base::ObserverList<Observer> observers_; 73 // }; 74 // 75 // 76 /////////////////////////////////////////////////////////////////////////////// 77 78 namespace base { 79 80 // Enumeration of which observers are notified by ObserverList. 81 enum class ObserverListPolicy { 82 // Specifies that any observers added during notification are notified. 83 // This is the default policy if no policy is provided to the constructor. 84 ALL, 85 86 // Specifies that observers added while sending out notification are not 87 // notified. 88 EXISTING_ONLY, 89 }; 90 91 // When check_empty is true, assert that the list is empty on destruction. 92 // When allow_reentrancy is false, iterating throught the list while already in 93 // the iteration loop will result in DCHECK failure. 94 // TODO(oshima): Change the default to non reentrant. https://crbug.com/812109 95 template <class ObserverType, 96 bool check_empty = false, 97 bool allow_reentrancy = true> 98 class ObserverList 99 : public SupportsWeakPtr< 100 ObserverList<ObserverType, check_empty, allow_reentrancy>> { 101 public: 102 // An iterator class that can be used to access the list of observers. 103 class Iter { 104 public: 105 using iterator_category = std::forward_iterator_tag; 106 using value_type = ObserverType; 107 using difference_type = ptrdiff_t; 108 using pointer = ObserverType*; 109 using reference = ObserverType&; 110 Iter()111 Iter() : index_(0), max_index_(0) {} 112 Iter(const ObserverList * list)113 explicit Iter(const ObserverList* list) 114 : list_(const_cast<ObserverList*>(list)->AsWeakPtr()), 115 index_(0), 116 max_index_(list->policy_ == ObserverListPolicy::ALL 117 ? std::numeric_limits<size_t>::max() 118 : list->observers_.size()) { 119 DCHECK(list_); 120 DCHECK(allow_reentrancy || !list_->live_iterator_count_); 121 EnsureValidIndex(); 122 ++list_->live_iterator_count_; 123 } 124 ~Iter()125 ~Iter() { 126 if (!list_) 127 return; 128 129 DCHECK_GT(list_->live_iterator_count_, 0); 130 if (--list_->live_iterator_count_ == 0) 131 list_->Compact(); 132 } 133 Iter(const Iter & other)134 Iter(const Iter& other) 135 : list_(other.list_), 136 index_(other.index_), 137 max_index_(other.max_index_) { 138 if (list_) 139 ++list_->live_iterator_count_; 140 } 141 142 Iter& operator=(Iter other) { 143 using std::swap; 144 swap(list_, other.list_); 145 swap(index_, other.index_); 146 swap(max_index_, other.max_index_); 147 return *this; 148 } 149 150 bool operator==(const Iter& other) const { 151 return (is_end() && other.is_end()) || 152 (list_.get() == other.list_.get() && index_ == other.index_); 153 } 154 155 bool operator!=(const Iter& other) const { return !(*this == other); } 156 157 Iter& operator++() { 158 if (list_) { 159 ++index_; 160 EnsureValidIndex(); 161 } 162 return *this; 163 } 164 165 Iter operator++(int) { 166 Iter it(*this); 167 ++(*this); 168 return it; 169 } 170 171 ObserverType* operator->() const { 172 ObserverType* const current = GetCurrent(); 173 DCHECK(current); 174 return current; 175 } 176 177 ObserverType& operator*() const { 178 ObserverType* const current = GetCurrent(); 179 DCHECK(current); 180 return *current; 181 } 182 183 private: 184 FRIEND_TEST_ALL_PREFIXES(ObserverListTest, BasicStdIterator); 185 FRIEND_TEST_ALL_PREFIXES(ObserverListTest, StdIteratorRemoveFront); 186 GetCurrent()187 ObserverType* GetCurrent() const { 188 DCHECK(list_); 189 DCHECK_LT(index_, clamped_max_index()); 190 return list_->observers_[index_]; 191 } 192 EnsureValidIndex()193 void EnsureValidIndex() { 194 DCHECK(list_); 195 const size_t max_index = clamped_max_index(); 196 while (index_ < max_index && !list_->observers_[index_]) 197 ++index_; 198 } 199 clamped_max_index()200 size_t clamped_max_index() const { 201 return std::min(max_index_, list_->observers_.size()); 202 } 203 is_end()204 bool is_end() const { return !list_ || index_ == clamped_max_index(); } 205 206 WeakPtr<ObserverList> list_; 207 208 // When initially constructed and each time the iterator is incremented, 209 // |index_| is guaranteed to point to a non-null index if the iterator 210 // has not reached the end of the ObserverList. 211 size_t index_; 212 size_t max_index_; 213 }; 214 215 using iterator = Iter; 216 using const_iterator = Iter; 217 begin()218 const_iterator begin() const { 219 // An optimization: do not involve weak pointers for empty list. 220 return observers_.empty() ? const_iterator() : const_iterator(this); 221 } 222 end()223 const_iterator end() const { return const_iterator(); } 224 225 ObserverList() = default; ObserverList(ObserverListPolicy policy)226 explicit ObserverList(ObserverListPolicy policy) : policy_(policy) {} 227 ~ObserverList()228 ~ObserverList() { 229 if (check_empty) { 230 Compact(); 231 DCHECK(observers_.empty()); 232 } 233 } 234 235 // Add an observer to this list. An observer should not be added to the same 236 // list more than once. 237 // 238 // Precondition: obs != nullptr 239 // Precondition: !HasObserver(obs) AddObserver(ObserverType * obs)240 void AddObserver(ObserverType* obs) { 241 DCHECK(obs); 242 if (HasObserver(obs)) { 243 NOTREACHED() << "Observers can only be added once!"; 244 return; 245 } 246 observers_.push_back(obs); 247 } 248 249 // Removes the given observer from this list. Does nothing if this observer is 250 // not in this list. RemoveObserver(const ObserverType * obs)251 void RemoveObserver(const ObserverType* obs) { 252 DCHECK(obs); 253 const auto it = std::find(observers_.begin(), observers_.end(), obs); 254 if (it == observers_.end()) 255 return; 256 257 DCHECK_GE(live_iterator_count_, 0); 258 if (live_iterator_count_) { 259 *it = nullptr; 260 } else { 261 observers_.erase(it); 262 } 263 } 264 265 // Determine whether a particular observer is in the list. HasObserver(const ObserverType * obs)266 bool HasObserver(const ObserverType* obs) const { 267 return ContainsValue(observers_, obs); 268 } 269 270 // Removes all the observers from this list. Clear()271 void Clear() { 272 DCHECK_GE(live_iterator_count_, 0); 273 if (live_iterator_count_) { 274 std::fill(observers_.begin(), observers_.end(), nullptr); 275 } else { 276 observers_.clear(); 277 } 278 } 279 might_have_observers()280 bool might_have_observers() const { return !observers_.empty(); } 281 282 private: 283 // Compacts list of observers by removing null pointers. Compact()284 void Compact() { 285 observers_.erase(std::remove(observers_.begin(), observers_.end(), nullptr), 286 observers_.end()); 287 } 288 289 std::vector<ObserverType*> observers_; 290 291 // Number of active iterators referencing this ObserverList. 292 // 293 // This counter is not synchronized although it is modified by const 294 // iterators. 295 int live_iterator_count_ = 0; 296 297 const ObserverListPolicy policy_ = ObserverListPolicy::ALL; 298 299 DISALLOW_COPY_AND_ASSIGN(ObserverList); 300 }; 301 302 template <class ObserverType, bool check_empty = false> 303 using ReentrantObserverList = ObserverList<ObserverType, check_empty, true>; 304 305 } // namespace base 306 307 #endif // BASE_OBSERVER_LIST_H_ 308