1 // Copyright (c) 2019 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 QUICHE_QUIC_CORE_QUIC_CIRCULAR_DEQUE_H_ 6 #define QUICHE_QUIC_CORE_QUIC_CIRCULAR_DEQUE_H_ 7 8 #include <algorithm> 9 #include <cstddef> 10 #include <cstring> 11 #include <iterator> 12 #include <memory> 13 #include <ostream> 14 #include <type_traits> 15 16 #include "net/third_party/quiche/src/quic/platform/api/quic_export.h" 17 #include "net/third_party/quiche/src/quic/platform/api/quic_logging.h" 18 19 namespace quic { 20 21 // QuicCircularDeque is a STL-style container that is similar to std deque in 22 // API and std::vector in capacity management. The goal is to optimize a common 23 // QUIC use case where we keep adding new elements to the end and removing old 24 // elements from the beginning, under such scenarios, if the container's size() 25 // remain relatively stable, QuicCircularDeque requires little to no memory 26 // allocations or deallocations. 27 // 28 // The implementation, as the name suggests, uses a flat circular buffer to hold 29 // all elements. At any point in time, either 30 // a) All elements are placed in a contiguous portion of this buffer, like a 31 // c-array, or 32 // b) Elements are phycially divided into two parts: the first part occupies the 33 // end of the buffer and the second part occupies the beginning of the 34 // buffer. 35 // 36 // Currently, elements can only be pushed or poped from either ends, it can't be 37 // inserted or erased in the middle. 38 // 39 // TODO(wub): Make memory grow/shrink strategies customizable. 40 template <typename T, 41 size_t MinCapacityIncrement = 3, 42 typename Allocator = std::allocator<T>> 43 class QUIC_NO_EXPORT QuicCircularDeque { 44 using AllocatorTraits = std::allocator_traits<Allocator>; 45 46 // Pointee is either T or const T. 47 template <typename Pointee> 48 class QUIC_NO_EXPORT basic_iterator { 49 using size_type = typename AllocatorTraits::size_type; 50 51 public: 52 using iterator_category = std::random_access_iterator_tag; 53 using value_type = typename AllocatorTraits::value_type; 54 using difference_type = typename AllocatorTraits::difference_type; 55 using pointer = Pointee*; 56 using reference = Pointee&; 57 58 basic_iterator() = default; 59 60 // A copy constructor if Pointee is T. 61 // A conversion from iterator to const_iterator if Pointee is const T. basic_iterator(const basic_iterator<value_type> & it)62 basic_iterator( 63 const basic_iterator<value_type>& it) // NOLINT(runtime/explicit) 64 : deque_(it.deque_), index_(it.index_) {} 65 66 // A copy assignment if Pointee is T. 67 // A assignment from iterator to const_iterator if Pointee is const T. 68 basic_iterator& operator=(const basic_iterator<value_type>& it) { 69 if (this != &it) { 70 deque_ = it.deque_; 71 index_ = it.index_; 72 } 73 return *this; 74 } 75 76 reference operator*() const { return *deque_->index_to_address(index_); } 77 pointer operator->() const { return deque_->index_to_address(index_); } 78 reference operator[](difference_type i) { return *(*this + i); } 79 80 basic_iterator& operator++() { 81 Increment(); 82 return *this; 83 } 84 85 basic_iterator operator++(int) { 86 basic_iterator result = *this; 87 Increment(); 88 return result; 89 } 90 91 basic_iterator operator--() { 92 Decrement(); 93 return *this; 94 } 95 96 basic_iterator operator--(int) { 97 basic_iterator result = *this; 98 Decrement(); 99 return result; 100 } 101 102 friend basic_iterator operator+(const basic_iterator& it, 103 difference_type delta) { 104 basic_iterator result = it; 105 result.IncrementBy(delta); 106 return result; 107 } 108 109 basic_iterator& operator+=(difference_type delta) { 110 IncrementBy(delta); 111 return *this; 112 } 113 114 friend basic_iterator operator-(const basic_iterator& it, 115 difference_type delta) { 116 basic_iterator result = it; 117 result.IncrementBy(-delta); 118 return result; 119 } 120 121 basic_iterator& operator-=(difference_type delta) { 122 IncrementBy(-delta); 123 return *this; 124 } 125 126 friend difference_type operator-(const basic_iterator& lhs, 127 const basic_iterator& rhs) { 128 return lhs.ExternalPosition() - rhs.ExternalPosition(); 129 } 130 131 friend bool operator==(const basic_iterator& lhs, 132 const basic_iterator& rhs) { 133 return lhs.index_ == rhs.index_; 134 } 135 136 friend bool operator!=(const basic_iterator& lhs, 137 const basic_iterator& rhs) { 138 return !(lhs == rhs); 139 } 140 141 friend bool operator<(const basic_iterator& lhs, 142 const basic_iterator& rhs) { 143 return lhs.ExternalPosition() < rhs.ExternalPosition(); 144 } 145 146 friend bool operator<=(const basic_iterator& lhs, 147 const basic_iterator& rhs) { 148 return !(lhs > rhs); 149 } 150 151 friend bool operator>(const basic_iterator& lhs, 152 const basic_iterator& rhs) { 153 return lhs.ExternalPosition() > rhs.ExternalPosition(); 154 } 155 156 friend bool operator>=(const basic_iterator& lhs, 157 const basic_iterator& rhs) { 158 return !(lhs < rhs); 159 } 160 161 private: basic_iterator(const QuicCircularDeque * deque,size_type index)162 basic_iterator(const QuicCircularDeque* deque, size_type index) 163 : deque_(deque), index_(index) {} 164 Increment()165 void Increment() { 166 DCHECK_LE(ExternalPosition() + 1, deque_->size()); 167 index_ = deque_->index_next(index_); 168 } 169 Decrement()170 void Decrement() { 171 DCHECK_GE(ExternalPosition(), 1u); 172 index_ = deque_->index_prev(index_); 173 } 174 IncrementBy(difference_type delta)175 void IncrementBy(difference_type delta) { 176 if (delta >= 0) { 177 // After increment we are before or at end(). 178 DCHECK_LE(static_cast<size_type>(ExternalPosition() + delta), 179 deque_->size()); 180 } else { 181 // After decrement we are after or at begin(). 182 DCHECK_GE(ExternalPosition(), static_cast<size_type>(-delta)); 183 } 184 index_ = deque_->index_increment_by(index_, delta); 185 } 186 ExternalPosition()187 size_type ExternalPosition() const { 188 if (index_ >= deque_->begin_) { 189 return index_ - deque_->begin_; 190 } 191 return index_ + deque_->data_capacity() - deque_->begin_; 192 } 193 194 friend class QuicCircularDeque; 195 const QuicCircularDeque* deque_ = nullptr; 196 size_type index_ = 0; 197 }; 198 199 public: 200 using allocator_type = typename AllocatorTraits::allocator_type; 201 using value_type = typename AllocatorTraits::value_type; 202 using size_type = typename AllocatorTraits::size_type; 203 using difference_type = typename AllocatorTraits::difference_type; 204 using reference = value_type&; 205 using const_reference = const value_type&; 206 using pointer = typename AllocatorTraits::pointer; 207 using const_pointer = typename AllocatorTraits::const_pointer; 208 using iterator = basic_iterator<T>; 209 using const_iterator = basic_iterator<const T>; 210 using reverse_iterator = std::reverse_iterator<iterator>; 211 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 212 QuicCircularDeque()213 QuicCircularDeque() : QuicCircularDeque(allocator_type()) {} QuicCircularDeque(const allocator_type & alloc)214 explicit QuicCircularDeque(const allocator_type& alloc) 215 : allocator_and_data_(alloc) {} 216 217 QuicCircularDeque(size_type count, 218 const T& value, 219 const Allocator& alloc = allocator_type()) allocator_and_data_(alloc)220 : allocator_and_data_(alloc) { 221 resize(count, value); 222 } 223 224 explicit QuicCircularDeque(size_type count, 225 const Allocator& alloc = allocator_type()) allocator_and_data_(alloc)226 : allocator_and_data_(alloc) { 227 resize(count); 228 } 229 230 template < 231 class InputIt, 232 typename = std::enable_if_t<std::is_base_of< 233 std::input_iterator_tag, 234 typename std::iterator_traits<InputIt>::iterator_category>::value>> 235 QuicCircularDeque(InputIt first, 236 InputIt last, 237 const Allocator& alloc = allocator_type()) allocator_and_data_(alloc)238 : allocator_and_data_(alloc) { 239 AssignRange(first, last); 240 } 241 QuicCircularDeque(const QuicCircularDeque & other)242 QuicCircularDeque(const QuicCircularDeque& other) 243 : QuicCircularDeque( 244 other, 245 AllocatorTraits::select_on_container_copy_construction( 246 other.allocator_and_data_.allocator())) {} 247 QuicCircularDeque(const QuicCircularDeque & other,const allocator_type & alloc)248 QuicCircularDeque(const QuicCircularDeque& other, const allocator_type& alloc) 249 : allocator_and_data_(alloc) { 250 assign(other.begin(), other.end()); 251 } 252 QuicCircularDeque(QuicCircularDeque && other)253 QuicCircularDeque(QuicCircularDeque&& other) 254 : begin_(other.begin_), 255 end_(other.end_), 256 allocator_and_data_(std::move(other.allocator_and_data_)) { 257 other.begin_ = other.end_ = 0; 258 other.allocator_and_data_.data = nullptr; 259 other.allocator_and_data_.data_capacity = 0; 260 } 261 QuicCircularDeque(QuicCircularDeque && other,const allocator_type & alloc)262 QuicCircularDeque(QuicCircularDeque&& other, const allocator_type& alloc) 263 : allocator_and_data_(alloc) { 264 MoveRetainAllocator(std::move(other)); 265 } 266 267 QuicCircularDeque(std::initializer_list<T> init, 268 const allocator_type& alloc = allocator_type()) 269 : QuicCircularDeque(init.begin(), init.end(), alloc) {} 270 271 QuicCircularDeque& operator=(const QuicCircularDeque& other) { 272 if (this == &other) { 273 return *this; 274 } 275 if (AllocatorTraits::propagate_on_container_copy_assignment::value && 276 (allocator_and_data_.allocator() != 277 other.allocator_and_data_.allocator())) { 278 // Destroy all current elements and blocks with the current allocator, 279 // before switching this to use the allocator propagated from "other". 280 DestroyAndDeallocateAll(); 281 begin_ = end_ = 0; 282 allocator_and_data_ = 283 AllocatorAndData(other.allocator_and_data_.allocator()); 284 } 285 assign(other.begin(), other.end()); 286 return *this; 287 } 288 289 QuicCircularDeque& operator=(QuicCircularDeque&& other) { 290 if (this == &other) { 291 return *this; 292 } 293 if (AllocatorTraits::propagate_on_container_move_assignment::value) { 294 // Take over the storage of "other", along with its allocator. 295 this->~QuicCircularDeque(); 296 new (this) QuicCircularDeque(std::move(other)); 297 } else { 298 MoveRetainAllocator(std::move(other)); 299 } 300 return *this; 301 } 302 ~QuicCircularDeque()303 ~QuicCircularDeque() { DestroyAndDeallocateAll(); } 304 assign(size_type count,const T & value)305 void assign(size_type count, const T& value) { 306 ClearRetainCapacity(); 307 reserve(count); 308 for (size_t i = 0; i < count; ++i) { 309 emplace_back(value); 310 } 311 } 312 313 template < 314 class InputIt, 315 typename = std::enable_if_t<std::is_base_of< 316 std::input_iterator_tag, 317 typename std::iterator_traits<InputIt>::iterator_category>::value>> assign(InputIt first,InputIt last)318 void assign(InputIt first, InputIt last) { 319 AssignRange(first, last); 320 } 321 assign(std::initializer_list<T> ilist)322 void assign(std::initializer_list<T> ilist) { 323 assign(ilist.begin(), ilist.end()); 324 } 325 at(size_type pos)326 reference at(size_type pos) { 327 DCHECK(pos < size()) << "pos:" << pos << ", size():" << size(); 328 size_type index = begin_ + pos; 329 if (index < data_capacity()) { 330 return *index_to_address(index); 331 } 332 return *index_to_address(index - data_capacity()); 333 } 334 at(size_type pos)335 const_reference at(size_type pos) const { 336 return const_cast<QuicCircularDeque*>(this)->at(pos); 337 } 338 339 reference operator[](size_type pos) { return at(pos); } 340 341 const_reference operator[](size_type pos) const { return at(pos); } 342 front()343 reference front() { 344 DCHECK(!empty()); 345 return *index_to_address(begin_); 346 } 347 front()348 const_reference front() const { 349 return const_cast<QuicCircularDeque*>(this)->front(); 350 } 351 back()352 reference back() { 353 DCHECK(!empty()); 354 return *(index_to_address(end_ == 0 ? data_capacity() - 1 : end_ - 1)); 355 } 356 back()357 const_reference back() const { 358 return const_cast<QuicCircularDeque*>(this)->back(); 359 } 360 begin()361 iterator begin() { return iterator(this, begin_); } begin()362 const_iterator begin() const { return const_iterator(this, begin_); } cbegin()363 const_iterator cbegin() const { return const_iterator(this, begin_); } 364 end()365 iterator end() { return iterator(this, end_); } end()366 const_iterator end() const { return const_iterator(this, end_); } cend()367 const_iterator cend() const { return const_iterator(this, end_); } 368 rbegin()369 reverse_iterator rbegin() { return reverse_iterator(end()); } rbegin()370 const_reverse_iterator rbegin() const { 371 return const_reverse_iterator(end()); 372 } crbegin()373 const_reverse_iterator crbegin() const { return rbegin(); } 374 rend()375 reverse_iterator rend() { return reverse_iterator(begin()); } rend()376 const_reverse_iterator rend() const { 377 return const_reverse_iterator(begin()); 378 } crend()379 const_reverse_iterator crend() const { return rend(); } 380 capacity()381 size_type capacity() const { 382 return data_capacity() == 0 ? 0 : data_capacity() - 1; 383 } 384 reserve(size_type new_cap)385 void reserve(size_type new_cap) { 386 if (new_cap > capacity()) { 387 Relocate(new_cap); 388 } 389 } 390 391 // Remove all elements. Leave capacity unchanged. clear()392 void clear() { ClearRetainCapacity(); } 393 empty()394 bool empty() const { return begin_ == end_; } 395 size()396 size_type size() const { 397 if (begin_ <= end_) { 398 return end_ - begin_; 399 } 400 return data_capacity() + end_ - begin_; 401 } 402 resize(size_type count)403 void resize(size_type count) { ResizeInternal(count); } 404 resize(size_type count,const value_type & value)405 void resize(size_type count, const value_type& value) { 406 ResizeInternal(count, value); 407 } 408 push_front(const T & value)409 void push_front(const T& value) { emplace_front(value); } push_front(T && value)410 void push_front(T&& value) { emplace_front(std::move(value)); } 411 412 template <class... Args> emplace_front(Args &&...args)413 reference emplace_front(Args&&... args) { 414 MaybeExpandCapacity(1); 415 begin_ = index_prev(begin_); 416 new (index_to_address(begin_)) T(std::forward<Args>(args)...); 417 return front(); 418 } 419 push_back(const T & value)420 void push_back(const T& value) { emplace_back(value); } push_back(T && value)421 void push_back(T&& value) { emplace_back(std::move(value)); } 422 423 template <class... Args> emplace_back(Args &&...args)424 reference emplace_back(Args&&... args) { 425 MaybeExpandCapacity(1); 426 new (index_to_address(end_)) T(std::forward<Args>(args)...); 427 end_ = index_next(end_); 428 return back(); 429 } 430 pop_front()431 void pop_front() { 432 DCHECK(!empty()); 433 DestroyByIndex(begin_); 434 begin_ = index_next(begin_); 435 MaybeShrinkCapacity(); 436 } 437 pop_front_n(size_type count)438 size_type pop_front_n(size_type count) { 439 size_type num_elements_to_pop = std::min(count, size()); 440 size_type new_begin = index_increment_by(begin_, num_elements_to_pop); 441 DestroyRange(begin_, new_begin); 442 begin_ = new_begin; 443 MaybeShrinkCapacity(); 444 return num_elements_to_pop; 445 } 446 pop_back()447 void pop_back() { 448 DCHECK(!empty()); 449 end_ = index_prev(end_); 450 DestroyByIndex(end_); 451 MaybeShrinkCapacity(); 452 } 453 pop_back_n(size_type count)454 size_type pop_back_n(size_type count) { 455 size_type num_elements_to_pop = std::min(count, size()); 456 size_type new_end = index_increment_by(end_, -num_elements_to_pop); 457 DestroyRange(new_end, end_); 458 end_ = new_end; 459 MaybeShrinkCapacity(); 460 return num_elements_to_pop; 461 } 462 swap(QuicCircularDeque & other)463 void swap(QuicCircularDeque& other) { 464 using std::swap; 465 swap(begin_, other.begin_); 466 swap(end_, other.end_); 467 468 if (AllocatorTraits::propagate_on_container_swap::value) { 469 swap(allocator_and_data_, other.allocator_and_data_); 470 } else { 471 // When propagate_on_container_swap is false, it is undefined behavior, by 472 // c++ standard, to swap between two AllocatorAwareContainer(s) with 473 // unequal allocators. 474 DCHECK(get_allocator() == other.get_allocator()) 475 << "Undefined swap behavior"; 476 swap(allocator_and_data_.data, other.allocator_and_data_.data); 477 swap(allocator_and_data_.data_capacity, 478 other.allocator_and_data_.data_capacity); 479 } 480 } 481 swap(QuicCircularDeque & lhs,QuicCircularDeque & rhs)482 friend void swap(QuicCircularDeque& lhs, QuicCircularDeque& rhs) { 483 lhs.swap(rhs); 484 } 485 get_allocator()486 allocator_type get_allocator() const { 487 return allocator_and_data_.allocator(); 488 } 489 490 friend bool operator==(const QuicCircularDeque& lhs, 491 const QuicCircularDeque& rhs) { 492 return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); 493 } 494 495 friend bool operator!=(const QuicCircularDeque& lhs, 496 const QuicCircularDeque& rhs) { 497 return !(lhs == rhs); 498 } 499 500 friend QUIC_NO_EXPORT std::ostream& operator<<(std::ostream& os, 501 const QuicCircularDeque& dq) { 502 os << "{"; 503 for (size_type pos = 0; pos != dq.size(); ++pos) { 504 if (pos != 0) { 505 os << ","; 506 } 507 os << " " << dq[pos]; 508 } 509 os << " }"; 510 return os; 511 } 512 513 private: MoveRetainAllocator(QuicCircularDeque && other)514 void MoveRetainAllocator(QuicCircularDeque&& other) { 515 if (get_allocator() == other.get_allocator()) { 516 // Take over the storage of "other", with which we share an allocator. 517 DestroyAndDeallocateAll(); 518 519 begin_ = other.begin_; 520 end_ = other.end_; 521 allocator_and_data_.data = other.allocator_and_data_.data; 522 allocator_and_data_.data_capacity = 523 other.allocator_and_data_.data_capacity; 524 525 other.begin_ = other.end_ = 0; 526 other.allocator_and_data_.data = nullptr; 527 other.allocator_and_data_.data_capacity = 0; 528 } else { 529 // We cannot take over of the storage from "other", since it has a 530 // different allocator; we're stuck move-assigning elements individually. 531 ClearRetainCapacity(); 532 for (auto& elem : other) { 533 push_back(std::move(elem)); 534 } 535 other.clear(); 536 } 537 } 538 539 template < 540 typename InputIt, 541 typename = std::enable_if_t<std::is_base_of< 542 std::input_iterator_tag, 543 typename std::iterator_traits<InputIt>::iterator_category>::value>> AssignRange(InputIt first,InputIt last)544 void AssignRange(InputIt first, InputIt last) { 545 ClearRetainCapacity(); 546 if (std::is_base_of< 547 std::random_access_iterator_tag, 548 typename std::iterator_traits<InputIt>::iterator_category>::value) { 549 reserve(std::distance(first, last)); 550 } 551 for (; first != last; ++first) { 552 emplace_back(*first); 553 } 554 } 555 556 // WARNING: begin_, end_ and allocator_and_data_ are not modified. DestroyAndDeallocateAll()557 void DestroyAndDeallocateAll() { 558 DestroyRange(begin_, end_); 559 560 if (data_capacity() > 0) { 561 DCHECK_NE(nullptr, allocator_and_data_.data); 562 AllocatorTraits::deallocate(allocator_and_data_.allocator(), 563 allocator_and_data_.data, data_capacity()); 564 } 565 } 566 ClearRetainCapacity()567 void ClearRetainCapacity() { 568 DestroyRange(begin_, end_); 569 begin_ = end_ = 0; 570 } 571 MaybeShrinkCapacity()572 void MaybeShrinkCapacity() { 573 // TODO(wub): Implement a storage policy that actually shrinks. 574 } 575 MaybeExpandCapacity(size_t num_additional_elements)576 void MaybeExpandCapacity(size_t num_additional_elements) { 577 size_t new_size = size() + num_additional_elements; 578 if (capacity() >= new_size) { 579 return; 580 } 581 582 // The minimum amount of additional capacity to grow. 583 size_t min_additional_capacity = 584 std::max(MinCapacityIncrement, capacity() / 4); 585 size_t new_capacity = 586 std::max(new_size, capacity() + min_additional_capacity); 587 588 Relocate(new_capacity); 589 } 590 Relocate(size_t new_capacity)591 void Relocate(size_t new_capacity) { 592 const size_t num_elements = size(); 593 DCHECK_GT(new_capacity, num_elements) 594 << "new_capacity:" << new_capacity << ", num_elements:" << num_elements; 595 596 size_t new_data_capacity = new_capacity + 1; 597 pointer new_data = AllocatorTraits::allocate( 598 allocator_and_data_.allocator(), new_data_capacity); 599 600 if (begin_ < end_) { 601 // Not wrapped. 602 RelocateUnwrappedRange(begin_, end_, new_data); 603 } else if (begin_ > end_) { 604 // Wrapped. 605 const size_t num_elements_before_wrap = data_capacity() - begin_; 606 RelocateUnwrappedRange(begin_, data_capacity(), new_data); 607 RelocateUnwrappedRange(0, end_, new_data + num_elements_before_wrap); 608 } 609 610 if (data_capacity()) { 611 AllocatorTraits::deallocate(allocator_and_data_.allocator(), 612 allocator_and_data_.data, data_capacity()); 613 } 614 615 allocator_and_data_.data = new_data; 616 allocator_and_data_.data_capacity = new_data_capacity; 617 begin_ = 0; 618 end_ = num_elements; 619 } 620 621 template <typename T_ = T> 622 typename std::enable_if<std::is_trivially_copyable<T_>::value, void>::type RelocateUnwrappedRange(size_type begin,size_type end,pointer dest)623 RelocateUnwrappedRange(size_type begin, size_type end, pointer dest) const { 624 DCHECK_LE(begin, end) << "begin:" << begin << ", end:" << end; 625 pointer src = index_to_address(begin); 626 DCHECK_NE(src, nullptr); 627 memcpy(dest, src, sizeof(T) * (end - begin)); 628 DestroyRange(begin, end); 629 } 630 631 template <typename T_ = T> 632 typename std::enable_if<!std::is_trivially_copyable<T_>::value && 633 std::is_move_constructible<T_>::value, 634 void>::type RelocateUnwrappedRange(size_type begin,size_type end,pointer dest)635 RelocateUnwrappedRange(size_type begin, size_type end, pointer dest) const { 636 DCHECK_LE(begin, end) << "begin:" << begin << ", end:" << end; 637 pointer src = index_to_address(begin); 638 pointer src_end = index_to_address(end); 639 while (src != src_end) { 640 new (dest) T(std::move(*src)); 641 DestroyByAddress(src); 642 ++dest; 643 ++src; 644 } 645 } 646 647 template <typename T_ = T> 648 typename std::enable_if<!std::is_trivially_copyable<T_>::value && 649 !std::is_move_constructible<T_>::value, 650 void>::type RelocateUnwrappedRange(size_type begin,size_type end,pointer dest)651 RelocateUnwrappedRange(size_type begin, size_type end, pointer dest) const { 652 DCHECK_LE(begin, end) << "begin:" << begin << ", end:" << end; 653 pointer src = index_to_address(begin); 654 pointer src_end = index_to_address(end); 655 while (src != src_end) { 656 new (dest) T(*src); 657 DestroyByAddress(src); 658 ++dest; 659 ++src; 660 } 661 } 662 663 template <class... U> ResizeInternal(size_type count,U &&...u)664 void ResizeInternal(size_type count, U&&... u) { 665 if (count > size()) { 666 // Expanding. 667 MaybeExpandCapacity(count - size()); 668 while (size() < count) { 669 emplace_back(std::forward<U>(u)...); 670 } 671 } else { 672 // Most likely shrinking. No-op if count == size(). 673 size_type new_end = (begin_ + count) % data_capacity(); 674 DestroyRange(new_end, end_); 675 end_ = new_end; 676 677 MaybeShrinkCapacity(); 678 } 679 } 680 DestroyRange(size_type begin,size_type end)681 void DestroyRange(size_type begin, size_type end) const { 682 if (std::is_trivially_destructible<T>::value) { 683 return; 684 } 685 if (end >= begin) { 686 DestroyUnwrappedRange(begin, end); 687 } else { 688 DestroyUnwrappedRange(begin, data_capacity()); 689 DestroyUnwrappedRange(0, end); 690 } 691 } 692 693 // Should only be called from DestroyRange. DestroyUnwrappedRange(size_type begin,size_type end)694 void DestroyUnwrappedRange(size_type begin, size_type end) const { 695 DCHECK_LE(begin, end) << "begin:" << begin << ", end:" << end; 696 for (; begin != end; ++begin) { 697 DestroyByIndex(begin); 698 } 699 } 700 DestroyByIndex(size_type index)701 void DestroyByIndex(size_type index) const { 702 DestroyByAddress(index_to_address(index)); 703 } 704 DestroyByAddress(pointer address)705 void DestroyByAddress(pointer address) const { 706 if (std::is_trivially_destructible<T>::value) { 707 return; 708 } 709 address->~T(); 710 } 711 data_capacity()712 size_type data_capacity() const { return allocator_and_data_.data_capacity; } 713 index_to_address(size_type index)714 pointer index_to_address(size_type index) const { 715 return allocator_and_data_.data + index; 716 } 717 index_prev(size_type index)718 size_type index_prev(size_type index) const { 719 return index == 0 ? data_capacity() - 1 : index - 1; 720 } 721 index_next(size_type index)722 size_type index_next(size_type index) const { 723 return index == data_capacity() - 1 ? 0 : index + 1; 724 } 725 index_increment_by(size_type index,difference_type delta)726 size_type index_increment_by(size_type index, difference_type delta) const { 727 if (delta == 0) { 728 return index; 729 } 730 731 DCHECK_LT(static_cast<size_type>(std::abs(delta)), data_capacity()); 732 return (index + data_capacity() + delta) % data_capacity(); 733 } 734 735 // Empty base-class optimization: bundle storage for our allocator together 736 // with the fields we had to store anyway, via inheriting from the allocator, 737 // so this allocator instance doesn't consume any storage when its type has no 738 // data members. 739 struct AllocatorAndData : private allocator_type { AllocatorAndDataAllocatorAndData740 explicit AllocatorAndData(const allocator_type& alloc) 741 : allocator_type(alloc) {} 742 allocatorAllocatorAndData743 const allocator_type& allocator() const { return *this; } allocatorAllocatorAndData744 allocator_type& allocator() { return *this; } 745 746 pointer data = nullptr; 747 size_type data_capacity = 0; 748 }; 749 750 size_type begin_ = 0; 751 size_type end_ = 0; 752 AllocatorAndData allocator_and_data_; 753 }; 754 755 } // namespace quic 756 757 #endif // QUICHE_QUIC_CORE_QUIC_CIRCULAR_DEQUE_H_ 758