1 /* 2 * Copyright (C) 2019 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef INCLUDE_PERFETTO_BASE_CIRCULAR_QUEUE_H_ 18 #define INCLUDE_PERFETTO_BASE_CIRCULAR_QUEUE_H_ 19 20 #include <stdint.h> 21 #include <iterator> 22 23 #include "perfetto/base/logging.h" 24 #include "perfetto/base/utils.h" 25 26 namespace perfetto { 27 namespace base { 28 29 // CircularQueue is a push-back-only / pop-front-only queue with the following 30 // characteristics: 31 // - The storage is based on a flat circular buffer. Beginning and end wrap 32 // as necessary, to keep pushes and pops O(1) as long as capacity expansion is 33 // not required. 34 // - Capacity is automatically expanded like in a std::vector. Expansion has a 35 // O(N) cost. 36 // - It allows random access, allowing in-place std::sort. 37 // - Iterators are not stable. Mutating the container invalidates all iterators. 38 // - It doesn't bother with const-correctness. 39 // 40 // Implementation details: 41 // Internally, |begin|, |end| and iterators use 64-bit monotonic indexes, which 42 // are incremented as if the queue was backed by unlimited storage. 43 // Even assuming that elements are inserted and removed every nanosecond, 64 bit 44 // is enough for 584 years. 45 // Wrapping happens only when addressing elements in the underlying circular 46 // storage. This limits the complexity and avoiding dealing with modular 47 // arithmetic all over the places. 48 template <class T> 49 class CircularQueue { 50 public: 51 class Iterator { 52 public: 53 using difference_type = ptrdiff_t; 54 using value_type = T; 55 using pointer = const T*; 56 using reference = const T&; 57 using iterator_category = std::random_access_iterator_tag; 58 59 Iterator(CircularQueue* queue, uint64_t pos, uint32_t generation) 60 : queue_(queue), 61 pos_(pos) 62 #if PERFETTO_DCHECK_IS_ON() 63 , 64 generation_(generation) 65 #endif 66 { 67 ignore_result(generation); 68 } 69 70 T* operator->() { 71 #if PERFETTO_DCHECK_IS_ON() 72 PERFETTO_DCHECK(generation_ == queue_->generation()); 73 #endif 74 return queue_->Get(pos_); 75 } 76 77 T& operator*() { return *(operator->()); } 78 79 const value_type& operator[](difference_type i) const { 80 return *(*this + i); 81 } 82 83 Iterator& operator++() { 84 Add(1); 85 return *this; 86 } 87 88 Iterator operator++(int) { 89 Iterator ret = *this; 90 Add(1); 91 return ret; 92 } 93 94 Iterator& operator--() { 95 Add(-1); 96 return *this; 97 } 98 99 Iterator operator--(int) { 100 Iterator ret = *this; 101 Add(-1); 102 return ret; 103 } 104 105 friend Iterator operator+(const Iterator& iter, difference_type offset) { 106 Iterator ret = iter; 107 ret.Add(offset); 108 return ret; 109 } 110 111 Iterator& operator+=(difference_type offset) { 112 Add(offset); 113 return *this; 114 } 115 116 friend Iterator operator-(const Iterator& iter, difference_type offset) { 117 Iterator ret = iter; 118 ret.Add(-offset); 119 return ret; 120 } 121 122 Iterator& operator-=(difference_type offset) { 123 Add(-offset); 124 return *this; 125 } 126 127 friend ptrdiff_t operator-(const Iterator& lhs, const Iterator& rhs) { 128 return static_cast<ptrdiff_t>(lhs.pos_) - 129 static_cast<ptrdiff_t>(rhs.pos_); 130 } 131 132 friend bool operator==(const Iterator& lhs, const Iterator& rhs) { 133 return lhs.pos_ == rhs.pos_; 134 } 135 136 friend bool operator!=(const Iterator& lhs, const Iterator& rhs) { 137 return lhs.pos_ != rhs.pos_; 138 } 139 140 friend bool operator<(const Iterator& lhs, const Iterator& rhs) { 141 return lhs.pos_ < rhs.pos_; 142 } 143 144 friend bool operator<=(const Iterator& lhs, const Iterator& rhs) { 145 return lhs.pos_ <= rhs.pos_; 146 } 147 148 friend bool operator>(const Iterator& lhs, const Iterator& rhs) { 149 return lhs.pos_ > rhs.pos_; 150 } 151 152 friend bool operator>=(const Iterator& lhs, const Iterator& rhs) { 153 return lhs.pos_ >= rhs.pos_; 154 } 155 156 private: 157 inline void Add(difference_type offset) { 158 pos_ = static_cast<uint64_t>(static_cast<difference_type>(pos_) + offset); 159 PERFETTO_DCHECK(pos_ <= queue_->end_); 160 } 161 162 CircularQueue* queue_; 163 uint64_t pos_; 164 165 #if PERFETTO_DCHECK_IS_ON() 166 uint32_t generation_; 167 #endif 168 }; 169 170 CircularQueue(size_t initial_capacity = 1024) { Grow(initial_capacity); } 171 172 CircularQueue(CircularQueue&& other) noexcept { 173 // Copy all fields using the (private) default copy assignment operator. 174 *this = other; 175 increment_generation(); 176 new (&other) CircularQueue(); // Reset the old queue so it's still usable. 177 } 178 179 CircularQueue& operator=(CircularQueue&& other) { 180 this->~CircularQueue(); // Destroy the current state. 181 new (this) CircularQueue(std::move(other)); // Use the move ctor above. 182 return *this; 183 } 184 185 ~CircularQueue() { 186 if (!entries_) { 187 PERFETTO_DCHECK(empty()); 188 return; 189 } 190 erase_front(size()); // Invoke destructors on all alive entries. 191 PERFETTO_DCHECK(empty()); 192 free(entries_); 193 } 194 195 template <typename... Args> 196 void emplace_back(Args&&... args) { 197 increment_generation(); 198 if (PERFETTO_UNLIKELY(size() >= capacity_)) 199 Grow(); 200 T* slot = Get(end_++); 201 new (slot) T(std::forward<Args>(args)...); 202 } 203 204 void erase_front(size_t n) { 205 increment_generation(); 206 for (; n && (begin_ < end_); --n) { 207 Get(begin_)->~T(); 208 begin_++; // This needs to be its own statement, Get() checks begin_. 209 } 210 } 211 212 void pop_front() { erase_front(1); } 213 214 T& at(size_t idx) { 215 PERFETTO_DCHECK(idx < size()); 216 return *Get(begin_ + idx); 217 } 218 219 Iterator begin() { return Iterator(this, begin_, generation()); } 220 Iterator end() { return Iterator(this, end_, generation()); } 221 T& front() { return *begin(); } 222 T& back() { return *(end() - 1); } 223 224 bool empty() const { return size() == 0; } 225 226 size_t size() const { 227 PERFETTO_DCHECK(end_ - begin_ <= capacity_); 228 return static_cast<size_t>(end_ - begin_); 229 } 230 231 size_t capacity() const { return capacity_; } 232 233 #if PERFETTO_DCHECK_IS_ON() 234 uint32_t generation() const { return generation_; } 235 void increment_generation() { ++generation_; } 236 #else 237 uint32_t generation() const { return 0; } 238 void increment_generation() {} 239 #endif 240 241 private: 242 CircularQueue(const CircularQueue&) = delete; 243 CircularQueue& operator=(const CircularQueue&) = default; 244 245 void Grow(size_t new_capacity = 0) { 246 // Capacity must be always a power of two. This allows Get() to use a simple 247 // bitwise-AND for handling the wrapping instead of a full division. 248 new_capacity = new_capacity ? new_capacity : capacity_ * 2; 249 PERFETTO_CHECK((new_capacity & (new_capacity - 1)) == 0); // Must be pow2. 250 251 // On 32-bit systems this might hit the 4GB wall and overflow. We can't do 252 // anything other than crash in this case. 253 PERFETTO_CHECK(new_capacity > capacity_); 254 size_t malloc_size = new_capacity * sizeof(T); 255 PERFETTO_CHECK(malloc_size > new_capacity); 256 auto* new_vec = static_cast<T*>(malloc(malloc_size)); 257 258 // Move all elements in the expanded array. 259 size_t new_size = 0; 260 for (uint64_t i = begin_; i < end_; i++) 261 new (&new_vec[new_size++]) T(std::move(*Get(i))); // Placement move ctor. 262 263 // Even if all the elements are std::move()-d and likely empty, we are still 264 // required to call the dtor for them. 265 for (uint64_t i = begin_; i < end_; i++) 266 Get(i)->~T(); 267 free(entries_); // It's fine to free(nullptr) (for the ctor call case). 268 269 begin_ = 0; 270 end_ = new_size; 271 capacity_ = new_capacity; 272 entries_ = new_vec; 273 } 274 275 inline T* Get(uint64_t pos) { 276 PERFETTO_DCHECK(pos >= begin_ && pos < end_); 277 PERFETTO_DCHECK((capacity_ & (capacity_ - 1)) == 0); // Must be a pow2. 278 auto index = static_cast<size_t>(pos & (capacity_ - 1)); 279 return &entries_[index]; 280 } 281 282 // Underlying storage. It's raw malloc-ed rather than being a unique_ptr<T[]> 283 // to allow having uninitialized entries inside it. 284 T* entries_ = nullptr; 285 size_t capacity_ = 0; // Number of allocated slots (NOT bytes) in |entries_|. 286 287 // The |begin_| and |end_| indexes are monotonic and never wrap. Modular arith 288 // is used only when dereferencing entries in the vector. 289 uint64_t begin_ = 0; 290 uint64_t end_ = 0; 291 292 // Generation is used in debug builds only for checking iterator validity. 293 #if PERFETTO_DCHECK_IS_ON() 294 uint32_t generation_ = 0; 295 #endif 296 }; 297 298 } // namespace base 299 } // namespace perfetto 300 301 #endif // INCLUDE_PERFETTO_BASE_CIRCULAR_QUEUE_H_ 302
