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