gfe-relnote: (n/a) Add pop_front_n and pop_back_n methods to QuicCircularDeque. Code not used yet.
PiperOrigin-RevId: 279127905
Change-Id: I3a5ee539cb53d1cb7fac68ba30f230135f1023fd
diff --git a/quic/core/quic_circular_deque.h b/quic/core/quic_circular_deque.h
index 54043fd..3a34626 100644
--- a/quic/core/quic_circular_deque.h
+++ b/quic/core/quic_circular_deque.h
@@ -151,17 +151,25 @@
basic_iterator(const QuicCircularDeque* deque, size_type index)
: deque_(deque), index_(index) {}
- void Increment() { index_ = deque_->index_next(index_); }
+ void Increment() {
+ DCHECK_LE(ExternalPosition() + 1, deque_->size());
+ index_ = deque_->index_next(index_);
+ }
- void Decrement() { index_ = deque_->index_prev(index_); }
+ void Decrement() {
+ DCHECK_GE(ExternalPosition(), 1);
+ index_ = deque_->index_prev(index_);
+ }
void IncrementBy(difference_type delta) {
- if (delta == 0) {
- return;
+ if (delta >= 0) {
+ // After increment we are before or at end().
+ DCHECK_LE(ExternalPosition() + delta, deque_->size());
+ } else {
+ // After decrement we are after or at begin().
+ DCHECK_GE(ExternalPosition(), -delta);
}
-
- index_ = (deque_->begin_ + ExternalPosition() + delta) %
- deque_->data_capacity();
+ index_ = deque_->index_increment_by(index_, delta);
}
size_type ExternalPosition() const {
@@ -415,6 +423,15 @@
MaybeShrinkCapacity();
}
+ size_type pop_front_n(size_type count) {
+ size_type num_elements_to_pop = std::min(count, size());
+ size_type new_begin = index_increment_by(begin_, num_elements_to_pop);
+ DestroyRange(begin_, new_begin);
+ begin_ = new_begin;
+ MaybeShrinkCapacity();
+ return num_elements_to_pop;
+ }
+
void pop_back() {
DCHECK(!empty());
end_ = index_prev(end_);
@@ -422,6 +439,15 @@
MaybeShrinkCapacity();
}
+ size_type pop_back_n(size_type count) {
+ size_type num_elements_to_pop = std::min(count, size());
+ size_type new_end = index_increment_by(end_, -num_elements_to_pop);
+ DestroyRange(new_end, end_);
+ end_ = new_end;
+ MaybeShrinkCapacity();
+ return num_elements_to_pop;
+ }
+
void swap(QuicCircularDeque& other) {
using std::swap;
swap(begin_, other.begin_);
@@ -683,6 +709,15 @@
return index == data_capacity() - 1 ? 0 : index + 1;
}
+ size_type index_increment_by(size_type index, difference_type delta) const {
+ if (delta == 0) {
+ return index;
+ }
+
+ DCHECK_LT(std::abs(delta), data_capacity());
+ return (index + data_capacity() + delta) % data_capacity();
+ }
+
// Empty base-class optimization: bundle storage for our allocator together
// with the fields we had to store anyway, via inheriting from the allocator,
// so this allocator instance doesn't consume any storage when its type has no
diff --git a/quic/core/quic_circular_deque_test.cc b/quic/core/quic_circular_deque_test.cc
index f9774ee..8844d92 100644
--- a/quic/core/quic_circular_deque_test.cc
+++ b/quic/core/quic_circular_deque_test.cc
@@ -660,6 +660,41 @@
ASSERT_GT(&dq1.front(), &dq1.back());
// dq1 destructs with wrapped data.
}
+
+ { // Pop n elements from front.
+ QuicCircularDeque<Foo, 4, CountingAllocator<Foo>> dq2(5);
+ for (size_t i = 0; i < dq2.size(); ++i) {
+ dq2[i].Set(i + 1);
+ }
+ EXPECT_THAT(dq2, ElementsAre(Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)));
+
+ EXPECT_EQ(2u, dq2.pop_front_n(2));
+ EXPECT_THAT(dq2, ElementsAre(Foo(3), Foo(4), Foo(5)));
+
+ EXPECT_EQ(3u, dq2.pop_front_n(100));
+ EXPECT_TRUE(dq2.empty());
+ }
+
+ { // Pop n elements from back.
+ QuicCircularDeque<Foo, 4, CountingAllocator<Foo>> dq3(6);
+ for (size_t i = 0; i < dq3.size(); ++i) {
+ dq3[i].Set(i + 1);
+ }
+ EXPECT_THAT(dq3,
+ ElementsAre(Foo(1), Foo(2), Foo(3), Foo(4), Foo(5), Foo(6)));
+
+ ShiftRight(&dq3, true);
+ ShiftRight(&dq3, true);
+ ShiftRight(&dq3, true);
+ EXPECT_THAT(dq3,
+ ElementsAre(Foo(4), Foo(5), Foo(6), Foo(1), Foo(2), Foo(3)));
+
+ EXPECT_EQ(2u, dq3.pop_back_n(2));
+ EXPECT_THAT(dq3, ElementsAre(Foo(4), Foo(5), Foo(6), Foo(1)));
+
+ EXPECT_EQ(2u, dq3.pop_back_n(2));
+ EXPECT_THAT(dq3, ElementsAre(Foo(4), Foo(5)));
+ }
}
TEST(QuicCircularDeque, Allocation) {
