OLD | NEW |
(Empty) | |
| 1 // Copyright 2017 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_CONTAINERS_CIRCULAR_DEQUE_H_ |
| 6 #define BASE_CONTAINERS_CIRCULAR_DEQUE_H_ |
| 7 |
| 8 #include <cstddef> |
| 9 #include <iterator> |
| 10 #include <type_traits> |
| 11 #include <utility> |
| 12 |
| 13 #include "base/containers/vector_buffer.h" |
| 14 #include "base/logging.h" |
| 15 #include "base/macros.h" |
| 16 #include "base/template_util.h" |
| 17 |
| 18 // base::circular_deque is similar to std::deque. Unlike std::deque, the |
| 19 // storage is provided in a flat circular buffer conceptually similar to a |
| 20 // vector. The beginning and end will wrap around as necessary so that |
| 21 // pushes and pops will be constant time as long as a capacity expansion is |
| 22 // not required. |
| 23 // |
| 24 // The API should be identical to std::deque with the following differences: |
| 25 // |
| 26 // - ITERATORS IN ARE NOT STABLE. Mutating the container will invalidate all |
| 27 // iterators. |
| 28 // |
| 29 // - Insertions may resize the vector and so are not linear time (std::deque |
| 30 // guarantees amortized constant time for insertions at the ends). |
| 31 // |
| 32 // - Container-wide comparisons are not implemented. If you want to compare |
| 33 // two containers, use an algorithm so the expensive iteration is explicit. |
| 34 // |
| 35 // - Insert and erase in the middle is not supported. This complicates the |
| 36 // implementation and is not necessary for our current goals. We can |
| 37 // consider adding this in the future if necessary. But consider that |
| 38 // the implementation will be quite slow and that callers needing this |
| 39 // beahvior may be better served with a std::list. |
| 40 // |
| 41 // If you want a similar container with only a queue API, use base::queue in |
| 42 // base/containers/queue.h. |
| 43 // |
| 44 // Constructors: |
| 45 // circular_deque(); |
| 46 // circular_deque(size_t count); |
| 47 // circular_deque(size_t count, const T& value); |
| 48 // circular_deque(InputIterator first, InputIterator last); |
| 49 // circular_deque(const circular_deque&); |
| 50 // circular_deque(circular_deque&&); |
| 51 // circular_deque(std::initializer_list<value_type>); |
| 52 // |
| 53 // Assignment functions: |
| 54 // circular_deque& operator=(const circular_deque&); |
| 55 // circular_deque& operator=(circular_deque&&); |
| 56 // circular_deque& operator=(std::initializer_list<T>); |
| 57 // void assign(size_t count, const T& value); |
| 58 // void assign(InputIterator first, InputIterator last); |
| 59 // void assign(std::initializer_list<T> value); |
| 60 // |
| 61 // Random accessors: |
| 62 // T& at(size_t); |
| 63 // const T& at(size_t) const; |
| 64 // T& operator[](size_t); |
| 65 // const T& operator[](size_t) const; |
| 66 // |
| 67 // End accessors: |
| 68 // T& front(); |
| 69 // const T& front() const; |
| 70 // T& back(); |
| 71 // const T& back() const; |
| 72 // |
| 73 // Iterator functions: |
| 74 // iterator begin(); |
| 75 // const_iterator begin() const; |
| 76 // const_iterator cbegin() const; |
| 77 // iterator end(); |
| 78 // const_iterator end() const; |
| 79 // const_iterator cend() const; |
| 80 // reverse_iterator rbegin(); |
| 81 // const_reverse_iterator rbegin() const; |
| 82 // const_reverse_iterator crbegin() const; |
| 83 // reverse_iterator rend(); |
| 84 // const_reverse_iterator rend() const; |
| 85 // const_reverse_iterator crend() const; |
| 86 // |
| 87 // Memory management: |
| 88 // void reserve(size_t); |
| 89 // size_t capacity() const; |
| 90 // void shrink_to_fit(); |
| 91 // |
| 92 // Size management: |
| 93 // void clear(); |
| 94 // bool empty() const; |
| 95 // size_t size() const; |
| 96 // void resize(size_t); |
| 97 // void resize(size_t count, const T& value); |
| 98 // |
| 99 // End insert and erase: |
| 100 // void push_front(const T&); |
| 101 // void push_front(T&&); |
| 102 // void push_back(const T&); |
| 103 // void push_back(T&&); |
| 104 // void emplace_front(Args&&...); |
| 105 // void emplace_back(Args&&...); |
| 106 // void pop_front; |
| 107 // void pop_back(); |
| 108 // |
| 109 // General: |
| 110 // void swap(circular_deque&); |
| 111 |
| 112 namespace base { |
| 113 |
| 114 template <class T> |
| 115 class circular_deque; |
| 116 |
| 117 namespace internal { |
| 118 |
| 119 template <typename T> |
| 120 class circular_deque_const_iterator { |
| 121 public: |
| 122 using difference_type = std::ptrdiff_t; |
| 123 using value_type = T; |
| 124 using pointer = const T*; |
| 125 using reference = const T&; |
| 126 using iterator_category = std::random_access_iterator_tag; |
| 127 |
| 128 circular_deque_const_iterator(const circular_deque<T>* parent, size_t index) |
| 129 : parent_deque_(parent), index_(index) { |
| 130 #if DCHECK_IS_ON() |
| 131 created_generation_ = parent->generation_; |
| 132 #endif // DCHECK_IS_ON() |
| 133 } |
| 134 |
| 135 // Dereferencing. |
| 136 const T& operator*() const { |
| 137 CheckUnstableUsage(); |
| 138 parent_deque_->CheckValidIndex(index_); |
| 139 return parent_deque_->buffer_[index_]; |
| 140 } |
| 141 const T* operator->() const { |
| 142 CheckUnstableUsage(); |
| 143 parent_deque_->CheckValidIndex(index_); |
| 144 return &parent_deque_->buffer_[index_]; |
| 145 } |
| 146 |
| 147 // Increment and decrement. |
| 148 circular_deque_const_iterator& operator++() { |
| 149 Increment(); |
| 150 return *this; |
| 151 } |
| 152 circular_deque_const_iterator operator++(int) { |
| 153 circular_deque_const_iterator ret = *this; |
| 154 Increment(); |
| 155 return ret; |
| 156 } |
| 157 circular_deque_const_iterator& operator--() { |
| 158 Decrement(); |
| 159 return *this; |
| 160 } |
| 161 circular_deque_const_iterator operator--(int) { |
| 162 circular_deque_const_iterator ret = *this; |
| 163 return ret; |
| 164 } |
| 165 |
| 166 // Random access mutation. |
| 167 friend circular_deque_const_iterator operator+( |
| 168 const circular_deque_const_iterator& iter, |
| 169 difference_type offset) { |
| 170 circular_deque_const_iterator ret = iter; |
| 171 ret.Add(offset); |
| 172 return ret; |
| 173 } |
| 174 circular_deque_const_iterator& operator+=(difference_type offset) { |
| 175 Add(offset); |
| 176 return *this; |
| 177 } |
| 178 friend circular_deque_const_iterator operator-( |
| 179 const circular_deque_const_iterator& iter, |
| 180 difference_type offset) { |
| 181 circular_deque_const_iterator ret = iter; |
| 182 ret.Add(-offset); |
| 183 return ret; |
| 184 } |
| 185 circular_deque_const_iterator& operator-=(difference_type offset) { |
| 186 Add(-offset); |
| 187 return *this; |
| 188 } |
| 189 |
| 190 friend std::ptrdiff_t operator-(const circular_deque_const_iterator& lhs, |
| 191 const circular_deque_const_iterator& rhs) { |
| 192 lhs.CheckComparable(rhs); |
| 193 return lhs.OffsetFromBegin() - rhs.OffsetFromBegin(); |
| 194 } |
| 195 |
| 196 // Comparisons. |
| 197 friend bool operator==(const circular_deque_const_iterator& lhs, |
| 198 const circular_deque_const_iterator& rhs) { |
| 199 lhs.CheckComparable(rhs); |
| 200 return lhs.index_ == rhs.index_; |
| 201 } |
| 202 friend bool operator!=(const circular_deque_const_iterator& lhs, |
| 203 const circular_deque_const_iterator& rhs) { |
| 204 return !(lhs == rhs); |
| 205 } |
| 206 friend bool operator<(const circular_deque_const_iterator& lhs, |
| 207 const circular_deque_const_iterator& rhs) { |
| 208 lhs.CheckComparable(rhs); |
| 209 return lhs.OffsetFromBegin() < rhs.OffsetFromBegin(); |
| 210 } |
| 211 friend bool operator<=(const circular_deque_const_iterator& lhs, |
| 212 const circular_deque_const_iterator& rhs) { |
| 213 return !(lhs > rhs); |
| 214 } |
| 215 friend bool operator>(const circular_deque_const_iterator& lhs, |
| 216 const circular_deque_const_iterator& rhs) { |
| 217 lhs.CheckComparable(rhs); |
| 218 return lhs.OffsetFromBegin() > rhs.OffsetFromBegin(); |
| 219 } |
| 220 friend bool operator>=(const circular_deque_const_iterator& lhs, |
| 221 const circular_deque_const_iterator& rhs) { |
| 222 return !(lhs < rhs); |
| 223 } |
| 224 |
| 225 protected: |
| 226 // Returns the offset from the beginning index of the buffer to the current |
| 227 // iten. |
| 228 size_t OffsetFromBegin() const { |
| 229 if (index_ >= parent_deque_->begin_) |
| 230 return index_ - parent_deque_->begin_; // On the same side as begin. |
| 231 return parent_deque_->buffer_.capacity() - parent_deque_->begin_ + index_; |
| 232 } |
| 233 |
| 234 void Increment() { |
| 235 CheckUnstableUsage(); |
| 236 parent_deque_->CheckValidIndex(index_); |
| 237 index_++; |
| 238 if (index_ == parent_deque_->buffer_.capacity()) |
| 239 index_ = 0; |
| 240 } |
| 241 void Decrement() { |
| 242 CheckUnstableUsage(); |
| 243 parent_deque_->CheckValidIndexOrEnd(index_); |
| 244 if (index_ == 0) |
| 245 index_ = parent_deque_->buffer_.capacity() - 1; |
| 246 else |
| 247 index_--; |
| 248 } |
| 249 void Add(difference_type delta) { |
| 250 CheckUnstableUsage(); |
| 251 parent_deque_->CheckValidIndex(index_); |
| 252 difference_type new_offset = OffsetFromBegin() + delta; |
| 253 DCHECK(new_offset >= 0 && |
| 254 new_offset <= static_cast<difference_type>(parent_deque_->size())); |
| 255 index_ = (new_offset + parent_deque_->begin_) % |
| 256 parent_deque_->buffer_.capacity(); |
| 257 } |
| 258 |
| 259 #if DCHECK_IS_ON() |
| 260 void CheckUnstableUsage() const { |
| 261 // Since circular_deque doesn't guarantee stability, any attempt to |
| 262 // dereference this iterator after a mutation (i.e. the generation doesn't |
| 263 // match the original) in the container is illegal. |
| 264 DCHECK(parent_deque_); |
| 265 DCHECK_EQ(created_generation_, parent_deque_->generation_) |
| 266 << "circular_deque iterator dereferenced after mutation."; |
| 267 } |
| 268 void CheckComparable(const circular_deque_const_iterator& other) const { |
| 269 DCHECK_EQ(parent_deque_, other.parent_deque_); |
| 270 CheckUnstableUsage(); |
| 271 other.CheckUnstableUsage(); |
| 272 } |
| 273 #else |
| 274 inline void CheckUnstableUsage() const {} |
| 275 inline void CheckInitialized() const {} |
| 276 inline void CheckComparable() const {} |
| 277 #endif // DCHECK_IS_ON() |
| 278 |
| 279 const circular_deque<T>* parent_deque_; |
| 280 size_t index_; |
| 281 |
| 282 #if DCHECK_IS_ON() |
| 283 // The generation of the parent deque when this iterator was created. The |
| 284 // container will update the generation for every modification so we can |
| 285 // test if the container was modified by comparing them. |
| 286 uint64_t created_generation_; |
| 287 #endif // DCHECK_IS_ON() |
| 288 }; |
| 289 |
| 290 template <typename T> |
| 291 class circular_deque_iterator : public circular_deque_const_iterator<T> { |
| 292 using base = circular_deque_const_iterator<T>; |
| 293 |
| 294 public: |
| 295 using difference_type = std::ptrdiff_t; |
| 296 using value_type = T; |
| 297 using pointer = T*; |
| 298 using reference = T&; |
| 299 using iterator_category = std::random_access_iterator_tag; |
| 300 |
| 301 circular_deque_iterator(circular_deque<T>* parent, size_t index) |
| 302 : circular_deque_const_iterator<T>(parent, index) {} |
| 303 |
| 304 // Dereferencing. |
| 305 T& operator*() { return const_cast<T&>(base::operator*()); } |
| 306 T* operator->() { return const_cast<T*>(base::operator->()); } |
| 307 |
| 308 // Random access mutation. |
| 309 friend circular_deque_iterator operator+(const circular_deque_iterator& iter, |
| 310 difference_type offset) { |
| 311 circular_deque_iterator ret = iter; |
| 312 ret.Add(offset); |
| 313 return ret; |
| 314 } |
| 315 circular_deque_iterator& operator+=(difference_type offset) { |
| 316 base::Add(offset); |
| 317 return *this; |
| 318 } |
| 319 friend circular_deque_iterator operator-(const circular_deque_iterator& iter, |
| 320 difference_type offset) { |
| 321 circular_deque_iterator ret = iter; |
| 322 ret.Add(-offset); |
| 323 return ret; |
| 324 } |
| 325 circular_deque_iterator& operator-=(difference_type offset) { |
| 326 base::Add(-offset); |
| 327 return *this; |
| 328 } |
| 329 |
| 330 // Increment and decrement. |
| 331 circular_deque_iterator& operator++() { |
| 332 base::Increment(); |
| 333 return *this; |
| 334 } |
| 335 circular_deque_iterator operator++(int) { |
| 336 circular_deque_iterator<T> ret = *this; |
| 337 base::Increment(); |
| 338 return ret; |
| 339 } |
| 340 circular_deque_iterator& operator--() { |
| 341 base::Decrement(); |
| 342 return *this; |
| 343 } |
| 344 circular_deque_iterator operator--(int) { |
| 345 circular_deque_iterator<T> ret = *this; |
| 346 base::Decrement(); |
| 347 return ret; |
| 348 } |
| 349 }; |
| 350 |
| 351 } // namespace internal |
| 352 |
| 353 template <typename T> |
| 354 class circular_deque { |
| 355 private: |
| 356 using VectorBuffer = internal::VectorBuffer<T>; |
| 357 |
| 358 public: |
| 359 using value_type = T; |
| 360 using size_type = std::size_t; |
| 361 using difference_type = std::ptrdiff_t; |
| 362 using reference = value_type&; |
| 363 using const_reference = const value_type&; |
| 364 using pointer = value_type*; |
| 365 using const_pointer = const value_type*; |
| 366 |
| 367 using iterator = internal::circular_deque_iterator<T>; |
| 368 using const_iterator = internal::circular_deque_const_iterator<T>; |
| 369 using reverse_iterator = std::reverse_iterator<iterator>; |
| 370 using const_reverse_iterator = std::reverse_iterator<const_iterator>; |
| 371 |
| 372 // --------------------------------------------------------------------------- |
| 373 // Constructor |
| 374 |
| 375 circular_deque() : begin_(0), end_(0) {} |
| 376 |
| 377 // Constructs with |count| copies of |value| or default constructed version. |
| 378 circular_deque(size_type count) : circular_deque() { resize(count); } |
| 379 circular_deque(size_type count, const T& value) : circular_deque() { |
| 380 resize(count, value); |
| 381 } |
| 382 |
| 383 // Range constructor. |
| 384 template <class InputIterator> |
| 385 circular_deque(InputIterator first, InputIterator last) : begin_(0), end_(0) { |
| 386 assign(first, last); |
| 387 } |
| 388 |
| 389 // Copy/move. |
| 390 circular_deque(const circular_deque& other) |
| 391 : buffer_(other.buffer_.capacity()), begin_(0), end_(0) { |
| 392 assign(other.begin(), other.end()); |
| 393 } |
| 394 circular_deque(circular_deque&& other) noexcept |
| 395 : buffer_(std::move(other.buffer_)), |
| 396 begin_(other.begin_), |
| 397 end_(other.end_) { |
| 398 other.begin_ = 0; |
| 399 other.end_ = 0; |
| 400 } |
| 401 |
| 402 circular_deque(std::initializer_list<value_type> init) |
| 403 : buffer_(), begin_(0), end_(0) { |
| 404 assign(init); |
| 405 } |
| 406 |
| 407 ~circular_deque() {} |
| 408 |
| 409 // --------------------------------------------------------------------------- |
| 410 // Assignments. |
| 411 // |
| 412 // All of these may invalidate iterators and references. |
| 413 |
| 414 circular_deque& operator=(const circular_deque& other) { |
| 415 clear(); |
| 416 reserve(other.size()); |
| 417 for (size_t i = 0; i < other.size(); i++) |
| 418 emplace_back(other[i]); |
| 419 |
| 420 IncrementGeneration(); |
| 421 return *this; |
| 422 } |
| 423 circular_deque& operator=(circular_deque&& other) noexcept { |
| 424 clear(); |
| 425 buffer_ = std::move(other.buffer_); |
| 426 begin_ = other.begin_; |
| 427 end_ = other.end_; |
| 428 |
| 429 other.begin_ = 0; |
| 430 other.end_ = 0; |
| 431 |
| 432 IncrementGeneration(); |
| 433 return *this; |
| 434 } |
| 435 circular_deque& operator=(std::initializer_list<value_type> ilist) { |
| 436 assign(std::begin(ilist), std::end(ilist)); |
| 437 IncrementGeneration(); |
| 438 return *this; |
| 439 } |
| 440 |
| 441 void assign(size_type count, const value_type& value) { |
| 442 clear(); |
| 443 reserve(count); |
| 444 for (size_t i = 0; i < count; i++) |
| 445 emplace_back(value); |
| 446 IncrementGeneration(); |
| 447 } |
| 448 |
| 449 // This variant should be enabled only when InputIterator is an iterator. |
| 450 template <typename InputIterator> |
| 451 typename std::enable_if<::base::internal::is_iterator<InputIterator>::value, |
| 452 void>::type |
| 453 assign(InputIterator first, InputIterator last) { |
| 454 // Possible future enhancement, dispatch on iterator tag type. For forward |
| 455 // iterators we can use std::difference to preallocate the space requried |
| 456 // and only do one copy. |
| 457 clear(); |
| 458 for (; first != last; ++first) |
| 459 emplace_back(*first); |
| 460 IncrementGeneration(); |
| 461 } |
| 462 |
| 463 void assign(std::initializer_list<value_type> value) { |
| 464 assign(value.begin(), value.end()); |
| 465 } |
| 466 |
| 467 // --------------------------------------------------------------------------- |
| 468 // Accessors. |
| 469 // |
| 470 // Since this class assumes no exceptions, at() and operator[] are equivalent. |
| 471 |
| 472 value_type& at(size_type i) { |
| 473 DCHECK(i < size()); |
| 474 size_t right_size = buffer_.capacity() - begin_; |
| 475 if (begin_ <= end_ || i < right_size) |
| 476 return buffer_[begin_ + i]; |
| 477 return buffer_[i - right_size]; |
| 478 } |
| 479 const value_type& at(size_type i) const { |
| 480 return const_cast<circular_deque*>(this)->at(i); |
| 481 } |
| 482 |
| 483 value_type& operator[](size_type i) { return at(i); } |
| 484 const value_type& operator[](size_type i) const { |
| 485 return const_cast<circular_deque*>(this)->at(i); |
| 486 } |
| 487 |
| 488 value_type& front() { |
| 489 DCHECK(!empty()); |
| 490 return buffer_[begin_]; |
| 491 } |
| 492 const value_type& front() const { |
| 493 DCHECK(!empty()); |
| 494 return buffer_[begin_]; |
| 495 } |
| 496 |
| 497 value_type& back() { |
| 498 DCHECK(!empty()); |
| 499 return *(--end()); |
| 500 } |
| 501 const value_type& back() const { |
| 502 DCHECK(!empty()); |
| 503 return *(--end()); |
| 504 } |
| 505 |
| 506 // --------------------------------------------------------------------------- |
| 507 // Iterators. |
| 508 |
| 509 iterator begin() { return iterator(this, begin_); } |
| 510 const_iterator begin() const { return const_iterator(this, begin_); } |
| 511 const_iterator cbegin() const { return const_iterator(this, begin_); } |
| 512 |
| 513 iterator end() { return iterator(this, end_); } |
| 514 const_iterator end() const { return const_iterator(this, end_); } |
| 515 const_iterator cend() const { return const_iterator(this, end_); } |
| 516 |
| 517 reverse_iterator rbegin() { return reverse_iterator(begin()); } |
| 518 const_reverse_iterator rbegin() const { |
| 519 return const_reverse_iterator(begin()); |
| 520 } |
| 521 const_reverse_iterator crbegin() const { return rbegin(); } |
| 522 |
| 523 reverse_iterator rend() { return reverse_iterator(end()); } |
| 524 const_reverse_iterator rend() const { return const_reverse_iterator(end()); } |
| 525 const_reverse_iterator crend() const { return rend(); } |
| 526 |
| 527 // --------------------------------------------------------------------------- |
| 528 // Memory management. |
| 529 |
| 530 void reserve(size_type new_capacity) { |
| 531 if (new_capacity > capacity()) |
| 532 ExpandCapacityTo(new_capacity + 1); |
| 533 } |
| 534 size_type capacity() const { |
| 535 // One item is wasted to indicate end(). |
| 536 return buffer_.capacity() == 0 ? 0 : buffer_.capacity() - 1; |
| 537 } |
| 538 void shrink_to_fit() { |
| 539 if (empty()) { |
| 540 // Optimize empty case to really delete everything if there was |
| 541 // something. |
| 542 if (buffer_.capacity()) |
| 543 buffer_ = VectorBuffer(); |
| 544 } else { |
| 545 // One item is wasted to indicate end(). |
| 546 ExpandCapacityTo(size() + 1); |
| 547 } |
| 548 } |
| 549 |
| 550 // --------------------------------------------------------------------------- |
| 551 // Size management. |
| 552 |
| 553 void clear() { resize(0); } |
| 554 |
| 555 bool empty() const { return begin_ == end_; } |
| 556 size_type size() const { |
| 557 if (begin_ <= end_) |
| 558 return end_ - begin_; |
| 559 return buffer_.capacity() - begin_ + end_; |
| 560 } |
| 561 |
| 562 // When reducing size, the elements are deleted from the end. When expanding |
| 563 // size, elements are added to the end with |value| or the default |
| 564 // constructed version. |
| 565 // |
| 566 // Resize on a queue should be very unusual so this is a simple |
| 567 // implementation. It could be optimized if needed. |
| 568 void resize(size_type count) { |
| 569 if (count > size()) { |
| 570 ExpandCapacityTo(count + 1); |
| 571 while (size() < count) |
| 572 emplace_back(); |
| 573 } else if (count < size()) { |
| 574 while (size() > count) |
| 575 pop_back(); |
| 576 } |
| 577 IncrementGeneration(); |
| 578 } |
| 579 void resize(size_type count, const value_type& value) { |
| 580 if (count > size()) { |
| 581 ExpandCapacityTo(count + 1); |
| 582 while (size() < count) |
| 583 emplace_back(value); |
| 584 } else if (count < size()) { |
| 585 while (size() > count) |
| 586 pop_back(); |
| 587 } |
| 588 IncrementGeneration(); |
| 589 } |
| 590 |
| 591 // --------------------------------------------------------------------------- |
| 592 // Insert and erase. |
| 593 // |
| 594 // These bulk insert operations are not provided as described in the file |
| 595 // level comment above: |
| 596 // |
| 597 // void insert(const_iterator pos, size_type count, const T& value); |
| 598 // void insert(const_iterator pos, InputIterator first, InputIterator last); |
| 599 // iterator insert(const_iterator pos, const T& value); |
| 600 // iterator insert(const_iterator pos, T&& value); |
| 601 // iterator emplace(const_iterator pos, Args&&... args); |
| 602 // |
| 603 // iterator erase(const_iterator pos); |
| 604 // iterator erase(const_iterator first, const_iterator last); |
| 605 |
| 606 // --------------------------------------------------------------------------- |
| 607 // Begin/end operations. |
| 608 |
| 609 void push_front(const T& value) { emplace_front(value); } |
| 610 void push_front(T&& value) { emplace_front(std::move(value)); } |
| 611 |
| 612 void push_back(const T& value) { emplace_back(value); } |
| 613 void push_back(T&& value) { emplace_back(std::move(value)); } |
| 614 |
| 615 template <class... Args> |
| 616 void emplace_front(Args&&... args) { |
| 617 ExpandCapacityIfNecessary(1); |
| 618 if (begin_ == 0) |
| 619 begin_ = buffer_.capacity() - 1; |
| 620 else |
| 621 begin_--; |
| 622 IncrementGeneration(); |
| 623 new (&buffer_[begin_]) T(std::forward<Args>(args)...); |
| 624 } |
| 625 |
| 626 template <class... Args> |
| 627 void emplace_back(Args&&... args) { |
| 628 ExpandCapacityIfNecessary(1); |
| 629 new (&buffer_[end_]) T(std::forward<Args>(args)...); |
| 630 if (end_ == buffer_.capacity() - 1) |
| 631 end_ = 0; |
| 632 else |
| 633 end_++; |
| 634 IncrementGeneration(); |
| 635 } |
| 636 |
| 637 void pop_front() { |
| 638 DCHECK(size()); |
| 639 buffer_.DestructRange(&buffer_[begin_], &buffer_[begin_ + 1]); |
| 640 begin_++; |
| 641 if (begin_ == buffer_.capacity()) |
| 642 begin_ = 0; |
| 643 |
| 644 // Technically popping will not invalidate any iterators since the |
| 645 // underlying buffer will be stable. But in the future we may want to add a |
| 646 // feature that resizes the buffer smaller if there is too much wasted |
| 647 // space. This ensures we can make such a change safely. |
| 648 IncrementGeneration(); |
| 649 } |
| 650 void pop_back() { |
| 651 DCHECK(size()); |
| 652 if (end_ == 0) |
| 653 end_ = buffer_.capacity() - 1; |
| 654 else |
| 655 end_--; |
| 656 buffer_.DestructRange(&buffer_[end_], &buffer_[end_ + 1]); |
| 657 |
| 658 // See pop_front comment about why this is here. |
| 659 IncrementGeneration(); |
| 660 } |
| 661 |
| 662 // --------------------------------------------------------------------------- |
| 663 // General operations. |
| 664 |
| 665 void swap(circular_deque& other) { |
| 666 std::swap(buffer_, other.buffer_); |
| 667 std::swap(begin_, other.begin_); |
| 668 std::swap(end_, other.end_); |
| 669 IncrementGeneration(); |
| 670 } |
| 671 |
| 672 friend void swap(circular_deque& lhs, circular_deque& rhs) { lhs.swap(rhs); } |
| 673 |
| 674 private: |
| 675 friend internal::circular_deque_iterator<T>; |
| 676 friend internal::circular_deque_const_iterator<T>; |
| 677 |
| 678 // Moves the items in the given circular buffer to the current one. The |
| 679 // source is moved from so will become invalid. The destination buffer must |
| 680 // have already been allocated with enough size. |
| 681 static void MoveBuffer(VectorBuffer& from_buf, |
| 682 size_t from_begin, |
| 683 size_t from_end, |
| 684 VectorBuffer* to_buf, |
| 685 size_t* to_begin, |
| 686 size_t* to_end) { |
| 687 size_t from_capacity = from_buf.capacity(); |
| 688 |
| 689 *to_begin = 0; |
| 690 if (from_begin < from_end) { |
| 691 // Contiguous. |
| 692 from_buf.MoveRange(&from_buf[from_begin], &from_buf[from_end], |
| 693 to_buf->begin()); |
| 694 *to_end = from_end - from_begin; |
| 695 } else if (from_begin > from_end) { |
| 696 // Discontiguous, copy the right side to the beginning of the new buffer. |
| 697 from_buf.MoveRange(&from_buf[from_begin], &from_buf[from_capacity], |
| 698 to_buf->begin()); |
| 699 size_t right_size = from_capacity - from_begin; |
| 700 // Append the left side. |
| 701 from_buf.MoveRange(&from_buf[0], &from_buf[from_end], |
| 702 &(*to_buf)[right_size]); |
| 703 *to_end = right_size + from_end; |
| 704 } else { |
| 705 // No items. |
| 706 *to_end = 0; |
| 707 } |
| 708 } |
| 709 |
| 710 // Expands the buffer size. This assumes the size is larger than the |
| 711 // number of elements in the vector (it won't call delete on anything). |
| 712 // Note the capacity passed here will be one larger than the "publicly |
| 713 // exposed capacity" to account for the unused end element. |
| 714 void ExpandCapacityTo(size_t new_capacity) { |
| 715 VectorBuffer new_buffer(new_capacity); |
| 716 MoveBuffer(buffer_, begin_, end_, &new_buffer, &begin_, &end_); |
| 717 buffer_ = std::move(new_buffer); |
| 718 } |
| 719 void ExpandCapacityIfNecessary(size_t additional_elts) { |
| 720 // Capacity is internal capacity, which is one extra. |
| 721 size_t min_new_capacity = size() + additional_elts + 1; |
| 722 if (buffer_.capacity() >= min_new_capacity) |
| 723 return; // Already enough room. |
| 724 |
| 725 // Start allocating nonempty buffers with this many entries. |
| 726 constexpr size_t min_slots = 4; |
| 727 min_new_capacity = std::max(min_new_capacity, min_slots); |
| 728 |
| 729 // std::vector always grows by at least 50%. WTF::Deque grows by at least |
| 730 // 25%. We expect queue workloads to generally stay at a similar size and |
| 731 // grow less than a vector might, so use 25%. |
| 732 size_t new_capacity = std::max( |
| 733 min_new_capacity, buffer_.capacity() + buffer_.capacity() / 4 + 1); |
| 734 ExpandCapacityTo(new_capacity); |
| 735 } |
| 736 |
| 737 #if DCHECK_IS_ON() |
| 738 // Asserts the given index is dereferencable. The index is an index into the |
| 739 // buffer, not an index used by operator[] or at() which will be offsets from |
| 740 // begin. |
| 741 void CheckValidIndex(size_t i) const { |
| 742 if (begin_ <= end_) |
| 743 DCHECK(i >= begin_ && i < end_); |
| 744 else |
| 745 DCHECK((i >= begin_ && i < buffer_.capacity()) || i < end_); |
| 746 } |
| 747 |
| 748 // Asserts the given index is either dereferencable or points to end(). |
| 749 void CheckValidIndexOrEnd(size_t i) const { |
| 750 if (i != end_) |
| 751 CheckValidIndex(i); |
| 752 } |
| 753 |
| 754 // See generation_ below. |
| 755 void IncrementGeneration() { generation_++; } |
| 756 #else |
| 757 // No-op versions of these functions for release builds. |
| 758 void CheckValidIndex(size_t) const {} |
| 759 void CheckValidIndexOrEnd(size_t) const {} |
| 760 void IncrementGeneration() {} |
| 761 #endif |
| 762 |
| 763 // Danger, the buffer_.capacity() is capacity() + 1 since there is an |
| 764 // extra item to indicate the end. Container internal code will want to use |
| 765 // buffer_.capacity() for offset computations. |
| 766 VectorBuffer buffer_; |
| 767 size_type begin_; |
| 768 size_type end_; |
| 769 |
| 770 #if DCHECK_IS_ON() |
| 771 // Incremented every time a modification that could affect iterator |
| 772 // invalidations. |
| 773 uint64_t generation_ = 0; |
| 774 #endif |
| 775 }; |
| 776 |
| 777 } // namespace base |
| 778 |
| 779 #endif // BASE_CONTAINERS_CIRCULAR_DEQUE_H_ |
OLD | NEW |